Changeset 720a007


Ignore:
Timestamp:
Mar 14, 2018, 2:06:29 PM (4 years ago)
Author:
Rob Schluntz <rschlunt@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, with_gc
Children:
753f13c9
Parents:
6a276a0
Message:

Implement new fallthrough semantics

Location:
src/ControlStruct
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/ControlStruct/MLEMutator.cc

    r6a276a0 r720a007  
    1010// Created On       : Mon May 18 07:44:20 2015
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Thu Aug  4 11:21:32 2016
    13 // Update Count     : 202
     12// Last Modified On : Thu Mar  8 17:08:25 2018
     13// Update Count     : 219
    1414//
    1515
     
    3838        }
    3939        namespace {
    40                 Statement * isLoop( Statement * stmt ) { return dynamic_cast< WhileStmt * >( stmt ) ? stmt : dynamic_cast< ForStmt * >( stmt ) ? stmt : 0; }
    41         }
     40                bool isLoop( const MLEMutator::Entry & e ) { return dynamic_cast< WhileStmt * >( e.get_controlStructure() ) || dynamic_cast< ForStmt * >( e.get_controlStructure() ); }
     41                bool isSwitch( const MLEMutator::Entry & e ) { return dynamic_cast< SwitchStmt *>( e.get_controlStructure() ); }
     42
     43                bool isBreakTarget( const MLEMutator::Entry & e ) { return isLoop( e ) || isSwitch( e ) || dynamic_cast< CompoundStmt *>( e.get_controlStructure() ); }
     44                bool isContinueTarget( const MLEMutator::Entry & e ) { return isLoop( e ); }
     45                bool isFallthroughTarget( const MLEMutator::Entry & e ) { return dynamic_cast< CaseStmt *>( e.get_controlStructure() );; }
     46                bool isFallthroughDefaultTarget( const MLEMutator::Entry & e ) { return isSwitch( e ); }
     47        } // namespace
    4248
    4349        // break labels have to come after the statement they break out of, so mutate a statement, then if they inform us
    4450        // through the breakLabel field tha they need a place to jump to on a break statement, add the break label to the
    4551        // body of statements
    46         void MLEMutator::fixBlock( std::list< Statement * > &kids ) {
     52        void MLEMutator::fixBlock( std::list< Statement * > &kids, bool caseClause ) {
     53                SemanticErrorException errors;
     54
    4755                for ( std::list< Statement * >::iterator k = kids.begin(); k != kids.end(); k++ ) {
    48                         *k = (*k)->acceptMutator(*visitor);
     56                        if ( caseClause ) {
     57                                // once a label is seen, it's no longer a valid fallthrough target
     58                                for ( Label & l : (*k)->labels ) {
     59                                        fallthroughLabels.erase( l );
     60                                }
     61                        }
     62
     63                        // aggregate errors since the PassVisitor mutate loop was unrollled
     64                        try {
     65                                *k = (*k)->acceptMutator(*visitor);
     66                        } catch( SemanticErrorException &e ) {
     67                                errors.append( e );
     68                        }
    4969
    5070                        if ( ! get_breakLabel().empty() ) {
     
    5575                        } // if
    5676                } // for
     77
     78                if ( ! errors.isEmpty() ) {
     79                        throw errors;
     80                }
    5781        }
    5882
     
    6387                        Label brkLabel = generator->newLabel("blockBreak", cmpndStmt);
    6488                        enclosingControlStructures.push_back( Entry( cmpndStmt, brkLabel ) );
     89                        GuardAction( [this]() { enclosingControlStructures.pop_back(); } );
    6590                } // if
    6691
     
    7499                                set_breakLabel( enclosingControlStructures.back().useBreakExit() );
    75100                        } // if
    76                         enclosingControlStructures.pop_back();
    77101                } // if
    78102        }
     
    112136                                        if ( isContinue ) {
    113137                                                // continue target is outermost loop
    114                                                 targetEntry = std::find_if( enclosingControlStructures.rbegin(), enclosingControlStructures.rend(), [](Entry &e) { return isLoop( e.get_controlStructure() ); } );
     138                                                targetEntry = std::find_if( enclosingControlStructures.rbegin(), enclosingControlStructures.rend(), isContinueTarget );
    115139                                        } else {
    116                                                 // break target is outmost control structure
    117                                                 if ( enclosingControlStructures.empty() ) SemanticError( branchStmt->location, "'break' outside a loop, switch, or labelled block" );
    118                                                 targetEntry = enclosingControlStructures.rbegin();
     140                                                // break target is outermost loop, switch, or block control structure
     141                                                if ( enclosingControlStructures.empty() ) SemanticError( branchStmt->location, "'break' outside a loop, 'switch', or labelled block" );
     142                                                targetEntry = std::find_if( enclosingControlStructures.rbegin(), enclosingControlStructures.rend(), isBreakTarget );
    119143                                        } // if
    120144                                } else {
     
    123147                                } // if
    124148                                // ensure that selected target is valid
    125                                 if ( targetEntry == enclosingControlStructures.rend() || (isContinue && ! isLoop( targetEntry->get_controlStructure() ) ) ) {
     149                                if ( targetEntry == enclosingControlStructures.rend() || (isContinue && ! isContinueTarget( *targetEntry ) ) ) {
    126150                                        SemanticError( branchStmt->location, toString( (isContinue ? "'continue'" : "'break'"), " target must be an enclosing ", (isContinue ? "loop: " : "control structure: "), originalTarget ) );
    127151                                } // if
    128152                                break;
    129153                        }
     154                        case BranchStmt::FallThrough:
     155                                targetEntry = std::find_if( enclosingControlStructures.rbegin(), enclosingControlStructures.rend(), isFallthroughTarget );
     156                                // ensure that selected target is valid
     157                                if ( targetEntry == enclosingControlStructures.rend() ) {
     158                                        SemanticError( branchStmt->location, "'fallthrough' must be enclosed in a 'switch' or 'choose'" );
     159                                } // if
     160                                if ( branchStmt->get_target() != "" ) {
     161                                        // labelled fallthrough
     162                                        // target must be in the set of valid fallthrough labels
     163                                        if ( ! fallthroughLabels.count( branchStmt->get_target() ) ) {
     164                                                SemanticError( branchStmt->location, toString( "'fallthrough' target must be a later case statement: ", originalTarget ) );
     165                                        }
     166                                        return new BranchStmt( originalTarget, BranchStmt::Goto );
     167                                }
     168                                break;
     169                        case BranchStmt::FallThroughDefault: {
     170                                // fallthrough default
     171                                targetEntry = std::find_if( enclosingControlStructures.rbegin(), enclosingControlStructures.rend(), isFallthroughDefaultTarget );
     172
     173                                // ensure that fallthrough is within a switch or choose
     174                                if ( targetEntry == enclosingControlStructures.rend() ) {
     175                                        SemanticError( branchStmt->location, "'fallthrough' must be enclosed in a 'switch' or 'choose'" );
     176                                } // if
     177
     178                                // ensure that switch or choose has a default clause
     179                                SwitchStmt * switchStmt = strict_dynamic_cast< SwitchStmt * >( targetEntry->get_controlStructure() );
     180                                bool foundDefault = false;
     181                                for ( Statement * stmt : switchStmt->statements ) {
     182                                        CaseStmt * caseStmt = strict_dynamic_cast< CaseStmt * >( stmt );
     183                                        if ( caseStmt->isDefault() ) {
     184                                                foundDefault = true;
     185                                        } // if
     186                                } // for
     187                                if ( ! foundDefault ) {
     188                                        SemanticError( branchStmt->location, "'fallthrough default' must be enclosed in a 'switch' or 'choose' control structure with a 'default' clause" );
     189                                }
     190                                break;
     191                        }
     192
    130193                        default:
    131194                                assert( false );
     
    142205                                assert( targetEntry->useContExit() != "");
    143206                                exitLabel = targetEntry->useContExit();
     207                                break;
     208                  case BranchStmt::FallThrough:
     209                                assert( targetEntry->useFallExit() != "");
     210                                exitLabel = targetEntry->useFallExit();
     211                                break;
     212                  case BranchStmt::FallThroughDefault:
     213                                assert( targetEntry->useFallDefaultExit() != "");
     214                                exitLabel = targetEntry->useFallDefaultExit();
     215                                // check that fallthrough default comes before the default clause
     216                                if ( ! targetEntry->isFallDefaultValid() ) {
     217                                        SemanticError( branchStmt->location, "'fallthrough default' must precede the 'default' clause" );
     218                                }
    144219                                break;
    145220                  default:
     
    187262                Label contLabel = generator->newLabel("loopContinue", loopStmt);
    188263                enclosingControlStructures.push_back( Entry( loopStmt, brkLabel, contLabel ) );
     264                GuardAction( [this]() { enclosingControlStructures.pop_back(); } );
    189265        }
    190266
     
    197273
    198274                // this will take the necessary steps to add definitions of the previous two labels, if they are used.
    199                 loopStmt->set_body( mutateLoop( loopStmt->get_body(), e ) );
    200                 enclosingControlStructures.pop_back();
     275                loopStmt->body = mutateLoop( loopStmt->get_body(), e );
    201276                return loopStmt;
    202277        }
     
    224299                        Label brkLabel = generator->newLabel("blockBreak", ifStmt);
    225300                        enclosingControlStructures.push_back( Entry( ifStmt, brkLabel ) );
     301                        GuardAction( [this]() { enclosingControlStructures.pop_back(); } );
    226302                } // if
    227303        }
     
    233309                                set_breakLabel( enclosingControlStructures.back().useBreakExit() );
    234310                        } // if
    235                         enclosingControlStructures.pop_back();
    236311                } // if
    237312                return ifStmt;
     
    240315        void MLEMutator::premutate( CaseStmt *caseStmt ) {
    241316                visit_children = false;
     317
     318                // mark default as seen before visiting its statements to catch default loops
     319                if ( caseStmt->isDefault() ) {
     320                        enclosingControlStructures.back().seenDefault();
     321                } // if
     322
    242323                caseStmt->condition = maybeMutate( caseStmt->condition, *visitor );
    243                 fixBlock( caseStmt->stmts );
     324                Label fallLabel = generator->newLabel( "fallThrough", caseStmt );
     325                {
     326                        // ensure that stack isn't corrupted by exceptions in fixBlock
     327                        auto guard = makeFuncGuard( [&]() { enclosingControlStructures.push_back( Entry( caseStmt, fallLabel ) ); }, [this]() { enclosingControlStructures.pop_back(); } );
     328
     329                        // empty case statement
     330                        if( ! caseStmt->stmts.empty() ) {
     331                                // the parser ensures that all statements in a case are grouped into a block
     332                                CompoundStmt * block = strict_dynamic_cast< CompoundStmt * >( caseStmt->stmts.front() );
     333                                fixBlock( block->kids, true );
     334
     335                                // add fallthrough label if necessary
     336                                assert( ! enclosingControlStructures.empty() );
     337                                if ( enclosingControlStructures.back().isFallUsed() ) {
     338                                        std::list<Label> ls{ enclosingControlStructures.back().useFallExit() };
     339                                        caseStmt->stmts.push_back( new NullStmt( ls ) );
     340                                } // if
     341                        } // if
     342                }
     343                assert( ! enclosingControlStructures.empty() );
     344                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() ) );
     345                if ( caseStmt->isDefault() ) {
     346                        if ( enclosingControlStructures.back().isFallDefaultUsed() ) {
     347                                // add fallthrough default label if necessary
     348                                std::list<Label> ls{ enclosingControlStructures.back().useFallDefaultExit() };
     349                                caseStmt->stmts.push_front( new NullStmt( ls ) );
     350                        } // if
     351                } // if
    244352        }
    245353
     
    247355                // generate a label for breaking out of a labeled switch
    248356                Label brkLabel = generator->newLabel("switchBreak", switchStmt);
    249                 enclosingControlStructures.push_back( Entry(switchStmt, brkLabel) );
     357                auto it = std::find_if( switchStmt->statements.rbegin(), switchStmt->statements.rend(), [](Statement * stmt) {
     358                        CaseStmt * caseStmt = strict_dynamic_cast< CaseStmt * >( stmt );
     359                        return caseStmt->isDefault();
     360                });
     361                CaseStmt * defaultCase = it != switchStmt->statements.rend() ? strict_dynamic_cast<CaseStmt *>( *it ) : nullptr;
     362                Label fallDefaultLabel = defaultCase ? generator->newLabel( "fallThroughDefault", defaultCase ) : "";
     363                enclosingControlStructures.push_back( Entry(switchStmt, brkLabel, fallDefaultLabel) );
     364                GuardAction( [this]() { enclosingControlStructures.pop_back(); } );
     365
     366                // Collect valid labels for fallthrough. This is initially all labels at the same level as a case statement.
     367                // As labels are seen during traversal, they are removed, since fallthrough is not allowed to jump backwards.
     368                for ( Statement * stmt : switchStmt->statements ) {
     369                        CaseStmt * caseStmt = strict_dynamic_cast< CaseStmt * >( stmt );
     370                        if ( caseStmt->stmts.empty() ) continue;
     371                        CompoundStmt * block = dynamic_cast< CompoundStmt * >( caseStmt->stmts.front() );
     372                        for ( Statement * stmt : block->kids ) {
     373                                for ( Label & l : stmt->labels ) {
     374                                        fallthroughLabels.insert( l );
     375                                }
     376                        }
     377                }
    250378        }
    251379
     
    272400
    273401                assert ( enclosingControlStructures.back() == switchStmt );
    274                 enclosingControlStructures.pop_back();
    275402                return switchStmt;
    276403        }
  • src/ControlStruct/MLEMutator.h

    r6a276a0 r720a007  
    1010// Created On       : Mon May 18 07:44:20 2015
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Sat Jul 22 09:19:59 2017
    13 // Update Count     : 35
     12// Last Modified On : Thu Mar  8 16:42:32 2018
     13// Update Count     : 41
    1414//
    1515
     
    1919#include <map>                     // for map
    2020#include <string>                  // for string
     21#include <set>                     // for unordered_set
    2122
    2223#include "Common/PassVisitor.h"
     
    2930        class LabelGenerator;
    3031
    31         class MLEMutator : public WithVisitorRef<MLEMutator>, public WithShortCircuiting {
     32        class MLEMutator : public WithVisitorRef<MLEMutator>, public WithShortCircuiting, public WithGuards {
     33          public:
    3234                class Entry;
    33 
    34           public:
    3535                MLEMutator( std::map<Label, Statement *> *t, LabelGenerator *gen = 0 ) : targetTable( t ), breakLabel(std::string("")), generator( gen ) {}
    3636                ~MLEMutator();
     
    5252                Label &get_breakLabel() { return breakLabel; }
    5353                void set_breakLabel( Label newValue ) { breakLabel = newValue; }
    54           private:
     54
    5555                class Entry {
    5656                  public:
    57                         explicit Entry( Statement *_loop, Label _breakExit, Label _contExit = Label("") ) :
    58                                 loop( _loop ), breakExit( _breakExit ), contExit( _contExit ), breakUsed(false), contUsed(false) {}
     57                        // specialized constructors for each combination of statement with labelled break/continue/fallthrough that is valid to cleanup the use cases
     58                        explicit Entry( ForStmt *stmt, Label breakExit, Label contExit ) :
     59                                stmt( stmt ), breakExit( breakExit ), contExit( contExit ) {}
    5960
    60                         bool operator==( const Statement *stmt ) { return loop == stmt; }
    61                         bool operator!=( const Statement *stmt ) { return loop != stmt; }
     61                        explicit Entry( WhileStmt *stmt, Label breakExit, Label contExit ) :
     62                                stmt( stmt ), breakExit( breakExit ), contExit( contExit ) {}
    6263
    63                         bool operator==( const Entry &other ) { return loop == other.get_controlStructure(); }
     64                        explicit Entry( CompoundStmt *stmt, Label breakExit ) :
     65                                stmt( stmt ), breakExit( breakExit ) {}
    6466
    65                         Statement *get_controlStructure() const { return loop; }
     67                        explicit Entry( IfStmt *stmt, Label breakExit ) :
     68                                stmt( stmt ), breakExit( breakExit ) {}
     69
     70                        explicit Entry( CaseStmt *stmt, Label fallExit ) :
     71                                stmt( stmt ), fallExit( fallExit ) {}
     72
     73                        explicit Entry( SwitchStmt *stmt, Label breakExit, Label fallDefaultExit ) :
     74                                stmt( stmt ), breakExit( breakExit ), fallDefaultExit( fallDefaultExit ) {}
     75
     76                        bool operator==( const Statement *other ) { return stmt == other; }
     77                        bool operator!=( const Statement *other ) { return stmt != other; }
     78
     79                        bool operator==( const Entry &other ) { return stmt == other.get_controlStructure(); }
     80
     81                        Statement *get_controlStructure() const { return stmt; }
    6682
    6783                        Label useContExit() { contUsed = true; return contExit; }
    6884                        Label useBreakExit() { breakUsed = true; return breakExit; }
     85                        Label useFallExit() { fallUsed = true; return fallExit; }
     86                        Label useFallDefaultExit() { fallDefaultUsed = true; return fallDefaultExit; }
    6987
    7088                        bool isContUsed() const { return contUsed; }
    7189                        bool isBreakUsed() const { return breakUsed; }
     90                        bool isFallUsed() const { return fallUsed; }
     91                        bool isFallDefaultUsed() const { return fallDefaultUsed; }
     92                        void seenDefault() { fallDefaultValid = false; }
     93                        bool isFallDefaultValid() const { return fallDefaultValid; }
    7294                  private:
    73                         Statement *loop;
    74                         Label breakExit, contExit;
    75                         bool breakUsed, contUsed;
     95                        Statement *stmt;
     96                        Label breakExit, contExit, fallExit, fallDefaultExit;
     97                        bool breakUsed = false, contUsed = false, fallUsed = false, fallDefaultUsed = false;
     98                        bool fallDefaultValid = true;
    7699                };
    77100
     101          private:
    78102                std::map< Label, Statement * > *targetTable;
     103                std::set< Label > fallthroughLabels;
    79104                std::list< Entry > enclosingControlStructures;
    80105                Label breakLabel;
     
    87112                Statement * posthandleLoopStmt( LoopClass * loopStmt );
    88113
    89                 void fixBlock( std::list< Statement * > &kids );
     114                void fixBlock( std::list< Statement * > &kids, bool caseClause = false );
    90115        };
    91116} // namespace ControlStruct
Note: See TracChangeset for help on using the changeset viewer.