source: src/ControlStruct/MLEMutator.cc@ 48fda7a

ADT ast-experimental
Last change on this file since 48fda7a was 9feb34b, checked in by Andrew Beach <ajbeach@…>, 2 years ago

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