diff options
Diffstat (limited to 'lib/Transforms/Utils')
-rw-r--r-- | lib/Transforms/Utils/CMakeLists.txt | 1 | ||||
-rw-r--r-- | lib/Transforms/Utils/CloneModule.cpp | 2 | ||||
-rw-r--r-- | lib/Transforms/Utils/LoopSimplify.cpp | 74 | ||||
-rw-r--r-- | lib/Transforms/Utils/LowerAllocations.cpp | 2 | ||||
-rw-r--r-- | lib/Transforms/Utils/SSI.cpp | 390 | ||||
-rw-r--r-- | lib/Transforms/Utils/SimplifyCFG.cpp | 2 |
6 files changed, 468 insertions, 3 deletions
diff --git a/lib/Transforms/Utils/CMakeLists.txt b/lib/Transforms/Utils/CMakeLists.txt index d68bf02..10cae5c 100644 --- a/lib/Transforms/Utils/CMakeLists.txt +++ b/lib/Transforms/Utils/CMakeLists.txt @@ -20,6 +20,7 @@ add_llvm_library(LLVMTransformUtils Mem2Reg.cpp PromoteMemoryToRegister.cpp SimplifyCFG.cpp + SSI.cpp UnifyFunctionExitNodes.cpp UnrollLoop.cpp ValueMapper.cpp diff --git a/lib/Transforms/Utils/CloneModule.cpp b/lib/Transforms/Utils/CloneModule.cpp index 337fa8a..82f5b93 100644 --- a/lib/Transforms/Utils/CloneModule.cpp +++ b/lib/Transforms/Utils/CloneModule.cpp @@ -35,7 +35,7 @@ Module *llvm::CloneModule(const Module *M) { Module *llvm::CloneModule(const Module *M, DenseMap<const Value*, Value*> &ValueMap) { // First off, we need to create the new module... - Module *New = new Module(M->getModuleIdentifier()); + Module *New = new Module(M->getModuleIdentifier(), M->getContext()); New->setDataLayout(M->getDataLayout()); New->setTargetTriple(M->getTargetTriple()); New->setModuleInlineAsm(M->getModuleInlineAsm()); diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp index 03d273d..d6b167f 100644 --- a/lib/Transforms/Utils/LoopSimplify.cpp +++ b/lib/Transforms/Utils/LoopSimplify.cpp @@ -42,6 +42,7 @@ #include "llvm/Analysis/Dominators.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Transforms/Utils/Local.h" #include "llvm/Support/CFG.h" #include "llvm/Support/Compiler.h" #include "llvm/ADT/SetOperations.h" @@ -258,6 +259,79 @@ ReprocessLoop: PN->eraseFromParent(); } + // If this loop has muliple exits and the exits all go to the same + // block, attempt to merge the exits. This helps several passes, such + // as LoopRotation, which do not support loops with multiple exits. + // SimplifyCFG also does this (and this code uses the same utility + // function), however this code is loop-aware, where SimplifyCFG is + // not. That gives it the advantage of being able to hoist + // loop-invariant instructions out of the way to open up more + // opportunities, and the disadvantage of having the responsibility + // to preserve dominator information. + if (ExitBlocks.size() > 1 && L->getUniqueExitBlock()) { + SmallVector<BasicBlock*, 8> ExitingBlocks; + L->getExitingBlocks(ExitingBlocks); + for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { + BasicBlock *ExitingBlock = ExitingBlocks[i]; + if (!ExitingBlock->getSinglePredecessor()) continue; + BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator()); + if (!BI || !BI->isConditional()) continue; + CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition()); + if (!CI || CI->getParent() != ExitingBlock) continue; + + // Attempt to hoist out all instructions except for the + // comparison and the branch. + bool AllInvariant = true; + for (BasicBlock::iterator I = ExitingBlock->begin(); &*I != BI; ) { + Instruction *Inst = I++; + if (Inst == CI) + continue; + if (Inst->isTrapping()) { + AllInvariant = false; + break; + } + for (unsigned j = 0, f = Inst->getNumOperands(); j != f; ++j) + if (!L->isLoopInvariant(Inst->getOperand(j))) { + AllInvariant = false; + break; + } + if (!AllInvariant) + break; + // Hoist. + Inst->moveBefore(L->getLoopPreheader()->getTerminator()); + } + if (!AllInvariant) continue; + + // The block has now been cleared of all instructions except for + // a comparison and a conditional branch. SimplifyCFG may be able + // to fold it now. + if (!FoldBranchToCommonDest(BI)) continue; + + // Success. The block is now dead, so remove it from the loop, + // update the dominator tree and dominance frontier, and delete it. + assert(pred_begin(ExitingBlock) == pred_end(ExitingBlock)); + Changed = true; + LI->removeBlock(ExitingBlock); + + DominanceFrontier *DF = getAnalysisIfAvailable<DominanceFrontier>(); + DomTreeNode *Node = DT->getNode(ExitingBlock); + const std::vector<DomTreeNodeBase<BasicBlock> *> &Children = + Node->getChildren(); + for (unsigned k = 0, g = Children.size(); k != g; ++k) { + DT->changeImmediateDominator(Children[k], Node->getIDom()); + if (DF) DF->changeImmediateDominator(Children[k]->getBlock(), + Node->getIDom()->getBlock(), + DT); + } + DT->eraseNode(ExitingBlock); + if (DF) DF->removeBlock(ExitingBlock); + + BI->getSuccessor(0)->removePredecessor(ExitingBlock); + BI->getSuccessor(1)->removePredecessor(ExitingBlock); + ExitingBlock->eraseFromParent(); + } + } + return Changed; } diff --git a/lib/Transforms/Utils/LowerAllocations.cpp b/lib/Transforms/Utils/LowerAllocations.cpp index 9af47f5..74e7028 100644 --- a/lib/Transforms/Utils/LowerAllocations.cpp +++ b/lib/Transforms/Utils/LowerAllocations.cpp @@ -89,7 +89,7 @@ bool LowerAllocations::doInitialization(Module &M) { const Type *BPTy = PointerType::getUnqual(Type::Int8Ty); // Prototype malloc as "char* malloc(...)", because we don't know in // doInitialization whether size_t is int or long. - FunctionType *FT = FunctionType::get(BPTy, std::vector<const Type*>(), true); + FunctionType *FT = FunctionType::get(BPTy, true); MallocFunc = M.getOrInsertFunction("malloc", FT); FreeFunc = M.getOrInsertFunction("free" , Type::VoidTy, BPTy, (Type *)0); return true; diff --git a/lib/Transforms/Utils/SSI.cpp b/lib/Transforms/Utils/SSI.cpp new file mode 100644 index 0000000..4c4dd37 --- /dev/null +++ b/lib/Transforms/Utils/SSI.cpp @@ -0,0 +1,390 @@ +//===------------------- SSI.cpp - Creates SSI Representation -------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass converts a list of variables to the Static Single Information +// form. This is a program representation described by Scott Ananian in his +// Master Thesis: "The Static Single Information Form (1999)". +// We are building an on-demand representation, that is, we do not convert +// every single variable in the target function to SSI form. Rather, we receive +// a list of target variables that must be converted. We also do not +// completely convert a target variable to the SSI format. Instead, we only +// change the variable in the points where new information can be attached +// to its live range, that is, at branch points. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "ssi" + +#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Utils/SSI.h" +#include "llvm/Analysis/Dominators.h" + +using namespace llvm; + +static const std::string SSI_PHI = "SSI_phi"; +static const std::string SSI_SIG = "SSI_sigma"; + +static const unsigned UNSIGNED_INFINITE = ~0U; + +void SSI::getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired<DominanceFrontier>(); + AU.addRequired<DominatorTree>(); + AU.setPreservesAll(); +} + +bool SSI::runOnFunction(Function &F) { + DT_ = &getAnalysis<DominatorTree>(); + return false; +} + +/// This methods creates the SSI representation for the list of values +/// received. It will only create SSI representation if a value is used +/// in a to decide a branch. Repeated values are created only once. +/// +void SSI::createSSI(SmallVectorImpl<Instruction *> &value) { + init(value); + + for (unsigned i = 0; i < num_values; ++i) { + if (created.insert(value[i])) { + needConstruction[i] = true; + } + } + insertSigmaFunctions(value); + + // Test if there is a need to transform to SSI + if (needConstruction.any()) { + insertPhiFunctions(value); + renameInit(value); + rename(DT_->getRoot()); + fixPhis(); + } + + clean(); +} + +/// Insert sigma functions (a sigma function is a phi function with one +/// operator) +/// +void SSI::insertSigmaFunctions(SmallVectorImpl<Instruction *> &value) { + for (unsigned i = 0; i < num_values; ++i) { + if (!needConstruction[i]) + continue; + + bool need = false; + for (Value::use_iterator begin = value[i]->use_begin(), end = + value[i]->use_end(); begin != end; ++begin) { + // Test if the Use of the Value is in a comparator + CmpInst *CI = dyn_cast<CmpInst>(begin); + if (CI && isUsedInTerminator(CI)) { + // Basic Block of the Instruction + BasicBlock *BB = CI->getParent(); + // Last Instruction of the Basic Block + const TerminatorInst *TI = BB->getTerminator(); + + for (unsigned j = 0, e = TI->getNumSuccessors(); j < e; ++j) { + // Next Basic Block + BasicBlock *BB_next = TI->getSuccessor(j); + if (BB_next != BB && + BB_next->getUniquePredecessor() != NULL && + dominateAny(BB_next, value[i])) { + PHINode *PN = PHINode::Create( + value[i]->getType(), SSI_SIG, BB_next->begin()); + PN->addIncoming(value[i], BB); + sigmas.insert(std::make_pair(PN, i)); + created.insert(PN); + need = true; + defsites[i].push_back(BB_next); + } + } + } + } + needConstruction[i] = need; + } +} + +/// Insert phi functions when necessary +/// +void SSI::insertPhiFunctions(SmallVectorImpl<Instruction *> &value) { + DominanceFrontier *DF = &getAnalysis<DominanceFrontier>(); + for (unsigned i = 0; i < num_values; ++i) { + // Test if there were any sigmas for this variable + if (needConstruction[i]) { + + SmallPtrSet<BasicBlock *, 1> BB_visited; + + // Insert phi functions if there is any sigma function + while (!defsites[i].empty()) { + + BasicBlock *BB = defsites[i].back(); + + defsites[i].pop_back(); + DominanceFrontier::iterator DF_BB = DF->find(BB); + + // Iterates through all the dominance frontier of BB + for (std::set<BasicBlock *>::iterator DF_BB_begin = + DF_BB->second.begin(), DF_BB_end = DF_BB->second.end(); + DF_BB_begin != DF_BB_end; ++DF_BB_begin) { + BasicBlock *BB_dominated = *DF_BB_begin; + + // Test if has not yet visited this node and if the + // original definition dominates this node + if (BB_visited.insert(BB_dominated) && + DT_->properlyDominates(value_original[i], BB_dominated) && + dominateAny(BB_dominated, value[i])) { + PHINode *PN = PHINode::Create( + value[i]->getType(), SSI_PHI, BB_dominated->begin()); + phis.insert(std::make_pair(PN, i)); + created.insert(PN); + + defsites[i].push_back(BB_dominated); + } + } + } + BB_visited.clear(); + } + } +} + +/// Some initialization for the rename part +/// +void SSI::renameInit(SmallVectorImpl<Instruction *> &value) { + value_stack.resize(num_values); + for (unsigned i = 0; i < num_values; ++i) { + value_stack[i].push_back(value[i]); + } +} + +/// Renames all variables in the specified BasicBlock. +/// Only variables that need to be rename will be. +/// +void SSI::rename(BasicBlock *BB) { + BitVector *defined = new BitVector(num_values, false); + + // Iterate through instructions and make appropriate renaming. + // For SSI_PHI (b = PHI()), store b at value_stack as a new + // definition of the variable it represents. + // For SSI_SIG (b = PHI(a)), substitute a with the current + // value of a, present in the value_stack. + // Then store bin the value_stack as the new definition of a. + // For all other instructions (b = OP(a, c, d, ...)), we need to substitute + // all operands with its current value, present in value_stack. + for (BasicBlock::iterator begin = BB->begin(), end = BB->end(); + begin != end; ++begin) { + Instruction *I = begin; + if (PHINode *PN = dyn_cast<PHINode>(I)) { // Treat PHI functions + int position; + + // Treat SSI_PHI + if ((position = getPositionPhi(PN)) != -1) { + value_stack[position].push_back(PN); + (*defined)[position] = true; + } + + // Treat SSI_SIG + else if ((position = getPositionSigma(PN)) != -1) { + substituteUse(I); + value_stack[position].push_back(PN); + (*defined)[position] = true; + } + + // Treat all other PHI functions + else { + substituteUse(I); + } + } + + // Treat all other functions + else { + substituteUse(I); + } + } + + // This loop iterates in all BasicBlocks that are successors of the current + // BasicBlock. For each SSI_PHI instruction found, insert an operand. + // This operand is the current operand in value_stack for the variable + // in "position". And the BasicBlock this operand represents is the current + // BasicBlock. + for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) { + BasicBlock *BB_succ = *SI; + + for (BasicBlock::iterator begin = BB_succ->begin(), + notPhi = BB_succ->getFirstNonPHI(); begin != *notPhi; ++begin) { + Instruction *I = begin; + PHINode *PN; + int position; + if ((PN = dyn_cast<PHINode>(I)) && ((position + = getPositionPhi(PN)) != -1)) { + PN->addIncoming(value_stack[position].back(), BB); + } + } + } + + // This loop calls rename on all children from this block. This time children + // refers to a successor block in the dominance tree. + DomTreeNode *DTN = DT_->getNode(BB); + for (DomTreeNode::iterator begin = DTN->begin(), end = DTN->end(); + begin != end; ++begin) { + DomTreeNodeBase<BasicBlock> *DTN_children = *begin; + BasicBlock *BB_children = DTN_children->getBlock(); + rename(BB_children); + } + + // Now we remove all inserted definitions of a variable from the top of + // the stack leaving the previous one as the top. + if (defined->any()) { + for (unsigned i = 0; i < num_values; ++i) { + if ((*defined)[i]) { + value_stack[i].pop_back(); + } + } + } +} + +/// Substitute any use in this instruction for the last definition of +/// the variable +/// +void SSI::substituteUse(Instruction *I) { + for (unsigned i = 0, e = I->getNumOperands(); i < e; ++i) { + Value *operand = I->getOperand(i); + for (unsigned j = 0; j < num_values; ++j) { + if (operand == value_stack[j].front() && + I != value_stack[j].back()) { + PHINode *PN_I = dyn_cast<PHINode>(I); + PHINode *PN_vs = dyn_cast<PHINode>(value_stack[j].back()); + + // If a phi created in a BasicBlock is used as an operand of another + // created in the same BasicBlock, this step marks this second phi, + // to fix this issue later. It cannot be fixed now, because the + // operands of the first phi are not final yet. + if (PN_I && PN_vs && + value_stack[j].back()->getParent() == I->getParent()) { + + phisToFix.insert(PN_I); + } + + I->setOperand(i, value_stack[j].back()); + break; + } + } + } +} + +/// Test if the BasicBlock BB dominates any use or definition of value. +/// +bool SSI::dominateAny(BasicBlock *BB, Instruction *value) { + for (Value::use_iterator begin = value->use_begin(), + end = value->use_end(); begin != end; ++begin) { + Instruction *I = cast<Instruction>(*begin); + BasicBlock *BB_father = I->getParent(); + if (DT_->dominates(BB, BB_father)) { + return true; + } + } + return false; +} + +/// When there is a phi node that is created in a BasicBlock and it is used +/// as an operand of another phi function used in the same BasicBlock, +/// LLVM looks this as an error. So on the second phi, the first phi is called +/// P and the BasicBlock it incomes is B. This P will be replaced by the value +/// it has for BasicBlock B. +/// +void SSI::fixPhis() { + for (SmallPtrSet<PHINode *, 1>::iterator begin = phisToFix.begin(), + end = phisToFix.end(); begin != end; ++begin) { + PHINode *PN = *begin; + for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i) { + PHINode *PN_father; + if ((PN_father = dyn_cast<PHINode>(PN->getIncomingValue(i))) && + PN->getParent() == PN_father->getParent()) { + BasicBlock *BB = PN->getIncomingBlock(i); + int pos = PN_father->getBasicBlockIndex(BB); + PN->setIncomingValue(i, PN_father->getIncomingValue(pos)); + } + } + } +} + +/// Return which variable (position on the vector of variables) this phi +/// represents on the phis list. +/// +unsigned SSI::getPositionPhi(PHINode *PN) { + DenseMap<PHINode *, unsigned>::iterator val = phis.find(PN); + if (val == phis.end()) + return UNSIGNED_INFINITE; + else + return val->second; +} + +/// Return which variable (position on the vector of variables) this phi +/// represents on the sigmas list. +/// +unsigned SSI::getPositionSigma(PHINode *PN) { + DenseMap<PHINode *, unsigned>::iterator val = sigmas.find(PN); + if (val == sigmas.end()) + return UNSIGNED_INFINITE; + else + return val->second; +} + +/// Return true if the the Comparison Instruction is an operator +/// of the Terminator instruction of its Basic Block. +/// +unsigned SSI::isUsedInTerminator(CmpInst *CI) { + TerminatorInst *TI = CI->getParent()->getTerminator(); + if (TI->getNumOperands() == 0) { + return false; + } else if (CI == TI->getOperand(0)) { + return true; + } else { + return false; + } +} + +/// Initializes +/// +void SSI::init(SmallVectorImpl<Instruction *> &value) { + num_values = value.size(); + needConstruction.resize(num_values, false); + + value_original.resize(num_values); + defsites.resize(num_values); + + for (unsigned i = 0; i < num_values; ++i) { + value_original[i] = value[i]->getParent(); + defsites[i].push_back(value_original[i]); + } +} + +/// Clean all used resources in this creation of SSI +/// +void SSI::clean() { + for (unsigned i = 0; i < num_values; ++i) { + defsites[i].clear(); + if (i < value_stack.size()) + value_stack[i].clear(); + } + + phis.clear(); + sigmas.clear(); + phisToFix.clear(); + + defsites.clear(); + value_stack.clear(); + value_original.clear(); + needConstruction.clear(); +} + +/// createSSIPass - The public interface to this file... +/// +FunctionPass *llvm::createSSIPass() { return new SSI(); } + +char SSI::ID = 0; +static RegisterPass<SSI> X("ssi", "Static Single Information Construction"); + diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp index ee0f6a6..58d4d5a 100644 --- a/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/lib/Transforms/Utils/SimplifyCFG.cpp @@ -1492,7 +1492,7 @@ static bool SimplifyCondBranchToTwoReturns(BranchInst *BI) { /// and if a predecessor branches to us and one of our successors, fold the /// setcc into the predecessor and use logical operations to pick the right /// destination. -static bool FoldBranchToCommonDest(BranchInst *BI) { +bool llvm::FoldBranchToCommonDest(BranchInst *BI) { BasicBlock *BB = BI->getParent(); Instruction *Cond = dyn_cast<Instruction>(BI->getCondition()); if (Cond == 0) return false; |