source: src/ControlStruct/MLEMutator.cc@ 2fa5bd2

ADT arm-eh ast-experimental enum forall-pointer-decay jacob/cs343-translation new-ast-unique-expr pthread-emulation qualifiedEnum
Last change on this file since 2fa5bd2 was 397c101a, checked in by Thierry Delisle <tdelisle@…>, 6 years ago

Fix bug where 'continue' would incorrectly claim to skip initialization Fixes #150
  • Property mode set to 100644
File size: 17.6 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
7// MLEMutator.cc --
8//
9// Author : Rodolfo G. Esteves
10// Created On : Mon May 18 07:44:20 2015
11// Last Modified By : Peter A. Buhr
12// Last Modified On : Tue Oct 22 17:22:44 2019
13// Update Count : 220
14//
15
16// NOTE: There are two known subtle differences from the code that uC++ generates for the same input
17// -CFA puts the break label inside at the end of a switch, uC++ puts it after
18// -CFA puts the break label after a block, uC++ puts it inside at the end
19// It is unclear if these differences are important, but if they are, then the fix would go in this file, since this is
20// where these labels are generated.
21
22#include <ext/alloc_traits.h> // for __alloc_traits<>::value_type
23#include <algorithm> // for find, find_if
24#include <cassert> // for assert, assertf
25#include <memory> // for allocator_traits<>::value_...
26
27#include "Common/utility.h" // for toString, operator+
28#include "ControlStruct/LabelGenerator.h" // for LabelGenerator
29#include "MLEMutator.h"
30#include "SynTree/Attribute.h" // for Attribute
31#include "SynTree/Expression.h" // for Expression
32#include "SynTree/Statement.h" // for BranchStmt, CompoundStmt
33
34namespace ControlStruct {
35 MLEMutator::~MLEMutator() {
36 delete targetTable;
37 targetTable = 0;
38 }
39 namespace {
40 bool isLoop( const MLEMutator::Entry & e ) { return dynamic_cast< WhileStmt * >( e.get_controlStructure() ) || dynamic_cast< ForStmt * >( e.get_controlStructure() ); }
41 bool isSwitch( const MLEMutator::Entry & e ) { return dynamic_cast< SwitchStmt *>( e.get_controlStructure() ); }
42
43 bool isBreakTarget( const MLEMutator::Entry & e ) { return isLoop( e ) || isSwitch( e ) || dynamic_cast< CompoundStmt *>( e.get_controlStructure() ); }
44 bool isContinueTarget( const MLEMutator::Entry & e ) { return isLoop( e ); }
45 bool isFallthroughTarget( const MLEMutator::Entry & e ) { return dynamic_cast< CaseStmt *>( e.get_controlStructure() );; }
46 bool isFallthroughDefaultTarget( const MLEMutator::Entry & e ) { return isSwitch( e ); }
47 } // namespace
48
49 // break labels have to come after the statement they break out of, so mutate a statement, then if they inform us
50 // through the breakLabel field tha they need a place to jump to on a break statement, add the break label to the
51 // body of statements
52 void MLEMutator::fixBlock( std::list< Statement * > &kids, bool caseClause ) {
53 SemanticErrorException errors;
54
55 for ( std::list< Statement * >::iterator k = kids.begin(); k != kids.end(); k++ ) {
56 if ( caseClause ) {
57 // once a label is seen, it's no longer a valid fallthrough target
58 for ( Label & l : (*k)->labels ) {
59 fallthroughLabels.erase( l );
60 }
61 }
62
63 // aggregate errors since the PassVisitor mutate loop was unrollled
64 try {
65 *k = (*k)->acceptMutator(*visitor);
66 } catch( SemanticErrorException &e ) {
67 errors.append( e );
68 }
69
70 if ( ! get_breakLabel().empty() ) {
71 std::list< Statement * >::iterator next = k+1;
72 std::list<Label> ls; ls.push_back( get_breakLabel() );
73 kids.insert( next, new NullStmt( ls ) );
74 set_breakLabel("");
75 } // if
76 } // for
77
78 if ( ! errors.isEmpty() ) {
79 throw errors;
80 }
81 }
82
83 void MLEMutator::premutate( CompoundStmt *cmpndStmt ) {
84 visit_children = false;
85 bool labeledBlock = !(cmpndStmt->labels.empty());
86 if ( labeledBlock ) {
87 Label brkLabel = generator->newLabel("blockBreak", cmpndStmt);
88 enclosingControlStructures.push_back( Entry( cmpndStmt, brkLabel ) );
89 GuardAction( [this]() { enclosingControlStructures.pop_back(); } );
90 } // if
91
92 // a child statement may set the break label - if they do, attach it to the next statement
93 std::list< Statement * > &kids = cmpndStmt->kids;
94 fixBlock( kids );
95
96 if ( labeledBlock ) {
97 assert( ! enclosingControlStructures.empty() );
98 if ( ! enclosingControlStructures.back().useBreakExit().empty() ) {
99 set_breakLabel( enclosingControlStructures.back().useBreakExit() );
100 } // if
101 } // if
102 }
103
104
105 void addUnused( Statement * stmt, const Label & originalTarget ) {
106 // break/continue without a label doesn't need unused attribute
107 if ( originalTarget == "" ) return;
108 // add unused attribute to the originalTarget of a labelled break/continue
109 for ( Label & l : stmt->get_labels() ) {
110 // find the label to add unused attribute to
111 if ( l == originalTarget ) {
112 for ( Attribute * attr : l.get_attributes() ) {
113 // ensure attribute isn't added twice
114 if ( attr->get_name() == "unused" ) return;
115 }
116 l.get_attributes().push_back( new Attribute( "unused" ) );
117 return;
118 }
119 }
120 assertf( false, "Could not find label '%s' on statement %s", originalTarget.get_name().c_str(), toString( stmt ).c_str() );
121 }
122
123
124 Statement *MLEMutator::postmutate( BranchStmt *branchStmt ) throw ( SemanticErrorException ) {
125 std::string originalTarget = branchStmt->originalTarget;
126
127 std::list< Entry >::reverse_iterator targetEntry;
128 switch ( branchStmt->get_type() ) {
129 case BranchStmt::Goto:
130 return branchStmt;
131 case BranchStmt::Continue:
132 case BranchStmt::Break: {
133 bool isContinue = branchStmt->get_type() == BranchStmt::Continue;
134 // unlabeled break/continue
135 if ( branchStmt->get_target() == "" ) {
136 if ( isContinue ) {
137 // continue target is outermost loop
138 targetEntry = std::find_if( enclosingControlStructures.rbegin(), enclosingControlStructures.rend(), isContinueTarget );
139 } else {
140 // break target is outermost loop, switch, or block control structure
141 if ( enclosingControlStructures.empty() ) SemanticError( branchStmt->location, "'break' outside a loop, 'switch', or labelled block" );
142 targetEntry = std::find_if( enclosingControlStructures.rbegin(), enclosingControlStructures.rend(), isBreakTarget );
143 } // if
144 } else {
145 // labeled break/continue - lookup label in table to find attached control structure
146 targetEntry = std::find( enclosingControlStructures.rbegin(), enclosingControlStructures.rend(), (*targetTable)[branchStmt->get_target()] );
147 } // if
148 // ensure that selected target is valid
149 if ( targetEntry == enclosingControlStructures.rend() || (isContinue && ! isContinueTarget( *targetEntry ) ) ) {
150 SemanticError( branchStmt->location, toString( (isContinue ? "'continue'" : "'break'"), " target must be an enclosing ", (isContinue ? "loop: " : "control structure: "), originalTarget ) );
151 } // if
152 break;
153 }
154 case BranchStmt::FallThrough:
155 targetEntry = std::find_if( enclosingControlStructures.rbegin(), enclosingControlStructures.rend(), isFallthroughTarget );
156 // ensure that selected target is valid
157 if ( targetEntry == enclosingControlStructures.rend() ) {
158 SemanticError( branchStmt->location, "'fallthrough' must be enclosed in a 'switch' or 'choose'" );
159 } // if
160 if ( branchStmt->get_target() != "" ) {
161 // labelled fallthrough
162 // target must be in the set of valid fallthrough labels
163 if ( ! fallthroughLabels.count( branchStmt->get_target() ) ) {
164 SemanticError( branchStmt->location, toString( "'fallthrough' target must be a later case statement: ", originalTarget ) );
165 }
166 return new BranchStmt( originalTarget, BranchStmt::Goto );
167 }
168 break;
169 case BranchStmt::FallThroughDefault: {
170 // fallthrough default
171 targetEntry = std::find_if( enclosingControlStructures.rbegin(), enclosingControlStructures.rend(), isFallthroughDefaultTarget );
172
173 // ensure that fallthrough is within a switch or choose
174 if ( targetEntry == enclosingControlStructures.rend() ) {
175 SemanticError( branchStmt->location, "'fallthrough' must be enclosed in a 'switch' or 'choose'" );
176 } // if
177
178 // ensure that switch or choose has a default clause
179 SwitchStmt * switchStmt = strict_dynamic_cast< SwitchStmt * >( targetEntry->get_controlStructure() );
180 bool foundDefault = false;
181 for ( Statement * stmt : switchStmt->statements ) {
182 CaseStmt * caseStmt = strict_dynamic_cast< CaseStmt * >( stmt );
183 if ( caseStmt->isDefault() ) {
184 foundDefault = true;
185 } // if
186 } // for
187 if ( ! foundDefault ) {
188 SemanticError( branchStmt->location, "'fallthrough default' must be enclosed in a 'switch' or 'choose' control structure with a 'default' clause" );
189 }
190 break;
191 }
192
193 default:
194 assert( false );
195 } // switch
196
197 // branch error checks, get the appropriate label name and create a goto
198 Label exitLabel;
199 switch ( branchStmt->type ) {
200 case BranchStmt::Break:
201 assert( targetEntry->useBreakExit() != "");
202 exitLabel = targetEntry->useBreakExit();
203 break;
204 case BranchStmt::Continue:
205 assert( targetEntry->useContExit() != "");
206 exitLabel = targetEntry->useContExit();
207 break;
208 case BranchStmt::FallThrough:
209 assert( targetEntry->useFallExit() != "");
210 exitLabel = targetEntry->useFallExit();
211 break;
212 case BranchStmt::FallThroughDefault:
213 assert( targetEntry->useFallDefaultExit() != "");
214 exitLabel = targetEntry->useFallDefaultExit();
215 // check that fallthrough default comes before the default clause
216 if ( ! targetEntry->isFallDefaultValid() ) {
217 SemanticError( branchStmt->location, "'fallthrough default' must precede the 'default' clause" );
218 }
219 break;
220 default:
221 assert(0); // shouldn't be here
222 } // switch
223
224 // add unused attribute to label to silence warnings
225 addUnused( targetEntry->get_controlStructure(), branchStmt->originalTarget );
226
227 // transform break/continue statements into goto to simplify later handling of branches
228 delete branchStmt;
229 return new BranchStmt( exitLabel, BranchStmt::Goto );
230 }
231
232 Statement *MLEMutator::mutateLoop( Statement *bodyLoop, Entry &e ) {
233 // only generate these when needed
234 if( !e.isContUsed() && !e.isBreakUsed() ) return bodyLoop;
235
236 // ensure loop body is a block
237 CompoundStmt * newBody = new CompoundStmt();
238 newBody->get_kids().push_back( bodyLoop );
239
240 if ( e.isContUsed() ) {
241 // continue label goes in the body as the last statement
242 std::list< Label > labels; labels.push_back( e.useContExit() );
243 newBody->get_kids().push_back( new NullStmt( labels ) );
244 } // if
245
246 if ( e.isBreakUsed() ) {
247 // break label goes after the loop -- it'll get set by the outer mutator if we do this
248 set_breakLabel( e.useBreakExit() );
249 } // if
250
251 return newBody;
252 }
253
254 template< typename LoopClass >
255 void MLEMutator::prehandleLoopStmt( LoopClass * loopStmt ) {
256 // remember this as the most recent enclosing loop, then mutate the body of the loop -- this will determine
257 // whether brkLabel and contLabel are used with branch statements and will recursively do the same to nested
258 // loops
259 Label brkLabel = generator->newLabel("loopBreak", loopStmt);
260 Label contLabel = generator->newLabel("loopContinue", loopStmt);
261 enclosingControlStructures.push_back( Entry( loopStmt, brkLabel, contLabel ) );
262 GuardAction( [this]() { enclosingControlStructures.pop_back(); } );
263 }
264
265 template< typename LoopClass >
266 Statement * MLEMutator::posthandleLoopStmt( LoopClass * loopStmt ) {
267 assert( ! enclosingControlStructures.empty() );
268 Entry &e = enclosingControlStructures.back();
269 // sanity check that the enclosing loops have been popped correctly
270 assert ( e == loopStmt );
271
272 // this will take the necessary steps to add definitions of the previous two labels, if they are used.
273 loopStmt->body = mutateLoop( loopStmt->get_body(), e );
274 return loopStmt;
275 }
276
277 void MLEMutator::premutate( WhileStmt * whileStmt ) {
278 return prehandleLoopStmt( whileStmt );
279 }
280
281 void MLEMutator::premutate( ForStmt * forStmt ) {
282 return prehandleLoopStmt( forStmt );
283 }
284
285 Statement * MLEMutator::postmutate( WhileStmt * whileStmt ) {
286 return posthandleLoopStmt( whileStmt );
287 }
288
289 Statement * MLEMutator::postmutate( ForStmt * forStmt ) {
290 return posthandleLoopStmt( forStmt );
291 }
292
293 void MLEMutator::premutate( IfStmt * ifStmt ) {
294 // generate a label for breaking out of a labeled if
295 bool labeledBlock = !(ifStmt->get_labels().empty());
296 if ( labeledBlock ) {
297 Label brkLabel = generator->newLabel("blockBreak", ifStmt);
298 enclosingControlStructures.push_back( Entry( ifStmt, brkLabel ) );
299 GuardAction( [this]() { enclosingControlStructures.pop_back(); } );
300 } // if
301 }
302
303 Statement * MLEMutator::postmutate( IfStmt * ifStmt ) {
304 bool labeledBlock = !(ifStmt->get_labels().empty());
305 if ( labeledBlock ) {
306 if ( ! enclosingControlStructures.back().useBreakExit().empty() ) {
307 set_breakLabel( enclosingControlStructures.back().useBreakExit() );
308 } // if
309 } // if
310 return ifStmt;
311 }
312
313 void MLEMutator::premutate( TryStmt * tryStmt ) {
314 // generate a label for breaking out of a labeled if
315 bool labeledBlock = !(tryStmt->get_labels().empty());
316 if ( labeledBlock ) {
317 Label brkLabel = generator->newLabel("blockBreak", tryStmt);
318 enclosingControlStructures.push_back( Entry( tryStmt, brkLabel ) );
319 GuardAction( [this]() { enclosingControlStructures.pop_back(); } );
320 } // if
321 }
322
323 Statement * MLEMutator::postmutate( TryStmt * tryStmt ) {
324 bool labeledBlock = !(tryStmt->get_labels().empty());
325 if ( labeledBlock ) {
326 if ( ! enclosingControlStructures.back().useBreakExit().empty() ) {
327 set_breakLabel( enclosingControlStructures.back().useBreakExit() );
328 } // if
329 } // if
330 return tryStmt;
331 }
332
333 void MLEMutator::premutate( CaseStmt *caseStmt ) {
334 visit_children = false;
335
336 // mark default as seen before visiting its statements to catch default loops
337 if ( caseStmt->isDefault() ) {
338 enclosingControlStructures.back().seenDefault();
339 } // if
340
341 caseStmt->condition = maybeMutate( caseStmt->condition, *visitor );
342 Label fallLabel = generator->newLabel( "fallThrough", caseStmt );
343 {
344 // ensure that stack isn't corrupted by exceptions in fixBlock
345 auto guard = makeFuncGuard( [&]() { enclosingControlStructures.push_back( Entry( caseStmt, fallLabel ) ); }, [this]() { enclosingControlStructures.pop_back(); } );
346
347 // empty case statement
348 if( ! caseStmt->stmts.empty() ) {
349 // the parser ensures that all statements in a case are grouped into a block
350 CompoundStmt * block = strict_dynamic_cast< CompoundStmt * >( caseStmt->stmts.front() );
351 fixBlock( block->kids, true );
352
353 // add fallthrough label if necessary
354 assert( ! enclosingControlStructures.empty() );
355 if ( enclosingControlStructures.back().isFallUsed() ) {
356 std::list<Label> ls{ enclosingControlStructures.back().useFallExit() };
357 caseStmt->stmts.push_back( new NullStmt( ls ) );
358 } // if
359 } // if
360 }
361 assert( ! enclosingControlStructures.empty() );
362 assertf( dynamic_cast<SwitchStmt *>( enclosingControlStructures.back().get_controlStructure() ), "Control structure enclosing a case clause must be a switch, but is: %s", toCString( enclosingControlStructures.back().get_controlStructure() ) );
363 if ( caseStmt->isDefault() ) {
364 if ( enclosingControlStructures.back().isFallDefaultUsed() ) {
365 // add fallthrough default label if necessary
366 std::list<Label> ls{ enclosingControlStructures.back().useFallDefaultExit() };
367 caseStmt->stmts.push_front( new NullStmt( ls ) );
368 } // if
369 } // if
370 }
371
372 void MLEMutator::premutate( SwitchStmt *switchStmt ) {
373 // generate a label for breaking out of a labeled switch
374 Label brkLabel = generator->newLabel("switchBreak", switchStmt);
375 auto it = std::find_if( switchStmt->statements.rbegin(), switchStmt->statements.rend(), [](Statement * stmt) {
376 CaseStmt * caseStmt = strict_dynamic_cast< CaseStmt * >( stmt );
377 return caseStmt->isDefault();
378 });
379 CaseStmt * defaultCase = it != switchStmt->statements.rend() ? strict_dynamic_cast<CaseStmt *>( *it ) : nullptr;
380 Label fallDefaultLabel = defaultCase ? generator->newLabel( "fallThroughDefault", defaultCase ) : "";
381 enclosingControlStructures.push_back( Entry(switchStmt, brkLabel, fallDefaultLabel) );
382 GuardAction( [this]() { enclosingControlStructures.pop_back(); } );
383
384 // Collect valid labels for fallthrough. This is initially all labels at the same level as a case statement.
385 // As labels are seen during traversal, they are removed, since fallthrough is not allowed to jump backwards.
386 for ( Statement * stmt : switchStmt->statements ) {
387 CaseStmt * caseStmt = strict_dynamic_cast< CaseStmt * >( stmt );
388 if ( caseStmt->stmts.empty() ) continue;
389 CompoundStmt * block = dynamic_cast< CompoundStmt * >( caseStmt->stmts.front() );
390 for ( Statement * stmt : block->kids ) {
391 for ( Label & l : stmt->labels ) {
392 fallthroughLabels.insert( l );
393 }
394 }
395 }
396 }
397
398 Statement * MLEMutator::postmutate( SwitchStmt * switchStmt ) {
399 Entry &e = enclosingControlStructures.back();
400 assert ( e == switchStmt );
401
402 // only generate break label if labeled break is used
403 if ( e.isBreakUsed() ) {
404 // for the purposes of keeping switch statements uniform (i.e. all statements that are direct children of a
405 // switch should be CastStmts), append the exit label + break to the last case statement; create a default
406 // case if there are no cases
407 std::list< Statement * > &statements = switchStmt->statements;
408 if ( statements.empty() ) {
409 statements.push_back( CaseStmt::makeDefault() );
410 } // if
411
412 if ( CaseStmt * c = dynamic_cast< CaseStmt * >( statements.back() ) ) {
413 Statement * stmt = new BranchStmt( Label("brkLabel"), BranchStmt::Break );
414 stmt->labels.push_back( e.useBreakExit() );
415 c->stmts.push_back( stmt );
416 } else assert(0); // as of this point, all statements of a switch are still CaseStmts
417 } // if
418
419 assert ( enclosingControlStructures.back() == switchStmt );
420 return switchStmt;
421 }
422} // namespace ControlStruct
423
424// Local Variables: //
425// tab-width: 4 //
426// mode: c++ //
427// compile-command: "make install" //
428// End: //
Note: See TracBrowser for help on using the repository browser.