+ class DomTreeDFS {
+ public:
+ class Node {
+ friend class DomTreeDFS;
+ public:
+ typedef std::vector<Node *>::iterator iterator;
+ typedef std::vector<Node *>::const_iterator const_iterator;
+
+ unsigned getDFSNumIn() const { return DFSin; }
+ unsigned getDFSNumOut() const { return DFSout; }
+
+ BasicBlock *getBlock() const { return BB; }
+
+ iterator begin() { return Children.begin(); }
+ iterator end() { return Children.end(); }
+
+ const_iterator begin() const { return Children.begin(); }
+ const_iterator end() const { return Children.end(); }
+
+ bool dominates(const Node *N) const {
+ return DFSin <= N->DFSin && DFSout >= N->DFSout;
+ }
+
+ bool DominatedBy(const Node *N) const {
+ return N->dominates(this);
+ }
+
+ /// Sorts by the number of descendants. With this, you can iterate
+ /// through a sorted list and the first matching entry is the most
+ /// specific match for your basic block. The order provided is stable;
+ /// DomTreeDFS::Nodes with the same number of descendants are sorted by
+ /// DFS in number.
+ bool operator<(const Node &N) const {
+ unsigned spread = DFSout - DFSin;
+ unsigned N_spread = N.DFSout - N.DFSin;
+ if (spread == N_spread) return DFSin < N.DFSin;
+ return spread < N_spread;
+ }
+ bool operator>(const Node &N) const { return N < *this; }
+
+ private:
+ unsigned DFSin, DFSout;
+ BasicBlock *BB;
+
+ std::vector<Node *> Children;
+ };
+
+ // XXX: this may be slow. Instead of using "new" for each node, consider
+ // putting them in a vector to keep them contiguous.
+ explicit DomTreeDFS(DominatorTree *DT) {
+ std::stack<std::pair<Node *, DomTreeNode *> > S;
+
+ Entry = new Node;
+ Entry->BB = DT->getRootNode()->getBlock();
+ S.push(std::make_pair(Entry, DT->getRootNode()));
+
+ NodeMap[Entry->BB] = Entry;
+
+ while (!S.empty()) {
+ std::pair<Node *, DomTreeNode *> &Pair = S.top();
+ Node *N = Pair.first;
+ DomTreeNode *DTNode = Pair.second;
+ S.pop();
+
+ for (DomTreeNode::iterator I = DTNode->begin(), E = DTNode->end();
+ I != E; ++I) {
+ Node *NewNode = new Node;
+ NewNode->BB = (*I)->getBlock();
+ N->Children.push_back(NewNode);
+ S.push(std::make_pair(NewNode, *I));
+
+ NodeMap[NewNode->BB] = NewNode;
+ }
+ }
+
+ renumber();
+
+#ifndef NDEBUG
+ DEBUG(dump());
+#endif
+ }
+
+#ifndef NDEBUG
+ virtual
+#endif
+ ~DomTreeDFS() {
+ std::stack<Node *> S;
+
+ S.push(Entry);
+ while (!S.empty()) {
+ Node *N = S.top(); S.pop();
+
+ for (Node::iterator I = N->begin(), E = N->end(); I != E; ++I)
+ S.push(*I);
+
+ delete N;
+ }
+ }
+
+ /// getRootNode - This returns the entry node for the CFG of the function.
+ Node *getRootNode() const { return Entry; }
+
+ /// getNodeForBlock - return the node for the specified basic block.
+ Node *getNodeForBlock(BasicBlock *BB) const {
+ if (!NodeMap.count(BB)) return 0;
+ return const_cast<DomTreeDFS*>(this)->NodeMap[BB];
+ }
+
+ /// dominates - returns true if the basic block for I1 dominates that of
+ /// the basic block for I2. If the instructions belong to the same basic
+ /// block, the instruction first instruction sequentially in the block is
+ /// considered dominating.
+ bool dominates(Instruction *I1, Instruction *I2) {
+ BasicBlock *BB1 = I1->getParent(),
+ *BB2 = I2->getParent();
+ if (BB1 == BB2) {
+ if (isa<TerminatorInst>(I1)) return false;
+ if (isa<TerminatorInst>(I2)) return true;
+ if ( isa<PHINode>(I1) && !isa<PHINode>(I2)) return true;
+ if (!isa<PHINode>(I1) && isa<PHINode>(I2)) return false;
+
+ for (BasicBlock::const_iterator I = BB2->begin(), E = BB2->end();
+ I != E; ++I) {
+ if (&*I == I1) return true;
+ else if (&*I == I2) return false;
+ }
+ assert(!"Instructions not found in parent BasicBlock?");
+ } else {
+ Node *Node1 = getNodeForBlock(BB1),
+ *Node2 = getNodeForBlock(BB2);
+ return Node1 && Node2 && Node1->dominates(Node2);
+ }
+ return false; // Not reached
+ }
+
+ private:
+ /// renumber - calculates the depth first search numberings and applies
+ /// them onto the nodes.
+ void renumber() {
+ std::stack<std::pair<Node *, Node::iterator> > S;
+ unsigned n = 0;
+
+ Entry->DFSin = ++n;
+ S.push(std::make_pair(Entry, Entry->begin()));
+
+ while (!S.empty()) {
+ std::pair<Node *, Node::iterator> &Pair = S.top();
+ Node *N = Pair.first;
+ Node::iterator &I = Pair.second;
+
+ if (I == N->end()) {
+ N->DFSout = ++n;
+ S.pop();
+ } else {
+ Node *Next = *I++;
+ Next->DFSin = ++n;
+ S.push(std::make_pair(Next, Next->begin()));
+ }
+ }
+ }
+
+#ifndef NDEBUG
+ virtual void dump() const {
+ dump(*cerr.stream());
+ }
+
+ void dump(std::ostream &os) const {
+ os << "Predicate simplifier DomTreeDFS: \n";
+ dump(Entry, 0, os);
+ os << "\n\n";
+ }
+
+ void dump(Node *N, int depth, std::ostream &os) const {
+ ++depth;
+ for (int i = 0; i < depth; ++i) { os << " "; }
+ os << "[" << depth << "] ";
+
+ os << N->getBlock()->getName() << " (" << N->getDFSNumIn()
+ << ", " << N->getDFSNumOut() << ")\n";
+
+ for (Node::iterator I = N->begin(), E = N->end(); I != E; ++I)
+ dump(*I, depth, os);
+ }
+#endif
+
+ Node *Entry;
+ std::map<BasicBlock *, Node *> NodeMap;
+ };
+
+ // SLT SGT ULT UGT EQ
+ // 0 1 0 1 0 -- GT 10
+ // 0 1 0 1 1 -- GE 11
+ // 0 1 1 0 0 -- SGTULT 12
+ // 0 1 1 0 1 -- SGEULE 13
+ // 0 1 1 1 0 -- SGT 14
+ // 0 1 1 1 1 -- SGE 15
+ // 1 0 0 1 0 -- SLTUGT 18
+ // 1 0 0 1 1 -- SLEUGE 19
+ // 1 0 1 0 0 -- LT 20
+ // 1 0 1 0 1 -- LE 21
+ // 1 0 1 1 0 -- SLT 22
+ // 1 0 1 1 1 -- SLE 23
+ // 1 1 0 1 0 -- UGT 26
+ // 1 1 0 1 1 -- UGE 27
+ // 1 1 1 0 0 -- ULT 28
+ // 1 1 1 0 1 -- ULE 29
+ // 1 1 1 1 0 -- NE 30
+ enum LatticeBits {
+ EQ_BIT = 1, UGT_BIT = 2, ULT_BIT = 4, SGT_BIT = 8, SLT_BIT = 16
+ };
+ enum LatticeVal {
+ GT = SGT_BIT | UGT_BIT,
+ GE = GT | EQ_BIT,
+ LT = SLT_BIT | ULT_BIT,
+ LE = LT | EQ_BIT,
+ NE = SLT_BIT | SGT_BIT | ULT_BIT | UGT_BIT,
+ SGTULT = SGT_BIT | ULT_BIT,
+ SGEULE = SGTULT | EQ_BIT,
+ SLTUGT = SLT_BIT | UGT_BIT,
+ SLEUGE = SLTUGT | EQ_BIT,
+ ULT = SLT_BIT | SGT_BIT | ULT_BIT,
+ UGT = SLT_BIT | SGT_BIT | UGT_BIT,
+ SLT = SLT_BIT | ULT_BIT | UGT_BIT,
+ SGT = SGT_BIT | ULT_BIT | UGT_BIT,
+ SLE = SLT | EQ_BIT,
+ SGE = SGT | EQ_BIT,
+ ULE = ULT | EQ_BIT,
+ UGE = UGT | EQ_BIT
+ };
+
+#ifndef NDEBUG
+ /// validPredicate - determines whether a given value is actually a lattice
+ /// value. Only used in assertions or debugging.
+ static bool validPredicate(LatticeVal LV) {
+ switch (LV) {
+ case GT: case GE: case LT: case LE: case NE:
+ case SGTULT: case SGT: case SGEULE:
+ case SLTUGT: case SLT: case SLEUGE:
+ case ULT: case UGT:
+ case SLE: case SGE: case ULE: case UGE:
+ return true;
+ default:
+ return false;
+ }
+ }
+#endif
+
+ /// reversePredicate - reverse the direction of the inequality
+ static LatticeVal reversePredicate(LatticeVal LV) {
+ unsigned reverse = LV ^ (SLT_BIT|SGT_BIT|ULT_BIT|UGT_BIT); //preserve EQ_BIT
+
+ if ((reverse & (SLT_BIT|SGT_BIT)) == 0)
+ reverse |= (SLT_BIT|SGT_BIT);
+
+ if ((reverse & (ULT_BIT|UGT_BIT)) == 0)
+ reverse |= (ULT_BIT|UGT_BIT);
+
+ LatticeVal Rev = static_cast<LatticeVal>(reverse);
+ assert(validPredicate(Rev) && "Failed reversing predicate.");
+ return Rev;
+ }
+
+ /// ValueNumbering stores the scope-specific value numbers for a given Value.
+ class VISIBILITY_HIDDEN ValueNumbering {
+
+ /// VNPair is a tuple of {Value, index number, DomTreeDFS::Node}. It
+ /// includes the comparison operators necessary to allow you to store it
+ /// in a sorted vector.
+ class VISIBILITY_HIDDEN VNPair {
+ public:
+ Value *V;
+ unsigned index;
+ DomTreeDFS::Node *Subtree;
+
+ VNPair(Value *V, unsigned index, DomTreeDFS::Node *Subtree)
+ : V(V), index(index), Subtree(Subtree) {}
+
+ bool operator==(const VNPair &RHS) const {
+ return V == RHS.V && Subtree == RHS.Subtree;
+ }
+
+ bool operator<(const VNPair &RHS) const {
+ if (V != RHS.V) return V < RHS.V;
+ return *Subtree < *RHS.Subtree;
+ }
+
+ bool operator<(Value *RHS) const {
+ return V < RHS;
+ }
+
+ bool operator>(Value *RHS) const {
+ return V > RHS;
+ }
+
+ friend bool operator<(Value *RHS, const VNPair &pair) {
+ return pair.operator>(RHS);
+ }
+ };
+
+ typedef std::vector<VNPair> VNMapType;
+ VNMapType VNMap;
+
+ /// The canonical choice for value number at index.
+ std::vector<Value *> Values;
+
+ DomTreeDFS *DTDFS;
+
+ public:
+#ifndef NDEBUG
+ virtual ~ValueNumbering() {}
+ virtual void dump() {
+ dump(*cerr.stream());
+ }
+
+ void dump(std::ostream &os) {
+ for (unsigned i = 1; i <= Values.size(); ++i) {
+ os << i << " = ";
+ WriteAsOperand(os, Values[i-1]);
+ os << " {";
+ for (unsigned j = 0; j < VNMap.size(); ++j) {
+ if (VNMap[j].index == i) {
+ WriteAsOperand(os, VNMap[j].V);
+ os << " (" << VNMap[j].Subtree->getDFSNumIn() << ") ";
+ }
+ }
+ os << "}\n";
+ }
+ }
+#endif
+
+ /// compare - returns true if V1 is a better canonical value than V2.
+ bool compare(Value *V1, Value *V2) const {
+ if (isa<Constant>(V1))
+ return !isa<Constant>(V2);
+ else if (isa<Constant>(V2))
+ return false;
+ else if (isa<Argument>(V1))
+ return !isa<Argument>(V2);
+ else if (isa<Argument>(V2))
+ return false;
+
+ Instruction *I1 = dyn_cast<Instruction>(V1);
+ Instruction *I2 = dyn_cast<Instruction>(V2);
+
+ if (!I1 || !I2)
+ return V1->getNumUses() < V2->getNumUses();
+
+ return DTDFS->dominates(I1, I2);
+ }
+
+ ValueNumbering(DomTreeDFS *DTDFS) : DTDFS(DTDFS) {}
+
+ /// valueNumber - finds the value number for V under the Subtree. If
+ /// there is no value number, returns zero.
+ unsigned valueNumber(Value *V, DomTreeDFS::Node *Subtree) {
+ if (!(isa<Constant>(V) || isa<Argument>(V) || isa<Instruction>(V))
+ || V->getType() == Type::VoidTy) return 0;
+
+ VNMapType::iterator E = VNMap.end();
+ VNPair pair(V, 0, Subtree);
+ VNMapType::iterator I = std::lower_bound(VNMap.begin(), E, pair);
+ while (I != E && I->V == V) {
+ if (I->Subtree->dominates(Subtree))
+ return I->index;
+ ++I;
+ }
+ return 0;
+ }
+
+ /// getOrInsertVN - always returns a value number, creating it if necessary.
+ unsigned getOrInsertVN(Value *V, DomTreeDFS::Node *Subtree) {
+ if (unsigned n = valueNumber(V, Subtree))
+ return n;
+ else
+ return newVN(V);
+ }
+
+ /// newVN - creates a new value number. Value V must not already have a
+ /// value number assigned.
+ unsigned newVN(Value *V) {
+ assert((isa<Constant>(V) || isa<Argument>(V) || isa<Instruction>(V)) &&
+ "Bad Value for value numbering.");
+ assert(V->getType() != Type::VoidTy && "Won't value number a void value");
+
+ Values.push_back(V);
+
+ VNPair pair = VNPair(V, Values.size(), DTDFS->getRootNode());
+ VNMapType::iterator I = std::lower_bound(VNMap.begin(), VNMap.end(), pair);
+ assert((I == VNMap.end() || value(I->index) != V) &&
+ "Attempt to create a duplicate value number.");
+ VNMap.insert(I, pair);
+
+ return Values.size();
+ }
+
+ /// value - returns the Value associated with a value number.
+ Value *value(unsigned index) const {
+ assert(index != 0 && "Zero index is reserved for not found.");
+ assert(index <= Values.size() && "Index out of range.");
+ return Values[index-1];
+ }
+
+ /// canonicalize - return a Value that is equal to V under Subtree.
+ Value *canonicalize(Value *V, DomTreeDFS::Node *Subtree) {
+ if (isa<Constant>(V)) return V;
+
+ if (unsigned n = valueNumber(V, Subtree))
+ return value(n);
+ else
+ return V;
+ }
+
+ /// addEquality - adds that value V belongs to the set of equivalent
+ /// values defined by value number n under Subtree.
+ void addEquality(unsigned n, Value *V, DomTreeDFS::Node *Subtree) {
+ assert(canonicalize(value(n), Subtree) == value(n) &&
+ "Node's 'canonical' choice isn't best within this subtree.");
+
+ // Suppose that we are given "%x -> node #1 (%y)". The problem is that
+ // we may already have "%z -> node #2 (%x)" somewhere above us in the
+ // graph. We need to find those edges and add "%z -> node #1 (%y)"
+ // to keep the lookups canonical.
+
+ std::vector<Value *> ToRepoint(1, V);
+
+ if (unsigned Conflict = valueNumber(V, Subtree)) {
+ for (VNMapType::iterator I = VNMap.begin(), E = VNMap.end();
+ I != E; ++I) {
+ if (I->index == Conflict && I->Subtree->dominates(Subtree))
+ ToRepoint.push_back(I->V);
+ }
+ }
+
+ for (std::vector<Value *>::iterator VI = ToRepoint.begin(),
+ VE = ToRepoint.end(); VI != VE; ++VI) {
+ Value *V = *VI;
+
+ VNPair pair(V, n, Subtree);
+ VNMapType::iterator B = VNMap.begin(), E = VNMap.end();
+ VNMapType::iterator I = std::lower_bound(B, E, pair);
+ if (I != E && I->V == V && I->Subtree == Subtree)
+ I->index = n; // Update best choice
+ else
+ VNMap.insert(I, pair); // New Value
+
+ // XXX: we currently don't have to worry about updating values with
+ // more specific Subtrees, but we will need to for PHI node support.
+
+#ifndef NDEBUG
+ Value *V_n = value(n);
+ if (isa<Constant>(V) && isa<Constant>(V_n)) {
+ assert(V == V_n && "Constant equals different constant?");
+ }
+#endif
+ }
+ }
+
+ /// remove - removes all references to value V.
+ void remove(Value *V) {
+ VNMapType::iterator B = VNMap.begin(), E = VNMap.end();
+ VNPair pair(V, 0, DTDFS->getRootNode());
+ VNMapType::iterator J = std::upper_bound(B, E, pair);
+ VNMapType::iterator I = J;
+
+ while (I != B && (I == E || I->V == V)) --I;
+
+ VNMap.erase(I, J);
+ }
+ };
+