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 optimization works by substituting %q for %p when protected by a
26 // conditional that assures us of that fact. Properties are stored as
27 // relationships between two values.
29 //===------------------------------------------------------------------===//
31 #define DEBUG_TYPE "predsimplify"
32 #include "llvm/Transforms/Scalar.h"
33 #include "llvm/Constants.h"
34 #include "llvm/Instructions.h"
35 #include "llvm/Pass.h"
36 #include "llvm/ADT/EquivalenceClasses.h"
37 #include "llvm/ADT/Statistic.h"
38 #include "llvm/ADT/STLExtras.h"
39 #include "llvm/Analysis/Dominators.h"
40 #include "llvm/Support/CFG.h"
41 #include "llvm/Support/Debug.h"
47 NumVarsReplaced("predsimplify", "Number of argument substitutions");
49 NumInstruction("predsimplify", "Number of instructions removed");
51 NumSwitchCases("predsimplify", "Number of switch cases removed");
53 NumBranches("predsimplify", "Number of branches made unconditional");
55 /// Used for choosing the canonical Value in a synonym set.
56 /// Leaves the better one in V1. Returns whether a swap took place.
57 static void order(Value *&V1, Value *&V2) {
58 if (isa<Constant>(V2)) {
59 if (!isa<Constant>(V1)) {
63 } else if (isa<Argument>(V2)) {
64 if (!isa<Constant>(V1) && !isa<Argument>(V1)) {
69 if (User *U1 = dyn_cast<User>(V1)) {
70 for (User::const_op_iterator I = U1->op_begin(), E = U1->op_end();
81 /// Represents the set of equivalent Value*s and provides insertion
82 /// and fast lookup. Also stores the set of inequality relationships.
85 class EquivalenceClasses<Value *> union_find;
87 typedef std::vector<Property>::iterator PropertyIterator;
88 typedef std::vector<Property>::const_iterator ConstPropertyIterator;
95 Value *canonicalize(Value *V) const {
100 Value *lookup(Value *V) const {
101 EquivalenceClasses<Value *>::member_iterator SI =
102 union_find.findLeader(V);
103 if (SI == union_find.member_end()) return NULL;
108 return union_find.empty();
111 void addEqual(Value *V1, Value *V2) {
112 // If %x = 0. and %y = -0., seteq %x, %y is true, but
113 // copysign(%x) is not the same as copysign(%y).
114 if (V2->getType()->isFloatingPoint()) return;
117 if (isa<Constant>(V2)) return; // refuse to set false == true.
119 DEBUG(std::cerr << "equal: " << *V1 << " and " << *V2 << "\n");
120 union_find.unionSets(V1, V2);
121 addImpliedProperties(EQ, V1, V2);
124 void addNotEqual(Value *V1, Value *V2) {
125 // If %x = NAN then seteq %x, %x is false.
126 if (V2->getType()->isFloatingPoint()) return;
128 DEBUG(std::cerr << "not equal: " << *V1 << " and " << *V2 << "\n");
129 if (findProperty(NE, V1, V2) != Properties.end())
133 Properties.push_back(Property(NE, V1, V2));
134 addImpliedProperties(NE, V1, V2);
137 PropertyIterator findProperty(Ops Opcode, Value *V1, Value *V2) {
138 assert(Opcode != EQ && "Can't findProperty on EQ."
139 "Use the lookup method instead.");
141 V1 = canonicalize(V1);
142 V2 = canonicalize(V2);
144 // Does the property already exist?
145 for (PropertyIterator I = Properties.begin(), E = Properties.end();
147 if (I->Opcode != Opcode) continue;
149 I->V1 = canonicalize(I->V1);
150 I->V2 = canonicalize(I->V2);
151 if ((I->V1 == V1 && I->V2 == V2) ||
152 (I->V1 == V2 && I->V2 == V1)) {
156 return Properties.end();
159 ConstPropertyIterator
160 findProperty(Ops Opcode, Value *V1, Value *V2) const {
161 assert(Opcode != EQ && "Can't findProperty on EQ."
162 "Use the lookup method instead.");
164 V1 = canonicalize(V1);
165 V2 = canonicalize(V2);
167 // Does the property already exist?
168 for (ConstPropertyIterator I = Properties.begin(),
169 E = Properties.end(); I != E; ++I) {
170 if (I->Opcode != Opcode) continue;
172 Value *v1 = canonicalize(I->V1),
173 *v2 = canonicalize(I->V2);
174 if ((v1 == V1 && v2 == V2) ||
175 (v1 == V2 && v2 == V1)) {
179 return Properties.end();
183 // Represents Head OP [Tail1, Tail2, ...]
184 // For example: %x != %a, %x != %b.
186 Property(Ops opcode, Value *v1, Value *v2)
187 : Opcode(opcode), V1(v1), V2(v2)
188 { assert(opcode != EQ && "Equality belongs in the synonym set, "
189 "not a property."); }
195 void add(Ops Opcode, Value *V1, Value *V2, bool invert) {
198 if (invert) addNotEqual(V1, V2);
199 else addEqual(V1, V2);
202 if (invert) addEqual(V1, V2);
203 else addNotEqual(V1, V2);
206 assert(0 && "Unknown property opcode.");
210 // Finds the properties implied by a equivalence and adds them too.
211 // Example: ("seteq %a, %b", true, EQ) --> (%a, %b, EQ)
212 // ("seteq %a, %b", false, EQ) --> (%a, %b, NE)
213 void addImpliedProperties(Ops Opcode, Value *V1, Value *V2) {
216 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V2)) {
217 switch (BO->getOpcode()) {
218 case Instruction::SetEQ:
219 if (V1 == ConstantBool::True)
220 add(Opcode, BO->getOperand(0), BO->getOperand(1), false);
221 if (V1 == ConstantBool::False)
222 add(Opcode, BO->getOperand(0), BO->getOperand(1), true);
224 case Instruction::SetNE:
225 if (V1 == ConstantBool::True)
226 add(Opcode, BO->getOperand(0), BO->getOperand(1), true);
227 if (V1 == ConstantBool::False)
228 add(Opcode, BO->getOperand(0), BO->getOperand(1), false);
230 case Instruction::SetLT:
231 case Instruction::SetGT:
232 if (V1 == ConstantBool::True)
233 add(Opcode, BO->getOperand(0), BO->getOperand(1), true);
235 case Instruction::SetLE:
236 case Instruction::SetGE:
237 if (V1 == ConstantBool::False)
238 add(Opcode, BO->getOperand(0), BO->getOperand(1), true);
240 case Instruction::And:
241 if (V1 == ConstantBool::True) {
242 add(Opcode, ConstantBool::True, BO->getOperand(0), false);
243 add(Opcode, ConstantBool::True, BO->getOperand(1), false);
246 case Instruction::Or:
247 if (V1 == ConstantBool::False) {
248 add(Opcode, ConstantBool::False, BO->getOperand(0), false);
249 add(Opcode, ConstantBool::False, BO->getOperand(1), false);
252 case Instruction::Xor:
253 if (V1 == ConstantBool::True) {
254 if (BO->getOperand(0) == ConstantBool::True)
255 add(Opcode, ConstantBool::False, BO->getOperand(1), false);
256 if (BO->getOperand(1) == ConstantBool::True)
257 add(Opcode, ConstantBool::False, BO->getOperand(0), false);
259 if (V1 == ConstantBool::False) {
260 if (BO->getOperand(0) == ConstantBool::True)
261 add(Opcode, ConstantBool::True, BO->getOperand(1), false);
262 if (BO->getOperand(1) == ConstantBool::True)
263 add(Opcode, ConstantBool::True, BO->getOperand(0), false);
269 } else if (SelectInst *SI = dyn_cast<SelectInst>(V2)) {
270 if (Opcode != EQ && Opcode != NE) return;
272 ConstantBool *True = (Opcode==EQ) ? ConstantBool::True
273 : ConstantBool::False,
274 *False = (Opcode==EQ) ? ConstantBool::False
275 : ConstantBool::True;
277 if (V1 == SI->getTrueValue())
278 addEqual(SI->getCondition(), True);
279 else if (V1 == SI->getFalseValue())
280 addEqual(SI->getCondition(), False);
281 else if (Opcode == EQ)
282 assert("Result of select not equal to either value.");
288 void debug(std::ostream &os) const {
289 for (EquivalenceClasses<Value*>::iterator I = union_find.begin(),
290 E = union_find.end(); I != E; ++I) {
291 if (!I->isLeader()) continue;
292 for (EquivalenceClasses<Value*>::member_iterator MI =
293 union_find.member_begin(I); MI != union_find.member_end(); ++MI)
294 std::cerr << **MI << " ";
295 std::cerr << "\n--\n";
300 std::vector<Property> Properties;
303 /// PredicateSimplifier - This class is a simplifier that replaces
304 /// one equivalent variable with another. It also tracks what
305 /// can't be equal and will solve setcc instructions when possible.
306 class PredicateSimplifier : public FunctionPass {
308 bool runOnFunction(Function &F);
309 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
312 // Try to replace the Use of the instruction with something simpler.
313 Value *resolve(SetCondInst *SCI, const PropertySet &);
314 Value *resolve(BinaryOperator *BO, const PropertySet &);
315 Value *resolve(SelectInst *SI, const PropertySet &);
316 Value *resolve(Value *V, const PropertySet &);
318 // Used by terminator instructions to proceed from the current basic
319 // block to the next. Verifies that "current" dominates "next",
320 // then calls visitBasicBlock.
321 void proceedToSuccessor(PropertySet &CurrentPS, PropertySet &NextPS,
322 DominatorTree::Node *Current, DominatorTree::Node *Next);
323 void proceedToSuccessor(PropertySet &CurrentPS,
324 DominatorTree::Node *Current, DominatorTree::Node *Next);
326 // Visits each instruction in the basic block.
327 void visitBasicBlock(DominatorTree::Node *DTNode,
328 PropertySet &KnownProperties);
330 // For each instruction, add the properties to KnownProperties.
331 void visit(Instruction *I, DominatorTree::Node *, PropertySet &);
332 void visit(TerminatorInst *TI, DominatorTree::Node *, PropertySet &);
333 void visit(BranchInst *BI, DominatorTree::Node *, PropertySet &);
334 void visit(SwitchInst *SI, DominatorTree::Node *, PropertySet);
335 void visit(LoadInst *LI, DominatorTree::Node *, PropertySet &);
336 void visit(StoreInst *SI, DominatorTree::Node *, PropertySet &);
337 void visit(BinaryOperator *BO, DominatorTree::Node *, PropertySet &);
343 RegisterPass<PredicateSimplifier> X("predsimplify",
344 "Predicate Simplifier");
347 FunctionPass *llvm::createPredicateSimplifierPass() {
348 return new PredicateSimplifier();
351 bool PredicateSimplifier::runOnFunction(Function &F) {
352 DT = &getAnalysis<DominatorTree>();
355 PropertySet KnownProperties;
356 visitBasicBlock(DT->getRootNode(), KnownProperties);
360 void PredicateSimplifier::getAnalysisUsage(AnalysisUsage &AU) const {
361 AU.addRequired<DominatorTree>();
364 // resolve catches cases addProperty won't because it wasn't used as a
365 // condition in the branch, and that visit won't, because the instruction
366 // was defined outside of the scope that the properties apply to.
367 Value *PredicateSimplifier::resolve(SetCondInst *SCI,
368 const PropertySet &KP) {
369 // Attempt to resolve the SetCondInst to a boolean.
371 Value *SCI0 = resolve(SCI->getOperand(0), KP),
372 *SCI1 = resolve(SCI->getOperand(1), KP);
373 PropertySet::ConstPropertyIterator NE =
374 KP.findProperty(PropertySet::NE, SCI0, SCI1);
376 if (NE != KP.Properties.end()) {
377 switch (SCI->getOpcode()) {
378 case Instruction::SetEQ:
379 return ConstantBool::False;
380 case Instruction::SetNE:
381 return ConstantBool::True;
382 case Instruction::SetLE:
383 case Instruction::SetGE:
384 case Instruction::SetLT:
385 case Instruction::SetGT:
388 assert(0 && "Unknown opcode in SetCondInst.");
393 ConstantIntegral *CI1 = dyn_cast<ConstantIntegral>(SCI0),
394 *CI2 = dyn_cast<ConstantIntegral>(SCI1);
396 if (!CI1 || !CI2) return SCI;
398 switch(SCI->getOpcode()) {
399 case Instruction::SetLE:
400 case Instruction::SetGE:
401 case Instruction::SetEQ:
402 if (CI1->getRawValue() == CI2->getRawValue())
403 return ConstantBool::True;
405 return ConstantBool::False;
406 case Instruction::SetLT:
407 case Instruction::SetGT:
408 case Instruction::SetNE:
409 if (CI1->getRawValue() == CI2->getRawValue())
410 return ConstantBool::False;
412 return ConstantBool::True;
414 assert(0 && "Unknown opcode in SetContInst.");
419 Value *PredicateSimplifier::resolve(BinaryOperator *BO,
420 const PropertySet &KP) {
421 if (SetCondInst *SCI = dyn_cast<SetCondInst>(BO))
422 return resolve(SCI, KP);
424 DEBUG(std::cerr << "BO->getOperand(1) = " << *BO->getOperand(1) << "\n");
426 Value *lhs = resolve(BO->getOperand(0), KP),
427 *rhs = resolve(BO->getOperand(1), KP);
428 ConstantIntegral *CI1 = dyn_cast<ConstantIntegral>(lhs);
429 ConstantIntegral *CI2 = dyn_cast<ConstantIntegral>(rhs);
431 DEBUG(std::cerr << "resolveBO: lhs = " << *lhs
432 << ", rhs = " << *rhs << "\n");
433 if (CI1) DEBUG(std::cerr << "CI1 = " << *CI1);
434 if (CI2) DEBUG(std::cerr << "CI2 = " << *CI2);
436 if (!CI1 || !CI2) return BO;
438 Value *V = ConstantExpr::get(BO->getOpcode(), CI1, CI2);
443 Value *PredicateSimplifier::resolve(SelectInst *SI, const PropertySet &KP) {
444 Value *Condition = resolve(SI->getCondition(), KP);
445 if (Condition == ConstantBool::True)
446 return resolve(SI->getTrueValue(), KP);
447 else if (Condition == ConstantBool::False)
448 return resolve(SI->getFalseValue(), KP);
452 Value *PredicateSimplifier::resolve(Value *V, const PropertySet &KP) {
453 if (isa<Constant>(V) || isa<BasicBlock>(V) || KP.empty()) return V;
455 V = KP.canonicalize(V);
457 DEBUG(std::cerr << "peering into " << *V << "\n");
459 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V))
460 return resolve(BO, KP);
461 else if (SelectInst *SI = dyn_cast<SelectInst>(V))
462 return resolve(SI, KP);
467 void PredicateSimplifier::visitBasicBlock(DominatorTree::Node *DTNode,
468 PropertySet &KnownProperties) {
469 BasicBlock *BB = DTNode->getBlock();
470 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
471 visit(I, DTNode, KnownProperties);
475 void PredicateSimplifier::visit(Instruction *I, DominatorTree::Node *DTNode,
476 PropertySet &KnownProperties) {
477 DEBUG(std::cerr << "Considering instruction " << *I << "\n");
478 DEBUG(KnownProperties.debug(std::cerr));
480 // Try to replace whole instruction.
481 Value *V = resolve(I, KnownProperties);
482 assert(V && "resolve not supposed to return NULL.");
486 I->replaceAllUsesWith(V);
487 I->eraseFromParent();
491 // Try to substitute operands.
492 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
493 Value *Oper = I->getOperand(i);
494 Value *V = resolve(Oper, KnownProperties);
495 assert(V && "resolve not supposed to return NULL.");
499 DEBUG(std::cerr << "resolving " << *I);
501 DEBUG(std::cerr << "into " << *I);
505 if (TerminatorInst *TI = dyn_cast<TerminatorInst>(I))
506 visit(TI, DTNode, KnownProperties);
507 else if (LoadInst *LI = dyn_cast<LoadInst>(I))
508 visit(LI, DTNode, KnownProperties);
509 else if (StoreInst *SI = dyn_cast<StoreInst>(I))
510 visit(SI, DTNode, KnownProperties);
511 else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I))
512 visit(BO, DTNode, KnownProperties);
515 void PredicateSimplifier::proceedToSuccessor(PropertySet &CurrentPS,
516 PropertySet &NextPS, DominatorTree::Node *Current,
517 DominatorTree::Node *Next) {
518 if (Next->getBlock()->getSinglePredecessor() == Current->getBlock())
519 proceedToSuccessor(NextPS, Current, Next);
521 proceedToSuccessor(CurrentPS, Current, Next);
524 void PredicateSimplifier::proceedToSuccessor(PropertySet &KP,
525 DominatorTree::Node *Current, DominatorTree::Node *Next) {
526 if (Current->properlyDominates(Next))
527 visitBasicBlock(Next, KP);
530 void PredicateSimplifier::visit(TerminatorInst *TI,
531 DominatorTree::Node *Node, PropertySet &KP){
532 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
536 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
541 for (unsigned i = 0, E = TI->getNumSuccessors(); i != E; ++i) {
542 BasicBlock *BB = TI->getSuccessor(i);
543 PropertySet KPcopy(KP);
544 proceedToSuccessor(KPcopy, Node, DT->getNode(TI->getSuccessor(i)));
548 void PredicateSimplifier::visit(BranchInst *BI,
549 DominatorTree::Node *Node, PropertySet &KP){
550 if (BI->isUnconditional()) {
551 proceedToSuccessor(KP, Node, DT->getNode(BI->getSuccessor(0)));
555 Value *Condition = BI->getCondition();
557 BasicBlock *TrueDest = BI->getSuccessor(0),
558 *FalseDest = BI->getSuccessor(1);
560 if (Condition == ConstantBool::True) {
561 FalseDest->removePredecessor(BI->getParent());
562 BI->setUnconditionalDest(TrueDest);
565 proceedToSuccessor(KP, Node, DT->getNode(TrueDest));
567 } else if (Condition == ConstantBool::False) {
568 TrueDest->removePredecessor(BI->getParent());
569 BI->setUnconditionalDest(FalseDest);
572 proceedToSuccessor(KP, Node, DT->getNode(FalseDest));
576 PropertySet TrueProperties(KP), FalseProperties(KP);
577 DEBUG(std::cerr << "true set:\n");
578 TrueProperties.addEqual(ConstantBool::True, Condition);
579 DEBUG(TrueProperties.debug(std::cerr));
580 DEBUG(std::cerr << "false set:\n");
581 FalseProperties.addEqual(ConstantBool::False, Condition);
582 DEBUG(FalseProperties.debug(std::cerr));
584 PropertySet KPcopy(KP);
585 proceedToSuccessor(KP, TrueProperties, Node, DT->getNode(TrueDest));
586 proceedToSuccessor(KPcopy, FalseProperties, Node, DT->getNode(FalseDest));
589 void PredicateSimplifier::visit(SwitchInst *SI,
590 DominatorTree::Node *DTNode, PropertySet KP) {
591 Value *Condition = SI->getCondition();
592 DEBUG(assert(Condition == KP.canonicalize(Condition) &&
593 "Instruction wasn't already canonicalized?"));
595 // If there's an NEProperty covering this SwitchInst, we may be able to
596 // eliminate one of the cases.
597 for (PropertySet::ConstPropertyIterator I = KP.Properties.begin(),
598 E = KP.Properties.end(); I != E; ++I) {
599 if (I->Opcode != PropertySet::NE) continue;
600 Value *V1 = KP.canonicalize(I->V1),
601 *V2 = KP.canonicalize(I->V2);
602 if (V1 != Condition && V2 != Condition) continue;
604 // Is one side a number?
605 ConstantInt *CI = dyn_cast<ConstantInt>(KP.canonicalize(I->V1));
606 if (!CI) CI = dyn_cast<ConstantInt>(KP.canonicalize(I->V2));
609 unsigned i = SI->findCaseValue(CI);
611 SI->getSuccessor(i)->removePredecessor(SI->getParent());
619 // Set the EQProperty in each of the cases BBs,
620 // and the NEProperties in the default BB.
621 PropertySet DefaultProperties(KP);
623 DominatorTree::Node *Node = DT->getNode(SI->getParent()),
624 *DefaultNode = DT->getNode(SI->getSuccessor(0));
625 if (!Node->dominates(DefaultNode)) DefaultNode = NULL;
627 for (unsigned I = 1, E = SI->getNumCases(); I < E; ++I) {
628 ConstantInt *CI = SI->getCaseValue(I);
630 BasicBlock *SuccBB = SI->getSuccessor(I);
631 PropertySet copy(KP);
632 if (SuccBB->getSinglePredecessor()) {
633 PropertySet NewProperties(KP);
634 NewProperties.addEqual(Condition, CI);
635 proceedToSuccessor(copy, NewProperties, DTNode, DT->getNode(SuccBB));
637 proceedToSuccessor(copy, DTNode, DT->getNode(SuccBB));
640 DefaultProperties.addNotEqual(Condition, CI);
644 proceedToSuccessor(DefaultProperties, DTNode, DefaultNode);
647 void PredicateSimplifier::visit(LoadInst *LI,
648 DominatorTree::Node *, PropertySet &KP) {
649 Value *Ptr = LI->getPointerOperand();
650 KP.addNotEqual(Constant::getNullValue(Ptr->getType()), Ptr);
653 void PredicateSimplifier::visit(StoreInst *SI,
654 DominatorTree::Node *, PropertySet &KP) {
655 Value *Ptr = SI->getPointerOperand();
656 KP.addNotEqual(Constant::getNullValue(Ptr->getType()), Ptr);
659 void PredicateSimplifier::visit(BinaryOperator *BO,
660 DominatorTree::Node *, PropertySet &KP) {
661 Instruction::BinaryOps ops = BO->getOpcode();
664 case Instruction::Div:
665 case Instruction::Rem: {
666 Value *Divisor = BO->getOperand(1);
667 KP.addNotEqual(Constant::getNullValue(Divisor->getType()), Divisor);
674 // Some other things we could do:
675 // In f=x*y, if x != 1 && y != 1 then f != x && f != y.
676 // In f=x+y, if x != 0 then f != y and if y != 0 then f != x.