LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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