LLVM API Documentation
00001 //===------------------- SSI.h - Creates SSI Representation -----*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This pass converts a list of variables to the Static Single Information 00011 // form. This is a program representation described by Scott Ananian in his 00012 // Master Thesis: "The Static Single Information Form (1999)". 00013 // We are building an on-demand representation, that is, we do not convert 00014 // every single variable in the target function to SSI form. Rather, we receive 00015 // a list of target variables that must be converted. We also do not 00016 // completely convert a target variable to the SSI format. Instead, we only 00017 // change the variable in the points where new information can be attached 00018 // to its live range, that is, at branch points. 00019 // 00020 //===----------------------------------------------------------------------===// 00021 00022 #ifndef LLVM_TRANSFORMS_UTILS_SSI_H 00023 #define LLVM_TRANSFORMS_UTILS_SSI_H 00024 00025 #include "llvm/Pass.h" 00026 #include "llvm/ADT/BitVector.h" 00027 #include "llvm/ADT/DenseMap.h" 00028 #include "llvm/ADT/SmallPtrSet.h" 00029 #include "llvm/ADT/SmallVector.h" 00030 00031 namespace llvm { 00032 00033 class DominatorTree; 00034 class PHINode; 00035 class Instruction; 00036 class CmpInst; 00037 00038 class SSI : public FunctionPass { 00039 public: 00040 static char ID; // Pass identification, replacement for typeid. 00041 SSI() : 00042 FunctionPass(&ID) { 00043 } 00044 00045 void getAnalysisUsage(AnalysisUsage &AU) const; 00046 00047 bool runOnFunction(Function&); 00048 00049 void createSSI(SmallVectorImpl<Instruction *> &value); 00050 00051 private: 00052 // Variables always live 00053 DominatorTree *DT_; 00054 00055 // Stores variables created by SSI 00056 SmallPtrSet<Instruction *, 16> created; 00057 00058 // These variables are only live for each creation 00059 unsigned num_values; 00060 00061 // Has a bit for each variable, true if it needs to be created 00062 // and false otherwise 00063 BitVector needConstruction; 00064 00065 // Phis created by SSI 00066 DenseMap<PHINode *, unsigned> phis; 00067 00068 // Sigmas created by SSI 00069 DenseMap<PHINode *, unsigned> sigmas; 00070 00071 // Phi nodes that have a phi as operand and has to be fixed 00072 SmallPtrSet<PHINode *, 1> phisToFix; 00073 00074 // List of definition points for every variable 00075 SmallVector<SmallVector<BasicBlock *, 1>, 0> defsites; 00076 00077 // Basic Block of the original definition of each variable 00078 SmallVector<BasicBlock *, 0> value_original; 00079 00080 // Stack of last seen definition of a variable 00081 SmallVector<SmallVector<Instruction *, 1>, 0> value_stack; 00082 00083 void insertSigmaFunctions(SmallVectorImpl<Instruction *> &value); 00084 void insertPhiFunctions(SmallVectorImpl<Instruction *> &value); 00085 void renameInit(SmallVectorImpl<Instruction *> &value); 00086 void rename(BasicBlock *BB); 00087 00088 void substituteUse(Instruction *I); 00089 bool dominateAny(BasicBlock *BB, Instruction *value); 00090 void fixPhis(); 00091 00092 unsigned getPositionPhi(PHINode *PN); 00093 unsigned getPositionSigma(PHINode *PN); 00094 00095 unsigned isUsedInTerminator(CmpInst *CI); 00096 00097 void init(SmallVectorImpl<Instruction *> &value); 00098 void clean(); 00099 }; 00100 } // end namespace 00101 #endif