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 // queries (such as "isEqual") and mutators (such as "addEqual"). To implement
45 // "isLess(%a, %c)", we start with getNode(%c) and walk downwards until
46 // we reach %a or the leaf node. Note that the graph is directed and acyclic,
47 // but may contain joins, meaning that this walk is not a linear time
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/SetOperations.h"
78 #include "llvm/ADT/SmallVector.h"
79 #include "llvm/ADT/Statistic.h"
80 #include "llvm/ADT/STLExtras.h"
81 #include "llvm/Analysis/Dominators.h"
82 #include "llvm/Analysis/ET-Forest.h"
83 #include "llvm/Assembly/Writer.h"
84 #include "llvm/Support/CFG.h"
85 #include "llvm/Support/Debug.h"
86 #include "llvm/Support/InstVisitor.h"
87 #include "llvm/Transforms/Utils/Local.h"
97 NumVarsReplaced("predsimplify", "Number of argument substitutions");
99 NumInstruction("predsimplify", "Number of instructions removed");
101 NumSimple("predsimplify", "Number of simple replacements");
103 /// The InequalityGraph stores the relationships between values.
104 /// Each Value in the graph is assigned to a Node. Nodes are pointer
105 /// comparable for equality. The caller is expected to maintain the logical
106 /// consistency of the system.
108 /// The InequalityGraph class may invalidate Node*s after any mutator call.
109 /// @brief The InequalityGraph stores the relationships between values.
110 class VISIBILITY_HIDDEN InequalityGraph {
115 // 0 0 0 -- invalid (false)
116 // 0 0 1 -- invalid (EQ)
122 // 1 1 1 -- invalid (true)
124 EQ_BIT = 1, GT_BIT = 2, LT_BIT = 4
127 GT = GT_BIT, GE = GT_BIT | EQ_BIT,
128 LT = LT_BIT, LE = LT_BIT | EQ_BIT,
132 static bool validPredicate(LatticeVal LV) {
133 return LV > 1 && LV < 7;
137 typedef std::map<Value *, Node *> NodeMapType;
140 const InequalityGraph *ConcreteIG;
143 /// A single node in the InequalityGraph. This stores the canonical Value
144 /// for the node, as well as the relationships with the neighbours.
146 /// Because the lists are intended to be used for traversal, it is invalid
147 /// for the node to list itself in LessEqual or GreaterEqual lists. The
148 /// fact that a node is equal to itself is implied, and may be checked
149 /// with pointer comparison.
150 /// @brief A single node in the InequalityGraph.
151 class VISIBILITY_HIDDEN Node {
152 friend class InequalityGraph;
156 typedef SmallVector<std::pair<Node *, LatticeVal>, 4> RelationsType;
157 RelationsType Relations;
159 typedef RelationsType::iterator iterator;
160 typedef RelationsType::const_iterator const_iterator;
163 /// Updates the lattice value for a given node. Create a new entry if
164 /// one doesn't exist, otherwise it merges the values. The new lattice
165 /// value must not be inconsistent with any previously existing value.
166 void update(Node *N, LatticeVal R) {
167 iterator I = find(N);
169 Relations.push_back(std::make_pair(N, R));
171 I->second = static_cast<LatticeVal>(I->second & R);
172 assert(validPredicate(I->second) &&
173 "Invalid union of lattice values.");
177 void assign(Node *N, LatticeVal R) {
178 iterator I = find(N);
179 if (I != end()) I->second = R;
181 Relations.push_back(std::make_pair(N, R));
185 iterator begin() { return Relations.begin(); }
186 iterator end() { return Relations.end(); }
187 iterator find(Node *N) {
188 iterator I = begin();
189 for (iterator E = end(); I != E; ++I)
190 if (I->first == N) break;
194 const_iterator begin() const { return Relations.begin(); }
195 const_iterator end() const { return Relations.end(); }
196 const_iterator find(Node *N) const {
197 const_iterator I = begin();
198 for (const_iterator E = end(); I != E; ++I)
199 if (I->first == N) break;
203 unsigned findIndex(Node *N) {
205 iterator I = begin();
206 for (iterator E = end(); I != E; ++I, ++i)
207 if (I->first == N) return i;
211 void erase(iterator i) { Relations.erase(i); }
213 Value *getValue() const { return Canonical; }
214 void setValue(Value *V) { Canonical = V; }
216 void addNotEqual(Node *N) { update(N, NE); }
217 void addLess(Node *N) { update(N, LT); }
218 void addLessEqual(Node *N) { update(N, LE); }
219 void addGreater(Node *N) { update(N, GT); }
220 void addGreaterEqual(Node *N) { update(N, GE); }
223 InequalityGraph() : ConcreteIG(NULL) {}
225 InequalityGraph(const InequalityGraph &_IG) {
227 if (_IG.ConcreteIG) ConcreteIG = _IG.ConcreteIG;
228 else ConcreteIG = &_IG;
241 /// If the Value is in the graph, return the canonical form. Otherwise,
242 /// return the original Value.
243 Value *canonicalize(Value *V) const {
244 if (const Node *N = getNode(V))
245 return N->getValue();
250 /// Returns the node currently representing Value V, or null if no such
252 Node *getNode(Value *V) {
255 NodeMapType::const_iterator I = Nodes.find(V);
256 return (I != Nodes.end()) ? I->second : 0;
259 const Node *getNode(Value *V) const {
260 if (ConcreteIG) return ConcreteIG->getNode(V);
262 NodeMapType::const_iterator I = Nodes.find(V);
263 return (I != Nodes.end()) ? I->second : 0;
266 Node *getOrInsertNode(Value *V) {
267 if (Node *N = getNode(V))
273 Node *newNode(Value *V) {
274 //DEBUG(std::cerr << "new node: " << *V << "\n");
277 assert(N == 0 && "Node already exists for value.");
283 /// Returns true iff the nodes are provably inequal.
284 bool isNotEqual(const Node *N1, const Node *N2) const {
285 if (N1 == N2) return false;
286 for (Node::const_iterator I = N1->begin(), E = N1->end(); I != E; ++I) {
288 return (I->second & EQ_BIT) == 0;
290 return isLess(N1, N2) || isGreater(N1, N2);
293 /// Returns true iff N1 is provably less than N2.
294 bool isLess(const Node *N1, const Node *N2) const {
295 if (N1 == N2) return false;
296 for (Node::const_iterator I = N2->begin(), E = N2->end(); I != E; ++I) {
298 return I->second == LT;
300 for (Node::const_iterator I = N2->begin(), E = N2->end(); I != E; ++I) {
301 if ((I->second & (LT_BIT | GT_BIT)) == LT_BIT)
302 if (isLess(N1, I->first)) return true;
307 /// Returns true iff N1 is provably less than or equal to N2.
308 bool isLessEqual(const Node *N1, const Node *N2) const {
309 if (N1 == N2) return true;
310 for (Node::const_iterator I = N2->begin(), E = N2->end(); I != E; ++I) {
312 return (I->second & (LT_BIT | GT_BIT)) == LT_BIT;
314 for (Node::const_iterator I = N2->begin(), E = N2->end(); I != E; ++I) {
315 if ((I->second & (LT_BIT | GT_BIT)) == LT_BIT)
316 if (isLessEqual(N1, I->first)) return true;
321 /// Returns true iff N1 is provably greater than N2.
322 bool isGreater(const Node *N1, const Node *N2) const {
323 return isLess(N2, N1);
326 /// Returns true iff N1 is provably greater than or equal to N2.
327 bool isGreaterEqual(const Node *N1, const Node *N2) const {
328 return isLessEqual(N2, N1);
331 // The add* methods assume that your input is logically valid and may
332 // assertion-fail or infinitely loop if you attempt a contradiction.
334 void addEqual(Node *N, Value *V) {
339 void addNotEqual(Node *N1, Node *N2) {
340 assert(N1 != N2 && "A node can't be inequal to itself.");
346 /// N1 is less than N2.
347 void addLess(Node *N1, Node *N2) {
348 assert(N1 != N2 && !isLess(N2, N1) && "Attempt to create < cycle.");
354 /// N1 is less than or equal to N2.
355 void addLessEqual(Node *N1, Node *N2) {
356 assert(N1 != N2 && "Nodes are equal. Use mergeNodes instead.");
357 assert(!isGreater(N1, N2) && "Impossible: Adding x <= y when x > y.");
359 N2->addLessEqual(N1);
360 N1->addGreaterEqual(N2);
363 /// Find the transitive closure starting at a node walking down the edges
364 /// of type Val. Type Inserter must be an inserter that accepts Node *.
365 template <typename Inserter>
366 void transitiveClosure(Node *N, LatticeVal Val, Inserter insert) {
367 for (Node::iterator I = N->begin(), E = N->end(); I != E; ++I) {
368 if (I->second == Val) {
370 transitiveClosure(I->first, Val, insert);
375 /// Kills off all the nodes in Kill by replicating their properties into
376 /// node N. The elements of Kill must be unique. After merging, N's new
377 /// canonical value is NewCanonical. Type C must be a container of Node *.
378 template <typename C>
379 void mergeNodes(Node *N, C &Kill, Value *NewCanonical);
381 /// Removes a Value from the graph, but does not delete any nodes. As this
382 /// method does not delete Nodes, V may not be the canonical choice for
384 void remove(Value *V) {
387 for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E;) {
388 NodeMapType::iterator J = I++;
389 assert(J->second->getValue() != V && "Can't delete canonical choice.");
390 if (J->first == V) Nodes.erase(J);
395 void debug(std::ostream &os) const {
396 std::set<Node *> VisitedNodes;
397 for (NodeMapType::const_iterator I = Nodes.begin(), E = Nodes.end();
400 os << *I->first << " == " << *N->getValue() << "\n";
401 if (VisitedNodes.insert(N).second) {
402 os << *N->getValue() << ":\n";
403 for (Node::const_iterator NI = N->begin(), NE = N->end();
405 static const std::string names[8] =
406 { "00", "01", " <", "<=", " >", ">=", "!=", "07" };
407 os << " " << names[NI->second] << " "
408 << *NI->first->getValue() << "\n";
416 InequalityGraph::~InequalityGraph() {
417 if (ConcreteIG) return;
419 std::vector<Node *> Remove;
420 for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end();
422 if (I->first == I->second->getValue())
423 Remove.push_back(I->second);
425 for (std::vector<Node *>::iterator I = Remove.begin(), E = Remove.end();
431 template <typename C>
432 void InequalityGraph::mergeNodes(Node *N, C &Kill, Value *NewCanonical) {
435 // Merge the relationships from the members of Kill into N.
436 for (typename C::iterator KI = Kill.begin(), KE = Kill.end();
439 for (Node::iterator I = (*KI)->begin(), E = (*KI)->end(); I != E; ++I) {
440 if (I->first == N) continue;
442 Node::iterator NI = N->find(I->first);
443 if (NI == N->end()) {
444 N->Relations.push_back(std::make_pair(I->first, I->second));
446 unsigned char LV = NI->second & I->second;
449 assert(std::find(Kill.begin(), Kill.end(), I->first) != Kill.end()
450 && "Lost EQ property.");
453 NI->second = static_cast<LatticeVal>(LV);
454 assert(InequalityGraph::validPredicate(NI->second) &&
455 "Invalid union of lattice values.");
459 // All edges are reciprocal; every Node that Kill points to also
460 // contains a pointer to Kill. Replace those with pointers with N.
461 unsigned iter = I->first->findIndex(*KI);
462 assert(iter != (unsigned)-1 && "Edge not reciprocal.");
463 I->first->assign(N, (I->first->begin()+iter)->second);
464 I->first->erase(I->first->begin()+iter);
467 // Removing references from N to Kill.
468 Node::iterator NI = N->find(*KI);
469 if (NI != N->end()) {
470 N->erase(NI); // breaks reciprocity until Kill is deleted.
474 N->setValue(NewCanonical);
476 // Update value mapping to point to the merged node.
477 for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end();
479 if (std::find(Kill.begin(), Kill.end(), I->second) != Kill.end())
483 for (typename C::iterator KI = Kill.begin(), KE = Kill.end();
489 void InequalityGraph::materialize() {
490 if (!ConcreteIG) return;
491 const InequalityGraph *IG = ConcreteIG;
494 for (NodeMapType::const_iterator I = IG->Nodes.begin(),
495 E = IG->Nodes.end(); I != E; ++I) {
496 if (I->first == I->second->getValue()) {
497 Node *N = newNode(I->first);
498 N->Relations.reserve(N->Relations.size());
501 for (NodeMapType::const_iterator I = IG->Nodes.begin(),
502 E = IG->Nodes.end(); I != E; ++I) {
503 if (I->first != I->second->getValue()) {
504 Nodes[I->first] = getNode(I->second->getValue());
506 Node *Old = I->second;
507 Node *N = getNode(I->first);
508 for (Node::const_iterator NI = Old->begin(), NE = Old->end();
510 N->assign(getNode(NI->first->getValue()), NI->second);
516 /// VRPSolver keeps track of how changes to one variable affect other
517 /// variables, and forwards changes along to the InequalityGraph. It
518 /// also maintains the correct choice for "canonical" in the IG.
519 /// @brief VRPSolver calculates inferences from a new relationship.
520 class VISIBILITY_HIDDEN VRPSolver {
522 std::deque<Instruction *> WorkList;
525 const InequalityGraph &cIG;
529 typedef InequalityGraph::Node Node;
531 /// Returns true if V1 is a better canonical value than V2.
532 bool compare(Value *V1, Value *V2) const {
533 if (isa<Constant>(V1))
534 return !isa<Constant>(V2);
535 else if (isa<Constant>(V2))
537 else if (isa<Argument>(V1))
538 return !isa<Argument>(V2);
539 else if (isa<Argument>(V2))
542 Instruction *I1 = dyn_cast<Instruction>(V1);
543 Instruction *I2 = dyn_cast<Instruction>(V2);
545 if (!I1 || !I2) return false;
547 BasicBlock *BB1 = I1->getParent(),
548 *BB2 = I2->getParent();
550 for (BasicBlock::const_iterator I = BB1->begin(), E = BB1->end();
552 if (&*I == I1) return true;
553 if (&*I == I2) return false;
555 assert(!"Instructions not found in parent BasicBlock?");
557 return Forest->properlyDominates(BB1, BB2);
562 void addToWorklist(Instruction *I) {
563 //DEBUG(std::cerr << "addToWorklist: " << *I << "\n");
565 if (!isa<BinaryOperator>(I) && !isa<SelectInst>(I)) return;
567 const Type *Ty = I->getType();
568 if (Ty == Type::VoidTy || Ty->isFPOrFPVector()) return;
570 if (isInstructionTriviallyDead(I)) return;
572 WorkList.push_back(I);
575 void addRecursive(Value *V) {
576 //DEBUG(std::cerr << "addRecursive: " << *V << "\n");
578 Instruction *I = dyn_cast<Instruction>(V);
581 else if (!isa<Argument>(V))
584 //DEBUG(std::cerr << "addRecursive uses...\n");
585 for (Value::use_iterator UI = V->use_begin(), UE = V->use_end();
587 // Use must be either be dominated by Top, or dominate Top.
588 if (Instruction *Inst = dyn_cast<Instruction>(*UI)) {
589 ETNode *INode = Forest->getNodeForBlock(Inst->getParent());
590 if (INode->DominatedBy(Top) || Top->DominatedBy(INode))
596 //DEBUG(std::cerr << "addRecursive ops...\n");
597 for (User::op_iterator OI = I->op_begin(), OE = I->op_end();
599 if (Instruction *Inst = dyn_cast<Instruction>(*OI))
603 //DEBUG(std::cerr << "exit addRecursive (" << *V << ").\n");
607 VRPSolver(InequalityGraph &IG, ETForest *Forest, BasicBlock *TopBB)
608 : IG(IG), cIG(IG), Forest(Forest), Top(Forest->getNodeForBlock(TopBB)) {}
610 bool isEqual(Value *V1, Value *V2) const {
611 if (V1 == V2) return true;
612 if (const Node *N1 = cIG.getNode(V1))
613 return N1 == cIG.getNode(V2);
617 bool isNotEqual(Value *V1, Value *V2) const {
618 if (V1 == V2) return false;
619 if (const Node *N1 = cIG.getNode(V1))
620 if (const Node *N2 = cIG.getNode(V2))
621 return cIG.isNotEqual(N1, N2);
625 bool isLess(Value *V1, Value *V2) const {
626 if (V1 == V2) return false;
627 if (const Node *N1 = cIG.getNode(V1))
628 if (const Node *N2 = cIG.getNode(V2))
629 return cIG.isLess(N1, N2);
633 bool isLessEqual(Value *V1, Value *V2) const {
634 if (V1 == V2) return true;
635 if (const Node *N1 = cIG.getNode(V1))
636 if (const Node *N2 = cIG.getNode(V2))
637 return cIG.isLessEqual(N1, N2);
641 bool isGreater(Value *V1, Value *V2) const {
642 if (V1 == V2) return false;
643 if (const Node *N1 = cIG.getNode(V1))
644 if (const Node *N2 = cIG.getNode(V2))
645 return cIG.isGreater(N1, N2);
649 bool isGreaterEqual(Value *V1, Value *V2) const {
650 if (V1 == V2) return true;
651 if (const Node *N1 = IG.getNode(V1))
652 if (const Node *N2 = IG.getNode(V2))
653 return cIG.isGreaterEqual(N1, N2);
657 // All of the add* functions return true if the InequalityGraph represents
658 // the property, and false if there is a logical contradiction. On false,
659 // you may no longer perform any queries on the InequalityGraph.
661 bool addEqual(Value *V1, Value *V2) {
662 //DEBUG(std::cerr << "addEqual(" << *V1 << ", "
664 if (isEqual(V1, V2)) return true;
666 const Node *cN1 = cIG.getNode(V1), *cN2 = cIG.getNode(V2);
668 if (cN1 && cN2 && cIG.isNotEqual(cN1, cN2))
671 if (compare(V2, V1)) { std::swap(V1, V2); std::swap(cN1, cN2); }
674 if (ConstantBool *CB = dyn_cast<ConstantBool>(V1)) {
675 Node *N1 = IG.getNode(V1);
677 // When "addEqual" is performed and the new value is a ConstantBool,
678 // iterate through the NE set and fix them up to be EQ of the
681 for (Node::iterator I = N1->begin(), E = N1->end(); I != E; ++I)
682 if ((I->second & 1) == 0) {
683 assert(N1 != I->first && "Node related to itself?");
684 addEqual(I->first->getValue(),
685 ConstantBool::get(!CB->getValue()));
691 if (Instruction *I2 = dyn_cast<Instruction>(V2)) {
692 ETNode *Node_I2 = Forest->getNodeForBlock(I2->getParent());
693 if (Top != Node_I2 && Node_I2->DominatedBy(Top)) {
695 if (cN1 && compare(V1, cN1->getValue())) V = cN1->getValue();
696 //DEBUG(std::cerr << "Simply removing " << *I2
697 // << ", replacing with " << *V << "\n");
698 I2->replaceAllUsesWith(V);
699 // leave it dead; it'll get erased later.
707 Node *N1 = IG.getNode(V1), *N2 = IG.getNode(V2);
711 if (compare(V1, N1->getValue())) N1->setValue(V1);
715 if (compare(V1, N2->getValue())) N2->setValue(V1);
718 // Suppose we're being told that %x == %y, and %x <= %z and %y >= %z.
719 // We can't just merge %x and %y because the relationship with %z would
720 // be EQ and that's invalid; they need to be the same Node.
722 // What we're doing is looking for any chain of nodes reaching %z such
723 // that %x <= %z and %y >= %z, and vice versa. The cool part is that
724 // every node in between is also equal because of the squeeze principle.
726 std::vector<Node *> N1_GE, N2_LE, N1_LE, N2_GE;
727 IG.transitiveClosure(N1, InequalityGraph::GE, back_inserter(N1_GE));
728 std::sort(N1_GE.begin(), N1_GE.end());
729 N1_GE.erase(std::unique(N1_GE.begin(), N1_GE.end()), N1_GE.end());
730 IG.transitiveClosure(N2, InequalityGraph::LE, back_inserter(N2_LE));
731 std::sort(N1_LE.begin(), N1_LE.end());
732 N1_LE.erase(std::unique(N1_LE.begin(), N1_LE.end()), N1_LE.end());
733 IG.transitiveClosure(N1, InequalityGraph::LE, back_inserter(N1_LE));
734 std::sort(N2_GE.begin(), N2_GE.end());
735 N2_GE.erase(std::unique(N2_GE.begin(), N2_GE.end()), N2_GE.end());
736 std::unique(N2_GE.begin(), N2_GE.end());
737 IG.transitiveClosure(N2, InequalityGraph::GE, back_inserter(N2_GE));
738 std::sort(N2_LE.begin(), N2_LE.end());
739 N2_LE.erase(std::unique(N2_LE.begin(), N2_LE.end()), N2_LE.end());
741 std::vector<Node *> Set1, Set2;
742 std::set_intersection(N1_GE.begin(), N1_GE.end(),
743 N2_LE.begin(), N2_LE.end(),
744 back_inserter(Set1));
745 std::set_intersection(N1_LE.begin(), N1_LE.end(),
746 N2_GE.begin(), N2_GE.end(),
747 back_inserter(Set2));
749 std::vector<Node *> Equal;
750 std::set_union(Set1.begin(), Set1.end(), Set2.begin(), Set2.end(),
751 back_inserter(Equal));
753 Value *Best = N1->getValue();
754 if (compare(N2->getValue(), Best)) Best = N2->getValue();
756 for (std::vector<Node *>::iterator I = Equal.begin(), E = Equal.end();
758 Value *V = (*I)->getValue();
759 if (compare(V, Best)) Best = V;
763 IG.mergeNodes(N1, Equal, Best);
765 if (!N1 && !N2) IG.addEqual(IG.newNode(V1), V2);
773 bool addNotEqual(Value *V1, Value *V2) {
774 //DEBUG(std::cerr << "addNotEqual(" << *V1 << ", "
776 if (isNotEqual(V1, V2)) return true;
778 // Never permit %x NE true/false.
779 if (ConstantBool *B1 = dyn_cast<ConstantBool>(V1)) {
780 return addEqual(ConstantBool::get(!B1->getValue()), V2);
781 } else if (ConstantBool *B2 = dyn_cast<ConstantBool>(V2)) {
782 return addEqual(V1, ConstantBool::get(!B2->getValue()));
785 Node *N1 = IG.getOrInsertNode(V1),
786 *N2 = IG.getOrInsertNode(V2);
788 if (N1 == N2) return false;
790 IG.addNotEqual(N1, N2);
798 /// Set V1 less than V2.
799 bool addLess(Value *V1, Value *V2) {
800 if (isLess(V1, V2)) return true;
801 if (isGreaterEqual(V1, V2)) return false;
803 Node *N1 = IG.getOrInsertNode(V1), *N2 = IG.getOrInsertNode(V2);
805 if (N1 == N2) return false;
815 /// Set V1 less than or equal to V2.
816 bool addLessEqual(Value *V1, Value *V2) {
817 if (isLessEqual(V1, V2)) return true;
818 if (V1 == V2) return true;
820 if (isLessEqual(V2, V1))
821 return addEqual(V1, V2);
823 if (isGreater(V1, V2)) return false;
825 Node *N1 = IG.getOrInsertNode(V1),
826 *N2 = IG.getOrInsertNode(V2);
828 if (N1 == N2) return true;
830 IG.addLessEqual(N1, N2);
839 DEBUG(std::cerr << "WorkList entry, size: " << WorkList.size() << "\n");
840 while (!WorkList.empty()) {
841 DEBUG(std::cerr << "WorkList size: " << WorkList.size() << "\n");
843 Instruction *I = WorkList.front();
844 WorkList.pop_front();
846 Value *Canonical = cIG.canonicalize(I);
847 const Type *Ty = I->getType();
849 //DEBUG(std::cerr << "solving: " << *I << "\n");
850 //DEBUG(IG.debug(std::cerr));
852 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
853 Value *Op0 = cIG.canonicalize(BO->getOperand(0)),
854 *Op1 = cIG.canonicalize(BO->getOperand(1));
856 ConstantIntegral *CI1 = dyn_cast<ConstantIntegral>(Op0),
857 *CI2 = dyn_cast<ConstantIntegral>(Op1);
860 addEqual(BO, ConstantExpr::get(BO->getOpcode(), CI1, CI2));
862 switch (BO->getOpcode()) {
863 case Instruction::SetEQ:
864 // "seteq int %a, %b" EQ true then %a EQ %b
865 // "seteq int %a, %b" EQ false then %a NE %b
866 if (Canonical == ConstantBool::getTrue())
868 else if (Canonical == ConstantBool::getFalse())
869 addNotEqual(Op0, Op1);
871 // %a EQ %b then "seteq int %a, %b" EQ true
872 // %a NE %b then "seteq int %a, %b" EQ false
873 if (isEqual(Op0, Op1))
874 addEqual(BO, ConstantBool::getTrue());
875 else if (isNotEqual(Op0, Op1))
876 addEqual(BO, ConstantBool::getFalse());
879 case Instruction::SetNE:
880 // "setne int %a, %b" EQ true then %a NE %b
881 // "setne int %a, %b" EQ false then %a EQ %b
882 if (Canonical == ConstantBool::getTrue())
883 addNotEqual(Op0, Op1);
884 else if (Canonical == ConstantBool::getFalse())
887 // %a EQ %b then "setne int %a, %b" EQ false
888 // %a NE %b then "setne int %a, %b" EQ true
889 if (isEqual(Op0, Op1))
890 addEqual(BO, ConstantBool::getFalse());
891 else if (isNotEqual(Op0, Op1))
892 addEqual(BO, ConstantBool::getTrue());
895 case Instruction::SetLT:
896 // "setlt int %a, %b" EQ true then %a LT %b
897 // "setlt int %a, %b" EQ false then %b LE %a
898 if (Canonical == ConstantBool::getTrue())
900 else if (Canonical == ConstantBool::getFalse())
901 addLessEqual(Op1, Op0);
903 // %a LT %b then "setlt int %a, %b" EQ true
904 // %a GE %b then "setlt int %a, %b" EQ false
905 if (isLess(Op0, Op1))
906 addEqual(BO, ConstantBool::getTrue());
907 else if (isGreaterEqual(Op0, Op1))
908 addEqual(BO, ConstantBool::getFalse());
911 case Instruction::SetLE:
912 // "setle int %a, %b" EQ true then %a LE %b
913 // "setle int %a, %b" EQ false then %b LT %a
914 if (Canonical == ConstantBool::getTrue())
915 addLessEqual(Op0, Op1);
916 else if (Canonical == ConstantBool::getFalse())
919 // %a LE %b then "setle int %a, %b" EQ true
920 // %a GT %b then "setle int %a, %b" EQ false
921 if (isLessEqual(Op0, Op1))
922 addEqual(BO, ConstantBool::getTrue());
923 else if (isGreater(Op0, Op1))
924 addEqual(BO, ConstantBool::getFalse());
927 case Instruction::SetGT:
928 // "setgt int %a, %b" EQ true then %b LT %a
929 // "setgt int %a, %b" EQ false then %a LE %b
930 if (Canonical == ConstantBool::getTrue())
932 else if (Canonical == ConstantBool::getFalse())
933 addLessEqual(Op0, Op1);
935 // %a GT %b then "setgt int %a, %b" EQ true
936 // %a LE %b then "setgt int %a, %b" EQ false
937 if (isGreater(Op0, Op1))
938 addEqual(BO, ConstantBool::getTrue());
939 else if (isLessEqual(Op0, Op1))
940 addEqual(BO, ConstantBool::getFalse());
943 case Instruction::SetGE:
944 // "setge int %a, %b" EQ true then %b LE %a
945 // "setge int %a, %b" EQ false then %a LT %b
946 if (Canonical == ConstantBool::getTrue())
947 addLessEqual(Op1, Op0);
948 else if (Canonical == ConstantBool::getFalse())
951 // %a GE %b then "setge int %a, %b" EQ true
952 // %a LT %b then "setlt int %a, %b" EQ false
953 if (isGreaterEqual(Op0, Op1))
954 addEqual(BO, ConstantBool::getTrue());
955 else if (isLess(Op0, Op1))
956 addEqual(BO, ConstantBool::getFalse());
959 case Instruction::And: {
960 // "and int %a, %b" EQ -1 then %a EQ -1 and %b EQ -1
961 // "and bool %a, %b" EQ true then %a EQ true and %b EQ true
962 ConstantIntegral *CI = ConstantIntegral::getAllOnesValue(Ty);
963 if (Canonical == CI) {
968 case Instruction::Or: {
969 // "or int %a, %b" EQ 0 then %a EQ 0 and %b EQ 0
970 // "or bool %a, %b" EQ false then %a EQ false and %b EQ false
971 Constant *Zero = Constant::getNullValue(Ty);
972 if (Canonical == Zero) {
977 case Instruction::Xor: {
978 // "xor bool true, %a" EQ true then %a EQ false
979 // "xor bool true, %a" EQ false then %a EQ true
980 // "xor bool false, %a" EQ true then %a EQ true
981 // "xor bool false, %a" EQ false then %a EQ false
982 // "xor int %c, %a" EQ %c then %a EQ 0
983 // "xor int %c, %a" NE %c then %a NE 0
984 // 1. Repeat all of the above, with order of operands reversed.
985 Value *LHS = Op0, *RHS = Op1;
986 if (!isa<Constant>(LHS)) std::swap(LHS, RHS);
988 if (ConstantBool *CB = dyn_cast<ConstantBool>(Canonical)) {
989 if (ConstantBool *A = dyn_cast<ConstantBool>(LHS))
990 addEqual(RHS, ConstantBool::get(A->getValue() ^
993 if (Canonical == LHS) {
994 if (isa<ConstantIntegral>(Canonical))
995 addEqual(RHS, Constant::getNullValue(Ty));
996 } else if (isNotEqual(LHS, Canonical)) {
997 addNotEqual(RHS, Constant::getNullValue(Ty));
1004 // "%x = add int %y, %z" and %x EQ %y then %z EQ 0
1005 // "%x = mul int %y, %z" and %x EQ %y then %z EQ 1
1006 // 1. Repeat all of the above, with order of operands reversed.
1007 // "%x = fdiv float %y, %z" and %x EQ %y then %z EQ 1
1008 Value *Known = Op0, *Unknown = Op1;
1009 if (Known != BO) std::swap(Known, Unknown);
1011 switch (BO->getOpcode()) {
1013 case Instruction::Xor:
1014 case Instruction::Or:
1015 case Instruction::Add:
1016 case Instruction::Sub:
1017 if (!Ty->isFloatingPoint())
1018 addEqual(Unknown, Constant::getNullValue(Ty));
1020 case Instruction::UDiv:
1021 case Instruction::SDiv:
1022 case Instruction::FDiv:
1023 if (Unknown == Op0) break; // otherwise, fallthrough
1024 case Instruction::And:
1025 case Instruction::Mul:
1026 Constant *One = NULL;
1027 if (isa<ConstantInt>(Unknown))
1028 One = ConstantInt::get(Ty, 1);
1029 else if (isa<ConstantFP>(Unknown))
1030 One = ConstantFP::get(Ty, 1);
1031 else if (isa<ConstantBool>(Unknown))
1032 One = ConstantBool::getTrue();
1034 if (One) addEqual(Unknown, One);
1038 } else if (SelectInst *SI = dyn_cast<SelectInst>(I)) {
1039 // Given: "%a = select bool %x, int %b, int %c"
1040 // %a EQ %b then %x EQ true
1041 // %a EQ %c then %x EQ false
1042 if (isEqual(I, SI->getTrueValue()) ||
1043 isNotEqual(I, SI->getFalseValue()))
1044 addEqual(SI->getCondition(), ConstantBool::getTrue());
1045 else if (isEqual(I, SI->getFalseValue()) ||
1046 isNotEqual(I, SI->getTrueValue()))
1047 addEqual(SI->getCondition(), ConstantBool::getFalse());
1049 // %x EQ true then %a EQ %b
1050 // %x EQ false then %a NE %b
1051 if (isEqual(SI->getCondition(), ConstantBool::getTrue()))
1052 addEqual(SI, SI->getTrueValue());
1053 else if (isEqual(SI->getCondition(), ConstantBool::getFalse()))
1054 addEqual(SI, SI->getFalseValue());
1060 /// PredicateSimplifier - This class is a simplifier that replaces
1061 /// one equivalent variable with another. It also tracks what
1062 /// can't be equal and will solve setcc instructions when possible.
1063 /// @brief Root of the predicate simplifier optimization.
1064 class VISIBILITY_HIDDEN PredicateSimplifier : public FunctionPass {
1071 BasicBlock *ToVisit;
1072 InequalityGraph *IG;
1074 State(BasicBlock *BB, InequalityGraph *IG) : ToVisit(BB), IG(IG) {}
1077 std::vector<State> WorkList;
1080 bool runOnFunction(Function &F);
1082 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
1083 AU.addRequiredID(BreakCriticalEdgesID);
1084 AU.addRequired<DominatorTree>();
1085 AU.addRequired<ETForest>();
1086 AU.setPreservesCFG();
1087 AU.addPreservedID(BreakCriticalEdgesID);
1091 /// Forwards - Adds new properties into PropertySet and uses them to
1092 /// simplify instructions. Because new properties sometimes apply to
1093 /// a transition from one BasicBlock to another, this will use the
1094 /// PredicateSimplifier::proceedToSuccessor(s) interface to enter the
1095 /// basic block with the new PropertySet.
1096 /// @brief Performs abstract execution of the program.
1097 class VISIBILITY_HIDDEN Forwards : public InstVisitor<Forwards> {
1098 friend class InstVisitor<Forwards>;
1099 PredicateSimplifier *PS;
1102 InequalityGraph &IG;
1104 Forwards(PredicateSimplifier *PS, InequalityGraph &IG)
1107 void visitTerminatorInst(TerminatorInst &TI);
1108 void visitBranchInst(BranchInst &BI);
1109 void visitSwitchInst(SwitchInst &SI);
1111 void visitAllocaInst(AllocaInst &AI);
1112 void visitLoadInst(LoadInst &LI);
1113 void visitStoreInst(StoreInst &SI);
1115 void visitBinaryOperator(BinaryOperator &BO);
1118 // Used by terminator instructions to proceed from the current basic
1119 // block to the next. Verifies that "current" dominates "next",
1120 // then calls visitBasicBlock.
1121 void proceedToSuccessors(const InequalityGraph &IG, BasicBlock *BBCurrent) {
1122 DominatorTree::Node *Current = DT->getNode(BBCurrent);
1123 for (DominatorTree::Node::iterator I = Current->begin(),
1124 E = Current->end(); I != E; ++I) {
1125 //visitBasicBlock((*I)->getBlock(), IG);
1126 WorkList.push_back(State((*I)->getBlock(), new InequalityGraph(IG)));
1130 void proceedToSuccessor(InequalityGraph *NextIG, BasicBlock *Next) {
1131 //visitBasicBlock(Next, NextIG);
1132 WorkList.push_back(State(Next, NextIG));
1135 // Visits each instruction in the basic block.
1136 void visitBasicBlock(BasicBlock *BB, InequalityGraph &IG) {
1137 DEBUG(std::cerr << "Entering Basic Block: " << BB->getName() << "\n");
1138 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
1139 visitInstruction(I++, IG);
1143 // Tries to simplify each Instruction and add new properties to
1145 void visitInstruction(Instruction *I, InequalityGraph &IG) {
1146 DEBUG(std::cerr << "Considering instruction " << *I << "\n");
1147 DEBUG(IG.debug(std::cerr));
1149 // Sometimes instructions are made dead due to earlier analysis.
1150 if (isInstructionTriviallyDead(I)) {
1151 I->eraseFromParent();
1155 // Try to replace the whole instruction.
1156 Value *V = IG.canonicalize(I);
1160 DEBUG(std::cerr << "Removing " << *I << ", replacing with "
1163 I->replaceAllUsesWith(V);
1164 I->eraseFromParent();
1168 // Try to substitute operands.
1169 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
1170 Value *Oper = I->getOperand(i);
1171 Value *V = IG.canonicalize(Oper);
1175 DEBUG(std::cerr << "Resolving " << *I);
1176 I->setOperand(i, V);
1177 DEBUG(std::cerr << " into " << *I);
1181 //DEBUG(std::cerr << "push (%" << I->getParent()->getName() << ")\n");
1182 Forwards visit(this, IG);
1184 //DEBUG(std::cerr << "pop (%" << I->getParent()->getName() << ")\n");
1188 bool PredicateSimplifier::runOnFunction(Function &F) {
1189 DT = &getAnalysis<DominatorTree>();
1190 Forest = &getAnalysis<ETForest>();
1192 DEBUG(std::cerr << "Entering Function: " << F.getName() << "\n");
1195 WorkList.push_back(State(DT->getRoot(), new InequalityGraph()));
1198 State S = WorkList.back();
1199 WorkList.pop_back();
1200 visitBasicBlock(S.ToVisit, *S.IG);
1202 } while (!WorkList.empty());
1204 //DEBUG(F.viewCFG());
1209 void PredicateSimplifier::Forwards::visitTerminatorInst(TerminatorInst &TI) {
1210 PS->proceedToSuccessors(IG, TI.getParent());
1213 void PredicateSimplifier::Forwards::visitBranchInst(BranchInst &BI) {
1214 BasicBlock *BB = BI.getParent();
1216 if (BI.isUnconditional()) {
1217 PS->proceedToSuccessors(IG, BB);
1221 Value *Condition = BI.getCondition();
1222 BasicBlock *TrueDest = BI.getSuccessor(0),
1223 *FalseDest = BI.getSuccessor(1);
1225 if (isa<ConstantBool>(Condition) || TrueDest == FalseDest) {
1226 PS->proceedToSuccessors(IG, BB);
1230 DominatorTree::Node *Node = PS->DT->getNode(BB);
1231 for (DominatorTree::Node::iterator I = Node->begin(), E = Node->end();
1233 BasicBlock *Dest = (*I)->getBlock();
1234 InequalityGraph *DestProperties = new InequalityGraph(IG);
1235 VRPSolver Solver(*DestProperties, PS->Forest, Dest);
1237 if (Dest == TrueDest) {
1238 DEBUG(std::cerr << "(" << BB->getName() << ") true set:\n");
1239 if (!Solver.addEqual(ConstantBool::getTrue(), Condition)) continue;
1241 DEBUG(DestProperties->debug(std::cerr));
1242 } else if (Dest == FalseDest) {
1243 DEBUG(std::cerr << "(" << BB->getName() << ") false set:\n");
1244 if (!Solver.addEqual(ConstantBool::getFalse(), Condition)) continue;
1246 DEBUG(DestProperties->debug(std::cerr));
1249 PS->proceedToSuccessor(DestProperties, Dest);
1253 void PredicateSimplifier::Forwards::visitSwitchInst(SwitchInst &SI) {
1254 Value *Condition = SI.getCondition();
1256 // Set the EQProperty in each of the cases BBs, and the NEProperties
1257 // in the default BB.
1258 // InequalityGraph DefaultProperties(IG);
1260 DominatorTree::Node *Node = PS->DT->getNode(SI.getParent());
1261 for (DominatorTree::Node::iterator I = Node->begin(), E = Node->end();
1263 BasicBlock *BB = (*I)->getBlock();
1265 InequalityGraph *BBProperties = new InequalityGraph(IG);
1266 VRPSolver Solver(*BBProperties, PS->Forest, BB);
1267 if (BB == SI.getDefaultDest()) {
1268 for (unsigned i = 1, e = SI.getNumCases(); i < e; ++i)
1269 if (SI.getSuccessor(i) != BB)
1270 if (!Solver.addNotEqual(Condition, SI.getCaseValue(i))) continue;
1272 } else if (ConstantInt *CI = SI.findCaseDest(BB)) {
1273 if (!Solver.addEqual(Condition, CI)) continue;
1276 PS->proceedToSuccessor(BBProperties, BB);
1280 void PredicateSimplifier::Forwards::visitAllocaInst(AllocaInst &AI) {
1281 VRPSolver VRP(IG, PS->Forest, AI.getParent());
1282 VRP.addNotEqual(Constant::getNullValue(AI.getType()), &AI);
1286 void PredicateSimplifier::Forwards::visitLoadInst(LoadInst &LI) {
1287 Value *Ptr = LI.getPointerOperand();
1288 // avoid "load uint* null" -> null NE null.
1289 if (isa<Constant>(Ptr)) return;
1291 VRPSolver VRP(IG, PS->Forest, LI.getParent());
1292 VRP.addNotEqual(Constant::getNullValue(Ptr->getType()), Ptr);
1296 void PredicateSimplifier::Forwards::visitStoreInst(StoreInst &SI) {
1297 Value *Ptr = SI.getPointerOperand();
1298 if (isa<Constant>(Ptr)) return;
1300 VRPSolver VRP(IG, PS->Forest, SI.getParent());
1301 VRP.addNotEqual(Constant::getNullValue(Ptr->getType()), Ptr);
1305 void PredicateSimplifier::Forwards::visitBinaryOperator(BinaryOperator &BO) {
1306 Instruction::BinaryOps ops = BO.getOpcode();
1309 case Instruction::URem:
1310 case Instruction::SRem:
1311 case Instruction::FRem:
1312 case Instruction::UDiv:
1313 case Instruction::SDiv:
1314 case Instruction::FDiv: {
1315 Value *Divisor = BO.getOperand(1);
1316 VRPSolver VRP(IG, PS->Forest, BO.getParent());
1317 VRP.addNotEqual(Constant::getNullValue(Divisor->getType()), Divisor);
1327 RegisterPass<PredicateSimplifier> X("predsimplify",
1328 "Predicate Simplifier");
1331 FunctionPass *llvm::createPredicateSimplifierPass() {
1332 return new PredicateSimplifier();