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