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