LLVM API Documentation
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); }