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