diff options
Diffstat (limited to 'lib/Transforms')
| -rw-r--r-- | lib/Transforms/Scalar/CorrelatedExprs.cpp | 1486 |
1 files changed, 0 insertions, 1486 deletions
diff --git a/lib/Transforms/Scalar/CorrelatedExprs.cpp b/lib/Transforms/Scalar/CorrelatedExprs.cpp deleted file mode 100644 index 9e1aa71e8b..0000000000 --- a/lib/Transforms/Scalar/CorrelatedExprs.cpp +++ /dev/null @@ -1,1486 +0,0 @@ -//===- CorrelatedExprs.cpp - Pass to detect and eliminated c.e.'s ---------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// Correlated Expression Elimination propagates information from conditional -// branches to blocks dominated by destinations of the branch. It propagates -// information from the condition check itself into the body of the branch, -// allowing transformations like these for example: -// -// if (i == 7) -// ... 4*i; // constant propagation -// -// M = i+1; N = j+1; -// if (i == j) -// X = M-N; // = M-M == 0; -// -// This is called Correlated Expression Elimination because we eliminate or -// simplify expressions that are correlated with the direction of a branch. In -// this way we use static information to give us some information about the -// dynamic value of a variable. -// -//===----------------------------------------------------------------------===// - -#define DEBUG_TYPE "cee" -#include "llvm/Transforms/Scalar.h" -#include "llvm/Constants.h" -#include "llvm/Pass.h" -#include "llvm/Function.h" -#include "llvm/Instructions.h" -#include "llvm/Type.h" -#include "llvm/DerivedTypes.h" -#include "llvm/Analysis/ConstantFolding.h" -#include "llvm/Analysis/Dominators.h" -#include "llvm/Assembly/Writer.h" -#include "llvm/Transforms/Utils/BasicBlockUtils.h" -#include "llvm/Support/CFG.h" -#include "llvm/Support/Compiler.h" -#include "llvm/Support/ConstantRange.h" -#include "llvm/Support/Debug.h" -#include "llvm/ADT/PostOrderIterator.h" -#include "llvm/ADT/Statistic.h" -#include <algorithm> -using namespace llvm; - -STATISTIC(NumCmpRemoved, "Number of cmp instruction eliminated"); -STATISTIC(NumOperandsCann, "Number of operands canonicalized"); -STATISTIC(BranchRevectors, "Number of branches revectored"); - -namespace { - class ValueInfo; - class VISIBILITY_HIDDEN Relation { - Value *Val; // Relation to what value? - unsigned Rel; // SetCC or ICmp relation, or Add if no information - public: - explicit Relation(Value *V) : Val(V), Rel(Instruction::Add) {} - bool operator<(const Relation &R) const { return Val < R.Val; } - Value *getValue() const { return Val; } - unsigned getRelation() const { return Rel; } - - // contradicts - Return true if the relationship specified by the operand - // contradicts already known information. - // - bool contradicts(unsigned Rel, const ValueInfo &VI) const; - - // incorporate - Incorporate information in the argument into this relation - // entry. This assumes that the information doesn't contradict itself. If - // any new information is gained, true is returned, otherwise false is - // returned to indicate that nothing was updated. - // - bool incorporate(unsigned Rel, ValueInfo &VI); - - // KnownResult - Whether or not this condition determines the result of a - // setcc or icmp in the program. False & True are intentionally 0 & 1 - // so we can convert to bool by casting after checking for unknown. - // - enum KnownResult { KnownFalse = 0, KnownTrue = 1, Unknown = 2 }; - - // getImpliedResult - If this relationship between two values implies that - // the specified relationship is true or false, return that. If we cannot - // determine the result required, return Unknown. - // - KnownResult getImpliedResult(unsigned Rel) const; - - // print - Output this relation to the specified stream - void print(std::ostream &OS) const; - void dump() const; - }; - - - // ValueInfo - One instance of this record exists for every value with - // relationships between other values. It keeps track of all of the - // relationships to other values in the program (specified with Relation) that - // are known to be valid in a region. - // - class VISIBILITY_HIDDEN ValueInfo { - // RelationShips - this value is know to have the specified relationships to - // other values. There can only be one entry per value, and this list is - // kept sorted by the Val field. - std::vector<Relation> Relationships; - - // If information about this value is known or propagated from constant - // expressions, this range contains the possible values this value may hold. - ConstantRange Bounds; - - // If we find that this value is equal to another value that has a lower - // rank, this value is used as it's replacement. - // - Value *Replacement; - public: - explicit ValueInfo(const Type *Ty) - : Bounds(Ty->isInteger() ? cast<IntegerType>(Ty)->getBitWidth() : 32), - Replacement(0) {} - - // getBounds() - Return the constant bounds of the value... - const ConstantRange &getBounds() const { return Bounds; } - ConstantRange &getBounds() { return Bounds; } - - const std::vector<Relation> &getRelationships() { return Relationships; } - - // getReplacement - Return the value this value is to be replaced with if it - // exists, otherwise return null. - // - Value *getReplacement() const { return Replacement; } - - // setReplacement - Used by the replacement calculation pass to figure out - // what to replace this value with, if anything. - // - void setReplacement(Value *Repl) { Replacement = Repl; } - - // getRelation - return the relationship entry for the specified value. - // This can invalidate references to other Relations, so use it carefully. - // - Relation &getRelation(Value *V) { - // Binary search for V's entry... - std::vector<Relation>::iterator I = - std::lower_bound(Relationships.begin(), Relationships.end(), - Relation(V)); - - // If we found the entry, return it... - if (I != Relationships.end() && I->getValue() == V) - return *I; - - // Insert and return the new relationship... - return *Relationships.insert(I, Relation(V)); - } - - const Relation *requestRelation(Value *V) const { - // Binary search for V's entry... - std::vector<Relation>::const_iterator I = - std::lower_bound(Relationships.begin(), Relationships.end(), - Relation(V)); - if (I != Relationships.end() && I->getValue() == V) - return &*I; - return 0; - } - - // print - Output information about this value relation... - void print(std::ostream &OS, Value *V) const; - void dump() const; - }; - - // RegionInfo - Keeps track of all of the value relationships for a region. A - // region is the are dominated by a basic block. RegionInfo's keep track of - // the RegionInfo for their dominator, because anything known in a dominator - // is known to be true in a dominated block as well. - // - class VISIBILITY_HIDDEN RegionInfo { - BasicBlock *BB; - - // ValueMap - Tracks the ValueInformation known for this region - typedef std::map<Value*, ValueInfo> ValueMapTy; - ValueMapTy ValueMap; - public: - explicit RegionInfo(BasicBlock *bb) : BB(bb) {} - - // getEntryBlock - Return the block that dominates all of the members of - // this region. - BasicBlock *getEntryBlock() const { return BB; } - - // empty - return true if this region has no information known about it. - bool empty() const { return ValueMap.empty(); } - - const RegionInfo &operator=(const RegionInfo &RI) { - ValueMap = RI.ValueMap; - return *this; - } - - // print - Output information about this region... - void print(std::ostream &OS) const; - void dump() const; - - // Allow external access. - typedef ValueMapTy::iterator iterator; - iterator begin() { return ValueMap.begin(); } - iterator end() { return ValueMap.end(); } - - ValueInfo &getValueInfo(Value *V) { - ValueMapTy::iterator I = ValueMap.lower_bound(V); - if (I != ValueMap.end() && I->first == V) return I->second; - return ValueMap.insert(I, std::make_pair(V, V->getType()))->second; - } - - const ValueInfo *requestValueInfo(Value *V) const { - ValueMapTy::const_iterator I = ValueMap.find(V); - if (I != ValueMap.end()) return &I->second; - return 0; - } - - /// removeValueInfo - Remove anything known about V from our records. This - /// works whether or not we know anything about V. - /// - void removeValueInfo(Value *V) { - ValueMap.erase(V); - } - }; - - /// CEE - Correlated Expression Elimination - class VISIBILITY_HIDDEN CEE : public FunctionPass { - std::map<Value*, unsigned> RankMap; - std::map<BasicBlock*, RegionInfo> RegionInfoMap; - DominatorTree *DT; - public: - static char ID; // Pass identification, replacement for typeid - CEE() : FunctionPass((intptr_t)&ID) {} - - virtual bool runOnFunction(Function &F); - - // We don't modify the program, so we preserve all analyses - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired<DominatorTree>(); - AU.addRequiredID(BreakCriticalEdgesID); - }; - - // print - Implement the standard print form to print out analysis - // information. - virtual void print(std::ostream &O, const Module *M) const; - - private: - RegionInfo &getRegionInfo(BasicBlock *BB) { - std::map<BasicBlock*, RegionInfo>::iterator I - = RegionInfoMap.lower_bound(BB); - if (I != RegionInfoMap.end() && I->first == BB) return I->second; - return RegionInfoMap.insert(I, std::make_pair(BB, BB))->second; - } - - void BuildRankMap(Function &F); - unsigned getRank(Value *V) const { - if (isa<Constant>(V)) return 0; - std::map<Value*, unsigned>::const_iterator I = RankMap.find(V); - if (I != RankMap.end()) return I->second; - return 0; // Must be some other global thing - } - - bool TransformRegion(BasicBlock *BB, std::set<BasicBlock*> &VisitedBlocks); - - bool ForwardCorrelatedEdgeDestination(TerminatorInst *TI, unsigned SuccNo, - RegionInfo &RI); - - void ForwardSuccessorTo(TerminatorInst *TI, unsigned Succ, BasicBlock *D, - RegionInfo &RI); - void ReplaceUsesOfValueInRegion(Value *Orig, Value *New, - BasicBlock *RegionDominator); - void CalculateRegionExitBlocks(BasicBlock *BB, BasicBlock *OldSucc, - std::vector<BasicBlock*> &RegionExitBlocks); - void InsertRegionExitMerges(PHINode *NewPHI, Instruction *OldVal, - const std::vector<BasicBlock*> &RegionExitBlocks); - - void PropagateBranchInfo(BranchInst *BI); - void PropagateSwitchInfo(SwitchInst *SI); - void PropagateEquality(Value *Op0, Value *Op1, RegionInfo &RI); - void PropagateRelation(unsigned Opcode, Value *Op0, - Value *Op1, RegionInfo &RI); - void UpdateUsersOfValue(Value *V, RegionInfo &RI); - void IncorporateInstruction(Instruction *Inst, RegionInfo &RI); - void ComputeReplacements(RegionInfo &RI); - - // getCmpResult - Given a icmp instruction, determine if the result is - // determined by facts we already know about the region under analysis. - // Return KnownTrue, KnownFalse, or UnKnown based on what we can determine. - Relation::KnownResult getCmpResult(CmpInst *ICI, const RegionInfo &RI); - - bool SimplifyBasicBlock(BasicBlock &BB, const RegionInfo &RI); - bool SimplifyInstruction(Instruction *Inst, const RegionInfo &RI); - }; - - char CEE::ID = 0; - RegisterPass<CEE> X("cee", "Correlated Expression Elimination"); -} - -FunctionPass *llvm::createCorrelatedExpressionEliminationPass() { - return new CEE(); -} - - -bool CEE::runOnFunction(Function &F) { - // Build a rank map for the function... - BuildRankMap(F); - - // Traverse the dominator tree, computing information for each node in the - // tree. Note that our traversal will not even touch unreachable basic - // blocks. - DT = &getAnalysis<DominatorTree>(); - - std::set<BasicBlock*> VisitedBlocks; - bool Changed = TransformRegion(&F.getEntryBlock(), VisitedBlocks); - - RegionInfoMap.clear(); - RankMap.clear(); - return Changed; -} - -// TransformRegion - Transform the region starting with BB according to the -// calculated region information for the block. Transforming the region -// involves analyzing any information this block provides to successors, -// propagating the information to successors, and finally transforming -// successors. -// -// This method processes the function in depth first order, which guarantees -// that we process the immediate dominator of a block before the block itself. -// Because we are passing information from immediate dominators down to -// dominatees, we obviously have to process the information source before the -// information consumer. -// -bool CEE::TransformRegion(BasicBlock *BB, std::set<BasicBlock*> &VisitedBlocks){ - // Prevent infinite recursion... - if (VisitedBlocks.count(BB)) return false; - VisitedBlocks.insert(BB); - - // Get the computed region information for this block... - RegionInfo &RI = getRegionInfo(BB); - - // Compute the replacement information for this block... - ComputeReplacements(RI); - - // If debugging, print computed region information... - DEBUG(RI.print(*cerr.stream())); - - // Simplify the contents of this block... - bool Changed = SimplifyBasicBlock(*BB, RI); - - // Get the terminator of this basic block... - TerminatorInst *TI = BB->getTerminator(); - - // Loop over all of the blocks that this block is the immediate dominator for. - // Because all information known in this region is also known in all of the - // blocks that are dominated by this one, we can safely propagate the - // information down now. - // - DomTreeNode *BBDom = DT->getNode(BB); - if (!RI.empty()) { // Time opt: only propagate if we can change something - for (std::vector<DomTreeNode*>::iterator DI = BBDom->begin(), - E = BBDom->end(); DI != E; ++DI) { - BasicBlock *ChildBB = (*DI)->getBlock(); - assert(RegionInfoMap.find(ChildBB) == RegionInfoMap.end() && - "RegionInfo should be calculated in dominanace order!"); - getRegionInfo(ChildBB) = RI; - } - } - - // Now that all of our successors have information if they deserve it, - // propagate any information our terminator instruction finds to our - // successors. - if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { - if (BI->isConditional()) - PropagateBranchInfo(BI); - } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { - PropagateSwitchInfo(SI); - } - - // If this is a branch to a block outside our region that simply performs - // another conditional branch, one whose outcome is known inside of this - // region, then vector this outgoing edge directly to the known destination. - // - for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) - while (ForwardCorrelatedEdgeDestination(TI, i, RI)) { - ++BranchRevectors; - Changed = true; - } - - // Now that all of our successors have information, recursively process them. - for (std::vector<DomTreeNode*>::iterator DI = BBDom->begin(), - E = BBDom->end(); DI != E; ++DI) { - BasicBlock *ChildBB = (*DI)->getBlock(); - Changed |= TransformRegion(ChildBB, VisitedBlocks); - } - - return Changed; -} - -// isBlockSimpleEnoughForCheck to see if the block is simple enough for us to -// revector the conditional branch in the bottom of the block, do so now. -// -static bool isBlockSimpleEnough(BasicBlock *BB) { - assert(isa<BranchInst>(BB->getTerminator())); - BranchInst *BI = cast<BranchInst>(BB->getTerminator()); - assert(BI->isConditional()); - - // Check the common case first: empty block, or block with just a setcc. - if (BB->size() == 1 || - (BB->size() == 2 && &BB->front() == BI->getCondition() && - BI->getCondition()->hasOneUse())) - return true; - - // Check the more complex case now... - BasicBlock::iterator I = BB->begin(); - - // FIXME: This should be reenabled once the regression with SIM is fixed! -#if 0 - // PHI Nodes are ok, just skip over them... - while (isa<PHINode>(*I)) ++I; -#endif - - // Accept the setcc instruction... - if (&*I == BI->getCondition()) - ++I; - - // Nothing else is acceptable here yet. We must not revector... unless we are - // at the terminator instruction. - if (&*I == BI) - return true; - - return false; -} - - -bool CEE::ForwardCorrelatedEdgeDestination(TerminatorInst *TI, unsigned SuccNo, - RegionInfo &RI) { - // If this successor is a simple block not in the current region, which - // contains only a conditional branch, we decide if the outcome of the branch - // can be determined from information inside of the region. Instead of going - // to this block, we can instead go to the destination we know is the right - // target. - // - - // Check to see if we dominate the block. If so, this block will get the - // condition turned to a constant anyway. - // - //if (EF->dominates(RI.getEntryBlock(), BB)) - // return 0; - - BasicBlock *BB = TI->getParent(); - - // Get the destination block of this edge... - BasicBlock *OldSucc = TI->getSuccessor(SuccNo); - - // Make sure that the block ends with a conditional branch and is simple - // enough for use to be able to revector over. - BranchInst *BI = dyn_cast<BranchInst>(OldSucc->getTerminator()); - if (BI == 0 || !BI->isConditional() || !isBlockSimpleEnough(OldSucc)) - return false; - - // We can only forward the branch over the block if the block ends with a - // cmp we can determine the outcome for. - // - // FIXME: we can make this more generic. Code below already handles more - // generic case. - if (!isa<CmpInst>(BI->getCondition())) - return false; - - // Make a new RegionInfo structure so that we can simulate the effect of the - // PHI nodes in the block we are skipping over... - // - RegionInfo NewRI(RI); - - // Remove value information for all of the values we are simulating... to make - // sure we don't have any stale information. - for (BasicBlock::iterator I = OldSucc->begin(), E = OldSucc->end(); I!=E; ++I) - if (I->getType() != Type::VoidTy) - NewRI.removeValueInfo(I); - - // Put the newly discovered information into the RegionInfo... - for (BasicBlock::iterator I = OldSucc->begin(), E = OldSucc->end(); I!=E; ++I) - if (PHINode *PN = dyn_cast<PHINode>(I)) { - int OpNum = PN->getBasicBlockIndex(BB); - assert(OpNum != -1 && "PHI doesn't have incoming edge for predecessor!?"); - PropagateEquality(PN, PN->getIncomingValue(OpNum), NewRI); - } else if (CmpInst *CI = dyn_cast<CmpInst>(I)) { - Relation::KnownResult Res = getCmpResult(CI, NewRI); - if (Res == Relation::Unknown) return false; - PropagateEquality(CI, ConstantInt::get(Type::Int1Ty, Res), NewRI); - } else { - assert(isa<BranchInst>(*I) && "Unexpected instruction type!"); - } - - // Compute the facts implied by what we have discovered... - ComputeReplacements(NewRI); - - ValueInfo &PredicateVI = NewRI.getValueInfo(BI->getCondition()); - if (PredicateVI.getReplacement() && - isa<Constant>(PredicateVI.getReplacement()) && - !isa<GlobalValue>(PredicateVI.getReplacement())) { - ConstantInt *CB = cast<ConstantInt>(PredicateVI.getReplacement()); - - // Forward to the successor that corresponds to the branch we will take. - ForwardSuccessorTo(TI, SuccNo, - BI->getSuccessor(!CB->getZExtValue()), NewRI); - return true; - } - - return false; -} - -static Value *getReplacementOrValue(Value *V, RegionInfo &RI) { - if (const ValueInfo *VI = RI.requestValueInfo(V)) - if (Value *Repl = VI->getReplacement()) - return Repl; - return V; -} - -/// ForwardSuccessorTo - We have found that we can forward successor # 'SuccNo' -/// of Terminator 'TI' to the 'Dest' BasicBlock. This method performs the -/// mechanics of updating SSA information and revectoring the branch. -/// -void CEE::ForwardSuccessorTo(TerminatorInst *TI, unsigned SuccNo, - BasicBlock *Dest, RegionInfo &RI) { - // If there are any PHI nodes in the Dest BB, we must duplicate the entry - // in the PHI node for the old successor to now include an entry from the - // current basic block. - // - BasicBlock *OldSucc = TI->getSuccessor(SuccNo); - BasicBlock *BB = TI->getParent(); - - DOUT << "Forwarding branch in basic block %" << BB->getName() - << " from block %" << OldSucc->getName() << " to block %" - << Dest->getName() << "\n" - << "Before forwarding: " << *BB->getParent(); - - // Because we know that there cannot be critical edges in the flow graph, and - // that OldSucc has multiple outgoing edges, this means that Dest cannot have - // multiple incoming edges. - // -#ifndef NDEBUG - pred_iterator DPI = pred_begin(Dest); ++DPI; - assert(DPI == pred_end(Dest) && "Critical edge found!!"); -#endif - - // Loop over any PHI nodes in the destination, eliminating them, because they - // may only have one input. - // - while (PHINode *PN = dyn_cast<PHINode>(&Dest->front())) { - assert(PN->getNumIncomingValues() == 1 && "Crit edge found!"); - // Eliminate the PHI node - PN->replaceAllUsesWith(PN->getIncomingValue(0)); - Dest->getInstList().erase(PN); - } - - // If there are values defined in the "OldSucc" basic block, we need to insert - // PHI nodes in the regions we are dealing with to emulate them. This can - // insert dead phi nodes, but it is more trouble to see if they are used than - // to just blindly insert them. - // - if (DT->dominates(OldSucc, Dest)) { - // RegionExitBlocks - Find all of the blocks that are not dominated by Dest, - // but have predecessors that are. Additionally, prune down the set to only - // include blocks that are dominated by OldSucc as well. - // - std::vector<BasicBlock*> RegionExitBlocks; - CalculateRegionExitBlocks(Dest, OldSucc, RegionExitBlocks); - - for (BasicBlock::iterator I = OldSucc->begin(), E = OldSucc->end(); - I != E; ++I) - if (I->getType() != Type::VoidTy) { - // Create and insert the PHI node into the top of Dest. - PHINode *NewPN = new PHINode(I->getType(), I->getName()+".fw_merge", - Dest->begin()); - // There is definitely an edge from OldSucc... add the edge now - NewPN->addIncoming(I, OldSucc); - - // There is also an edge from BB now, add the edge with the calculated - // value from the RI. - NewPN->addIncoming(getReplacementOrValue(I, RI), BB); - - // Make everything in the Dest region use the new PHI node now... - ReplaceUsesOfValueInRegion(I, NewPN, Dest); - - // Make sure that exits out of the region dominated by NewPN get PHI - // nodes that merge the values as appropriate. - InsertRegionExitMerges(NewPN, I, RegionExitBlocks); - } - } - - // If there were PHI nodes in OldSucc, we need to remove the entry for this - // edge from the PHI node, and we need to replace any references to the PHI - // node with a new value. - // - for (BasicBlock::iterator I = OldSucc->begin(); isa<PHINode>(I); ) { - PHINode *PN = cast<PHINode>(I); - - // Get the value flowing across the old edge and remove the PHI node entry - // for this edge: we are about to remove the edge! Don't remove the PHI - // node yet though if this is the last edge into it. - Value *EdgeValue = PN->removeIncomingValue(BB, false); - - // Make sure that anything that used to use PN now refers to EdgeValue - ReplaceUsesOfValueInRegion(PN, EdgeValue, Dest); - - // If there is only one value left coming into the PHI node, replace the PHI - // node itself with the one incoming value left. - // - if (PN->getNumIncomingValues() == 1) { - assert(PN->getNumIncomingValues() == 1); - PN->replaceAllUsesWith(PN->getIncomingValue(0)); - PN->getParent()->getInstList().erase(PN); - I = OldSucc->begin(); - } else if (PN->getNumIncomingValues() == 0) { // Nuke the PHI - // If we removed the last incoming value to this PHI, nuke the PHI node - // now. - PN->replaceAllUsesWith(Constant::getNullValue(PN->getType())); - PN->getParent()->getInstList().erase(PN); - I = OldSucc->begin(); - } else { - ++I; // Otherwise, move on to the next PHI node - } - } - - // Actually revector the branch now... - TI->setSuccessor(SuccNo, Dest); - - // If we just introduced a critical edge in the flow graph, make sure to break - // it right away... - SplitCriticalEdge(TI, SuccNo, this); - - // Make sure that we don't introduce critical edges from oldsucc now! - for (unsigned i = 0, e = OldSucc->getTerminator()->getNumSuccessors(); - i != e; ++i) - SplitCriticalEdge(OldSucc->getTerminator(), i, this); - - // Since we invalidated the CFG, recalculate the dominator set so that it is - // useful for later processing! - // FIXME: This is much worse than it really should be! - //EF->recalculate(); - - DOUT << "After forwarding: " << *BB->getParent(); -} - -/// ReplaceUsesOfValueInRegion - This method replaces all uses of Orig with uses -/// of New. It only affects instructions that are defined in basic blocks that -/// are dominated by Head. -/// -void CEE::ReplaceUsesOfValueInRegion(Value *Orig, Value *New, - BasicBlock *RegionDominator) { - assert(Orig != New && "Cannot replace value with itself"); - std::vector<Instruction*> InstsToChange; - std::vector<PHINode*> PHIsToChange; - InstsToChange.reserve(Orig->getNumUses()); - - // Loop over instructions adding them to InstsToChange vector, this allows us - // an easy way to avoid invalidating the use_iterator at a bad time. - for (Value::use_iterator I = Orig->use_begin(), E = Orig->use_end(); - I != E; ++I) - if (Instruction *User = dyn_cast<Instruction>(*I)) - if (DT->dominates(RegionDominator, User->getParent())) - InstsToChange.push_back(User); - else if (PHINode *PN = dyn_cast<PHINode>(User)) { - PHIsToChange.push_back(PN); - } - - // PHIsToChange contains PHI nodes that use Orig that do not live in blocks - // dominated by orig. If the block the value flows in from is dominated by - // RegionDominator, then we rewrite the PHI - for (unsigned i = 0, e = PHIsToChange.size(); i != e; ++i) { - PHINode *PN = PHIsToChange[i]; - for (unsigned j = 0, e = PN->getNumIncomingValues(); j != e; ++j) - if (PN->getIncomingValue(j) == Orig && - DT->dominates(RegionDominator, PN->getIncomingBlock(j))) - PN->setIncomingValue(j, New); - } - - // Loop over the InstsToChange list, replacing all uses of Orig with uses of - // New. This list contains all of the instructions in our region that use - // Orig. - for (unsigned i = 0, e = InstsToChange.size(); i != e; ++i) - if (PHINode *PN = dyn_cast<PHINode>(InstsToChange[i])) { - // PHINodes must be handled carefully. If the PHI node itself is in the - // region, we have to make sure to only do the replacement for incoming - // values that correspond to basic blocks in the region. - for (unsigned j = 0, e = PN->getNumIncomingValues(); j != e; ++j) - if (PN->getIncomingValue(j) == Orig && - DT->dominates(RegionDominator, PN->getIncomingBlock(j))) - PN->setIncomingValue(j, New); - - } else { - InstsToChange[i]->replaceUsesOfWith(Orig, New); - } -} - -static void CalcRegionExitBlocks(BasicBlock *Header, BasicBlock *BB, - std::set<BasicBlock*> &Visited, - DominatorTree &DT, - std::vector<BasicBlock*> &RegionExitBlocks) { - if (Visited.count(BB)) return; - Visited.insert(BB); - - if (DT.dominates(Header, BB)) { // Block in the region, recursively traverse - for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) - CalcRegionExitBlocks(Header, *I, Visited, DT, RegionExitBlocks); - } else { - // Header does not dominate this block, but we have a predecessor that does - // dominate us. Add ourself to the list. - RegionExitBlocks.push_back(BB); - } -} - -/// CalculateRegionExitBlocks - Find all of the blocks that are not dominated by -/// BB, but have predecessors that are. Additionally, prune down the set to -/// only include blocks that are dominated by OldSucc as well. -/// -void CEE::CalculateRegionExitBlocks(BasicBlock *BB, BasicBlock *OldSucc, - std::vector<BasicBlock*> &RegionExitBlocks){ - std::set<BasicBlock*> Visited; // Don't infinite loop - - // Recursively calculate blocks we are interested in... - CalcRegionExitBlocks(BB, BB, Visited, *DT, RegionExitBlocks); - - // Filter out blocks that are not dominated by OldSucc... - for (unsigned i = 0; i != RegionExitBlocks.size(); ) { - if (DT->dominates(OldSucc, RegionExitBlocks[i])) - ++i; // Block is ok, keep it. - else { - // Move to end of list... - std::swap(RegionExitBlocks[i], RegionExitBlocks.back()); - RegionExitBlocks.pop_back(); // Nuke the end - } - } -} - -void CEE::InsertRegionExitMerges(PHINode *BBVal, Instruction *OldVal, - const std::vector<BasicBlock*> &RegionExitBlocks) { - assert(BBVal->getType() == OldVal->getType() && "Should be derived values!"); - BasicBlock *BB = BBVal->getParent(); - - // Loop over all of the blocks we have to place PHIs in, doing it. - for (unsigned i = 0, e = RegionExitBlocks.size(); i != e; ++i) { - BasicBlock *FBlock = RegionExitBlocks[i]; // Block on the frontier - - // Create the new PHI node - PHINode *NewPN = new PHINode(BBVal->getType(), - OldVal->getName()+".fw_frontier", - FBlock->begin()); - - // Add an incoming value for every predecessor of the block... - for (pred_iterator PI = pred_begin(FBlock), PE = pred_end(FBlock); - PI != PE; ++PI) { - // If the incoming edge is from the region dominated by BB, use BBVal, - // otherwise use OldVal. - NewPN->addIncoming(DT->dominates(BB, *PI) ? BBVal : OldVal, *PI); - } - - // Now make everyone dominated by this block use this new value! - ReplaceUsesOfValueInRegion(OldVal, NewPN, FBlock); - } -} - - - -// BuildRankMap - This method builds the rank map data structure which gives -// each instruction/value in the function a value based on how early it appears -// in the function. We give constants and globals rank 0, arguments are -// numbered starting at one, and instructions are numbered in reverse post-order -// from where the arguments leave off. This gives instructions in loops higher -// values than instructions not in loops. -// -void CEE::BuildRankMap(Function &F) { - unsigned Rank = 1; // Skip rank zero. - - // Number the arguments... - for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) - RankMap[I] = Rank++; - - // Number the instructions in reverse post order... - ReversePostOrderTraversal<Function*> RPOT(&F); - for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(), - E = RPOT.end(); I != E; ++I) - for (BasicBlock::iterator BBI = (*I)->begin(), E = (*I)->end(); - BBI != E; ++BBI) - if (BBI->getType() != Type::VoidTy) - RankMap[BBI] = Rank++; -} - - -// PropagateBranchInfo - When this method is invoked, we need to propagate -// information derived from the branch condition into the true and false -// branches of BI. Since we know that there aren't any critical edges in the -// flow graph, this can proceed unconditionally. -// -void CEE::PropagateBranchInfo(BranchInst *BI) { - assert(BI->isConditional() && "Must be a conditional branch!"); - - // Propagate information into the true block... - // - PropagateEquality(BI->getCondition(), ConstantInt::getTrue(), - getRegionInfo(BI->getSuccessor(0))); - - // Propagate information into the false block... - // - PropagateEquality(BI->getCondition(), ConstantInt::getFalse(), - getRegionInfo(BI->getSuccessor(1))); -} - - -// PropagateSwitchInfo - We need to propagate the value tested by the -// switch statement through each case block. -// -void CEE::PropagateSwitchInfo(SwitchInst *SI) { - // Propagate information down each of our non-default case labels. We - // don't yet propagate information down the default label, because a - // potentially large number of inequality constraints provide less - // benefit per unit work than a single equality constraint. - // - Value *cond = SI->getCondition(); - for (unsigned i = 1; i < SI->getNumSuccessors(); ++i) - PropagateEquality(cond, SI->getSuccessorValue(i), - getRegionInfo(SI->getSuccessor(i))); -} - - -// PropagateEquality - If we discover that two values are equal to each other in -// a specified region, propagate this knowledge recursively. -// -void CEE::PropagateEquality(Value *Op0, Value *Op1, RegionInfo &RI) { - if (Op0 == Op1) return; // Gee whiz. Are these really equal each other? - - if (isa<Constant>(Op0)) // Make sure the constant is always Op1 - std::swap(Op0, Op1); - - // Make sure we don't already know these are equal, to avoid infinite loops... - ValueInfo &VI = RI.getValueInfo(Op0); - - // Get information about the known relationship between Op0 & Op1 - Relation &KnownRelation = VI.getRelation(Op1); - - // If we already know they're equal, don't reprocess... - if (KnownRelation.getRelation() == FCmpInst::FCMP_OEQ || - KnownRelation.getRelation() == ICmpInst::ICMP_EQ) - return; - - // If this is boolean, check to see if one of the operands is a constant. If - // it's a constant, then see if the other one is one of a setcc instruction, - // an AND, OR, or XOR instruction. - // - ConstantInt *CB = dyn_cast<ConstantInt>(Op1); - if (CB && Op1->getType() == Type::Int1Ty) { - if (Instruction *Inst = dyn_cast<Instruction>(Op0)) { - // If we know that this instruction is an AND instruction, and the - // result is true, this means that both operands to the OR are known - // to be true as well. - // - if (CB->getZExtValue() && Inst->getOpcode() == Instruction::And) { - PropagateEquality(Inst->getOperand(0), CB, RI); - PropagateEquality(Inst->getOperand(1), CB, RI); - } - - // If we know that this instruction is an OR instruction, and the result - // is false, this means that both operands to the OR are know to be - // false as well. - // - if (!CB->getZExtValue() && Inst->getOpcode() == Instruction::Or) { - PropagateEquality(Inst->getOperand(0), CB, RI); - PropagateEquality(Inst->getOperand(1), CB, RI); - } - - // If we know that this instruction is a NOT instruction, we know that - // the operand is known to be the inverse of whatever the current - // value is. - // - if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(Inst)) - if (BinaryOperator::isNot(BOp)) - PropagateEquality(BinaryOperator::getNotArgument(BOp), - ConstantInt::get(Type::Int1Ty, - !CB->getZExtValue()), RI); - - // If we know the value of a FCmp instruction, propagate the information - // about the relation into this region as well. - // - if (FCmpInst *FCI = dyn_cast<FCmpInst>(Inst)) { - if (CB->getZExtValue()) { // If we know the condition is true... - // Propagate info about the LHS to the RHS & RHS to LHS - PropagateRelation(FCI->getPredicate(), FCI->getOperand(0), - FCI->getOperand(1), RI); - PropagateRelation(FCI->getSwappedPredicate(), - FCI->getOperand(1), FCI->getOperand(0), RI); - - } else { // If we know the condition is false... - // We know the opposite of the condition is true... - FCmpInst::Predicate C = FCI->getInversePredicate(); - - PropagateRelation(C, FCI->getOperand(0), FCI->getOperand(1), RI); - PropagateRelation(FCmpInst::getSwappedPredicate(C), - FCI->getOperand(1), FCI->getOperand(0), RI); - } - } - - // If we know the value of a ICmp instruction, propagate the information - |