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 bool runOnFunction(Function&);
49 void createSSI(SmallVectorImpl<Instruction *> &value);
52 // Variables always live
55 // Stores variables created by SSI
56 SmallPtrSet<Instruction *, 16> created;
58 // These variables are only live for each creation
61 // Has a bit for each variable, true if it needs to be created
62 // and false otherwise
63 BitVector needConstruction;
65 // Phis created by SSI
66 DenseMap<PHINode *, unsigned> phis;
68 // Sigmas created by SSI
69 DenseMap<PHINode *, unsigned> sigmas;
71 // Phi nodes that have a phi as operand and has to be fixed
72 SmallPtrSet<PHINode *, 1> phisToFix;
74 // List of definition points for every variable
75 SmallVector<SmallVector<BasicBlock *, 1>, 0> defsites;
77 // Basic Block of the original definition of each variable
78 SmallVector<BasicBlock *, 0> value_original;
80 // Stack of last seen definition of a variable
81 SmallVector<SmallVector<Instruction *, 1>, 0> value_stack;
83 void insertSigmaFunctions(SmallVectorImpl<Instruction *> &value);
84 void insertPhiFunctions(SmallVectorImpl<Instruction *> &value);
85 void renameInit(SmallVectorImpl<Instruction *> &value);
86 void rename(BasicBlock *BB);
88 void substituteUse(Instruction *I);
89 bool dominateAny(BasicBlock *BB, Instruction *value);
92 unsigned getPositionPhi(PHINode *PN);
93 unsigned getPositionSigma(PHINode *PN);
95 unsigned isUsedInTerminator(CmpInst *CI);
97 void init(SmallVectorImpl<Instruction *> &value);