From 2a9d82a740bb8edacbd6102934cd22f5b352ba56 Mon Sep 17 00:00:00 2001 From: Ted Kremenek Date: Mon, 17 Sep 2007 21:59:08 +0000 Subject: [PATCH] Bug fix to merging of data flow values (merge incorrectly made values too "conservative"). Several revisions to UninitializedValues checker after testing. We now appear to be working correctly (probably some bugs still, but main functionality appears to be there). Implemented careful emitting of warnings so that we wouldn't get a cascade of warnings for simply not defining a single variable and using it everywhere. This way the warnings point closer to the root cause rather than "symptoms" from using values derived from uninitialized variables. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@42067 91177308-0d34-0410-b5e6-96231b3b80d8 --- Analysis/DataflowSolver.h | 45 +++++++++++++++++++++++--------- Analysis/UninitializedValues.cpp | 30 ++++++++++++++++----- 2 files changed, 55 insertions(+), 20 deletions(-) diff --git a/Analysis/DataflowSolver.h b/Analysis/DataflowSolver.h index 4a089dbcdc..5266af3407 100644 --- a/Analysis/DataflowSolver.h +++ b/Analysis/DataflowSolver.h @@ -85,6 +85,9 @@ public: /// only be used for querying the dataflow values within a block with /// and Observer object. void runOnBlock(const CFGBlock* B) { + if (D.getBlockDataMap().find(B) == D.getBlockDataMap().end()) + return; + TransferFuncsTy TF (D.getAnalysisData()); ProcessBlock(B,TF,AnalysisDirTag()); } @@ -118,14 +121,6 @@ private: I != E; ++I) WorkList.enqueue(*I); } - - // For blocks that have no associated dataflow value, instantiate a - // default value. - BlockDataMapTy& M = D.getBlockDataMap(); - - for (CFG::const_iterator I=cfg.begin(), E=cfg.end(); I!=E; ++I) - if (M.find(&*I) == M.end()) - M[&*I].resetValues(D.getAnalysisData()); } /// SolveDataflowEquations (BACKWARD ANALYSIS) - Perform the actual @@ -155,7 +150,7 @@ private: /// ProcessBlock (FORWARD ANALYSIS) - Process the transfer functions /// for a given block based on a forward analysis. - bool ProcessBlock(const CFGBlock* B, TransferFuncsTy& TF, + bool ProcessBlock(const CFGBlock* B, TransferFuncsTy& TF, dataflow::forward_analysis_tag) { ValTy& V = TF.getVal(); @@ -164,9 +159,21 @@ private: V.resetValues(D.getAnalysisData()); MergeOperatorTy Merge; + BlockDataMapTy& M = D.getBlockDataMap(); + bool firstMerge = true; + for (CFGBlock::const_pred_iterator I=B->pred_begin(), - E=B->pred_end(); I!=E; ++I) - Merge(V,D.getBlockData(*I)); + E=B->pred_end(); I!=E; ++I) { + typename BlockDataMapTy::iterator BI = M.find(*I); + if (BI != M.end()) { + if (firstMerge) { + firstMerge = false; + V.copyValues(BI->second); + } + else + Merge(V,BI->second); + } + } // Process the statements in the block in the forward direction. for (CFGBlock::const_iterator I=B->begin(), E=B->end(); I!=E; ++I) @@ -186,9 +193,21 @@ private: V.resetValues(D.getAnalysisData()); MergeOperatorTy Merge; + BlockDataMapTy& M = D.getBlockDataMap(); + bool firstMerge = true; + for (CFGBlock::const_succ_iterator I=B->succ_begin(), - E=B->succ_end(); I!=E; ++I) - Merge(V,D.getBlockData(*I)); + E=B->succ_end(); I!=E; ++I) { + typename BlockDataMapTy::iterator BI = M.find(*I); + if (BI != M.end()) { + if (firstMerge) { + firstMerge = false; + V.copyValues(BI->second); + } + else + Merge(V,BI->second); + } + } // Process the statements in the block in the forward direction. for (CFGBlock::const_reverse_iterator I=B->begin(), E=B->end(); I!=E; ++I) diff --git a/Analysis/UninitializedValues.cpp b/Analysis/UninitializedValues.cpp index ce9454d0cc..c5b13a4074 100644 --- a/Analysis/UninitializedValues.cpp +++ b/Analysis/UninitializedValues.cpp @@ -75,8 +75,8 @@ void UninitializedValues::InitializeValues(const CFG& cfg) { R.BlockStmt_Visit(*BI); // Initialize the values of the last block. - UninitializedValues::ValTy& V = getBlockDataMap()[&cfg.getEntry()]; - V.resetValues(getAnalysisData()); +// UninitializedValues::ValTy& V = getBlockDataMap()[&cfg.getEntry()]; +// V.resetValues(getAnalysisData()); } //===----------------------------------------------------------------------===// @@ -88,8 +88,11 @@ namespace { class TransferFuncs : public CFGStmtVisitor { UninitializedValues::ValTy V; UninitializedValues::AnalysisDataTy& AD; + bool InitWithAssigns; public: - TransferFuncs(UninitializedValues::AnalysisDataTy& ad) : AD(ad) { + TransferFuncs(UninitializedValues::AnalysisDataTy& ad, + bool init_with_assigns=true) : + AD(ad), InitWithAssigns(init_with_assigns) { V.resetValues(AD); } @@ -134,9 +137,21 @@ bool TransferFuncs::VisitBinaryOperator(BinaryOperator* B) { else if (DeclRefExpr* DR = dyn_cast(S)) if (BlockVarDecl* VD = dyn_cast(DR->getDecl())) { assert ( AD.VMap.find(VD) != AD.VMap.end() && "Unknown VarDecl."); - return V.DeclBV[ AD.VMap[VD] ] = Visit(B->getRHS()); + + if(InitWithAssigns) { + // Pseudo-hack to prevent cascade of warnings. If the RHS uses + // an uninitialized value, then we are already going to flag a warning + // related to the "cause". Thus, propogating uninitialized doesn't + // make sense, since we are just adding extra messages that don't + // contribute to diagnosing the bug. In InitWithAssigns mode + // we unconditionally set the assigned variable to Initialized to + // prevent Uninitialized propogation. + return V.DeclBV[AD.VMap[VD]] = Initialized(); + } + else + return V.DeclBV[ AD.VMap[VD] ] = Visit(B->getRHS()); } - + break; } } @@ -154,7 +169,8 @@ bool TransferFuncs::VisitDeclStmt(DeclStmt* S) { AD.EMap.end() && "Unknown Expr."); assert ( AD.VMap.find(VD) != AD.VMap.end() && "Unknown VarDecl."); - x = V.DeclBV[ AD.VMap[VD] ] = V.ExprBV[ AD.EMap[cast(I)] ]; + x = V.ExprBV[ AD.EMap[cast(I)] ]; + V.DeclBV[ AD.VMap[VD] ] = x; } return x; @@ -246,7 +262,7 @@ struct Merge { assert (Dst.ExprBV.size() == Src.ExprBV.size() && "Bitvector sizes do not match."); - Dst.ExprBV |= Src.ExprBV; + Dst.ExprBV &= Src.ExprBV; } }; } // end anonymous namespace -- 2.50.1