Consumed analysis: improve loop handling. The prior version of the analysis
marked all variables as "unknown" at the start of a loop. The new version
keeps the initial state of variables unchanged, but issues a warning if the
state at the end of the loop is different from the state at the beginning.
This patch will eventually be replaced with a more precise analysis.
Initial patch by chris.wailes@gmail.com. Reviewed and edited by
delesley@google.com.
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@192314 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/Consumed.cpp b/lib/Analysis/Consumed.cpp
index ee8dd77..d291f62 100644
--- a/lib/Analysis/Consumed.cpp
+++ b/lib/Analysis/Consumed.cpp
@@ -31,18 +31,15 @@
#include "llvm/Support/Compiler.h"
#include "llvm/Support/raw_ostream.h"
+// TODO: Use information from tests in while-loop conditional.
// TODO: Add notes about the actual and expected state for
// TODO: Correctly identify unreachable blocks when chaining boolean operators.
// TODO: Adjust the parser and AttributesList class to support lists of
// identifiers.
// TODO: Warn about unreachable code.
// TODO: Switch to using a bitmap to track unreachable blocks.
-// TODO: Mark variables as Unknown going into while- or for-loops only if they
-// are referenced inside that block. (Deferred)
// TODO: Handle variable definitions, e.g. bool valid = x.isValid();
// if (valid) ...; (Deferred)
-// TODO: Add a method(s) to identify which method calls perform what state
-// transitions. (Deferred)
// TODO: Take notes on state transitions to provide better warning messages.
// (Deferred)
// TODO: Test nested conditionals: A) Checking the same value multiple times,
@@ -54,6 +51,27 @@
// Key method definition
ConsumedWarningsHandlerBase::~ConsumedWarningsHandlerBase() {}
+static SourceLocation getWarningLocForLoopExit(const CFGBlock *ExitBlock) {
+ // Find the source location of the last statement in the block, if the block
+ // is not empty.
+ if (const Stmt *StmtNode = ExitBlock->getTerminator()) {
+ return StmtNode->getLocStart();
+ } else {
+ for (CFGBlock::const_reverse_iterator BI = ExitBlock->rbegin(),
+ BE = ExitBlock->rend(); BI != BE; ++BI) {
+ // FIXME: Handle other CFGElement kinds.
+ if (Optional<CFGStmt> CS = BI->getAs<CFGStmt>())
+ return CS->getStmt()->getLocStart();
+ }
+ }
+
+ // The block is empty, and has a single predecessor. Use its exit location.
+ assert(ExitBlock->pred_size() == 1 && *ExitBlock->pred_begin() &&
+ ExitBlock->succ_size() != 0);
+
+ return getWarningLocForLoopExit(*ExitBlock->pred_begin());
+}
+
static ConsumedState invertConsumedUnconsumed(ConsumedState State) {
switch (State) {
case CS_Unconsumed:
@@ -897,11 +915,26 @@
}
}
+bool ConsumedBlockInfo::allBackEdgesVisited(const CFGBlock *CurrBlock,
+ const CFGBlock *TargetBlock) {
+
+ assert(CurrBlock && "Block pointer must not be NULL");
+ assert(TargetBlock && "TargetBlock pointer must not be NULL");
+
+ unsigned int CurrBlockOrder = VisitOrder[CurrBlock->getBlockID()];
+ for (CFGBlock::const_pred_iterator PI = TargetBlock->pred_begin(),
+ PE = TargetBlock->pred_end(); PI != PE; ++PI) {
+ if (*PI && CurrBlockOrder < VisitOrder[(*PI)->getBlockID()] )
+ return false;
+ }
+ return true;
+}
+
void ConsumedBlockInfo::addInfo(const CFGBlock *Block,
ConsumedStateMap *StateMap,
bool &AlreadyOwned) {
- if (VisitedBlocks.alreadySet(Block)) return;
+ assert(Block && "Block pointer must not be NULL");
ConsumedStateMap *Entry = StateMapsArray[Block->getBlockID()];
@@ -920,10 +953,7 @@
void ConsumedBlockInfo::addInfo(const CFGBlock *Block,
ConsumedStateMap *StateMap) {
- if (VisitedBlocks.alreadySet(Block)) {
- delete StateMap;
- return;
- }
+ assert(Block != NULL && "Block pointer must not be NULL");
ConsumedStateMap *Entry = StateMapsArray[Block->getBlockID()];
@@ -936,15 +966,56 @@
}
}
-ConsumedStateMap* ConsumedBlockInfo::getInfo(const CFGBlock *Block) {
+ConsumedStateMap* ConsumedBlockInfo::borrowInfo(const CFGBlock *Block) {
+ assert(Block && "Block pointer must not be NULL");
+ assert(StateMapsArray[Block->getBlockID()] && "Block has no block info");
+
return StateMapsArray[Block->getBlockID()];
}
-void ConsumedBlockInfo::markVisited(const CFGBlock *Block) {
- VisitedBlocks.insert(Block);
+void ConsumedBlockInfo::discardInfo(const CFGBlock *Block) {
+ unsigned int BlockID = Block->getBlockID();
+ delete StateMapsArray[BlockID];
+ StateMapsArray[BlockID] = NULL;
}
-ConsumedState ConsumedStateMap::getState(const VarDecl *Var) {
+ConsumedStateMap* ConsumedBlockInfo::getInfo(const CFGBlock *Block) {
+ assert(Block && "Block pointer must not be NULL");
+
+ ConsumedStateMap *StateMap = StateMapsArray[Block->getBlockID()];
+ if (isBackEdgeTarget(Block)) {
+ return new ConsumedStateMap(*StateMap);
+ } else {
+ StateMapsArray[Block->getBlockID()] = NULL;
+ return StateMap;
+ }
+}
+
+bool ConsumedBlockInfo::isBackEdge(const CFGBlock *From, const CFGBlock *To) {
+ assert(From && "From block must not be NULL");
+ assert(To && "From block must not be NULL");
+
+ return VisitOrder[From->getBlockID()] > VisitOrder[To->getBlockID()];
+}
+
+bool ConsumedBlockInfo::isBackEdgeTarget(const CFGBlock *Block) {
+ assert(Block != NULL && "Block pointer must not be NULL");
+
+ // Anything with less than two predecessors can't be the target of a back
+ // edge.
+ if (Block->pred_size() < 2)
+ return false;
+
+ unsigned int BlockVisitOrder = VisitOrder[Block->getBlockID()];
+ for (CFGBlock::const_pred_iterator PI = Block->pred_begin(),
+ PE = Block->pred_end(); PI != PE; ++PI) {
+ if (*PI && BlockVisitOrder < VisitOrder[(*PI)->getBlockID()])
+ return true;
+ }
+ return false;
+}
+
+ConsumedState ConsumedStateMap::getState(const VarDecl *Var) const {
MapType::const_iterator Entry = Map.find(Var);
if (Entry != Map.end()) {
@@ -963,8 +1034,8 @@
return;
}
- for (MapType::const_iterator DMI = Other->Map.begin(),
- DME = Other->Map.end(); DMI != DME; ++DMI) {
+ for (MapType::const_iterator DMI = Other->Map.begin(), DME = Other->Map.end();
+ DMI != DME; ++DMI) {
LocalState = this->getState(DMI->first);
@@ -976,19 +1047,34 @@
}
}
+void ConsumedStateMap::intersectAtLoopHead(const CFGBlock *LoopHead,
+ const CFGBlock *LoopBack, const ConsumedStateMap *LoopBackStates,
+ ConsumedWarningsHandlerBase &WarningsHandler) {
+
+ ConsumedState LocalState;
+ SourceLocation BlameLoc = getWarningLocForLoopExit(LoopBack);
+
+ for (MapType::const_iterator DMI = LoopBackStates->Map.begin(),
+ DME = LoopBackStates->Map.end(); DMI != DME; ++DMI) {
+
+ LocalState = this->getState(DMI->first);
+
+ if (LocalState == CS_None)
+ continue;
+
+ if (LocalState != DMI->second) {
+ Map[DMI->first] = CS_Unknown;
+ WarningsHandler.warnLoopStateMismatch(
+ BlameLoc, DMI->first->getNameAsString());
+ }
+ }
+}
+
void ConsumedStateMap::markUnreachable() {
this->Reachable = false;
Map.clear();
}
-void ConsumedStateMap::makeUnknown() {
- for (MapType::const_iterator DMI = Map.begin(), DME = Map.end(); DMI != DME;
- ++DMI) {
-
- Map[DMI->first] = CS_Unknown;
- }
-}
-
void ConsumedStateMap::setState(const VarDecl *Var, ConsumedState State) {
Map[Var] = State;
}
@@ -997,6 +1083,17 @@
Map.erase(Var);
}
+bool ConsumedStateMap::operator!=(const ConsumedStateMap *Other) const {
+ for (MapType::const_iterator DMI = Other->Map.begin(), DME = Other->Map.end();
+ DMI != DME; ++DMI) {
+
+ if (this->getState(DMI->first) != DMI->second)
+ return true;
+ }
+
+ return false;
+}
+
void ConsumedAnalyzer::determineExpectedReturnState(AnalysisDeclContext &AC,
const FunctionDecl *D) {
QualType ReturnType;
@@ -1126,10 +1223,11 @@
return;
determineExpectedReturnState(AC, D);
-
- BlockInfo = ConsumedBlockInfo(CFGraph);
-
+
PostOrderCFGView *SortedGraph = AC.getAnalysis<PostOrderCFGView>();
+ // AC.getCFG()->viewCFG(LangOptions());
+
+ BlockInfo = ConsumedBlockInfo(CFGraph->getNumBlockIDs(), SortedGraph);
CurrStates = new ConsumedStateMap();
ConsumedStmtVisitor Visitor(AC, *this, CurrStates);
@@ -1145,7 +1243,6 @@
E = SortedGraph->end(); I != E; ++I) {
const CFGBlock *CurrBlock = *I;
- BlockInfo.markVisited(CurrBlock);
if (CurrStates == NULL)
CurrStates = BlockInfo.getInfo(CurrBlock);
@@ -1181,27 +1278,33 @@
if (!splitState(CurrBlock, Visitor)) {
CurrStates->setSource(NULL);
- if (CurrBlock->succ_size() > 1) {
- CurrStates->makeUnknown();
+ if (CurrBlock->succ_size() > 1 ||
+ (CurrBlock->succ_size() == 1 &&
+ (*CurrBlock->succ_begin())->pred_size() > 1)) {
bool OwnershipTaken = false;
for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(),
SE = CurrBlock->succ_end(); SI != SE; ++SI) {
- if (*SI) BlockInfo.addInfo(*SI, CurrStates, OwnershipTaken);
+ if (*SI == NULL) continue;
+
+ if (BlockInfo.isBackEdge(CurrBlock, *SI)) {
+ BlockInfo.borrowInfo(*SI)->intersectAtLoopHead(*SI, CurrBlock,
+ CurrStates,
+ WarningsHandler);
+
+ if (BlockInfo.allBackEdgesVisited(*SI, CurrBlock))
+ BlockInfo.discardInfo(*SI);
+ } else {
+ BlockInfo.addInfo(*SI, CurrStates, OwnershipTaken);
+ }
}
if (!OwnershipTaken)
delete CurrStates;
CurrStates = NULL;
-
- } else if (CurrBlock->succ_size() == 1 &&
- (*CurrBlock->succ_begin())->pred_size() > 1) {
-
- BlockInfo.addInfo(*CurrBlock->succ_begin(), CurrStates);
- CurrStates = NULL;
}
}
} // End of block iterator.
diff --git a/lib/Sema/AnalysisBasedWarnings.cpp b/lib/Sema/AnalysisBasedWarnings.cpp
index a206acd..53e53b2 100644
--- a/lib/Sema/AnalysisBasedWarnings.cpp
+++ b/lib/Sema/AnalysisBasedWarnings.cpp
@@ -1477,6 +1477,13 @@
}
}
+ void warnLoopStateMismatch(SourceLocation Loc, StringRef VariableName) {
+ PartialDiagnosticAt Warning(Loc, S.PDiag(diag::warn_loop_state_mismatch) <<
+ VariableName);
+
+ Warnings.push_back(DelayedDiag(Warning, OptionalNotes()));
+ }
+
void warnReturnTypestateForUnconsumableType(SourceLocation Loc,
StringRef TypeName) {
PartialDiagnosticAt Warning(Loc, S.PDiag(