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/Pass.h"
  26 #include "llvm/ADT/BitVector.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       /// runOnMachineFunction - pass entry point
  48       bool runOnFunction(Function&);
  49
  50       void createSSI(SmallVectorImpl<Instruction *> &value);
  51
  52     private:
  53       // Variables always live
  54       DominatorTree *DT_;
  55
  56       // Stores variables created by SSI
  57       SmallPtrSet<Instruction *, 16> created;
  58
  59       // These variables are only live for each creation
  60       unsigned num_values;
  61
  62       // Has a bit for each variable, true if it needs to be created
  63       // and false otherwise
  64       BitVector needConstruction;
  65
  66       // Phis created by SSI
  67       DenseMap<PHINode *, unsigned> phis;
  68
  69       // Sigmas created by SSI
  70       DenseMap<PHINode *, unsigned> sigmas;
  71
  72       // Phi nodes that have a phi as operand and has to be fixed
  73       SmallPtrSet<PHINode *, 1> phisToFix;
  74
  75       // List of definition points for every variable
  76       SmallVector<SmallVector<BasicBlock *, 1>, 0> defsites;
  77
  78       // Basic Block of the original definition of each variable
  79       SmallVector<BasicBlock *, 0> value_original;
  80
  81       // Stack of last seen definition of a variable
  82       SmallVector<SmallVector<Instruction *, 1>, 0> value_stack;
  83
  84       void insertSigmaFunctions(SmallVectorImpl<Instruction *> &value);
  85       void insertPhiFunctions(SmallVectorImpl<Instruction *> &value);
  86       void renameInit(SmallVectorImpl<Instruction *> &value);
  87       void rename(BasicBlock *BB);
  88
  89       void substituteUse(Instruction *I);
  90       bool dominateAny(BasicBlock *BB, Instruction *value);
  91       void fixPhis();
  92
  93       unsigned getPositionPhi(PHINode *PN);
  94       unsigned getPositionSigma(PHINode *PN);
  95
  96       unsigned isUsedInTerminator(CmpInst *CI);
  97
  98       void init(SmallVectorImpl<Instruction *> &value);
  99       void clean();
 100   };
 101 } // end namespace
 102 #endif