lib/Transforms/Scalar/ABCD.cpp

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