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 proof 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   bool modified;
  61
  62   enum ProveResult {
  63     False = 0,
  64     Reduced = 1,
  65     True = 2
  66   };
  67
  68   typedef ProveResult (*meet_function)(ProveResult, ProveResult);
  69   static ProveResult max(ProveResult res1, ProveResult res2) {
  70     return (ProveResult) std::max(res1, res2);
  71   }
  72   static ProveResult min(ProveResult res1, ProveResult res2) {
  73     return (ProveResult) std::min(res1, res2);
  74   }
  75
  76   class Bound {
  77    public:
  78     Bound(APInt v, bool upper) : value(v), upper_bound(upper) {}
  79     Bound(const Bound *b, int cnst)
  80       : value(b->value - cnst), upper_bound(b->upper_bound) {}
  81     Bound(const Bound *b, const APInt &cnst)
  82       : value(b->value - cnst), upper_bound(b->upper_bound) {}
  83
  84     /// Test if Bound is an upper bound
  85     bool isUpperBound() const { return upper_bound; }
  86
  87     /// Get the bitwidth of this bound
  88     int32_t getBitWidth() const { return value.getBitWidth(); }
  89
  90     /// Creates a Bound incrementing the one received
  91     static Bound *createIncrement(const Bound *b) {
  92       return new Bound(b->isUpperBound() ? b->value+1 : b->value-1,
  93                        b->upper_bound);
  94     }
  95
  96     /// Creates a Bound decrementing the one received
  97     static Bound *createDecrement(const Bound *b) {
  98       return new Bound(b->isUpperBound() ? b->value-1 : b->value+1,
  99                        b->upper_bound);
 100     }
 101
 102     /// Test if two bounds are equal
 103     static bool eq(const Bound *a, const Bound *b) {
 104       if (!a || !b) return false;
 105
 106       assert(a->isUpperBound() == b->isUpperBound());
 107       return a->value == b->value;
 108     }
 109
 110     /// Test if val is less than or equal to Bound b
 111     static bool leq(APInt val, const Bound *b) {
 112       if (!b) return false;
 113       return b->isUpperBound() ? val.sle(b->value) : val.sge(b->value);
 114     }
 115
 116     /// Test if Bound a is less then or equal to Bound
 117     static bool leq(const Bound *a, const Bound *b) {
 118       if (!a || !b) return false;
 119
 120       assert(a->isUpperBound() == b->isUpperBound());
 121       return a->isUpperBound() ? a->value.sle(b->value) :
 122                                  a->value.sge(b->value);
 123     }
 124
 125     /// Test if Bound a is less then Bound b
 126     static bool lt(const Bound *a, const Bound *b) {
 127       if (!a || !b) return false;
 128
 129       assert(a->isUpperBound() == b->isUpperBound());
 130       return a->isUpperBound() ? a->value.slt(b->value) :
 131                                  a->value.sgt(b->value);
 132     }
 133
 134     /// Test if Bound b is greater then or equal val
 135     static bool geq(const Bound *b, APInt val) {
 136       return leq(val, b);
 137     }
 138
 139     /// Test if Bound a is greater then or equal Bound b
 140     static bool geq(const Bound *a, const Bound *b) {
 141       return leq(b, a);
 142     }
 143
 144    private:
 145     APInt value;
 146     bool upper_bound;
 147   };
 148
 149   /// This class is used to store results some parts of the graph,
 150   /// so information does not need to be recalculated. The maximum false,
 151   /// minimum true and minimum reduced results are stored
 152   class MemoizedResultChart {
 153    public:
 154      MemoizedResultChart() : max_false(NULL), min_true(NULL),
 155                              min_reduced(NULL) {}
 156
 157     /// Returns the max false
 158     Bound *getFalse() const { return max_false; }
 159
 160     /// Returns the min true
 161     Bound *getTrue() const { return min_true; }
 162
 163     /// Returns the min reduced
 164     Bound *getReduced() const { return min_reduced; }
 165
 166     /// Return the stored result for this bound
 167     ProveResult getResult(const Bound *bound) const;
 168
 169     /// Stores a false found
 170     void addFalse(Bound *bound);
 171
 172     /// Stores a true found
 173     void addTrue(Bound *bound);
 174
 175     /// Stores a Reduced found
 176     void addReduced(Bound *bound);
 177
 178     /// Clears redundant reduced
 179     /// If a min_true is smaller than a min_reduced then the min_reduced
 180     /// is unnecessary and then removed. It also works for min_reduced
 181     /// begin smaller than max_false.
 182     void clearRedundantReduced();
 183
 184     void clear() {
 185       delete max_false;
 186       delete min_true;
 187       delete min_reduced;
 188     }
 189
 190   private:
 191     Bound *max_false, *min_true, *min_reduced;
 192   };
 193
 194   /// This class stores the result found for a node of the graph,
 195   /// so these results do not need to be recalculate and only searched for.
 196   class MemoizedResult {
 197   public:
 198     /// Test if there is true result stored from b to a
 199     /// that is less then the bound
 200     bool hasTrue(Value *b, const Bound *bound) const {
 201       Bound *trueBound = map.lookup(b).getTrue();
 202       return trueBound && Bound::leq(trueBound, bound);
 203     }
 204
 205     /// Test if there is false result stored from b to a
 206     /// that is less then the bound
 207     bool hasFalse(Value *b, const Bound *bound) const {
 208       Bound *falseBound = map.lookup(b).getFalse();
 209       return falseBound && Bound::leq(falseBound, bound);
 210     }
 211
 212     /// Test if there is reduced result stored from b to a
 213     /// that is less then the bound
 214     bool hasReduced(Value *b, const Bound *bound) const {
 215       Bound *reducedBound = map.lookup(b).getReduced();
 216       return reducedBound && Bound::leq(reducedBound, bound);
 217     }
 218
 219     /// Returns the stored bound for b
 220     ProveResult getBoundResult(Value *b, Bound *bound) {
 221       return map[b].getResult(bound);
 222     }
 223
 224     /// Clears the map
 225     void clear() {
 226       DenseMapIterator<Value*, MemoizedResultChart> begin = map.begin();
 227       DenseMapIterator<Value*, MemoizedResultChart> end = map.end();
 228       for (; begin != end; ++begin) {
 229         begin->second.clear();
 230       }
 231       map.clear();
 232     }
 233
 234     /// Stores the bound found
 235     void updateBound(Value *b, Bound *bound, const ProveResult res);
 236
 237   private:
 238     // Maps a nod in the graph with its results found.
 239     DenseMap<Value*, MemoizedResultChart> map;
 240   };
 241
 242   /// This class represents an edge in the inequality graph used by the
 243   /// ABCD algorithm. An edge connects node v to node u with a value c if
 244   /// we could infer a constraint v <= u + c in the source program.
 245   class Edge {
 246   public:
 247     Edge(Value *V, APInt val, bool upper) : vertex(V), value(val),
 248                                             upper_bound(upper)
 249     {}
 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, end = phis_to_remove.size(); i < end; ++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   APInt MinusOne = APInt::getAllOnesValue(value.getBitWidth());
 670   inequality_graph.addEdge(I, BO, value, true);
 671   inequality_graph.addEdge(BO, I, value * MinusOne, false);
 672   createConstraintInstruction(I);
 673 }
 674
 675 /// Given a binary operator, we are only interest in the case
 676 /// that one operand is an Instruction and the other is a ConstantInt. In
 677 /// this case the method returns true, otherwise false. It also obtains the
 678 /// Instruction and ConstantInt from the BinaryOperator and returns it.
 679 bool ABCD::createBinaryOperatorInfo(BinaryOperator *BO, Instruction **I1,
 680                                     Instruction **I2, ConstantInt **C1,
 681                                     ConstantInt **C2) {
 682   Value *op1 = BO->getOperand(0);
 683   Value *op2 = BO->getOperand(1);
 684
 685   if ((*I1 = dyn_cast<Instruction>(op1))) {
 686     if ((*C2 = dyn_cast<ConstantInt>(op2)))
 687       return true; // First is Instruction and second ConstantInt
 688
 689     return false; // Both are Instruction
 690   } else {
 691     if ((*C1 = dyn_cast<ConstantInt>(op1)) &&
 692         (*I2 = dyn_cast<Instruction>(op2)))
 693       return true; // First is ConstantInt and second Instruction
 694
 695     return false; // Both are not Instruction
 696   }
 697 }
 698
 699 /// Creates constraints for Comparator Instructions.
 700 /// Only comparators that have any of the following operators
 701 /// are used to create constraints: >=, >, <=, <. And only if
 702 /// at least one operand is an Instruction. In a Comparator Instruction
 703 /// a op b, there will be 4 sigma functions a_t, a_f, b_t and b_f. Where
 704 /// t and f represent sigma for operands in true and false branches. The
 705 /// following constraints can be obtained. a_t <= a, a_f <= a, b_t <= b and
 706 /// b_f <= b. There are two more constraints that depend on the operator.
 707 /// For the operator <= : a_t <= b_t   and b_f <= a_f-1
 708 /// For the operator <  : a_t <= b_t-1 and b_f <= a_f
 709 /// For the operator >= : b_t <= a_t   and a_f <= b_f-1
 710 /// For the operator >  : b_t <= a_t-1 and a_f <= b_f
 711 void ABCD::createConstraintCmpInst(ICmpInst *ICI, TerminatorInst *TI) {
 712   Value *V_op1 = ICI->getOperand(0);
 713   Value *V_op2 = ICI->getOperand(1);
 714
 715   if (!isa<IntegerType>(V_op1->getType()))
 716     return;
 717
 718   Instruction *I_op1 = dyn_cast<Instruction>(V_op1);
 719   Instruction *I_op2 = dyn_cast<Instruction>(V_op2);
 720
 721   // Test if at least one operand is an Instruction
 722   if (!I_op1 && !I_op2)
 723     return;
 724
 725   BasicBlock *BB_succ_t = TI->getSuccessor(0);
 726   BasicBlock *BB_succ_f = TI->getSuccessor(1);
 727
 728   PHINode *SIG_op1_t = NULL, *SIG_op1_f = NULL,
 729           *SIG_op2_t = NULL, *SIG_op2_f = NULL;
 730
 731   createConstraintSigInst(I_op1, BB_succ_t, BB_succ_f,
 732                           &SIG_op1_t, &SIG_op1_f);
 733   createConstraintSigInst(I_op2, BB_succ_t, BB_succ_f,
 734                           &SIG_op2_t, &SIG_op2_f);
 735
 736   int32_t width = cast<IntegerType>(V_op1->getType())->getBitWidth();
 737   APInt MinusOne = APInt::getAllOnesValue(width);
 738   APInt Zero = APInt::getNullValue(width);
 739
 740   CmpInst::Predicate Pred = ICI->getPredicate();
 741   switch (Pred) {
 742   case CmpInst::ICMP_SGT: // signed greater than
 743     createConstraintSigSig(SIG_op2_t, SIG_op1_t, MinusOne);
 744     createConstraintSigSig(SIG_op1_f, SIG_op2_f, Zero);
 745     break;
 746
 747   case CmpInst::ICMP_SGE: // signed greater or equal
 748     createConstraintSigSig(SIG_op2_t, SIG_op1_t, Zero);
 749     createConstraintSigSig(SIG_op1_f, SIG_op2_f, MinusOne);
 750     break;
 751
 752   case CmpInst::ICMP_SLT: // signed less than
 753     createConstraintSigSig(SIG_op1_t, SIG_op2_t, MinusOne);
 754     createConstraintSigSig(SIG_op2_f, SIG_op1_f, Zero);
 755     break;
 756
 757   case CmpInst::ICMP_SLE: // signed less or equal
 758     createConstraintSigSig(SIG_op1_t, SIG_op2_t, Zero);
 759     createConstraintSigSig(SIG_op2_f, SIG_op1_f, MinusOne);
 760     break;
 761
 762   default:
 763     break;
 764   }
 765
 766   if (I_op1)
 767     createConstraintInstruction(I_op1);
 768   if (I_op2)
 769     createConstraintInstruction(I_op2);
 770 }
 771
 772 /// Creates constraints for PHI nodes.
 773 /// In a PHI node a = phi(b,c) we can create the constraint
 774 /// a<= max(b,c). With this constraint there will be the edges,
 775 /// b->a and c->a with weight 0 in the lower bound graph, and the edges
 776 /// a->b and a->c with weight 0 in the upper bound graph.
 777 void ABCD::createConstraintPHINode(PHINode *PN) {
 778   int32_t width = cast<IntegerType>(PN->getType())->getBitWidth();
 779   for (unsigned i = 0, end = PN->getNumIncomingValues(); i < end; ++i) {
 780     Value *V = PN->getIncomingValue(i);
 781     if (Instruction *I = dyn_cast<Instruction>(V)) {
 782       createConstraintInstruction(I);
 783     }
 784     inequality_graph.addEdge(V, PN, APInt(width, 0), true);
 785     inequality_graph.addEdge(V, PN, APInt(width, 0), false);
 786   }
 787 }
 788
 789 /// This method creates a constraint between a Sigma and an Instruction.
 790 /// These constraints are created as soon as we find a comparator that uses a
 791 /// SSI variable.
 792 void ABCD::createConstraintSigInst(Instruction *I_op, BasicBlock *BB_succ_t,
 793                                    BasicBlock *BB_succ_f, PHINode **SIG_op_t,
 794                                    PHINode **SIG_op_f) {
 795   *SIG_op_t = findSigma(BB_succ_t, I_op);
 796   *SIG_op_f = findSigma(BB_succ_f, I_op);
 797
 798   if (*SIG_op_t) {
 799     int32_t width = cast<IntegerType>((*SIG_op_t)->getType())->getBitWidth();
 800     inequality_graph.addEdge(I_op, *SIG_op_t, APInt(width, 0), true);
 801     inequality_graph.addEdge(*SIG_op_t, I_op, APInt(width, 0), false);
 802     created.insert(*SIG_op_t);
 803   }
 804   if (*SIG_op_f) {
 805     int32_t width = cast<IntegerType>((*SIG_op_f)->getType())->getBitWidth();
 806     inequality_graph.addEdge(I_op, *SIG_op_f, APInt(width, 0), true);
 807     inequality_graph.addEdge(*SIG_op_f, I_op, APInt(width, 0), false);
 808     created.insert(*SIG_op_f);
 809   }
 810 }
 811
 812 /// If PN_op1 and PN_o2 are different from NULL, create a constraint
 813 /// PN_op2 -> PN_op1 with value. In case any of them is NULL, replace
 814 /// with the respective V_op#, if V_op# is a ConstantInt.
 815 void ABCD::createConstraintSigSig(PHINode *SIG_op1, PHINode *SIG_op2,
 816                                   APInt value) {
 817   if (SIG_op1 && SIG_op2) {
 818     APInt MinusOne = APInt::getAllOnesValue(value.getBitWidth());
 819     inequality_graph.addEdge(SIG_op2, SIG_op1, value, true);
 820     inequality_graph.addEdge(SIG_op1, SIG_op2, value * MinusOne, false);
 821   }
 822 }
 823
 824 /// Returns the sigma representing the Instruction I in BasicBlock BB.
 825 /// Returns NULL in case there is no sigma for this Instruction in this
 826 /// Basic Block. This methods assume that sigmas are the first instructions
 827 /// in a block, and that there can be only two sigmas in a block. So it will
 828 /// only look on the first two instructions of BasicBlock BB.
 829 PHINode *ABCD::findSigma(BasicBlock *BB, Instruction *I) {
 830   // BB has more than one predecessor, BB cannot have sigmas.
 831   if (I == NULL || BB->getSinglePredecessor() == NULL)
 832     return NULL;
 833
 834   BasicBlock::iterator begin = BB->begin();
 835   BasicBlock::iterator end = BB->end();
 836
 837   for (unsigned i = 0; i < 2 && begin != end; ++i, ++begin) {
 838     Instruction *I_succ = begin;
 839     if (PHINode *PN = dyn_cast<PHINode>(I_succ))
 840       if (PN->getIncomingValue(0) == I)
 841         return PN;
 842   }
 843
 844   return NULL;
 845 }
 846
 847 /// Original ABCD algorithm to prove redundant checks.
 848 /// This implementation works on any kind of inequality branch.
 849 bool ABCD::demandProve(Value *a, Value *b, int c, bool upper_bound) {
 850   int32_t width = cast<IntegerType>(a->getType())->getBitWidth();
 851   Bound *bound = new Bound(APInt(width, c), upper_bound);
 852
 853   mem_result.clear();
 854   active.clear();
 855
 856   ProveResult res = prove(a, b, bound, 0);
 857   return res != False;
 858 }
 859
 860 /// Prove that distance between b and a is <= bound
 861 ABCD::ProveResult ABCD::prove(Value *a, Value *b, Bound *bound,
 862                               unsigned level) {
 863   // if (C[b-a<=e] == True for some e <= bound
 864   // Same or stronger difference was already proven
 865   if (mem_result.hasTrue(b, bound))
 866     return True;
 867
 868   // if (C[b-a<=e] == False for some e >= bound
 869   // Same or weaker difference was already disproved
 870   if (mem_result.hasFalse(b, bound))
 871     return False;
 872
 873   // if (C[b-a<=e] == Reduced for some e <= bound
 874   // b is on a cycle that was reduced for same or stronger difference
 875   if (mem_result.hasReduced(b, bound))
 876     return Reduced;
 877
 878   // traversal reached the source vertex
 879   if (a == b && Bound::geq(bound, APInt(bound->getBitWidth(), 0, true)))
 880     return True;
 881
 882   // if b has no predecessor then fail
 883   if (!inequality_graph.hasEdge(b, bound->isUpperBound()))
 884     return False;
 885
 886   // a cycle was encountered
 887   if (active.count(b)) {
 888     if (Bound::leq(active.lookup(b), bound))
 889       return Reduced; // a "harmless" cycle
 890
 891     return False; // an amplifying cycle
 892   }
 893
 894   active[b] = bound;
 895   PHINode *PN = dyn_cast<PHINode>(b);
 896
 897   // Test if a Value is a Phi. If it is a PHINode with more than 1 incoming
 898   // value, then it is a phi, if it has 1 incoming value it is a sigma.
 899   if (PN && PN->getNumIncomingValues() > 1)
 900     updateMemDistance(a, b, bound, level, min);
 901   else
 902     updateMemDistance(a, b, bound, level, max);
 903
 904   active.erase(b);
 905
 906   ABCD::ProveResult res = mem_result.getBoundResult(b, bound);
 907   return res;
 908 }
 909
 910 /// Updates the distance value for a and b
 911 void ABCD::updateMemDistance(Value *a, Value *b, Bound *bound, unsigned level,
 912                              meet_function meet) {
 913   ABCD::ProveResult res = (meet == max) ? False : True;
 914
 915   SmallPtrSet<Edge *, 16> Edges = inequality_graph.getEdges(b);
 916   SmallPtrSet<Edge *, 16>::iterator begin = Edges.begin(), end = Edges.end();
 917
 918   for (; begin != end ; ++begin) {
 919     if (((res >= Reduced) && (meet == max)) ||
 920        ((res == False) && (meet == min))) {
 921         break;
 922     }
 923     Edge *in = *begin;
 924     if (in->isUpperBound() == bound->isUpperBound()) {
 925       Value *succ = in->getVertex();
 926       res = meet(res, prove(a, succ, new Bound(bound, in->getValue()),
 927                  level+1));
 928     }
 929   }
 930
 931   mem_result.updateBound(b, bound, res);
 932 }
 933
 934 /// Return the stored result for this bound
 935 ABCD::ProveResult ABCD::MemoizedResultChart::getResult(const Bound *bound)const{
 936   if (max_false && Bound::leq(bound, max_false))
 937     return False;
 938   if (min_true && Bound::leq(min_true, bound))
 939     return True;
 940   if (min_reduced && Bound::leq(min_reduced, bound))
 941     return Reduced;
 942   return False;
 943 }
 944
 945 /// Stores a false found
 946 void ABCD::MemoizedResultChart::addFalse(Bound *bound) {
 947   if (!max_false || Bound::leq(max_false, bound))
 948     max_false = bound;
 949
 950   if (Bound::eq(max_false, min_reduced))
 951     min_reduced = Bound::createIncrement(min_reduced);
 952   if (Bound::eq(max_false, min_true))
 953     min_true = Bound::createIncrement(min_true);
 954   if (Bound::eq(min_reduced, min_true))
 955     min_reduced = NULL;
 956   clearRedundantReduced();
 957 }
 958
 959 /// Stores a true found
 960 void ABCD::MemoizedResultChart::addTrue(Bound *bound) {
 961   if (!min_true || Bound::leq(bound, min_true))
 962     min_true = bound;
 963
 964   if (Bound::eq(min_true, min_reduced))
 965     min_reduced = Bound::createDecrement(min_reduced);
 966   if (Bound::eq(min_true, max_false))
 967     max_false = Bound::createDecrement(max_false);
 968   if (Bound::eq(max_false, min_reduced))
 969     min_reduced = NULL;
 970   clearRedundantReduced();
 971 }
 972
 973 /// Stores a Reduced found
 974 void ABCD::MemoizedResultChart::addReduced(Bound *bound) {
 975   if (!min_reduced || Bound::leq(bound, min_reduced))
 976     min_reduced = bound;
 977
 978   if (Bound::eq(min_reduced, min_true))
 979     min_true = Bound::createIncrement(min_true);
 980   if (Bound::eq(min_reduced, max_false))
 981     max_false = Bound::createDecrement(max_false);
 982 }
 983
 984 /// Clears redundant reduced
 985 /// If a min_true is smaller than a min_reduced then the min_reduced
 986 /// is unnecessary and then removed. It also works for min_reduced
 987 /// begin smaller than max_false.
 988 void ABCD::MemoizedResultChart::clearRedundantReduced() {
 989   if (min_true && min_reduced && Bound::lt(min_true, min_reduced))
 990     min_reduced = NULL;
 991   if (max_false && min_reduced && Bound::lt(min_reduced, max_false))
 992     min_reduced = NULL;
 993 }
 994
 995 /// Stores the bound found
 996 void ABCD::MemoizedResult::updateBound(Value *b, Bound *bound,
 997                                        const ProveResult res) {
 998   if (res == False) {
 999     map[b].addFalse(bound);
1000   } else if (res == True) {
1001     map[b].addTrue(bound);
1002   } else {
1003     map[b].addReduced(bound);
1004   }
1005 }
1006
1007 /// Adds an edge from V_from to V_to with weight value
1008 void ABCD::InequalityGraph::addEdge(Value *V_to, Value *V_from,
1009                               APInt value, bool upper) {
1010   assert(V_from->getType() == V_to->getType());
1011   assert(cast<IntegerType>(V_from->getType())->getBitWidth() ==
1012          value.getBitWidth());
1013
1014   DenseMap<Value *, SmallPtrSet<Edge *, 16> >::iterator from;
1015   from = addNode(V_from);
1016   from->second.insert(new Edge(V_to, value, upper));
1017 }
1018
1019 /// Test if there is any edge from V in the upper direction
1020 bool ABCD::InequalityGraph::hasEdge(Value *V, bool upper) const {
1021   SmallPtrSet<Edge *, 16> it = graph.lookup(V);
1022
1023   SmallPtrSet<Edge *, 16>::iterator begin = it.begin();
1024   SmallPtrSet<Edge *, 16>::iterator end = it.end();
1025   for (; begin != end; ++begin) {
1026     if ((*begin)->isUpperBound() == upper) {
1027       return true;
1028     }
1029   }
1030   return false;
1031 }
1032
1033 /// Prints the header of the dot file
1034 void ABCD::InequalityGraph::printHeader(raw_ostream &OS, Function &F) const {
1035   OS << "digraph dotgraph {\n";
1036   OS << "label=\"Inequality Graph for \'";
1037   OS << F.getNameStr() << "\' function\";\n";
1038   OS << "node [shape=record,fontname=\"Times-Roman\",fontsize=14];\n";
1039 }
1040
1041 /// Prints the body of the dot file
1042 void ABCD::InequalityGraph::printBody(raw_ostream &OS) const {
1043   DenseMap<Value *, SmallPtrSet<Edge *, 16> >::iterator begin =
1044       graph.begin(), end = graph.end();
1045
1046   for (; begin != end ; ++begin) {
1047     SmallPtrSet<Edge *, 16>::iterator begin_par =
1048         begin->second.begin(), end_par = begin->second.end();
1049     Value *source = begin->first;
1050
1051     printVertex(OS, source);
1052
1053     for (; begin_par != end_par ; ++begin_par) {
1054       Edge *edge = *begin_par;
1055       printEdge(OS, source, edge);
1056     }
1057   }
1058 }
1059
1060 /// Prints vertex source to the dot file
1061 ///
1062 void ABCD::InequalityGraph::printVertex(raw_ostream &OS, Value *source) const {
1063   OS << "\"";
1064   printName(OS, source);
1065   OS << "\"";
1066   OS << " [label=\"{";
1067   printName(OS, source);
1068   OS << "}\"];\n";
1069 }
1070
1071 /// Prints the edge to the dot file
1072 void ABCD::InequalityGraph::printEdge(raw_ostream &OS, Value *source,
1073                                       Edge *edge) const {
1074   Value *dest = edge->getVertex();
1075   APInt value = edge->getValue();
1076   bool upper = edge->isUpperBound();
1077
1078   OS << "\"";
1079   printName(OS, source);
1080   OS << "\"";
1081   OS << " -> ";
1082   OS << "\"";
1083   printName(OS, dest);
1084   OS << "\"";
1085   OS << " [label=\"" << value << "\"";
1086   if (upper) {
1087     OS << "color=\"blue\"";
1088   } else {
1089     OS << "color=\"red\"";
1090   }
1091   OS << "];\n";
1092 }
1093
1094 void ABCD::InequalityGraph::printName(raw_ostream &OS, Value *info) const {
1095   if (ConstantInt *CI = dyn_cast<ConstantInt>(info)) {
1096     OS << *CI->getValue().getRawData();
1097   } else {
1098     if (info->getName() == "") {
1099       info->setName("V");
1100     }
1101     OS << info->getNameStr();
1102   }
1103 }
1104
1105 /// createABCDPass - The public interface to this file...
1106 FunctionPass *llvm::createABCDPass() {
1107   return new ABCD();
1108 }