summaryrefslogtreecommitdiff
path: root/lib/Transforms/Utils
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Transforms/Utils')
-rw-r--r--lib/Transforms/Utils/CMakeLists.txt1
-rw-r--r--lib/Transforms/Utils/CloneModule.cpp2
-rw-r--r--lib/Transforms/Utils/LoopSimplify.cpp74
-rw-r--r--lib/Transforms/Utils/LowerAllocations.cpp2
-rw-r--r--lib/Transforms/Utils/SSI.cpp390
-rw-r--r--lib/Transforms/Utils/SimplifyCFG.cpp2
6 files changed, 468 insertions, 3 deletions
diff --git a/lib/Transforms/Utils/CMakeLists.txt b/lib/Transforms/Utils/CMakeLists.txt
index d68bf0291011..10cae5ca7087 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 337fa8a44bbe..82f5b93a9544 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 03d273d25d79..d6b167f8b848 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 9af47f56ef3d..74e7028d127c 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 000000000000..4c4dd37ddf75
--- /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 ee0f6a65de4e..58d4d5a344c1 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;