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

arm-ehjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-expr
Last change on this file since 5cdeecd was 5cdeecd, checked in by Andrew Beach <ajbeach@…>, 21 months 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.