diff options
Diffstat (limited to 'lib/Analysis/CFG.cpp')
-rw-r--r-- | lib/Analysis/CFG.cpp | 354 |
1 files changed, 205 insertions, 149 deletions
diff --git a/lib/Analysis/CFG.cpp b/lib/Analysis/CFG.cpp index 842a385..d9073aa 100644 --- a/lib/Analysis/CFG.cpp +++ b/lib/Analysis/CFG.cpp @@ -234,6 +234,12 @@ public: } }; +TryResult bothKnownTrue(TryResult R1, TryResult R2) { + if (!R1.isKnown() || !R2.isKnown()) + return TryResult(); + return TryResult(R1.isTrue() && R2.isTrue()); +} + class reverse_children { llvm::SmallVector<Stmt *, 12> childrenBuf; ArrayRef<Stmt*> children; @@ -300,7 +306,7 @@ class CFGBuilder { CFGBlock *SwitchTerminatedBlock; CFGBlock *DefaultCaseBlock; CFGBlock *TryTerminatedBlock; - + // Current position in local scope. LocalScope::const_iterator ScopePos; @@ -343,7 +349,7 @@ public: cachedEntry(nullptr), lastLookup(nullptr) {} // buildCFG - Used by external clients to construct the CFG. - CFG* buildCFG(const Decl *D, Stmt *Statement); + std::unique_ptr<CFG> buildCFG(const Decl *D, Stmt *Statement); bool alwaysAdd(const Stmt *stmt); @@ -410,16 +416,80 @@ private: CFGBlock *VisitChildren(Stmt *S); CFGBlock *VisitNoRecurse(Expr *E, AddStmtChoice asc); + /// When creating the CFG for temporary destructors, we want to mirror the + /// branch structure of the corresponding constructor calls. + /// Thus, while visiting a statement for temporary destructors, we keep a + /// context to keep track of the following information: + /// - whether a subexpression is executed unconditionally + /// - if a subexpression is executed conditionally, the first + /// CXXBindTemporaryExpr we encounter in that subexpression (which + /// corresponds to the last temporary destructor we have to call for this + /// subexpression) and the CFG block at that point (which will become the + /// successor block when inserting the decision point). + /// + /// That way, we can build the branch structure for temporary destructors as + /// follows: + /// 1. If a subexpression is executed unconditionally, we add the temporary + /// destructor calls to the current block. + /// 2. If a subexpression is executed conditionally, when we encounter a + /// CXXBindTemporaryExpr: + /// a) If it is the first temporary destructor call in the subexpression, + /// we remember the CXXBindTemporaryExpr and the current block in the + /// TempDtorContext; we start a new block, and insert the temporary + /// destructor call. + /// b) Otherwise, add the temporary destructor call to the current block. + /// 3. When we finished visiting a conditionally executed subexpression, + /// and we found at least one temporary constructor during the visitation + /// (2.a has executed), we insert a decision block that uses the + /// CXXBindTemporaryExpr as terminator, and branches to the current block + /// if the CXXBindTemporaryExpr was marked executed, and otherwise + /// branches to the stored successor. + struct TempDtorContext { + TempDtorContext() + : IsConditional(false), KnownExecuted(true), Succ(nullptr), + TerminatorExpr(nullptr) {} + + TempDtorContext(TryResult KnownExecuted) + : IsConditional(true), KnownExecuted(KnownExecuted), Succ(nullptr), + TerminatorExpr(nullptr) {} + + /// Returns whether we need to start a new branch for a temporary destructor + /// call. This is the case when the the temporary destructor is + /// conditionally executed, and it is the first one we encounter while + /// visiting a subexpression - other temporary destructors at the same level + /// will be added to the same block and are executed under the same + /// condition. + bool needsTempDtorBranch() const { + return IsConditional && !TerminatorExpr; + } + + /// Remember the successor S of a temporary destructor decision branch for + /// the corresponding CXXBindTemporaryExpr E. + void setDecisionPoint(CFGBlock *S, CXXBindTemporaryExpr *E) { + Succ = S; + TerminatorExpr = E; + } + + const bool IsConditional; + const TryResult KnownExecuted; + CFGBlock *Succ; + CXXBindTemporaryExpr *TerminatorExpr; + }; + // Visitors to walk an AST and generate destructors of temporaries in // full expression. - CFGBlock *VisitForTemporaryDtors(Stmt *E, bool BindToTemporary = false); - CFGBlock *VisitChildrenForTemporaryDtors(Stmt *E); - CFGBlock *VisitBinaryOperatorForTemporaryDtors(BinaryOperator *E); - CFGBlock *VisitCXXBindTemporaryExprForTemporaryDtors(CXXBindTemporaryExpr *E, - bool BindToTemporary); - CFGBlock * - VisitConditionalOperatorForTemporaryDtors(AbstractConditionalOperator *E, - bool BindToTemporary); + CFGBlock *VisitForTemporaryDtors(Stmt *E, bool BindToTemporary, + TempDtorContext &Context); + CFGBlock *VisitChildrenForTemporaryDtors(Stmt *E, TempDtorContext &Context); + CFGBlock *VisitBinaryOperatorForTemporaryDtors(BinaryOperator *E, + TempDtorContext &Context); + CFGBlock *VisitCXXBindTemporaryExprForTemporaryDtors( + CXXBindTemporaryExpr *E, bool BindToTemporary, TempDtorContext &Context); + CFGBlock *VisitConditionalOperatorForTemporaryDtors( + AbstractConditionalOperator *E, bool BindToTemporary, + TempDtorContext &Context); + void InsertTempDtorDecisionBlock(const TempDtorContext &Context, + CFGBlock *FalseSucc = nullptr); // NYS == Not Yet Supported CFGBlock *NYS() { @@ -901,7 +971,7 @@ static const VariableArrayType *FindVA(const Type *t) { /// body (compound statement). The ownership of the returned CFG is /// transferred to the caller. If CFG construction fails, this method returns /// NULL. -CFG* CFGBuilder::buildCFG(const Decl *D, Stmt *Statement) { +std::unique_ptr<CFG> CFGBuilder::buildCFG(const Decl *D, Stmt *Statement) { assert(cfg.get()); if (!Statement) return nullptr; @@ -973,7 +1043,7 @@ CFG* CFGBuilder::buildCFG(const Decl *D, Stmt *Statement) { // Create an empty entry block that has no predecessors. cfg->setEntry(createBlock()); - return cfg.release(); + return std::move(cfg); } /// createBlock - Used to lazily create blocks that are connected @@ -1000,21 +1070,19 @@ CFGBlock *CFGBuilder::addInitializer(CXXCtorInitializer *I) { if (!BuildOpts.AddInitializers) return Block; - bool IsReference = false; bool HasTemporaries = false; // Destructors of temporaries in initialization expression should be called // after initialization finishes. Expr *Init = I->getInit(); if (Init) { - if (FieldDecl *FD = I->getAnyMember()) - IsReference = FD->getType()->isReferenceType(); HasTemporaries = isa<ExprWithCleanups>(Init); if (BuildOpts.AddTemporaryDtors && HasTemporaries) { // Generate destructors for temporaries in initialization expression. + TempDtorContext Context; VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(), - IsReference); + /*BindToTemporary=*/false, Context); } } @@ -1946,7 +2014,6 @@ CFGBlock *CFGBuilder::VisitDeclSubExpr(DeclStmt *DS) { return Block; } - bool IsReference = false; bool HasTemporaries = false; // Guard static initializers under a branch. @@ -1968,13 +2035,13 @@ CFGBlock *CFGBuilder::VisitDeclSubExpr(DeclStmt *DS) { // after initialization finishes. Expr *Init = VD->getInit(); if (Init) { - IsReference = VD->getType()->isReferenceType(); HasTemporaries = isa<ExprWithCleanups>(Init); if (BuildOpts.AddTemporaryDtors && HasTemporaries) { // Generate destructors for temporaries in initialization expression. + TempDtorContext Context; VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(), - IsReference); + /*BindToTemporary=*/false, Context); } } @@ -3354,7 +3421,8 @@ CFGBlock *CFGBuilder::VisitExprWithCleanups(ExprWithCleanups *E, if (BuildOpts.AddTemporaryDtors) { // If adding implicit destructors visit the full expression for adding // destructors of temporaries. - VisitForTemporaryDtors(E->getSubExpr()); + TempDtorContext Context; + VisitForTemporaryDtors(E->getSubExpr(), false, Context); // Full expression has to be added as CFGStmt so it will be sequenced // before destructors of it's temporaries. @@ -3463,7 +3531,8 @@ CFGBlock *CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt *I) { return addStmt(I->getTarget()); } -CFGBlock *CFGBuilder::VisitForTemporaryDtors(Stmt *E, bool BindToTemporary) { +CFGBlock *CFGBuilder::VisitForTemporaryDtors(Stmt *E, bool BindToTemporary, + TempDtorContext &Context) { assert(BuildOpts.AddImplicitDtors && BuildOpts.AddTemporaryDtors); tryAgain: @@ -3473,32 +3542,52 @@ tryAgain: } switch (E->getStmtClass()) { default: - return VisitChildrenForTemporaryDtors(E); + return VisitChildrenForTemporaryDtors(E, Context); case Stmt::BinaryOperatorClass: - return VisitBinaryOperatorForTemporaryDtors(cast<BinaryOperator>(E)); + return VisitBinaryOperatorForTemporaryDtors(cast<BinaryOperator>(E), + Context); case Stmt::CXXBindTemporaryExprClass: return VisitCXXBindTemporaryExprForTemporaryDtors( - cast<CXXBindTemporaryExpr>(E), BindToTemporary); + cast<CXXBindTemporaryExpr>(E), BindToTemporary, Context); case Stmt::BinaryConditionalOperatorClass: case Stmt::ConditionalOperatorClass: return VisitConditionalOperatorForTemporaryDtors( - cast<AbstractConditionalOperator>(E), BindToTemporary); + cast<AbstractConditionalOperator>(E), BindToTemporary, Context); case Stmt::ImplicitCastExprClass: // For implicit cast we want BindToTemporary to be passed further. E = cast<CastExpr>(E)->getSubExpr(); goto tryAgain; + case Stmt::CXXFunctionalCastExprClass: + // For functional cast we want BindToTemporary to be passed further. + E = cast<CXXFunctionalCastExpr>(E)->getSubExpr(); + goto tryAgain; + case Stmt::ParenExprClass: E = cast<ParenExpr>(E)->getSubExpr(); goto tryAgain; - case Stmt::MaterializeTemporaryExprClass: - E = cast<MaterializeTemporaryExpr>(E)->GetTemporaryExpr(); + case Stmt::MaterializeTemporaryExprClass: { + const MaterializeTemporaryExpr* MTE = cast<MaterializeTemporaryExpr>(E); + BindToTemporary = (MTE->getStorageDuration() != SD_FullExpression); + SmallVector<const Expr *, 2> CommaLHSs; + SmallVector<SubobjectAdjustment, 2> Adjustments; + // Find the expression whose lifetime needs to be extended. + E = const_cast<Expr *>( + cast<MaterializeTemporaryExpr>(E) + ->GetTemporaryExpr() + ->skipRValueSubobjectAdjustments(CommaLHSs, Adjustments)); + // Visit the skipped comma operator left-hand sides for other temporaries. + for (const Expr *CommaLHS : CommaLHSs) { + VisitForTemporaryDtors(const_cast<Expr *>(CommaLHS), + /*BindToTemporary=*/false, Context); + } goto tryAgain; + } case Stmt::BlockExprClass: // Don't recurse into blocks; their subexpressions don't get evaluated @@ -3511,7 +3600,8 @@ tryAgain: auto *LE = cast<LambdaExpr>(E); CFGBlock *B = Block; for (Expr *Init : LE->capture_inits()) { - if (CFGBlock *R = VisitForTemporaryDtors(Init)) + if (CFGBlock *R = VisitForTemporaryDtors( + Init, /*BindToTemporary=*/false, Context)) B = R; } return B; @@ -3527,7 +3617,13 @@ tryAgain: } } -CFGBlock *CFGBuilder::VisitChildrenForTemporaryDtors(Stmt *E) { +CFGBlock *CFGBuilder::VisitChildrenForTemporaryDtors(Stmt *E, + TempDtorContext &Context) { + if (isa<LambdaExpr>(E)) { + // Do not visit the children of lambdas; they have their own CFGs. + return Block; + } + // When visiting children for destructors we want to visit them in reverse // order that they will appear in the CFG. Because the CFG is built // bottom-up, this means we visit them in their natural order, which @@ -3535,165 +3631,126 @@ CFGBlock *CFGBuilder::VisitChildrenForTemporaryDtors(Stmt *E) { CFGBlock *B = Block; for (Stmt::child_range I = E->children(); I; ++I) { if (Stmt *Child = *I) - if (CFGBlock *R = VisitForTemporaryDtors(Child)) + if (CFGBlock *R = VisitForTemporaryDtors(Child, false, Context)) B = R; } return B; } -CFGBlock *CFGBuilder::VisitBinaryOperatorForTemporaryDtors(BinaryOperator *E) { +CFGBlock *CFGBuilder::VisitBinaryOperatorForTemporaryDtors( + BinaryOperator *E, TempDtorContext &Context) { if (E->isLogicalOp()) { - // Destructors for temporaries in LHS expression should be called after - // those for RHS expression. Even if this will unnecessarily create a block, - // this block will be used at least by the full expression. - autoCreateBlock(); - CFGBlock *ConfluenceBlock = VisitForTemporaryDtors(E->getLHS()); - if (badCFG) - return nullptr; - - Succ = ConfluenceBlock; - Block = nullptr; - CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS()); - - if (RHSBlock) { - if (badCFG) - return nullptr; + VisitForTemporaryDtors(E->getLHS(), false, Context); + TryResult RHSExecuted = tryEvaluateBool(E->getLHS()); + if (RHSExecuted.isKnown() && E->getOpcode() == BO_LOr) + RHSExecuted.negate(); + + // We do not know at CFG-construction time whether the right-hand-side was + // executed, thus we add a branch node that depends on the temporary + // constructor call. + TempDtorContext RHSContext( + bothKnownTrue(Context.KnownExecuted, RHSExecuted)); + VisitForTemporaryDtors(E->getRHS(), false, RHSContext); + InsertTempDtorDecisionBlock(RHSContext); - // If RHS expression did produce destructors we need to connect created - // blocks to CFG in same manner as for binary operator itself. - CFGBlock *LHSBlock = createBlock(false); - LHSBlock->setTerminator(CFGTerminator(E, true)); - - // For binary operator LHS block is before RHS in list of predecessors - // of ConfluenceBlock. - std::reverse(ConfluenceBlock->pred_begin(), - ConfluenceBlock->pred_end()); - - // See if this is a known constant. - TryResult KnownVal = tryEvaluateBool(E->getLHS()); - if (KnownVal.isKnown() && (E->getOpcode() == BO_LOr)) - KnownVal.negate(); - - // Link LHSBlock with RHSBlock exactly the same way as for binary operator - // itself. - if (E->getOpcode() == BO_LOr) { - addSuccessor(LHSBlock, KnownVal.isTrue() ? nullptr : ConfluenceBlock); - addSuccessor(LHSBlock, KnownVal.isFalse() ? nullptr : RHSBlock); - } else { - assert (E->getOpcode() == BO_LAnd); - addSuccessor(LHSBlock, KnownVal.isFalse() ? nullptr : RHSBlock); - addSuccessor(LHSBlock, KnownVal.isTrue() ? nullptr : ConfluenceBlock); - } - - Block = LHSBlock; - return LHSBlock; - } - - Block = ConfluenceBlock; - return ConfluenceBlock; + return Block; } if (E->isAssignmentOp()) { // For assignment operator (=) LHS expression is visited // before RHS expression. For destructors visit them in reverse order. - CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS()); - CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS()); + CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS(), false, Context); + CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS(), false, Context); return LHSBlock ? LHSBlock : RHSBlock; } // For any other binary operator RHS expression is visited before // LHS expression (order of children). For destructors visit them in reverse // order. - CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS()); - CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS()); + CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS(), false, Context); + CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS(), false, Context); return RHSBlock ? RHSBlock : LHSBlock; } CFGBlock *CFGBuilder::VisitCXXBindTemporaryExprForTemporaryDtors( - CXXBindTemporaryExpr *E, bool BindToTemporary) { + CXXBindTemporaryExpr *E, bool BindToTemporary, TempDtorContext &Context) { // First add destructors for temporaries in subexpression. - CFGBlock *B = VisitForTemporaryDtors(E->getSubExpr()); + CFGBlock *B = VisitForTemporaryDtors(E->getSubExpr(), false, Context); if (!BindToTemporary) { // If lifetime of temporary is not prolonged (by assigning to constant // reference) add destructor for it. - // If the destructor is marked as a no-return destructor, we need to create - // a new block for the destructor which does not have as a successor - // anything built thus far. Control won't flow out of this block. const CXXDestructorDecl *Dtor = E->getTemporary()->getDestructor(); + if (Dtor->isNoReturn()) { - Succ = B; + // If the destructor is marked as a no-return destructor, we need to + // create a new block for the destructor which does not have as a + // successor anything built thus far. Control won't flow out of this + // block. + if (B) Succ = B; Block = createNoReturnBlock(); + } else if (Context.needsTempDtorBranch()) { + // If we need to introduce a branch, we add a new block that we will hook + // up to a decision block later. + if (B) Succ = B; + Block = createBlock(); } else { autoCreateBlock(); } - + if (Context.needsTempDtorBranch()) { + Context.setDecisionPoint(Succ, E); + } appendTemporaryDtor(Block, E); + B = Block; } return B; } -CFGBlock *CFGBuilder::VisitConditionalOperatorForTemporaryDtors( - AbstractConditionalOperator *E, bool BindToTemporary) { - // First add destructors for condition expression. Even if this will - // unnecessarily create a block, this block will be used at least by the full - // expression. - autoCreateBlock(); - CFGBlock *ConfluenceBlock = VisitForTemporaryDtors(E->getCond()); - if (badCFG) - return nullptr; - if (BinaryConditionalOperator *BCO - = dyn_cast<BinaryConditionalOperator>(E)) { - ConfluenceBlock = VisitForTemporaryDtors(BCO->getCommon()); - if (badCFG) - return nullptr; - } - - // Try to add block with destructors for LHS expression. - CFGBlock *LHSBlock = nullptr; - Succ = ConfluenceBlock; - Block = nullptr; - LHSBlock = VisitForTemporaryDtors(E->getTrueExpr(), BindToTemporary); - if (badCFG) - return nullptr; - - // Try to add block with destructors for RHS expression; - Succ = ConfluenceBlock; - Block = nullptr; - CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getFalseExpr(), - BindToTemporary); - if (badCFG) - return nullptr; - - if (!RHSBlock && !LHSBlock) { - // If neither LHS nor RHS expression had temporaries to destroy don't create - // more blocks. - Block = ConfluenceBlock; - return Block; +void CFGBuilder::InsertTempDtorDecisionBlock(const TempDtorContext &Context, + CFGBlock *FalseSucc) { + if (!Context.TerminatorExpr) { + // If no temporary was found, we do not need to insert a decision point. + return; } + assert(Context.TerminatorExpr); + CFGBlock *Decision = createBlock(false); + Decision->setTerminator(CFGTerminator(Context.TerminatorExpr, true)); + addSuccessor(Decision, Block, !Context.KnownExecuted.isFalse()); + addSuccessor(Decision, FalseSucc ? FalseSucc : Context.Succ, + !Context.KnownExecuted.isTrue()); + Block = Decision; +} - Block = createBlock(false); - Block->setTerminator(CFGTerminator(E, true)); - assert(Block->getTerminator().isTemporaryDtorsBranch()); - - // See if this is a known constant. - const TryResult &KnownVal = tryEvaluateBool(E->getCond()); - - if (LHSBlock) { - addSuccessor(Block, LHSBlock, !KnownVal.isFalse()); - } else if (KnownVal.isFalse()) { - addSuccessor(Block, nullptr); +CFGBlock *CFGBuilder::VisitConditionalOperatorForTemporaryDtors( + AbstractConditionalOperator *E, bool BindToTemporary, + TempDtorContext &Context) { + VisitForTemporaryDtors(E->getCond(), false, Context); + CFGBlock *ConditionBlock = Block; + CFGBlock *ConditionSucc = Succ; + TryResult ConditionVal = tryEvaluateBool(E->getCond()); + TryResult NegatedVal = ConditionVal; + if (NegatedVal.isKnown()) NegatedVal.negate(); + + TempDtorContext TrueContext( + bothKnownTrue(Context.KnownExecuted, ConditionVal)); + VisitForTemporaryDtors(E->getTrueExpr(), BindToTemporary, TrueContext); + CFGBlock *TrueBlock = Block; + + Block = ConditionBlock; + Succ = ConditionSucc; + TempDtorContext FalseContext( + bothKnownTrue(Context.KnownExecuted, NegatedVal)); + VisitForTemporaryDtors(E->getFalseExpr(), BindToTemporary, FalseContext); + + if (TrueContext.TerminatorExpr && FalseContext.TerminatorExpr) { + InsertTempDtorDecisionBlock(FalseContext, TrueBlock); + } else if (TrueContext.TerminatorExpr) { + Block = TrueBlock; + InsertTempDtorDecisionBlock(TrueContext); } else { - addSuccessor(Block, ConfluenceBlock); - std::reverse(ConfluenceBlock->pred_begin(), ConfluenceBlock->pred_end()); + InsertTempDtorDecisionBlock(FalseContext); } - - if (!RHSBlock) - RHSBlock = ConfluenceBlock; - - addSuccessor(Block, RHSBlock, !KnownVal.isTrue()); - return Block; } @@ -3718,10 +3775,9 @@ CFGBlock *CFG::createBlock() { return &back(); } -/// buildCFG - Constructs a CFG from an AST. Ownership of the returned -/// CFG is returned to the caller. -CFG* CFG::buildCFG(const Decl *D, Stmt *Statement, ASTContext *C, - const BuildOptions &BO) { +/// buildCFG - Constructs a CFG from an AST. +std::unique_ptr<CFG> CFG::buildCFG(const Decl *D, Stmt *Statement, + ASTContext *C, const BuildOptions &BO) { CFGBuilder Builder(C, BO); return Builder.buildCFG(D, Statement); } |