1 //===------- ABCD.cpp - Removes redundant conditional branches ------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass removes redundant branch instructions. This algorithm was
11 // described by Rastislav Bodik, Rajiv Gupta and Vivek Sarkar in their paper
12 // "ABCD: Eliminating Array Bounds Checks on Demand (2000)". The original
13 // Algorithm was created to remove array bound checks for strongly typed
14 // languages. This implementation expands the idea and removes any conditional
15 // branches that can be proved redundant, not only those used in array bound
16 // checks. With the SSI representation, each variable has a
17 // constraint. By analyzing these constraints we can prove that a branch is
18 // redundant. When a branch is proved redundant it means that
19 // one direction will always be taken; thus, we can change this branch into an
20 // unconditional jump.
21 // It is advisable to run SimplifyCFG and Aggressive Dead Code Elimination
22 // after ABCD to clean up the code.
23 // This implementation was created based on the implementation of the ABCD
24 // algorithm implemented for the compiler Jitrino.
26 //===----------------------------------------------------------------------===//
28 #define DEBUG_TYPE "abcd"
29 #include "llvm/ADT/DenseMap.h"
30 #include "llvm/ADT/SmallPtrSet.h"
31 #include "llvm/ADT/Statistic.h"
32 #include "llvm/Constants.h"
33 #include "llvm/Function.h"
34 #include "llvm/Instructions.h"
35 #include "llvm/Pass.h"
36 #include "llvm/Support/raw_ostream.h"
37 #include "llvm/Support/Debug.h"
38 #include "llvm/Transforms/Scalar.h"
39 #include "llvm/Transforms/Utils/SSI.h"
43 STATISTIC(NumBranchTested, "Number of conditional branches analyzed");
44 STATISTIC(NumBranchRemoved, "Number of conditional branches removed");
48 class ABCD : public FunctionPass {
50 static char ID; // Pass identification, replacement for typeid.
51 ABCD() : FunctionPass(&ID) {}
53 void getAnalysisUsage(AnalysisUsage &AU) const {
54 AU.addRequired<SSI>();
57 bool runOnFunction(Function &F);
60 /// Keep track of whether we've modified the program yet.
69 typedef ProveResult (*meet_function)(ProveResult, ProveResult);
70 static ProveResult max(ProveResult res1, ProveResult res2) {
71 return (ProveResult) std::max(res1, res2);
73 static ProveResult min(ProveResult res1, ProveResult res2) {
74 return (ProveResult) std::min(res1, res2);
79 Bound(APInt v, bool upper) : value(v), upper_bound(upper) {}
80 Bound(const Bound *b, int cnst)
81 : value(b->value - cnst), upper_bound(b->upper_bound) {}
82 Bound(const Bound *b, const APInt &cnst)
83 : value(b->value - cnst), upper_bound(b->upper_bound) {}
85 /// Test if Bound is an upper bound
86 bool isUpperBound() const { return upper_bound; }
88 /// Get the bitwidth of this bound
89 int32_t getBitWidth() const { return value.getBitWidth(); }
91 /// Creates a Bound incrementing the one received
92 static Bound *createIncrement(const Bound *b) {
93 return new Bound(b->isUpperBound() ? b->value+1 : b->value-1,
97 /// Creates a Bound decrementing the one received
98 static Bound *createDecrement(const Bound *b) {
99 return new Bound(b->isUpperBound() ? b->value-1 : b->value+1,
103 /// Test if two bounds are equal
104 static bool eq(const Bound *a, const Bound *b) {
105 if (!a || !b) return false;
107 assert(a->isUpperBound() == b->isUpperBound());
108 return a->value == b->value;
111 /// Test if val is less than or equal to Bound b
112 static bool leq(APInt val, const Bound *b) {
113 if (!b) return false;
114 return b->isUpperBound() ? val.sle(b->value) : val.sge(b->value);
117 /// Test if Bound a is less then or equal to Bound
118 static bool leq(const Bound *a, const Bound *b) {
119 if (!a || !b) return false;
121 assert(a->isUpperBound() == b->isUpperBound());
122 return a->isUpperBound() ? a->value.sle(b->value) :
123 a->value.sge(b->value);
126 /// Test if Bound a is less then Bound b
127 static bool lt(const Bound *a, const Bound *b) {
128 if (!a || !b) return false;
130 assert(a->isUpperBound() == b->isUpperBound());
131 return a->isUpperBound() ? a->value.slt(b->value) :
132 a->value.sgt(b->value);
135 /// Test if Bound b is greater then or equal val
136 static bool geq(const Bound *b, APInt val) {
140 /// Test if Bound a is greater then or equal Bound b
141 static bool geq(const Bound *a, const Bound *b) {
150 /// This class is used to store results some parts of the graph,
151 /// so information does not need to be recalculated. The maximum false,
152 /// minimum true and minimum reduced results are stored
153 class MemoizedResultChart {
155 MemoizedResultChart()
156 : max_false(NULL), min_true(NULL), min_reduced(NULL) {}
158 /// Returns the max false
159 Bound *getFalse() const { return max_false; }
161 /// Returns the min true
162 Bound *getTrue() const { return min_true; }
164 /// Returns the min reduced
165 Bound *getReduced() const { return min_reduced; }
167 /// Return the stored result for this bound
168 ProveResult getResult(const Bound *bound) const;
170 /// Stores a false found
171 void addFalse(Bound *bound);
173 /// Stores a true found
174 void addTrue(Bound *bound);
176 /// Stores a Reduced found
177 void addReduced(Bound *bound);
179 /// Clears redundant reduced
180 /// If a min_true is smaller than a min_reduced then the min_reduced
181 /// is unnecessary and then removed. It also works for min_reduced
182 /// begin smaller than max_false.
183 void clearRedundantReduced();
192 Bound *max_false, *min_true, *min_reduced;
195 /// This class stores the result found for a node of the graph,
196 /// so these results do not need to be recalculated, only searched for.
197 class MemoizedResult {
199 /// Test if there is true result stored from b to a
200 /// that is less then the bound
201 bool hasTrue(Value *b, const Bound *bound) const {
202 Bound *trueBound = map.lookup(b).getTrue();
203 return trueBound && Bound::leq(trueBound, bound);
206 /// Test if there is false result stored from b to a
207 /// that is less then the bound
208 bool hasFalse(Value *b, const Bound *bound) const {
209 Bound *falseBound = map.lookup(b).getFalse();
210 return falseBound && Bound::leq(falseBound, bound);
213 /// Test if there is reduced result stored from b to a
214 /// that is less then the bound
215 bool hasReduced(Value *b, const Bound *bound) const {
216 Bound *reducedBound = map.lookup(b).getReduced();
217 return reducedBound && Bound::leq(reducedBound, bound);
220 /// Returns the stored bound for b
221 ProveResult getBoundResult(Value *b, Bound *bound) {
222 return map[b].getResult(bound);
227 DenseMapIterator<Value*, MemoizedResultChart> begin = map.begin();
228 DenseMapIterator<Value*, MemoizedResultChart> end = map.end();
229 for (; begin != end; ++begin) {
230 begin->second.clear();
235 /// Stores the bound found
236 void updateBound(Value *b, Bound *bound, const ProveResult res);
239 // Maps a nod in the graph with its results found.
240 DenseMap<Value*, MemoizedResultChart> map;
243 /// This class represents an edge in the inequality graph used by the
244 /// ABCD algorithm. An edge connects node v to node u with a value c if
245 /// we could infer a constraint v <= u + c in the source program.
248 Edge(Value *V, APInt val, bool upper)
249 : vertex(V), value(val), upper_bound(upper) {}
251 Value *getVertex() const { return vertex; }
252 const APInt &getValue() const { return value; }
253 bool isUpperBound() const { return upper_bound; }
261 /// Weighted and Directed graph to represent constraints.
262 /// There is one type of constraint, a <= b + X, which will generate an
263 /// edge from b to a with weight X.
264 class InequalityGraph {
267 /// Adds an edge from V_from to V_to with weight value
268 void addEdge(Value *V_from, Value *V_to, APInt value, bool upper);
270 /// Test if there is a node V
271 bool hasNode(Value *V) const { return graph.count(V); }
273 /// Test if there is any edge from V in the upper direction
274 bool hasEdge(Value *V, bool upper) const;
276 /// Returns all edges pointed by vertex V
277 SmallPtrSet<Edge *, 16> getEdges(Value *V) const {
278 return graph.lookup(V);
281 /// Prints the graph in dot format.
282 /// Blue edges represent upper bound and Red lower bound.
283 void printGraph(raw_ostream &OS, Function &F) const {
295 DenseMap<Value *, SmallPtrSet<Edge *, 16> > graph;
297 /// Adds a Node to the graph.
298 DenseMap<Value *, SmallPtrSet<Edge *, 16> >::iterator addNode(Value *V) {
299 SmallPtrSet<Edge *, 16> p;
300 return graph.insert(std::make_pair(V, p)).first;
303 /// Prints the header of the dot file
304 void printHeader(raw_ostream &OS, Function &F) const;
306 /// Prints the footer of the dot file
307 void printFooter(raw_ostream &OS) const {
311 /// Prints the body of the dot file
312 void printBody(raw_ostream &OS) const;
314 /// Prints vertex source to the dot file
315 void printVertex(raw_ostream &OS, Value *source) const;
317 /// Prints the edge to the dot file
318 void printEdge(raw_ostream &OS, Value *source, Edge *edge) const;
320 void printName(raw_ostream &OS, Value *info) const;
323 /// Iterates through all BasicBlocks, if the Terminator Instruction
324 /// uses an Comparator Instruction, all operands of this comparator
325 /// are sent to be transformed to SSI. Only Instruction operands are
327 void createSSI(Function &F);
329 /// Creates the graphs for this function.
330 /// It will look for all comparators used in branches, and create them.
331 /// These comparators will create constraints for any instruction as an
333 void executeABCD(Function &F);
335 /// Seeks redundancies in the comparator instruction CI.
336 /// If the ABCD algorithm can prove that the comparator CI always
337 /// takes one way, then the Terminator Instruction TI is substituted from
338 /// a conditional branch to a unconditional one.
339 /// This code basically receives a comparator, and verifies which kind of
340 /// instruction it is. Depending on the kind of instruction, we use different
341 /// strategies to prove its redundancy.
342 void seekRedundancy(ICmpInst *ICI, TerminatorInst *TI);
344 /// Substitutes Terminator Instruction TI, that is a conditional branch,
345 /// with one unconditional branch. Succ_edge determines if the new
346 /// unconditional edge will be the first or second edge of the former TI
348 void removeRedundancy(TerminatorInst *TI, bool Succ_edge);
350 /// When an conditional branch is removed, the BasicBlock that is no longer
351 /// reachable will have problems in phi functions. This method fixes these
352 /// phis removing the former BasicBlock from the list of incoming BasicBlocks
353 /// of all phis. In case the phi remains with no predecessor it will be
354 /// marked to be removed later.
355 void fixPhi(BasicBlock *BB, BasicBlock *Succ);
357 /// Removes phis that have no predecessor
360 /// Creates constraints for Instructions.
361 /// If the constraint for this instruction has already been created
363 void createConstraintInstruction(Instruction *I);
365 /// Creates constraints for Binary Operators.
366 /// It will create constraints only for addition and subtraction,
367 /// the other binary operations are not treated by ABCD.
368 /// For additions in the form a = b + X and a = X + b, where X is a constant,
369 /// the constraint a <= b + X can be obtained. For this constraint, an edge
370 /// a->b with weight X is added to the lower bound graph, and an edge
371 /// b->a with weight -X is added to the upper bound graph.
372 /// Only subtractions in the format a = b - X is used by ABCD.
373 /// Edges are created using the same semantic as addition.
374 void createConstraintBinaryOperator(BinaryOperator *BO);
376 /// Creates constraints for Comparator Instructions.
377 /// Only comparators that have any of the following operators
378 /// are used to create constraints: >=, >, <=, <. And only if
379 /// at least one operand is an Instruction. In a Comparator Instruction
380 /// a op b, there will be 4 sigma functions a_t, a_f, b_t and b_f. Where
381 /// t and f represent sigma for operands in true and false branches. The
382 /// following constraints can be obtained. a_t <= a, a_f <= a, b_t <= b and
383 /// b_f <= b. There are two more constraints that depend on the operator.
384 /// For the operator <= : a_t <= b_t and b_f <= a_f-1
385 /// For the operator < : a_t <= b_t-1 and b_f <= a_f
386 /// For the operator >= : b_t <= a_t and a_f <= b_f-1
387 /// For the operator > : b_t <= a_t-1 and a_f <= b_f
388 void createConstraintCmpInst(ICmpInst *ICI, TerminatorInst *TI);
390 /// Creates constraints for PHI nodes.
391 /// In a PHI node a = phi(b,c) we can create the constraint
392 /// a<= max(b,c). With this constraint there will be the edges,
393 /// b->a and c->a with weight 0 in the lower bound graph, and the edges
394 /// a->b and a->c with weight 0 in the upper bound graph.
395 void createConstraintPHINode(PHINode *PN);
397 /// Given a binary operator, we are only interest in the case
398 /// that one operand is an Instruction and the other is a ConstantInt. In
399 /// this case the method returns true, otherwise false. It also obtains the
400 /// Instruction and ConstantInt from the BinaryOperator and returns it.
401 bool createBinaryOperatorInfo(BinaryOperator *BO, Instruction **I1,
402 Instruction **I2, ConstantInt **C1,
405 /// This method creates a constraint between a Sigma and an Instruction.
406 /// These constraints are created as soon as we find a comparator that uses a
408 void createConstraintSigInst(Instruction *I_op, BasicBlock *BB_succ_t,
409 BasicBlock *BB_succ_f, PHINode **SIG_op_t,
412 /// If PN_op1 and PN_o2 are different from NULL, create a constraint
413 /// PN_op2 -> PN_op1 with value. In case any of them is NULL, replace
414 /// with the respective V_op#, if V_op# is a ConstantInt.
415 void createConstraintSigSig(PHINode *SIG_op1, PHINode *SIG_op2,
416 ConstantInt *V_op1, ConstantInt *V_op2,
419 /// Returns the sigma representing the Instruction I in BasicBlock BB.
420 /// Returns NULL in case there is no sigma for this Instruction in this
421 /// Basic Block. This methods assume that sigmas are the first instructions
422 /// in a block, and that there can be only two sigmas in a block. So it will
423 /// only look on the first two instructions of BasicBlock BB.
424 PHINode *findSigma(BasicBlock *BB, Instruction *I);
426 /// Original ABCD algorithm to prove redundant checks.
427 /// This implementation works on any kind of inequality branch.
428 bool demandProve(Value *a, Value *b, int c, bool upper_bound);
430 /// Prove that distance between b and a is <= bound
431 ProveResult prove(Value *a, Value *b, Bound *bound, unsigned level);
433 /// Updates the distance value for a and b
434 void updateMemDistance(Value *a, Value *b, Bound *bound, unsigned level,
437 InequalityGraph inequality_graph;
438 MemoizedResult mem_result;
439 DenseMap<Value*, Bound*> active;
440 SmallPtrSet<Value*, 16> created;
441 SmallVector<PHINode *, 16> phis_to_remove;
444 } // end anonymous namespace.
447 static RegisterPass<ABCD> X("abcd", "ABCD: Eliminating Array Bounds Checks on Demand");
450 bool ABCD::runOnFunction(Function &F) {
454 DEBUG(inequality_graph.printGraph(errs(), F));
457 inequality_graph.clear();
461 phis_to_remove.clear();
465 /// Iterates through all BasicBlocks, if the Terminator Instruction
466 /// uses an Comparator Instruction, all operands of this comparator
467 /// are sent to be transformed to SSI. Only Instruction operands are
469 void ABCD::createSSI(Function &F) {
470 SSI *ssi = &getAnalysis<SSI>();
472 SmallVector<Instruction *, 16> Insts;
474 for (Function::iterator begin = F.begin(), end = F.end();
475 begin != end; ++begin) {
476 BasicBlock *BB = begin;
477 TerminatorInst *TI = BB->getTerminator();
478 if (TI->getNumOperands() == 0)
481 if (ICmpInst *ICI = dyn_cast<ICmpInst>(TI->getOperand(0))) {
482 if (Instruction *I = dyn_cast<Instruction>(ICI->getOperand(0))) {
483 modified = true; // XXX: but yet createSSI might do nothing
486 if (Instruction *I = dyn_cast<Instruction>(ICI->getOperand(1))) {
492 ssi->createSSI(Insts);
495 /// Creates the graphs for this function.
496 /// It will look for all comparators used in branches, and create them.
497 /// These comparators will create constraints for any instruction as an
499 void ABCD::executeABCD(Function &F) {
500 for (Function::iterator begin = F.begin(), end = F.end();
501 begin != end; ++begin) {
502 BasicBlock *BB = begin;
503 TerminatorInst *TI = BB->getTerminator();
504 if (TI->getNumOperands() == 0)
507 ICmpInst *ICI = dyn_cast<ICmpInst>(TI->getOperand(0));
508 if (!ICI || !isa<IntegerType>(ICI->getOperand(0)->getType()))
511 createConstraintCmpInst(ICI, TI);
512 seekRedundancy(ICI, TI);
516 /// Seeks redundancies in the comparator instruction CI.
517 /// If the ABCD algorithm can prove that the comparator CI always
518 /// takes one way, then the Terminator Instruction TI is substituted from
519 /// a conditional branch to a unconditional one.
520 /// This code basically receives a comparator, and verifies which kind of
521 /// instruction it is. Depending on the kind of instruction, we use different
522 /// strategies to prove its redundancy.
523 void ABCD::seekRedundancy(ICmpInst *ICI, TerminatorInst *TI) {
524 CmpInst::Predicate Pred = ICI->getPredicate();
526 Value *source, *dest;
527 int distance1, distance2;
531 case CmpInst::ICMP_SGT: // signed greater than
537 case CmpInst::ICMP_SGE: // signed greater or equal
543 case CmpInst::ICMP_SLT: // signed less than
549 case CmpInst::ICMP_SLE: // signed less or equal
560 source = ICI->getOperand(0);
561 dest = ICI->getOperand(1);
562 if (demandProve(dest, source, distance1, upper)) {
563 removeRedundancy(TI, true);
564 } else if (demandProve(dest, source, distance2, !upper)) {
565 removeRedundancy(TI, false);
569 /// Substitutes Terminator Instruction TI, that is a conditional branch,
570 /// with one unconditional branch. Succ_edge determines if the new
571 /// unconditional edge will be the first or second edge of the former TI
573 void ABCD::removeRedundancy(TerminatorInst *TI, bool Succ_edge) {
576 Succ = TI->getSuccessor(0);
577 fixPhi(TI->getParent(), TI->getSuccessor(1));
579 Succ = TI->getSuccessor(1);
580 fixPhi(TI->getParent(), TI->getSuccessor(0));
583 BranchInst::Create(Succ, TI);
584 TI->eraseFromParent(); // XXX: invoke
589 /// When an conditional branch is removed, the BasicBlock that is no longer
590 /// reachable will have problems in phi functions. This method fixes these
591 /// phis removing the former BasicBlock from the list of incoming BasicBlocks
592 /// of all phis. In case the phi remains with no predecessor it will be
593 /// marked to be removed later.
594 void ABCD::fixPhi(BasicBlock *BB, BasicBlock *Succ) {
595 BasicBlock::iterator begin = Succ->begin();
596 while (PHINode *PN = dyn_cast<PHINode>(begin++)) {
597 PN->removeIncomingValue(BB, false);
598 if (PN->getNumIncomingValues() == 0)
599 phis_to_remove.push_back(PN);
603 /// Removes phis that have no predecessor
604 void ABCD::removePhis() {
605 for (unsigned i = 0, e = phis_to_remove.size(); i != e; ++i) {
606 PHINode *PN = phis_to_remove[i];
607 PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
608 PN->eraseFromParent();
612 /// Creates constraints for Instructions.
613 /// If the constraint for this instruction has already been created
615 void ABCD::createConstraintInstruction(Instruction *I) {
616 // Test if this instruction has not been created before
617 if (created.insert(I)) {
618 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
619 createConstraintBinaryOperator(BO);
620 } else if (PHINode *PN = dyn_cast<PHINode>(I)) {
621 createConstraintPHINode(PN);
626 /// Creates constraints for Binary Operators.
627 /// It will create constraints only for addition and subtraction,
628 /// the other binary operations are not treated by ABCD.
629 /// For additions in the form a = b + X and a = X + b, where X is a constant,
630 /// the constraint a <= b + X can be obtained. For this constraint, an edge
631 /// a->b with weight X is added to the lower bound graph, and an edge
632 /// b->a with weight -X is added to the upper bound graph.
633 /// Only subtractions in the format a = b - X is used by ABCD.
634 /// Edges are created using the same semantic as addition.
635 void ABCD::createConstraintBinaryOperator(BinaryOperator *BO) {
636 Instruction *I1 = NULL, *I2 = NULL;
637 ConstantInt *CI1 = NULL, *CI2 = NULL;
639 // Test if an operand is an Instruction and the other is a Constant
640 if (!createBinaryOperatorInfo(BO, &I1, &I2, &CI1, &CI2))
646 switch (BO->getOpcode()) {
647 case Instruction::Add:
650 value = CI2->getValue();
653 value = CI1->getValue();
657 case Instruction::Sub:
658 // Instructions like a = X-b, where X is a constant are not represented
664 value = -CI2->getValue();
671 inequality_graph.addEdge(I, BO, value, true);
672 inequality_graph.addEdge(BO, I, -value, false);
673 createConstraintInstruction(I);
676 /// Given a binary operator, we are only interest in the case
677 /// that one operand is an Instruction and the other is a ConstantInt. In
678 /// this case the method returns true, otherwise false. It also obtains the
679 /// Instruction and ConstantInt from the BinaryOperator and returns it.
680 bool ABCD::createBinaryOperatorInfo(BinaryOperator *BO, Instruction **I1,
681 Instruction **I2, ConstantInt **C1,
683 Value *op1 = BO->getOperand(0);
684 Value *op2 = BO->getOperand(1);
686 if ((*I1 = dyn_cast<Instruction>(op1))) {
687 if ((*C2 = dyn_cast<ConstantInt>(op2)))
688 return true; // First is Instruction and second ConstantInt
690 return false; // Both are Instruction
692 if ((*C1 = dyn_cast<ConstantInt>(op1)) &&
693 (*I2 = dyn_cast<Instruction>(op2)))
694 return true; // First is ConstantInt and second Instruction
696 return false; // Both are not Instruction
700 /// Creates constraints for Comparator Instructions.
701 /// Only comparators that have any of the following operators
702 /// are used to create constraints: >=, >, <=, <. And only if
703 /// at least one operand is an Instruction. In a Comparator Instruction
704 /// a op b, there will be 4 sigma functions a_t, a_f, b_t and b_f. Where
705 /// t and f represent sigma for operands in true and false branches. The
706 /// following constraints can be obtained. a_t <= a, a_f <= a, b_t <= b and
707 /// b_f <= b. There are two more constraints that depend on the operator.
708 /// For the operator <= : a_t <= b_t and b_f <= a_f-1
709 /// For the operator < : a_t <= b_t-1 and b_f <= a_f
710 /// For the operator >= : b_t <= a_t and a_f <= b_f-1
711 /// For the operator > : b_t <= a_t-1 and a_f <= b_f
712 void ABCD::createConstraintCmpInst(ICmpInst *ICI, TerminatorInst *TI) {
713 Value *V_op1 = ICI->getOperand(0);
714 Value *V_op2 = ICI->getOperand(1);
716 if (!isa<IntegerType>(V_op1->getType()))
719 Instruction *I_op1 = dyn_cast<Instruction>(V_op1);
720 Instruction *I_op2 = dyn_cast<Instruction>(V_op2);
722 // Test if at least one operand is an Instruction
723 if (!I_op1 && !I_op2)
726 BasicBlock *BB_succ_t = TI->getSuccessor(0);
727 BasicBlock *BB_succ_f = TI->getSuccessor(1);
729 PHINode *SIG_op1_t = NULL, *SIG_op1_f = NULL,
730 *SIG_op2_t = NULL, *SIG_op2_f = NULL;
732 createConstraintSigInst(I_op1, BB_succ_t, BB_succ_f, &SIG_op1_t, &SIG_op1_f);
733 createConstraintSigInst(I_op2, BB_succ_t, BB_succ_f, &SIG_op2_t, &SIG_op2_f);
735 int32_t width = cast<IntegerType>(V_op1->getType())->getBitWidth();
736 APInt MinusOne = APInt::getAllOnesValue(width);
737 APInt Zero = APInt::getNullValue(width);
739 CmpInst::Predicate Pred = ICI->getPredicate();
740 ConstantInt *CI1 = dyn_cast<ConstantInt>(V_op1);
741 ConstantInt *CI2 = dyn_cast<ConstantInt>(V_op2);
743 case CmpInst::ICMP_SGT: // signed greater than
744 createConstraintSigSig(SIG_op2_t, SIG_op1_t, CI2, CI1, MinusOne);
745 createConstraintSigSig(SIG_op1_f, SIG_op2_f, CI1, CI2, Zero);
748 case CmpInst::ICMP_SGE: // signed greater or equal
749 createConstraintSigSig(SIG_op2_t, SIG_op1_t, CI2, CI1, Zero);
750 createConstraintSigSig(SIG_op1_f, SIG_op2_f, CI1, CI2, MinusOne);
753 case CmpInst::ICMP_SLT: // signed less than
754 createConstraintSigSig(SIG_op1_t, SIG_op2_t, CI1, CI2, MinusOne);
755 createConstraintSigSig(SIG_op2_f, SIG_op1_f, CI2, CI1, Zero);
758 case CmpInst::ICMP_SLE: // signed less or equal
759 createConstraintSigSig(SIG_op1_t, SIG_op2_t, CI1, CI2, Zero);
760 createConstraintSigSig(SIG_op2_f, SIG_op1_f, CI2, CI1, MinusOne);
768 createConstraintInstruction(I_op1);
770 createConstraintInstruction(I_op2);
773 /// Creates constraints for PHI nodes.
774 /// In a PHI node a = phi(b,c) we can create the constraint
775 /// a<= max(b,c). With this constraint there will be the edges,
776 /// b->a and c->a with weight 0 in the lower bound graph, and the edges
777 /// a->b and a->c with weight 0 in the upper bound graph.
778 void ABCD::createConstraintPHINode(PHINode *PN) {
779 // FIXME: We really want to disallow sigma nodes, but I don't know the best
780 // way to detect the other than this.
781 if (PN->getNumOperands() == 2) return;
783 int32_t width = cast<IntegerType>(PN->getType())->getBitWidth();
784 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
785 Value *V = PN->getIncomingValue(i);
786 if (Instruction *I = dyn_cast<Instruction>(V)) {
787 createConstraintInstruction(I);
789 inequality_graph.addEdge(V, PN, APInt(width, 0), true);
790 inequality_graph.addEdge(V, PN, APInt(width, 0), false);
794 /// This method creates a constraint between a Sigma and an Instruction.
795 /// These constraints are created as soon as we find a comparator that uses a
797 void ABCD::createConstraintSigInst(Instruction *I_op, BasicBlock *BB_succ_t,
798 BasicBlock *BB_succ_f, PHINode **SIG_op_t,
799 PHINode **SIG_op_f) {
800 *SIG_op_t = findSigma(BB_succ_t, I_op);
801 *SIG_op_f = findSigma(BB_succ_f, I_op);
804 int32_t width = cast<IntegerType>((*SIG_op_t)->getType())->getBitWidth();
805 inequality_graph.addEdge(I_op, *SIG_op_t, APInt(width, 0), true);
806 inequality_graph.addEdge(*SIG_op_t, I_op, APInt(width, 0), false);
809 int32_t width = cast<IntegerType>((*SIG_op_f)->getType())->getBitWidth();
810 inequality_graph.addEdge(I_op, *SIG_op_f, APInt(width, 0), true);
811 inequality_graph.addEdge(*SIG_op_f, I_op, APInt(width, 0), false);
815 /// If PN_op1 and PN_o2 are different from NULL, create a constraint
816 /// PN_op2 -> PN_op1 with value. In case any of them is NULL, replace
817 /// with the respective V_op#, if V_op# is a ConstantInt.
818 void ABCD::createConstraintSigSig(PHINode *SIG_op1, PHINode *SIG_op2,
819 ConstantInt *V_op1, ConstantInt *V_op2,
821 if (SIG_op1 && SIG_op2) {
822 inequality_graph.addEdge(SIG_op2, SIG_op1, value, true);
823 inequality_graph.addEdge(SIG_op1, SIG_op2, -value, false);
824 } else if (SIG_op1 && V_op2) {
825 inequality_graph.addEdge(V_op2, SIG_op1, value, true);
826 inequality_graph.addEdge(SIG_op1, V_op2, -value, false);
827 } else if (SIG_op2 && V_op1) {
828 inequality_graph.addEdge(SIG_op2, V_op1, value, true);
829 inequality_graph.addEdge(V_op1, SIG_op2, -value, false);
833 /// Returns the sigma representing the Instruction I in BasicBlock BB.
834 /// Returns NULL in case there is no sigma for this Instruction in this
835 /// Basic Block. This methods assume that sigmas are the first instructions
836 /// in a block, and that there can be only two sigmas in a block. So it will
837 /// only look on the first two instructions of BasicBlock BB.
838 PHINode *ABCD::findSigma(BasicBlock *BB, Instruction *I) {
839 // BB has more than one predecessor, BB cannot have sigmas.
840 if (I == NULL || BB->getSinglePredecessor() == NULL)
843 BasicBlock::iterator begin = BB->begin();
844 BasicBlock::iterator end = BB->end();
846 for (unsigned i = 0; i < 2 && begin != end; ++i, ++begin) {
847 Instruction *I_succ = begin;
848 if (PHINode *PN = dyn_cast<PHINode>(I_succ))
849 if (PN->getIncomingValue(0) == I)
856 /// Original ABCD algorithm to prove redundant checks.
857 /// This implementation works on any kind of inequality branch.
858 bool ABCD::demandProve(Value *a, Value *b, int c, bool upper_bound) {
859 int32_t width = cast<IntegerType>(a->getType())->getBitWidth();
860 Bound *bound = new Bound(APInt(width, c), upper_bound);
865 ProveResult res = prove(a, b, bound, 0);
869 /// Prove that distance between b and a is <= bound
870 ABCD::ProveResult ABCD::prove(Value *a, Value *b, Bound *bound,
872 // if (C[b-a<=e] == True for some e <= bound
873 // Same or stronger difference was already proven
874 if (mem_result.hasTrue(b, bound))
877 // if (C[b-a<=e] == False for some e >= bound
878 // Same or weaker difference was already disproved
879 if (mem_result.hasFalse(b, bound))
882 // if (C[b-a<=e] == Reduced for some e <= bound
883 // b is on a cycle that was reduced for same or stronger difference
884 if (mem_result.hasReduced(b, bound))
887 // traversal reached the source vertex
888 if (a == b && Bound::geq(bound, APInt(bound->getBitWidth(), 0, true)))
891 // if b has no predecessor then fail
892 if (!inequality_graph.hasEdge(b, bound->isUpperBound()))
895 // a cycle was encountered
896 if (active.count(b)) {
897 if (Bound::leq(active.lookup(b), bound))
898 return Reduced; // a "harmless" cycle
900 return False; // an amplifying cycle
904 PHINode *PN = dyn_cast<PHINode>(b);
906 // Test if a Value is a Phi. If it is a PHINode with more than 1 incoming
907 // value, then it is a phi, if it has 1 incoming value it is a sigma.
908 if (PN && PN->getNumIncomingValues() > 1)
909 updateMemDistance(a, b, bound, level, min);
911 updateMemDistance(a, b, bound, level, max);
915 ABCD::ProveResult res = mem_result.getBoundResult(b, bound);
919 /// Updates the distance value for a and b
920 void ABCD::updateMemDistance(Value *a, Value *b, Bound *bound, unsigned level,
921 meet_function meet) {
922 ABCD::ProveResult res = (meet == max) ? False : True;
924 SmallPtrSet<Edge *, 16> Edges = inequality_graph.getEdges(b);
925 SmallPtrSet<Edge *, 16>::iterator begin = Edges.begin(), end = Edges.end();
927 for (; begin != end ; ++begin) {
928 if (((res >= Reduced) && (meet == max)) ||
929 ((res == False) && (meet == min))) {
933 if (in->isUpperBound() == bound->isUpperBound()) {
934 Value *succ = in->getVertex();
935 res = meet(res, prove(a, succ, new Bound(bound, in->getValue()),
940 mem_result.updateBound(b, bound, res);
943 /// Return the stored result for this bound
944 ABCD::ProveResult ABCD::MemoizedResultChart::getResult(const Bound *bound)const{
945 if (max_false && Bound::leq(bound, max_false))
947 if (min_true && Bound::leq(min_true, bound))
949 if (min_reduced && Bound::leq(min_reduced, bound))
954 /// Stores a false found
955 void ABCD::MemoizedResultChart::addFalse(Bound *bound) {
956 if (!max_false || Bound::leq(max_false, bound))
959 if (Bound::eq(max_false, min_reduced))
960 min_reduced = Bound::createIncrement(min_reduced);
961 if (Bound::eq(max_false, min_true))
962 min_true = Bound::createIncrement(min_true);
963 if (Bound::eq(min_reduced, min_true))
965 clearRedundantReduced();
968 /// Stores a true found
969 void ABCD::MemoizedResultChart::addTrue(Bound *bound) {
970 if (!min_true || Bound::leq(bound, min_true))
973 if (Bound::eq(min_true, min_reduced))
974 min_reduced = Bound::createDecrement(min_reduced);
975 if (Bound::eq(min_true, max_false))
976 max_false = Bound::createDecrement(max_false);
977 if (Bound::eq(max_false, min_reduced))
979 clearRedundantReduced();
982 /// Stores a Reduced found
983 void ABCD::MemoizedResultChart::addReduced(Bound *bound) {
984 if (!min_reduced || Bound::leq(bound, min_reduced))
987 if (Bound::eq(min_reduced, min_true))
988 min_true = Bound::createIncrement(min_true);
989 if (Bound::eq(min_reduced, max_false))
990 max_false = Bound::createDecrement(max_false);
993 /// Clears redundant reduced
994 /// If a min_true is smaller than a min_reduced then the min_reduced
995 /// is unnecessary and then removed. It also works for min_reduced
996 /// begin smaller than max_false.
997 void ABCD::MemoizedResultChart::clearRedundantReduced() {
998 if (min_true && min_reduced && Bound::lt(min_true, min_reduced))
1000 if (max_false && min_reduced && Bound::lt(min_reduced, max_false))
1004 /// Stores the bound found
1005 void ABCD::MemoizedResult::updateBound(Value *b, Bound *bound,
1006 const ProveResult res) {
1008 map[b].addFalse(bound);
1009 } else if (res == True) {
1010 map[b].addTrue(bound);
1012 map[b].addReduced(bound);
1016 /// Adds an edge from V_from to V_to with weight value
1017 void ABCD::InequalityGraph::addEdge(Value *V_to, Value *V_from,
1018 APInt value, bool upper) {
1019 assert(V_from->getType() == V_to->getType());
1020 assert(cast<IntegerType>(V_from->getType())->getBitWidth() ==
1021 value.getBitWidth());
1023 DenseMap<Value *, SmallPtrSet<Edge *, 16> >::iterator from;
1024 from = addNode(V_from);
1025 from->second.insert(new Edge(V_to, value, upper));
1028 /// Test if there is any edge from V in the upper direction
1029 bool ABCD::InequalityGraph::hasEdge(Value *V, bool upper) const {
1030 SmallPtrSet<Edge *, 16> it = graph.lookup(V);
1032 SmallPtrSet<Edge *, 16>::iterator begin = it.begin();
1033 SmallPtrSet<Edge *, 16>::iterator end = it.end();
1034 for (; begin != end; ++begin) {
1035 if ((*begin)->isUpperBound() == upper) {
1042 /// Prints the header of the dot file
1043 void ABCD::InequalityGraph::printHeader(raw_ostream &OS, Function &F) const {
1044 OS << "digraph dotgraph {\n";
1045 OS << "label=\"Inequality Graph for \'";
1046 OS << F.getNameStr() << "\' function\";\n";
1047 OS << "node [shape=record,fontname=\"Times-Roman\",fontsize=14];\n";
1050 /// Prints the body of the dot file
1051 void ABCD::InequalityGraph::printBody(raw_ostream &OS) const {
1052 DenseMap<Value *, SmallPtrSet<Edge *, 16> >::iterator begin =
1053 graph.begin(), end = graph.end();
1055 for (; begin != end ; ++begin) {
1056 SmallPtrSet<Edge *, 16>::iterator begin_par =
1057 begin->second.begin(), end_par = begin->second.end();
1058 Value *source = begin->first;
1060 printVertex(OS, source);
1062 for (; begin_par != end_par ; ++begin_par) {
1063 Edge *edge = *begin_par;
1064 printEdge(OS, source, edge);
1069 /// Prints vertex source to the dot file
1071 void ABCD::InequalityGraph::printVertex(raw_ostream &OS, Value *source) const {
1073 printName(OS, source);
1075 OS << " [label=\"{";
1076 printName(OS, source);
1080 /// Prints the edge to the dot file
1081 void ABCD::InequalityGraph::printEdge(raw_ostream &OS, Value *source,
1083 Value *dest = edge->getVertex();
1084 APInt value = edge->getValue();
1085 bool upper = edge->isUpperBound();
1088 printName(OS, source);
1092 printName(OS, dest);
1094 OS << " [label=\"" << value << "\"";
1096 OS << "color=\"blue\"";
1098 OS << "color=\"red\"";
1103 void ABCD::InequalityGraph::printName(raw_ostream &OS, Value *info) const {
1104 if (ConstantInt *CI = dyn_cast<ConstantInt>(info)) {
1107 if (!info->hasName()) {
1110 OS << info->getNameStr();
1114 /// createABCDPass - The public interface to this file...
1115 FunctionPass *llvm::createABCDPass() {