diff options
Diffstat (limited to 'clang/lib/Analysis')
| -rw-r--r-- | clang/lib/Analysis/CFG.cpp | 45 | ||||
| -rw-r--r-- | clang/lib/Analysis/ConstructionContext.cpp | 11 | ||||
| -rw-r--r-- | clang/lib/Analysis/ExprMutationAnalyzer.cpp | 18 | ||||
| -rw-r--r-- | clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp | 71 | ||||
| -rw-r--r-- | clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp | 48 | ||||
| -rw-r--r-- | clang/lib/Analysis/FlowSensitive/DebugSupport.cpp | 14 | ||||
| -rw-r--r-- | clang/lib/Analysis/FlowSensitive/Transfer.cpp | 48 | ||||
| -rw-r--r-- | clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp | 20 | ||||
| -rw-r--r-- | clang/lib/Analysis/FlowSensitive/WatchedLiteralsSolver.cpp | 110 | ||||
| -rw-r--r-- | clang/lib/Analysis/LiveVariables.cpp | 27 |
10 files changed, 338 insertions, 74 deletions
diff --git a/clang/lib/Analysis/CFG.cpp b/clang/lib/Analysis/CFG.cpp index 614d94ae31a6..84178ff488a5 100644 --- a/clang/lib/Analysis/CFG.cpp +++ b/clang/lib/Analysis/CFG.cpp @@ -1659,9 +1659,13 @@ CFGBlock *CFGBuilder::addInitializer(CXXCtorInitializer *I) { appendInitializer(Block, I); if (Init) { + // If the initializer is an ArrayInitLoopExpr, we want to extract the + // initializer, that's used for each element. + const auto *AILE = dyn_cast_or_null<ArrayInitLoopExpr>(Init); + findConstructionContexts( ConstructionContextLayer::create(cfg->getBumpVectorContext(), I), - Init); + AILE ? AILE->getSubExpr() : Init); if (HasTemporaries) { // For expression with temporaries go directly to subexpression to omit @@ -2928,12 +2932,30 @@ CFGBlock *CFGBuilder::VisitDeclSubExpr(DeclStmt *DS) { } } + // If we bind to a tuple-like type, we iterate over the HoldingVars, and + // create a DeclStmt for each of them. + if (const auto *DD = dyn_cast<DecompositionDecl>(VD)) { + for (auto BD : llvm::reverse(DD->bindings())) { + if (auto *VD = BD->getHoldingVar()) { + DeclGroupRef DG(VD); + DeclStmt *DSNew = + new (Context) DeclStmt(DG, VD->getLocation(), GetEndLoc(VD)); + cfg->addSyntheticDeclStmt(DSNew, DS); + Block = VisitDeclSubExpr(DSNew); + } + } + } + autoCreateBlock(); appendStmt(Block, DS); + // If the initializer is an ArrayInitLoopExpr, we want to extract the + // initializer, that's used for each element. + const auto *AILE = dyn_cast_or_null<ArrayInitLoopExpr>(Init); + findConstructionContexts( ConstructionContextLayer::create(cfg->getBumpVectorContext(), DS), - Init); + AILE ? AILE->getSubExpr() : Init); // Keep track of the last non-null block, as 'Block' can be nulled out // if the initializer expression is something like a 'while' in a @@ -3340,9 +3362,20 @@ CFGBlock *CFGBuilder::VisitBlockExpr(BlockExpr *E, AddStmtChoice asc) { CFGBlock *CFGBuilder::VisitLambdaExpr(LambdaExpr *E, AddStmtChoice asc) { CFGBlock *LastBlock = VisitNoRecurse(E, asc); + + unsigned Idx = 0; for (LambdaExpr::capture_init_iterator it = E->capture_init_begin(), - et = E->capture_init_end(); it != et; ++it) { + et = E->capture_init_end(); + it != et; ++it, ++Idx) { if (Expr *Init = *it) { + // If the initializer is an ArrayInitLoopExpr, we want to extract the + // initializer, that's used for each element. + const auto *AILE = dyn_cast_or_null<ArrayInitLoopExpr>(Init); + + findConstructionContexts(ConstructionContextLayer::create( + cfg->getBumpVectorContext(), {E, Idx}), + AILE ? AILE->getSubExpr() : Init); + CFGBlock *Tmp = Visit(Init); if (Tmp) LastBlock = Tmp; @@ -5616,6 +5649,12 @@ static void print_construction_context(raw_ostream &OS, Stmts.push_back(TOCC->getConstructorAfterElision()); break; } + case ConstructionContext::LambdaCaptureKind: { + const auto *LCC = cast<LambdaCaptureConstructionContext>(CC); + Helper.handledStmt(const_cast<LambdaExpr *>(LCC->getLambdaExpr()), OS); + OS << "+" << LCC->getIndex(); + return; + } case ConstructionContext::ArgumentKind: { const auto *ACC = cast<ArgumentConstructionContext>(CC); if (const Stmt *BTE = ACC->getCXXBindTemporaryExpr()) { diff --git a/clang/lib/Analysis/ConstructionContext.cpp b/clang/lib/Analysis/ConstructionContext.cpp index 6ba1e2173d2c..8a862c06f13a 100644 --- a/clang/lib/Analysis/ConstructionContext.cpp +++ b/clang/lib/Analysis/ConstructionContext.cpp @@ -156,6 +156,12 @@ const ConstructionContext *ConstructionContext::createBoundTemporaryFromLayers( return create<CXX17ElidedCopyConstructorInitializerConstructionContext>( C, I, BTE); } + case ConstructionContextItem::LambdaCaptureKind: { + assert(ParentLayer->isLast()); + const auto *E = cast<LambdaExpr>(ParentItem.getStmt()); + return create<LambdaCaptureConstructionContext>(C, E, + ParentItem.getIndex()); + } } // switch (ParentItem.getKind()) llvm_unreachable("Unexpected construction context with destructor!"); @@ -200,6 +206,11 @@ const ConstructionContext *ConstructionContext::createFromLayers( case ConstructionContextItem::ElidableConstructorKind: { llvm_unreachable("The argument needs to be materialized first!"); } + case ConstructionContextItem::LambdaCaptureKind: { + assert(TopLayer->isLast()); + const auto *E = cast<LambdaExpr>(TopItem.getStmt()); + return create<LambdaCaptureConstructionContext>(C, E, TopItem.getIndex()); + } case ConstructionContextItem::InitializerKind: { assert(TopLayer->isLast()); const CXXCtorInitializer *I = TopItem.getCXXCtorInitializer(); diff --git a/clang/lib/Analysis/ExprMutationAnalyzer.cpp b/clang/lib/Analysis/ExprMutationAnalyzer.cpp index e3bb902b1fe9..c876eaa6358a 100644 --- a/clang/lib/Analysis/ExprMutationAnalyzer.cpp +++ b/clang/lib/Analysis/ExprMutationAnalyzer.cpp @@ -455,14 +455,16 @@ const Stmt *ExprMutationAnalyzer::findRangeLoopMutation(const Expr *Exp) { // array is considered modified if the loop-variable is a non-const reference. const auto DeclStmtToNonRefToArray = declStmt(hasSingleDecl(varDecl(hasType( hasUnqualifiedDesugaredType(referenceType(pointee(arrayType()))))))); - const auto RefToArrayRefToElements = match( - findAll(stmt(cxxForRangeStmt( - hasLoopVariable(varDecl(hasType(nonConstReferenceType())) - .bind(NodeID<Decl>::value)), - hasRangeStmt(DeclStmtToNonRefToArray), - hasRangeInit(canResolveToExpr(equalsNode(Exp))))) - .bind("stmt")), - Stm, Context); + const auto RefToArrayRefToElements = + match(findAll(stmt(cxxForRangeStmt( + hasLoopVariable( + varDecl(anyOf(hasType(nonConstReferenceType()), + hasType(nonConstPointerType()))) + .bind(NodeID<Decl>::value)), + hasRangeStmt(DeclStmtToNonRefToArray), + hasRangeInit(canResolveToExpr(equalsNode(Exp))))) + .bind("stmt")), + Stm, Context); if (const auto *BadRangeInitFromArray = selectFirst<Stmt>("stmt", RefToArrayRefToElements)) diff --git a/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp b/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp index 5105999741e6..216f41bdee1c 100644 --- a/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp +++ b/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp @@ -113,16 +113,27 @@ BoolValue &DataflowAnalysisContext::getOrCreateNegation(BoolValue &Val) { BoolValue &DataflowAnalysisContext::getOrCreateImplication(BoolValue &LHS, BoolValue &RHS) { - return &LHS == &RHS ? getBoolLiteralValue(true) - : getOrCreateDisjunction(getOrCreateNegation(LHS), RHS); + if (&LHS == &RHS) + return getBoolLiteralValue(true); + + auto Res = ImplicationVals.try_emplace(std::make_pair(&LHS, &RHS), nullptr); + if (Res.second) + Res.first->second = + &takeOwnership(std::make_unique<ImplicationValue>(LHS, RHS)); + return *Res.first->second; } BoolValue &DataflowAnalysisContext::getOrCreateIff(BoolValue &LHS, BoolValue &RHS) { - return &LHS == &RHS - ? getBoolLiteralValue(true) - : getOrCreateConjunction(getOrCreateImplication(LHS, RHS), - getOrCreateImplication(RHS, LHS)); + if (&LHS == &RHS) + return getBoolLiteralValue(true); + + auto Res = BiconditionalVals.try_emplace(makeCanonicalBoolValuePair(LHS, RHS), + nullptr); + if (Res.second) + Res.first->second = + &takeOwnership(std::make_unique<BiconditionalValue>(LHS, RHS)); + return *Res.first->second; } AtomicBoolValue &DataflowAnalysisContext::makeFlowConditionToken() { @@ -199,18 +210,18 @@ void DataflowAnalysisContext::addTransitiveFlowConditionConstraints( if (!Res.second) return; - auto ConstraintsIT = FlowConditionConstraints.find(&Token); - if (ConstraintsIT == FlowConditionConstraints.end()) { + auto ConstraintsIt = FlowConditionConstraints.find(&Token); + if (ConstraintsIt == FlowConditionConstraints.end()) { Constraints.insert(&Token); } else { // Bind flow condition token via `iff` to its set of constraints: // FC <=> (C1 ^ C2 ^ ...), where Ci are constraints - Constraints.insert(&getOrCreateIff(Token, *ConstraintsIT->second)); + Constraints.insert(&getOrCreateIff(Token, *ConstraintsIt->second)); } - auto DepsIT = FlowConditionDeps.find(&Token); - if (DepsIT != FlowConditionDeps.end()) { - for (AtomicBoolValue *DepToken : DepsIT->second) { + auto DepsIt = FlowConditionDeps.find(&Token); + if (DepsIt != FlowConditionDeps.end()) { + for (AtomicBoolValue *DepToken : DepsIt->second) { addTransitiveFlowConditionConstraints(*DepToken, Constraints, VisitedTokens); } @@ -220,10 +231,10 @@ void DataflowAnalysisContext::addTransitiveFlowConditionConstraints( BoolValue &DataflowAnalysisContext::substituteBoolValue( BoolValue &Val, llvm::DenseMap<BoolValue *, BoolValue *> &SubstitutionsCache) { - auto IT = SubstitutionsCache.find(&Val); - if (IT != SubstitutionsCache.end()) { + auto It = SubstitutionsCache.find(&Val); + if (It != SubstitutionsCache.end()) { // Return memoized result of substituting this boolean value. - return *IT->second; + return *It->second; } // Handle substitution on the boolean value (and its subvalues), saving the @@ -258,6 +269,24 @@ BoolValue &DataflowAnalysisContext::substituteBoolValue( Result = &getOrCreateConjunction(LeftSub, RightSub); break; } + case Value::Kind::Implication: { + auto &IV = *cast<ImplicationValue>(&Val); + auto &LeftSub = + substituteBoolValue(IV.getLeftSubValue(), SubstitutionsCache); + auto &RightSub = + substituteBoolValue(IV.getRightSubValue(), SubstitutionsCache); + Result = &getOrCreateImplication(LeftSub, RightSub); + break; + } + case Value::Kind::Biconditional: { + auto &BV = *cast<BiconditionalValue>(&Val); + auto &LeftSub = + substituteBoolValue(BV.getLeftSubValue(), SubstitutionsCache); + auto &RightSub = + substituteBoolValue(BV.getRightSubValue(), SubstitutionsCache); + Result = &getOrCreateIff(LeftSub, RightSub); + break; + } default: llvm_unreachable("Unhandled Value Kind"); } @@ -280,19 +309,19 @@ BoolValue &DataflowAnalysisContext::buildAndSubstituteFlowCondition( BoolValue &DataflowAnalysisContext::buildAndSubstituteFlowConditionWithCache( AtomicBoolValue &Token, llvm::DenseMap<BoolValue *, BoolValue *> &SubstitutionsCache) { - auto ConstraintsIT = FlowConditionConstraints.find(&Token); - if (ConstraintsIT == FlowConditionConstraints.end()) { + auto ConstraintsIt = FlowConditionConstraints.find(&Token); + if (ConstraintsIt == FlowConditionConstraints.end()) { return getBoolLiteralValue(true); } - auto DepsIT = FlowConditionDeps.find(&Token); - if (DepsIT != FlowConditionDeps.end()) { - for (AtomicBoolValue *DepToken : DepsIT->second) { + auto DepsIt = FlowConditionDeps.find(&Token); + if (DepsIt != FlowConditionDeps.end()) { + for (AtomicBoolValue *DepToken : DepsIt->second) { auto &NewDep = buildAndSubstituteFlowConditionWithCache( *DepToken, SubstitutionsCache); SubstitutionsCache[DepToken] = &NewDep; } } - return substituteBoolValue(*ConstraintsIT->second, SubstitutionsCache); + return substituteBoolValue(*ConstraintsIt->second, SubstitutionsCache); } void DataflowAnalysisContext::dumpFlowCondition(AtomicBoolValue &Token) { diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp index 2b6cd0c4f857..f6f71e34b892 100644 --- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp +++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp @@ -200,6 +200,42 @@ Environment::Environment(DataflowAnalysisContext &DACtx, } } +Environment Environment::pushCall(const CallExpr *Call) const { + Environment Env(*this); + + // FIXME: Currently this only works if the callee is never a method and the + // same callee is never analyzed from multiple separate callsites. To + // generalize this, we'll need to store a "context" field (probably a stack of + // `const CallExpr *`s) in the `Environment`, and then change the + // `DataflowAnalysisContext` class to hold a map from contexts to "frames", + // where each frame stores its own version of what are currently the + // `DeclToLoc`, `ExprToLoc`, and `ThisPointeeLoc` fields. + + const auto *FuncDecl = Call->getDirectCallee(); + assert(FuncDecl != nullptr); + assert(FuncDecl->getBody() != nullptr); + // FIXME: In order to allow the callee to reference globals, we probably need + // to call `initGlobalVars` here in some way. + + auto ParamIt = FuncDecl->param_begin(); + auto ArgIt = Call->arg_begin(); + auto ArgEnd = Call->arg_end(); + + // FIXME: Parameters don't always map to arguments 1:1; examples include + // overloaded operators implemented as member functions, and parameter packs. + for (; ArgIt != ArgEnd; ++ParamIt, ++ArgIt) { + assert(ParamIt != FuncDecl->param_end()); + + const VarDecl *Param = *ParamIt; + const Expr *Arg = *ArgIt; + auto *ArgLoc = Env.getStorageLocation(*Arg, SkipPast::Reference); + assert(ArgLoc != nullptr); + Env.setStorageLocation(*Param, *ArgLoc); + } + + return Env; +} + bool Environment::equivalentTo(const Environment &Other, Environment::ValueModel &Model) const { assert(DACtx == Other.DACtx); @@ -352,16 +388,16 @@ void Environment::setValue(const StorageLocation &Loc, Value &Val) { } } - auto IT = MemberLocToStruct.find(&Loc); - if (IT != MemberLocToStruct.end()) { + auto It = MemberLocToStruct.find(&Loc); + if (It != MemberLocToStruct.end()) { // `Loc` is the location of a struct member so we need to also update the // value of the member in the corresponding `StructValue`. - assert(IT->second.first != nullptr); - StructValue &StructVal = *IT->second.first; + assert(It->second.first != nullptr); + StructValue &StructVal = *It->second.first; - assert(IT->second.second != nullptr); - const ValueDecl &Member = *IT->second.second; + assert(It->second.second != nullptr); + const ValueDecl &Member = *It->second.second; StructVal.setChild(Member, Val); } diff --git a/clang/lib/Analysis/FlowSensitive/DebugSupport.cpp b/clang/lib/Analysis/FlowSensitive/DebugSupport.cpp index 309ff0682f50..714ad08643ed 100644 --- a/clang/lib/Analysis/FlowSensitive/DebugSupport.cpp +++ b/clang/lib/Analysis/FlowSensitive/DebugSupport.cpp @@ -96,6 +96,20 @@ public: S = formatv("(not\n{0})", debugString(N.getSubVal(), Depth + 1)); break; } + case Value::Kind::Implication: { + auto &IV = cast<ImplicationValue>(B); + auto L = debugString(IV.getLeftSubValue(), Depth + 1); + auto R = debugString(IV.getRightSubValue(), Depth + 1); + S = formatv("(=>\n{0}\n{1})", L, R); + break; + } + case Value::Kind::Biconditional: { + auto &BV = cast<BiconditionalValue>(B); + auto L = debugString(BV.getLeftSubValue(), Depth + 1); + auto R = debugString(BV.getRightSubValue(), Depth + 1); + S = formatv("(=\n{0}\n{1})", L, R); + break; + } default: llvm_unreachable("Unhandled value kind"); } diff --git a/clang/lib/Analysis/FlowSensitive/Transfer.cpp b/clang/lib/Analysis/FlowSensitive/Transfer.cpp index 500e1a7a9390..bbf7526adce9 100644 --- a/clang/lib/Analysis/FlowSensitive/Transfer.cpp +++ b/clang/lib/Analysis/FlowSensitive/Transfer.cpp @@ -20,7 +20,9 @@ #include "clang/AST/OperationKinds.h" #include "clang/AST/Stmt.h" #include "clang/AST/StmtVisitor.h" +#include "clang/Analysis/FlowSensitive/ControlFlowContext.h" #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" +#include "clang/Analysis/FlowSensitive/NoopAnalysis.h" #include "clang/Analysis/FlowSensitive/Value.h" #include "clang/Basic/Builtins.h" #include "clang/Basic/OperatorKinds.h" @@ -46,8 +48,9 @@ static BoolValue &evaluateBooleanEquality(const Expr &LHS, const Expr &RHS, class TransferVisitor : public ConstStmtVisitor<TransferVisitor> { public: - TransferVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env) - : StmtToEnv(StmtToEnv), Env(Env) {} + TransferVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env, + TransferOptions Options) + : StmtToEnv(StmtToEnv), Env(Env), Options(Options) {} void VisitBinaryOperator(const BinaryOperator *S) { const Expr *LHS = S->getLHS(); @@ -503,6 +506,35 @@ public: if (ArgLoc == nullptr) return; Env.setStorageLocation(*S, *ArgLoc); + } else if (const FunctionDecl *F = S->getDirectCallee()) { + // This case is for context-sensitive analysis, which we only do if we + // have the callee body available in the translation unit. + if (!Options.ContextSensitive || F->getBody() == nullptr) + return; + + auto &ASTCtx = F->getASTContext(); + + // FIXME: Cache these CFGs. + auto CFCtx = ControlFlowContext::build(F, F->getBody(), &ASTCtx); + // FIXME: Handle errors here and below. + assert(CFCtx); + auto ExitBlock = CFCtx->getCFG().getExit().getBlockID(); + + auto CalleeEnv = Env.pushCall(S); + + // FIXME: Use the same analysis as the caller for the callee. + DataflowAnalysisOptions Options; + auto Analysis = NoopAnalysis(ASTCtx, Options); + + auto BlockToOutputState = + dataflow::runDataflowAnalysis(*CFCtx, Analysis, CalleeEnv); + assert(BlockToOutputState); + assert(ExitBlock < BlockToOutputState->size()); + + auto ExitState = (*BlockToOutputState)[ExitBlock]; + assert(ExitState); + + Env = ExitState->Env; } } @@ -564,11 +596,11 @@ public: Env.setValue(Loc, *Val); if (Type->isStructureOrClassType()) { - for (auto IT : llvm::zip(Type->getAsRecordDecl()->fields(), S->inits())) { - const FieldDecl *Field = std::get<0>(IT); + for (auto It : llvm::zip(Type->getAsRecordDecl()->fields(), S->inits())) { + const FieldDecl *Field = std::get<0>(It); assert(Field != nullptr); - const Expr *Init = std::get<1>(IT); + const Expr *Init = std::get<1>(It); assert(Init != nullptr); if (Value *InitVal = Env.getValue(*Init, SkipPast::None)) @@ -633,10 +665,12 @@ private: const StmtToEnvMap &StmtToEnv; Environment &Env; + TransferOptions Options; }; -void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env) { - TransferVisitor(StmtToEnv, Env).Visit(&S); +void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env, + TransferOptions Options) { + TransferVisitor(StmtToEnv, Env, Options).Visit(&S); } } // namespace dataflow diff --git a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp index 6ce9dd55914d..fbb521763ee6 100644 --- a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp +++ b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp @@ -47,9 +47,9 @@ public: : CFCtx(CFCtx), BlockToState(BlockToState) {} const Environment *getEnvironment(const Stmt &S) const override { - auto BlockIT = CFCtx.getStmtToBlock().find(&ignoreCFGOmittedNodes(S)); - assert(BlockIT != CFCtx.getStmtToBlock().end()); - const auto &State = BlockToState[BlockIT->getSecond()->getBlockID()]; + auto BlockIt = CFCtx.getStmtToBlock().find(&ignoreCFGOmittedNodes(S)); + assert(BlockIt != CFCtx.getStmtToBlock().end()); + const auto &State = BlockToState[BlockIt->getSecond()->getBlockID()]; assert(State); return &State.value().Env; } @@ -74,8 +74,9 @@ static int blockIndexInPredecessor(const CFGBlock &Pred, class TerminatorVisitor : public ConstStmtVisitor<TerminatorVisitor> { public: TerminatorVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env, - int BlockSuccIdx) - : StmtToEnv(StmtToEnv), Env(Env), BlockSuccIdx(BlockSuccIdx) {} + int BlockSuccIdx, TransferOptions TransferOpts) + : StmtToEnv(StmtToEnv), Env(Env), BlockSuccIdx(BlockSuccIdx), + TransferOpts(TransferOpts) {} void VisitIfStmt(const IfStmt *S) { auto *Cond = S->getCond(); @@ -118,7 +119,7 @@ private: void extendFlowCondition(const Expr &Cond) { // The terminator sub-expression might not be evaluated. if (Env.getStorageLocation(Cond, SkipPast::None) == nullptr) - transfer(StmtToEnv, Cond, Env); + transfer(StmtToEnv, Cond, Env, TransferOpts); // FIXME: The flow condition must be an r-value, so `SkipPast::None` should // suffice. @@ -150,6 +151,7 @@ private: const StmtToEnvMap &StmtToEnv; Environment &Env; int BlockSuccIdx; + TransferOptions TransferOpts; }; /// Computes the input state for a given basic block by joining the output @@ -217,7 +219,8 @@ static TypeErasedDataflowAnalysisState computeBlockInputState( if (const Stmt *PredTerminatorStmt = Pred->getTerminatorStmt()) { const StmtToEnvMapImpl StmtToEnv(CFCtx, BlockStates); TerminatorVisitor(StmtToEnv, PredState.Env, - blockIndexInPredecessor(*Pred, Block)) + blockIndexInPredecessor(*Pred, Block), + Analysis.builtinTransferOptions()) .Visit(PredTerminatorStmt); } } @@ -253,7 +256,8 @@ static void transferCFGStmt( assert(S != nullptr); if (Analysis.applyBuiltinTransfer()) - transfer(StmtToEnvMapImpl(CFCtx, BlockStates), *S, State.Env); + transfer(StmtToEnvMapImpl(CFCtx, BlockStates), *S, State.Env, + Analysis.builtinTransferOptions()); Analysis.transferTypeErased(S, State.Lattice, State.Env); if (HandleTransferredStmt != nullptr) diff --git a/clang/lib/Analysis/FlowSensitive/WatchedLiteralsSolver.cpp b/clang/lib/Analysis/FlowSensitive/WatchedLiteralsSolver.cpp index 6a3948bd1fea..cd1fd708a43a 100644 --- a/clang/lib/Analysis/FlowSensitive/WatchedLiteralsSolver.cpp +++ b/clang/lib/Analysis/FlowSensitive/WatchedLiteralsSolver.cpp @@ -221,6 +221,18 @@ BooleanFormula buildBooleanFormula(const llvm::DenseSet<BoolValue *> &Vals) { UnprocessedSubVals.push(&N->getSubVal()); break; } + case Value::Kind::Implication: { + auto *I = cast<ImplicationValue>(Val); + UnprocessedSubVals.push(&I->getLeftSubValue()); + UnprocessedSubVals.push(&I->getRightSubValue()); + break; + } + case Value::Kind::Biconditional: { + auto *B = cast<BiconditionalValue>(Val); + UnprocessedSubVals.push(&B->getLeftSubValue()); + UnprocessedSubVals.push(&B->getRightSubValue()); + break; + } case Value::Kind::AtomicBool: { Atomics[Var] = cast<AtomicBoolValue>(Val); break; @@ -263,30 +275,52 @@ BooleanFormula buildBooleanFormula(const llvm::DenseSet<BoolValue *> &Vals) { const Variable LeftSubVar = GetVar(&C->getLeftSubValue()); const Variable RightSubVar = GetVar(&C->getRightSubValue()); - // `X <=> (A ^ B)` is equivalent to `(!X v A) ^ (!X v B) ^ (X v !A v !B)` - // which is already in conjunctive normal form. Below we add each of the - // conjuncts of the latter expression to the result. - Formula.addClause(negLit(Var), posLit(LeftSubVar)); - Formula.addClause(negLit(Var), posLit(RightSubVar)); - Formula.addClause(posLit(Var), negLit(LeftSubVar), negLit(RightSubVar)); + if (LeftSubVar == RightSubVar) { + // `X <=> (A ^ A)` is equivalent to `(!X v A) ^ (X v !A)` which is + // already in conjunctive normal form. Below we add each of the + // conjuncts of the latter expression to the result. + Formula.addClause(negLit(Var), posLit(LeftSubVar)); + Formula.addClause(posLit(Var), negLit(LeftSubVar)); - // Visit the sub-values of `Val`. - UnprocessedSubVals.push(&C->getLeftSubValue()); - UnprocessedSubVals.push(&C->getRightSubValue()); + // Visit a sub-value of `Val` (pick any, they are identical). + UnprocessedSubVals.push(&C->getLeftSubValue()); + } else { + // `X <=> (A ^ B)` is equivalent to `(!X v A) ^ (!X v B) ^ (X v !A v !B)` + // which is already in conjunctive normal form. Below we add each of the + // conjuncts of the latter expression to the result. + Formula.addClause(negLit(Var), posLit(LeftSubVar)); + Formula.addClause(negLit(Var), posLit(RightSubVar)); + Formula.addClause(posLit(Var), negLit(LeftSubVar), negLit(RightSubVar)); + + // Visit the sub-values of `Val`. + UnprocessedSubVals.push(&C->getLeftSubValue()); + UnprocessedSubVals.push(&C->getRightSubValue()); + } } else if (auto *D = dyn_cast<DisjunctionValue>(Val)) { const Variable LeftSubVar = GetVar(&D->getLeftSubValue()); const Variable RightSubVar = GetVar(&D->getRightSubValue()); - // `X <=> (A v B)` is equivalent to `(!X v A v B) ^ (X v !A) ^ (X v !B)` - // which is already in conjunctive normal form. Below we add each of the - // conjuncts of the latter expression to the result. - Formula.addClause(negLit(Var), posLit(LeftSubVar), posLit(RightSubVar)); - Formula.addClause(posLit(Var), negLit(LeftSubVar)); - Formula.addClause(posLit(Var), negLit(RightSubVar)); + if (LeftSubVar == RightSubVar) { + // `X <=> (A v A)` is equivalent to `(!X v A) ^ (X v !A)` which is + // already in conjunctive normal form. Below we add each of the + // conjuncts of the latter expression to the result. + Formula.addClause(negLit(Var), posLit(LeftSubVar)); + Formula.addClause(posLit(Var), negLit(LeftSubVar)); - // Visit the sub-values of `Val`. - UnprocessedSubVals.push(&D->getLeftSubValue()); - UnprocessedSubVals.push(&D->getRightSubValue()); + // Visit a sub-value of `Val` (pick any, they are identical). + UnprocessedSubVals.push(&D->getLeftSubValue()); + } else { + // `X <=> (A v B)` is equivalent to `(!X v A v B) ^ (X v !A) ^ (X v !B)` + // which is already in conjunctive normal form. Below we add each of the + // conjuncts of the latter expression to the result. + Formula.addClause(negLit(Var), posLit(LeftSubVar), posLit(RightSubVar)); + Formula.addClause(posLit(Var), negLit(LeftSubVar)); + Formula.addClause(posLit(Var), negLit(RightSubVar)); + + // Visit the sub-values of `Val`. + UnprocessedSubVals.push(&D->getLeftSubValue()); + UnprocessedSubVals.push(&D->getRightSubValue()); + } } else if (auto *N = dyn_cast<NegationValue>(Val)) { const Variable SubVar = GetVar(&N->getSubVal()); @@ -298,6 +332,46 @@ BooleanFormula buildBooleanFormula(const llvm::DenseSet<BoolValue *> &Vals) { // Visit the sub-values of `Val`. UnprocessedSubVals.push(&N->getSubVal()); + } else if (auto *I = dyn_cast<ImplicationValue>(Val)) { + const Variable LeftSubVar = GetVar(&I->getLeftSubValue()); + const Variable RightSubVar = GetVar(&I->getRightSubValue()); + + // `X <=> (A => B)` is equivalent to + // `(X v A) ^ (X v !B) ^ (!X v !A v B)` which is already in + // conjunctive normal form. Below we add each of the conjuncts of the + // latter expression to the result. + Formula.addClause(posLit(Var), posLit(LeftSubVar)); + Formula.addClause(posLit(Var), negLit(RightSubVar)); + Formula.addClause(negLit(Var), negLit(LeftSubVar), posLit(RightSubVar)); + + // Visit the sub-values of `Val`. + UnprocessedSubVals.push(&I->getLeftSubValue()); + UnprocessedSubVals.push(&I->getRightSubValue()); + } else if (auto *B = dyn_cast<BiconditionalValue>(Val)) { + const Variable LeftSubVar = GetVar(&B->getLeftSubValue()); + const Variable RightSubVar = GetVar(&B->getRightSubValue()); + + if (LeftSubVar == RightSubVar) { + // `X <=> (A <=> A)` is equvalent to `X` which is already in + // conjunctive normal form. Below we add each of the conjuncts of the + // latter expression to the result. + Formula.addClause(posLit(Var)); + + // No need to visit the sub-values of `Val`. + } else { + // `X <=> (A <=> B)` is equivalent to + // `(X v A v B) ^ (X v !A v !B) ^ (!X v A v !B) ^ (!X v !A v B)` which is + // already in conjunctive normal form. Below we add each of the conjuncts + // of the latter expression to the result. + Formula.addClause(posLit(Var), posLit(LeftSubVar), posLit(RightSubVar)); + Formula.addClause(posLit(Var), negLit(LeftSubVar), negLit(RightSubVar)); + Formula.addClause(negLit(Var), posLit(LeftSubVar), negLit(RightSubVar)); + Formula.addClause(negLit(Var), negLit(LeftSubVar), posLit(RightSubVar)); + + // Visit the sub-values of `Val`. + UnprocessedSubVals.push(&B->getLeftSubValue()); + UnprocessedSubVals.push(&B->getRightSubValue()); + } } } diff --git a/clang/lib/Analysis/LiveVariables.cpp b/clang/lib/Analysis/LiveVariables.cpp index 6c601c290c92..ff7f3ebe28f8 100644 --- a/clang/lib/Analysis/LiveVariables.cpp +++ b/clang/lib/Analysis/LiveVariables.cpp @@ -72,6 +72,11 @@ bool LiveVariables::LivenessValues::isLive(const VarDecl *D) const { bool alive = false; for (const BindingDecl *BD : DD->bindings()) alive |= liveBindings.contains(BD); + + // Note: the only known case this condition is necessary, is when a bindig + // to a tuple-like structure is created. The HoldingVar initializers have a + // DeclRefExpr to the DecompositionDecl. + alive |= liveDecls.contains(DD); return alive; } return liveDecls.contains(D); @@ -343,8 +348,12 @@ void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) { if (const BindingDecl* BD = dyn_cast<BindingDecl>(D)) { Killed = !BD->getType()->isReferenceType(); - if (Killed) + if (Killed) { + if (const auto *HV = BD->getHoldingVar()) + val.liveDecls = LV.DSetFact.remove(val.liveDecls, HV); + val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD); + } } else if (const auto *VD = dyn_cast<VarDecl>(D)) { Killed = writeShouldKill(VD); if (Killed) @@ -371,8 +380,12 @@ void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) { const Decl* D = DR->getDecl(); bool InAssignment = LV.inAssignment[DR]; if (const auto *BD = dyn_cast<BindingDecl>(D)) { - if (!InAssignment) + if (!InAssignment) { + if (const auto *HV = BD->getHoldingVar()) + val.liveDecls = LV.DSetFact.add(val.liveDecls, HV); + val.liveBindings = LV.BSetFact.add(val.liveBindings, BD); + } } else if (const auto *VD = dyn_cast<VarDecl>(D)) { if (!InAssignment && !isAlwaysAlive(VD)) val.liveDecls = LV.DSetFact.add(val.liveDecls, VD); @@ -382,8 +395,16 @@ void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) { void TransferFunctions::VisitDeclStmt(DeclStmt *DS) { for (const auto *DI : DS->decls()) { if (const auto *DD = dyn_cast<DecompositionDecl>(DI)) { - for (const auto *BD : DD->bindings()) + for (const auto *BD : DD->bindings()) { + if (const auto *HV = BD->getHoldingVar()) + val.liveDecls = LV.DSetFact.remove(val.liveDecls, HV); + val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD); + } + + // When a bindig to a tuple-like structure is created, the HoldingVar + // initializers have a DeclRefExpr to the DecompositionDecl. + val.liveDecls = LV.DSetFact.remove(val.liveDecls, DD); } else if (const auto *VD = dyn_cast<VarDecl>(DI)) { if (!isAlwaysAlive(VD)) val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); |