source: src/ControlStruct/MLEMutator.cc @ 884f3f67

ADTast-experimentalenumpthread-emulationqualifiedEnum
Last change on this file since 884f3f67 was a554e5f4, checked in by caparsons <caparson@…>, 3 years ago

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

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