1 //===-- PredicateSimplifier.cpp - Path Sensitive Simplifier ---------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by Nick Lewycky and is distributed under the
6 // University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Path-sensitive optimizer. In a branch where x == y, replace uses of
11 // x with y. Permits further optimization, such as the elimination of
12 // the unreachable call:
14 // void test(int *p, int *q)
20 // foo(); // unreachable
23 //===----------------------------------------------------------------------===//
25 // This pass focusses on four properties; equals, not equals, less-than
26 // and less-than-or-equals-to. The greater-than forms are also held just
27 // to allow walking from a lesser node to a greater one. These properties
28 // are stored in a lattice; LE can become LT or EQ, NE can become LT or GT.
30 // These relationships define a graph between values of the same type. Each
31 // Value is stored in a map table that retrieves the associated Node. This
32 // is how EQ relationships are stored; the map contains pointers to the
33 // same node. The node contains a most canonical Value* form and the list of
34 // known relationships.
36 // If two nodes are known to be inequal, then they will contain pointers to
37 // each other with an "NE" relationship. If node getNode(%x) is less than
38 // getNode(%y), then the %x node will contain <%y, GT> and %y will contain
39 // <%x, LT>. This allows us to tie nodes together into a graph like this:
43 // with four nodes representing the properties. The InequalityGraph provides
44 // querying with "isRelatedBy" and mutators "addEquality" and "addInequality".
45 // To find a relationship, we start with one of the nodes any binary search
46 // through its list to find where the relationships with the second node start.
47 // Then we iterate through those to find the first relationship that dominates
50 // To create these properties, we wait until a branch or switch instruction
51 // implies that a particular value is true (or false). The VRPSolver is
52 // responsible for analyzing the variable and seeing what new inferences
53 // can be made from each property. For example:
55 // %P = seteq int* %ptr, null
56 // %a = or bool %P, %Q
57 // br bool %a label %cond_true, label %cond_false
59 // For the true branch, the VRPSolver will start with %a EQ true and look at
60 // the definition of %a and find that it can infer that %P and %Q are both
61 // true. From %P being true, it can infer that %ptr NE null. For the false
62 // branch it can't infer anything from the "or" instruction.
64 // Besides branches, we can also infer properties from instruction that may
65 // have undefined behaviour in certain cases. For example, the dividend of
66 // a division may never be zero. After the division instruction, we may assume
67 // that the dividend is not equal to zero.
69 //===----------------------------------------------------------------------===//
71 #define DEBUG_TYPE "predsimplify"
72 #include "llvm/Transforms/Scalar.h"
73 #include "llvm/Constants.h"
74 #include "llvm/DerivedTypes.h"
75 #include "llvm/Instructions.h"
76 #include "llvm/Pass.h"
77 #include "llvm/ADT/DepthFirstIterator.h"
78 #include "llvm/ADT/SetOperations.h"
79 #include "llvm/ADT/SmallVector.h"
80 #include "llvm/ADT/Statistic.h"
81 #include "llvm/ADT/STLExtras.h"
82 #include "llvm/Analysis/Dominators.h"
83 #include "llvm/Analysis/ET-Forest.h"
84 #include "llvm/Support/CFG.h"
85 #include "llvm/Support/Compiler.h"
86 #include "llvm/Support/Debug.h"
87 #include "llvm/Support/InstVisitor.h"
88 #include "llvm/Transforms/Utils/Local.h"
94 STATISTIC(NumVarsReplaced, "Number of argument substitutions");
95 STATISTIC(NumInstruction , "Number of instructions removed");
96 STATISTIC(NumSimple , "Number of simple replacements");
97 STATISTIC(NumBlocks , "Number of blocks marked unreachable");
100 // SLT SGT ULT UGT EQ
101 // 0 1 0 1 0 -- GT 10
102 // 0 1 0 1 1 -- GE 11
103 // 0 1 1 0 0 -- SGTULT 12
104 // 0 1 1 0 1 -- SGEULE 13
105 // 0 1 1 1 0 -- SGTUNE 14
106 // 0 1 1 1 1 -- SGEUANY 15
107 // 1 0 0 1 0 -- SLTUGT 18
108 // 1 0 0 1 1 -- SLEUGE 19
109 // 1 0 1 0 0 -- LT 20
110 // 1 0 1 0 1 -- LE 21
111 // 1 0 1 1 0 -- SLTUNE 22
112 // 1 0 1 1 1 -- SLEUANY 23
113 // 1 1 0 1 0 -- SNEUGT 26
114 // 1 1 0 1 1 -- SANYUGE 27
115 // 1 1 1 0 0 -- SNEULT 28
116 // 1 1 1 0 1 -- SANYULE 29
117 // 1 1 1 1 0 -- NE 30
119 EQ_BIT = 1, UGT_BIT = 2, ULT_BIT = 4, SGT_BIT = 8, SLT_BIT = 16
122 GT = SGT_BIT | UGT_BIT,
124 LT = SLT_BIT | ULT_BIT,
126 NE = SLT_BIT | SGT_BIT | ULT_BIT | UGT_BIT,
127 SGTULT = SGT_BIT | ULT_BIT,
128 SGEULE = SGTULT | EQ_BIT,
129 SLTUGT = SLT_BIT | UGT_BIT,
130 SLEUGE = SLTUGT | EQ_BIT,
131 SNEULT = SLT_BIT | SGT_BIT | ULT_BIT,
132 SNEUGT = SLT_BIT | SGT_BIT | UGT_BIT,
133 SLTUNE = SLT_BIT | ULT_BIT | UGT_BIT,
134 SGTUNE = SGT_BIT | ULT_BIT | UGT_BIT,
135 SLEUANY = SLT_BIT | ULT_BIT | UGT_BIT | EQ_BIT,
136 SGEUANY = SGT_BIT | ULT_BIT | UGT_BIT | EQ_BIT,
137 SANYULE = SLT_BIT | SGT_BIT | ULT_BIT | EQ_BIT,
138 SANYUGE = SLT_BIT | SGT_BIT | UGT_BIT | EQ_BIT
141 static bool validPredicate(LatticeVal LV) {
143 case GT: case GE: case LT: case LE: case NE:
144 case SGTULT: case SGTUNE: case SGEULE:
145 case SLTUGT: case SLTUNE: case SLEUGE:
146 case SNEULT: case SNEUGT:
147 case SLEUANY: case SGEUANY: case SANYULE: case SANYUGE:
154 /// reversePredicate - reverse the direction of the inequality
155 static LatticeVal reversePredicate(LatticeVal LV) {
156 unsigned reverse = LV ^ (SLT_BIT|SGT_BIT|ULT_BIT|UGT_BIT); //preserve EQ_BIT
157 if ((reverse & (SLT_BIT|SGT_BIT)) == 0)
158 reverse |= (SLT_BIT|SGT_BIT);
160 if ((reverse & (ULT_BIT|UGT_BIT)) == 0)
161 reverse |= (ULT_BIT|UGT_BIT);
163 LatticeVal Rev = static_cast<LatticeVal>(reverse);
164 assert(validPredicate(Rev) && "Failed reversing predicate.");
168 /// The InequalityGraph stores the relationships between values.
169 /// Each Value in the graph is assigned to a Node. Nodes are pointer
170 /// comparable for equality. The caller is expected to maintain the logical
171 /// consistency of the system.
173 /// The InequalityGraph class may invalidate Node*s after any mutator call.
174 /// @brief The InequalityGraph stores the relationships between values.
175 class VISIBILITY_HIDDEN InequalityGraph {
178 InequalityGraph(); // DO NOT IMPLEMENT
179 InequalityGraph(InequalityGraph &); // DO NOT IMPLEMENT
181 explicit InequalityGraph(ETNode *TreeRoot) : TreeRoot(TreeRoot) {}
185 /// This is a StrictWeakOrdering predicate that sorts ETNodes by how many
186 /// children they have. With this, you can iterate through a list sorted by
187 /// this operation and the first matching entry is the most specific match
188 /// for your basic block. The order provided is total; ETNodes with the
189 /// same number of children are sorted by pointer address.
190 struct VISIBILITY_HIDDEN OrderByDominance {
191 bool operator()(const ETNode *LHS, const ETNode *RHS) const {
192 unsigned LHS_spread = LHS->getDFSNumOut() - LHS->getDFSNumIn();
193 unsigned RHS_spread = RHS->getDFSNumOut() - RHS->getDFSNumIn();
194 if (LHS_spread != RHS_spread) return LHS_spread < RHS_spread;
195 else return LHS < RHS;
199 /// An Edge is contained inside a Node making one end of the edge implicit
200 /// and contains a pointer to the other end. The edge contains a lattice
201 /// value specifying the relationship between the two nodes. Further, there
202 /// is an ETNode specifying which subtree of the dominator the edge applies.
203 class VISIBILITY_HIDDEN Edge {
205 Edge(unsigned T, LatticeVal V, ETNode *ST)
206 : To(T), LV(V), Subtree(ST) {}
212 bool operator<(const Edge &edge) const {
213 if (To != edge.To) return To < edge.To;
214 else return OrderByDominance()(Subtree, edge.Subtree);
216 bool operator<(unsigned to) const {
221 /// A single node in the InequalityGraph. This stores the canonical Value
222 /// for the node, as well as the relationships with the neighbours.
224 /// Because the lists are intended to be used for traversal, it is invalid
225 /// for the node to list itself in LessEqual or GreaterEqual lists. The
226 /// fact that a node is equal to itself is implied, and may be checked
227 /// with pointer comparison.
228 /// @brief A single node in the InequalityGraph.
229 class VISIBILITY_HIDDEN Node {
230 friend class InequalityGraph;
232 typedef SmallVector<Edge, 4> RelationsType;
233 RelationsType Relations;
237 // TODO: can this idea improve performance?
238 //friend class std::vector<Node>;
239 //Node(Node &N) { RelationsType.swap(N.RelationsType); }
242 typedef RelationsType::iterator iterator;
243 typedef RelationsType::const_iterator const_iterator;
245 Node(Value *V) : Canonical(V) {}
250 virtual void dump() const {
251 dump(*cerr.stream());
254 void dump(std::ostream &os) const {
255 os << *getValue() << ":\n";
256 for (Node::const_iterator NI = begin(), NE = end(); NI != NE; ++NI) {
257 static const std::string names[32] =
258 { "000000", "000001", "000002", "000003", "000004", "000005",
259 "000006", "000007", "000008", "000009", " >", " >=",
260 " s>u<", "s>=u<=", " s>", " s>=", "000016", "000017",
261 " s<u>", "s<=u>=", " <", " <=", " s<", " s<=",
262 "000024", "000025", " u>", " u>=", " u<", " u<=",
264 os << " " << names[NI->LV] << " " << NI->To
265 << "(" << NI->Subtree << ")\n";
271 iterator begin() { return Relations.begin(); }
272 iterator end() { return Relations.end(); }
273 const_iterator begin() const { return Relations.begin(); }
274 const_iterator end() const { return Relations.end(); }
276 iterator find(unsigned n, ETNode *Subtree) {
278 for (iterator I = std::lower_bound(begin(), E, n);
279 I != E && I->To == n; ++I) {
280 if (Subtree->DominatedBy(I->Subtree))
286 const_iterator find(unsigned n, ETNode *Subtree) const {
287 const_iterator E = end();
288 for (const_iterator I = std::lower_bound(begin(), E, n);
289 I != E && I->To == n; ++I) {
290 if (Subtree->DominatedBy(I->Subtree))
296 Value *getValue() const
301 /// Updates the lattice value for a given node. Create a new entry if
302 /// one doesn't exist, otherwise it merges the values. The new lattice
303 /// value must not be inconsistent with any previously existing value.
304 void update(unsigned n, LatticeVal R, ETNode *Subtree) {
305 assert(validPredicate(R) && "Invalid predicate.");
306 iterator I = find(n, Subtree);
308 Edge edge(n, R, Subtree);
309 iterator Insert = std::lower_bound(begin(), end(), edge);
310 Relations.insert(Insert, edge);
312 LatticeVal LV = static_cast<LatticeVal>(I->LV & R);
313 assert(validPredicate(LV) && "Invalid union of lattice values.");
315 if (Subtree == I->Subtree)
318 assert(Subtree->DominatedBy(I->Subtree) &&
319 "Find returned subtree that doesn't apply.");
321 Edge edge(n, R, Subtree);
322 iterator Insert = std::lower_bound(begin(), end(), edge);
323 Relations.insert(Insert, edge);
331 struct VISIBILITY_HIDDEN NodeMapEdge {
336 NodeMapEdge(Value *V, unsigned index, ETNode *Subtree)
337 : V(V), index(index), Subtree(Subtree) {}
339 bool operator==(const NodeMapEdge &RHS) const {
341 Subtree == RHS.Subtree;
344 bool operator<(const NodeMapEdge &RHS) const {
345 if (V != RHS.V) return V < RHS.V;
346 return OrderByDominance()(Subtree, RHS.Subtree);
349 bool operator<(Value *RHS) const {
354 typedef std::vector<NodeMapEdge> NodeMapType;
357 std::vector<Node> Nodes;
359 std::vector<std::pair<ConstantIntegral *, unsigned> > Constants;
360 void initializeConstant(Constant *C, unsigned index) {
361 ConstantIntegral *CI = dyn_cast<ConstantIntegral>(C);
364 // XXX: instead of O(n) calls to addInequality, just find the 2, 3 or 4
365 // nodes that are nearest less than or greater than (signed or unsigned).
366 for (std::vector<std::pair<ConstantIntegral *, unsigned> >::iterator
367 I = Constants.begin(), E = Constants.end(); I != E; ++I) {
368 ConstantIntegral *Other = I->first;
369 if (CI->getType() == Other->getType()) {
372 if (CI->getZExtValue() < Other->getZExtValue())
377 if (CI->getSExtValue() < Other->getSExtValue())
382 LatticeVal LV = static_cast<LatticeVal>(lv);
383 assert(validPredicate(LV) && "Not a valid predicate.");
384 if (!isRelatedBy(index, I->second, TreeRoot, LV))
385 addInequality(index, I->second, TreeRoot, LV);
388 Constants.push_back(std::make_pair(CI, index));
392 /// node - returns the node object at a given index retrieved from getNode.
393 /// Index zero is reserved and may not be passed in here. The pointer
394 /// returned is valid until the next call to newNode or getOrInsertNode.
395 Node *node(unsigned index) {
396 assert(index != 0 && "Zero index is reserved for not found.");
397 assert(index <= Nodes.size() && "Index out of range.");
398 return &Nodes[index-1];
401 /// Returns the node currently representing Value V, or zero if no such
403 unsigned getNode(Value *V, ETNode *Subtree) {
404 NodeMapType::iterator E = NodeMap.end();
405 NodeMapEdge Edge(V, 0, Subtree);
406 NodeMapType::iterator I = std::lower_bound(NodeMap.begin(), E, Edge);
407 while (I != E && I->V == V) {
408 if (Subtree->DominatedBy(I->Subtree))
415 /// getOrInsertNode - always returns a valid node index, creating a node
416 /// to match the Value if needed.
417 unsigned getOrInsertNode(Value *V, ETNode *Subtree) {
418 if (unsigned n = getNode(V, Subtree))
424 /// newNode - creates a new node for a given Value and returns the index.
425 unsigned newNode(Value *V) {
426 Nodes.push_back(Node(V));
428 NodeMapEdge MapEntry = NodeMapEdge(V, Nodes.size(), TreeRoot);
429 assert(!std::binary_search(NodeMap.begin(), NodeMap.end(), MapEntry) &&
430 "Attempt to create a duplicate Node.");
431 NodeMap.insert(std::lower_bound(NodeMap.begin(), NodeMap.end(),
432 MapEntry), MapEntry);
435 // This is the missing piece to turn on VRP.
436 if (Constant *C = dyn_cast<Constant>(V))
437 initializeConstant(C, MapEntry.index);
440 return MapEntry.index;
443 /// If the Value is in the graph, return the canonical form. Otherwise,
444 /// return the original Value.
445 Value *canonicalize(Value *V, ETNode *Subtree) {
446 if (isa<Constant>(V)) return V;
448 if (unsigned n = getNode(V, Subtree))
449 return node(n)->getValue();
454 /// isRelatedBy - true iff n1 op n2
455 bool isRelatedBy(unsigned n1, unsigned n2, ETNode *Subtree, LatticeVal LV) {
456 if (n1 == n2) return LV & EQ_BIT;
459 Node::iterator I = N1->find(n2, Subtree), E = N1->end();
460 if (I != E) return (I->LV & LV) == I->LV;
465 // The add* methods assume that your input is logically valid and may
466 // assertion-fail or infinitely loop if you attempt a contradiction.
468 void addEquality(unsigned n, Value *V, ETNode *Subtree) {
469 assert(canonicalize(node(n)->getValue(), Subtree) == node(n)->getValue()
470 && "Node's 'canonical' choice isn't best within this subtree.");
472 // Suppose that we are given "%x -> node #1 (%y)". The problem is that
473 // we may already have "%z -> node #2 (%x)" somewhere above us in the
474 // graph. We need to find those edges and add "%z -> node #1 (%y)"
475 // to keep the lookups canonical.
477 std::vector<Value *> ToRepoint;
478 ToRepoint.push_back(V);
480 if (unsigned Conflict = getNode(V, Subtree)) {
481 // XXX: NodeMap.size() exceeds 68000 entries compiling kimwitu++!
482 // This adds 57 seconds to the otherwise 3 second build. Unacceptable.
484 // IDEA: could we iterate 1..Nodes.size() calling getNode? It's
485 // O(n log n) but kimwitu++ only has about 300 nodes.
486 for (NodeMapType::iterator I = NodeMap.begin(), E = NodeMap.end();
488 if (I->index == Conflict && Subtree->DominatedBy(I->Subtree))
489 ToRepoint.push_back(I->V);
493 for (std::vector<Value *>::iterator VI = ToRepoint.begin(),
494 VE = ToRepoint.end(); VI != VE; ++VI) {
497 // XXX: review this code. This may be doing too many insertions.
498 NodeMapEdge Edge(V, n, Subtree);
499 NodeMapType::iterator E = NodeMap.end();
500 NodeMapType::iterator I = std::lower_bound(NodeMap.begin(), E, Edge);
501 if (I == E || I->V != V || I->Subtree != Subtree) {
503 NodeMap.insert(I, Edge);
504 } else if (I != E && I->V == V && I->Subtree == Subtree) {
505 // Update best choice
511 if (isa<Constant>(V)) {
512 if (isa<Constant>(N->getValue())) {
513 assert(V == N->getValue() && "Constant equals different constant?");
520 /// addInequality - Sets n1 op n2.
521 /// It is also an error to call this on an inequality that is already true.
522 void addInequality(unsigned n1, unsigned n2, ETNode *Subtree,
524 assert(n1 != n2 && "A node can't be inequal to itself.");
527 assert(!isRelatedBy(n1, n2, Subtree, reversePredicate(LV1)) &&
528 "Contradictory inequality.");
533 // Suppose we're adding %n1 < %n2. Find all the %a < %n1 and
534 // add %a < %n2 too. This keeps the graph fully connected.
536 // Someone with a head for this sort of logic, please review this.
537 // Given that %x SLTUGT %y and %a SLEUANY %x, what is the relationship
538 // between %a and %y? I believe the below code is correct, but I don't
539 // think it's the most efficient solution.
541 unsigned LV1_s = LV1 & (SLT_BIT|SGT_BIT);
542 unsigned LV1_u = LV1 & (ULT_BIT|UGT_BIT);
543 for (Node::iterator I = N1->begin(), E = N1->end(); I != E; ++I) {
544 if (I->LV != NE && I->To != n2) {
545 ETNode *Local_Subtree = NULL;
546 if (Subtree->DominatedBy(I->Subtree))
547 Local_Subtree = Subtree;
548 else if (I->Subtree->DominatedBy(Subtree))
549 Local_Subtree = I->Subtree;
552 unsigned new_relationship = 0;
553 LatticeVal ILV = reversePredicate(I->LV);
554 unsigned ILV_s = ILV & (SLT_BIT|SGT_BIT);
555 unsigned ILV_u = ILV & (ULT_BIT|UGT_BIT);
557 if (LV1_s != (SLT_BIT|SGT_BIT) && ILV_s == LV1_s)
558 new_relationship |= ILV_s;
560 if (LV1_u != (ULT_BIT|UGT_BIT) && ILV_u == LV1_u)
561 new_relationship |= ILV_u;
563 if (new_relationship) {
564 if ((new_relationship & (SLT_BIT|SGT_BIT)) == 0)
565 new_relationship |= (SLT_BIT|SGT_BIT);
566 if ((new_relationship & (ULT_BIT|UGT_BIT)) == 0)
567 new_relationship |= (ULT_BIT|UGT_BIT);
568 if ((LV1 & EQ_BIT) && (ILV & EQ_BIT))
569 new_relationship |= EQ_BIT;
571 LatticeVal NewLV = static_cast<LatticeVal>(new_relationship);
573 node(I->To)->update(n2, NewLV, Local_Subtree);
574 N2->update(I->To, reversePredicate(NewLV), Local_Subtree);
580 for (Node::iterator I = N2->begin(), E = N2->end(); I != E; ++I) {
581 if (I->LV != NE && I->To != n1) {
582 ETNode *Local_Subtree = NULL;
583 if (Subtree->DominatedBy(I->Subtree))
584 Local_Subtree = Subtree;
585 else if (I->Subtree->DominatedBy(Subtree))
586 Local_Subtree = I->Subtree;
589 unsigned new_relationship = 0;
590 unsigned ILV_s = I->LV & (SLT_BIT|SGT_BIT);
591 unsigned ILV_u = I->LV & (ULT_BIT|UGT_BIT);
593 if (LV1_s != (SLT_BIT|SGT_BIT) && ILV_s == LV1_s)
594 new_relationship |= ILV_s;
596 if (LV1_u != (ULT_BIT|UGT_BIT) && ILV_u == LV1_u)
597 new_relationship |= ILV_u;
599 if (new_relationship) {
600 if ((new_relationship & (SLT_BIT|SGT_BIT)) == 0)
601 new_relationship |= (SLT_BIT|SGT_BIT);
602 if ((new_relationship & (ULT_BIT|UGT_BIT)) == 0)
603 new_relationship |= (ULT_BIT|UGT_BIT);
604 if ((LV1 & EQ_BIT) && (I->LV & EQ_BIT))
605 new_relationship |= EQ_BIT;
607 LatticeVal NewLV = static_cast<LatticeVal>(new_relationship);
609 N1->update(I->To, NewLV, Local_Subtree);
610 node(I->To)->update(n1, reversePredicate(NewLV), Local_Subtree);
617 N1->update(n2, LV1, Subtree);
618 N2->update(n1, reversePredicate(LV1), Subtree);
621 /// Removes a Value from the graph, but does not delete any nodes. As this
622 /// method does not delete Nodes, V may not be the canonical choice for
623 /// a node with any relationships. It is invalid to call newNode on a Value
624 /// that has been removed.
625 void remove(Value *V) {
626 for (unsigned i = 0; i < NodeMap.size();) {
627 NodeMapType::iterator I = NodeMap.begin()+i;
628 assert((node(I->index)->getValue() != V || node(I->index)->begin() ==
629 node(I->index)->end()) && "Tried to delete in-use node.");
632 if (node(I->index)->getValue() == V)
633 node(I->index)->Canonical = NULL;
641 virtual void dump() {
642 dump(*cerr.stream());
645 void dump(std::ostream &os) {
646 std::set<Node *> VisitedNodes;
647 for (NodeMapType::const_iterator I = NodeMap.begin(), E = NodeMap.end();
649 Node *N = node(I->index);
650 os << *I->V << " == " << I->index << "(" << I->Subtree << ")\n";
651 if (VisitedNodes.insert(N).second) {
652 os << I->index << ". ";
653 if (!N->getValue()) os << "(deleted node)\n";
661 /// UnreachableBlocks keeps tracks of blocks that are for one reason or
662 /// another discovered to be unreachable. This is used to cull the graph when
663 /// analyzing instructions, and to mark blocks with the "unreachable"
664 /// terminator instruction after the function has executed.
665 class VISIBILITY_HIDDEN UnreachableBlocks {
667 std::vector<BasicBlock *> DeadBlocks;
670 /// mark - mark a block as dead
671 void mark(BasicBlock *BB) {
672 std::vector<BasicBlock *>::iterator E = DeadBlocks.end();
673 std::vector<BasicBlock *>::iterator I =
674 std::lower_bound(DeadBlocks.begin(), E, BB);
676 if (I == E || *I != BB) DeadBlocks.insert(I, BB);
679 /// isDead - returns whether a block is known to be dead already
680 bool isDead(BasicBlock *BB) {
681 std::vector<BasicBlock *>::iterator E = DeadBlocks.end();
682 std::vector<BasicBlock *>::iterator I =
683 std::lower_bound(DeadBlocks.begin(), E, BB);
685 return I != E && *I == BB;
688 /// kill - replace the dead blocks' terminator with an UnreachableInst.
690 bool modified = false;
691 for (std::vector<BasicBlock *>::iterator I = DeadBlocks.begin(),
692 E = DeadBlocks.end(); I != E; ++I) {
695 DOUT << "unreachable block: " << BB->getName() << "\n";
697 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB);
699 BasicBlock *Succ = *SI;
700 Succ->removePredecessor(BB);
703 TerminatorInst *TI = BB->getTerminator();
704 TI->replaceAllUsesWith(UndefValue::get(TI->getType()));
705 TI->eraseFromParent();
706 new UnreachableInst(BB);
715 /// VRPSolver keeps track of how changes to one variable affect other
716 /// variables, and forwards changes along to the InequalityGraph. It
717 /// also maintains the correct choice for "canonical" in the IG.
718 /// @brief VRPSolver calculates inferences from a new relationship.
719 class VISIBILITY_HIDDEN VRPSolver {
723 ICmpInst::Predicate Op;
725 Instruction *Context;
727 std::deque<Operation> WorkList;
730 UnreachableBlocks &UB;
734 Instruction *TopInst;
737 typedef InequalityGraph::Node Node;
739 /// IdomI - Determines whether one Instruction dominates another.
740 bool IdomI(Instruction *I1, Instruction *I2) const {
741 BasicBlock *BB1 = I1->getParent(),
742 *BB2 = I2->getParent();
744 if (isa<TerminatorInst>(I1)) return false;
745 if (isa<TerminatorInst>(I2)) return true;
746 if (isa<PHINode>(I1) && !isa<PHINode>(I2)) return true;
747 if (!isa<PHINode>(I1) && isa<PHINode>(I2)) return false;
749 for (BasicBlock::const_iterator I = BB1->begin(), E = BB1->end();
751 if (&*I == I1) return true;
752 if (&*I == I2) return false;
754 assert(!"Instructions not found in parent BasicBlock?");
756 return Forest->properlyDominates(BB1, BB2);
761 /// Returns true if V1 is a better canonical value than V2.
762 bool compare(Value *V1, Value *V2) const {
763 if (isa<Constant>(V1))
764 return !isa<Constant>(V2);
765 else if (isa<Constant>(V2))
767 else if (isa<Argument>(V1))
768 return !isa<Argument>(V2);
769 else if (isa<Argument>(V2))
772 Instruction *I1 = dyn_cast<Instruction>(V1);
773 Instruction *I2 = dyn_cast<Instruction>(V2);
776 return V1->getNumUses() < V2->getNumUses();
778 return IdomI(I1, I2);
781 // below - true if the Instruction is dominated by the current context
782 // block or instruction
783 bool below(Instruction *I) {
785 return IdomI(TopInst, I);
787 ETNode *Node = Forest->getNodeForBlock(I->getParent());
788 return Node == Top || Node->DominatedBy(Top);
792 bool makeEqual(Value *V1, Value *V2) {
793 DOUT << "makeEqual(" << *V1 << ", " << *V2 << ")\n";
795 if (V1 == V2) return true;
797 if (isa<Constant>(V1) && isa<Constant>(V2))
800 unsigned n1 = IG.getNode(V1, Top), n2 = IG.getNode(V2, Top);
803 if (n1 == n2) return true;
804 if (IG.isRelatedBy(n1, n2, Top, NE)) return false;
807 if (n1) assert(V1 == IG.node(n1)->getValue() && "Value isn't canonical.");
808 if (n2) assert(V2 == IG.node(n2)->getValue() && "Value isn't canonical.");
810 if (compare(V2, V1)) { std::swap(V1, V2); std::swap(n1, n2); }
812 assert(!isa<Constant>(V2) && "Tried to remove a constant.");
814 SetVector<unsigned> Remove;
815 if (n2) Remove.insert(n2);
818 // Suppose we're being told that %x == %y, and %x <= %z and %y >= %z.
819 // We can't just merge %x and %y because the relationship with %z would
820 // be EQ and that's invalid. What we're doing is looking for any nodes
821 // %z such that %x <= %z and %y >= %z, and vice versa.
823 // Also handle %a <= %b and %c <= %a when adding %b <= %c.
825 Node *N1 = IG.node(n1);
826 Node::iterator end = N1->end();
827 for (unsigned i = 0; i < Remove.size(); ++i) {
828 Node *N = IG.node(Remove[i]);
829 Value *V = N->getValue();
830 for (Node::iterator I = N->begin(), E = N->end(); I != E; ++I) {
831 if (I->LV & EQ_BIT) {
832 if (Top == I->Subtree || Top->DominatedBy(I->Subtree)) {
833 Node::iterator NI = N1->find(I->To, Top);
835 if (!(NI->LV & EQ_BIT)) return false;
836 if (isRelatedBy(V, IG.node(NI->To)->getValue(),
839 Remove.insert(NI->To);
846 // See if one of the nodes about to be removed is actually a better
847 // canonical choice than n1.
848 unsigned orig_n1 = n1;
849 std::vector<unsigned>::iterator DontRemove = Remove.end();
850 for (std::vector<unsigned>::iterator I = Remove.begin()+1 /* skip n2 */,
851 E = Remove.end(); I != E; ++I) {
853 Value *V = IG.node(n)->getValue();
854 if (compare(V, V1)) {
860 if (DontRemove != Remove.end()) {
861 unsigned n = *DontRemove;
863 Remove.insert(orig_n1);
867 // We'd like to allow makeEqual on two values to perform a simple
868 // substitution without every creating nodes in the IG whenever possible.
870 // The first iteration through this loop operates on V2 before going
871 // through the Remove list and operating on those too. If all of the
872 // iterations performed simple replacements then we exit early.
873 bool exitEarly = true;
875 for (Value *R = V2; i == 0 || i < Remove.size(); ++i) {
876 if (i) R = IG.node(Remove[i])->getValue(); // skip n2.
878 // Try to replace the whole instruction. If we can, we're done.
879 Instruction *I2 = dyn_cast<Instruction>(R);
880 if (I2 && below(I2)) {
881 std::vector<Instruction *> ToNotify;
882 for (Value::use_iterator UI = R->use_begin(), UE = R->use_end();
884 Use &TheUse = UI.getUse();
886 if (Instruction *I = dyn_cast<Instruction>(TheUse.getUser()))
887 ToNotify.push_back(I);
890 DOUT << "Simply removing " << *I2
891 << ", replacing with " << *V1 << "\n";
892 I2->replaceAllUsesWith(V1);
893 // leave it dead; it'll get erased later.
897 for (std::vector<Instruction *>::iterator II = ToNotify.begin(),
898 IE = ToNotify.end(); II != IE; ++II) {
905 // Otherwise, replace all dominated uses.
906 for (Value::use_iterator UI = R->use_begin(), UE = R->use_end();
908 Use &TheUse = UI.getUse();
910 if (Instruction *I = dyn_cast<Instruction>(TheUse.getUser())) {
920 // If that killed the instruction, stop here.
921 if (I2 && isInstructionTriviallyDead(I2)) {
922 DOUT << "Killed all uses of " << *I2
923 << ", replacing with " << *V1 << "\n";
927 // If we make it to here, then we will need to create a node for N1.
928 // Otherwise, we can skip out early!
932 if (exitEarly) return true;
935 // XXX: this should call newNode, but instead the node might be created
936 // in isRelatedBy. That's also a fixme.
937 if (!n1) n1 = IG.getOrInsertNode(V1, Top);
939 // Migrate relationships from removed nodes to N1.
940 Node *N1 = IG.node(n1);
941 for (std::vector<unsigned>::iterator I = Remove.begin(), E = Remove.end();
944 Node *N = IG.node(n);
945 for (Node::iterator NI = N->begin(), NE = N->end(); NI != NE; ++NI) {
946 if (Top == NI->Subtree || NI->Subtree->DominatedBy(Top)) {
948 assert((NI->LV & EQ_BIT) && "Node inequal to itself.");
951 if (Remove.count(NI->To))
954 IG.node(NI->To)->update(n1, reversePredicate(NI->LV), Top);
955 N1->update(NI->To, NI->LV, Top);
960 // Point V2 (and all items in Remove) to N1.
962 IG.addEquality(n1, V2, Top);
964 for (std::vector<unsigned>::iterator I = Remove.begin(),
965 E = Remove.end(); I != E; ++I) {
966 IG.addEquality(n1, IG.node(*I)->getValue(), Top);
970 // If !Remove.empty() then V2 = Remove[0]->getValue().
971 // Even when Remove is empty, we still want to process V2.
973 for (Value *R = V2; i == 0 || i < Remove.size(); ++i) {
974 if (i) R = IG.node(Remove[i])->getValue(); // skip n2.
976 if (Instruction *I2 = dyn_cast<Instruction>(R)) defToOps(I2);
977 for (Value::use_iterator UI = V2->use_begin(), UE = V2->use_end();
979 Use &TheUse = UI.getUse();
981 if (Instruction *I = dyn_cast<Instruction>(TheUse.getUser())) {
990 /// cmpInstToLattice - converts an CmpInst::Predicate to lattice value
991 /// Requires that the lattice value be valid; does not accept ICMP_EQ.
992 static LatticeVal cmpInstToLattice(ICmpInst::Predicate Pred) {
994 case ICmpInst::ICMP_EQ:
995 assert(!"No matching lattice value.");
996 return static_cast<LatticeVal>(EQ_BIT);
998 assert(!"Invalid 'icmp' predicate.");
999 case ICmpInst::ICMP_NE:
1001 case ICmpInst::ICMP_UGT:
1003 case ICmpInst::ICMP_UGE:
1005 case ICmpInst::ICMP_ULT:
1007 case ICmpInst::ICMP_ULE:
1009 case ICmpInst::ICMP_SGT:
1011 case ICmpInst::ICMP_SGE:
1013 case ICmpInst::ICMP_SLT:
1015 case ICmpInst::ICMP_SLE:
1021 VRPSolver(InequalityGraph &IG, UnreachableBlocks &UB, ETForest *Forest,
1022 bool &modified, BasicBlock *TopBB)
1026 Top(Forest->getNodeForBlock(TopBB)),
1029 modified(modified) {}
1031 VRPSolver(InequalityGraph &IG, UnreachableBlocks &UB, ETForest *Forest,
1032 bool &modified, Instruction *TopInst)
1039 TopBB = TopInst->getParent();
1040 Top = Forest->getNodeForBlock(TopBB);
1043 bool isRelatedBy(Value *V1, Value *V2, ICmpInst::Predicate Pred) const {
1044 if (Constant *C1 = dyn_cast<Constant>(V1))
1045 if (Constant *C2 = dyn_cast<Constant>(V2))
1046 return ConstantExpr::getCompare(Pred, C1, C2) ==
1047 ConstantBool::getTrue();
1049 // XXX: this is lousy. If we're passed a Constant, then we might miss
1050 // some relationships if it isn't in the IG because the relationships
1051 // added by initializeConstant are missing.
1052 if (isa<Constant>(V1)) IG.getOrInsertNode(V1, Top);
1053 if (isa<Constant>(V2)) IG.getOrInsertNode(V2, Top);
1055 if (unsigned n1 = IG.getNode(V1, Top))
1056 if (unsigned n2 = IG.getNode(V2, Top)) {
1057 if (n1 == n2) return Pred == ICmpInst::ICMP_EQ ||
1058 Pred == ICmpInst::ICMP_ULE ||
1059 Pred == ICmpInst::ICMP_UGE ||
1060 Pred == ICmpInst::ICMP_SLE ||
1061 Pred == ICmpInst::ICMP_SGE;
1062 if (Pred == ICmpInst::ICMP_EQ) return false;
1063 return IG.isRelatedBy(n1, n2, Top, cmpInstToLattice(Pred));
1069 /// add - adds a new property to the work queue
1070 void add(Value *V1, Value *V2, ICmpInst::Predicate Pred,
1071 Instruction *I = NULL) {
1072 DOUT << "adding " << *V1 << " " << Pred << " " << *V2;
1073 if (I) DOUT << " context: " << *I;
1074 else DOUT << " default context";
1077 WorkList.push_back(Operation());
1078 Operation &O = WorkList.back();
1079 O.LHS = V1, O.RHS = V2, O.Op = Pred, O.Context = I;
1082 /// defToOps - Given an instruction definition that we've learned something
1083 /// new about, find any new relationships between its operands.
1084 void defToOps(Instruction *I) {
1085 Instruction *NewContext = below(I) ? I : TopInst;
1086 Value *Canonical = IG.canonicalize(I, Top);
1088 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
1089 const Type *Ty = BO->getType();
1090 assert(!Ty->isFPOrFPVector() && "Float in work queue!");
1092 Value *Op0 = IG.canonicalize(BO->getOperand(0), Top);
1093 Value *Op1 = IG.canonicalize(BO->getOperand(1), Top);
1095 // TODO: "and bool true, %x" EQ %y then %x EQ %y.
1097 switch (BO->getOpcode()) {
1098 case Instruction::And: {
1099 // "and int %a, %b" EQ -1 then %a EQ -1 and %b EQ -1
1100 // "and bool %a, %b" EQ true then %a EQ true and %b EQ true
1101 ConstantIntegral *CI = ConstantIntegral::getAllOnesValue(Ty);
1102 if (Canonical == CI) {
1103 add(CI, Op0, ICmpInst::ICMP_EQ, NewContext);
1104 add(CI, Op1, ICmpInst::ICMP_EQ, NewContext);
1107 case Instruction::Or: {
1108 // "or int %a, %b" EQ 0 then %a EQ 0 and %b EQ 0
1109 // "or bool %a, %b" EQ false then %a EQ false and %b EQ false
1110 Constant *Zero = Constant::getNullValue(Ty);
1111 if (Canonical == Zero) {
1112 add(Zero, Op0, ICmpInst::ICMP_EQ, NewContext);
1113 add(Zero, Op1, ICmpInst::ICMP_EQ, NewContext);
1116 case Instruction::Xor: {
1117 // "xor bool true, %a" EQ true then %a EQ false
1118 // "xor bool true, %a" EQ false then %a EQ true
1119 // "xor bool false, %a" EQ true then %a EQ true
1120 // "xor bool false, %a" EQ false then %a EQ false
1121 // "xor int %c, %a" EQ %c then %a EQ 0
1122 // "xor int %c, %a" NE %c then %a NE 0
1123 // 1. Repeat all of the above, with order of operands reversed.
1126 if (!isa<Constant>(LHS)) std::swap(LHS, RHS);
1128 if (ConstantBool *CB = dyn_cast<ConstantBool>(Canonical)) {
1129 if (ConstantBool *A = dyn_cast<ConstantBool>(LHS))
1130 add(RHS, ConstantBool::get(A->getValue() ^ CB->getValue()),
1131 ICmpInst::ICMP_EQ, NewContext);
1133 if (Canonical == LHS) {
1134 if (isa<ConstantIntegral>(Canonical))
1135 add(RHS, Constant::getNullValue(Ty), ICmpInst::ICMP_EQ,
1137 } else if (isRelatedBy(LHS, Canonical, ICmpInst::ICMP_NE)) {
1138 add(RHS, Constant::getNullValue(Ty), ICmpInst::ICMP_NE,
1145 } else if (ICmpInst *IC = dyn_cast<ICmpInst>(I)) {
1146 // "icmp ult int %a, int %y" EQ true then %a u< y
1149 if (Canonical == ConstantBool::getTrue()) {
1150 add(IC->getOperand(0), IC->getOperand(1), IC->getPredicate(),
1152 } else if (Canonical == ConstantBool::getFalse()) {
1153 add(IC->getOperand(0), IC->getOperand(1),
1154 ICmpInst::getInversePredicate(IC->getPredicate()), NewContext);
1156 } else if (SelectInst *SI = dyn_cast<SelectInst>(I)) {
1157 if (I->getType()->isFPOrFPVector()) return;
1159 // Given: "%a = select bool %x, int %b, int %c"
1160 // %a EQ %b and %b NE %c then %x EQ true
1161 // %a EQ %c and %b NE %c then %x EQ false
1163 Value *True = SI->getTrueValue();
1164 Value *False = SI->getFalseValue();
1165 if (isRelatedBy(True, False, ICmpInst::ICMP_NE)) {
1166 if (Canonical == IG.canonicalize(True, Top) ||
1167 isRelatedBy(Canonical, False, ICmpInst::ICMP_NE))
1168 add(SI->getCondition(), ConstantBool::getTrue(),
1169 ICmpInst::ICMP_EQ, NewContext);
1170 else if (Canonical == IG.canonicalize(False, Top) ||
1171 isRelatedBy(I, True, ICmpInst::ICMP_NE))
1172 add(SI->getCondition(), ConstantBool::getFalse(),
1173 ICmpInst::ICMP_EQ, NewContext);
1176 // TODO: CastInst "%a = cast ... %b" where %a is EQ or NE a constant.
1179 /// opsToDef - A new relationship was discovered involving one of this
1180 /// instruction's operands. Find any new relationship involving the
1182 void opsToDef(Instruction *I) {
1183 Instruction *NewContext = below(I) ? I : TopInst;
1185 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
1186 Value *Op0 = IG.canonicalize(BO->getOperand(0), Top);
1187 Value *Op1 = IG.canonicalize(BO->getOperand(1), Top);
1189 if (ConstantIntegral *CI0 = dyn_cast<ConstantIntegral>(Op0))
1190 if (ConstantIntegral *CI1 = dyn_cast<ConstantIntegral>(Op1)) {
1191 add(BO, ConstantExpr::get(BO->getOpcode(), CI0, CI1),
1192 ICmpInst::ICMP_EQ, NewContext);
1196 // "%y = and bool true, %x" then %x EQ %y.
1197 // "%y = or bool false, %x" then %x EQ %y.
1198 if (BO->getOpcode() == Instruction::Or) {
1199 Constant *Zero = Constant::getNullValue(BO->getType());
1201 add(BO, Op1, ICmpInst::ICMP_EQ, NewContext);
1203 } else if (Op1 == Zero) {
1204 add(BO, Op0, ICmpInst::ICMP_EQ, NewContext);
1207 } else if (BO->getOpcode() == Instruction::And) {
1208 Constant *AllOnes = ConstantIntegral::getAllOnesValue(BO->getType());
1209 if (Op0 == AllOnes) {
1210 add(BO, Op1, ICmpInst::ICMP_EQ, NewContext);
1212 } else if (Op1 == AllOnes) {
1213 add(BO, Op0, ICmpInst::ICMP_EQ, NewContext);
1218 // "%x = add int %y, %z" and %x EQ %y then %z EQ 0
1219 // "%x = mul int %y, %z" and %x EQ %y then %z EQ 1
1220 // 1. Repeat all of the above, with order of operands reversed.
1221 // "%x = udiv int %y, %z" and %x EQ %y then %z EQ 1
1223 Value *Known = Op0, *Unknown = Op1;
1224 if (Known != BO) std::swap(Known, Unknown);
1226 const Type *Ty = BO->getType();
1227 assert(!Ty->isFPOrFPVector() && "Float in work queue!");
1229 switch (BO->getOpcode()) {
1231 case Instruction::Xor:
1232 case Instruction::Or:
1233 case Instruction::Add:
1234 case Instruction::Sub:
1235 add(Unknown, Constant::getNullValue(Ty), ICmpInst::ICMP_EQ, NewContext);
1237 case Instruction::UDiv:
1238 case Instruction::SDiv:
1239 if (Unknown == Op0) break; // otherwise, fallthrough
1240 case Instruction::And:
1241 case Instruction::Mul:
1242 Constant *One = NULL;
1243 if (isa<ConstantInt>(Unknown))
1244 One = ConstantInt::get(Ty, 1);
1245 else if (isa<ConstantBool>(Unknown))
1246 One = ConstantBool::getTrue();
1248 if (One) add(Unknown, One, ICmpInst::ICMP_EQ, NewContext);
1253 // TODO: "%a = add int %b, 1" and %b > %z then %a >= %z.
1255 } else if (ICmpInst *IC = dyn_cast<ICmpInst>(I)) {
1256 // "%a = icmp ult %b, %c" and %b u< %c then %a EQ true
1257 // "%a = icmp ult %b, %c" and %b u>= %c then %a EQ false
1260 Value *Op0 = IG.canonicalize(IC->getOperand(0), Top);
1261 Value *Op1 = IG.canonicalize(IC->getOperand(1), Top);
1263 ICmpInst::Predicate Pred = IC->getPredicate();
1264 if (isRelatedBy(Op0, Op1, Pred)) {
1265 add(IC, ConstantBool::getTrue(), ICmpInst::ICMP_EQ, NewContext);
1266 } else if (isRelatedBy(Op0, Op1, ICmpInst::getInversePredicate(Pred))) {
1267 add(IC, ConstantBool::getFalse(), ICmpInst::ICMP_EQ, NewContext);
1270 // TODO: make the predicate more strict, if possible.
1272 } else if (SelectInst *SI = dyn_cast<SelectInst>(I)) {
1273 // Given: "%a = select bool %x, int %b, int %c"
1274 // %x EQ true then %a EQ %b
1275 // %x EQ false then %a EQ %c
1276 // %b EQ %c then %a EQ %b
1278 Value *Canonical = IG.canonicalize(SI->getCondition(), Top);
1279 if (Canonical == ConstantBool::getTrue()) {
1280 add(SI, SI->getTrueValue(), ICmpInst::ICMP_EQ, NewContext);
1281 } else if (Canonical == ConstantBool::getFalse()) {
1282 add(SI, SI->getFalseValue(), ICmpInst::ICMP_EQ, NewContext);
1283 } else if (IG.canonicalize(SI->getTrueValue(), Top) ==
1284 IG.canonicalize(SI->getFalseValue(), Top)) {
1285 add(SI, SI->getTrueValue(), ICmpInst::ICMP_EQ, NewContext);
1288 // TODO: CastInst "%a = cast ... %b" where %b is EQ or NE a constant.
1291 /// solve - process the work queue
1292 /// Return false if a logical contradiction occurs.
1294 //DOUT << "WorkList entry, size: " << WorkList.size() << "\n";
1295 while (!WorkList.empty()) {
1296 //DOUT << "WorkList size: " << WorkList.size() << "\n";
1298 Operation &O = WorkList.front();
1300 TopInst = O.Context;
1301 Top = Forest->getNodeForBlock(TopInst->getParent());
1303 O.LHS = IG.canonicalize(O.LHS, Top);
1304 O.RHS = IG.canonicalize(O.RHS, Top);
1306 assert(O.LHS == IG.canonicalize(O.LHS, Top) && "Canonicalize isn't.");
1307 assert(O.RHS == IG.canonicalize(O.RHS, Top) && "Canonicalize isn't.");
1309 DOUT << "solving " << *O.LHS << " " << O.Op << " " << *O.RHS;
1310 if (O.Context) DOUT << " context: " << *O.Context;
1311 else DOUT << " default context";
1316 // TODO: actually check the constants and add to UB.
1317 if (isa<Constant>(O.LHS) && isa<Constant>(O.RHS)) {
1318 WorkList.pop_front();
1322 if (O.Op == ICmpInst::ICMP_EQ) {
1323 if (!makeEqual(O.LHS, O.RHS))
1326 LatticeVal LV = cmpInstToLattice(O.Op);
1328 if ((LV & EQ_BIT) &&
1329 isRelatedBy(O.LHS, O.RHS, ICmpInst::getSwappedPredicate(O.Op))) {
1330 if (!makeEqual(O.LHS, O.RHS))
1333 if (isRelatedBy(O.LHS, O.RHS, ICmpInst::getInversePredicate(O.Op))){
1334 DOUT << "inequality contradiction!\n";
1335 WorkList.pop_front();
1339 unsigned n1 = IG.getOrInsertNode(O.LHS, Top);
1340 unsigned n2 = IG.getOrInsertNode(O.RHS, Top);
1343 if (O.Op != ICmpInst::ICMP_UGE && O.Op != ICmpInst::ICMP_ULE &&
1344 O.Op != ICmpInst::ICMP_SGE && O.Op != ICmpInst::ICMP_SLE)
1347 WorkList.pop_front();
1351 if (IG.isRelatedBy(n1, n2, Top, LV)) {
1352 WorkList.pop_front();
1356 IG.addInequality(n1, n2, Top, LV);
1358 if (Instruction *I1 = dyn_cast<Instruction>(O.LHS)) defToOps(I1);
1359 if (isa<Instruction>(O.LHS) || isa<Argument>(O.LHS)) {
1360 for (Value::use_iterator UI = O.LHS->use_begin(),
1361 UE = O.LHS->use_end(); UI != UE;) {
1362 Use &TheUse = UI.getUse();
1364 if (Instruction *I = dyn_cast<Instruction>(TheUse.getUser())) {
1369 if (Instruction *I2 = dyn_cast<Instruction>(O.RHS)) defToOps(I2);
1370 if (isa<Instruction>(O.RHS) || isa<Argument>(O.RHS)) {
1371 for (Value::use_iterator UI = O.RHS->use_begin(),
1372 UE = O.RHS->use_end(); UI != UE;) {
1373 Use &TheUse = UI.getUse();
1375 if (Instruction *I = dyn_cast<Instruction>(TheUse.getUser())) {
1382 WorkList.pop_front();
1387 /// PredicateSimplifier - This class is a simplifier that replaces
1388 /// one equivalent variable with another. It also tracks what
1389 /// can't be equal and will solve setcc instructions when possible.
1390 /// @brief Root of the predicate simplifier optimization.
1391 class VISIBILITY_HIDDEN PredicateSimplifier : public FunctionPass {
1395 InequalityGraph *IG;
1396 UnreachableBlocks UB;
1398 std::vector<DominatorTree::Node *> WorkList;
1401 bool runOnFunction(Function &F);
1403 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
1404 AU.addRequiredID(BreakCriticalEdgesID);
1405 AU.addRequired<DominatorTree>();
1406 AU.addRequired<ETForest>();
1410 /// Forwards - Adds new properties into PropertySet and uses them to
1411 /// simplify instructions. Because new properties sometimes apply to
1412 /// a transition from one BasicBlock to another, this will use the
1413 /// PredicateSimplifier::proceedToSuccessor(s) interface to enter the
1414 /// basic block with the new PropertySet.
1415 /// @brief Performs abstract execution of the program.
1416 class VISIBILITY_HIDDEN Forwards : public InstVisitor<Forwards> {
1417 friend class InstVisitor<Forwards>;
1418 PredicateSimplifier *PS;
1419 DominatorTree::Node *DTNode;
1422 InequalityGraph &IG;
1423 UnreachableBlocks &UB;
1425 Forwards(PredicateSimplifier *PS, DominatorTree::Node *DTNode)
1426 : PS(PS), DTNode(DTNode), IG(*PS->IG), UB(PS->UB) {}
1428 void visitTerminatorInst(TerminatorInst &TI);
1429 void visitBranchInst(BranchInst &BI);
1430 void visitSwitchInst(SwitchInst &SI);
1432 void visitAllocaInst(AllocaInst &AI);
1433 void visitLoadInst(LoadInst &LI);
1434 void visitStoreInst(StoreInst &SI);
1436 void visitBinaryOperator(BinaryOperator &BO);
1439 // Used by terminator instructions to proceed from the current basic
1440 // block to the next. Verifies that "current" dominates "next",
1441 // then calls visitBasicBlock.
1442 void proceedToSuccessors(DominatorTree::Node *Current) {
1443 for (DominatorTree::Node::iterator I = Current->begin(),
1444 E = Current->end(); I != E; ++I) {
1445 WorkList.push_back(*I);
1449 void proceedToSuccessor(DominatorTree::Node *Next) {
1450 WorkList.push_back(Next);
1453 // Visits each instruction in the basic block.
1454 void visitBasicBlock(DominatorTree::Node *Node) {
1455 BasicBlock *BB = Node->getBlock();
1456 ETNode *ET = Forest->getNodeForBlock(BB);
1457 DOUT << "Entering Basic Block: " << BB->getName() << " (" << ET << ")\n";
1458 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
1459 visitInstruction(I++, Node, ET);
1463 // Tries to simplify each Instruction and add new properties to
1465 void visitInstruction(Instruction *I, DominatorTree::Node *DT, ETNode *ET) {
1466 DOUT << "Considering instruction " << *I << "\n";
1469 // Sometimes instructions are killed in earlier analysis.
1470 if (isInstructionTriviallyDead(I)) {
1474 I->eraseFromParent();
1478 // Try to replace the whole instruction.
1479 Value *V = IG->canonicalize(I, ET);
1480 assert(V == I && "Late instruction canonicalization.");
1484 DOUT << "Removing " << *I << ", replacing with " << *V << "\n";
1486 I->replaceAllUsesWith(V);
1487 I->eraseFromParent();
1491 // Try to substitute operands.
1492 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
1493 Value *Oper = I->getOperand(i);
1494 Value *V = IG->canonicalize(Oper, ET);
1495 assert(V == Oper && "Late operand canonicalization.");
1499 DOUT << "Resolving " << *I;
1500 I->setOperand(i, V);
1501 DOUT << " into " << *I;
1505 DOUT << "push (%" << I->getParent()->getName() << ")\n";
1506 Forwards visit(this, DT);
1508 DOUT << "pop (%" << I->getParent()->getName() << ")\n";
1512 bool PredicateSimplifier::runOnFunction(Function &F) {
1513 DT = &getAnalysis<DominatorTree>();
1514 Forest = &getAnalysis<ETForest>();
1516 Forest->updateDFSNumbers(); // XXX: should only act when numbers are out of date
1518 DOUT << "Entering Function: " << F.getName() << "\n";
1521 BasicBlock *RootBlock = &F.getEntryBlock();
1522 IG = new InequalityGraph(Forest->getNodeForBlock(RootBlock));
1523 WorkList.push_back(DT->getRootNode());
1526 DominatorTree::Node *DTNode = WorkList.back();
1527 WorkList.pop_back();
1528 if (!UB.isDead(DTNode->getBlock())) visitBasicBlock(DTNode);
1529 } while (!WorkList.empty());
1533 modified |= UB.kill();
1538 void PredicateSimplifier::Forwards::visitTerminatorInst(TerminatorInst &TI) {
1539 PS->proceedToSuccessors(DTNode);
1542 void PredicateSimplifier::Forwards::visitBranchInst(BranchInst &BI) {
1543 if (BI.isUnconditional()) {
1544 PS->proceedToSuccessors(DTNode);
1548 Value *Condition = BI.getCondition();
1549 BasicBlock *TrueDest = BI.getSuccessor(0);
1550 BasicBlock *FalseDest = BI.getSuccessor(1);
1552 if (isa<Constant>(Condition) || TrueDest == FalseDest) {
1553 PS->proceedToSuccessors(DTNode);
1557 for (DominatorTree::Node::iterator I = DTNode->begin(), E = DTNode->end();
1559 BasicBlock *Dest = (*I)->getBlock();
1560 DOUT << "Branch thinking about %" << Dest->getName()
1561 << "(" << PS->Forest->getNodeForBlock(Dest) << ")\n";
1563 if (Dest == TrueDest) {
1564 DOUT << "(" << DTNode->getBlock()->getName() << ") true set:\n";
1565 VRPSolver VRP(IG, UB, PS->Forest, PS->modified, Dest);
1566 VRP.add(ConstantBool::getTrue(), Condition, ICmpInst::ICMP_EQ);
1569 } else if (Dest == FalseDest) {
1570 DOUT << "(" << DTNode->getBlock()->getName() << ") false set:\n";
1571 VRPSolver VRP(IG, UB, PS->Forest, PS->modified, Dest);
1572 VRP.add(ConstantBool::getFalse(), Condition, ICmpInst::ICMP_EQ);
1577 PS->proceedToSuccessor(*I);
1581 void PredicateSimplifier::Forwards::visitSwitchInst(SwitchInst &SI) {
1582 Value *Condition = SI.getCondition();
1584 // Set the EQProperty in each of the cases BBs, and the NEProperties
1585 // in the default BB.
1587 for (DominatorTree::Node::iterator I = DTNode->begin(), E = DTNode->end();
1589 BasicBlock *BB = (*I)->getBlock();
1590 DOUT << "Switch thinking about BB %" << BB->getName()
1591 << "(" << PS->Forest->getNodeForBlock(BB) << ")\n";
1593 VRPSolver VRP(IG, UB, PS->Forest, PS->modified, BB);
1594 if (BB == SI.getDefaultDest()) {
1595 for (unsigned i = 1, e = SI.getNumCases(); i < e; ++i)
1596 if (SI.getSuccessor(i) != BB)
1597 VRP.add(Condition, SI.getCaseValue(i), ICmpInst::ICMP_NE);
1599 } else if (ConstantInt *CI = SI.findCaseDest(BB)) {
1600 VRP.add(Condition, CI, ICmpInst::ICMP_EQ);
1603 PS->proceedToSuccessor(*I);
1607 void PredicateSimplifier::Forwards::visitAllocaInst(AllocaInst &AI) {
1608 VRPSolver VRP(IG, UB, PS->Forest, PS->modified, &AI);
1609 VRP.add(Constant::getNullValue(AI.getType()), &AI, ICmpInst::ICMP_NE);
1613 void PredicateSimplifier::Forwards::visitLoadInst(LoadInst &LI) {
1614 Value *Ptr = LI.getPointerOperand();
1615 // avoid "load uint* null" -> null NE null.
1616 if (isa<Constant>(Ptr)) return;
1618 VRPSolver VRP(IG, UB, PS->Forest, PS->modified, &LI);
1619 VRP.add(Constant::getNullValue(Ptr->getType()), Ptr, ICmpInst::ICMP_NE);
1623 void PredicateSimplifier::Forwards::visitStoreInst(StoreInst &SI) {
1624 Value *Ptr = SI.getPointerOperand();
1625 if (isa<Constant>(Ptr)) return;
1627 VRPSolver VRP(IG, UB, PS->Forest, PS->modified, &SI);
1628 VRP.add(Constant::getNullValue(Ptr->getType()), Ptr, ICmpInst::ICMP_NE);
1632 void PredicateSimplifier::Forwards::visitBinaryOperator(BinaryOperator &BO) {
1633 Instruction::BinaryOps ops = BO.getOpcode();
1636 case Instruction::URem:
1637 case Instruction::SRem:
1638 case Instruction::UDiv:
1639 case Instruction::SDiv: {
1640 Value *Divisor = BO.getOperand(1);
1641 VRPSolver VRP(IG, UB, PS->Forest, PS->modified, &BO);
1642 VRP.add(Constant::getNullValue(Divisor->getType()), Divisor,
1652 RegisterPass<PredicateSimplifier> X("predsimplify",
1653 "Predicate Simplifier");
1656 FunctionPass *llvm::createPredicateSimplifierPass() {
1657 return new PredicateSimplifier();