source: src/ControlStruct/MLEMutator.cc @ 4eebbcc

ADTast-experimental
Last change on this file since 4eebbcc was f8965f4, checked in by Thierry Delisle <tdelisle@…>, 2 years ago

Removed unnecessary throw lists

  • 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/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                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.