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) {}
251 virtual void dump() const {
252 dump(*cerr.stream());
255 void dump(std::ostream &os) const {
256 os << *getValue() << ":\n";
257 for (Node::const_iterator NI = begin(), NE = end(); NI != NE; ++NI) {
258 static const std::string names[32] =
259 { "000000", "000001", "000002", "000003", "000004", "000005",
260 "000006", "000007", "000008", "000009", " >", " >=",
261 " s>u<", "s>=u<=", " s>", " s>=", "000016", "000017",
262 " s<u>", "s<=u>=", " <", " <=", " s<", " s<=",
263 "000024", "000025", " u>", " u>=", " u<", " u<=",
265 os << " " << names[NI->LV] << " " << NI->To
266 << "(" << NI->Subtree << ")\n";
272 iterator begin() { return Relations.begin(); }
273 iterator end() { return Relations.end(); }
274 const_iterator begin() const { return Relations.begin(); }
275 const_iterator end() const { return Relations.end(); }
277 iterator find(unsigned n, ETNode *Subtree) {
279 for (iterator I = std::lower_bound(begin(), E, n);
280 I != E && I->To == n; ++I) {
281 if (Subtree->DominatedBy(I->Subtree))
287 const_iterator find(unsigned n, ETNode *Subtree) const {
288 const_iterator E = end();
289 for (const_iterator I = std::lower_bound(begin(), E, n);
290 I != E && I->To == n; ++I) {
291 if (Subtree->DominatedBy(I->Subtree))
297 Value *getValue() const
302 /// Updates the lattice value for a given node. Create a new entry if
303 /// one doesn't exist, otherwise it merges the values. The new lattice
304 /// value must not be inconsistent with any previously existing value.
305 void update(unsigned n, LatticeVal R, ETNode *Subtree) {
306 assert(validPredicate(R) && "Invalid predicate.");
307 iterator I = find(n, Subtree);
309 Edge edge(n, R, Subtree);
310 iterator Insert = std::lower_bound(begin(), end(), edge);
311 Relations.insert(Insert, edge);
313 LatticeVal LV = static_cast<LatticeVal>(I->LV & R);
314 assert(validPredicate(LV) && "Invalid union of lattice values.");
316 if (Subtree == I->Subtree)
319 assert(Subtree->DominatedBy(I->Subtree) &&
320 "Find returned subtree that doesn't apply.");
322 Edge edge(n, R, Subtree);
323 iterator Insert = std::lower_bound(begin(), end(), edge);
324 Relations.insert(Insert, edge);
332 struct VISIBILITY_HIDDEN NodeMapEdge {
337 NodeMapEdge(Value *V, unsigned index, ETNode *Subtree)
338 : V(V), index(index), Subtree(Subtree) {}
340 bool operator==(const NodeMapEdge &RHS) const {
342 Subtree == RHS.Subtree;
345 bool operator<(const NodeMapEdge &RHS) const {
346 if (V != RHS.V) return V < RHS.V;
347 return OrderByDominance()(Subtree, RHS.Subtree);
350 bool operator<(Value *RHS) const {
355 typedef std::vector<NodeMapEdge> NodeMapType;
358 std::vector<Node> Nodes;
360 std::vector<std::pair<ConstantIntegral *, unsigned> > Constants;
361 void initializeConstant(Constant *C, unsigned index) {
362 ConstantIntegral *CI = dyn_cast<ConstantIntegral>(C);
365 // XXX: instead of O(n) calls to addInequality, just find the 2, 3 or 4
366 // nodes that are nearest less than or greater than (signed or unsigned).
367 for (std::vector<std::pair<ConstantIntegral *, unsigned> >::iterator
368 I = Constants.begin(), E = Constants.end(); I != E; ++I) {
369 ConstantIntegral *Other = I->first;
370 if (CI->getType() == Other->getType()) {
373 if (CI->getZExtValue() < Other->getZExtValue())
378 if (CI->getSExtValue() < Other->getSExtValue())
383 LatticeVal LV = static_cast<LatticeVal>(lv);
384 assert(validPredicate(LV) && "Not a valid predicate.");
385 if (!isRelatedBy(index, I->second, TreeRoot, LV))
386 addInequality(index, I->second, TreeRoot, LV);
389 Constants.push_back(std::make_pair(CI, index));
393 /// node - returns the node object at a given index retrieved from getNode.
394 /// Index zero is reserved and may not be passed in here. The pointer
395 /// returned is valid until the next call to newNode or getOrInsertNode.
396 Node *node(unsigned index) {
397 assert(index != 0 && "Zero index is reserved for not found.");
398 assert(index <= Nodes.size() && "Index out of range.");
399 return &Nodes[index-1];
402 /// Returns the node currently representing Value V, or zero if no such
404 unsigned getNode(Value *V, ETNode *Subtree) {
405 NodeMapType::iterator E = NodeMap.end();
406 NodeMapEdge Edge(V, 0, Subtree);
407 NodeMapType::iterator I = std::lower_bound(NodeMap.begin(), E, Edge);
408 while (I != E && I->V == V) {
409 if (Subtree->DominatedBy(I->Subtree))
416 /// getOrInsertNode - always returns a valid node index, creating a node
417 /// to match the Value if needed.
418 unsigned getOrInsertNode(Value *V, ETNode *Subtree) {
419 if (unsigned n = getNode(V, Subtree))
425 /// newNode - creates a new node for a given Value and returns the index.
426 unsigned newNode(Value *V) {
427 Nodes.push_back(Node(V));
429 NodeMapEdge MapEntry = NodeMapEdge(V, Nodes.size(), TreeRoot);
430 assert(!std::binary_search(NodeMap.begin(), NodeMap.end(), MapEntry) &&
431 "Attempt to create a duplicate Node.");
432 NodeMap.insert(std::lower_bound(NodeMap.begin(), NodeMap.end(),
433 MapEntry), MapEntry);
436 // This is the missing piece to turn on VRP.
437 if (Constant *C = dyn_cast<Constant>(V))
438 initializeConstant(C, MapEntry.index);
441 return MapEntry.index;
444 /// If the Value is in the graph, return the canonical form. Otherwise,
445 /// return the original Value.
446 Value *canonicalize(Value *V, ETNode *Subtree) {
447 if (isa<Constant>(V)) return V;
449 if (unsigned n = getNode(V, Subtree))
450 return node(n)->getValue();
455 /// isRelatedBy - true iff n1 op n2
456 bool isRelatedBy(unsigned n1, unsigned n2, ETNode *Subtree, LatticeVal LV) {
457 if (n1 == n2) return LV & EQ_BIT;
460 Node::iterator I = N1->find(n2, Subtree), E = N1->end();
461 if (I != E) return (I->LV & LV) == I->LV;
466 // The add* methods assume that your input is logically valid and may
467 // assertion-fail or infinitely loop if you attempt a contradiction.
469 void addEquality(unsigned n, Value *V, ETNode *Subtree) {
470 assert(canonicalize(node(n)->getValue(), Subtree) == node(n)->getValue()
471 && "Node's 'canonical' choice isn't best within this subtree.");
473 // Suppose that we are given "%x -> node #1 (%y)". The problem is that
474 // we may already have "%z -> node #2 (%x)" somewhere above us in the
475 // graph. We need to find those edges and add "%z -> node #1 (%y)"
476 // to keep the lookups canonical.
478 std::vector<Value *> ToRepoint;
479 ToRepoint.push_back(V);
481 if (unsigned Conflict = getNode(V, Subtree)) {
482 // XXX: NodeMap.size() exceeds 68000 entries compiling kimwitu++!
483 // This adds 57 seconds to the otherwise 3 second build. Unacceptable.
485 // IDEA: could we iterate 1..Nodes.size() calling getNode? It's
486 // O(n log n) but kimwitu++ only has about 300 nodes.
487 for (NodeMapType::iterator I = NodeMap.begin(), E = NodeMap.end();
489 if (I->index == Conflict && Subtree->DominatedBy(I->Subtree))
490 ToRepoint.push_back(I->V);
494 for (std::vector<Value *>::iterator VI = ToRepoint.begin(),
495 VE = ToRepoint.end(); VI != VE; ++VI) {
498 // XXX: review this code. This may be doing too many insertions.
499 NodeMapEdge Edge(V, n, Subtree);
500 NodeMapType::iterator E = NodeMap.end();
501 NodeMapType::iterator I = std::lower_bound(NodeMap.begin(), E, Edge);
502 if (I == E || I->V != V || I->Subtree != Subtree) {
504 NodeMap.insert(I, Edge);
505 } else if (I != E && I->V == V && I->Subtree == Subtree) {
506 // Update best choice
512 if (isa<Constant>(V)) {
513 if (isa<Constant>(N->getValue())) {
514 assert(V == N->getValue() && "Constant equals different constant?");
521 /// addInequality - Sets n1 op n2.
522 /// It is also an error to call this on an inequality that is already true.
523 void addInequality(unsigned n1, unsigned n2, ETNode *Subtree,
525 assert(n1 != n2 && "A node can't be inequal to itself.");
528 assert(!isRelatedBy(n1, n2, Subtree, reversePredicate(LV1)) &&
529 "Contradictory inequality.");
534 // Suppose we're adding %n1 < %n2. Find all the %a < %n1 and
535 // add %a < %n2 too. This keeps the graph fully connected.
537 // Someone with a head for this sort of logic, please review this.
538 // Given that %x SLTUGT %y and %a SLEUANY %x, what is the relationship
539 // between %a and %y? I believe the below code is correct, but I don't
540 // think it's the most efficient solution.
542 unsigned LV1_s = LV1 & (SLT_BIT|SGT_BIT);
543 unsigned LV1_u = LV1 & (ULT_BIT|UGT_BIT);
544 for (Node::iterator I = N1->begin(), E = N1->end(); I != E; ++I) {
545 if (I->LV != NE && I->To != n2) {
546 ETNode *Local_Subtree = NULL;
547 if (Subtree->DominatedBy(I->Subtree))
548 Local_Subtree = Subtree;
549 else if (I->Subtree->DominatedBy(Subtree))
550 Local_Subtree = I->Subtree;
553 unsigned new_relationship = 0;
554 LatticeVal ILV = reversePredicate(I->LV);
555 unsigned ILV_s = ILV & (SLT_BIT|SGT_BIT);
556 unsigned ILV_u = ILV & (ULT_BIT|UGT_BIT);
558 if (LV1_s != (SLT_BIT|SGT_BIT) && ILV_s == LV1_s)
559 new_relationship |= ILV_s;
561 if (LV1_u != (ULT_BIT|UGT_BIT) && ILV_u == LV1_u)
562 new_relationship |= ILV_u;
564 if (new_relationship) {
565 if ((new_relationship & (SLT_BIT|SGT_BIT)) == 0)
566 new_relationship |= (SLT_BIT|SGT_BIT);
567 if ((new_relationship & (ULT_BIT|UGT_BIT)) == 0)
568 new_relationship |= (ULT_BIT|UGT_BIT);
569 if ((LV1 & EQ_BIT) && (ILV & EQ_BIT))
570 new_relationship |= EQ_BIT;
572 LatticeVal NewLV = static_cast<LatticeVal>(new_relationship);
574 node(I->To)->update(n2, NewLV, Local_Subtree);
575 N2->update(I->To, reversePredicate(NewLV), Local_Subtree);
581 for (Node::iterator I = N2->begin(), E = N2->end(); I != E; ++I) {
582 if (I->LV != NE && I->To != n1) {
583 ETNode *Local_Subtree = NULL;
584 if (Subtree->DominatedBy(I->Subtree))
585 Local_Subtree = Subtree;
586 else if (I->Subtree->DominatedBy(Subtree))
587 Local_Subtree = I->Subtree;
590 unsigned new_relationship = 0;
591 unsigned ILV_s = I->LV & (SLT_BIT|SGT_BIT);
592 unsigned ILV_u = I->LV & (ULT_BIT|UGT_BIT);
594 if (LV1_s != (SLT_BIT|SGT_BIT) && ILV_s == LV1_s)
595 new_relationship |= ILV_s;
597 if (LV1_u != (ULT_BIT|UGT_BIT) && ILV_u == LV1_u)
598 new_relationship |= ILV_u;
600 if (new_relationship) {
601 if ((new_relationship & (SLT_BIT|SGT_BIT)) == 0)
602 new_relationship |= (SLT_BIT|SGT_BIT);
603 if ((new_relationship & (ULT_BIT|UGT_BIT)) == 0)
604 new_relationship |= (ULT_BIT|UGT_BIT);
605 if ((LV1 & EQ_BIT) && (I->LV & EQ_BIT))
606 new_relationship |= EQ_BIT;
608 LatticeVal NewLV = static_cast<LatticeVal>(new_relationship);
610 N1->update(I->To, NewLV, Local_Subtree);
611 node(I->To)->update(n1, reversePredicate(NewLV), Local_Subtree);
618 N1->update(n2, LV1, Subtree);
619 N2->update(n1, reversePredicate(LV1), Subtree);
622 /// Removes a Value from the graph, but does not delete any nodes. As this
623 /// method does not delete Nodes, V may not be the canonical choice for
624 /// a node with any relationships. It is invalid to call newNode on a Value
625 /// that has been removed.
626 void remove(Value *V) {
627 for (unsigned i = 0; i < NodeMap.size();) {
628 NodeMapType::iterator I = NodeMap.begin()+i;
629 assert((node(I->index)->getValue() != V || node(I->index)->begin() ==
630 node(I->index)->end()) && "Tried to delete in-use node.");
633 if (node(I->index)->getValue() == V)
634 node(I->index)->Canonical = NULL;
642 virtual ~InequalityGraph() {}
643 virtual void dump() {
644 dump(*cerr.stream());
647 void dump(std::ostream &os) {
648 std::set<Node *> VisitedNodes;
649 for (NodeMapType::const_iterator I = NodeMap.begin(), E = NodeMap.end();
651 Node *N = node(I->index);
652 os << *I->V << " == " << I->index << "(" << I->Subtree << ")\n";
653 if (VisitedNodes.insert(N).second) {
654 os << I->index << ". ";
655 if (!N->getValue()) os << "(deleted node)\n";
663 /// UnreachableBlocks keeps tracks of blocks that are for one reason or
664 /// another discovered to be unreachable. This is used to cull the graph when
665 /// analyzing instructions, and to mark blocks with the "unreachable"
666 /// terminator instruction after the function has executed.
667 class VISIBILITY_HIDDEN UnreachableBlocks {
669 std::vector<BasicBlock *> DeadBlocks;
672 /// mark - mark a block as dead
673 void mark(BasicBlock *BB) {
674 std::vector<BasicBlock *>::iterator E = DeadBlocks.end();
675 std::vector<BasicBlock *>::iterator I =
676 std::lower_bound(DeadBlocks.begin(), E, BB);
678 if (I == E || *I != BB) DeadBlocks.insert(I, BB);
681 /// isDead - returns whether a block is known to be dead already
682 bool isDead(BasicBlock *BB) {
683 std::vector<BasicBlock *>::iterator E = DeadBlocks.end();
684 std::vector<BasicBlock *>::iterator I =
685 std::lower_bound(DeadBlocks.begin(), E, BB);
687 return I != E && *I == BB;
690 /// kill - replace the dead blocks' terminator with an UnreachableInst.
692 bool modified = false;
693 for (std::vector<BasicBlock *>::iterator I = DeadBlocks.begin(),
694 E = DeadBlocks.end(); I != E; ++I) {
697 DOUT << "unreachable block: " << BB->getName() << "\n";
699 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB);
701 BasicBlock *Succ = *SI;
702 Succ->removePredecessor(BB);
705 TerminatorInst *TI = BB->getTerminator();
706 TI->replaceAllUsesWith(UndefValue::get(TI->getType()));
707 TI->eraseFromParent();
708 new UnreachableInst(BB);
717 /// VRPSolver keeps track of how changes to one variable affect other
718 /// variables, and forwards changes along to the InequalityGraph. It
719 /// also maintains the correct choice for "canonical" in the IG.
720 /// @brief VRPSolver calculates inferences from a new relationship.
721 class VISIBILITY_HIDDEN VRPSolver {
725 ICmpInst::Predicate Op;
727 Instruction *Context;
729 std::deque<Operation> WorkList;
732 UnreachableBlocks &UB;
736 Instruction *TopInst;
739 typedef InequalityGraph::Node Node;
741 /// IdomI - Determines whether one Instruction dominates another.
742 bool IdomI(Instruction *I1, Instruction *I2) const {
743 BasicBlock *BB1 = I1->getParent(),
744 *BB2 = I2->getParent();
746 if (isa<TerminatorInst>(I1)) return false;
747 if (isa<TerminatorInst>(I2)) return true;
748 if (isa<PHINode>(I1) && !isa<PHINode>(I2)) return true;
749 if (!isa<PHINode>(I1) && isa<PHINode>(I2)) return false;
751 for (BasicBlock::const_iterator I = BB1->begin(), E = BB1->end();
753 if (&*I == I1) return true;
754 if (&*I == I2) return false;
756 assert(!"Instructions not found in parent BasicBlock?");
758 return Forest->properlyDominates(BB1, BB2);
763 /// Returns true if V1 is a better canonical value than V2.
764 bool compare(Value *V1, Value *V2) const {
765 if (isa<Constant>(V1))
766 return !isa<Constant>(V2);
767 else if (isa<Constant>(V2))
769 else if (isa<Argument>(V1))
770 return !isa<Argument>(V2);
771 else if (isa<Argument>(V2))
774 Instruction *I1 = dyn_cast<Instruction>(V1);
775 Instruction *I2 = dyn_cast<Instruction>(V2);
778 return V1->getNumUses() < V2->getNumUses();
780 return IdomI(I1, I2);
783 // below - true if the Instruction is dominated by the current context
784 // block or instruction
785 bool below(Instruction *I) {
787 return IdomI(TopInst, I);
789 ETNode *Node = Forest->getNodeForBlock(I->getParent());
790 return Node == Top || Node->DominatedBy(Top);
794 bool makeEqual(Value *V1, Value *V2) {
795 DOUT << "makeEqual(" << *V1 << ", " << *V2 << ")\n";
797 if (V1 == V2) return true;
799 if (isa<Constant>(V1) && isa<Constant>(V2))
802 unsigned n1 = IG.getNode(V1, Top), n2 = IG.getNode(V2, Top);
805 if (n1 == n2) return true;
806 if (IG.isRelatedBy(n1, n2, Top, NE)) return false;
809 if (n1) assert(V1 == IG.node(n1)->getValue() && "Value isn't canonical.");
810 if (n2) assert(V2 == IG.node(n2)->getValue() && "Value isn't canonical.");
812 if (compare(V2, V1)) { std::swap(V1, V2); std::swap(n1, n2); }
814 assert(!isa<Constant>(V2) && "Tried to remove a constant.");
816 SetVector<unsigned> Remove;
817 if (n2) Remove.insert(n2);
820 // Suppose we're being told that %x == %y, and %x <= %z and %y >= %z.
821 // We can't just merge %x and %y because the relationship with %z would
822 // be EQ and that's invalid. What we're doing is looking for any nodes
823 // %z such that %x <= %z and %y >= %z, and vice versa.
825 // Also handle %a <= %b and %c <= %a when adding %b <= %c.
827 Node *N1 = IG.node(n1);
828 Node::iterator end = N1->end();
829 for (unsigned i = 0; i < Remove.size(); ++i) {
830 Node *N = IG.node(Remove[i]);
831 Value *V = N->getValue();
832 for (Node::iterator I = N->begin(), E = N->end(); I != E; ++I) {
833 if (I->LV & EQ_BIT) {
834 if (Top == I->Subtree || Top->DominatedBy(I->Subtree)) {
835 Node::iterator NI = N1->find(I->To, Top);
837 if (!(NI->LV & EQ_BIT)) return false;
838 if (isRelatedBy(V, IG.node(NI->To)->getValue(),
841 Remove.insert(NI->To);
848 // See if one of the nodes about to be removed is actually a better
849 // canonical choice than n1.
850 unsigned orig_n1 = n1;
851 std::vector<unsigned>::iterator DontRemove = Remove.end();
852 for (std::vector<unsigned>::iterator I = Remove.begin()+1 /* skip n2 */,
853 E = Remove.end(); I != E; ++I) {
855 Value *V = IG.node(n)->getValue();
856 if (compare(V, V1)) {
862 if (DontRemove != Remove.end()) {
863 unsigned n = *DontRemove;
865 Remove.insert(orig_n1);
869 // We'd like to allow makeEqual on two values to perform a simple
870 // substitution without every creating nodes in the IG whenever possible.
872 // The first iteration through this loop operates on V2 before going
873 // through the Remove list and operating on those too. If all of the
874 // iterations performed simple replacements then we exit early.
875 bool exitEarly = true;
877 for (Value *R = V2; i == 0 || i < Remove.size(); ++i) {
878 if (i) R = IG.node(Remove[i])->getValue(); // skip n2.
880 // Try to replace the whole instruction. If we can, we're done.
881 Instruction *I2 = dyn_cast<Instruction>(R);
882 if (I2 && below(I2)) {
883 std::vector<Instruction *> ToNotify;
884 for (Value::use_iterator UI = R->use_begin(), UE = R->use_end();
886 Use &TheUse = UI.getUse();
888 if (Instruction *I = dyn_cast<Instruction>(TheUse.getUser()))
889 ToNotify.push_back(I);
892 DOUT << "Simply removing " << *I2
893 << ", replacing with " << *V1 << "\n";
894 I2->replaceAllUsesWith(V1);
895 // leave it dead; it'll get erased later.
899 for (std::vector<Instruction *>::iterator II = ToNotify.begin(),
900 IE = ToNotify.end(); II != IE; ++II) {
907 // Otherwise, replace all dominated uses.
908 for (Value::use_iterator UI = R->use_begin(), UE = R->use_end();
910 Use &TheUse = UI.getUse();
912 if (Instruction *I = dyn_cast<Instruction>(TheUse.getUser())) {
922 // If that killed the instruction, stop here.
923 if (I2 && isInstructionTriviallyDead(I2)) {
924 DOUT << "Killed all uses of " << *I2
925 << ", replacing with " << *V1 << "\n";
929 // If we make it to here, then we will need to create a node for N1.
930 // Otherwise, we can skip out early!
934 if (exitEarly) return true;
937 // XXX: this should call newNode, but instead the node might be created
938 // in isRelatedBy. That's also a fixme.
939 if (!n1) n1 = IG.getOrInsertNode(V1, Top);
941 // Migrate relationships from removed nodes to N1.
942 Node *N1 = IG.node(n1);
943 for (std::vector<unsigned>::iterator I = Remove.begin(), E = Remove.end();
946 Node *N = IG.node(n);
947 for (Node::iterator NI = N->begin(), NE = N->end(); NI != NE; ++NI) {
948 if (Top == NI->Subtree || NI->Subtree->DominatedBy(Top)) {
950 assert((NI->LV & EQ_BIT) && "Node inequal to itself.");
953 if (Remove.count(NI->To))
956 IG.node(NI->To)->update(n1, reversePredicate(NI->LV), Top);
957 N1->update(NI->To, NI->LV, Top);
962 // Point V2 (and all items in Remove) to N1.
964 IG.addEquality(n1, V2, Top);
966 for (std::vector<unsigned>::iterator I = Remove.begin(),
967 E = Remove.end(); I != E; ++I) {
968 IG.addEquality(n1, IG.node(*I)->getValue(), Top);
972 // If !Remove.empty() then V2 = Remove[0]->getValue().
973 // Even when Remove is empty, we still want to process V2.
975 for (Value *R = V2; i == 0 || i < Remove.size(); ++i) {
976 if (i) R = IG.node(Remove[i])->getValue(); // skip n2.
978 if (Instruction *I2 = dyn_cast<Instruction>(R)) defToOps(I2);
979 for (Value::use_iterator UI = V2->use_begin(), UE = V2->use_end();
981 Use &TheUse = UI.getUse();
983 if (Instruction *I = dyn_cast<Instruction>(TheUse.getUser())) {
992 /// cmpInstToLattice - converts an CmpInst::Predicate to lattice value
993 /// Requires that the lattice value be valid; does not accept ICMP_EQ.
994 static LatticeVal cmpInstToLattice(ICmpInst::Predicate Pred) {
996 case ICmpInst::ICMP_EQ:
997 assert(!"No matching lattice value.");
998 return static_cast<LatticeVal>(EQ_BIT);
1000 assert(!"Invalid 'icmp' predicate.");
1001 case ICmpInst::ICMP_NE:
1003 case ICmpInst::ICMP_UGT:
1005 case ICmpInst::ICMP_UGE:
1007 case ICmpInst::ICMP_ULT:
1009 case ICmpInst::ICMP_ULE:
1011 case ICmpInst::ICMP_SGT:
1013 case ICmpInst::ICMP_SGE:
1015 case ICmpInst::ICMP_SLT:
1017 case ICmpInst::ICMP_SLE:
1023 VRPSolver(InequalityGraph &IG, UnreachableBlocks &UB, ETForest *Forest,
1024 bool &modified, BasicBlock *TopBB)
1028 Top(Forest->getNodeForBlock(TopBB)),
1031 modified(modified) {}
1033 VRPSolver(InequalityGraph &IG, UnreachableBlocks &UB, ETForest *Forest,
1034 bool &modified, Instruction *TopInst)
1041 TopBB = TopInst->getParent();
1042 Top = Forest->getNodeForBlock(TopBB);
1045 bool isRelatedBy(Value *V1, Value *V2, ICmpInst::Predicate Pred) const {
1046 if (Constant *C1 = dyn_cast<Constant>(V1))
1047 if (Constant *C2 = dyn_cast<Constant>(V2))
1048 return ConstantExpr::getCompare(Pred, C1, C2) ==
1049 ConstantBool::getTrue();
1051 // XXX: this is lousy. If we're passed a Constant, then we might miss
1052 // some relationships if it isn't in the IG because the relationships
1053 // added by initializeConstant are missing.
1054 if (isa<Constant>(V1)) IG.getOrInsertNode(V1, Top);
1055 if (isa<Constant>(V2)) IG.getOrInsertNode(V2, Top);
1057 if (unsigned n1 = IG.getNode(V1, Top))
1058 if (unsigned n2 = IG.getNode(V2, Top)) {
1059 if (n1 == n2) return Pred == ICmpInst::ICMP_EQ ||
1060 Pred == ICmpInst::ICMP_ULE ||
1061 Pred == ICmpInst::ICMP_UGE ||
1062 Pred == ICmpInst::ICMP_SLE ||
1063 Pred == ICmpInst::ICMP_SGE;
1064 if (Pred == ICmpInst::ICMP_EQ) return false;
1065 return IG.isRelatedBy(n1, n2, Top, cmpInstToLattice(Pred));
1071 /// add - adds a new property to the work queue
1072 void add(Value *V1, Value *V2, ICmpInst::Predicate Pred,
1073 Instruction *I = NULL) {
1074 DOUT << "adding " << *V1 << " " << Pred << " " << *V2;
1075 if (I) DOUT << " context: " << *I;
1076 else DOUT << " default context";
1079 WorkList.push_back(Operation());
1080 Operation &O = WorkList.back();
1081 O.LHS = V1, O.RHS = V2, O.Op = Pred, O.Context = I;
1084 /// defToOps - Given an instruction definition that we've learned something
1085 /// new about, find any new relationships between its operands.
1086 void defToOps(Instruction *I) {
1087 Instruction *NewContext = below(I) ? I : TopInst;
1088 Value *Canonical = IG.canonicalize(I, Top);
1090 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
1091 const Type *Ty = BO->getType();
1092 assert(!Ty->isFPOrFPVector() && "Float in work queue!");
1094 Value *Op0 = IG.canonicalize(BO->getOperand(0), Top);
1095 Value *Op1 = IG.canonicalize(BO->getOperand(1), Top);
1097 // TODO: "and bool true, %x" EQ %y then %x EQ %y.
1099 switch (BO->getOpcode()) {
1100 case Instruction::And: {
1101 // "and int %a, %b" EQ -1 then %a EQ -1 and %b EQ -1
1102 // "and bool %a, %b" EQ true then %a EQ true and %b EQ true
1103 ConstantIntegral *CI = ConstantIntegral::getAllOnesValue(Ty);
1104 if (Canonical == CI) {
1105 add(CI, Op0, ICmpInst::ICMP_EQ, NewContext);
1106 add(CI, Op1, ICmpInst::ICMP_EQ, NewContext);
1109 case Instruction::Or: {
1110 // "or int %a, %b" EQ 0 then %a EQ 0 and %b EQ 0
1111 // "or bool %a, %b" EQ false then %a EQ false and %b EQ false
1112 Constant *Zero = Constant::getNullValue(Ty);
1113 if (Canonical == Zero) {
1114 add(Zero, Op0, ICmpInst::ICMP_EQ, NewContext);
1115 add(Zero, Op1, ICmpInst::ICMP_EQ, NewContext);
1118 case Instruction::Xor: {
1119 // "xor bool true, %a" EQ true then %a EQ false
1120 // "xor bool true, %a" EQ false then %a EQ true
1121 // "xor bool false, %a" EQ true then %a EQ true
1122 // "xor bool false, %a" EQ false then %a EQ false
1123 // "xor int %c, %a" EQ %c then %a EQ 0
1124 // "xor int %c, %a" NE %c then %a NE 0
1125 // 1. Repeat all of the above, with order of operands reversed.
1128 if (!isa<Constant>(LHS)) std::swap(LHS, RHS);
1130 if (ConstantBool *CB = dyn_cast<ConstantBool>(Canonical)) {
1131 if (ConstantBool *A = dyn_cast<ConstantBool>(LHS))
1132 add(RHS, ConstantBool::get(A->getValue() ^ CB->getValue()),
1133 ICmpInst::ICMP_EQ, NewContext);
1135 if (Canonical == LHS) {
1136 if (isa<ConstantIntegral>(Canonical))
1137 add(RHS, Constant::getNullValue(Ty), ICmpInst::ICMP_EQ,
1139 } else if (isRelatedBy(LHS, Canonical, ICmpInst::ICMP_NE)) {
1140 add(RHS, Constant::getNullValue(Ty), ICmpInst::ICMP_NE,
1147 } else if (ICmpInst *IC = dyn_cast<ICmpInst>(I)) {
1148 // "icmp ult int %a, int %y" EQ true then %a u< y
1151 if (Canonical == ConstantBool::getTrue()) {
1152 add(IC->getOperand(0), IC->getOperand(1), IC->getPredicate(),
1154 } else if (Canonical == ConstantBool::getFalse()) {
1155 add(IC->getOperand(0), IC->getOperand(1),
1156 ICmpInst::getInversePredicate(IC->getPredicate()), NewContext);
1158 } else if (SelectInst *SI = dyn_cast<SelectInst>(I)) {
1159 if (I->getType()->isFPOrFPVector()) return;
1161 // Given: "%a = select bool %x, int %b, int %c"
1162 // %a EQ %b and %b NE %c then %x EQ true
1163 // %a EQ %c and %b NE %c then %x EQ false
1165 Value *True = SI->getTrueValue();
1166 Value *False = SI->getFalseValue();
1167 if (isRelatedBy(True, False, ICmpInst::ICMP_NE)) {
1168 if (Canonical == IG.canonicalize(True, Top) ||
1169 isRelatedBy(Canonical, False, ICmpInst::ICMP_NE))
1170 add(SI->getCondition(), ConstantBool::getTrue(),
1171 ICmpInst::ICMP_EQ, NewContext);
1172 else if (Canonical == IG.canonicalize(False, Top) ||
1173 isRelatedBy(I, True, ICmpInst::ICMP_NE))
1174 add(SI->getCondition(), ConstantBool::getFalse(),
1175 ICmpInst::ICMP_EQ, NewContext);
1178 // TODO: CastInst "%a = cast ... %b" where %a is EQ or NE a constant.
1181 /// opsToDef - A new relationship was discovered involving one of this
1182 /// instruction's operands. Find any new relationship involving the
1184 void opsToDef(Instruction *I) {
1185 Instruction *NewContext = below(I) ? I : TopInst;
1187 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
1188 Value *Op0 = IG.canonicalize(BO->getOperand(0), Top);
1189 Value *Op1 = IG.canonicalize(BO->getOperand(1), Top);
1191 if (ConstantIntegral *CI0 = dyn_cast<ConstantIntegral>(Op0))
1192 if (ConstantIntegral *CI1 = dyn_cast<ConstantIntegral>(Op1)) {
1193 add(BO, ConstantExpr::get(BO->getOpcode(), CI0, CI1),
1194 ICmpInst::ICMP_EQ, NewContext);
1198 // "%y = and bool true, %x" then %x EQ %y.
1199 // "%y = or bool false, %x" then %x EQ %y.
1200 if (BO->getOpcode() == Instruction::Or) {
1201 Constant *Zero = Constant::getNullValue(BO->getType());
1203 add(BO, Op1, ICmpInst::ICMP_EQ, NewContext);
1205 } else if (Op1 == Zero) {
1206 add(BO, Op0, ICmpInst::ICMP_EQ, NewContext);
1209 } else if (BO->getOpcode() == Instruction::And) {
1210 Constant *AllOnes = ConstantIntegral::getAllOnesValue(BO->getType());
1211 if (Op0 == AllOnes) {
1212 add(BO, Op1, ICmpInst::ICMP_EQ, NewContext);
1214 } else if (Op1 == AllOnes) {
1215 add(BO, Op0, ICmpInst::ICMP_EQ, NewContext);
1220 // "%x = add int %y, %z" and %x EQ %y then %z EQ 0
1221 // "%x = mul int %y, %z" and %x EQ %y then %z EQ 1
1222 // 1. Repeat all of the above, with order of operands reversed.
1223 // "%x = udiv int %y, %z" and %x EQ %y then %z EQ 1
1225 Value *Known = Op0, *Unknown = Op1;
1226 if (Known != BO) std::swap(Known, Unknown);
1228 const Type *Ty = BO->getType();
1229 assert(!Ty->isFPOrFPVector() && "Float in work queue!");
1231 switch (BO->getOpcode()) {
1233 case Instruction::Xor:
1234 case Instruction::Or:
1235 case Instruction::Add:
1236 case Instruction::Sub:
1237 add(Unknown, Constant::getNullValue(Ty), ICmpInst::ICMP_EQ, NewContext);
1239 case Instruction::UDiv:
1240 case Instruction::SDiv:
1241 if (Unknown == Op0) break; // otherwise, fallthrough
1242 case Instruction::And:
1243 case Instruction::Mul:
1244 Constant *One = NULL;
1245 if (isa<ConstantInt>(Unknown))
1246 One = ConstantInt::get(Ty, 1);
1247 else if (isa<ConstantBool>(Unknown))
1248 One = ConstantBool::getTrue();
1250 if (One) add(Unknown, One, ICmpInst::ICMP_EQ, NewContext);
1255 // TODO: "%a = add int %b, 1" and %b > %z then %a >= %z.
1257 } else if (ICmpInst *IC = dyn_cast<ICmpInst>(I)) {
1258 // "%a = icmp ult %b, %c" and %b u< %c then %a EQ true
1259 // "%a = icmp ult %b, %c" and %b u>= %c then %a EQ false
1262 Value *Op0 = IG.canonicalize(IC->getOperand(0), Top);
1263 Value *Op1 = IG.canonicalize(IC->getOperand(1), Top);
1265 ICmpInst::Predicate Pred = IC->getPredicate();
1266 if (isRelatedBy(Op0, Op1, Pred)) {
1267 add(IC, ConstantBool::getTrue(), ICmpInst::ICMP_EQ, NewContext);
1268 } else if (isRelatedBy(Op0, Op1, ICmpInst::getInversePredicate(Pred))) {
1269 add(IC, ConstantBool::getFalse(), ICmpInst::ICMP_EQ, NewContext);
1272 // TODO: make the predicate more strict, if possible.
1274 } else if (SelectInst *SI = dyn_cast<SelectInst>(I)) {
1275 // Given: "%a = select bool %x, int %b, int %c"
1276 // %x EQ true then %a EQ %b
1277 // %x EQ false then %a EQ %c
1278 // %b EQ %c then %a EQ %b
1280 Value *Canonical = IG.canonicalize(SI->getCondition(), Top);
1281 if (Canonical == ConstantBool::getTrue()) {
1282 add(SI, SI->getTrueValue(), ICmpInst::ICMP_EQ, NewContext);
1283 } else if (Canonical == ConstantBool::getFalse()) {
1284 add(SI, SI->getFalseValue(), ICmpInst::ICMP_EQ, NewContext);
1285 } else if (IG.canonicalize(SI->getTrueValue(), Top) ==
1286 IG.canonicalize(SI->getFalseValue(), Top)) {
1287 add(SI, SI->getTrueValue(), ICmpInst::ICMP_EQ, NewContext);
1290 // TODO: CastInst "%a = cast ... %b" where %b is EQ or NE a constant.
1293 /// solve - process the work queue
1294 /// Return false if a logical contradiction occurs.
1296 //DOUT << "WorkList entry, size: " << WorkList.size() << "\n";
1297 while (!WorkList.empty()) {
1298 //DOUT << "WorkList size: " << WorkList.size() << "\n";
1300 Operation &O = WorkList.front();
1302 TopInst = O.Context;
1303 Top = Forest->getNodeForBlock(TopInst->getParent());
1305 O.LHS = IG.canonicalize(O.LHS, Top);
1306 O.RHS = IG.canonicalize(O.RHS, Top);
1308 assert(O.LHS == IG.canonicalize(O.LHS, Top) && "Canonicalize isn't.");
1309 assert(O.RHS == IG.canonicalize(O.RHS, Top) && "Canonicalize isn't.");
1311 DOUT << "solving " << *O.LHS << " " << O.Op << " " << *O.RHS;
1312 if (O.Context) DOUT << " context: " << *O.Context;
1313 else DOUT << " default context";
1318 // TODO: actually check the constants and add to UB.
1319 if (isa<Constant>(O.LHS) && isa<Constant>(O.RHS)) {
1320 WorkList.pop_front();
1324 if (O.Op == ICmpInst::ICMP_EQ) {
1325 if (!makeEqual(O.LHS, O.RHS))
1328 LatticeVal LV = cmpInstToLattice(O.Op);
1330 if ((LV & EQ_BIT) &&
1331 isRelatedBy(O.LHS, O.RHS, ICmpInst::getSwappedPredicate(O.Op))) {
1332 if (!makeEqual(O.LHS, O.RHS))
1335 if (isRelatedBy(O.LHS, O.RHS, ICmpInst::getInversePredicate(O.Op))){
1336 DOUT << "inequality contradiction!\n";
1337 WorkList.pop_front();
1341 unsigned n1 = IG.getOrInsertNode(O.LHS, Top);
1342 unsigned n2 = IG.getOrInsertNode(O.RHS, Top);
1345 if (O.Op != ICmpInst::ICMP_UGE && O.Op != ICmpInst::ICMP_ULE &&
1346 O.Op != ICmpInst::ICMP_SGE && O.Op != ICmpInst::ICMP_SLE)
1349 WorkList.pop_front();
1353 if (IG.isRelatedBy(n1, n2, Top, LV)) {
1354 WorkList.pop_front();
1358 IG.addInequality(n1, n2, Top, LV);
1360 if (Instruction *I1 = dyn_cast<Instruction>(O.LHS)) defToOps(I1);
1361 if (isa<Instruction>(O.LHS) || isa<Argument>(O.LHS)) {
1362 for (Value::use_iterator UI = O.LHS->use_begin(),
1363 UE = O.LHS->use_end(); UI != UE;) {
1364 Use &TheUse = UI.getUse();
1366 if (Instruction *I = dyn_cast<Instruction>(TheUse.getUser())) {
1371 if (Instruction *I2 = dyn_cast<Instruction>(O.RHS)) defToOps(I2);
1372 if (isa<Instruction>(O.RHS) || isa<Argument>(O.RHS)) {
1373 for (Value::use_iterator UI = O.RHS->use_begin(),
1374 UE = O.RHS->use_end(); UI != UE;) {
1375 Use &TheUse = UI.getUse();
1377 if (Instruction *I = dyn_cast<Instruction>(TheUse.getUser())) {
1384 WorkList.pop_front();
1389 /// PredicateSimplifier - This class is a simplifier that replaces
1390 /// one equivalent variable with another. It also tracks what
1391 /// can't be equal and will solve setcc instructions when possible.
1392 /// @brief Root of the predicate simplifier optimization.
1393 class VISIBILITY_HIDDEN PredicateSimplifier : public FunctionPass {
1397 InequalityGraph *IG;
1398 UnreachableBlocks UB;
1400 std::vector<DominatorTree::Node *> WorkList;
1403 bool runOnFunction(Function &F);
1405 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
1406 AU.addRequiredID(BreakCriticalEdgesID);
1407 AU.addRequired<DominatorTree>();
1408 AU.addRequired<ETForest>();
1412 /// Forwards - Adds new properties into PropertySet and uses them to
1413 /// simplify instructions. Because new properties sometimes apply to
1414 /// a transition from one BasicBlock to another, this will use the
1415 /// PredicateSimplifier::proceedToSuccessor(s) interface to enter the
1416 /// basic block with the new PropertySet.
1417 /// @brief Performs abstract execution of the program.
1418 class VISIBILITY_HIDDEN Forwards : public InstVisitor<Forwards> {
1419 friend class InstVisitor<Forwards>;
1420 PredicateSimplifier *PS;
1421 DominatorTree::Node *DTNode;
1424 InequalityGraph &IG;
1425 UnreachableBlocks &UB;
1427 Forwards(PredicateSimplifier *PS, DominatorTree::Node *DTNode)
1428 : PS(PS), DTNode(DTNode), IG(*PS->IG), UB(PS->UB) {}
1430 void visitTerminatorInst(TerminatorInst &TI);
1431 void visitBranchInst(BranchInst &BI);
1432 void visitSwitchInst(SwitchInst &SI);
1434 void visitAllocaInst(AllocaInst &AI);
1435 void visitLoadInst(LoadInst &LI);
1436 void visitStoreInst(StoreInst &SI);
1438 void visitBinaryOperator(BinaryOperator &BO);
1441 // Used by terminator instructions to proceed from the current basic
1442 // block to the next. Verifies that "current" dominates "next",
1443 // then calls visitBasicBlock.
1444 void proceedToSuccessors(DominatorTree::Node *Current) {
1445 for (DominatorTree::Node::iterator I = Current->begin(),
1446 E = Current->end(); I != E; ++I) {
1447 WorkList.push_back(*I);
1451 void proceedToSuccessor(DominatorTree::Node *Next) {
1452 WorkList.push_back(Next);
1455 // Visits each instruction in the basic block.
1456 void visitBasicBlock(DominatorTree::Node *Node) {
1457 BasicBlock *BB = Node->getBlock();
1458 ETNode *ET = Forest->getNodeForBlock(BB);
1459 DOUT << "Entering Basic Block: " << BB->getName() << " (" << ET << ")\n";
1460 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
1461 visitInstruction(I++, Node, ET);
1465 // Tries to simplify each Instruction and add new properties to
1467 void visitInstruction(Instruction *I, DominatorTree::Node *DT, ETNode *ET) {
1468 DOUT << "Considering instruction " << *I << "\n";
1471 // Sometimes instructions are killed in earlier analysis.
1472 if (isInstructionTriviallyDead(I)) {
1476 I->eraseFromParent();
1480 // Try to replace the whole instruction.
1481 Value *V = IG->canonicalize(I, ET);
1482 assert(V == I && "Late instruction canonicalization.");
1486 DOUT << "Removing " << *I << ", replacing with " << *V << "\n";
1488 I->replaceAllUsesWith(V);
1489 I->eraseFromParent();
1493 // Try to substitute operands.
1494 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
1495 Value *Oper = I->getOperand(i);
1496 Value *V = IG->canonicalize(Oper, ET);
1497 assert(V == Oper && "Late operand canonicalization.");
1501 DOUT << "Resolving " << *I;
1502 I->setOperand(i, V);
1503 DOUT << " into " << *I;
1507 DOUT << "push (%" << I->getParent()->getName() << ")\n";
1508 Forwards visit(this, DT);
1510 DOUT << "pop (%" << I->getParent()->getName() << ")\n";
1514 bool PredicateSimplifier::runOnFunction(Function &F) {
1515 DT = &getAnalysis<DominatorTree>();
1516 Forest = &getAnalysis<ETForest>();
1518 Forest->updateDFSNumbers(); // XXX: should only act when numbers are out of date
1520 DOUT << "Entering Function: " << F.getName() << "\n";
1523 BasicBlock *RootBlock = &F.getEntryBlock();
1524 IG = new InequalityGraph(Forest->getNodeForBlock(RootBlock));
1525 WorkList.push_back(DT->getRootNode());
1528 DominatorTree::Node *DTNode = WorkList.back();
1529 WorkList.pop_back();
1530 if (!UB.isDead(DTNode->getBlock())) visitBasicBlock(DTNode);
1531 } while (!WorkList.empty());
1535 modified |= UB.kill();
1540 void PredicateSimplifier::Forwards::visitTerminatorInst(TerminatorInst &TI) {
1541 PS->proceedToSuccessors(DTNode);
1544 void PredicateSimplifier::Forwards::visitBranchInst(BranchInst &BI) {
1545 if (BI.isUnconditional()) {
1546 PS->proceedToSuccessors(DTNode);
1550 Value *Condition = BI.getCondition();
1551 BasicBlock *TrueDest = BI.getSuccessor(0);
1552 BasicBlock *FalseDest = BI.getSuccessor(1);
1554 if (isa<Constant>(Condition) || TrueDest == FalseDest) {
1555 PS->proceedToSuccessors(DTNode);
1559 for (DominatorTree::Node::iterator I = DTNode->begin(), E = DTNode->end();
1561 BasicBlock *Dest = (*I)->getBlock();
1562 DOUT << "Branch thinking about %" << Dest->getName()
1563 << "(" << PS->Forest->getNodeForBlock(Dest) << ")\n";
1565 if (Dest == TrueDest) {
1566 DOUT << "(" << DTNode->getBlock()->getName() << ") true set:\n";
1567 VRPSolver VRP(IG, UB, PS->Forest, PS->modified, Dest);
1568 VRP.add(ConstantBool::getTrue(), Condition, ICmpInst::ICMP_EQ);
1571 } else if (Dest == FalseDest) {
1572 DOUT << "(" << DTNode->getBlock()->getName() << ") false set:\n";
1573 VRPSolver VRP(IG, UB, PS->Forest, PS->modified, Dest);
1574 VRP.add(ConstantBool::getFalse(), Condition, ICmpInst::ICMP_EQ);
1579 PS->proceedToSuccessor(*I);
1583 void PredicateSimplifier::Forwards::visitSwitchInst(SwitchInst &SI) {
1584 Value *Condition = SI.getCondition();
1586 // Set the EQProperty in each of the cases BBs, and the NEProperties
1587 // in the default BB.
1589 for (DominatorTree::Node::iterator I = DTNode->begin(), E = DTNode->end();
1591 BasicBlock *BB = (*I)->getBlock();
1592 DOUT << "Switch thinking about BB %" << BB->getName()
1593 << "(" << PS->Forest->getNodeForBlock(BB) << ")\n";
1595 VRPSolver VRP(IG, UB, PS->Forest, PS->modified, BB);
1596 if (BB == SI.getDefaultDest()) {
1597 for (unsigned i = 1, e = SI.getNumCases(); i < e; ++i)
1598 if (SI.getSuccessor(i) != BB)
1599 VRP.add(Condition, SI.getCaseValue(i), ICmpInst::ICMP_NE);
1601 } else if (ConstantInt *CI = SI.findCaseDest(BB)) {
1602 VRP.add(Condition, CI, ICmpInst::ICMP_EQ);
1605 PS->proceedToSuccessor(*I);
1609 void PredicateSimplifier::Forwards::visitAllocaInst(AllocaInst &AI) {
1610 VRPSolver VRP(IG, UB, PS->Forest, PS->modified, &AI);
1611 VRP.add(Constant::getNullValue(AI.getType()), &AI, ICmpInst::ICMP_NE);
1615 void PredicateSimplifier::Forwards::visitLoadInst(LoadInst &LI) {
1616 Value *Ptr = LI.getPointerOperand();
1617 // avoid "load uint* null" -> null NE null.
1618 if (isa<Constant>(Ptr)) return;
1620 VRPSolver VRP(IG, UB, PS->Forest, PS->modified, &LI);
1621 VRP.add(Constant::getNullValue(Ptr->getType()), Ptr, ICmpInst::ICMP_NE);
1625 void PredicateSimplifier::Forwards::visitStoreInst(StoreInst &SI) {
1626 Value *Ptr = SI.getPointerOperand();
1627 if (isa<Constant>(Ptr)) return;
1629 VRPSolver VRP(IG, UB, PS->Forest, PS->modified, &SI);
1630 VRP.add(Constant::getNullValue(Ptr->getType()), Ptr, ICmpInst::ICMP_NE);
1634 void PredicateSimplifier::Forwards::visitBinaryOperator(BinaryOperator &BO) {
1635 Instruction::BinaryOps ops = BO.getOpcode();
1638 case Instruction::URem:
1639 case Instruction::SRem:
1640 case Instruction::UDiv:
1641 case Instruction::SDiv: {
1642 Value *Divisor = BO.getOperand(1);
1643 VRPSolver VRP(IG, UB, PS->Forest, PS->modified, &BO);
1644 VRP.add(Constant::getNullValue(Divisor->getType()), Divisor,
1654 RegisterPass<PredicateSimplifier> X("predsimplify",
1655 "Predicate Simplifier");
1658 FunctionPass *llvm::createPredicateSimplifierPass() {
1659 return new PredicateSimplifier();