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 = icmp ne int* %ptr, null
56 // %a = and 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 "and" 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/SetVector.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 -- SGT 14
106 // 0 1 1 1 1 -- SGE 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 -- SLT 22
112 // 1 0 1 1 1 -- SLE 23
113 // 1 1 0 1 0 -- UGT 26
114 // 1 1 0 1 1 -- UGE 27
115 // 1 1 1 0 0 -- ULT 28
116 // 1 1 1 0 1 -- ULE 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 ULT = SLT_BIT | SGT_BIT | ULT_BIT,
132 UGT = SLT_BIT | SGT_BIT | UGT_BIT,
133 SLT = SLT_BIT | ULT_BIT | UGT_BIT,
134 SGT = SGT_BIT | ULT_BIT | UGT_BIT,
141 static bool validPredicate(LatticeVal LV) {
143 case GT: case GE: case LT: case LE: case NE:
144 case SGTULT: case SGT: case SGEULE:
145 case SLTUGT: case SLT: case SLEUGE:
147 case SLE: case SGE: case ULE: case UGE:
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->getDFSNumIn() << ")\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) {
317 assert(Subtree->DominatedBy(I->Subtree) &&
318 "Find returned subtree that doesn't apply.");
320 Edge edge(n, R, Subtree);
321 iterator Insert = std::lower_bound(begin(), end(), edge);
322 Relations.insert(Insert, edge); // invalidates I
323 I = find(n, Subtree);
326 // Also, we have to tighten any edge that Subtree dominates.
327 for (iterator B = begin(); I->To == n; --I) {
328 if (I->Subtree->DominatedBy(Subtree)) {
329 LatticeVal LV = static_cast<LatticeVal>(I->LV & R);
330 assert(validPredicate(LV) && "Invalid union of lattice values.");
341 struct VISIBILITY_HIDDEN NodeMapEdge {
346 NodeMapEdge(Value *V, unsigned index, ETNode *Subtree)
347 : V(V), index(index), Subtree(Subtree) {}
349 bool operator==(const NodeMapEdge &RHS) const {
351 Subtree == RHS.Subtree;
354 bool operator<(const NodeMapEdge &RHS) const {
355 if (V != RHS.V) return V < RHS.V;
356 return OrderByDominance()(Subtree, RHS.Subtree);
359 bool operator<(Value *RHS) const {
364 typedef std::vector<NodeMapEdge> NodeMapType;
367 std::vector<Node> Nodes;
369 std::vector<std::pair<ConstantInt *, unsigned> > Ints;
371 /// This is used to keep the ConstantInts list in unsigned ascending order.
372 /// If the bitwidths don't match, this sorts smaller values ahead.
374 bool operator()(const std::pair<ConstantInt *, unsigned> &LHS,
375 const std::pair<ConstantInt *, unsigned> &RHS) const {
376 if (LHS.first->getType()->getBitWidth() !=
377 RHS.first->getType()->getBitWidth())
378 return LHS.first->getType()->getBitWidth() <
379 RHS.first->getType()->getBitWidth();
380 return LHS.first->getValue().ult(RHS.first->getValue());
384 /// True when the bitwidth of LHS < bitwidth of RHS.
385 struct FindByIntegerWidth {
386 bool operator()(const std::pair<ConstantInt *, unsigned> &LHS,
387 const std::pair<ConstantInt *, unsigned> &RHS) const {
388 return LHS.first->getType()->getBitWidth() <
389 RHS.first->getType()->getBitWidth();
393 void initializeInt(ConstantInt *CI, unsigned index) {
394 std::vector<std::pair<ConstantInt *, unsigned> >::iterator begin, end,
395 last, iULT, iUGT, iSLT, iSGT;
397 std::pair<ConstantInt *, unsigned> pair = std::make_pair(CI, index);
399 begin = std::lower_bound(Ints.begin(), Ints.end(), pair,
400 FindByIntegerWidth());
401 end = std::upper_bound(begin, Ints.end(), pair, FindByIntegerWidth());
403 if (begin == end) last = end;
406 iUGT = std::lower_bound(begin, end, pair, SortByZExt());
407 iULT = (iUGT == begin || begin == end) ? end : iUGT - 1;
409 if (iUGT != end && iULT != end &&
410 iULT->first->getValue().isNegative() ==
411 iUGT->first->getValue().isNegative()) { // signs match
415 if (iULT == end || iUGT == end) {
416 if (iULT == end) iSLT = last; else iSLT = iULT;
417 if (iUGT == end) iSGT = begin; else iSGT = iUGT;
418 } else if (iULT->first->getValue().isNegative()) {
419 assert(iUGT->first->getValue().isPositive() &&
420 "Bad sign comparison.");
424 assert(iULT->first->getValue().isPositive() >= 0 &&
425 iUGT->first->getValue().isNegative() &&"Bad sign comparison.");
431 iSGT->first->getValue().slt(CI->getValue()))
434 iSLT->first->getValue().sgt(CI->getValue()))
438 if (begin->first->getValue().slt(CI->getValue()))
440 begin->first->getValue().sgt(iSLT->first->getValue()))
444 if (last->first->getValue().sgt(CI->getValue()))
446 last->first->getValue().slt(iSGT->first->getValue()))
451 if (iULT != end) addInequality(iULT->second, index, TreeRoot, ULT);
452 if (iUGT != end) addInequality(iUGT->second, index, TreeRoot, UGT);
453 if (iSLT != end) addInequality(iSLT->second, index, TreeRoot, SLT);
454 if (iSGT != end) addInequality(iSGT->second, index, TreeRoot, SGT);
456 Ints.insert(iUGT, pair);
460 /// node - returns the node object at a given index retrieved from getNode.
461 /// Index zero is reserved and may not be passed in here. The pointer
462 /// returned is valid until the next call to newNode or getOrInsertNode.
463 Node *node(unsigned index) {
464 assert(index != 0 && "Zero index is reserved for not found.");
465 assert(index <= Nodes.size() && "Index out of range.");
466 return &Nodes[index-1];
469 /// Returns the node currently representing Value V, or zero if no such
471 unsigned getNode(Value *V, ETNode *Subtree) {
472 NodeMapType::iterator E = NodeMap.end();
473 NodeMapEdge Edge(V, 0, Subtree);
474 NodeMapType::iterator I = std::lower_bound(NodeMap.begin(), E, Edge);
475 while (I != E && I->V == V) {
476 if (Subtree->DominatedBy(I->Subtree))
483 /// getOrInsertNode - always returns a valid node index, creating a node
484 /// to match the Value if needed.
485 unsigned getOrInsertNode(Value *V, ETNode *Subtree) {
486 if (unsigned n = getNode(V, Subtree))
492 /// newNode - creates a new node for a given Value and returns the index.
493 unsigned newNode(Value *V) {
494 Nodes.push_back(Node(V));
496 NodeMapEdge MapEntry = NodeMapEdge(V, Nodes.size(), TreeRoot);
497 assert(!std::binary_search(NodeMap.begin(), NodeMap.end(), MapEntry) &&
498 "Attempt to create a duplicate Node.");
499 NodeMap.insert(std::lower_bound(NodeMap.begin(), NodeMap.end(),
500 MapEntry), MapEntry);
502 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
503 initializeInt(CI, MapEntry.index);
505 return MapEntry.index;
508 /// If the Value is in the graph, return the canonical form. Otherwise,
509 /// return the original Value.
510 Value *canonicalize(Value *V, ETNode *Subtree) {
511 if (isa<Constant>(V)) return V;
513 if (unsigned n = getNode(V, Subtree))
514 return node(n)->getValue();
519 /// isRelatedBy - true iff n1 op n2
520 bool isRelatedBy(unsigned n1, unsigned n2, ETNode *Subtree, LatticeVal LV) {
521 if (n1 == n2) return LV & EQ_BIT;
524 Node::iterator I = N1->find(n2, Subtree), E = N1->end();
525 if (I != E) return (I->LV & LV) == I->LV;
530 // The add* methods assume that your input is logically valid and may
531 // assertion-fail or infinitely loop if you attempt a contradiction.
533 void addEquality(unsigned n, Value *V, ETNode *Subtree) {
534 assert(canonicalize(node(n)->getValue(), Subtree) == node(n)->getValue()
535 && "Node's 'canonical' choice isn't best within this subtree.");
537 // Suppose that we are given "%x -> node #1 (%y)". The problem is that
538 // we may already have "%z -> node #2 (%x)" somewhere above us in the
539 // graph. We need to find those edges and add "%z -> node #1 (%y)"
540 // to keep the lookups canonical.
542 std::vector<Value *> ToRepoint;
543 ToRepoint.push_back(V);
545 if (unsigned Conflict = getNode(V, Subtree)) {
546 // XXX: NodeMap.size() exceeds 68,000 entries compiling kimwitu++!
547 for (NodeMapType::iterator I = NodeMap.begin(), E = NodeMap.end();
549 if (I->index == Conflict && Subtree->DominatedBy(I->Subtree))
550 ToRepoint.push_back(I->V);
554 for (std::vector<Value *>::iterator VI = ToRepoint.begin(),
555 VE = ToRepoint.end(); VI != VE; ++VI) {
558 // XXX: review this code. This may be doing too many insertions.
559 NodeMapEdge Edge(V, n, Subtree);
560 NodeMapType::iterator E = NodeMap.end();
561 NodeMapType::iterator I = std::lower_bound(NodeMap.begin(), E, Edge);
562 if (I == E || I->V != V || I->Subtree != Subtree) {
564 NodeMap.insert(I, Edge);
565 } else if (I != E && I->V == V && I->Subtree == Subtree) {
566 // Update best choice
572 if (isa<Constant>(V)) {
573 if (isa<Constant>(N->getValue())) {
574 assert(V == N->getValue() && "Constant equals different constant?");
581 /// addInequality - Sets n1 op n2.
582 /// It is also an error to call this on an inequality that is already true.
583 void addInequality(unsigned n1, unsigned n2, ETNode *Subtree,
585 assert(n1 != n2 && "A node can't be inequal to itself.");
588 assert(!isRelatedBy(n1, n2, Subtree, reversePredicate(LV1)) &&
589 "Contradictory inequality.");
594 // Suppose we're adding %n1 < %n2. Find all the %a < %n1 and
595 // add %a < %n2 too. This keeps the graph fully connected.
597 // Someone with a head for this sort of logic, please review this.
598 // Given that %x SLTUGT %y and %a SLE %x, what is the relationship
599 // between %a and %y? I believe the below code is correct, but I don't
600 // think it's the most efficient solution.
602 unsigned LV1_s = LV1 & (SLT_BIT|SGT_BIT);
603 unsigned LV1_u = LV1 & (ULT_BIT|UGT_BIT);
604 for (Node::iterator I = N1->begin(), E = N1->end(); I != E; ++I) {
605 if (I->LV != NE && I->To != n2) {
606 ETNode *Local_Subtree = NULL;
607 if (Subtree->DominatedBy(I->Subtree))
608 Local_Subtree = Subtree;
609 else if (I->Subtree->DominatedBy(Subtree))
610 Local_Subtree = I->Subtree;
613 unsigned new_relationship = 0;
614 LatticeVal ILV = reversePredicate(I->LV);
615 unsigned ILV_s = ILV & (SLT_BIT|SGT_BIT);
616 unsigned ILV_u = ILV & (ULT_BIT|UGT_BIT);
618 if (LV1_s != (SLT_BIT|SGT_BIT) && ILV_s == LV1_s)
619 new_relationship |= ILV_s;
621 if (LV1_u != (ULT_BIT|UGT_BIT) && ILV_u == LV1_u)
622 new_relationship |= ILV_u;
624 if (new_relationship) {
625 if ((new_relationship & (SLT_BIT|SGT_BIT)) == 0)
626 new_relationship |= (SLT_BIT|SGT_BIT);
627 if ((new_relationship & (ULT_BIT|UGT_BIT)) == 0)
628 new_relationship |= (ULT_BIT|UGT_BIT);
629 if ((LV1 & EQ_BIT) && (ILV & EQ_BIT))
630 new_relationship |= EQ_BIT;
632 LatticeVal NewLV = static_cast<LatticeVal>(new_relationship);
634 node(I->To)->update(n2, NewLV, Local_Subtree);
635 N2->update(I->To, reversePredicate(NewLV), Local_Subtree);
641 for (Node::iterator I = N2->begin(), E = N2->end(); I != E; ++I) {
642 if (I->LV != NE && I->To != n1) {
643 ETNode *Local_Subtree = NULL;
644 if (Subtree->DominatedBy(I->Subtree))
645 Local_Subtree = Subtree;
646 else if (I->Subtree->DominatedBy(Subtree))
647 Local_Subtree = I->Subtree;
650 unsigned new_relationship = 0;
651 unsigned ILV_s = I->LV & (SLT_BIT|SGT_BIT);
652 unsigned ILV_u = I->LV & (ULT_BIT|UGT_BIT);
654 if (LV1_s != (SLT_BIT|SGT_BIT) && ILV_s == LV1_s)
655 new_relationship |= ILV_s;
657 if (LV1_u != (ULT_BIT|UGT_BIT) && ILV_u == LV1_u)
658 new_relationship |= ILV_u;
660 if (new_relationship) {
661 if ((new_relationship & (SLT_BIT|SGT_BIT)) == 0)
662 new_relationship |= (SLT_BIT|SGT_BIT);
663 if ((new_relationship & (ULT_BIT|UGT_BIT)) == 0)
664 new_relationship |= (ULT_BIT|UGT_BIT);
665 if ((LV1 & EQ_BIT) && (I->LV & EQ_BIT))
666 new_relationship |= EQ_BIT;
668 LatticeVal NewLV = static_cast<LatticeVal>(new_relationship);
670 N1->update(I->To, NewLV, Local_Subtree);
671 node(I->To)->update(n1, reversePredicate(NewLV), Local_Subtree);
678 N1->update(n2, LV1, Subtree);
679 N2->update(n1, reversePredicate(LV1), Subtree);
682 /// Removes a Value from the graph, but does not delete any nodes. As this
683 /// method does not delete Nodes, V may not be the canonical choice for
684 /// a node with any relationships. It is invalid to call newNode on a Value
685 /// that has been removed.
686 void remove(Value *V) {
687 for (unsigned i = 0; i < NodeMap.size();) {
688 NodeMapType::iterator I = NodeMap.begin()+i;
689 assert((node(I->index)->getValue() != V || node(I->index)->begin() ==
690 node(I->index)->end()) && "Tried to delete in-use node.");
693 if (node(I->index)->getValue() == V)
694 node(I->index)->Canonical = NULL;
702 virtual ~InequalityGraph() {}
703 virtual void dump() {
704 dump(*cerr.stream());
707 void dump(std::ostream &os) {
708 std::set<Node *> VisitedNodes;
709 for (NodeMapType::const_iterator I = NodeMap.begin(), E = NodeMap.end();
711 Node *N = node(I->index);
712 os << *I->V << " == " << I->index
713 << "(" << I->Subtree->getDFSNumIn() << ")\n";
714 if (VisitedNodes.insert(N).second) {
715 os << I->index << ". ";
716 if (!N->getValue()) os << "(deleted node)\n";
724 /// UnreachableBlocks keeps tracks of blocks that are for one reason or
725 /// another discovered to be unreachable. This is used to cull the graph when
726 /// analyzing instructions, and to mark blocks with the "unreachable"
727 /// terminator instruction after the function has executed.
728 class VISIBILITY_HIDDEN UnreachableBlocks {
730 std::vector<BasicBlock *> DeadBlocks;
733 /// mark - mark a block as dead
734 void mark(BasicBlock *BB) {
735 std::vector<BasicBlock *>::iterator E = DeadBlocks.end();
736 std::vector<BasicBlock *>::iterator I =
737 std::lower_bound(DeadBlocks.begin(), E, BB);
739 if (I == E || *I != BB) DeadBlocks.insert(I, BB);
742 /// isDead - returns whether a block is known to be dead already
743 bool isDead(BasicBlock *BB) {
744 std::vector<BasicBlock *>::iterator E = DeadBlocks.end();
745 std::vector<BasicBlock *>::iterator I =
746 std::lower_bound(DeadBlocks.begin(), E, BB);
748 return I != E && *I == BB;
751 /// kill - replace the dead blocks' terminator with an UnreachableInst.
753 bool modified = false;
754 for (std::vector<BasicBlock *>::iterator I = DeadBlocks.begin(),
755 E = DeadBlocks.end(); I != E; ++I) {
758 DOUT << "unreachable block: " << BB->getName() << "\n";
760 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB);
762 BasicBlock *Succ = *SI;
763 Succ->removePredecessor(BB);
766 TerminatorInst *TI = BB->getTerminator();
767 TI->replaceAllUsesWith(UndefValue::get(TI->getType()));
768 TI->eraseFromParent();
769 new UnreachableInst(BB);
778 /// VRPSolver keeps track of how changes to one variable affect other
779 /// variables, and forwards changes along to the InequalityGraph. It
780 /// also maintains the correct choice for "canonical" in the IG.
781 /// @brief VRPSolver calculates inferences from a new relationship.
782 class VISIBILITY_HIDDEN VRPSolver {
786 ICmpInst::Predicate Op;
788 BasicBlock *ContextBB;
789 Instruction *ContextInst;
791 std::deque<Operation> WorkList;
794 UnreachableBlocks &UB;
798 Instruction *TopInst;
801 typedef InequalityGraph::Node Node;
803 /// IdomI - Determines whether one Instruction dominates another.
804 bool IdomI(Instruction *I1, Instruction *I2) const {
805 BasicBlock *BB1 = I1->getParent(),
806 *BB2 = I2->getParent();
808 if (isa<TerminatorInst>(I1)) return false;
809 if (isa<TerminatorInst>(I2)) return true;
810 if (isa<PHINode>(I1) && !isa<PHINode>(I2)) return true;
811 if (!isa<PHINode>(I1) && isa<PHINode>(I2)) return false;
813 for (BasicBlock::const_iterator I = BB1->begin(), E = BB1->end();
815 if (&*I == I1) return true;
816 if (&*I == I2) return false;
818 assert(!"Instructions not found in parent BasicBlock?");
820 return Forest->properlyDominates(BB1, BB2);
825 /// Returns true if V1 is a better canonical value than V2.
826 bool compare(Value *V1, Value *V2) const {
827 if (isa<Constant>(V1))
828 return !isa<Constant>(V2);
829 else if (isa<Constant>(V2))
831 else if (isa<Argument>(V1))
832 return !isa<Argument>(V2);
833 else if (isa<Argument>(V2))
836 Instruction *I1 = dyn_cast<Instruction>(V1);
837 Instruction *I2 = dyn_cast<Instruction>(V2);
840 return V1->getNumUses() < V2->getNumUses();
842 return IdomI(I1, I2);
845 // below - true if the Instruction is dominated by the current context
846 // block or instruction
847 bool below(Instruction *I) {
849 return IdomI(TopInst, I);
851 ETNode *Node = Forest->getNodeForBlock(I->getParent());
852 return Node->DominatedBy(Top);
856 bool makeEqual(Value *V1, Value *V2) {
857 DOUT << "makeEqual(" << *V1 << ", " << *V2 << ")\n";
859 if (V1 == V2) return true;
861 if (isa<Constant>(V1) && isa<Constant>(V2))
864 unsigned n1 = IG.getNode(V1, Top), n2 = IG.getNode(V2, Top);
867 if (n1 == n2) return true;
868 if (IG.isRelatedBy(n1, n2, Top, NE)) return false;
871 if (n1) assert(V1 == IG.node(n1)->getValue() && "Value isn't canonical.");
872 if (n2) assert(V2 == IG.node(n2)->getValue() && "Value isn't canonical.");
874 assert(!compare(V2, V1) && "Please order parameters to makeEqual.");
876 assert(!isa<Constant>(V2) && "Tried to remove a constant.");
878 SetVector<unsigned> Remove;
879 if (n2) Remove.insert(n2);
882 // Suppose we're being told that %x == %y, and %x <= %z and %y >= %z.
883 // We can't just merge %x and %y because the relationship with %z would
884 // be EQ and that's invalid. What we're doing is looking for any nodes
885 // %z such that %x <= %z and %y >= %z, and vice versa.
887 Node *N1 = IG.node(n1);
888 Node *N2 = IG.node(n2);
889 Node::iterator end = N2->end();
891 // Find the intersection between N1 and N2 which is dominated by
892 // Top. If we find %x where N1 <= %x <= N2 (or >=) then add %x to
894 for (Node::iterator I = N1->begin(), E = N1->end(); I != E; ++I) {
895 if (!(I->LV & EQ_BIT) || !Top->DominatedBy(I->Subtree)) continue;
897 unsigned ILV_s = I->LV & (SLT_BIT|SGT_BIT);
898 unsigned ILV_u = I->LV & (ULT_BIT|UGT_BIT);
899 Node::iterator NI = N2->find(I->To, Top);
901 LatticeVal NILV = reversePredicate(NI->LV);
902 unsigned NILV_s = NILV & (SLT_BIT|SGT_BIT);
903 unsigned NILV_u = NILV & (ULT_BIT|UGT_BIT);
905 if ((ILV_s != (SLT_BIT|SGT_BIT) && ILV_s == NILV_s) ||
906 (ILV_u != (ULT_BIT|UGT_BIT) && ILV_u == NILV_u))
907 Remove.insert(I->To);
911 // See if one of the nodes about to be removed is actually a better
912 // canonical choice than n1.
913 unsigned orig_n1 = n1;
914 SetVector<unsigned>::iterator DontRemove = Remove.end();
915 for (SetVector<unsigned>::iterator I = Remove.begin()+1 /* skip n2 */,
916 E = Remove.end(); I != E; ++I) {
918 Value *V = IG.node(n)->getValue();
919 if (compare(V, V1)) {
925 if (DontRemove != Remove.end()) {
926 unsigned n = *DontRemove;
928 Remove.insert(orig_n1);
932 // We'd like to allow makeEqual on two values to perform a simple
933 // substitution without every creating nodes in the IG whenever possible.
935 // The first iteration through this loop operates on V2 before going
936 // through the Remove list and operating on those too. If all of the
937 // iterations performed simple replacements then we exit early.
938 bool exitEarly = true;
940 for (Value *R = V2; i == 0 || i < Remove.size(); ++i) {
941 if (i) R = IG.node(Remove[i])->getValue(); // skip n2.
943 // Try to replace the whole instruction. If we can, we're done.
944 Instruction *I2 = dyn_cast<Instruction>(R);
945 if (I2 && below(I2)) {
946 std::vector<Instruction *> ToNotify;
947 for (Value::use_iterator UI = R->use_begin(), UE = R->use_end();
949 Use &TheUse = UI.getUse();
951 if (Instruction *I = dyn_cast<Instruction>(TheUse.getUser()))
952 ToNotify.push_back(I);
955 DOUT << "Simply removing " << *I2
956 << ", replacing with " << *V1 << "\n";
957 I2->replaceAllUsesWith(V1);
958 // leave it dead; it'll get erased later.
962 for (std::vector<Instruction *>::iterator II = ToNotify.begin(),
963 IE = ToNotify.end(); II != IE; ++II) {
970 // Otherwise, replace all dominated uses.
971 for (Value::use_iterator UI = R->use_begin(), UE = R->use_end();
973 Use &TheUse = UI.getUse();
975 if (Instruction *I = dyn_cast<Instruction>(TheUse.getUser())) {
985 // If that killed the instruction, stop here.
986 if (I2 && isInstructionTriviallyDead(I2)) {
987 DOUT << "Killed all uses of " << *I2
988 << ", replacing with " << *V1 << "\n";
992 // If we make it to here, then we will need to create a node for N1.
993 // Otherwise, we can skip out early!
997 if (exitEarly) return true;
1000 // XXX: this should call newNode, but instead the node might be created
1001 // in isRelatedBy. That's also a fixme.
1003 n1 = IG.getOrInsertNode(V1, Top);
1005 if (isa<ConstantInt>(V1))
1006 if (IG.isRelatedBy(n1, n2, Top, NE)) return false;
1009 // Migrate relationships from removed nodes to N1.
1010 Node *N1 = IG.node(n1);
1011 for (SetVector<unsigned>::iterator I = Remove.begin(), E = Remove.end();
1014 Node *N = IG.node(n);
1015 for (Node::iterator NI = N->begin(), NE = N->end(); NI != NE; ++NI) {
1016 if (NI->Subtree->DominatedBy(Top)) {
1018 assert((NI->LV & EQ_BIT) && "Node inequal to itself.");
1021 if (Remove.count(NI->To))
1024 IG.node(NI->To)->update(n1, reversePredicate(NI->LV), Top);
1025 N1->update(NI->To, NI->LV, Top);
1030 // Point V2 (and all items in Remove) to N1.
1032 IG.addEquality(n1, V2, Top);
1034 for (SetVector<unsigned>::iterator I = Remove.begin(),
1035 E = Remove.end(); I != E; ++I) {
1036 IG.addEquality(n1, IG.node(*I)->getValue(), Top);
1040 // If !Remove.empty() then V2 = Remove[0]->getValue().
1041 // Even when Remove is empty, we still want to process V2.
1043 for (Value *R = V2; i == 0 || i < Remove.size(); ++i) {
1044 if (i) R = IG.node(Remove[i])->getValue(); // skip n2.
1046 if (Instruction *I2 = dyn_cast<Instruction>(R)) {
1048 Top->DominatedBy(Forest->getNodeForBlock(I2->getParent())))
1051 for (Value::use_iterator UI = V2->use_begin(), UE = V2->use_end();
1053 Use &TheUse = UI.getUse();
1055 if (Instruction *I = dyn_cast<Instruction>(TheUse.getUser())) {
1057 Top->DominatedBy(Forest->getNodeForBlock(I->getParent())))
1066 /// cmpInstToLattice - converts an CmpInst::Predicate to lattice value
1067 /// Requires that the lattice value be valid; does not accept ICMP_EQ.
1068 static LatticeVal cmpInstToLattice(ICmpInst::Predicate Pred) {
1070 case ICmpInst::ICMP_EQ:
1071 assert(!"No matching lattice value.");
1072 return static_cast<LatticeVal>(EQ_BIT);
1074 assert(!"Invalid 'icmp' predicate.");
1075 case ICmpInst::ICMP_NE:
1077 case ICmpInst::ICMP_UGT:
1079 case ICmpInst::ICMP_UGE:
1081 case ICmpInst::ICMP_ULT:
1083 case ICmpInst::ICMP_ULE:
1085 case ICmpInst::ICMP_SGT:
1087 case ICmpInst::ICMP_SGE:
1089 case ICmpInst::ICMP_SLT:
1091 case ICmpInst::ICMP_SLE:
1097 VRPSolver(InequalityGraph &IG, UnreachableBlocks &UB, ETForest *Forest,
1098 bool &modified, BasicBlock *TopBB)
1102 Top(Forest->getNodeForBlock(TopBB)),
1105 modified(modified) {}
1107 VRPSolver(InequalityGraph &IG, UnreachableBlocks &UB, ETForest *Forest,
1108 bool &modified, Instruction *TopInst)
1115 TopBB = TopInst->getParent();
1116 Top = Forest->getNodeForBlock(TopBB);
1119 bool isRelatedBy(Value *V1, Value *V2, ICmpInst::Predicate Pred) const {
1120 if (Constant *C1 = dyn_cast<Constant>(V1))
1121 if (Constant *C2 = dyn_cast<Constant>(V2))
1122 return ConstantExpr::getCompare(Pred, C1, C2) ==
1123 ConstantInt::getTrue();
1125 // XXX: this is lousy. If we're passed a Constant, then we might miss
1126 // some relationships if it isn't in the IG because the relationships
1127 // added by initializeConstant are missing.
1128 if (isa<Constant>(V1)) IG.getOrInsertNode(V1, Top);
1129 if (isa<Constant>(V2)) IG.getOrInsertNode(V2, Top);
1131 if (unsigned n1 = IG.getNode(V1, Top))
1132 if (unsigned n2 = IG.getNode(V2, Top)) {
1133 if (n1 == n2) return Pred == ICmpInst::ICMP_EQ ||
1134 Pred == ICmpInst::ICMP_ULE ||
1135 Pred == ICmpInst::ICMP_UGE ||
1136 Pred == ICmpInst::ICMP_SLE ||
1137 Pred == ICmpInst::ICMP_SGE;
1138 if (Pred == ICmpInst::ICMP_EQ) return false;
1139 return IG.isRelatedBy(n1, n2, Top, cmpInstToLattice(Pred));
1145 /// add - adds a new property to the work queue
1146 void add(Value *V1, Value *V2, ICmpInst::Predicate Pred,
1147 Instruction *I = NULL) {
1148 DOUT << "adding " << *V1 << " " << Pred << " " << *V2;
1149 if (I) DOUT << " context: " << *I;
1150 else DOUT << " default context";
1153 WorkList.push_back(Operation());
1154 Operation &O = WorkList.back();
1155 O.LHS = V1, O.RHS = V2, O.Op = Pred, O.ContextInst = I;
1156 O.ContextBB = I ? I->getParent() : TopBB;
1159 /// defToOps - Given an instruction definition that we've learned something
1160 /// new about, find any new relationships between its operands.
1161 void defToOps(Instruction *I) {
1162 Instruction *NewContext = below(I) ? I : TopInst;
1163 Value *Canonical = IG.canonicalize(I, Top);
1165 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
1166 const Type *Ty = BO->getType();
1167 assert(!Ty->isFPOrFPVector() && "Float in work queue!");
1169 Value *Op0 = IG.canonicalize(BO->getOperand(0), Top);
1170 Value *Op1 = IG.canonicalize(BO->getOperand(1), Top);
1172 // TODO: "and bool true, %x" EQ %y then %x EQ %y.
1174 switch (BO->getOpcode()) {
1175 case Instruction::And: {
1176 // "and int %a, %b" EQ -1 then %a EQ -1 and %b EQ -1
1177 // "and bool %a, %b" EQ true then %a EQ true and %b EQ true
1178 ConstantInt *CI = ConstantInt::getAllOnesValue(Ty);
1179 if (Canonical == CI) {
1180 add(CI, Op0, ICmpInst::ICMP_EQ, NewContext);
1181 add(CI, Op1, ICmpInst::ICMP_EQ, NewContext);
1184 case Instruction::Or: {
1185 // "or int %a, %b" EQ 0 then %a EQ 0 and %b EQ 0
1186 // "or bool %a, %b" EQ false then %a EQ false and %b EQ false
1187 Constant *Zero = Constant::getNullValue(Ty);
1188 if (Canonical == Zero) {
1189 add(Zero, Op0, ICmpInst::ICMP_EQ, NewContext);
1190 add(Zero, Op1, ICmpInst::ICMP_EQ, NewContext);
1193 case Instruction::Xor: {
1194 // "xor bool true, %a" EQ true then %a EQ false
1195 // "xor bool true, %a" EQ false then %a EQ true
1196 // "xor bool false, %a" EQ true then %a EQ true
1197 // "xor bool false, %a" EQ false then %a EQ false
1198 // "xor int %c, %a" EQ %c then %a EQ 0
1199 // "xor int %c, %a" NE %c then %a NE 0
1200 // 1. Repeat all of the above, with order of operands reversed.
1203 if (!isa<Constant>(LHS)) std::swap(LHS, RHS);
1205 if (ConstantInt *CI = dyn_cast<ConstantInt>(Canonical)) {
1206 if (ConstantInt *Arg = dyn_cast<ConstantInt>(LHS)) {
1207 add(RHS, ConstantInt::get(CI->getValue() ^ Arg->getValue()),
1208 ICmpInst::ICMP_EQ, NewContext);
1211 if (Canonical == LHS) {
1212 if (isa<ConstantInt>(Canonical))
1213 add(RHS, Constant::getNullValue(Ty), ICmpInst::ICMP_EQ,
1215 } else if (isRelatedBy(LHS, Canonical, ICmpInst::ICMP_NE)) {
1216 add(RHS, Constant::getNullValue(Ty), ICmpInst::ICMP_NE,
1223 } else if (ICmpInst *IC = dyn_cast<ICmpInst>(I)) {
1224 // "icmp ult int %a, int %y" EQ true then %a u< y
1227 if (Canonical == ConstantInt::getTrue()) {
1228 add(IC->getOperand(0), IC->getOperand(1), IC->getPredicate(),
1230 } else if (Canonical == ConstantInt::getFalse()) {
1231 add(IC->getOperand(0), IC->getOperand(1),
1232 ICmpInst::getInversePredicate(IC->getPredicate()), NewContext);
1234 } else if (SelectInst *SI = dyn_cast<SelectInst>(I)) {
1235 if (I->getType()->isFPOrFPVector()) return;
1237 // Given: "%a = select bool %x, int %b, int %c"
1238 // %a EQ %b and %b NE %c then %x EQ true
1239 // %a EQ %c and %b NE %c then %x EQ false
1241 Value *True = SI->getTrueValue();
1242 Value *False = SI->getFalseValue();
1243 if (isRelatedBy(True, False, ICmpInst::ICMP_NE)) {
1244 if (Canonical == IG.canonicalize(True, Top) ||
1245 isRelatedBy(Canonical, False, ICmpInst::ICMP_NE))
1246 add(SI->getCondition(), ConstantInt::getTrue(),
1247 ICmpInst::ICMP_EQ, NewContext);
1248 else if (Canonical == IG.canonicalize(False, Top) ||
1249 isRelatedBy(I, True, ICmpInst::ICMP_NE))
1250 add(SI->getCondition(), ConstantInt::getFalse(),
1251 ICmpInst::ICMP_EQ, NewContext);
1254 // TODO: CastInst "%a = cast ... %b" where %a is EQ or NE a constant.
1257 /// opsToDef - A new relationship was discovered involving one of this
1258 /// instruction's operands. Find any new relationship involving the
1260 void opsToDef(Instruction *I) {
1261 Instruction *NewContext = below(I) ? I : TopInst;
1263 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
1264 Value *Op0 = IG.canonicalize(BO->getOperand(0), Top);
1265 Value *Op1 = IG.canonicalize(BO->getOperand(1), Top);
1267 if (ConstantInt *CI0 = dyn_cast<ConstantInt>(Op0))
1268 if (ConstantInt *CI1 = dyn_cast<ConstantInt>(Op1)) {
1269 add(BO, ConstantExpr::get(BO->getOpcode(), CI0, CI1),
1270 ICmpInst::ICMP_EQ, NewContext);
1274 // "%y = and bool true, %x" then %x EQ %y.
1275 // "%y = or bool false, %x" then %x EQ %y.
1276 if (BO->getOpcode() == Instruction::Or) {
1277 Constant *Zero = Constant::getNullValue(BO->getType());
1279 add(BO, Op1, ICmpInst::ICMP_EQ, NewContext);
1281 } else if (Op1 == Zero) {
1282 add(BO, Op0, ICmpInst::ICMP_EQ, NewContext);
1285 } else if (BO->getOpcode() == Instruction::And) {
1286 Constant *AllOnes = ConstantInt::getAllOnesValue(BO->getType());
1287 if (Op0 == AllOnes) {
1288 add(BO, Op1, ICmpInst::ICMP_EQ, NewContext);
1290 } else if (Op1 == AllOnes) {
1291 add(BO, Op0, ICmpInst::ICMP_EQ, NewContext);
1296 // "%x = add int %y, %z" and %x EQ %y then %z EQ 0
1297 // "%x = mul int %y, %z" and %x EQ %y then %z EQ 1
1298 // 1. Repeat all of the above, with order of operands reversed.
1299 // "%x = udiv int %y, %z" and %x EQ %y then %z EQ 1
1301 Value *Known = Op0, *Unknown = Op1;
1302 if (Known != BO) std::swap(Known, Unknown);
1304 const Type *Ty = BO->getType();
1305 assert(!Ty->isFPOrFPVector() && "Float in work queue!");
1307 switch (BO->getOpcode()) {
1309 case Instruction::Xor:
1310 case Instruction::Or:
1311 case Instruction::Add:
1312 case Instruction::Sub:
1313 add(Unknown, Constant::getNullValue(Ty), ICmpInst::ICMP_EQ,
1316 case Instruction::UDiv:
1317 case Instruction::SDiv:
1318 if (Unknown == Op0) break; // otherwise, fallthrough
1319 case Instruction::And:
1320 case Instruction::Mul:
1321 if (isa<ConstantInt>(Unknown)) {
1322 Constant *One = ConstantInt::get(Ty, 1);
1323 add(Unknown, One, ICmpInst::ICMP_EQ, NewContext);
1329 // TODO: "%a = add int %b, 1" and %b > %z then %a >= %z.
1331 } else if (ICmpInst *IC = dyn_cast<ICmpInst>(I)) {
1332 // "%a = icmp ult %b, %c" and %b u< %c then %a EQ true
1333 // "%a = icmp ult %b, %c" and %b u>= %c then %a EQ false
1336 Value *Op0 = IG.canonicalize(IC->getOperand(0), Top);
1337 Value *Op1 = IG.canonicalize(IC->getOperand(1), Top);
1339 ICmpInst::Predicate Pred = IC->getPredicate();
1340 if (isRelatedBy(Op0, Op1, Pred)) {
1341 add(IC, ConstantInt::getTrue(), ICmpInst::ICMP_EQ, NewContext);
1342 } else if (isRelatedBy(Op0, Op1, ICmpInst::getInversePredicate(Pred))) {
1343 add(IC, ConstantInt::getFalse(), ICmpInst::ICMP_EQ, NewContext);
1346 // TODO: "bool %x s<u> %y" implies %x = true and %y = false.
1348 // TODO: make the predicate more strict, if possible.
1350 } else if (SelectInst *SI = dyn_cast<SelectInst>(I)) {
1351 // Given: "%a = select bool %x, int %b, int %c"
1352 // %x EQ true then %a EQ %b
1353 // %x EQ false then %a EQ %c
1354 // %b EQ %c then %a EQ %b
1356 Value *Canonical = IG.canonicalize(SI->getCondition(), Top);
1357 if (Canonical == ConstantInt::getTrue()) {
1358 add(SI, SI->getTrueValue(), ICmpInst::ICMP_EQ, NewContext);
1359 } else if (Canonical == ConstantInt::getFalse()) {
1360 add(SI, SI->getFalseValue(), ICmpInst::ICMP_EQ, NewContext);
1361 } else if (IG.canonicalize(SI->getTrueValue(), Top) ==
1362 IG.canonicalize(SI->getFalseValue(), Top)) {
1363 add(SI, SI->getTrueValue(), ICmpInst::ICMP_EQ, NewContext);
1365 } else if (CastInst *CI = dyn_cast<CastInst>(I)) {
1366 if (CI->getDestTy()->isFPOrFPVector()) return;
1368 if (Constant *C = dyn_cast<Constant>(
1369 IG.canonicalize(CI->getOperand(0), Top))) {
1370 add(CI, ConstantExpr::getCast(CI->getOpcode(), C, CI->getDestTy()),
1371 ICmpInst::ICMP_EQ, NewContext);
1374 // TODO: "%a = cast ... %b" where %b is NE/LT/GT a constant.
1378 /// solve - process the work queue
1379 /// Return false if a logical contradiction occurs.
1381 //DOUT << "WorkList entry, size: " << WorkList.size() << "\n";
1382 while (!WorkList.empty()) {
1383 //DOUT << "WorkList size: " << WorkList.size() << "\n";
1385 Operation &O = WorkList.front();
1386 TopInst = O.ContextInst;
1387 TopBB = O.ContextBB;
1388 Top = Forest->getNodeForBlock(TopBB);
1390 O.LHS = IG.canonicalize(O.LHS, Top);
1391 O.RHS = IG.canonicalize(O.RHS, Top);
1393 assert(O.LHS == IG.canonicalize(O.LHS, Top) && "Canonicalize isn't.");
1394 assert(O.RHS == IG.canonicalize(O.RHS, Top) && "Canonicalize isn't.");
1396 DOUT << "solving " << *O.LHS << " " << O.Op << " " << *O.RHS;
1397 if (O.ContextInst) DOUT << " context inst: " << *O.ContextInst;
1398 else DOUT << " context block: " << O.ContextBB->getName();
1403 // If they're both Constant, skip it. Check for contradiction and mark
1404 // the BB as unreachable if so.
1405 if (Constant *CI_L = dyn_cast<Constant>(O.LHS)) {
1406 if (Constant *CI_R = dyn_cast<Constant>(O.RHS)) {
1407 if (ConstantExpr::getCompare(O.Op, CI_L, CI_R) ==
1408 ConstantInt::getFalse())
1411 WorkList.pop_front();
1416 if (compare(O.RHS, O.LHS)) {
1417 std::swap(O.LHS, O.RHS);
1418 O.Op = ICmpInst::getSwappedPredicate(O.Op);
1421 if (O.Op == ICmpInst::ICMP_EQ) {
1422 if (!makeEqual(O.LHS, O.RHS))
1425 LatticeVal LV = cmpInstToLattice(O.Op);
1427 if ((LV & EQ_BIT) &&
1428 isRelatedBy(O.LHS, O.RHS, ICmpInst::getSwappedPredicate(O.Op))) {
1429 if (!makeEqual(O.LHS, O.RHS))
1432 if (isRelatedBy(O.LHS, O.RHS, ICmpInst::getInversePredicate(O.Op))){
1434 WorkList.pop_front();
1438 unsigned n1 = IG.getOrInsertNode(O.LHS, Top);
1439 unsigned n2 = IG.getOrInsertNode(O.RHS, Top);
1442 if (O.Op != ICmpInst::ICMP_UGE && O.Op != ICmpInst::ICMP_ULE &&
1443 O.Op != ICmpInst::ICMP_SGE && O.Op != ICmpInst::ICMP_SLE)
1446 WorkList.pop_front();
1450 if (IG.isRelatedBy(n1, n2, Top, LV)) {
1451 WorkList.pop_front();
1455 // Generalize %x u> -10 to %x > -10.
1456 if (ConstantInt *CI = dyn_cast<ConstantInt>(O.RHS)) {
1457 // xform doesn't apply to i1
1458 if (CI->getType()->getBitWidth() > 1) {
1459 if (LV == SLT && CI->getValue().isNegative()) {
1460 // i8 %x s< -5 implies %x < -5 and %x u> 127
1462 const IntegerType *Ty = CI->getType();
1464 add(O.LHS, ConstantInt::get(Ty->getMask().lshr(1)),
1465 ICmpInst::ICMP_UGT);
1466 } else if (LV == SGT && CI->getValue().isPositive()) {
1467 // i8 %x s> 5 implies %x > 5 and %x u< 128
1469 const IntegerType *Ty = CI->getType();
1471 add(O.LHS, ConstantInt::get(
1472 APInt::getSignedMinValue(Ty->getBitWidth())),
1473 ICmpInst::ICMP_ULT);
1474 } else if (CI->getValue().isPositive()) {
1475 if (LV == ULT || LV == SLT) LV = LT;
1476 if (LV == UGT || LV == SGT) LV = GT;
1481 IG.addInequality(n1, n2, Top, LV);
1483 if (Instruction *I1 = dyn_cast<Instruction>(O.LHS)) {
1485 Top->DominatedBy(Forest->getNodeForBlock(I1->getParent())))
1488 if (isa<Instruction>(O.LHS) || isa<Argument>(O.LHS)) {
1489 for (Value::use_iterator UI = O.LHS->use_begin(),
1490 UE = O.LHS->use_end(); UI != UE;) {
1491 Use &TheUse = UI.getUse();
1493 if (Instruction *I = dyn_cast<Instruction>(TheUse.getUser())) {
1495 Top->DominatedBy(Forest->getNodeForBlock(I->getParent())))
1500 if (Instruction *I2 = dyn_cast<Instruction>(O.RHS)) {
1502 Top->DominatedBy(Forest->getNodeForBlock(I2->getParent())))
1505 if (isa<Instruction>(O.RHS) || isa<Argument>(O.RHS)) {
1506 for (Value::use_iterator UI = O.RHS->use_begin(),
1507 UE = O.RHS->use_end(); UI != UE;) {
1508 Use &TheUse = UI.getUse();
1510 if (Instruction *I = dyn_cast<Instruction>(TheUse.getUser())) {
1512 Top->DominatedBy(Forest->getNodeForBlock(I->getParent())))
1520 WorkList.pop_front();
1525 /// PredicateSimplifier - This class is a simplifier that replaces
1526 /// one equivalent variable with another. It also tracks what
1527 /// can't be equal and will solve setcc instructions when possible.
1528 /// @brief Root of the predicate simplifier optimization.
1529 class VISIBILITY_HIDDEN PredicateSimplifier : public FunctionPass {
1533 InequalityGraph *IG;
1534 UnreachableBlocks UB;
1536 std::vector<DominatorTree::Node *> WorkList;
1539 bool runOnFunction(Function &F);
1541 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
1542 AU.addRequiredID(BreakCriticalEdgesID);
1543 AU.addRequired<DominatorTree>();
1544 AU.addRequired<ETForest>();
1548 /// Forwards - Adds new properties into PropertySet and uses them to
1549 /// simplify instructions. Because new properties sometimes apply to
1550 /// a transition from one BasicBlock to another, this will use the
1551 /// PredicateSimplifier::proceedToSuccessor(s) interface to enter the
1552 /// basic block with the new PropertySet.
1553 /// @brief Performs abstract execution of the program.
1554 class VISIBILITY_HIDDEN Forwards : public InstVisitor<Forwards> {
1555 friend class InstVisitor<Forwards>;
1556 PredicateSimplifier *PS;
1557 DominatorTree::Node *DTNode;
1560 InequalityGraph &IG;
1561 UnreachableBlocks &UB;
1563 Forwards(PredicateSimplifier *PS, DominatorTree::Node *DTNode)
1564 : PS(PS), DTNode(DTNode), IG(*PS->IG), UB(PS->UB) {}
1566 void visitTerminatorInst(TerminatorInst &TI);
1567 void visitBranchInst(BranchInst &BI);
1568 void visitSwitchInst(SwitchInst &SI);
1570 void visitAllocaInst(AllocaInst &AI);
1571 void visitLoadInst(LoadInst &LI);
1572 void visitStoreInst(StoreInst &SI);
1574 void visitSExtInst(SExtInst &SI);
1575 void visitZExtInst(ZExtInst &ZI);
1577 void visitBinaryOperator(BinaryOperator &BO);
1580 // Used by terminator instructions to proceed from the current basic
1581 // block to the next. Verifies that "current" dominates "next",
1582 // then calls visitBasicBlock.
1583 void proceedToSuccessors(DominatorTree::Node *Current) {
1584 for (DominatorTree::Node::iterator I = Current->begin(),
1585 E = Current->end(); I != E; ++I) {
1586 WorkList.push_back(*I);
1590 void proceedToSuccessor(DominatorTree::Node *Next) {
1591 WorkList.push_back(Next);
1594 // Visits each instruction in the basic block.
1595 void visitBasicBlock(DominatorTree::Node *Node) {
1596 BasicBlock *BB = Node->getBlock();
1597 ETNode *ET = Forest->getNodeForBlock(BB);
1598 DOUT << "Entering Basic Block: " << BB->getName()
1599 << " (" << ET->getDFSNumIn() << ")\n";
1600 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
1601 visitInstruction(I++, Node, ET);
1605 // Tries to simplify each Instruction and add new properties to
1607 void visitInstruction(Instruction *I, DominatorTree::Node *DT, ETNode *ET) {
1608 DOUT << "Considering instruction " << *I << "\n";
1611 // Sometimes instructions are killed in earlier analysis.
1612 if (isInstructionTriviallyDead(I)) {
1616 I->eraseFromParent();
1621 // Try to replace the whole instruction.
1622 Value *V = IG->canonicalize(I, ET);
1623 assert(V == I && "Late instruction canonicalization.");
1627 DOUT << "Removing " << *I << ", replacing with " << *V << "\n";
1629 I->replaceAllUsesWith(V);
1630 I->eraseFromParent();
1634 // Try to substitute operands.
1635 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
1636 Value *Oper = I->getOperand(i);
1637 Value *V = IG->canonicalize(Oper, ET);
1638 assert(V == Oper && "Late operand canonicalization.");
1642 DOUT << "Resolving " << *I;
1643 I->setOperand(i, V);
1644 DOUT << " into " << *I;
1649 DOUT << "push (%" << I->getParent()->getName() << ")\n";
1650 Forwards visit(this, DT);
1652 DOUT << "pop (%" << I->getParent()->getName() << ")\n";
1656 bool PredicateSimplifier::runOnFunction(Function &F) {
1657 DT = &getAnalysis<DominatorTree>();
1658 Forest = &getAnalysis<ETForest>();
1660 Forest->updateDFSNumbers(); // XXX: should only act when numbers are out of date
1662 DOUT << "Entering Function: " << F.getName() << "\n";
1665 BasicBlock *RootBlock = &F.getEntryBlock();
1666 IG = new InequalityGraph(Forest->getNodeForBlock(RootBlock));
1667 WorkList.push_back(DT->getRootNode());
1670 DominatorTree::Node *DTNode = WorkList.back();
1671 WorkList.pop_back();
1672 if (!UB.isDead(DTNode->getBlock())) visitBasicBlock(DTNode);
1673 } while (!WorkList.empty());
1677 modified |= UB.kill();
1682 void PredicateSimplifier::Forwards::visitTerminatorInst(TerminatorInst &TI) {
1683 PS->proceedToSuccessors(DTNode);
1686 void PredicateSimplifier::Forwards::visitBranchInst(BranchInst &BI) {
1687 if (BI.isUnconditional()) {
1688 PS->proceedToSuccessors(DTNode);
1692 Value *Condition = BI.getCondition();
1693 BasicBlock *TrueDest = BI.getSuccessor(0);
1694 BasicBlock *FalseDest = BI.getSuccessor(1);
1696 if (isa<Constant>(Condition) || TrueDest == FalseDest) {
1697 PS->proceedToSuccessors(DTNode);
1701 for (DominatorTree::Node::iterator I = DTNode->begin(), E = DTNode->end();
1703 BasicBlock *Dest = (*I)->getBlock();
1704 DOUT << "Branch thinking about %" << Dest->getName()
1705 << "(" << PS->Forest->getNodeForBlock(Dest)->getDFSNumIn() << ")\n";
1707 if (Dest == TrueDest) {
1708 DOUT << "(" << DTNode->getBlock()->getName() << ") true set:\n";
1709 VRPSolver VRP(IG, UB, PS->Forest, PS->modified, Dest);
1710 VRP.add(ConstantInt::getTrue(), Condition, ICmpInst::ICMP_EQ);
1713 } else if (Dest == FalseDest) {
1714 DOUT << "(" << DTNode->getBlock()->getName() << ") false set:\n";
1715 VRPSolver VRP(IG, UB, PS->Forest, PS->modified, Dest);
1716 VRP.add(ConstantInt::getFalse(), Condition, ICmpInst::ICMP_EQ);
1721 PS->proceedToSuccessor(*I);
1725 void PredicateSimplifier::Forwards::visitSwitchInst(SwitchInst &SI) {
1726 Value *Condition = SI.getCondition();
1728 // Set the EQProperty in each of the cases BBs, and the NEProperties
1729 // in the default BB.
1731 for (DominatorTree::Node::iterator I = DTNode->begin(), E = DTNode->end();
1733 BasicBlock *BB = (*I)->getBlock();
1734 DOUT << "Switch thinking about BB %" << BB->getName()
1735 << "(" << PS->Forest->getNodeForBlock(BB)->getDFSNumIn() << ")\n";
1737 VRPSolver VRP(IG, UB, PS->Forest, PS->modified, BB);
1738 if (BB == SI.getDefaultDest()) {
1739 for (unsigned i = 1, e = SI.getNumCases(); i < e; ++i)
1740 if (SI.getSuccessor(i) != BB)
1741 VRP.add(Condition, SI.getCaseValue(i), ICmpInst::ICMP_NE);
1743 } else if (ConstantInt *CI = SI.findCaseDest(BB)) {
1744 VRP.add(Condition, CI, ICmpInst::ICMP_EQ);
1747 PS->proceedToSuccessor(*I);
1751 void PredicateSimplifier::Forwards::visitAllocaInst(AllocaInst &AI) {
1752 VRPSolver VRP(IG, UB, PS->Forest, PS->modified, &AI);
1753 VRP.add(Constant::getNullValue(AI.getType()), &AI, ICmpInst::ICMP_NE);
1757 void PredicateSimplifier::Forwards::visitLoadInst(LoadInst &LI) {
1758 Value *Ptr = LI.getPointerOperand();
1759 // avoid "load uint* null" -> null NE null.
1760 if (isa<Constant>(Ptr)) return;
1762 VRPSolver VRP(IG, UB, PS->Forest, PS->modified, &LI);
1763 VRP.add(Constant::getNullValue(Ptr->getType()), Ptr, ICmpInst::ICMP_NE);
1767 void PredicateSimplifier::Forwards::visitStoreInst(StoreInst &SI) {
1768 Value *Ptr = SI.getPointerOperand();
1769 if (isa<Constant>(Ptr)) return;
1771 VRPSolver VRP(IG, UB, PS->Forest, PS->modified, &SI);
1772 VRP.add(Constant::getNullValue(Ptr->getType()), Ptr, ICmpInst::ICMP_NE);
1776 void PredicateSimplifier::Forwards::visitSExtInst(SExtInst &SI) {
1777 VRPSolver VRP(IG, UB, PS->Forest, PS->modified, &SI);
1778 uint32_t SrcBitWidth = cast<IntegerType>(SI.getSrcTy())->getBitWidth();
1779 uint32_t DstBitWidth = cast<IntegerType>(SI.getDestTy())->getBitWidth();
1780 APInt Min(APInt::getSignedMinValue(SrcBitWidth));
1781 APInt Max(APInt::getSignedMaxValue(SrcBitWidth));
1782 Min.sext(DstBitWidth);
1783 Max.sext(DstBitWidth);
1784 VRP.add(ConstantInt::get(Min), &SI, ICmpInst::ICMP_SLE);
1785 VRP.add(ConstantInt::get(Max), &SI, ICmpInst::ICMP_SGE);
1789 void PredicateSimplifier::Forwards::visitZExtInst(ZExtInst &ZI) {
1790 VRPSolver VRP(IG, UB, PS->Forest, PS->modified, &ZI);
1791 uint32_t SrcBitWidth = cast<IntegerType>(ZI.getSrcTy())->getBitWidth();
1792 uint32_t DstBitWidth = cast<IntegerType>(ZI.getDestTy())->getBitWidth();
1793 APInt Max(APInt::getMaxValue(SrcBitWidth));
1794 Max.zext(DstBitWidth);
1795 VRP.add(ConstantInt::get(Max), &ZI, ICmpInst::ICMP_UGE);
1799 void PredicateSimplifier::Forwards::visitBinaryOperator(BinaryOperator &BO) {
1800 Instruction::BinaryOps ops = BO.getOpcode();
1803 case Instruction::URem:
1804 case Instruction::SRem:
1805 case Instruction::UDiv:
1806 case Instruction::SDiv: {
1807 Value *Divisor = BO.getOperand(1);
1808 VRPSolver VRP(IG, UB, PS->Forest, PS->modified, &BO);
1809 VRP.add(Constant::getNullValue(Divisor->getType()), Divisor,
1819 RegisterPass<PredicateSimplifier> X("predsimplify",
1820 "Predicate Simplifier");
1823 FunctionPass *llvm::createPredicateSimplifierPass() {
1824 return new PredicateSimplifier();