1 //===------------------- SSI.h - Creates SSI Representation -----*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
20 //===----------------------------------------------------------------------===//
22 #ifndef LLVM_TRANSFORMS_UTILS_SSI_H
23 #define LLVM_TRANSFORMS_UTILS_SSI_H
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"
38 class SSI : public FunctionPass {
40 static char ID; // Pass identification, replacement for typeid.
45 void getAnalysisUsage(AnalysisUsage &AU) const;
47 /// runOnMachineFunction - pass entry point
48 bool runOnFunction(Function&);
50 void createSSI(SmallVectorImpl<Instruction *> &value);
53 // Variables always live
56 // Stores variables created by SSI
57 SmallPtrSet<Instruction *, 16> created;
59 // These variables are only live for each creation
62 // Has a bit for each variable, true if it needs to be created
63 // and false otherwise
64 BitVector needConstruction;
66 // Phis created by SSI
67 DenseMap<PHINode *, unsigned> phis;
69 // Sigmas created by SSI
70 DenseMap<PHINode *, unsigned> sigmas;
72 // Phi nodes that have a phi as operand and has to be fixed
73 SmallPtrSet<PHINode *, 1> phisToFix;
75 // List of definition points for every variable
76 SmallVector<SmallVector<BasicBlock *, 1>, 0> defsites;
78 // Basic Block of the original definition of each variable
79 SmallVector<BasicBlock *, 0> value_original;
81 // Stack of last seen definition of a variable
82 SmallVector<SmallVector<Instruction *, 1>, 0> value_stack;
84 void insertSigmaFunctions(SmallVectorImpl<Instruction *> &value);
85 void insertPhiFunctions(SmallVectorImpl<Instruction *> &value);
86 void renameInit(SmallVectorImpl<Instruction *> &value);
87 void rename(BasicBlock *BB);
89 void substituteUse(Instruction *I);
90 bool dominateAny(BasicBlock *BB, Instruction *value);
93 unsigned getPositionPhi(PHINode *PN);
94 unsigned getPositionSigma(PHINode *PN);
96 unsigned isUsedInTerminator(CmpInst *CI);
98 void init(SmallVectorImpl<Instruction *> &value);