LLVM API Documentation

SSI.h

Go to the documentation of this file.
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