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     SmallPtrSet<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 *, SmallPtrSet<Edge *, 16> > graph;
 299
 300     /// Adds a Node to the graph.
 301     DenseMap<Value *, SmallPtrSet<Edge *, 16> >::iterator addNode(Value *V) {
 302       SmallPtrSet<Edge *, 16> p;
 303       return graph.insert(std::make_pair(V, p)).first;
 304     }
 305
 306     /// Prints the header of the dot file
 307     void printHeader(raw_ostream &OS, Function &F) const;
 308
 309     /// Prints the footer of the dot file
 310     void printFooter(raw_ostream &OS) const {
 311       OS << "}\n";
 312     }
 313
 314     /// Prints the body of the dot file
 315     void printBody(raw_ostream &OS) const;
 316
 317     /// Prints vertex source to the dot file
 318     void printVertex(raw_ostream &OS, Value *source) const;
 319
 320     /// Prints the edge to the dot file
 321     void printEdge(raw_ostream &OS, Value *source, Edge *edge) const;
 322
 323     void printName(raw_ostream &OS, Value *info) const;
 324   };
 325
 326   /// Iterates through all BasicBlocks, if the Terminator Instruction
 327   /// uses an Comparator Instruction, all operands of this comparator
 328   /// are sent to be transformed to SSI. Only Instruction operands are
 329   /// transformed.
 330   void createSSI(Function &F);
 331
 332   /// Creates the graphs for this function.
 333   /// It will look for all comparators used in branches, and create them.
 334   /// These comparators will create constraints for any instruction as an
 335   /// operand.
 336   void executeABCD(Function &F);
 337
 338   /// Seeks redundancies in the comparator instruction CI.
 339   /// If the ABCD algorithm can prove that the comparator CI always
 340   /// takes one way, then the Terminator Instruction TI is substituted from
 341   /// a conditional branch to a unconditional one.
 342   /// This code basically receives a comparator, and verifies which kind of
 343   /// instruction it is. Depending on the kind of instruction, we use different
 344   /// strategies to prove its redundancy.
 345   void seekRedundancy(ICmpInst *ICI, TerminatorInst *TI);
 346
 347   /// Substitutes Terminator Instruction TI, that is a conditional branch,
 348   /// with one unconditional branch. Succ_edge determines if the new
 349   /// unconditional edge will be the first or second edge of the former TI
 350   /// instruction.
 351   void removeRedundancy(TerminatorInst *TI, bool Succ_edge);
 352
 353   /// When an conditional branch is removed, the BasicBlock that is no longer
 354   /// reachable will have problems in phi functions. This method fixes these
 355   /// phis removing the former BasicBlock from the list of incoming BasicBlocks
 356   /// of all phis. In case the phi remains with no predecessor it will be
 357   /// marked to be removed later.
 358   void fixPhi(BasicBlock *BB, BasicBlock *Succ);
 359
 360   /// Removes phis that have no predecessor
 361   void removePhis();
 362
 363   /// Creates constraints for Instructions.
 364   /// If the constraint for this instruction has already been created
 365   /// nothing is done.
 366   void createConstraintInstruction(Instruction *I);
 367
 368   /// Creates constraints for Binary Operators.
 369   /// It will create constraints only for addition and subtraction,
 370   /// the other binary operations are not treated by ABCD.
 371   /// For additions in the form a = b + X and a = X + b, where X is a constant,
 372   /// the constraint a <= b + X can be obtained. For this constraint, an edge
 373   /// a->b with weight X is added to the lower bound graph, and an edge
 374   /// b->a with weight -X is added to the upper bound graph.
 375   /// Only subtractions in the format a = b - X is used by ABCD.
 376   /// Edges are created using the same semantic as addition.
 377   void createConstraintBinaryOperator(BinaryOperator *BO);
 378
 379   /// Creates constraints for Comparator Instructions.
 380   /// Only comparators that have any of the following operators
 381   /// are used to create constraints: >=, >, <=, <. And only if
 382   /// at least one operand is an Instruction. In a Comparator Instruction
 383   /// a op b, there will be 4 sigma functions a_t, a_f, b_t and b_f. Where
 384   /// t and f represent sigma for operands in true and false branches. The
 385   /// following constraints can be obtained. a_t <= a, a_f <= a, b_t <= b and
 386   /// b_f <= b. There are two more constraints that depend on the operator.
 387   /// For the operator <= : a_t <= b_t   and b_f <= a_f-1
 388   /// For the operator <  : a_t <= b_t-1 and b_f <= a_f
 389   /// For the operator >= : b_t <= a_t   and a_f <= b_f-1
 390   /// For the operator >  : b_t <= a_t-1 and a_f <= b_f
 391   void createConstraintCmpInst(ICmpInst *ICI, TerminatorInst *TI);
 392
 393   /// Creates constraints for PHI nodes.
 394   /// In a PHI node a = phi(b,c) we can create the constraint
 395   /// a<= max(b,c). With this constraint there will be the edges,
 396   /// b->a and c->a with weight 0 in the lower bound graph, and the edges
 397   /// a->b and a->c with weight 0 in the upper bound graph.
 398   void createConstraintPHINode(PHINode *PN);
 399
 400   /// Given a binary operator, we are only interest in the case
 401   /// that one operand is an Instruction and the other is a ConstantInt. In
 402   /// this case the method returns true, otherwise false. It also obtains the
 403   /// Instruction and ConstantInt from the BinaryOperator and returns it.
 404   bool createBinaryOperatorInfo(BinaryOperator *BO, Instruction **I1,
 405                                 Instruction **I2, ConstantInt **C1,
 406                                 ConstantInt **C2);
 407
 408   /// This method creates a constraint between a Sigma and an Instruction.
 409   /// These constraints are created as soon as we find a comparator that uses a
 410   /// SSI variable.
 411   void createConstraintSigInst(Instruction *I_op, BasicBlock *BB_succ_t,
 412                                BasicBlock *BB_succ_f, PHINode **SIG_op_t,
 413                                PHINode **SIG_op_f);
 414
 415   /// If PN_op1 and PN_o2 are different from NULL, create a constraint
 416   /// PN_op2 -> PN_op1 with value. In case any of them is NULL, replace
 417   /// with the respective V_op#, if V_op# is a ConstantInt.
 418   void createConstraintSigSig(PHINode *SIG_op1, PHINode *SIG_op2,
 419                               ConstantInt *V_op1, ConstantInt *V_op2,
 420                               APInt value);
 421
 422   /// Returns the sigma representing the Instruction I in BasicBlock BB.
 423   /// Returns NULL in case there is no sigma for this Instruction in this
 424   /// Basic Block. This methods assume that sigmas are the first instructions
 425   /// in a block, and that there can be only two sigmas in a block. So it will
 426   /// only look on the first two instructions of BasicBlock BB.
 427   PHINode *findSigma(BasicBlock *BB, Instruction *I);
 428
 429   /// Original ABCD algorithm to prove redundant checks.
 430   /// This implementation works on any kind of inequality branch.
 431   bool demandProve(Value *a, Value *b, int c, bool upper_bound);
 432
 433   /// Prove that distance between b and a is <= bound
 434   ProveResult prove(Value *a, Value *b, const Bound &bound, unsigned level);
 435
 436   /// Updates the distance value for a and b
 437   void updateMemDistance(Value *a, Value *b, const Bound &bound, unsigned level,
 438                          meet_function meet);
 439
 440   InequalityGraph inequality_graph;
 441   MemoizedResult mem_result;
 442   DenseMap<Value*, const Bound*> active;
 443   SmallPtrSet<Value*, 16> created;
 444   SmallVector<PHINode *, 16> phis_to_remove;
 445 };
 446
 447 }  // end anonymous namespace.
 448
 449 char ABCD::ID = 0;
 450 static RegisterPass<ABCD> X("abcd", "ABCD: Eliminating Array Bounds Checks on Demand");
 451
 452
 453 bool ABCD::runOnFunction(Function &F) {
 454   modified = false;
 455   createSSI(F);
 456   executeABCD(F);
 457   DEBUG(inequality_graph.printGraph(dbgs(), F));
 458   removePhis();
 459
 460   inequality_graph.clear();
 461   mem_result.clear();
 462   active.clear();
 463   created.clear();
 464   phis_to_remove.clear();
 465   return modified;
 466 }
 467
 468 /// Iterates through all BasicBlocks, if the Terminator Instruction
 469 /// uses an Comparator Instruction, all operands of this comparator
 470 /// are sent to be transformed to SSI. Only Instruction operands are
 471 /// transformed.
 472 void ABCD::createSSI(Function &F) {
 473   SSI *ssi = &getAnalysis<SSI>();
 474
 475   SmallVector<Instruction *, 16> Insts;
 476
 477   for (Function::iterator begin = F.begin(), end = F.end();
 478        begin != end; ++begin) {
 479     BasicBlock *BB = begin;
 480     TerminatorInst *TI = BB->getTerminator();
 481     if (TI->getNumOperands() == 0)
 482       continue;
 483
 484     if (ICmpInst *ICI = dyn_cast<ICmpInst>(TI->getOperand(0))) {
 485       if (Instruction *I = dyn_cast<Instruction>(ICI->getOperand(0))) {
 486         modified = true;  // XXX: but yet createSSI might do nothing
 487         Insts.push_back(I);
 488       }
 489       if (Instruction *I = dyn_cast<Instruction>(ICI->getOperand(1))) {
 490         modified = true;
 491         Insts.push_back(I);
 492       }
 493     }
 494   }
 495   ssi->createSSI(Insts);
 496 }
 497
 498 /// Creates the graphs for this function.
 499 /// It will look for all comparators used in branches, and create them.
 500 /// These comparators will create constraints for any instruction as an
 501 /// operand.
 502 void ABCD::executeABCD(Function &F) {
 503   for (Function::iterator begin = F.begin(), end = F.end();
 504        begin != end; ++begin) {
 505     BasicBlock *BB = begin;
 506     TerminatorInst *TI = BB->getTerminator();
 507     if (TI->getNumOperands() == 0)
 508       continue;
 509
 510     ICmpInst *ICI = dyn_cast<ICmpInst>(TI->getOperand(0));
 511     if (!ICI || !ICI->getOperand(0)->getType()->isIntegerTy())
 512       continue;
 513
 514     createConstraintCmpInst(ICI, TI);
 515     seekRedundancy(ICI, TI);
 516   }
 517 }
 518
 519 /// Seeks redundancies in the comparator instruction CI.
 520 /// If the ABCD algorithm can prove that the comparator CI always
 521 /// takes one way, then the Terminator Instruction TI is substituted from
 522 /// a conditional branch to a unconditional one.
 523 /// This code basically receives a comparator, and verifies which kind of
 524 /// instruction it is. Depending on the kind of instruction, we use different
 525 /// strategies to prove its redundancy.
 526 void ABCD::seekRedundancy(ICmpInst *ICI, TerminatorInst *TI) {
 527   CmpInst::Predicate Pred = ICI->getPredicate();
 528
 529   Value *source, *dest;
 530   int distance1, distance2;
 531   bool upper;
 532
 533   switch(Pred) {
 534     case CmpInst::ICMP_SGT: // signed greater than
 535       upper = false;
 536       distance1 = 1;
 537       distance2 = 0;
 538       break;
 539
 540     case CmpInst::ICMP_SGE: // signed greater or equal
 541       upper = false;
 542       distance1 = 0;
 543       distance2 = -1;
 544       break;
 545
 546     case CmpInst::ICMP_SLT: // signed less than
 547       upper = true;
 548       distance1 = -1;
 549       distance2 = 0;
 550       break;
 551
 552     case CmpInst::ICMP_SLE: // signed less or equal
 553       upper = true;
 554       distance1 = 0;
 555       distance2 = 1;
 556       break;
 557
 558     default:
 559       return;
 560   }
 561
 562   ++NumBranchTested;
 563   source = ICI->getOperand(0);
 564   dest = ICI->getOperand(1);
 565   if (demandProve(dest, source, distance1, upper)) {
 566     removeRedundancy(TI, true);
 567   } else if (demandProve(dest, source, distance2, !upper)) {
 568     removeRedundancy(TI, false);
 569   }
 570 }
 571
 572 /// Substitutes Terminator Instruction TI, that is a conditional branch,
 573 /// with one unconditional branch. Succ_edge determines if the new
 574 /// unconditional edge will be the first or second edge of the former TI
 575 /// instruction.
 576 void ABCD::removeRedundancy(TerminatorInst *TI, bool Succ_edge) {
 577   BasicBlock *Succ;
 578   if (Succ_edge) {
 579     Succ = TI->getSuccessor(0);
 580     fixPhi(TI->getParent(), TI->getSuccessor(1));
 581   } else {
 582     Succ = TI->getSuccessor(1);
 583     fixPhi(TI->getParent(), TI->getSuccessor(0));
 584   }
 585
 586   BranchInst::Create(Succ, TI);
 587   TI->eraseFromParent();  // XXX: invoke
 588   ++NumBranchRemoved;
 589   modified = true;
 590 }
 591
 592 /// When an conditional branch is removed, the BasicBlock that is no longer
 593 /// reachable will have problems in phi functions. This method fixes these
 594 /// phis removing the former BasicBlock from the list of incoming BasicBlocks
 595 /// of all phis. In case the phi remains with no predecessor it will be
 596 /// marked to be removed later.
 597 void ABCD::fixPhi(BasicBlock *BB, BasicBlock *Succ) {
 598   BasicBlock::iterator begin = Succ->begin();
 599   while (PHINode *PN = dyn_cast<PHINode>(begin++)) {
 600     PN->removeIncomingValue(BB, false);
 601     if (PN->getNumIncomingValues() == 0)
 602       phis_to_remove.push_back(PN);
 603   }
 604 }
 605
 606 /// Removes phis that have no predecessor
 607 void ABCD::removePhis() {
 608   for (unsigned i = 0, e = phis_to_remove.size(); i != e; ++i) {
 609     PHINode *PN = phis_to_remove[i];
 610     PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
 611     PN->eraseFromParent();
 612   }
 613 }
 614
 615 /// Creates constraints for Instructions.
 616 /// If the constraint for this instruction has already been created
 617 /// nothing is done.
 618 void ABCD::createConstraintInstruction(Instruction *I) {
 619   // Test if this instruction has not been created before
 620   if (created.insert(I)) {
 621     if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
 622       createConstraintBinaryOperator(BO);
 623     } else if (PHINode *PN = dyn_cast<PHINode>(I)) {
 624       createConstraintPHINode(PN);
 625     }
 626   }
 627 }
 628
 629 /// Creates constraints for Binary Operators.
 630 /// It will create constraints only for addition and subtraction,
 631 /// the other binary operations are not treated by ABCD.
 632 /// For additions in the form a = b + X and a = X + b, where X is a constant,
 633 /// the constraint a <= b + X can be obtained. For this constraint, an edge
 634 /// a->b with weight X is added to the lower bound graph, and an edge
 635 /// b->a with weight -X is added to the upper bound graph.
 636 /// Only subtractions in the format a = b - X is used by ABCD.
 637 /// Edges are created using the same semantic as addition.
 638 void ABCD::createConstraintBinaryOperator(BinaryOperator *BO) {
 639   Instruction *I1 = NULL, *I2 = NULL;
 640   ConstantInt *CI1 = NULL, *CI2 = NULL;
 641
 642   // Test if an operand is an Instruction and the other is a Constant
 643   if (!createBinaryOperatorInfo(BO, &I1, &I2, &CI1, &CI2))
 644     return;
 645
 646   Instruction *I = 0;
 647   APInt value;
 648
 649   switch (BO->getOpcode()) {
 650     case Instruction::Add:
 651       if (I1) {
 652         I = I1;
 653         value = CI2->getValue();
 654       } else if (I2) {
 655         I = I2;
 656         value = CI1->getValue();
 657       }
 658       break;
 659
 660     case Instruction::Sub:
 661       // Instructions like a = X-b, where X is a constant are not represented
 662       // in the graph.
 663       if (!I1)
 664         return;
 665
 666       I = I1;
 667       value = -CI2->getValue();
 668       break;
 669
 670     default:
 671       return;
 672   }
 673
 674   inequality_graph.addEdge(I, BO, value, true);
 675   inequality_graph.addEdge(BO, I, -value, false);
 676   createConstraintInstruction(I);
 677 }
 678
 679 /// Given a binary operator, we are only interest in the case
 680 /// that one operand is an Instruction and the other is a ConstantInt. In
 681 /// this case the method returns true, otherwise false. It also obtains the
 682 /// Instruction and ConstantInt from the BinaryOperator and returns it.
 683 bool ABCD::createBinaryOperatorInfo(BinaryOperator *BO, Instruction **I1,
 684                                     Instruction **I2, ConstantInt **C1,
 685                                     ConstantInt **C2) {
 686   Value *op1 = BO->getOperand(0);
 687   Value *op2 = BO->getOperand(1);
 688
 689   if ((*I1 = dyn_cast<Instruction>(op1))) {
 690     if ((*C2 = dyn_cast<ConstantInt>(op2)))
 691       return true; // First is Instruction and second ConstantInt
 692
 693     return false; // Both are Instruction
 694   } else {
 695     if ((*C1 = dyn_cast<ConstantInt>(op1)) &&
 696         (*I2 = dyn_cast<Instruction>(op2)))
 697       return true; // First is ConstantInt and second Instruction
 698
 699     return false; // Both are not Instruction
 700   }
 701 }
 702
 703 /// Creates constraints for Comparator Instructions.
 704 /// Only comparators that have any of the following operators
 705 /// are used to create constraints: >=, >, <=, <. And only if
 706 /// at least one operand is an Instruction. In a Comparator Instruction
 707 /// a op b, there will be 4 sigma functions a_t, a_f, b_t and b_f. Where
 708 /// t and f represent sigma for operands in true and false branches. The
 709 /// following constraints can be obtained. a_t <= a, a_f <= a, b_t <= b and
 710 /// b_f <= b. There are two more constraints that depend on the operator.
 711 /// For the operator <= : a_t <= b_t   and b_f <= a_f-1
 712 /// For the operator <  : a_t <= b_t-1 and b_f <= a_f
 713 /// For the operator >= : b_t <= a_t   and a_f <= b_f-1
 714 /// For the operator >  : b_t <= a_t-1 and a_f <= b_f
 715 void ABCD::createConstraintCmpInst(ICmpInst *ICI, TerminatorInst *TI) {
 716   Value *V_op1 = ICI->getOperand(0);
 717   Value *V_op2 = ICI->getOperand(1);
 718
 719   if (!V_op1->getType()->isIntegerTy())
 720     return;
 721
 722   Instruction *I_op1 = dyn_cast<Instruction>(V_op1);
 723   Instruction *I_op2 = dyn_cast<Instruction>(V_op2);
 724
 725   // Test if at least one operand is an Instruction
 726   if (!I_op1 && !I_op2)
 727     return;
 728
 729   BasicBlock *BB_succ_t = TI->getSuccessor(0);
 730   BasicBlock *BB_succ_f = TI->getSuccessor(1);
 731
 732   PHINode *SIG_op1_t = NULL, *SIG_op1_f = NULL,
 733           *SIG_op2_t = NULL, *SIG_op2_f = NULL;
 734
 735   createConstraintSigInst(I_op1, BB_succ_t, BB_succ_f, &SIG_op1_t, &SIG_op1_f);
 736   createConstraintSigInst(I_op2, BB_succ_t, BB_succ_f, &SIG_op2_t, &SIG_op2_f);
 737
 738   int32_t width = cast<IntegerType>(V_op1->getType())->getBitWidth();
 739   APInt MinusOne = APInt::getAllOnesValue(width);
 740   APInt Zero = APInt::getNullValue(width);
 741
 742   CmpInst::Predicate Pred = ICI->getPredicate();
 743   ConstantInt *CI1 = dyn_cast<ConstantInt>(V_op1);
 744   ConstantInt *CI2 = dyn_cast<ConstantInt>(V_op2);
 745   switch (Pred) {
 746   case CmpInst::ICMP_SGT:  // signed greater than
 747     createConstraintSigSig(SIG_op2_t, SIG_op1_t, CI2, CI1, MinusOne);
 748     createConstraintSigSig(SIG_op1_f, SIG_op2_f, CI1, CI2, Zero);
 749     break;
 750
 751   case CmpInst::ICMP_SGE:  // signed greater or equal
 752     createConstraintSigSig(SIG_op2_t, SIG_op1_t, CI2, CI1, Zero);
 753     createConstraintSigSig(SIG_op1_f, SIG_op2_f, CI1, CI2, MinusOne);
 754     break;
 755
 756   case CmpInst::ICMP_SLT:  // signed less than
 757     createConstraintSigSig(SIG_op1_t, SIG_op2_t, CI1, CI2, MinusOne);
 758     createConstraintSigSig(SIG_op2_f, SIG_op1_f, CI2, CI1, Zero);
 759     break;
 760
 761   case CmpInst::ICMP_SLE:  // signed less or equal
 762     createConstraintSigSig(SIG_op1_t, SIG_op2_t, CI1, CI2, Zero);
 763     createConstraintSigSig(SIG_op2_f, SIG_op1_f, CI2, CI1, MinusOne);
 764     break;
 765
 766   default:
 767     break;
 768   }
 769
 770   if (I_op1)
 771     createConstraintInstruction(I_op1);
 772   if (I_op2)
 773     createConstraintInstruction(I_op2);
 774 }
 775
 776 /// Creates constraints for PHI nodes.
 777 /// In a PHI node a = phi(b,c) we can create the constraint
 778 /// a<= max(b,c). With this constraint there will be the edges,
 779 /// b->a and c->a with weight 0 in the lower bound graph, and the edges
 780 /// a->b and a->c with weight 0 in the upper bound graph.
 781 void ABCD::createConstraintPHINode(PHINode *PN) {
 782   // FIXME: We really want to disallow sigma nodes, but I don't know the best
 783   // way to detect the other than this.
 784   if (PN->getNumOperands() == 2) return;
 785
 786   int32_t width = cast<IntegerType>(PN->getType())->getBitWidth();
 787   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 788     Value *V = PN->getIncomingValue(i);
 789     if (Instruction *I = dyn_cast<Instruction>(V)) {
 790       createConstraintInstruction(I);
 791     }
 792     inequality_graph.addEdge(V, PN, APInt(width, 0), true);
 793     inequality_graph.addEdge(V, PN, APInt(width, 0), false);
 794   }
 795 }
 796
 797 /// This method creates a constraint between a Sigma and an Instruction.
 798 /// These constraints are created as soon as we find a comparator that uses a
 799 /// SSI variable.
 800 void ABCD::createConstraintSigInst(Instruction *I_op, BasicBlock *BB_succ_t,
 801                                    BasicBlock *BB_succ_f, PHINode **SIG_op_t,
 802                                    PHINode **SIG_op_f) {
 803   *SIG_op_t = findSigma(BB_succ_t, I_op);
 804   *SIG_op_f = findSigma(BB_succ_f, I_op);
 805
 806   if (*SIG_op_t) {
 807     int32_t width = cast<IntegerType>((*SIG_op_t)->getType())->getBitWidth();
 808     inequality_graph.addEdge(I_op, *SIG_op_t, APInt(width, 0), true);
 809     inequality_graph.addEdge(*SIG_op_t, I_op, APInt(width, 0), false);
 810   }
 811   if (*SIG_op_f) {
 812     int32_t width = cast<IntegerType>((*SIG_op_f)->getType())->getBitWidth();
 813     inequality_graph.addEdge(I_op, *SIG_op_f, APInt(width, 0), true);
 814     inequality_graph.addEdge(*SIG_op_f, I_op, APInt(width, 0), false);
 815   }
 816 }
 817
 818 /// If PN_op1 and PN_o2 are different from NULL, create a constraint
 819 /// PN_op2 -> PN_op1 with value. In case any of them is NULL, replace
 820 /// with the respective V_op#, if V_op# is a ConstantInt.
 821 void ABCD::createConstraintSigSig(PHINode *SIG_op1, PHINode *SIG_op2,
 822                                   ConstantInt *V_op1, ConstantInt *V_op2,
 823                                   APInt value) {
 824   if (SIG_op1 && SIG_op2) {
 825     inequality_graph.addEdge(SIG_op2, SIG_op1, value, true);
 826     inequality_graph.addEdge(SIG_op1, SIG_op2, -value, false);
 827   } else if (SIG_op1 && V_op2) {
 828     inequality_graph.addEdge(V_op2, SIG_op1, value, true);
 829     inequality_graph.addEdge(SIG_op1, V_op2, -value, false);
 830   } else if (SIG_op2 && V_op1) {
 831     inequality_graph.addEdge(SIG_op2, V_op1, value, true);
 832     inequality_graph.addEdge(V_op1, SIG_op2, -value, false);
 833   }
 834 }
 835
 836 /// Returns the sigma representing the Instruction I in BasicBlock BB.
 837 /// Returns NULL in case there is no sigma for this Instruction in this
 838 /// Basic Block. This methods assume that sigmas are the first instructions
 839 /// in a block, and that there can be only two sigmas in a block. So it will
 840 /// only look on the first two instructions of BasicBlock BB.
 841 PHINode *ABCD::findSigma(BasicBlock *BB, Instruction *I) {
 842   // BB has more than one predecessor, BB cannot have sigmas.
 843   if (I == NULL || BB->getSinglePredecessor() == NULL)
 844     return NULL;
 845
 846   BasicBlock::iterator begin = BB->begin();
 847   BasicBlock::iterator end = BB->end();
 848
 849   for (unsigned i = 0; i < 2 && begin != end; ++i, ++begin) {
 850     Instruction *I_succ = begin;
 851     if (PHINode *PN = dyn_cast<PHINode>(I_succ))
 852       if (PN->getIncomingValue(0) == I)
 853         return PN;
 854   }
 855
 856   return NULL;
 857 }
 858
 859 /// Original ABCD algorithm to prove redundant checks.
 860 /// This implementation works on any kind of inequality branch.
 861 bool ABCD::demandProve(Value *a, Value *b, int c, bool upper_bound) {
 862   int32_t width = cast<IntegerType>(a->getType())->getBitWidth();
 863   Bound bound(APInt(width, c), upper_bound);
 864
 865   mem_result.clear();
 866   active.clear();
 867
 868   ProveResult res = prove(a, b, bound, 0);
 869   return res != False;
 870 }
 871
 872 /// Prove that distance between b and a is <= bound
 873 ABCD::ProveResult ABCD::prove(Value *a, Value *b, const Bound &bound,
 874                               unsigned level) {
 875   // if (C[b-a<=e] == True for some e <= bound
 876   // Same or stronger difference was already proven
 877   if (mem_result.hasTrue(b, bound))
 878     return True;
 879
 880   // if (C[b-a<=e] == False for some e >= bound
 881   // Same or weaker difference was already disproved
 882   if (mem_result.hasFalse(b, bound))
 883     return False;
 884
 885   // if (C[b-a<=e] == Reduced for some e <= bound
 886   // b is on a cycle that was reduced for same or stronger difference
 887   if (mem_result.hasReduced(b, bound))
 888     return Reduced;
 889
 890   // traversal reached the source vertex
 891   if (a == b && Bound::geq(bound, APInt(bound.getBitWidth(), 0, true)))
 892     return True;
 893
 894   // if b has no predecessor then fail
 895   if (!inequality_graph.hasEdge(b, bound.isUpperBound()))
 896     return False;
 897
 898   // a cycle was encountered
 899   if (active.count(b)) {
 900     if (Bound::leq(*active.lookup(b), bound))
 901       return Reduced; // a "harmless" cycle
 902
 903     return False; // an amplifying cycle
 904   }
 905
 906   active[b] = &bound;
 907   PHINode *PN = dyn_cast<PHINode>(b);
 908
 909   // Test if a Value is a Phi. If it is a PHINode with more than 1 incoming
 910   // value, then it is a phi, if it has 1 incoming value it is a sigma.
 911   if (PN && PN->getNumIncomingValues() > 1)
 912     updateMemDistance(a, b, bound, level, min);
 913   else
 914     updateMemDistance(a, b, bound, level, max);
 915
 916   active.erase(b);
 917
 918   ABCD::ProveResult res = mem_result.getBoundResult(b, bound);
 919   return res;
 920 }
 921
 922 /// Updates the distance value for a and b
 923 void ABCD::updateMemDistance(Value *a, Value *b, const Bound &bound,
 924                              unsigned level, meet_function meet) {
 925   ABCD::ProveResult res = (meet == max) ? False : True;
 926
 927   SmallPtrSet<Edge *, 16> Edges = inequality_graph.getEdges(b);
 928   SmallPtrSet<Edge *, 16>::iterator begin = Edges.begin(), end = Edges.end();
 929
 930   for (; begin != end ; ++begin) {
 931     if (((res >= Reduced) && (meet == max)) ||
 932        ((res == False) && (meet == min))) {
 933       break;
 934     }
 935     Edge *in = *begin;
 936     if (in->isUpperBound() == bound.isUpperBound()) {
 937       Value *succ = in->getVertex();
 938       res = meet(res, prove(a, succ, Bound(bound, in->getValue()),
 939                             level+1));
 940     }
 941   }
 942
 943   mem_result.updateBound(b, bound, res);
 944 }
 945
 946 /// Return the stored result for this bound
 947 ABCD::ProveResult ABCD::MemoizedResultChart::getResult(const Bound &bound)const{
 948   if (max_false && Bound::leq(bound, *max_false))
 949     return False;
 950   if (min_true && Bound::leq(*min_true, bound))
 951     return True;
 952   if (min_reduced && Bound::leq(*min_reduced, bound))
 953     return Reduced;
 954   return False;
 955 }
 956
 957 /// Stores a false found
 958 void ABCD::MemoizedResultChart::addFalse(const Bound &bound) {
 959   if (!max_false || Bound::leq(*max_false, bound))
 960     max_false.reset(new Bound(bound));
 961
 962   if (Bound::eq(max_false.get(), min_reduced.get()))
 963     min_reduced.reset(new Bound(Bound::createIncrement(*min_reduced)));
 964   if (Bound::eq(max_false.get(), min_true.get()))
 965     min_true.reset(new Bound(Bound::createIncrement(*min_true)));
 966   if (Bound::eq(min_reduced.get(), min_true.get()))
 967     min_reduced.reset();
 968   clearRedundantReduced();
 969 }
 970
 971 /// Stores a true found
 972 void ABCD::MemoizedResultChart::addTrue(const Bound &bound) {
 973   if (!min_true || Bound::leq(bound, *min_true))
 974     min_true.reset(new Bound(bound));
 975
 976   if (Bound::eq(min_true.get(), min_reduced.get()))
 977     min_reduced.reset(new Bound(Bound::createDecrement(*min_reduced)));
 978   if (Bound::eq(min_true.get(), max_false.get()))
 979     max_false.reset(new Bound(Bound::createDecrement(*max_false)));
 980   if (Bound::eq(max_false.get(), min_reduced.get()))
 981     min_reduced.reset();
 982   clearRedundantReduced();
 983 }
 984
 985 /// Stores a Reduced found
 986 void ABCD::MemoizedResultChart::addReduced(const Bound &bound) {
 987   if (!min_reduced || Bound::leq(bound, *min_reduced))
 988     min_reduced.reset(new Bound(bound));
 989
 990   if (Bound::eq(min_reduced.get(), min_true.get()))
 991     min_true.reset(new Bound(Bound::createIncrement(*min_true)));
 992   if (Bound::eq(min_reduced.get(), max_false.get()))
 993     max_false.reset(new Bound(Bound::createDecrement(*max_false)));
 994 }
 995
 996 /// Clears redundant reduced
 997 /// If a min_true is smaller than a min_reduced then the min_reduced
 998 /// is unnecessary and then removed. It also works for min_reduced
 999 /// begin smaller than max_false.
