source: src/ControlStruct/MLEMutator.cc@ 5cdeecd

ADT arm-eh ast-experimental enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox new-ast new-ast-unique-expr pthread-emulation qualifiedEnum
Last change on this file since 5cdeecd was 5cdeecd, checked in by Andrew Beach <ajbeach@…>, 6 years ago

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