LLVM API Documentation

CorrelatedExprs.cpp

Go to the documentation of this file.
00001 //===- CorrelatedExprs.cpp - Pass to detect and eliminated c.e.'s ---------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // Correlated Expression Elimination propagates information from conditional
00011 // branches to blocks dominated by destinations of the branch.  It propagates
00012 // information from the condition check itself into the body of the branch,
00013 // allowing transformations like these for example:
00014 //
00015 //  if (i == 7)
00016 //    ... 4*i;  // constant propagation
00017 //
00018 //  M = i+1; N = j+1;
00019 //  if (i == j)
00020 //    X = M-N;  // = M-M == 0;
00021 //
00022 // This is called Correlated Expression Elimination because we eliminate or
00023 // simplify expressions that are correlated with the direction of a branch.  In
00024 // this way we use static information to give us some information about the
00025 // dynamic value of a variable.
00026 //
00027 //===----------------------------------------------------------------------===//
00028 
00029 #include "llvm/Transforms/Scalar.h"
00030 #include "llvm/Constants.h"
00031 #include "llvm/Pass.h"
00032 #include "llvm/Function.h"
00033 #include "llvm/Instructions.h"
00034 #include "llvm/Type.h"
00035 #include "llvm/Analysis/Dominators.h"
00036 #include "llvm/Assembly/Writer.h"
00037 #include "llvm/Transforms/Utils/Local.h"
00038 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
00039 #include "llvm/Support/ConstantRange.h"
00040 #include "llvm/Support/CFG.h"
00041 #include "llvm/Support/Debug.h"
00042 #include "llvm/ADT/PostOrderIterator.h"
00043 #include "llvm/ADT/Statistic.h"
00044 #include <algorithm>
00045 #include <iostream>
00046 using namespace llvm;
00047 
00048 namespace {
00049   Statistic<> NumSetCCRemoved("cee", "Number of setcc instruction eliminated");
00050   Statistic<> NumOperandsCann("cee", "Number of operands canonicalized");
00051   Statistic<> BranchRevectors("cee", "Number of branches revectored");
00052 
00053   class ValueInfo;
00054   class Relation {
00055     Value *Val;                 // Relation to what value?
00056     Instruction::BinaryOps Rel; // SetCC relation, or Add if no information
00057   public:
00058     Relation(Value *V) : Val(V), Rel(Instruction::Add) {}
00059     bool operator<(const Relation &R) const { return Val < R.Val; }
00060     Value *getValue() const { return Val; }
00061     Instruction::BinaryOps getRelation() const { return Rel; }
00062 
00063     // contradicts - Return true if the relationship specified by the operand
00064     // contradicts already known information.
00065     //
00066     bool contradicts(Instruction::BinaryOps Rel, const ValueInfo &VI) const;
00067 
00068     // incorporate - Incorporate information in the argument into this relation
00069     // entry.  This assumes that the information doesn't contradict itself.  If
00070     // any new information is gained, true is returned, otherwise false is
00071     // returned to indicate that nothing was updated.
00072     //
00073     bool incorporate(Instruction::BinaryOps Rel, ValueInfo &VI);
00074 
00075     // KnownResult - Whether or not this condition determines the result of a
00076     // setcc in the program.  False & True are intentionally 0 & 1 so we can
00077     // convert to bool by casting after checking for unknown.
00078     //
00079     enum KnownResult { KnownFalse = 0, KnownTrue = 1, Unknown = 2 };
00080 
00081     // getImpliedResult - If this relationship between two values implies that
00082     // the specified relationship is true or false, return that.  If we cannot
00083     // determine the result required, return Unknown.
00084     //
00085     KnownResult getImpliedResult(Instruction::BinaryOps Rel) const;
00086 
00087     // print - Output this relation to the specified stream
00088     void print(std::ostream &OS) const;
00089     void dump() const;
00090   };
00091 
00092 
00093   // ValueInfo - One instance of this record exists for every value with
00094   // relationships between other values.  It keeps track of all of the
00095   // relationships to other values in the program (specified with Relation) that
00096   // are known to be valid in a region.
00097   //
00098   class ValueInfo {
00099     // RelationShips - this value is know to have the specified relationships to
00100     // other values.  There can only be one entry per value, and this list is
00101     // kept sorted by the Val field.
00102     std::vector<Relation> Relationships;
00103 
00104     // If information about this value is known or propagated from constant
00105     // expressions, this range contains the possible values this value may hold.
00106     ConstantRange Bounds;
00107 
00108     // If we find that this value is equal to another value that has a lower
00109     // rank, this value is used as it's replacement.
00110     //
00111     Value *Replacement;
00112   public:
00113     ValueInfo(const Type *Ty)
00114       : Bounds(Ty->isIntegral() ? Ty : Type::IntTy), Replacement(0) {}
00115 
00116     // getBounds() - Return the constant bounds of the value...
00117     const ConstantRange &getBounds() const { return Bounds; }
00118     ConstantRange &getBounds() { return Bounds; }
00119 
00120     const std::vector<Relation> &getRelationships() { return Relationships; }
00121 
00122     // getReplacement - Return the value this value is to be replaced with if it
00123     // exists, otherwise return null.
00124     //
00125     Value *getReplacement() const { return Replacement; }
00126 
00127     // setReplacement - Used by the replacement calculation pass to figure out
00128     // what to replace this value with, if anything.
00129     //
00130     void setReplacement(Value *Repl) { Replacement = Repl; }
00131 
00132     // getRelation - return the relationship entry for the specified value.
00133     // This can invalidate references to other Relations, so use it carefully.
00134     //
00135     Relation &getRelation(Value *V) {
00136       // Binary search for V's entry...
00137       std::vector<Relation>::iterator I =
00138         std::lower_bound(Relationships.begin(), Relationships.end(),
00139                          Relation(V));
00140 
00141       // If we found the entry, return it...
00142       if (I != Relationships.end() && I->getValue() == V)
00143         return *I;
00144 
00145       // Insert and return the new relationship...
00146       return *Relationships.insert(I, V);
00147     }
00148 
00149     const Relation *requestRelation(Value *V) const {
00150       // Binary search for V's entry...
00151       std::vector<Relation>::const_iterator I =
00152         std::lower_bound(Relationships.begin(), Relationships.end(),
00153                          Relation(V));
00154       if (I != Relationships.end() && I->getValue() == V)
00155         return &*I;
00156       return 0;
00157     }
00158 
00159     // print - Output information about this value relation...
00160     void print(std::ostream &OS, Value *V) const;
00161     void dump() const;
00162   };
00163 
00164   // RegionInfo - Keeps track of all of the value relationships for a region.  A
00165   // region is the are dominated by a basic block.  RegionInfo's keep track of
00166   // the RegionInfo for their dominator, because anything known in a dominator
00167   // is known to be true in a dominated block as well.
00168   //
00169   class RegionInfo {
00170     BasicBlock *BB;
00171 
00172     // ValueMap - Tracks the ValueInformation known for this region
00173     typedef std::map<Value*, ValueInfo> ValueMapTy;
00174     ValueMapTy ValueMap;
00175   public:
00176     RegionInfo(BasicBlock *bb) : BB(bb) {}
00177 
00178     // getEntryBlock - Return the block that dominates all of the members of
00179     // this region.
00180     BasicBlock *getEntryBlock() const { return BB; }
00181 
00182     // empty - return true if this region has no information known about it.
00183     bool empty() const { return ValueMap.empty(); }
00184 
00185     const RegionInfo &operator=(const RegionInfo &RI) {
00186       ValueMap = RI.ValueMap;
00187       return *this;
00188     }
00189 
00190     // print - Output information about this region...
00191     void print(std::ostream &OS) const;
00192     void dump() const;
00193 
00194     // Allow external access.
00195     typedef ValueMapTy::iterator iterator;
00196     iterator begin() { return ValueMap.begin(); }
00197     iterator end() { return ValueMap.end(); }
00198 
00199     ValueInfo &getValueInfo(Value *V) {
00200       ValueMapTy::iterator I = ValueMap.lower_bound(V);
00201       if (I != ValueMap.end() && I->first == V) return I->second;
00202       return ValueMap.insert(I, std::make_pair(V, V->getType()))->second;
00203     }
00204 
00205     const ValueInfo *requestValueInfo(Value *V) const {
00206       ValueMapTy::const_iterator I = ValueMap.find(V);
00207       if (I != ValueMap.end()) return &I->second;
00208       return 0;
00209     }
00210 
00211     /// removeValueInfo - Remove anything known about V from our records.  This
00212     /// works whether or not we know anything about V.
00213     ///
00214     void removeValueInfo(Value *V) {
00215       ValueMap.erase(V);
00216     }
00217   };
00218 
00219   /// CEE - Correlated Expression Elimination
00220   class CEE : public FunctionPass {
00221     std::map<Value*, unsigned> RankMap;
00222     std::map<BasicBlock*, RegionInfo> RegionInfoMap;
00223     ETForest *EF;
00224     DominatorTree *DT;
00225   public:
00226     virtual bool runOnFunction(Function &F);
00227 
00228     // We don't modify the program, so we preserve all analyses
00229     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00230       AU.addRequired<ETForest>();
00231       AU.addRequired<DominatorTree>();
00232       AU.addRequiredID(BreakCriticalEdgesID);
00233     };
00234 
00235     // print - Implement the standard print form to print out analysis
00236     // information.
00237     virtual void print(std::ostream &O, const Module *M) const;
00238 
00239   private:
00240     RegionInfo &getRegionInfo(BasicBlock *BB) {
00241       std::map<BasicBlock*, RegionInfo>::iterator I
00242         = RegionInfoMap.lower_bound(BB);
00243       if (I != RegionInfoMap.end() && I->first == BB) return I->second;
00244       return RegionInfoMap.insert(I, std::make_pair(BB, BB))->second;
00245     }
00246 
00247     void BuildRankMap(Function &F);
00248     unsigned getRank(Value *V) const {
00249       if (isa<Constant>(V)) return 0;
00250       std::map<Value*, unsigned>::const_iterator I = RankMap.find(V);
00251       if (I != RankMap.end()) return I->second;
00252       return 0; // Must be some other global thing
00253     }
00254 
00255     bool TransformRegion(BasicBlock *BB, std::set<BasicBlock*> &VisitedBlocks);
00256 
00257     bool ForwardCorrelatedEdgeDestination(TerminatorInst *TI, unsigned SuccNo,
00258                                           RegionInfo &RI);
00259 
00260     void ForwardSuccessorTo(TerminatorInst *TI, unsigned Succ, BasicBlock *D,
00261                             RegionInfo &RI);
00262     void ReplaceUsesOfValueInRegion(Value *Orig, Value *New,
00263                                     BasicBlock *RegionDominator);
00264     void CalculateRegionExitBlocks(BasicBlock *BB, BasicBlock *OldSucc,
00265                                    std::vector<BasicBlock*> &RegionExitBlocks);
00266     void InsertRegionExitMerges(PHINode *NewPHI, Instruction *OldVal,
00267                              const std::vector<BasicBlock*> &RegionExitBlocks);
00268 
00269     void PropagateBranchInfo(BranchInst *BI);
00270     void PropagateSwitchInfo(SwitchInst *SI);
00271     void PropagateEquality(Value *Op0, Value *Op1, RegionInfo &RI);
00272     void PropagateRelation(Instruction::BinaryOps Opcode, Value *Op0,
00273                            Value *Op1, RegionInfo &RI);
00274     void UpdateUsersOfValue(Value *V, RegionInfo &RI);
00275     void IncorporateInstruction(Instruction *Inst, RegionInfo &RI);
00276     void ComputeReplacements(RegionInfo &RI);
00277 
00278 
00279     // getSetCCResult - Given a setcc instruction, determine if the result is
00280     // determined by facts we already know about the region under analysis.
00281     // Return KnownTrue, KnownFalse, or Unknown based on what we can determine.
00282     //
00283     Relation::KnownResult getSetCCResult(SetCondInst *SC, const RegionInfo &RI);
00284 
00285 
00286     bool SimplifyBasicBlock(BasicBlock &BB, const RegionInfo &RI);
00287     bool SimplifyInstruction(Instruction *Inst, const RegionInfo &RI);
00288   };
00289   RegisterOpt<CEE> X("cee", "Correlated Expression Elimination");
00290 }
00291 
00292 FunctionPass *llvm::createCorrelatedExpressionEliminationPass() {
00293   return new CEE();
00294 }
00295 
00296 
00297 bool CEE::runOnFunction(Function &F) {
00298   // Build a rank map for the function...
00299   BuildRankMap(F);
00300 
00301   // Traverse the dominator tree, computing information for each node in the
00302   // tree.  Note that our traversal will not even touch unreachable basic
00303   // blocks.
00304   EF = &getAnalysis<ETForest>();
00305   DT = &getAnalysis<DominatorTree>();
00306 
00307   std::set<BasicBlock*> VisitedBlocks;
00308   bool Changed = TransformRegion(&F.getEntryBlock(), VisitedBlocks);
00309 
00310   RegionInfoMap.clear();
00311   RankMap.clear();
00312   return Changed;
00313 }
00314 
00315 // TransformRegion - Transform the region starting with BB according to the
00316 // calculated region information for the block.  Transforming the region
00317 // involves analyzing any information this block provides to successors,
00318 // propagating the information to successors, and finally transforming
00319 // successors.
00320 //
00321 // This method processes the function in depth first order, which guarantees
00322 // that we process the immediate dominator of a block before the block itself.
00323 // Because we are passing information from immediate dominators down to
00324 // dominatees, we obviously have to process the information source before the
00325 // information consumer.
00326 //
00327 bool CEE::TransformRegion(BasicBlock *BB, std::set<BasicBlock*> &VisitedBlocks){
00328   // Prevent infinite recursion...
00329   if (VisitedBlocks.count(BB)) return false;
00330   VisitedBlocks.insert(BB);
00331 
00332   // Get the computed region information for this block...
00333   RegionInfo &RI = getRegionInfo(BB);
00334 
00335   // Compute the replacement information for this block...
00336   ComputeReplacements(RI);
00337 
00338   // If debugging, print computed region information...
00339   DEBUG(RI.print(std::cerr));
00340 
00341   // Simplify the contents of this block...
00342   bool Changed = SimplifyBasicBlock(*BB, RI);
00343 
00344   // Get the terminator of this basic block...
00345   TerminatorInst *TI = BB->getTerminator();
00346 
00347   // Loop over all of the blocks that this block is the immediate dominator for.
00348   // Because all information known in this region is also known in all of the
00349   // blocks that are dominated by this one, we can safely propagate the
00350   // information down now.
00351   //
00352   DominatorTree::Node *BBN = (*DT)[BB];
00353   if (!RI.empty())        // Time opt: only propagate if we can change something
00354     for (unsigned i = 0, e = BBN->getChildren().size(); i != e; ++i) {
00355       BasicBlock *Dominated = BBN->getChildren()[i]->getBlock();
00356       assert(RegionInfoMap.find(Dominated) == RegionInfoMap.end() &&
00357              "RegionInfo should be calculated in dominanace order!");
00358       getRegionInfo(Dominated) = RI;
00359     }
00360 
00361   // Now that all of our successors have information if they deserve it,
00362   // propagate any information our terminator instruction finds to our
00363   // successors.
00364   if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
00365     if (BI->isConditional())
00366       PropagateBranchInfo(BI);
00367   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
00368     PropagateSwitchInfo(SI);
00369   }
00370 
00371   // If this is a branch to a block outside our region that simply performs
00372   // another conditional branch, one whose outcome is known inside of this
00373   // region, then vector this outgoing edge directly to the known destination.
00374   //
00375   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
00376     while (ForwardCorrelatedEdgeDestination(TI, i, RI)) {
00377       ++BranchRevectors;
00378       Changed = true;
00379     }
00380 
00381   // Now that all of our successors have information, recursively process them.
00382   for (unsigned i = 0, e = BBN->getChildren().size(); i != e; ++i)
00383     Changed |= TransformRegion(BBN->getChildren()[i]->getBlock(),VisitedBlocks);
00384 
00385   return Changed;
00386 }
00387 
00388 // isBlockSimpleEnoughForCheck to see if the block is simple enough for us to
00389 // revector the conditional branch in the bottom of the block, do so now.
00390 //
00391 static bool isBlockSimpleEnough(BasicBlock *BB) {
00392   assert(isa<BranchInst>(BB->getTerminator()));
00393   BranchInst *BI = cast<BranchInst>(BB->getTerminator());
00394   assert(BI->isConditional());
00395 
00396   // Check the common case first: empty block, or block with just a setcc.
00397   if (BB->size() == 1 ||
00398       (BB->size() == 2 && &BB->front() == BI->getCondition() &&
00399        BI->getCondition()->hasOneUse()))
00400     return true;
00401 
00402   // Check the more complex case now...
00403   BasicBlock::iterator I = BB->begin();
00404 
00405   // FIXME: This should be reenabled once the regression with SIM is fixed!
00406 #if 0
00407   // PHI Nodes are ok, just skip over them...
00408   while (isa<PHINode>(*I)) ++I;
00409 #endif
00410 
00411   // Accept the setcc instruction...
00412   if (&*I == BI->getCondition())
00413     ++I;
00414 
00415   // Nothing else is acceptable here yet.  We must not revector... unless we are
00416   // at the terminator instruction.
00417   if (&*I == BI)
00418     return true;
00419 
00420   return false;
00421 }
00422 
00423 
00424 bool CEE::ForwardCorrelatedEdgeDestination(TerminatorInst *TI, unsigned SuccNo,
00425                                            RegionInfo &RI) {
00426   // If this successor is a simple block not in the current region, which
00427   // contains only a conditional branch, we decide if the outcome of the branch
00428   // can be determined from information inside of the region.  Instead of going
00429   // to this block, we can instead go to the destination we know is the right
00430   // target.
00431   //
00432 
00433   // Check to see if we dominate the block. If so, this block will get the
00434   // condition turned to a constant anyway.
00435   //
00436   //if (EF->dominates(RI.getEntryBlock(), BB))
00437   // return 0;
00438 
00439   BasicBlock *BB = TI->getParent();
00440 
00441   // Get the destination block of this edge...
00442   BasicBlock *OldSucc = TI->getSuccessor(SuccNo);
00443 
00444   // Make sure that the block ends with a conditional branch and is simple
00445   // enough for use to be able to revector over.
00446   BranchInst *BI = dyn_cast<BranchInst>(OldSucc->getTerminator());
00447   if (BI == 0 || !BI->isConditional() || !isBlockSimpleEnough(OldSucc))
00448     return false;
00449 
00450   // We can only forward the branch over the block if the block ends with a
00451   // setcc we can determine the outcome for.
00452   //
00453   // FIXME: we can make this more generic.  Code below already handles more
00454   // generic case.
00455   SetCondInst *SCI = dyn_cast<SetCondInst>(BI->getCondition());
00456   if (SCI == 0) return false;
00457 
00458   // Make a new RegionInfo structure so that we can simulate the effect of the
00459   // PHI nodes in the block we are skipping over...
00460   //
00461   RegionInfo NewRI(RI);
00462 
00463   // Remove value information for all of the values we are simulating... to make
00464   // sure we don't have any stale information.
00465   for (BasicBlock::iterator I = OldSucc->begin(), E = OldSucc->end(); I!=E; ++I)
00466     if (I->getType() != Type::VoidTy)
00467       NewRI.removeValueInfo(I);
00468 
00469   // Put the newly discovered information into the RegionInfo...
00470   for (BasicBlock::iterator I = OldSucc->begin(), E = OldSucc->end(); I!=E; ++I)
00471     if (PHINode *PN = dyn_cast<PHINode>(I)) {
00472       int OpNum = PN->getBasicBlockIndex(BB);
00473       assert(OpNum != -1 && "PHI doesn't have incoming edge for predecessor!?");
00474       PropagateEquality(PN, PN->getIncomingValue(OpNum), NewRI);
00475     } else if (SetCondInst *SCI = dyn_cast<SetCondInst>(I)) {
00476       Relation::KnownResult Res = getSetCCResult(SCI, NewRI);
00477       if (Res == Relation::Unknown) return false;
00478       PropagateEquality(SCI, ConstantBool::get(Res), NewRI);
00479     } else {
00480       assert(isa<BranchInst>(*I) && "Unexpected instruction type!");
00481     }
00482 
00483   // Compute the facts implied by what we have discovered...
00484   ComputeReplacements(NewRI);
00485 
00486   ValueInfo &PredicateVI = NewRI.getValueInfo(BI->getCondition());
00487   if (PredicateVI.getReplacement() &&
00488       isa<Constant>(PredicateVI.getReplacement()) &&
00489       !isa<GlobalValue>(PredicateVI.getReplacement())) {
00490     ConstantBool *CB = cast<ConstantBool>(PredicateVI.getReplacement());
00491 
00492     // Forward to the successor that corresponds to the branch we will take.
00493     ForwardSuccessorTo(TI, SuccNo, BI->getSuccessor(!CB->getValue()), NewRI);
00494     return true;
00495   }
00496 
00497   return false;
00498 }
00499 
00500 static Value *getReplacementOrValue(Value *V, RegionInfo &RI) {
00501   if (const ValueInfo *VI = RI.requestValueInfo(V))
00502     if (Value *Repl = VI->getReplacement())
00503       return Repl;
00504   return V;
00505 }
00506 
00507 /// ForwardSuccessorTo - We have found that we can forward successor # 'SuccNo'
00508 /// of Terminator 'TI' to the 'Dest' BasicBlock.  This method performs the
00509 /// mechanics of updating SSA information and revectoring the branch.
00510 ///
00511 void CEE::ForwardSuccessorTo(TerminatorInst *TI, unsigned SuccNo,
00512                              BasicBlock *Dest, RegionInfo &RI) {
00513   // If there are any PHI nodes in the Dest BB, we must duplicate the entry
00514   // in the PHI node for the old successor to now include an entry from the
00515   // current basic block.
00516   //
00517   BasicBlock *OldSucc = TI->getSuccessor(SuccNo);
00518   BasicBlock *BB = TI->getParent();
00519 
00520   DEBUG(std::cerr << "Forwarding branch in basic block %" << BB->getName()
00521         << " from block %" << OldSucc->getName() << " to block %"
00522         << Dest->getName() << "\n");
00523 
00524   DEBUG(std::cerr << "Before forwarding: " << *BB->getParent());
00525 
00526   // Because we know that there cannot be critical edges in the flow graph, and
00527   // that OldSucc has multiple outgoing edges, this means that Dest cannot have
00528   // multiple incoming edges.
00529   //
00530 #ifndef NDEBUG
00531   pred_iterator DPI = pred_begin(Dest); ++DPI;
00532   assert(DPI == pred_end(Dest) && "Critical edge found!!");
00533 #endif
00534 
00535   // Loop over any PHI nodes in the destination, eliminating them, because they
00536   // may only have one input.
00537   //
00538   while (PHINode *PN = dyn_cast<PHINode>(&Dest->front())) {
00539     assert(PN->getNumIncomingValues() == 1 && "Crit edge found!");
00540     // Eliminate the PHI node
00541     PN->replaceAllUsesWith(PN->getIncomingValue(0));
00542     Dest->getInstList().erase(PN);
00543   }
00544 
00545   // If there are values defined in the "OldSucc" basic block, we need to insert
00546   // PHI nodes in the regions we are dealing with to emulate them.  This can
00547   // insert dead phi nodes, but it is more trouble to see if they are used than
00548   // to just blindly insert them.
00549   //
00550   if (EF->dominates(OldSucc, Dest)) {
00551     // RegionExitBlocks - Find all of the blocks that are not dominated by Dest,
00552     // but have predecessors that are.  Additionally, prune down the set to only
00553     // include blocks that are dominated by OldSucc as well.
00554     //
00555     std::vector<BasicBlock*> RegionExitBlocks;
00556     CalculateRegionExitBlocks(Dest, OldSucc, RegionExitBlocks);
00557 
00558     for (BasicBlock::iterator I = OldSucc->begin(), E = OldSucc->end();
00559          I != E; ++I)
00560       if (I->getType() != Type::VoidTy) {
00561         // Create and insert the PHI node into the top of Dest.
00562         PHINode *NewPN = new PHINode(I->getType(), I->getName()+".fw_merge",
00563                                      Dest->begin());
00564         // There is definitely an edge from OldSucc... add the edge now
00565         NewPN->addIncoming(I, OldSucc);
00566 
00567         // There is also an edge from BB now, add the edge with the calculated
00568         // value from the RI.
00569         NewPN->addIncoming(getReplacementOrValue(I, RI), BB);
00570 
00571         // Make everything in the Dest region use the new PHI node now...
00572         ReplaceUsesOfValueInRegion(I, NewPN, Dest);
00573 
00574         // Make sure that exits out of the region dominated by NewPN get PHI
00575         // nodes that merge the values as appropriate.
00576         InsertRegionExitMerges(NewPN, I, RegionExitBlocks);
00577       }
00578   }
00579 
00580   // If there were PHI nodes in OldSucc, we need to remove the entry for this
00581   // edge from the PHI node, and we need to replace any references to the PHI
00582   // node with a new value.
00583   //
00584   for (BasicBlock::iterator I = OldSucc->begin(); isa<PHINode>(I); ) {
00585     PHINode *PN = cast<PHINode>(I);
00586 
00587     // Get the value flowing across the old edge and remove the PHI node entry
00588     // for this edge: we are about to remove the edge!  Don't remove the PHI
00589     // node yet though if this is the last edge into it.
00590     Value *EdgeValue = PN->removeIncomingValue(BB, false);
00591 
00592     // Make sure that anything that used to use PN now refers to EdgeValue
00593     ReplaceUsesOfValueInRegion(PN, EdgeValue, Dest);
00594 
00595     // If there is only one value left coming into the PHI node, replace the PHI
00596     // node itself with the one incoming value left.
00597     //
00598     if (PN->getNumIncomingValues() == 1) {
00599       assert(PN->getNumIncomingValues() == 1);
00600       PN->replaceAllUsesWith(PN->getIncomingValue(0));
00601       PN->getParent()->getInstList().erase(PN);
00602       I = OldSucc->begin();
00603     } else if (PN->getNumIncomingValues() == 0) {  // Nuke the PHI
00604       // If we removed the last incoming value to this PHI, nuke the PHI node
00605       // now.
00606       PN->replaceAllUsesWith(Constant::getNullValue(PN->getType()));
00607       PN->getParent()->getInstList().erase(PN);
00608       I = OldSucc->begin();
00609     } else {
00610       ++I;  // Otherwise, move on to the next PHI node
00611     }
00612   }
00613 
00614   // Actually revector the branch now...
00615   TI->setSuccessor(SuccNo, Dest);
00616 
00617   // If we just introduced a critical edge in the flow graph, make sure to break
00618   // it right away...
00619   SplitCriticalEdge(TI, SuccNo, this);
00620 
00621   // Make sure that we don't introduce critical edges from oldsucc now!
00622   for (unsigned i = 0, e = OldSucc->getTerminator()->getNumSuccessors();
00623        i != e; ++i)
00624     if (isCriticalEdge(OldSucc->getTerminator(), i))
00625       SplitCriticalEdge(OldSucc->getTerminator(), i, this);
00626 
00627   // Since we invalidated the CFG, recalculate the dominator set so that it is
00628   // useful for later processing!
00629   // FIXME: This is much worse than it really should be!
00630   //EF->recalculate();
00631 
00632   DEBUG(std::cerr << "After forwarding: " << *BB->getParent());
00633 }
00634 
00635 /// ReplaceUsesOfValueInRegion - This method replaces all uses of Orig with uses
00636 /// of New.  It only affects instructions that are defined in basic blocks that
00637 /// are dominated by Head.
00638 ///
00639 void CEE::ReplaceUsesOfValueInRegion(Value *Orig, Value *New,
00640                                      BasicBlock *RegionDominator) {
00641   assert(Orig != New && "Cannot replace value with itself");
00642   std::vector<Instruction*> InstsToChange;
00643   std::vector<PHINode*>     PHIsToChange;
00644   InstsToChange.reserve(Orig->getNumUses());
00645 
00646   // Loop over instructions adding them to InstsToChange vector, this allows us
00647   // an easy way to avoid invalidating the use_iterator at a bad time.
00648   for (Value::use_iterator I = Orig->use_begin(), E = Orig->use_end();
00649        I != E; ++I)
00650     if (Instruction *User = dyn_cast<Instruction>(*I))
00651       if (EF->dominates(RegionDominator, User->getParent()))
00652         InstsToChange.push_back(User);
00653       else if (PHINode *PN = dyn_cast<PHINode>(User)) {
00654         PHIsToChange.push_back(PN);
00655       }
00656 
00657   // PHIsToChange contains PHI nodes that use Orig that do not live in blocks
00658   // dominated by orig.  If the block the value flows in from is dominated by
00659   // RegionDominator, then we rewrite the PHI
00660   for (unsigned i = 0, e = PHIsToChange.size(); i != e; ++i) {
00661     PHINode *PN = PHIsToChange[i];
00662     for (unsigned j = 0, e = PN->getNumIncomingValues(); j != e; ++j)
00663       if (PN->getIncomingValue(j) == Orig &&
00664           EF->dominates(RegionDominator, PN->getIncomingBlock(j)))
00665         PN->setIncomingValue(j, New);
00666   }
00667 
00668   // Loop over the InstsToChange list, replacing all uses of Orig with uses of
00669   // New.  This list contains all of the instructions in our region that use
00670   // Orig.
00671   for (unsigned i = 0, e = InstsToChange.size(); i != e; ++i)
00672     if (PHINode *PN = dyn_cast<PHINode>(InstsToChange[i])) {
00673       // PHINodes must be handled carefully.  If the PHI node itself is in the
00674       // region, we have to make sure to only do the replacement for incoming
00675       // values that correspond to basic blocks in the region.
00676       for (unsigned j = 0, e = PN->getNumIncomingValues(); j != e; ++j)
00677         if (PN->getIncomingValue(j) == Orig &&
00678             EF->dominates(RegionDominator, PN->getIncomingBlock(j)))
00679           PN->setIncomingValue(j, New);
00680 
00681     } else {
00682       InstsToChange[i]->replaceUsesOfWith(Orig, New);
00683     }
00684 }
00685 
00686 static void CalcRegionExitBlocks(BasicBlock *Header, BasicBlock *BB,
00687                                  std::set<BasicBlock*> &Visited,
00688                                  ETForest &EF,
00689                                  std::vector<BasicBlock*> &RegionExitBlocks) {
00690   if (Visited.count(BB)) return;
00691   Visited.insert(BB);
00692 
00693   if (EF.dominates(Header, BB)) {  // Block in the region, recursively traverse
00694     for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
00695       CalcRegionExitBlocks(Header, *I, Visited, EF, RegionExitBlocks);
00696   } else {
00697     // Header does not dominate this block, but we have a predecessor that does
00698     // dominate us.  Add ourself to the list.
00699     RegionExitBlocks.push_back(BB);
00700   }
00701 }
00702 
00703 /// CalculateRegionExitBlocks - Find all of the blocks that are not dominated by
00704 /// BB, but have predecessors that are.  Additionally, prune down the set to
00705 /// only include blocks that are dominated by OldSucc as well.
00706 ///
00707 void CEE::CalculateRegionExitBlocks(BasicBlock *BB, BasicBlock *OldSucc,
00708                                     std::vector<BasicBlock*> &RegionExitBlocks){
00709   std::set<BasicBlock*> Visited;  // Don't infinite loop
00710 
00711   // Recursively calculate blocks we are interested in...
00712   CalcRegionExitBlocks(BB, BB, Visited, *EF, RegionExitBlocks);
00713 
00714   // Filter out blocks that are not dominated by OldSucc...
00715   for (unsigned i = 0; i != RegionExitBlocks.size(); ) {
00716     if (EF->dominates(OldSucc, RegionExitBlocks[i]))
00717       ++i;  // Block is ok, keep it.
00718     else {
00719       // Move to end of list...
00720       std::swap(RegionExitBlocks[i], RegionExitBlocks.back());
00721       RegionExitBlocks.pop_back();        // Nuke the end
00722     }
00723   }
00724 }
00725 
00726 void CEE::InsertRegionExitMerges(PHINode *BBVal, Instruction *OldVal,
00727                              const std::vector<BasicBlock*> &RegionExitBlocks) {
00728   assert(BBVal->getType() == OldVal->getType() && "Should be derived values!");
00729   BasicBlock *BB = BBVal->getParent();
00730   BasicBlock *OldSucc = OldVal->getParent();
00731 
00732   // Loop over all of the blocks we have to place PHIs in, doing it.
00733   for (unsigned i = 0, e = RegionExitBlocks.size(); i != e; ++i) {
00734     BasicBlock *FBlock = RegionExitBlocks[i];  // Block on the frontier
00735 
00736     // Create the new PHI node
00737     PHINode *NewPN = new PHINode(BBVal->getType(),
00738                                  OldVal->getName()+".fw_frontier",
00739                                  FBlock->begin());
00740 
00741     // Add an incoming value for every predecessor of the block...
00742     for (pred_iterator PI = pred_begin(FBlock), PE = pred_end(FBlock);
00743          PI != PE; ++PI) {
00744       // If the incoming edge is from the region dominated by BB, use BBVal,
00745       // otherwise use OldVal.
00746       NewPN->addIncoming(EF->dominates(BB, *PI) ? BBVal : OldVal, *PI);
00747     }
00748 
00749     // Now make everyone dominated by this block use this new value!
00750     ReplaceUsesOfValueInRegion(OldVal, NewPN, FBlock);
00751   }
00752 }
00753 
00754 
00755 
00756 // BuildRankMap - This method builds the rank map data structure which gives
00757 // each instruction/value in the function a value based on how early it appears
00758 // in the function.  We give constants and globals rank 0, arguments are
00759 // numbered starting at one, and instructions are numbered in reverse post-order
00760 // from where the arguments leave off.  This gives instructions in loops higher
00761 // values than instructions not in loops.
00762 //
00763 void CEE::BuildRankMap(Function &F) {
00764   unsigned Rank = 1;  // Skip rank zero.
00765 
00766   // Number the arguments...
00767   for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I)
00768     RankMap[I] = Rank++;
00769 
00770   // Number the instructions in reverse post order...
00771   ReversePostOrderTraversal<Function*> RPOT(&F);
00772   for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(),
00773          E = RPOT.end(); I != E; ++I)
00774     for (BasicBlock::iterator BBI = (*I)->begin(), E = (*I)->end();
00775          BBI != E; ++BBI)
00776       if (BBI->getType() != Type::VoidTy)
00777         RankMap[BBI] = Rank++;
00778 }
00779 
00780 
00781 // PropagateBranchInfo - When this method is invoked, we need to propagate
00782 // information derived from the branch condition into the true and false
00783 // branches of BI.  Since we know that there aren't any critical edges in the
00784 // flow graph, this can proceed unconditionally.
00785 //
00786 void CEE::PropagateBranchInfo(BranchInst *BI) {
00787   assert(BI->isConditional() && "Must be a conditional branch!");
00788 
00789   // Propagate information into the true block...
00790   //
00791   PropagateEquality(BI->getCondition(), ConstantBool::True,
00792                     getRegionInfo(BI->getSuccessor(0)));
00793 
00794   // Propagate information into the false block...
00795   //
00796   PropagateEquality(BI->getCondition(), ConstantBool::False,
00797                     getRegionInfo(BI->getSuccessor(1)));
00798 }
00799 
00800 
00801 // PropagateSwitchInfo - We need to propagate the value tested by the
00802 // switch statement through each case block.
00803 //
00804 void CEE::PropagateSwitchInfo(SwitchInst *SI) {
00805   // Propagate information down each of our non-default case labels.  We
00806   // don't yet propagate information down the default label, because a
00807   // potentially large number of inequality constraints provide less
00808   // benefit per unit work than a single equality constraint.
00809   //
00810   Value *cond = SI->getCondition();
00811   for (unsigned i = 1; i < SI->getNumSuccessors(); ++i)
00812     PropagateEquality(cond, SI->getSuccessorValue(i),
00813                       getRegionInfo(SI->getSuccessor(i)));
00814 }
00815 
00816 
00817 // PropagateEquality - If we discover that two values are equal to each other in
00818 // a specified region, propagate this knowledge recursively.
00819 //
00820 void CEE::PropagateEquality(Value *Op0, Value *Op1, RegionInfo &RI) {
00821   if (Op0 == Op1) return;  // Gee whiz. Are these really equal each other?
00822 
00823   if (isa<Constant>(Op0))  // Make sure the constant is always Op1
00824     std::swap(Op0, Op1);
00825 
00826   // Make sure we don't already know these are equal, to avoid infinite loops...
00827   ValueInfo &VI = RI.getValueInfo(Op0);
00828 
00829   // Get information about the known relationship between Op0 & Op1
00830   Relation &KnownRelation = VI.getRelation(Op1);
00831 
00832   // If we already know they're equal, don't reprocess...
00833   if (KnownRelation.getRelation() == Instruction::SetEQ)
00834     return;
00835 
00836   // If this is boolean, check to see if one of the operands is a constant.  If
00837   // it's a constant, then see if the other one is one of a setcc instruction,
00838   // an AND, OR, or XOR instruction.
00839   //
00840   if (ConstantBool *CB = dyn_cast<ConstantBool>(Op1)) {
00841 
00842     if (Instruction *Inst = dyn_cast<Instruction>(Op0)) {
00843       // If we know that this instruction is an AND instruction, and the result
00844       // is true, this means that both operands to the OR are known to be true
00845       // as well.
00846       //
00847       if (CB->getValue() && Inst->getOpcode() == Instruction::And) {
00848         PropagateEquality(Inst->getOperand(0), CB, RI);
00849         PropagateEquality(Inst->getOperand(1), CB, RI);
00850       }
00851 
00852       // If we know that this instruction is an OR instruction, and the result
00853       // is false, this means that both operands to the OR are know to be false
00854       // as well.
00855       //
00856       if (!CB->getValue() && Inst->getOpcode() == Instruction::Or) {
00857         PropagateEquality(Inst->getOperand(0), CB, RI);
00858         PropagateEquality(Inst->getOperand(1), CB, RI);
00859       }
00860 
00861       // If we know that this instruction is a NOT instruction, we know that the
00862       // operand is known to be the inverse of whatever the current value is.
00863       //
00864       if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(Inst))
00865         if (BinaryOperator::isNot(BOp))
00866           PropagateEquality(BinaryOperator::getNotArgument(BOp),
00867                             ConstantBool::get(!CB->getValue()), RI);
00868 
00869       // If we know the value of a SetCC instruction, propagate the information
00870       // about the relation into this region as well.
00871       //
00872       if (SetCondInst *SCI = dyn_cast<SetCondInst>(Inst)) {
00873         if (CB->getValue()) {  // If we know the condition is true...
00874           // Propagate info about the LHS to the RHS & RHS to LHS
00875           PropagateRelation(SCI->getOpcode(), SCI->getOperand(0),
00876                             SCI->getOperand(1), RI);
00877           PropagateRelation(SCI->getSwappedCondition(),
00878                             SCI->getOperand(1), SCI->getOperand(0), RI);
00879 
00880         } else {               // If we know the condition is false...
00881           // We know the opposite of the condition is true...
00882           Instruction::BinaryOps C = SCI->getInverseCondition();
00883 
00884           PropagateRelation(C, SCI->getOperand(0), SCI->getOperand(1), RI);
00885           PropagateRelation(SetCondInst::getSwappedCondition(C),
00886                             SCI->getOperand(1), SCI->getOperand(0), RI);
00887         }
00888       }
00889     }
00890   }
00891 
00892   // Propagate information about Op0 to Op1 & visa versa
00893   PropagateRelation(Instruction::SetEQ, Op0, Op1, RI);
00894   PropagateRelation(Instruction::SetEQ, Op1, Op0, RI);
00895 }
00896 
00897 
00898 // PropagateRelation - We know that the specified relation is true in all of the
00899 // blocks in the specified region.  Propagate the information about Op0 and
00900 // anything derived from it into this region.
00901 //
00902 void CEE::PropagateRelation(Instruction::BinaryOps Opcode, Value *Op0,
00903                             Value *Op1, RegionInfo &RI) {
00904   assert(Op0->getType() == Op1->getType() && "Equal types expected!");
00905 
00906   // Constants are already pretty well understood.  We will apply information
00907   // about the constant to Op1 in another call to PropagateRelation.
00908   //
00909   if (isa<Constant>(Op0)) return;
00910 
00911   // Get the region information for this block to update...
00912   ValueInfo &VI = RI.getValueInfo(Op0);
00913 
00914   // Get information about the known relationship between Op0 & Op1
00915   Relation &Op1R = VI.getRelation(Op1);
00916 
00917   // Quick bailout for common case if we are reprocessing an instruction...
00918   if (Op1R.getRelation() == Opcode)
00919     return;
00920 
00921   // If we already have information that contradicts the current information we
00922   // are propagating, ignore this info.  Something bad must have happened!
00923   //
00924   if (Op1R.contradicts(Opcode, VI)) {
00925     Op1R.contradicts(Opcode, VI);
00926     std::cerr << "Contradiction found for opcode: "
00927               << Instruction::getOpcodeName(Opcode) << "\n";
00928     Op1R.print(std::cerr);
00929     return;
00930   }
00931 
00932   // If the information propagated is new, then we want process the uses of this
00933   // instruction to propagate the information down to them.
00934   //
00935   if (Op1R.incorporate(Opcode, VI))
00936     UpdateUsersOfValue(Op0, RI);
00937 }
00938 
00939 
00940 // UpdateUsersOfValue - The information about V in this region has been updated.
00941 // Propagate this to all consumers of the value.
00942 //
00943 void CEE::UpdateUsersOfValue(Value *V, RegionInfo &RI) {
00944   for (Value::use_iterator I = V->use_begin(), E = V->use_end();
00945        I != E; ++I)
00946     if (Instruction *Inst = dyn_cast<Instruction>(*I)) {
00947       // If this is an instruction using a value that we know something about,
00948       // try to propagate information to the value produced by the
00949       // instruction.  We can only do this if it is an instruction we can
00950       // propagate information for (a setcc for example), and we only WANT to
00951       // do this if the instruction dominates this region.
00952       //
00953       // If the instruction doesn't dominate this region, then it cannot be
00954       // used in this region and we don't care about it.  If the instruction
00955       // is IN this region, then we will simplify the instruction before we
00956       // get to uses of it anyway, so there is no reason to bother with it
00957       // here.  This check is also effectively checking to make sure that Inst
00958       // is in the same function as our region (in case V is a global f.e.).
00959       //
00960       if (EF->properlyDominates(Inst->getParent(), RI.getEntryBlock()))
00961         IncorporateInstruction(Inst, RI);
00962     }
00963 }
00964 
00965 // IncorporateInstruction - We just updated the information about one of the
00966 // operands to the specified instruction.  Update the information about the
00967 // value produced by this instruction
00968 //
00969 void CEE::IncorporateInstruction(Instruction *Inst, RegionInfo &RI) {
00970   if (SetCondInst *SCI = dyn_cast<SetCondInst>(Inst)) {
00971     // See if we can figure out a result for this instruction...
00972     Relation::KnownResult Result = getSetCCResult(SCI, RI);
00973     if (Result != Relation::Unknown) {
00974       PropagateEquality(SCI, Result ? ConstantBool::True : ConstantBool::False,
00975                         RI);
00976     }
00977   }
00978 }
00979 
00980 
00981 // ComputeReplacements - Some values are known to be equal to other values in a
00982 // region.  For example if there is a comparison of equality between a variable
00983 // X and a constant C, we can replace all uses of X with C in the region we are
00984 // interested in.  We generalize this replacement to replace variables with
00985 // other variables if they are equal and there is a variable with lower rank
00986 // than the current one.  This offers a canonicalizing property that exposes
00987 // more redundancies for later transformations to take advantage of.
00988 //
00989 void CEE::ComputeReplacements(RegionInfo &RI) {
00990   // Loop over all of the values in the region info map...
00991   for (RegionInfo::iterator I = RI.begin(), E = RI.end(); I != E; ++I) {
00992     ValueInfo &VI = I->second;
00993 
00994     // If we know that this value is a particular constant, set Replacement to
00995     // the constant...
00996     Value *Replacement = VI.getBounds().getSingleElement();
00997 
00998     // If this value is not known to be some constant, figure out the lowest
00999     // rank value that it is known to be equal to (if anything).
01000     //
01001     if (Replacement == 0) {
01002       // Find out if there are any equality relationships with values of lower
01003       // rank than VI itself...
01004       unsigned MinRank = getRank(I->first);
01005 
01006       // Loop over the relationships known about Op0.
01007       const std::vector<Relation> &Relationships = VI.getRelationships();
01008       for (unsigned i = 0, e = Relationships.size(); i != e; ++i)
01009         if (Relationships[i].getRelation() == Instruction::SetEQ) {
01010           unsigned R = getRank(Relationships[i].getValue());
01011           if (R < MinRank) {
01012             MinRank = R;
01013             Replacement = Relationships[i].getValue();
01014           }
01015         }
01016     }
01017 
01018     // If we found something to replace this value with, keep track of it.
01019     if (Replacement)
01020       VI.setReplacement(Replacement);
01021   }
01022 }
01023 
01024 // SimplifyBasicBlock - Given information about values in region RI, simplify
01025 // the instructions in the specified basic block.
01026 //
01027 bool CEE::SimplifyBasicBlock(BasicBlock &BB, const RegionInfo &RI) {
01028   bool Changed = false;
01029   for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ) {
01030     Instruction *Inst = I++;
01031 
01032     // Convert instruction arguments to canonical forms...
01033     Changed |= SimplifyInstruction(Inst, RI);
01034 
01035     if (SetCondInst *SCI = dyn_cast<SetCondInst>(Inst)) {
01036       // Try to simplify a setcc instruction based on inherited information
01037       Relation::KnownResult Result = getSetCCResult(SCI, RI);
01038       if (Result != Relation::Unknown) {
01039         DEBUG(std::cerr << "Replacing setcc with " << Result
01040                         << " constant: " << *SCI);
01041 
01042         SCI->replaceAllUsesWith(ConstantBool::get((bool)Result));
01043         // The instruction is now dead, remove it from the program.
01044         SCI->getParent()->getInstList().erase(SCI);
01045         ++NumSetCCRemoved;
01046         Changed = true;
01047       }
01048     }
01049   }
01050 
01051   return Changed;
01052 }
01053 
01054 // SimplifyInstruction - Inspect the operands of the instruction, converting
01055 // them to their canonical form if possible.  This takes care of, for example,
01056 // replacing a value 'X' with a constant 'C' if the instruction in question is
01057 // dominated by a true seteq 'X', 'C'.
01058 //
01059 bool CEE::SimplifyInstruction(Instruction *I, const RegionInfo &RI) {
01060   bool Changed = false;
01061 
01062   for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
01063     if (const ValueInfo *VI = RI.requestValueInfo(I->getOperand(i)))
01064       if (Value *Repl = VI->getReplacement()) {
01065         // If we know if a replacement with lower rank than Op0, make the
01066         // replacement now.
01067         DEBUG(std::cerr << "In Inst: " << *I << "  Replacing operand #" << i
01068                         << " with " << *Repl << "\n");
01069         I->setOperand(i, Repl);
01070         Changed = true;
01071         ++NumOperandsCann;
01072       }
01073 
01074   return Changed;
01075 }
01076 
01077 
01078 // getSetCCResult - Try to simplify a setcc instruction based on information
01079 // inherited from a dominating setcc instruction.  V is one of the operands to
01080 // the setcc instruction, and VI is the set of information known about it.  We
01081 // take two cases into consideration here.  If the comparison is against a
01082 // constant value, we can use the constant range to see if the comparison is
01083 // possible to succeed.  If it is not a comparison against a constant, we check
01084 // to see if there is a known relationship between the two values.  If so, we
01085 // may be able to eliminate the check.
01086 //
01087 Relation::KnownResult CEE::getSetCCResult(SetCondInst *SCI,
01088                                           const RegionInfo &RI) {
01089   Value *Op0 = SCI->getOperand(0), *Op1 = SCI->getOperand(1);
01090   Instruction::BinaryOps Opcode = SCI->getOpcode();
01091 
01092   if (isa<Constant>(Op0)) {
01093     if (isa<Constant>(Op1)) {
01094       if (Constant *Result = ConstantFoldInstruction(SCI)) {
01095         // Wow, this is easy, directly eliminate the SetCondInst.
01096         DEBUG(std::cerr << "Replacing setcc with constant fold: " << *SCI);
01097         return cast<ConstantBool>(Result)->getValue()
01098           ? Relation::KnownTrue : Relation::KnownFalse;
01099       }
01100     } else {
01101       // We want to swap this instruction so that operand #0 is the constant.
01102       std::swap(Op0, Op1);
01103       Opcode = SCI->getSwappedCondition();
01104     }
01105   }
01106 
01107   // Try to figure out what the result of this comparison will be...
01108   Relation::KnownResult Result = Relation::Unknown;
01109 
01110   // We have to know something about the relationship to prove anything...
01111   if (const ValueInfo *Op0VI = RI.requestValueInfo(Op0)) {
01112 
01113     // At this point, we know that if we have a constant argument that it is in
01114     // Op1.  Check to see if we know anything about comparing value with a
01115     // constant, and if we can use this info to fold the setcc.
01116     //
01117     if (ConstantIntegral *C = dyn_cast<ConstantIntegral>(Op1)) {
01118       // Check to see if we already know the result of this comparison...
01119       ConstantRange R = ConstantRange(Opcode, C);
01120       ConstantRange Int = R.intersectWith(Op0VI->getBounds());
01121 
01122       // If the intersection of the two ranges is empty, then the condition
01123       // could never be true!
01124       //
01125       if (Int.isEmptySet()) {
01126         Result = Relation::KnownFalse;
01127 
01128       // Otherwise, if VI.getBounds() (the possible values) is a subset of R
01129       // (the allowed values) then we know that the condition must always be
01130       // true!
01131       //
01132       } else if (Int == Op0VI->getBounds()) {
01133         Result = Relation::KnownTrue;
01134       }
01135     } else {
01136       // If we are here, we know that the second argument is not a constant
01137       // integral.  See if we know anything about Op0 & Op1 that allows us to
01138       // fold this anyway.
01139       //
01140       // Do we have value information about Op0 and a relation to Op1?
01141       if (const Relation *Op2R = Op0VI->requestRelation(Op1))
01142         Result = Op2R->getImpliedResult(Opcode);
01143     }
01144   }
01145   return Result;
01146 }
01147 
01148 //===----------------------------------------------------------------------===//
01149 //  Relation Implementation
01150 //===----------------------------------------------------------------------===//
01151 
01152 // CheckCondition - Return true if the specified condition is false.  Bound may
01153 // be null.
01154 static bool CheckCondition(Constant *Bound, Constant *C,
01155                            Instruction::BinaryOps BO) {
01156   assert(C != 0 && "C is not specified!");
01157   if (Bound == 0) return false;
01158 
01159   Constant *Val = ConstantExpr::get(BO, Bound, C);
01160   if (ConstantBool *CB = dyn_cast<ConstantBool>(Val))
01161     return !CB->getValue();  // Return true if the condition is false...
01162   return false;
01163 }
01164 
01165 // contradicts - Return true if the relationship specified by the operand
01166 // contradicts already known information.
01167 //
01168 bool Relation::contradicts(Instruction::BinaryOps Op,
01169                            const ValueInfo &VI) const {
01170   assert (Op != Instruction::Add && "Invalid relation argument!");
01171 
01172   // If this is a relationship with a constant, make sure that this relationship
01173   // does not contradict properties known about the bounds of the constant.
01174   //
01175   if (ConstantIntegral *C = dyn_cast<ConstantIntegral>(Val))
01176     if (ConstantRange(Op, C).intersectWith(VI.getBounds()).isEmptySet())
01177       return true;
01178 
01179   switch (Rel) {
01180   default: assert(0 && "Unknown Relationship code!");
01181   case Instruction::Add: return false;  // Nothing known, nothing contradicts
01182   case Instruction::SetEQ:
01183     return Op == Instruction::SetLT || Op == Instruction::SetGT ||
01184            Op == Instruction::SetNE;
01185   case Instruction::SetNE: return Op == Instruction::SetEQ;
01186   case Instruction::SetLE: return Op == Instruction::SetGT;
01187   case Instruction::SetGE: return Op == Instruction::SetLT;
01188   case Instruction::SetLT:
01189     return Op == Instruction::SetEQ || Op == Instruction::SetGT ||
01190            Op == Instruction::SetGE;
01191   case Instruction::SetGT:
01192     return Op == Instruction::SetEQ || Op == Instruction::SetLT ||
01193            Op == Instruction::SetLE;
01194   }
01195 }
01196 
01197 // incorporate - Incorporate information in the argument into this relation
01198 // entry.  This assumes that the information doesn't contradict itself.  If any
01199 // new information is gained, true is returned, otherwise false is returned to
01200 // indicate that nothing was updated.
01201 //
01202 bool Relation::incorporate(Instruction::BinaryOps Op, ValueInfo &VI) {
01203   assert(!contradicts(Op, VI) &&
01204          "Cannot incorporate contradictory information!");
01205 
01206   // If this is a relationship with a constant, make sure that we update the
01207   // range that is possible for the value to have...
01208   //
01209   if (ConstantIntegral *C = dyn_cast<ConstantIntegral>(Val))
01210     VI.getBounds() = ConstantRange(Op, C).intersectWith(VI.getBounds());
01211 
01212   switch (Rel) {
01213   default: assert(0 && "Unknown prior value!");
01214   case Instruction::Add:   Rel = Op; return true;
01215   case Instruction::SetEQ: return false;  // Nothing is more precise
01216   case Instruction::SetNE: return false;  // Nothing is more precise
01217   case Instruction::SetLT: return false;  // Nothing is more precise
01218   case Instruction::SetGT: return false;  // Nothing is more precise
01219   case Instruction::SetLE:
01220     if (Op == Instruction::SetEQ || Op == Instruction::SetLT) {
01221       Rel = Op;
01222       return true;
01223     } else if (Op == Instruction::SetNE) {
01224       Rel = Instruction::SetLT;
01225       return true;
01226     }
01227     return false;
01228   case Instruction::SetGE: return Op == Instruction::SetLT;
01229     if (Op == Instruction::SetEQ || Op == Instruction::SetGT) {
01230       Rel = Op;
01231       return true;
01232     } else if (Op == Instruction::SetNE) {
01233       Rel = Instruction::SetGT;
01234       return true;
01235     }
01236     return false;
01237   }
01238 }
01239 
01240 // getImpliedResult - If this relationship between two values implies that
01241 // the specified relationship is true or false, return that.  If we cannot
01242 // determine the result required, return Unknown.
01243 //
01244 Relation::KnownResult
01245 Relation::getImpliedResult(Instruction::BinaryOps Op) const {
01246   if (Rel == Op) return KnownTrue;
01247   if (Rel == SetCondInst::getInverseCondition(Op)) return KnownFalse;
01248 
01249   switch (Rel) {
01250   default: assert(0 && "Unknown prior value!");
01251   case Instruction::SetEQ:
01252     if (Op == Instruction::SetLE || Op == Instruction::SetGE) return KnownTrue;
01253     if (Op == Instruction::SetLT || Op == Instruction::SetGT) return KnownFalse;
01254     break;
01255   case Instruction::SetLT:
01256     if (Op == Instruction::SetNE || Op == Instruction::SetLE) return KnownTrue;
01257     if (Op == Instruction::SetEQ) return KnownFalse;
01258     break;
01259   case Instruction::SetGT:
01260     if (Op == Instruction::SetNE || Op == Instruction::SetGE) return KnownTrue;
01261     if (Op == Instruction::SetEQ) return KnownFalse;
01262     break;
01263   case Instruction::SetNE:
01264   case Instruction::SetLE:
01265   case Instruction::SetGE:
01266   case Instruction::Add:
01267     break;
01268   }
01269   return Unknown;
01270 }
01271 
01272 
01273 //===----------------------------------------------------------------------===//
01274 // Printing Support...
01275 //===----------------------------------------------------------------------===//
01276 
01277 // print - Implement the standard print form to print out analysis information.
01278 void CEE::print(std::ostream &O, const Module *M) const {
01279   O << "\nPrinting Correlated Expression Info:\n";
01280   for (std::map<BasicBlock*, RegionInfo>::const_iterator I =
01281          RegionInfoMap.begin(), E = RegionInfoMap.end(); I != E; ++I)
01282     I->second.print(O);
01283 }
01284 
01285 // print - Output information about this region...
01286 void RegionInfo::print(std::ostream &OS) const {
01287   if (ValueMap.empty()) return;
01288 
01289   OS << " RegionInfo for basic block: " << BB->getName() << "\n";
01290   for (std::map<Value*, ValueInfo>::const_iterator
01291          I = ValueMap.begin(), E = ValueMap.end(); I != E; ++I)
01292     I->second.print(OS, I->first);
01293   OS << "\n";
01294 }
01295 
01296 // print - Output information about this value relation...
01297 void ValueInfo::print(std::ostream &OS, Value *V) const {
01298   if (Relationships.empty()) return;
01299 
01300   if (V) {
01301     OS << "  ValueInfo for: ";
01302     WriteAsOperand(OS, V);
01303   }
01304   OS << "\n    Bounds = " << Bounds << "\n";
01305   if (Replacement) {
01306     OS << "    Replacement = ";
01307     WriteAsOperand(OS, Replacement);
01308     OS << "\n";
01309   }
01310   for (unsigned i = 0, e = Relationships.size(); i != e; ++i)
01311     Relationships[i].print(OS);
01312 }
01313 
01314 // print - Output this relation to the specified stream
01315 void Relation::print(std::ostream &OS) const {
01316   OS << "    is ";
01317   switch (Rel) {
01318   default:           OS << "*UNKNOWN*"; break;
01319   case Instruction::SetEQ: OS << "== "; break;
01320   case Instruction::SetNE: OS << "!= "; break;
01321   case Instruction::SetLT: OS << "< "; break;
01322   case Instruction::SetGT: OS << "> "; break;
01323   case Instruction::SetLE: OS << "<= "; break;
01324   case Instruction::SetGE: OS << ">= "; break;
01325   }
01326 
01327   WriteAsOperand(OS, Val);
01328   OS << "\n";
01329 }
01330 
01331 // Don't inline these methods or else we won't be able to call them from GDB!
01332 void Relation::dump() const { print(std::cerr); }
01333 void ValueInfo::dump() const { print(std::cerr, 0); }
01334 void RegionInfo::dump() const { print(std::cerr); }