1000 void ABCD::MemoizedResultChart::clearRedundantReduced() {
1001   if (min_true && min_reduced && Bound::lt(*min_true, *min_reduced))
1002     min_reduced.reset();
1003   if (max_false && min_reduced && Bound::lt(*min_reduced, *max_false))
1004     min_reduced.reset();
1005 }
1006
1007 /// Stores the bound found
1008 void ABCD::MemoizedResult::updateBound(Value *b, const Bound &bound,
1009                                        const ProveResult res) {
1010   if (res == False) {
1011     map[b].addFalse(bound);
1012   } else if (res == True) {
1013     map[b].addTrue(bound);
1014   } else {
1015     map[b].addReduced(bound);
1016   }
1017 }
1018
1019 /// Adds an edge from V_from to V_to with weight value
1020 void ABCD::InequalityGraph::addEdge(Value *V_to, Value *V_from,
1021                                     APInt value, bool upper) {
1022   assert(V_from->getType() == V_to->getType());
1023   assert(cast<IntegerType>(V_from->getType())->getBitWidth() ==
1024          value.getBitWidth());
1025
1026   DenseMap<Value *, SmallPtrSet<Edge *, 16> >::iterator from;
1027   from = addNode(V_from);
1028   from->second.insert(new Edge(V_to, value, upper));
1029 }
1030
1031 /// Test if there is any edge from V in the upper direction
1032 bool ABCD::InequalityGraph::hasEdge(Value *V, bool upper) const {
1033   SmallPtrSet<Edge *, 16> it = graph.lookup(V);
1034
1035   SmallPtrSet<Edge *, 16>::iterator begin = it.begin();
1036   SmallPtrSet<Edge *, 16>::iterator end = it.end();
1037   for (; begin != end; ++begin) {
1038     if ((*begin)->isUpperBound() == upper) {
1039       return true;
1040     }
1041   }
1042   return false;
1043 }
1044
1045 /// Prints the header of the dot file
1046 void ABCD::InequalityGraph::printHeader(raw_ostream &OS, Function &F) const {
1047   OS << "digraph dotgraph {\n";
1048   OS << "label=\"Inequality Graph for \'";
1049   OS << F.getNameStr() << "\' function\";\n";
1050   OS << "node [shape=record,fontname=\"Times-Roman\",fontsize=14];\n";
1051 }
1052
1053 /// Prints the body of the dot file
1054 void ABCD::InequalityGraph::printBody(raw_ostream &OS) const {
1055   DenseMap<Value *, SmallPtrSet<Edge *, 16> >::const_iterator begin =
1056       graph.begin(), end = graph.end();
1057
1058   for (; begin != end ; ++begin) {
1059     SmallPtrSet<Edge *, 16>::iterator begin_par =
1060         begin->second.begin(), end_par = begin->second.end();
1061     Value *source = begin->first;
1062
1063     printVertex(OS, source);
1064
1065     for (; begin_par != end_par ; ++begin_par) {
1066       Edge *edge = *begin_par;
1067       printEdge(OS, source, edge);
1068     }
1069   }
1070 }
1071
1072 /// Prints vertex source to the dot file
1073 ///
1074 void ABCD::InequalityGraph::printVertex(raw_ostream &OS, Value *source) const {
1075   OS << "\"";
1076   printName(OS, source);
1077   OS << "\"";
1078   OS << " [label=\"{";
1079   printName(OS, source);
1080   OS << "}\"];\n";
1081 }
1082
1083 /// Prints the edge to the dot file
1084 void ABCD::InequalityGraph::printEdge(raw_ostream &OS, Value *source,
1085                                       Edge *edge) const {
1086   Value *dest = edge->getVertex();
1087   APInt value = edge->getValue();
1088   bool upper = edge->isUpperBound();
1089
1090   OS << "\"";
1091   printName(OS, source);
1092   OS << "\"";
1093   OS << " -> ";
1094   OS << "\"";
1095   printName(OS, dest);
1096   OS << "\"";
1097   OS << " [label=\"" << value << "\"";
1098   if (upper) {
1099     OS << "color=\"blue\"";
1100   } else {
1101     OS << "color=\"red\"";
1102   }
1103   OS << "];\n";
1104 }
1105
1106 void ABCD::InequalityGraph::printName(raw_ostream &OS, Value *info) const {
1107   if (ConstantInt *CI = dyn_cast<ConstantInt>(info)) {
1108     OS << *CI;
1109   } else {
1110     if (!info->hasName()) {
1111       info->setName("V");
1112     }
1113     OS << info->getNameStr();
1114   }
1115 }
1116
1117 /// createABCDPass - The public interface to this file...
1118 FunctionPass *llvm::createABCDPass() {
1119   return new ABCD();
1120 }