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 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 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       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       assert(a.isUpperBound() == b.isUpperBound());
 120       return a.isUpperBound() ? a.value.sle(b.value) :
 121                                 a.value.sge(b.value);
 122     }
 123
 124     /// Test if Bound a is less then Bound b
 125     static bool lt(const Bound &a, const Bound &b) {
 126       assert(a.isUpperBound() == b.isUpperBound());
 127       return a.isUpperBound() ? a.value.slt(b.value) :
 128                                 a.value.sgt(b.value);
 129     }
 130
 131     /// Test if Bound b is greater then or equal val
 132     static bool geq(const Bound &b, APInt val) {
 133       return leq(val, b);
 134     }
 135
 136     /// Test if Bound a is greater then or equal Bound b
 137     static bool geq(const Bound &a, const Bound &b) {
 138       return leq(b, a);
 139     }
 140
 141    private:
 142     APInt value;
 143     bool upper_bound;
 144   };
 145
 146   /// This class is used to store results some parts of the graph,
 147   /// so information does not need to be recalculated. The maximum false,
 148   /// minimum true and minimum reduced results are stored
 149   class MemoizedResultChart {
 150    public:
 151      MemoizedResultChart() {}
 152      MemoizedResultChart(const MemoizedResultChart &other) {
 153        if (other.max_false)
 154          max_false.reset(new Bound(*other.max_false));
 155        if (other.min_true)
 156          min_true.reset(new Bound(*other.min_true));
 157        if (other.min_reduced)
 158          min_reduced.reset(new Bound(*other.min_reduced));
 159      }
 160
 161     /// Returns the max false
 162     const Bound *getFalse() const { return max_false.get(); }
 163
 164     /// Returns the min true
 165     const Bound *getTrue() const { return min_true.get(); }
 166
 167     /// Returns the min reduced
 168     const Bound *getReduced() const { return min_reduced.get(); }
 169
 170     /// Return the stored result for this bound
 171     ProveResult getResult(const Bound &bound) const;
 172
 173     /// Stores a false found
 174     void addFalse(const Bound &bound);
 175
 176     /// Stores a true found
 177     void addTrue(const Bound &bound);
 178
 179     /// Stores a Reduced found
 180     void addReduced(const Bound &bound);
 181
 182     /// Clears redundant reduced
 183     /// If a min_true is smaller than a min_reduced then the min_reduced
 184     /// is unnecessary and then removed. It also works for min_reduced
 185     /// begin smaller than max_false.
 186     void clearRedundantReduced();
 187
 188     void clear() {
 189       max_false.reset();
 190       min_true.reset();
 191       min_reduced.reset();
 192     }
 193
 194   private:
 195     OwningPtr<Bound> max_false, min_true, min_reduced;
 196   };
 197
 198   /// This class stores the result found for a node of the graph,
 199   /// so these results do not need to be recalculated, only searched for.
 200   class MemoizedResult {
 201   public:
 202     /// Test if there is true result stored from b to a
 203     /// that is less then the bound
 204     bool hasTrue(Value *b, const Bound &bound) const {
 205       const Bound *trueBound = map.lookup(b).getTrue();
 206       return trueBound && Bound::leq(*trueBound, bound);
 207     }
 208
 209     /// Test if there is false result stored from b to a
 210     /// that is less then the bound
 211     bool hasFalse(Value *b, const Bound &bound) const {
 212       const Bound *falseBound = map.lookup(b).getFalse();
 213       return falseBound && Bound::leq(*falseBound, bound);
 214     }
 215
 216     /// Test if there is reduced result stored from b to a
 217     /// that is less then the bound
 218     bool hasReduced(Value *b, const Bound &bound) const {
 219       const Bound *reducedBound = map.lookup(b).getReduced();
 220       return reducedBound && Bound::leq(*reducedBound, bound);
 221     }
 222
 223     /// Returns the stored bound for b
 224     ProveResult getBoundResult(Value *b, const Bound &bound) {
 225       return map[b].getResult(bound);
 226     }
 227
 228     /// Clears the map
 229     void clear() {
 230       DenseMapIterator<Value*, MemoizedResultChart> begin = map.begin();
 231       DenseMapIterator<Value*, MemoizedResultChart> end = map.end();
 232       for (; begin != end; ++begin) {
 233         begin->second.clear();
 234       }
 235       map.clear();
 236     }
 237
 238     /// Stores the bound found
 239     void updateBound(Value *b, const Bound &bound, const ProveResult res);
 240
 241   private:
 242     // Maps a nod in the graph with its results found.
 243     DenseMap<Value*, MemoizedResultChart> map;
 244   };
 245
 246   /// This class represents an edge in the inequality graph used by the
 247   /// ABCD algorithm. An edge connects node v to node u with a value c if
 248   /// we could infer a constraint v <= u + c in the source program.
 249   class Edge {
 250   public:
 251     Edge(Value *V, APInt val, bool upper)
 252       : vertex(V), value(val), upper_bound(upper) {}
 253
 254     Value *getVertex() const { return vertex; }
 255     const APInt &getValue() const { return value; }
 256     bool isUpperBound() const { return upper_bound; }
 257
 258   private:
 259     Value *vertex;
 260     APInt value;
 261     bool upper_bound;
 262   };
 263
 264   /// Weighted and Directed graph to represent constraints.
 265   /// There is one type of constraint, a <= b + X, which will generate an
 266   /// edge from b to a with weight X.
 267   class InequalityGraph {
 268   public:
 269
 270     /// Adds an edge from V_from to V_to with weight value
 271     void addEdge(Value *V_from, Value *V_to, APInt value, bool upper);
 272
 273     /// Test if there is a node V
 274     bool hasNode(Value *V) const { return graph.count(V); }
 275
 276     /// Test if there is any edge from V in the upper direction
 277     bool hasEdge(Value *V, bool upper) const;
 278
 279     /// Returns all edges pointed by vertex V
 280     SmallVector<Edge, 16> getEdges(Value *V) const {
 281       return graph.lookup(V);
 282     }
 283
 284     /// Prints the graph in dot format.
 285     /// Blue edges represent upper bound and Red lower bound.
 286     void printGraph(raw_ostream &OS, Function &F) const {
 287       printHeader(OS, F);
 288       printBody(OS);
 289       printFooter(OS);
 290     }
 291
 292     /// Clear the graph
 293     void clear() {
 294       graph.clear();
 295     }
 296
 297   private:
 298     DenseMap<Value *, SmallVector<Edge, 16> > graph;
 299
 300     /// Prints the header of the dot file
 301     void printHeader(raw_ostream &OS, Function &F) const;
 302
 303     /// Prints the footer of the dot file
 304     void printFooter(raw_ostream &OS) const {
 305       OS << "}\n";
 306     }
 307
 308     /// Prints the body of the dot file
 309     void printBody(raw_ostream &OS) const;
 310
 311     /// Prints vertex source to the dot file
 312     void printVertex(raw_ostream &OS, Value *source) const;
 313
 314     /// Prints the edge to the dot file
 315     void printEdge(raw_ostream &OS, Value *source, const Edge &edge) const;
 316
 317     void printName(raw_ostream &OS, Value *info) const;
 318   };
 319
 320   /// Iterates through all BasicBlocks, if the Terminator Instruction
 321   /// uses an Comparator Instruction, all operands of this comparator
 322   /// are sent to be transformed to SSI. Only Instruction operands are
 323   /// transformed.
 324   void createSSI(Function &F);
 325
 326   /// Creates the graphs for this function.
 327   /// It will look for all comparators used in branches, and create them.
 328   /// These comparators will create constraints for any instruction as an
 329   /// operand.
 330   void executeABCD(Function &F);
 331
 332   /// Seeks redundancies in the comparator instruction CI.
 333   /// If the ABCD algorithm can prove that the comparator CI always
 334   /// takes one way, then the Terminator Instruction TI is substituted from
 335   /// a conditional branch to a unconditional one.
 336   /// This code basically receives a comparator, and verifies which kind of
 337   /// instruction it is. Depending on the kind of instruction, we use different
 338   /// strategies to prove its redundancy.
 339   void seekRedundancy(ICmpInst *ICI, TerminatorInst *TI);
 340
 341   /// Substitutes Terminator Instruction TI, that is a conditional branch,
 342   /// with one unconditional branch. Succ_edge determines if the new
 343   /// unconditional edge will be the first or second edge of the former TI
 344   /// instruction.
 345   void removeRedundancy(TerminatorInst *TI, bool Succ_edge);
 346
 347   /// When an conditional branch is removed, the BasicBlock that is no longer
 348   /// reachable will have problems in phi functions. This method fixes these
 349   /// phis removing the former BasicBlock from the list of incoming BasicBlocks
 350   /// of all phis. In case the phi remains with no predecessor it will be
 351   /// marked to be removed later.
 352   void fixPhi(BasicBlock *BB, BasicBlock *Succ);
 353
 354   /// Removes phis that have no predecessor
 355   void removePhis();
 356
 357   /// Creates constraints for Instructions.
 358   /// If the constraint for this instruction has already been created
 359   /// nothing is done.
 360   void createConstraintInstruction(Instruction *I);
 361
 362   /// Creates constraints for Binary Operators.
 363   /// It will create constraints only for addition and subtraction,
 364   /// the other binary operations are not treated by ABCD.
 365   /// For additions in the form a = b + X and a = X + b, where X is a constant,
 366   /// the constraint a <= b + X can be obtained. For this constraint, an edge
 367   /// a->b with weight X is added to the lower bound graph, and an edge
 368   /// b->a with weight -X is added to the upper bound graph.
 369   /// Only subtractions in the format a = b - X is used by ABCD.
 370   /// Edges are created using the same semantic as addition.
 371   void createConstraintBinaryOperator(BinaryOperator *BO);
 372
 373   /// Creates constraints for Comparator Instructions.
 374   /// Only comparators that have any of the following operators
 375   /// are used to create constraints: >=, >, <=, <. And only if
 376   /// at least one operand is an Instruction. In a Comparator Instruction
 377   /// a op b, there will be 4 sigma functions a_t, a_f, b_t and b_f. Where
 378   /// t and f represent sigma for operands in true and false branches. The
 379   /// following constraints can be obtained. a_t <= a, a_f <= a, b_t <= b and
 380   /// b_f <= b. There are two more constraints that depend on the operator.
 381   /// For the operator <= : a_t <= b_t   and b_f <= a_f-1
 382   /// For the operator <  : a_t <= b_t-1 and b_f <= a_f
 383   /// For the operator >= : b_t <= a_t   and a_f <= b_f-1
 384   /// For the operator >  : b_t <= a_t-1 and a_f <= b_f
 385   void createConstraintCmpInst(ICmpInst *ICI, TerminatorInst *TI);
 386
 387   /// Creates constraints for PHI nodes.
 388   /// In a PHI node a = phi(b,c) we can create the constraint
 389   /// a<= max(b,c). With this constraint there will be the edges,
 390   /// b->a and c->a with weight 0 in the lower bound graph, and the edges
 391   /// a->b and a->c with weight 0 in the upper bound graph.
 392   void createConstraintPHINode(PHINode *PN);
 393
 394   /// Given a binary operator, we are only interest in the case
 395   /// that one operand is an Instruction and the other is a ConstantInt. In
 396   /// this case the method returns true, otherwise false. It also obtains the
 397   /// Instruction and ConstantInt from the BinaryOperator and returns it.
 398   bool createBinaryOperatorInfo(BinaryOperator *BO, Instruction **I1,
 399                                 Instruction **I2, ConstantInt **C1,
 400                                 ConstantInt **C2);
 401
 402   /// This method creates a constraint between a Sigma and an Instruction.
 403   /// These constraints are created as soon as we find a comparator that uses a
 404   /// SSI variable.
 405   void createConstraintSigInst(Instruction *I_op, BasicBlock *BB_succ_t,
 406                                BasicBlock *BB_succ_f, PHINode **SIG_op_t,
 407                                PHINode **SIG_op_f);
 408
 409   /// If PN_op1 and PN_o2 are different from NULL, create a constraint
 410   /// PN_op2 -> PN_op1 with value. In case any of them is NULL, replace
 411   /// with the respective V_op#, if V_op# is a ConstantInt.
 412   void createConstraintSigSig(PHINode *SIG_op1, PHINode *SIG_op2,
 413                               ConstantInt *V_op1, ConstantInt *V_op2,
 414                               APInt value);
 415
 416   /// Returns the sigma representing the Instruction I in BasicBlock BB.
 417   /// Returns NULL in case there is no sigma for this Instruction in this
 418   /// Basic Block. This methods assume that sigmas are the first instructions
 419   /// in a block, and that there can be only two sigmas in a block. So it will
 420   /// only look on the first two instructions of BasicBlock BB.
 421   PHINode *findSigma(BasicBlock *BB, Instruction *I);
 422
 423   /// Original ABCD algorithm to prove redundant checks.
 424   /// This implementation works on any kind of inequality branch.
 425   bool demandProve(Value *a, Value *b, int c, bool upper_bound);
 426
 427   /// Prove that distance between b and a is <= bound
 428   ProveResult prove(Value *a, Value *b, const Bound &bound, unsigned level);
 429
 430   /// Updates the distance value for a and b
 431   void updateMemDistance(Value *a, Value *b, const Bound &bound, unsigned level,
 432                          meet_function meet);
 433
 434   InequalityGraph inequality_graph;
 435   MemoizedResult mem_result;
 436   DenseMap<Value*, const Bound*> active;
 437   SmallPtrSet<Value*, 16> created;
 438   SmallVector<PHINode *, 16> phis_to_remove;
 439 };
 440
 441 }  // end anonymous namespace.
 442
 443 char ABCD::ID = 0;
 444 INITIALIZE_PASS(ABCD, "abcd",
 445                 "ABCD: Eliminating Array Bounds Checks on Demand",
 446                 false, false);
 447
 448 bool ABCD::runOnFunction(Function &F) {
 449   modified = false;
 450   createSSI(F);
 451   executeABCD(F);
 452   DEBUG(inequality_graph.printGraph(dbgs(), 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 || !ICI->getOperand(0)->getType()->isIntegerTy())
 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 (!V_op1->getType()->isIntegerTy())
 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   ConstantInt *CI1 = dyn_cast<ConstantInt>(V_op1);
 739   ConstantInt *CI2 = dyn_cast<ConstantInt>(V_op2);
 740   switch (Pred) {
 741   case CmpInst::ICMP_SGT:  // signed greater than
 742     createConstraintSigSig(SIG_op2_t, SIG_op1_t, CI2, CI1, MinusOne);
 743     createConstraintSigSig(SIG_op1_f, SIG_op2_f, CI1, CI2, Zero);
 744     break;
 745
 746   case CmpInst::ICMP_SGE:  // signed greater or equal
 747     createConstraintSigSig(SIG_op2_t, SIG_op1_t, CI2, CI1, Zero);
 748     createConstraintSigSig(SIG_op1_f, SIG_op2_f, CI1, CI2, MinusOne);
 749     break;
 750
 751   case CmpInst::ICMP_SLT:  // signed less than
 752     createConstraintSigSig(SIG_op1_t, SIG_op2_t, CI1, CI2, MinusOne);
 753     createConstraintSigSig(SIG_op2_f, SIG_op1_f, CI2, CI1, Zero);
 754     break;
 755
 756   case CmpInst::ICMP_SLE:  // signed less or equal
 757     createConstraintSigSig(SIG_op1_t, SIG_op2_t, CI1, CI2, Zero);
 758     createConstraintSigSig(SIG_op2_f, SIG_op1_f, CI2, CI1, MinusOne);
 759     break;
 760
 761   default:
 762     break;
 763   }
 764
 765   if (I_op1)
 766     createConstraintInstruction(I_op1);
 767   if (I_op2)
 768     createConstraintInstruction(I_op2);
 769 }
 770
 771 /// Creates constraints for PHI nodes.
 772 /// In a PHI node a = phi(b,c) we can create the constraint
 773 /// a<= max(b,c). With this constraint there will be the edges,
 774 /// b->a and c->a with weight 0 in the lower bound graph, and the edges
 775 /// a->b and a->c with weight 0 in the upper bound graph.
 776 void ABCD::createConstraintPHINode(PHINode *PN) {
 777   // FIXME: We really want to disallow sigma nodes, but I don't know the best
 778   // way to detect the other than this.
 779   if (PN->getNumOperands() == 2) return;
 780
 781   int32_t width = cast<IntegerType>(PN->getType())->getBitWidth();
 782   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 783     Value *V = PN->getIncomingValue(i);
 784     if (Instruction *I = dyn_cast<Instruction>(V)) {
 785       createConstraintInstruction(I);
 786     }
 787     inequality_graph.addEdge(V, PN, APInt(width, 0), true);
 788     inequality_graph.addEdge(V, PN, APInt(width, 0), false);
 789   }
 790 }
 791
 792 /// This method creates a constraint between a Sigma and an Instruction.
 793 /// These constraints are created as soon as we find a comparator that uses a
 794 /// SSI variable.
 795 void ABCD::createConstraintSigInst(Instruction *I_op, BasicBlock *BB_succ_t,
 796                                    BasicBlock *BB_succ_f, PHINode **SIG_op_t,
 797                                    PHINode **SIG_op_f) {
 798   *SIG_op_t = findSigma(BB_succ_t, I_op);
 799   *SIG_op_f = findSigma(BB_succ_f, I_op);
 800
 801   if (*SIG_op_t) {
 802     int32_t width = cast<IntegerType>((*SIG_op_t)->getType())->getBitWidth();
 803     inequality_graph.addEdge(I_op, *SIG_op_t, APInt(width, 0), true);
 804     inequality_graph.addEdge(*SIG_op_t, I_op, APInt(width, 0), false);
 805   }
 806   if (*SIG_op_f) {
 807     int32_t width = cast<IntegerType>((*SIG_op_f)->getType())->getBitWidth();
 808     inequality_graph.addEdge(I_op, *SIG_op_f, APInt(width, 0), true);
 809     inequality_graph.addEdge(*SIG_op_f, I_op, APInt(width, 0), false);
 810   }
 811 }
 812
 813 /// If PN_op1 and PN_o2 are different from NULL, create a constraint
 814 /// PN_op2 -> PN_op1 with value. In case any of them is NULL, replace
 815 /// with the respective V_op#, if V_op# is a ConstantInt.
 816 void ABCD::createConstraintSigSig(PHINode *SIG_op1, PHINode *SIG_op2,
 817                                   ConstantInt *V_op1, ConstantInt *V_op2,
 818                                   APInt value) {
 819   if (SIG_op1 && SIG_op2) {
 820     inequality_graph.addEdge(SIG_op2, SIG_op1, value, true);
 821     inequality_graph.addEdge(SIG_op1, SIG_op2, -value, false);
 822   } else if (SIG_op1 && V_op2) {
 823     inequality_graph.addEdge(V_op2, SIG_op1, value, true);
 824     inequality_graph.addEdge(SIG_op1, V_op2, -value, false);
 825   } else if (SIG_op2 && V_op1) {
 826     inequality_graph.addEdge(SIG_op2, V_op1, value, true);
 827     inequality_graph.addEdge(V_op1, SIG_op2, -value, false);
 828   }
 829 }
 830
 831 /// Returns the sigma representing the Instruction I in BasicBlock BB.
 832 /// Returns NULL in case there is no sigma for this Instruction in this
 833 /// Basic Block. This methods assume that sigmas are the first instructions
 834 /// in a block, and that there can be only two sigmas in a block. So it will
 835 /// only look on the first two instructions of BasicBlock BB.
 836 PHINode *ABCD::findSigma(BasicBlock *BB, Instruction *I) {
 837   // BB has more than one predecessor, BB cannot have sigmas.
 838   if (I == NULL || BB->getSinglePredecessor() == NULL)
 839     return NULL;
 840
 841   BasicBlock::iterator begin = BB->begin();
 842   BasicBlock::iterator end = BB->end();
 843
 844   for (unsigned i = 0; i < 2 && begin != end; ++i, ++begin) {
 845     Instruction *I_succ = begin;
 846     if (PHINode *PN = dyn_cast<PHINode>(I_succ))
 847       if (PN->getIncomingValue(0) == I)
 848         return PN;
 849   }
 850
 851   return NULL;
 852 }
 853
 854 /// Original ABCD algorithm to prove redundant checks.
 855 /// This implementation works on any kind of inequality branch.
 856 bool ABCD::demandProve(Value *a, Value *b, int c, bool upper_bound) {
 857   int32_t width = cast<IntegerType>(a->getType())->getBitWidth();
 858   Bound bound(APInt(width, c), upper_bound);
 859
 860   mem_result.clear();
 861   active.clear();
 862
 863   ProveResult res = prove(a, b, bound, 0);
 864   return res != False;
 865 }
 866
 867 /// Prove that distance between b and a is <= bound
 868 ABCD::ProveResult ABCD::prove(Value *a, Value *b, const Bound &bound,
 869                               unsigned level) {
 870   // if (C[b-a<=e] == True for some e <= bound
 871   // Same or stronger difference was already proven
 872   if (mem_result.hasTrue(b, bound))
 873     return True;
 874
 875   // if (C[b-a<=e] == False for some e >= bound
 876   // Same or weaker difference was already disproved
 877   if (mem_result.hasFalse(b, bound))
 878     return False;
 879
 880   // if (C[b-a<=e] == Reduced for some e <= bound
 881   // b is on a cycle that was reduced for same or stronger difference
 882   if (mem_result.hasReduced(b, bound))
 883     return Reduced;
 884
 885   // traversal reached the source vertex
 886   if (a == b && Bound::geq(bound, APInt(bound.getBitWidth(), 0, true)))
 887     return True;
 888
 889   // if b has no predecessor then fail
 890   if (!inequality_graph.hasEdge(b, bound.isUpperBound()))
 891     return False;
 892
 893   // a cycle was encountered
 894   if (active.count(b)) {
 895     if (Bound::leq(*active.lookup(b), bound))
 896       return Reduced; // a "harmless" cycle
 897
 898     return False; // an amplifying cycle
 899   }
 900
 901   active[b] = &bound;
 902   PHINode *PN = dyn_cast<PHINode>(b);
 903
 904   // Test if a Value is a Phi. If it is a PHINode with more than 1 incoming
 905   // value, then it is a phi, if it has 1 incoming value it is a sigma.
 906   if (PN && PN->getNumIncomingValues() > 1)
 907     updateMemDistance(a, b, bound, level, min);
 908   else
 909     updateMemDistance(a, b, bound, level, max);
 910
 911   active.erase(b);
 912
 913   ABCD::ProveResult res = mem_result.getBoundResult(b, bound);
 914   return res;
 915 }
 916
 917 /// Updates the distance value for a and b
 918 void ABCD::updateMemDistance(Value *a, Value *b, const Bound &bound,
 919                              unsigned level, meet_function meet) {
 920   ABCD::ProveResult res = (meet == max) ? False : True;
 921
 922   SmallVector<Edge, 16> Edges = inequality_graph.getEdges(b);
 923   SmallVector<Edge, 16>::iterator begin = Edges.begin(), end = Edges.end();
 924
 925   for (; begin != end ; ++begin) {
 926     if (((res >= Reduced) && (meet == max)) ||
 927        ((res == False) && (meet == min))) {
 928       break;
 929     }
 930     const Edge &in = *begin;
 931     if (in.isUpperBound() == bound.isUpperBound()) {
 932       Value *succ = in.getVertex();
 933       res = meet(res, prove(a, succ, Bound(bound, in.getValue()),
 934                             level+1));
 935     }
 936   }
 937
 938   mem_result.updateBound(b, bound, res);
 939 }
 940
 941 /// Return the stored result for this bound
 942 ABCD::ProveResult ABCD::MemoizedResultChart::getResult(const Bound &bound)const{
 943   if (max_false && Bound::leq(bound, *max_false))
 944     return False;
 945   if (min_true && Bound::leq(*min_true, bound))
 946     return True;
 947   if (min_reduced && Bound::leq(*min_reduced, bound))
 948     return Reduced;
 949   return False;
 950 }
 951
 952 /// Stores a false found
 953 void ABCD::MemoizedResultChart::addFalse(const Bound &bound) {
 954   if (!max_false || Bound::leq(*max_false, bound))
 955     max_false.reset(new Bound(bound));
 956
 957   if (Bound::eq(max_false.get(), min_reduced.get()))
 958     min_reduced.reset(new Bound(Bound::createIncrement(*min_reduced)));
 959   if (Bound::eq(max_false.get(), min_true.get()))
 960     min_true.reset(new Bound(Bound::createIncrement(*min_true)));
 961   if (Bound::eq(min_reduced.get(), min_true.get()))
 962     min_reduced.reset();
 963   clearRedundantReduced();
 964 }
 965
 966 /// Stores a true found
 967 void ABCD::MemoizedResultChart::addTrue(const Bound &bound) {
 968   if (!min_true || Bound::leq(bound, *min_true))
 969     min_true.reset(new Bound(bound));
 970
 971   if (Bound::eq(min_true.get(), min_reduced.get()))
 972     min_reduced.reset(new Bound(Bound::createDecrement(*min_reduced)));
 973   if (Bound::eq(min_true.get(), max_false.get()))
 974     max_false.reset(new Bound(Bound::createDecrement(*max_false)));
 975   if (Bound::eq(max_false.get(), min_reduced.get()))
 976     min_reduced.reset();
 977   clearRedundantReduced();
 978 }
 979
 980 /// Stores a Reduced found
 981 void ABCD::MemoizedResultChart::addReduced(const Bound &bound) {
 982   if (!min_reduced || Bound::leq(bound, *min_reduced))
 983     min_reduced.reset(new Bound(bound));
 984
 985   if (Bound::eq(min_reduced.get(), min_true.get()))
 986     min_true.reset(new Bound(Bound::createIncrement(*min_true)));
 987   if (Bound::eq(min_reduced.get(), max_false.get()))
 988     max_false.reset(new Bound(Bound::createDecrement(*max_false)));
 989 }
 990
 991 /// Clears redundant reduced
 992 /// If a min_true is smaller than a min_reduced then the min_reduced
 993 /// is unnecessary and then removed. It also works for min_reduced
 994 /// begin smaller than max_false.
 995 void ABCD::MemoizedResultChart::clearRedundantReduced() {
 996   if (min_true && min_reduced && Bound::lt(*min_true, *min_reduced))
 997     min_reduced.reset();
 998   if (max_false && min_reduced && Bound::lt(*min_reduced, *max_false))
 999     min_reduced.reset();
1000 }
1001
1002 /// Stores the bound found
1003 void ABCD::MemoizedResult::updateBound(Value *b, const Bound &bound,
1004                                        const ProveResult res) {
1005   if (res == False) {
1006     map[b].addFalse(bound);
1007   } else if (res == True) {
1008     map[b].addTrue(bound);
1009   } else {
1010     map[b].addReduced(bound);
1011   }
1012 }
1013
1014 /// Adds an edge from V_from to V_to with weight value
1015 void ABCD::InequalityGraph::addEdge(Value *V_to, Value *V_from,
1016                                     APInt value, bool upper) {
1017   assert(V_from->getType() == V_to->getType());
1018   assert(cast<IntegerType>(V_from->getType())->getBitWidth() ==
1019          value.getBitWidth());
1020
1021   graph[V_from].push_back(Edge(V_to, value, upper));
1022 }
1023
1024 /// Test if there is any edge from V in the upper direction
1025 bool ABCD::InequalityGraph::hasEdge(Value *V, bool upper) const {
1026   SmallVector<Edge, 16> it = graph.lookup(V);
1027
1028   SmallVector<Edge, 16>::iterator begin = it.begin();
1029   SmallVector<Edge, 16>::iterator end = it.end();
1030   for (; begin != end; ++begin) {
1031     if (begin->isUpperBound() == upper) {
1032       return true;
1033     }
1034   }
1035   return false;
1036 }
1037
1038 /// Prints the header of the dot file
1039 void ABCD::InequalityGraph::printHeader(raw_ostream &OS, Function &F) const {
1040   OS << "digraph dotgraph {\n";
1041   OS << "label=\"Inequality Graph for \'";
1042   OS << F.getNameStr() << "\' function\";\n";
1043   OS << "node [shape=record,fontname=\"Times-Roman\",fontsize=14];\n";
1044 }
1045
1046 /// Prints the body of the dot file
1047 void ABCD::InequalityGraph::printBody(raw_ostream &OS) const {
1048   DenseMap<Value *, SmallVector<Edge, 16> >::const_iterator begin =
1049       graph.begin(), end = graph.end();
1050
1051   for (; begin != end ; ++begin) {
1052     SmallVector<Edge, 16>::const_iterator begin_par =
1053         begin->second.begin(), end_par = begin->second.end();
1054     Value *source = begin->first;
1055
1056     printVertex(OS, source);
1057
1058     for (; begin_par != end_par ; ++begin_par) {
1059       const Edge &edge = *begin_par;
1060       printEdge(OS, source, edge);
1061     }
1062   }
1063 }
1064
1065 /// Prints vertex source to the dot file
1066 ///
1067 void ABCD::InequalityGraph::printVertex(raw_ostream &OS, Value *source) const {
1068   OS << "\"";
1069   printName(OS, source);
1070   OS << "\"";
1071   OS << " [label=\"{";
1072   printName(OS, source);
1073   OS << "}\"];\n";
1074 }
1075
1076 /// Prints the edge to the dot file
1077 void ABCD::InequalityGraph::printEdge(raw_ostream &OS, Value *source,
1078                                       const Edge &edge) const {
1079   Value *dest = edge.getVertex();
1080   APInt value = edge.getValue();
1081   bool upper = edge.isUpperBound();
1082
1083   OS << "\"";
1084   printName(OS, source);
1085   OS << "\"";
1086   OS << " -> ";
1087   OS << "\"";
1088   printName(OS, dest);
1089   OS << "\"";
1090   OS << " [label=\"" << value << "\"";
1091   if (upper) {
1092     OS << "color=\"blue\"";
1093   } else {
1094     OS << "color=\"red\"";
1095   }
1096   OS << "];\n";
1097 }
1098
1099 void ABCD::InequalityGraph::printName(raw_ostream &OS, Value *info) const {
1100   if (ConstantInt *CI = dyn_cast<ConstantInt>(info)) {
1101     OS << *CI;
1102   } else {
1103     if (!info->hasName()) {
1104       info->setName("V");
1105     }
1106     OS << info->getNameStr();
1107   }
1108 }
1109
1110 /// createABCDPass - The public interface to this file...
1111 FunctionPass *llvm::createABCDPass() {
1112   return new ABCD();
1113 }