Children.push_back(C);
return C;
}
-
+
size_t getNumChildren() const {
return Children.size();
}
// FIXME: Should remove this
virtual bool runOnFunction(Function &F) { return false; }
+ /// compare - Return false if the other dominator tree base maches this
+ /// dominator tree base. Otherwise return true.
+ bool compare(DominatorTreeBase &Other) const {
+
+ // Collect nodes.
+ SmallPtrSet<const NodeT *,4> MyBBs;
+ for (typename DomTreeNodeMapType::const_iterator
+ I = this->DomTreeNodes.begin(),
+ E = this->DomTreeNodes.end(); I != E; ++I) {
+ const NodeT *BB = I->first;
+ MyBBs.insert(BB);
+ }
+
+ SmallPtrSet<const NodeT *,4> OtherBBs;
+ const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
+ for (typename DomTreeNodeMapType::const_iterator
+ I = OtherDomTreeNodes.begin(),
+ E = OtherDomTreeNodes.end(); I != E; ++I) {
+ const NodeT *BB = I->first;
+ OtherBBs.insert(BB);
+ }
+
+ if (OtherBBs.size() != MyBBs.size())
+ return true;
+
+ // Compare node sets.
+ for (typename SmallPtrSet<const NodeT *,4>::const_iterator I = MyBBs.begin(),
+ E = MyBBs.end(); I != E; ++I) {
+ const NodeT *BB = *I;
+ if (OtherBBs.erase(BB) == 0)
+ return true;
+ }
+ if (!OtherBBs.empty())
+ return true;
+ return false;
+ }
+
virtual void releaseMemory() { reset(); }
/// getNode - return the (Post)DominatorTree node for the specified basic
inline DomTreeNode *getRootNode() const {
return DT->getRootNode();
}
-
+
+ /// compare - Return false if the other dominator tree maches this
+ /// dominator tree. Otherwise return true.
+ inline bool compare(DominatorTree &Other) const {
+ DomTreeNode *R = getRootNode();
+ DomTreeNode *OtherR = Other.getRootNode();
+
+ if (!R || !OtherR || R->getBlock() != OtherR->getBlock())
+ return true;
+
+ if (DT->compare(Other.getBase()))
+ return true;
+
+ return false;
+ }
+
virtual bool runOnFunction(Function &F);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
protected:
DomSetMapType Frontiers;
- std::vector<BasicBlock*> Roots;
- const bool IsPostDominators;
+ std::vector<BasicBlock*> Roots;
+ const bool IsPostDominators;
public:
DominanceFrontierBase(intptr_t ID, bool isPostDom)
I->second.erase(Node);
}
+ /// compareDomSet - Return false if two domsets match. Otherwise
+ /// return ture;
+ bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const {
+ std::set<BasicBlock *> tmpSet;
+ for (DomSetType::const_iterator I = DS2.begin(),
+ E = DS2.end(); I != E; ++I)
+ tmpSet.insert(*I);
+
+ for (DomSetType::const_iterator I = DS1.begin(),
+ E = DS1.end(); I != E; ++I) {
+ BasicBlock *Node = *I;
+
+ if (tmpSet.erase(Node) == 0)
+ // Node is in DS1 but not in DS2.
+ return true;
+ }
+
+ if(!tmpSet.empty())
+ // There are nodes that are in DS2 but not in DS1.
+ return true;
+
+ // DS1 and DS2 matches.
+ return false;
+ }
+
+ /// compare - Return true if the other dominance frontier base matches
+ /// this dominance frontier base. Otherwise return false.
+ bool compare(DominanceFrontierBase &Other) const {
+ DomSetMapType tmpFrontiers;
+ for (DomSetMapType::const_iterator I = Other.begin(),
+ E = Other.end(); I != E; ++I)
+ tmpFrontiers.insert(std::make_pair(I->first, I->second));
+
+ for (DomSetMapType::iterator I = tmpFrontiers.begin(),
+ E = tmpFrontiers.end(); I != E; ++I) {
+ BasicBlock *Node = I->first;
+ const_iterator DFI = find(Node);
+ if (DFI == end())
+ return true;
+
+ if (compareDomSet(I->second, DFI->second))
+ return true;
+
+ tmpFrontiers.erase(Node);
+ }
+
+ if (!tmpFrontiers.empty())
+ return true;
+
+ return false;
+ }
+
/// print - Convert to human readable form
///
virtual void print(std::ostream &OS, const Module* = 0) const;
NewDFI->second.erase(BB);
}
-private:
const DomSetType &calculate(const DominatorTree &DT,
const DomTreeNode *Node);
};
#include "llvm/ModuleProvider.h"
#include "llvm/Support/Streams.h"
#include "llvm/Support/ManagedStatic.h"
+#include "llvm/Analysis/Dominators.h"
#include "llvm-c/Core.h"
#include <algorithm>
#include <vector>
None, Arguments, Structure, Executions, Details
};
+bool VerifyDomInfo = false;
+static cl::opt<bool,true>
+VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo),
+ cl::desc("Verify dominator info (time consuming)"));
+
static cl::opt<enum PassDebugLevel>
PassDebugging("debug-pass", cl::Hidden,
cl::desc("Print PassManager debugging information"),
}
}
+/// verifyDomInfo - Verify dominator information if it is available.
+void PMDataManager::verifyDomInfo(Pass &P, Function &F) {
+
+ if (!VerifyDomInfo || !P.getResolver())
+ return;
+
+ DominatorTree *DT = P.getAnalysisToUpdate<DominatorTree>();
+ if (!DT)
+ return;
+
+ DominatorTree OtherDT;
+ OtherDT.getBase().recalculate(F);
+ if (DT->compare(OtherDT)) {
+ cerr << "Dominator Information for " << F.getNameStart() << "\n";
+ cerr << "Pass " << P.getPassName() << "\n";
+ cerr << "----- Valid -----\n";
+ OtherDT.dump();
+ cerr << "----- InValid -----\n";
+ DT->dump();
+ assert (0 && "Invalid dominator info");
+ }
+
+ DominanceFrontier *DF = P.getAnalysisToUpdate<DominanceFrontier>();
+ if (!DF)
+ return;
+
+ DominanceFrontier OtherDF;
+ std::vector<BasicBlock*> DTRoots = DT->getRoots();
+ OtherDF.calculate(*DT, DT->getNode(DTRoots[0]));
+ if (DF->compare(OtherDF)) {
+ cerr << "Dominator Information for " << F.getNameStart() << "\n";
+ cerr << "Pass " << P.getPassName() << "\n";
+ cerr << "----- Valid -----\n";
+ OtherDF.dump();
+ cerr << "----- InValid -----\n";
+ DF->dump();
+ assert (0 && "Invalid dominator info");
+ }
+}
+
/// Remove Analyss not preserved by Pass P
void PMDataManager::removeNotPreservedAnalysis(Pass *P) {
AnalysisUsage AnUsage;
InheritedAnalysis[Index]->erase(Info);
}
}
-
}
/// Remove analysis passes that are not used any longer
Pass *PRequired = *I;
unsigned RDepth = 0;
+ assert (PRequired->getResolver() && "Analysis Resolver is not set");
PMDataManager &DM = PRequired->getResolver()->getPMDataManager();
RDepth = DM.getDepth();
// If that is not the case then it will raise an assert when it is used.
continue;
AnalysisResolver *AR = P->getResolver();
+ assert (AR && "Analysis Resolver is not set");
AR->addAnalysisImplsPair(*I, Impl);
}
}
removeNotPreservedAnalysis(FP);
recordAvailableAnalysis(FP);
removeDeadPasses(FP, F.getNameStart(), ON_FUNCTION_MSG);
+
+ // Verify dominator information if it is available and preserved.
+ verifyDomInfo(*FP, F);
}
return Changed;
}