lib/Transforms/Scalar/ABCD.cpp

   1 //===------- ABCD.cpp - Removes redundant conditional branches ------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  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.
  25 //
  26 //===----------------------------------------------------------------------===//
  27
  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"
  40
  41 using namespace llvm;
  42
  43 STATISTIC(NumBranchTested, "Number of conditional branches analyzed");
  44 STATISTIC(NumBranchRemoved, "Number of conditional branches removed");
  45
  46 namespace {
  47
  48 class ABCD : public FunctionPass {
  49  public:
  50   static char ID;  // Pass identification, replacement for typeid.
  51   ABCD() : FunctionPass(&ID) {}
  52
  53   void getAnalysisUsage(AnalysisUsage &AU) const {
  54     AU.addRequired<SSI>();
  55   }
  56
  57   bool runOnFunction(Function &F);
  58
  59  private:
  60   /// Keep track of whether we've modified the program yet.
  61   bool modified;
  62
  63   enum ProveResult {
  64     False = 0,
  65     Reduced = 1,
  66     True = 2
  67   };
  68
  69   typedef ProveResult (*meet_function)(ProveResult, ProveResult);
  70   static ProveResult max(ProveResult res1, ProveResult res2) {
  71     return (ProveResult) std::max(res1, res2);
  72   }
  73   static ProveResult min(ProveResult res1, ProveResult res2) {
  74     return (ProveResult) std::min(res1, res2);
  75   }
  76
  77   class Bound {
  78    public:
  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) {}
  84
  85     /// Test if Bound is an upper bound
  86     bool isUpperBound() const { return upper_bound; }
  87
  88     /// Get the bitwidth of this bound
  89     int32_t getBitWidth() const { return value.getBitWidth(); }
  90
  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,
  94                        b->upper_bound);
  95     }
  96
  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,
 100                        b->upper_bound);
 101     }
 102
 103     /// Test if two bounds are equal
 104     static bool eq(const Bound *a, const Bound *b) {
 105       if (!a || !b) return false;
 106
 107       assert(a->isUpperBound() == b->isUpperBound());
 108       return a->value == b->value;
 109     }
 110
 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);
 115     }
 116
 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;
 120
 121       assert(a->isUpperBound() == b->isUpperBound());
 122       return a->isUpperBound() ? a->value.sle(b->value) :
 123                                  a->value.sge(b->value);
 124     }
 125
 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;
 129
 130       assert(a->isUpperBound() == b->isUpperBound());
 131       return a->isUpperBound() ? a->value.slt(b->value) :
 132                                  a->value.sgt(b->value);
 133     }
 134
 135     /// Test if Bound b is greater then or equal val
 136     static bool geq(const Bound *b, APInt val) {
 137       return leq(val, b);
 138     }
 139
 140     /// Test if Bound a is greater then or equal Bound b
 141     static bool geq(const Bound *a, const Bound *b) {
 142       return leq(b, a);
 143     }
 144
 145    private:
 146     APInt value;
 147     bool upper_bound;
 148   };
 149
 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 {
 154    public:
 155      MemoizedResultChart()
 156        : max_false(NULL), min_true(NULL), min_reduced(NULL) {}
 157
 158     /// Returns the max false
 159     Bound *getFalse() const { return max_false; }
 160
 161     /// Returns the min true
 162     Bound *getTrue() const { return min_true; }
 163
 164     /// Returns the min reduced
 165     Bound *getReduced() const { return min_reduced; }
 166
 167     /// Return the stored result for this bound
 168     ProveResult getResult(const Bound *bound) const;
 169
 170     /// Stores a false found
 171     void addFalse(Bound *bound);
 172
 173     /// Stores a true found
 174     void addTrue(Bound *bound);
 175
 176     /// Stores a Reduced found
 177     void addReduced(Bound *bound);
 178
 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();
 184
 185     void clear() {
 186       delete max_false;
 187       delete min_true;
 188       delete min_reduced;
 189     }
 190
 191   private:
 192     Bound *max_false, *min_true, *min_reduced;
 193   };
 194
 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 {
 198   public:
 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);
 204     }
 205
 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);
 211     }
 212
 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);
 218     }
 219
 220     /// Returns the stored bound for b
 221     ProveResult getBoundResult(Value *b, Bound *bound) {
 222       return map[b].getResult(bound);
 223     }
 224
 225     /// Clears the map
 226     void clear() {
 227       DenseMapIterator<Value*, MemoizedResultChart> begin = map.begin();
 228       DenseMapIterator<Value*, MemoizedResultChart> end = map.end();
 229       for (; begin != end; ++begin) {
 230         begin->second.clear();
 231       }
 232       map.clear();
 233     }
 234
 235     /// Stores the bound found
 236     void updateBound(Value *b, Bound *bound, const ProveResult res);
 237
 238   private:
 239     // Maps a nod in the graph with its results found.
 240     DenseMap<Value*, MemoizedResultChart> map;
 241   };
 242
 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.
 246   class Edge {
 247   public:
 248     Edge(Value *V, APInt val, bool upper)
 249       : vertex(V), value(val), upper_bound(upper) {}
 250
 251     Value *getVertex() const { return vertex; }
 252     const APInt &getValue() const { return value; }
 253     bool isUpperBound() const { return upper_bound; }
 254
 255   private:
 256     Value *vertex;
 257     APInt value;
 258     bool upper_bound;
 259   };
 260
 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 {
 265   public:
 266
 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);
 269
 270     /// Test if there is a node V
 271     bool hasNode(Value *V) const { return graph.count(V); }
 272
 273     /// Test if there is any edge from V in the upper direction
 274     bool hasEdge(Value *V, bool upper) const;
 275
 276     /// Returns all edges pointed by vertex V
 277     SmallPtrSet<Edge *, 16> getEdges(Value *V) const {
 278       return graph.lookup(V);
 279     }
 280
 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 {
 284       printHeader(OS, F);
 285       printBody(OS);
 286       printFooter(OS);
 287     }
 288
 289     /// Clear the graph
 290     void clear() {
 291       graph.clear();
 292     }
 293
 294   private:
 295     DenseMap<Value *, SmallPtrSet<Edge *, 16> > graph;
 296
 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;
 301     }
 302
 303     /// Prints the header of the dot file
 304     void printHeader(raw_ostream &OS, Function &F) const;
 305
 306     /// Prints the footer of the dot file
 307     void printFooter(raw_ostream &OS) const {
 308       OS << "}\n";
 309     }
 310
 311     /// Prints the body of the dot file
 312     void printBody(raw_ostream &OS) const;
 313
 314     /// Prints vertex source to the dot file
 315     void printVertex(raw_ostream &OS, Value *source) const;
 316
 317     /// Prints the edge to the dot file
 318     void printEdge(raw_ostream &OS, Value *source, Edge *edge) const;
 319
 320     void printName(raw_ostream &OS, Value *info) const;
 321   };
 322
 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
 326   /// transformed.
 327   void createSSI(Function &F);
 328
 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
 332   /// operand.
 333   void executeABCD(Function &F);
 334
 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);
 343
 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
 347   /// instruction.
 348   void removeRedundancy(TerminatorInst *TI, bool Succ_edge);
 349
 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);
 356
 357   /// Removes phis that have no predecessor
 358   void removePhis();
 359
 360   /// Creates constraints for Instructions.
 361   /// If the constraint for this instruction has already been created
 362   /// nothing is done.
 363   void createConstraintInstruction(Instruction *I);
 364
 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);
 375
 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);
 389
 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);
 396
 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,
 403                                 ConstantInt **C2);
 404
 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
 407   /// SSI variable.
 408   void createConstraintSigInst(Instruction *I_op, BasicBlock *BB_succ_t,
 409                                BasicBlock *BB_succ_f, PHINode **SIG_op_t,
 410                                PHINode **SIG_op_f);
 411
 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, APInt value);
 416
 417   /// Returns the sigma representing the Instruction I in BasicBlock BB.
 418   /// Returns NULL in case there is no sigma for this Instruction in this
 419   /// Basic Block. This methods assume that sigmas are the first instructions
 420   /// in a block, and that there can be only two sigmas in a block. So it will
 421   /// only look on the first two instructions of BasicBlock BB.
 422   PHINode *findSigma(BasicBlock *BB, Instruction *I);
 423
 424   /// Original ABCD algorithm to prove redundant checks.
 425   /// This implementation works on any kind of inequality branch.
 426   bool demandProve(Value *a, Value *b, int c, bool upper_bound);
 427
 428   /// Prove that distance between b and a is <= bound
 429   ProveResult prove(Value *a, Value *b, Bound *bound, unsigned level);
 430
 431   /// Updates the distance value for a and b
 432   void updateMemDistance(Value *a, Value *b, Bound *bound, unsigned level,
 433                          meet_function meet);
 434
 435   InequalityGraph inequality_graph;
 436   MemoizedResult mem_result;
 437   DenseMap<Value*, Bound*> active;
 438   SmallPtrSet<Value*, 16> created;
 439   SmallVector<PHINode *, 16> phis_to_remove;
 440 };
 441
 442 }  // end anonymous namespace.
 443
 444 char ABCD::ID = 0;
 445 static RegisterPass<ABCD> X("abcd", "ABCD: Eliminating Array Bounds Checks on Demand");
 446
 447
 448 bool ABCD::runOnFunction(Function &F) {
 449   modified = false;
 450   createSSI(F);
 451   executeABCD(F);
 452   DEBUG(inequality_graph.printGraph(errs(), F));
 453   removePhis();
 454
 455   inequality_graph.clear();
 456   mem_result.clear();
 457   active.clear();
 458   created.clear();
 459   phis_to_remove.clear();
 460   return modified;
 461 }
 462
 463 /// Iterates through all BasicBlocks, if the Terminator Instruction
 464 /// uses an Comparator Instruction, all operands of this comparator
 465 /// are sent to be transformed to SSI. Only Instruction operands are
 466 /// transformed.
 467 void ABCD::createSSI(Function &F) {
 468   SSI *ssi = &getAnalysis<SSI>();
 469
 470   SmallVector<Instruction *, 16> Insts;
 471
 472   for (Function::iterator begin = F.begin(), end = F.end();
 473        begin != end; ++begin) {
 474     BasicBlock *BB = begin;
 475     TerminatorInst *TI = BB->getTerminator();
 476     if (TI->getNumOperands() == 0)
 477       continue;
 478
 479     if (ICmpInst *ICI = dyn_cast<ICmpInst>(TI->getOperand(0))) {
 480       if (Instruction *I = dyn_cast<Instruction>(ICI->getOperand(0))) {
 481         modified = true;  // XXX: but yet createSSI might do nothing
 482         Insts.push_back(I);
 483       }
 484       if (Instruction *I = dyn_cast<Instruction>(ICI->getOperand(1))) {
 485         modified = true;
 486         Insts.push_back(I);
 487       }
 488     }
 489   }
 490   ssi->createSSI(Insts);
 491 }
 492
 493 /// Creates the graphs for this function.
 494 /// It will look for all comparators used in branches, and create them.
 495 /// These comparators will create constraints for any instruction as an
 496 /// operand.
 497 void ABCD::executeABCD(Function &F) {
 498   for (Function::iterator begin = F.begin(), end = F.end();
 499        begin != end; ++begin) {
 500     BasicBlock *BB = begin;
 501     TerminatorInst *TI = BB->getTerminator();
 502     if (TI->getNumOperands() == 0)
 503       continue;
 504
 505     ICmpInst *ICI = dyn_cast<ICmpInst>(TI->getOperand(0));
 506     if (!ICI || !isa<IntegerType>(ICI->getOperand(0)->getType()))
 507       continue;
 508
 509     createConstraintCmpInst(ICI, TI);
 510     seekRedundancy(ICI, TI);
 511   }
 512 }
 513
 514 /// Seeks redundancies in the comparator instruction CI.
 515 /// If the ABCD algorithm can prove that the comparator CI always
 516 /// takes one way, then the Terminator Instruction TI is substituted from
 517 /// a conditional branch to a unconditional one.
 518 /// This code basically receives a comparator, and verifies which kind of
 519 /// instruction it is. Depending on the kind of instruction, we use different
 520 /// strategies to prove its redundancy.
 521 void ABCD::seekRedundancy(ICmpInst *ICI, TerminatorInst *TI) {
 522   CmpInst::Predicate Pred = ICI->getPredicate();
 523
 524   Value *source, *dest;
 525   int distance1, distance2;
 526   bool upper;
 527
 528   switch(Pred) {
 529     case CmpInst::ICMP_SGT: // signed greater than
 530       upper = false;
 531       distance1 = 1;
 532       distance2 = 0;
 533       break;
 534
 535     case CmpInst::ICMP_SGE: // signed greater or equal
 536       upper = false;
 537       distance1 = 0;
 538       distance2 = -1;
 539       break;
 540
 541     case CmpInst::ICMP_SLT: // signed less than
 542       upper = true;
 543       distance1 = -1;
 544       distance2 = 0;
 545       break;
 546
 547     case CmpInst::ICMP_SLE: // signed less or equal
 548       upper = true;
 549       distance1 = 0;
 550       distance2 = 1;
 551       break;
 552
 553     default:
 554       return;
 555   }
 556
 557   ++NumBranchTested;
 558   source = ICI->getOperand(0);
 559   dest = ICI->getOperand(1);
 560   if (demandProve(dest, source, distance1, upper)) {
 561     removeRedundancy(TI, true);
 562   } else if (demandProve(dest, source, distance2, !upper)) {
 563     removeRedundancy(TI, false);
 564   }
 565 }
 566
 567 /// Substitutes Terminator Instruction TI, that is a conditional branch,
 568 /// with one unconditional branch. Succ_edge determines if the new
 569 /// unconditional edge will be the first or second edge of the former TI
 570 /// instruction.
 571 void ABCD::removeRedundancy(TerminatorInst *TI, bool Succ_edge) {
 572   BasicBlock *Succ;
 573   if (Succ_edge) {
 574     Succ = TI->getSuccessor(0);
 575     fixPhi(TI->getParent(), TI->getSuccessor(1));
 576   } else {
 577     Succ = TI->getSuccessor(1);
 578     fixPhi(TI->getParent(), TI->getSuccessor(0));
 579   }
 580
 581   BranchInst::Create(Succ, TI);
 582   TI->eraseFromParent();  // XXX: invoke
 583   ++NumBranchRemoved;
 584   modified = true;
 585 }
 586
 587 /// When an conditional branch is removed, the BasicBlock that is no longer
 588 /// reachable will have problems in phi functions. This method fixes these
 589 /// phis removing the former BasicBlock from the list of incoming BasicBlocks
 590 /// of all phis. In case the phi remains with no predecessor it will be
 591 /// marked to be removed later.
 592 void ABCD::fixPhi(BasicBlock *BB, BasicBlock *Succ) {
 593   BasicBlock::iterator begin = Succ->begin();
 594   while (PHINode *PN = dyn_cast<PHINode>(begin++)) {
 595     PN->removeIncomingValue(BB, false);
 596     if (PN->getNumIncomingValues() == 0)
 597       phis_to_remove.push_back(PN);
 598   }
 599 }
 600
 601 /// Removes phis that have no predecessor
 602 void ABCD::removePhis() {
 603   for (unsigned i = 0, e = phis_to_remove.size(); i != e; ++i) {
 604     PHINode *PN = phis_to_remove[i];
 605     PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
 606     PN->eraseFromParent();
 607   }
 608 }
 609
 610 /// Creates constraints for Instructions.
 611 /// If the constraint for this instruction has already been created
 612 /// nothing is done.
 613 void ABCD::createConstraintInstruction(Instruction *I) {
 614   // Test if this instruction has not been created before
 615   if (created.insert(I)) {
 616     if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
 617       createConstraintBinaryOperator(BO);
 618     } else if (PHINode *PN = dyn_cast<PHINode>(I)) {
 619       createConstraintPHINode(PN);
 620     }
 621   }
 622 }
 623
 624 /// Creates constraints for Binary Operators.
 625 /// It will create constraints only for addition and subtraction,
 626 /// the other binary operations are not treated by ABCD.
 627 /// For additions in the form a = b + X and a = X + b, where X is a constant,
 628 /// the constraint a <= b + X can be obtained. For this constraint, an edge
 629 /// a->b with weight X is added to the lower bound graph, and an edge
 630 /// b->a with weight -X is added to the upper bound graph.
 631 /// Only subtractions in the format a = b - X is used by ABCD.
 632 /// Edges are created using the same semantic as addition.
 633 void ABCD::createConstraintBinaryOperator(BinaryOperator *BO) {
 634   Instruction *I1 = NULL, *I2 = NULL;
 635   ConstantInt *CI1 = NULL, *CI2 = NULL;
 636
 637   // Test if an operand is an Instruction and the other is a Constant
 638   if (!createBinaryOperatorInfo(BO, &I1, &I2, &CI1, &CI2))
 639     return;
 640
 641   Instruction *I = 0;
 642   APInt value;
 643
 644   switch (BO->getOpcode()) {
 645     case Instruction::Add:
 646       if (I1) {
 647         I = I1;
 648         value = CI2->getValue();
 649       } else if (I2) {
 650         I = I2;
 651         value = CI1->getValue();
 652       }
 653       break;
 654
 655     case Instruction::Sub:
 656       // Instructions like a = X-b, where X is a constant are not represented
 657       // in the graph.
 658       if (!I1)
 659         return;
 660
 661       I = I1;
 662       value = -CI2->getValue();
 663       break;
 664
 665     default:
 666       return;
 667   }
 668
 669   inequality_graph.addEdge(I, BO, value, true);
 670   inequality_graph.addEdge(BO, I, -value, false);
 671   createConstraintInstruction(I);
 672 }
 673
 674 /// Given a binary operator, we are only interest in the case
 675 /// that one operand is an Instruction and the other is a ConstantInt. In
 676 /// this case the method returns true, otherwise false. It also obtains the
 677 /// Instruction and ConstantInt from the BinaryOperator and returns it.
 678 bool ABCD::createBinaryOperatorInfo(BinaryOperator *BO, Instruction **I1,
 679                                     Instruction **I2, ConstantInt **C1,
 680                                     ConstantInt **C2) {
 681   Value *op1 = BO->getOperand(0);
 682   Value *op2 = BO->getOperand(1);
 683
 684   if ((*I1 = dyn_cast<Instruction>(op1))) {
 685     if ((*C2 = dyn_cast<ConstantInt>(op2)))
 686       return true; // First is Instruction and second ConstantInt
 687
 688     return false; // Both are Instruction
 689   } else {
 690     if ((*C1 = dyn_cast<ConstantInt>(op1)) &&
 691         (*I2 = dyn_cast<Instruction>(op2)))
 692       return true; // First is ConstantInt and second Instruction
 693
 694     return false; // Both are not Instruction
 695   }
 696 }
 697
 698 /// Creates constraints for Comparator Instructions.
 699 /// Only comparators that have any of the following operators
 700 /// are used to create constraints: >=, >, <=, <. And only if
 701 /// at least one operand is an Instruction. In a Comparator Instruction
 702 /// a op b, there will be 4 sigma functions a_t, a_f, b_t and b_f. Where
 703 /// t and f represent sigma for operands in true and false branches. The
 704 /// following constraints can be obtained. a_t <= a, a_f <= a, b_t <= b and
 705 /// b_f <= b. There are two more constraints that depend on the operator.
 706 /// For the operator <= : a_t <= b_t   and b_f <= a_f-1
 707 /// For the operator <  : a_t <= b_t-1 and b_f <= a_f
 708 /// For the operator >= : b_t <= a_t   and a_f <= b_f-1
 709 /// For the operator >  : b_t <= a_t-1 and a_f <= b_f
 710 void ABCD::createConstraintCmpInst(ICmpInst *ICI, TerminatorInst *TI) {
 711   Value *V_op1 = ICI->getOperand(0);
 712   Value *V_op2 = ICI->getOperand(1);
 713
 714   if (!isa<IntegerType>(V_op1->getType()))
 715     return;
 716
 717   Instruction *I_op1 = dyn_cast<Instruction>(V_op1);
 718   Instruction *I_op2 = dyn_cast<Instruction>(V_op2);
 719
 720   // Test if at least one operand is an Instruction
 721   if (!I_op1 && !I_op2)
 722     return;
 723
 724   BasicBlock *BB_succ_t = TI->getSuccessor(0);
 725   BasicBlock *BB_succ_f = TI->getSuccessor(1);
 726
 727   PHINode *SIG_op1_t = NULL, *SIG_op1_f = NULL,
 728           *SIG_op2_t = NULL, *SIG_op2_f = NULL;
 729
 730   createConstraintSigInst(I_op1, BB_succ_t, BB_succ_f, &SIG_op1_t, &SIG_op1_f);
 731   createConstraintSigInst(I_op2, BB_succ_t, BB_succ_f, &SIG_op2_t, &SIG_op2_f);
 732
 733   int32_t width = cast<IntegerType>(V_op1->getType())->getBitWidth();
 734   APInt MinusOne = APInt::getAllOnesValue(width);
 735   APInt Zero = APInt::getNullValue(width);
 736
 737   CmpInst::Predicate Pred = ICI->getPredicate();
 738   switch (Pred) {
 739   case CmpInst::ICMP_SGT:  // signed greater than
 740     createConstraintSigSig(SIG_op2_t, SIG_op1_t, MinusOne);
 741     createConstraintSigSig(SIG_op1_f, SIG_op2_f, Zero);
 742     break;
 743
 744   case CmpInst::ICMP_SGE:  // signed greater or equal
 745     createConstraintSigSig(SIG_op2_t, SIG_op1_t, Zero);
 746     createConstraintSigSig(SIG_op1_f, SIG_op2_f, MinusOne);
 747     break;
 748
 749   case CmpInst::ICMP_SLT:  // signed less than
 750     createConstraintSigSig(SIG_op1_t, SIG_op2_t, MinusOne);
 751     createConstraintSigSig(SIG_op2_f, SIG_op1_f, Zero);
 752     break;
 753
 754   case CmpInst::ICMP_SLE:  // signed less or equal
 755     createConstraintSigSig(SIG_op1_t, SIG_op2_t, Zero);
 756     createConstraintSigSig(SIG_op2_f, SIG_op1_f, MinusOne);
 757     break;
 758
 759   default:
 760     break;
 761   }
 762
 763   if (I_op1)
 764     createConstraintInstruction(I_op1);
 765   if (I_op2)
 766     createConstraintInstruction(I_op2);
 767 }
 768
 769 /// Creates constraints for PHI nodes.
 770 /// In a PHI node a = phi(b,c) we can create the constraint
 771 /// a<= max(b,c). With this constraint there will be the edges,
 772 /// b->a and c->a with weight 0 in the lower bound graph, and the edges
 773 /// a->b and a->c with weight 0 in the upper bound graph.
 774 void ABCD::createConstraintPHINode(PHINode *PN) {
 775   int32_t width = cast<IntegerType>(PN->getType())->getBitWidth();
 776   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 777     Value *V = PN->getIncomingValue(i);
 778     if (Instruction *I = dyn_cast<Instruction>(V)) {
 779       createConstraintInstruction(I);
 780     }
 781     inequality_graph.addEdge(V, PN, APInt(width, 0), true);
 782     inequality_graph.addEdge(V, PN, APInt(width, 0), false);
 783   }
 784 }
 785
 786 /// This method creates a constraint between a Sigma and an Instruction.
 787 /// These constraints are created as soon as we find a comparator that uses a
 788 /// SSI variable.
 789 void ABCD::createConstraintSigInst(Instruction *I_op, BasicBlock *BB_succ_t,
 790                                    BasicBlock *BB_succ_f, PHINode **SIG_op_t,
 791                                    PHINode **SIG_op_f) {
 792   *SIG_op_t = findSigma(BB_succ_t, I_op);
 793   *SIG_op_f = findSigma(BB_succ_f, I_op);
 794
 795   if (*SIG_op_t) {
 796     int32_t width = cast<IntegerType>((*SIG_op_t)->getType())->getBitWidth();
 797     inequality_graph.addEdge(I_op, *SIG_op_t, APInt(width, 0), true);
 798     inequality_graph.addEdge(*SIG_op_t, I_op, APInt(width, 0), false);
 799     if (created.insert(*SIG_op_t))
 800       createConstraintPHINode(cast<PHINode>(*SIG_op_t));
 801   }
 802   if (*SIG_op_f) {
 803     int32_t width = cast<IntegerType>((*SIG_op_f)->getType())->getBitWidth();
 804     inequality_graph.addEdge(I_op, *SIG_op_f, APInt(width, 0), true);
 805     inequality_graph.addEdge(*SIG_op_f, I_op, APInt(width, 0), false);
 806     if (created.insert(*SIG_op_f))
 807       createConstraintPHINode(cast<PHINode>(*SIG_op_f));
 808   }
 809 }
 810
 811 /// If PN_op1 and PN_o2 are different from NULL, create a constraint
 812 /// PN_op2 -> PN_op1 with value. In case any of them is NULL, replace
 813 /// with the respective V_op#, if V_op# is a ConstantInt.
 814 void ABCD::createConstraintSigSig(PHINode *SIG_op1, PHINode *SIG_op2,
 815                                   APInt value) {
 816   if (SIG_op1 && SIG_op2) {
 817     inequality_graph.addEdge(SIG_op2, SIG_op1, value, true);
 818     inequality_graph.addEdge(SIG_op1, SIG_op2, -value, false);
 819   }
 820 }
 821
 822 /// Returns the sigma representing the Instruction I in BasicBlock BB.
 823 /// Returns NULL in case there is no sigma for this Instruction in this
 824 /// Basic Block. This methods assume that sigmas are the first instructions
 825 /// in a block, and that there can be only two sigmas in a block. So it will
 826 /// only look on the first two instructions of BasicBlock BB.
 827 PHINode *ABCD::findSigma(BasicBlock *BB, Instruction *I) {
 828   // BB has more than one predecessor, BB cannot have sigmas.
 829   if (I == NULL || BB->getSinglePredecessor() == NULL)
 830     return NULL;
 831
 832   BasicBlock::iterator begin = BB->begin();
 833   BasicBlock::iterator end = BB->end();
 834
 835   for (unsigned i = 0; i < 2 && begin != end; ++i, ++begin) {
 836     Instruction *I_succ = begin;
 837     if (PHINode *PN = dyn_cast<PHINode>(I_succ))
 838       if (PN->getIncomingValue(0) == I)
 839         return PN;
 840   }
 841
 842   return NULL;
 843 }
 844
 845 /// Original ABCD algorithm to prove redundant checks.
 846 /// This implementation works on any kind of inequality branch.
 847 bool ABCD::demandProve(Value *a, Value *b, int c, bool upper_bound) {
 848   int32_t width = cast<IntegerType>(a->getType())->getBitWidth();
 849   Bound *bound = new Bound(APInt(width, c), upper_bound);
 850
 851   mem_result.clear();
 852   active.clear();
 853
 854   ProveResult res = prove(a, b, bound, 0);
 855   return res != False;
 856 }
 857
 858 /// Prove that distance between b and a is <= bound
 859 ABCD::ProveResult ABCD::prove(Value *a, Value *b, Bound *bound,
 860                               unsigned level) {
 861   // if (C[b-a<=e] == True for some e <= bound
 862   // Same or stronger difference was already proven
 863   if (mem_result.hasTrue(b, bound))
 864     return True;
 865
 866   // if (C[b-a<=e] == False for some e >= bound
 867   // Same or weaker difference was already disproved
 868   if (mem_result.hasFalse(b, bound))
 869     return False;
 870
 871   // if (C[b-a<=e] == Reduced for some e <= bound
 872   // b is on a cycle that was reduced for same or stronger difference
 873   if (mem_result.hasReduced(b, bound))
 874     return Reduced;
 875
 876   // traversal reached the source vertex
 877   if (a == b && Bound::geq(bound, APInt(bound->getBitWidth(), 0, true)))
 878     return True;
 879
 880   // if b has no predecessor then fail
 881   if (!inequality_graph.hasEdge(b, bound->isUpperBound()))
 882     return False;
 883
 884   // a cycle was encountered
 885   if (active.count(b)) {
 886     if (Bound::leq(active.lookup(b), bound))
 887       return Reduced; // a "harmless" cycle
 888
 889     return False; // an amplifying cycle
 890   }
 891
 892   active[b] = bound;
 893   PHINode *PN = dyn_cast<PHINode>(b);
 894
 895   // Test if a Value is a Phi. If it is a PHINode with more than 1 incoming
 896   // value, then it is a phi, if it has 1 incoming value it is a sigma.
 897   if (PN && PN->getNumIncomingValues() > 1)
 898     updateMemDistance(a, b, bound, level, min);
 899   else
 900     updateMemDistance(a, b, bound, level, max);
 901
 902   active.erase(b);
 903
 904   ABCD::ProveResult res = mem_result.getBoundResult(b, bound);
 905   return res;
 906 }
 907
 908 /// Updates the distance value for a and b
 909 void ABCD::updateMemDistance(Value *a, Value *b, Bound *bound, unsigned level,
 910                              meet_function meet) {
 911   ABCD::ProveResult res = (meet == max) ? False : True;
 912
 913   SmallPtrSet<Edge *, 16> Edges = inequality_graph.getEdges(b);
 914   SmallPtrSet<Edge *, 16>::iterator begin = Edges.begin(), end = Edges.end();
 915
 916   for (; begin != end ; ++begin) {
 917     if (((res >= Reduced) && (meet == max)) ||
 918        ((res == False) && (meet == min))) {
 919       break;
 920     }
 921     Edge *in = *begin;
 922     if (in->isUpperBound() == bound->isUpperBound()) {
 923       Value *succ = in->getVertex();
 924       res = meet(res, prove(a, succ, new Bound(bound, in->getValue()),
 925                  level+1));
 926     }
 927   }
 928
 929   mem_result.updateBound(b, bound, res);
 930 }
 931
 932 /// Return the stored result for this bound
 933 ABCD::ProveResult ABCD::MemoizedResultChart::getResult(const Bound *bound)const{
 934   if (max_false && Bound::leq(bound, max_false))
 935     return False;
 936   if (min_true && Bound::leq(min_true, bound))
 937     return True;
 938   if (min_reduced && Bound::leq(min_reduced, bound))
 939     return Reduced;
 940   return False;
 941 }
 942
 943 /// Stores a false found
 944 void ABCD::MemoizedResultChart::addFalse(Bound *bound) {
 945   if (!max_false || Bound::leq(max_false, bound))
 946     max_false = bound;
 947
 948   if (Bound::eq(max_false, min_reduced))
 949     min_reduced = Bound::createIncrement(min_reduced);
 950   if (Bound::eq(max_false, min_true))
 951     min_true = Bound::createIncrement(min_true);
 952   if (Bound::eq(min_reduced, min_true))
 953     min_reduced = NULL;
 954   clearRedundantReduced();
 955 }
 956
 957 /// Stores a true found
 958 void ABCD::MemoizedResultChart::addTrue(Bound *bound) {
 959   if (!min_true || Bound::leq(bound, min_true))
 960     min_true = bound;
 961
 962   if (Bound::eq(min_true, min_reduced))
 963     min_reduced = Bound::createDecrement(min_reduced);
 964   if (Bound::eq(min_true, max_false))
 965     max_false = Bound::createDecrement(max_false);
 966   if (Bound::eq(max_false, min_reduced))
 967     min_reduced = NULL;
 968   clearRedundantReduced();
 969 }
 970
 971 /// Stores a Reduced found
 972 void ABCD::MemoizedResultChart::addReduced(Bound *bound) {
 973   if (!min_reduced || Bound::leq(bound, min_reduced))
 974     min_reduced = bound;
 975
 976   if (Bound::eq(min_reduced, min_true))
 977     min_true = Bound::createIncrement(min_true);
 978   if (Bound::eq(min_reduced, max_false))
 979     max_false = Bound::createDecrement(max_false);
 980 }
 981
 982 /// Clears redundant reduced
 983 /// If a min_true is smaller than a min_reduced then the min_reduced
 984 /// is unnecessary and then removed. It also works for min_reduced
 985 /// begin smaller than max_false.
 986 void ABCD::MemoizedResultChart::clearRedundantReduced() {
 987   if (min_true && min_reduced && Bound::lt(min_true, min_reduced))
 988     min_reduced = NULL;
 989   if (max_false && min_reduced && Bound::lt(min_reduced, max_false))
 990     min_reduced = NULL;
 991 }
 992
 993 /// Stores the bound found
 994 void ABCD::MemoizedResult::updateBound(Value *b, Bound *bound,
 995                                        const ProveResult res) {
 996   if (res == False) {
 997     map[b].addFalse(bound);
 998   } else if (res == True) {
 999     map[b].addTrue(bound);
1000   } else {
1001     map[b].addReduced(bound);
1002   }
1003 }
1004
1005 /// Adds an edge from V_from to V_to with weight value
1006 void ABCD::InequalityGraph::addEdge(Value *V_to, Value *V_from,
1007                                     APInt value, bool upper) {
1008   assert(V_from->getType() == V_to->getType());
1009   assert(cast<IntegerType>(V_from->getType())->getBitWidth() ==
1010          value.getBitWidth());
1011
1012   DenseMap<Value *, SmallPtrSet<Edge *, 16> >::iterator from;
1013   from = addNode(V_from);
1014   from->second.insert(new Edge(V_to, value, upper));
1015 }
1016
1017 /// Test if there is any edge from V in the upper direction
1018 bool ABCD::InequalityGraph::hasEdge(Value *V, bool upper) const {
1019   SmallPtrSet<Edge *, 16> it = graph.lookup(V);
1020
1021   SmallPtrSet<Edge *, 16>::iterator begin = it.begin();
1022   SmallPtrSet<Edge *, 16>::iterator end = it.end();
1023   for (; begin != end; ++begin) {
1024     if ((*begin)->isUpperBound() == upper) {
1025       return true;
1026     }
1027   }
1028   return false;
1029 }
1030
1031 /// Prints the header of the dot file
1032 void ABCD::InequalityGraph::printHeader(raw_ostream &OS, Function &F) const {
1033   OS << "digraph dotgraph {\n";
1034   OS << "label=\"Inequality Graph for \'";
1035   OS << F.getNameStr() << "\' function\";\n";
1036   OS << "node [shape=record,fontname=\"Times-Roman\",fontsize=14];\n";
1037 }
1038
1039 /// Prints the body of the dot file
1040 void ABCD::InequalityGraph::printBody(raw_ostream &OS) const {
1041   DenseMap<Value *, SmallPtrSet<Edge *, 16> >::iterator begin =
1042       graph.begin(), end = graph.end();
1043
1044   for (; begin != end ; ++begin) {
1045     SmallPtrSet<Edge *, 16>::iterator begin_par =
1046         begin->second.begin(), end_par = begin->second.end();
1047     Value *source = begin->first;
1048
1049     printVertex(OS, source);
1050
1051     for (; begin_par != end_par ; ++begin_par) {
1052       Edge *edge = *begin_par;
1053       printEdge(OS, source, edge);
1054     }
1055   }
1056 }
1057
1058 /// Prints vertex source to the dot file
1059 ///
1060 void ABCD::InequalityGraph::printVertex(raw_ostream &OS, Value *source) const {
1061   OS << "\"";
1062   printName(OS, source);
1063   OS << "\"";
1064   OS << " [label=\"{";
1065   printName(OS, source);
1066   OS << "}\"];\n";
1067 }
1068
1069 /// Prints the edge to the dot file
1070 void ABCD::InequalityGraph::printEdge(raw_ostream &OS, Value *source,
1071                                       Edge *edge) const {
1072   Value *dest = edge->getVertex();
1073   APInt value = edge->getValue();
1074   bool upper = edge->isUpperBound();
1075
1076   OS << "\"";
1077   printName(OS, source);
1078   OS << "\"";
1079   OS << " -> ";
1080   OS << "\"";
1081   printName(OS, dest);
1082   OS << "\"";
1083   OS << " [label=\"" << value << "\"";
1084   if (upper) {
1085     OS << "color=\"blue\"";
1086   } else {
1087     OS << "color=\"red\"";
1088   }
1089   OS << "];\n";
1090 }
1091
1092 void ABCD::InequalityGraph::printName(raw_ostream &OS, Value *info) const {
1093   if (ConstantInt *CI = dyn_cast<ConstantInt>(info)) {
1094     OS << *CI;
1095   } else {
1096     if (!info->hasName()) {
1097       info->setName("V");
1098     }
1099     OS << info->getNameStr();
1100   }
1101 }
1102
1103 /// createABCDPass - The public interface to this file...
1104 FunctionPass *llvm::createABCDPass() {
1105   return new ABCD();
1106 }