include/llvm/Transforms/Utils/SSI.h

   1 //===------------------- SSI.h - Creates SSI Representation -----*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass converts a list of variables to the Static Single Information
  11 // form. This is a program representation described by Scott Ananian in his
  12 // Master Thesis: "The Static Single Information Form (1999)".
  13 // We are building an on-demand representation, that is, we do not convert
  14 // every single variable in the target function to SSI form. Rather, we receive
  15 // a list of target variables that must be converted. We also do not
  16 // completely convert a target variable to the SSI format. Instead, we only
  17 // change the variable in the points where new information can be attached
  18 // to its live range, that is, at branch points.
  19 //
  20 //===----------------------------------------------------------------------===//
  21
  22 #ifndef LLVM_TRANSFORMS_UTILS_SSI_H
  23 #define LLVM_TRANSFORMS_UTILS_SSI_H
  24
  25 #include "llvm/InstrTypes.h"
  26 #include "llvm/Pass.h"
  27 #include "llvm/ADT/DenseMap.h"
  28 #include "llvm/ADT/SmallPtrSet.h"
  29 #include "llvm/ADT/SmallVector.h"
  30
  31 namespace llvm {
  32
  33   class DominatorTree;
  34   class PHINode;
  35   class Instruction;
  36   class CmpInst;
  37
  38   class SSI : public FunctionPass {
  39     public:
  40       static char ID; // Pass identification, replacement for typeid.
  41       SSI() :
  42         FunctionPass(&ID) {
  43       }
  44
  45       void getAnalysisUsage(AnalysisUsage &AU) const;
  46
  47       bool runOnFunction(Function&);
  48
  49       void createSSI(SmallVectorImpl<Instruction *> &value);
  50
  51     private:
  52       // Variables always live
  53       DominatorTree *DT_;
  54
  55       // Stores variables created by SSI
  56       SmallPtrSet<Instruction *, 16> created;
  57
  58       // Phis created by SSI
  59       DenseMap<PHINode *, Instruction*> phis;
  60
  61       // Sigmas created by SSI
  62       DenseMap<PHINode *, Instruction*> sigmas;
  63
  64       // Phi nodes that have a phi as operand and has to be fixed
  65       SmallPtrSet<PHINode *, 1> phisToFix;
  66
  67       // List of definition points for every variable
  68       DenseMap<Instruction*, SmallVector<BasicBlock*, 4> > defsites;
  69
  70       // Basic Block of the original definition of each variable
  71       DenseMap<Instruction*, BasicBlock*> value_original;
  72
  73       // Stack of last seen definition of a variable
  74       DenseMap<Instruction*, SmallVector<Instruction *, 1> > value_stack;
  75
  76       void insertSigmaFunctions(SmallPtrSet<Instruction*, 4> &value);
  77       void insertSigma(TerminatorInst *TI, Instruction *I);
  78       void insertPhiFunctions(SmallPtrSet<Instruction*, 4> &value);
  79       void renameInit(SmallPtrSet<Instruction*, 4> &value);
  80       void rename(BasicBlock *BB);
  81
  82       void substituteUse(Instruction *I);
  83       bool dominateAny(BasicBlock *BB, Instruction *value);
  84       void fixPhis();
  85
  86       Instruction* getPositionPhi(PHINode *PN);
  87       Instruction* getPositionSigma(PHINode *PN);
  88
  89       void init(SmallVectorImpl<Instruction *> &value);
  90       void clean();
  91   };
  92 } // end namespace
  93 #endif