From 715029478c0a54cab2c366816d11d712bf51efc5 Mon Sep 17 00:00:00 2001 From: Nick Lewycky Date: Fri, 3 Jul 2009 19:28:36 +0000 Subject: [PATCH] =?utf8?q?=EF=BB=BFAdd=20Static=20Single=20Information=20c?= =?utf8?q?onstruction=20pass=20written=20by=20Andr=C3=A9=20Tavares!=20Use?= =?utf8?q?=20it=20by=20requiring=20it=20through=20the=20pass=20manager,=20?= =?utf8?q?then=20calling=20its=20createSSI=20method=20on=20the=20variables?= =?utf8?q?=20that=20you=20want=20in=20SSI=20form.?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74780 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/LinkAllPasses.h | 1 + include/llvm/Transforms/Scalar.h | 6 + include/llvm/Transforms/Utils/SSI.h | 102 ++++++++ lib/Transforms/Utils/SSI.cpp | 390 ++++++++++++++++++++++++++++ 4 files changed, 499 insertions(+) create mode 100644 include/llvm/Transforms/Utils/SSI.h create mode 100644 lib/Transforms/Utils/SSI.cpp diff --git a/include/llvm/LinkAllPasses.h b/include/llvm/LinkAllPasses.h index 22d6aeb74f7..e199758f015 100644 --- a/include/llvm/LinkAllPasses.h +++ b/include/llvm/LinkAllPasses.h @@ -129,6 +129,7 @@ namespace { (void) llvm::createPrintFunctionPass("", 0); (void) llvm::createDbgInfoPrinterPass(); (void) llvm::createPartialInliningPass(); + (void) llvm::createSSIPass(); (void)new llvm::IntervalPartition(); (void)new llvm::FindUsedTypes(); diff --git a/include/llvm/Transforms/Scalar.h b/include/llvm/Transforms/Scalar.h index 971baeef910..29cd3e3dc6c 100644 --- a/include/llvm/Transforms/Scalar.h +++ b/include/llvm/Transforms/Scalar.h @@ -337,6 +337,12 @@ FunctionPass *createCodeGenPreparePass(const TargetLowering *TLI = 0); FunctionPass *createInstructionNamerPass(); extern const PassInfo *const InstructionNamerID; +//===----------------------------------------------------------------------===// +// +// SSI - This pass converts to Static Single Information form. +// +FunctionPass *createSSIPass(); + } // End llvm namespace #endif diff --git a/include/llvm/Transforms/Utils/SSI.h b/include/llvm/Transforms/Utils/SSI.h new file mode 100644 index 00000000000..59dd6d026ce --- /dev/null +++ b/include/llvm/Transforms/Utils/SSI.h @@ -0,0 +1,102 @@ +//===------------------- SSI.h - Creates SSI Representation -----*- C++ -*-===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_UTILS_SSI_H +#define LLVM_TRANSFORMS_UTILS_SSI_H + +#include "llvm/Pass.h" +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" + +namespace llvm { + + class DominatorTree; + class PHINode; + class Instruction; + class CmpInst; + + class SSI : public FunctionPass { + public: + static char ID; // Pass identification, replacement for typeid. + SSI() : + FunctionPass(&ID) { + } + + void getAnalysisUsage(AnalysisUsage &AU) const; + + /// runOnMachineFunction - pass entry point + bool runOnFunction(Function&); + + void createSSI(SmallVectorImpl &value); + + private: + // Variables always live + DominatorTree *DT_; + + // Stores variables created by SSI + SmallPtrSet created; + + // These variables are only live for each creation + unsigned num_values; + + // Has a bit for each variable, true if it needs to be created + // and false otherwise + BitVector needConstruction; + + // Phis created by SSI + DenseMap phis; + + // Sigmas created by SSI + DenseMap sigmas; + + // Phi nodes that have a phi as operand and has to be fixed + SmallPtrSet phisToFix; + + // List of definition points for every variable + SmallVector, 0> defsites; + + // Basic Block of the original definition of each variable + SmallVector value_original; + + // Stack of last seen definition of a variable + SmallVector, 0> value_stack; + + void insertSigmaFunctions(SmallVectorImpl &value); + void insertPhiFunctions(SmallVectorImpl &value); + void renameInit(SmallVectorImpl &value); + void rename(BasicBlock *BB); + + void substituteUse(Instruction *I); + bool dominateAny(BasicBlock *BB, Instruction *value); + void fixPhis(); + + unsigned getPositionPhi(PHINode *PN); + unsigned getPositionSigma(PHINode *PN); + + unsigned isUsedInTerminator(CmpInst *CI); + + void init(SmallVectorImpl &value); + void clean(); + }; +} // end namespace +#endif diff --git a/lib/Transforms/Utils/SSI.cpp b/lib/Transforms/Utils/SSI.cpp new file mode 100644 index 00000000000..4c4dd37ddf7 --- /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(); + AU.addRequired(); + AU.setPreservesAll(); +} + +bool SSI::runOnFunction(Function &F) { + DT_ = &getAnalysis(); + 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 &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 &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(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 &value) { + DominanceFrontier *DF = &getAnalysis(); + for (unsigned i = 0; i < num_values; ++i) { + // Test if there were any sigmas for this variable + if (needConstruction[i]) { + + SmallPtrSet 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::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 &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(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(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 *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(I); + PHINode *PN_vs = dyn_cast(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(*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::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(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::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::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 &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 X("ssi", "Static Single Information Construction"); + -- 2.34.1