diff options
Diffstat (limited to 'clang/lib/Analysis/FlowSensitive')
3 files changed, 68 insertions, 39 deletions
diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp index 05395e07..3cb656a 100644 --- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp +++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp @@ -237,13 +237,8 @@ joinLocToVal(const llvm::MapVector<const StorageLocation *, Value *> &LocToVal, continue; assert(It->second != nullptr); - if (areEquivalentValues(*Val, *It->second)) { - Result.insert({Loc, Val}); - continue; - } - - if (Value *JoinedVal = joinDistinctValues( - Loc->getType(), *Val, Env1, *It->second, Env2, JoinedEnv, Model)) { + if (Value *JoinedVal = Environment::joinValues( + Loc->getType(), Val, Env1, It->second, Env2, JoinedEnv, Model)) { Result.insert({Loc, JoinedVal}); } } @@ -775,27 +770,16 @@ Environment Environment::join(const Environment &EnvA, const Environment &EnvB, JoinedEnv.LocForRecordReturnVal = EnvA.LocForRecordReturnVal; JoinedEnv.ThisPointeeLoc = EnvA.ThisPointeeLoc; - if (EnvA.ReturnVal == nullptr || EnvB.ReturnVal == nullptr) { - // `ReturnVal` might not always get set -- for example if we have a return - // statement of the form `return some_other_func()` and we decide not to - // analyze `some_other_func()`. - // In this case, we can't say anything about the joined return value -- we - // don't simply want to propagate the return value that we do have, because - // it might not be the correct one. - // This occurs for example in the test `ContextSensitiveMutualRecursion`. + if (EnvA.CallStack.empty()) { JoinedEnv.ReturnVal = nullptr; - } else if (areEquivalentValues(*EnvA.ReturnVal, *EnvB.ReturnVal)) { - JoinedEnv.ReturnVal = EnvA.ReturnVal; } else { - assert(!EnvA.CallStack.empty()); // FIXME: Make `CallStack` a vector of `FunctionDecl` so we don't need this // cast. auto *Func = dyn_cast<FunctionDecl>(EnvA.CallStack.back()); assert(Func != nullptr); - if (Value *JoinedVal = - joinDistinctValues(Func->getReturnType(), *EnvA.ReturnVal, EnvA, - *EnvB.ReturnVal, EnvB, JoinedEnv, Model)) - JoinedEnv.ReturnVal = JoinedVal; + JoinedEnv.ReturnVal = + joinValues(Func->getReturnType(), EnvA.ReturnVal, EnvA, EnvB.ReturnVal, + EnvB, JoinedEnv, Model); } if (EnvA.ReturnLoc == EnvB.ReturnLoc) @@ -821,6 +805,24 @@ Environment Environment::join(const Environment &EnvA, const Environment &EnvB, return JoinedEnv; } +Value *Environment::joinValues(QualType Ty, Value *Val1, + const Environment &Env1, Value *Val2, + const Environment &Env2, Environment &JoinedEnv, + Environment::ValueModel &Model) { + if (Val1 == nullptr || Val2 == nullptr) + // We can't say anything about the joined value -- even if one of the values + // is non-null, we don't want to simply propagate it, because it would be + // too specific: Because the other value is null, that means we have no + // information at all about the value (i.e. the value is unconstrained). + return nullptr; + + if (areEquivalentValues(*Val1, *Val2)) + // Arbitrarily return one of the two values. + return Val1; + + return joinDistinctValues(Ty, *Val1, Env1, *Val2, Env2, JoinedEnv, Model); +} + StorageLocation &Environment::createStorageLocation(QualType Type) { return DACtx->createStorageLocation(Type); } diff --git a/clang/lib/Analysis/FlowSensitive/Transfer.cpp b/clang/lib/Analysis/FlowSensitive/Transfer.cpp index 2771c8b..f56fd64 100644 --- a/clang/lib/Analysis/FlowSensitive/Transfer.cpp +++ b/clang/lib/Analysis/FlowSensitive/Transfer.cpp @@ -124,8 +124,9 @@ namespace { class TransferVisitor : public ConstStmtVisitor<TransferVisitor> { public: - TransferVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env) - : StmtToEnv(StmtToEnv), Env(Env) {} + TransferVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env, + Environment::ValueModel &Model) + : StmtToEnv(StmtToEnv), Env(Env), Model(Model) {} void VisitBinaryOperator(const BinaryOperator *S) { const Expr *LHS = S->getLHS(); @@ -641,17 +642,41 @@ public: } void VisitConditionalOperator(const ConditionalOperator *S) { - // FIXME: Revisit this once flow conditions are added to the framework. For - // `a = b ? c : d` we can add `b => a == c && !b => a == d` to the flow - // condition. - // When we do this, we will need to retrieve the values of the operands from - // the environments for the basic blocks they are computed in, in a similar - // way to how this is done for short-circuited logical operators in - // `getLogicOperatorSubExprValue()`. - if (S->isGLValue()) - Env.setStorageLocation(*S, Env.createObject(S->getType())); - else if (!S->getType()->isRecordType()) { - if (Value *Val = Env.createValue(S->getType())) + const Environment *TrueEnv = StmtToEnv.getEnvironment(*S->getTrueExpr()); + const Environment *FalseEnv = StmtToEnv.getEnvironment(*S->getFalseExpr()); + + if (TrueEnv == nullptr || FalseEnv == nullptr) { + // We should always have an environment as we should visit the true / + // false branches before the conditional operator. + assert(false); + return; + } + + if (S->isGLValue()) { + StorageLocation *TrueLoc = TrueEnv->getStorageLocation(*S->getTrueExpr()); + StorageLocation *FalseLoc = + FalseEnv->getStorageLocation(*S->getFalseExpr()); + if (TrueLoc == FalseLoc && TrueLoc != nullptr) + Env.setStorageLocation(*S, *TrueLoc); + } else if (!S->getType()->isRecordType()) { + // The conditional operator can evaluate to either of the values of the + // two branches. To model this, join these two values together to yield + // the result of the conditional operator. + // Note: Most joins happen in `computeBlockInputState()`, but this case is + // different: + // - `computeBlockInputState()` (which in turn calls `Environment::join()` + // joins values associated with the _same_ expression or storage + // location, then associates the joined value with that expression or + // storage location. This join has nothing to do with transfer -- + // instead, it joins together the results of performing transfer on two + // different blocks. + // - Here, we join values associated with _different_ expressions (the + // true and false branch), then associate the joined value with a third + // expression (the conditional operator itself). This join is what it + // means to perform transfer on the conditional operator. + if (Value *Val = Environment::joinValues( + S->getType(), TrueEnv->getValue(*S->getTrueExpr()), *TrueEnv, + FalseEnv->getValue(*S->getFalseExpr()), *FalseEnv, Env, Model)) Env.setValue(*S, *Val); } } @@ -810,12 +835,14 @@ private: const StmtToEnvMap &StmtToEnv; Environment &Env; + Environment::ValueModel &Model; }; } // namespace -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, + Environment::ValueModel &Model) { + TransferVisitor(StmtToEnv, Env, Model).Visit(&S); } } // namespace dataflow diff --git a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp index 71d5c1a..12eff4d 100644 --- a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp +++ b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp @@ -316,7 +316,7 @@ builtinTransferStatement(unsigned CurBlockID, const CFGStmt &Elt, const Stmt *S = Elt.getStmt(); assert(S != nullptr); transfer(StmtToEnvMap(AC.ACFG, AC.BlockStates, CurBlockID, InputState), *S, - InputState.Env); + InputState.Env, AC.Analysis); } /// Built-in transfer function for `CFGInitializer`. @@ -452,7 +452,7 @@ transferCFGBlock(const CFGBlock &Block, AnalysisContext &AC, // terminator condition, but not as a `CFGElement`. The condition of an if // statement is one such example. transfer(StmtToEnvMap(AC.ACFG, AC.BlockStates, Block.getBlockID(), State), - *TerminatorCond, State.Env); + *TerminatorCond, State.Env, AC.Analysis); // If the transfer function didn't produce a value, create an atom so that // we have *some* value for the condition expression. This ensures that |