Add Static Single Information construction pass written by André Tavares!

Use it by requiring it through the pass manager, then calling its createSSI
method on the variables that you want in SSI form.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@74780 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 108 insertions, 0 deletions

diff --git a/include/llvm/Transforms/Scalar.h b/include/llvm/Transforms/Scalar.h
index 971baee..29cd3e3 100644
--- a/include/llvm/Transforms/Scalar.h
+++ b/include/llvm/Transforms/Scalar.h
@@ -337,6 +337,12 @@ FunctionPass *createCodeGenPreparePass(const TargetLowering *TLI = 0);
 FunctionPass *createInstructionNamerPass();
 extern const PassInfo *const InstructionNamerID;
   
+//===----------------------------------------------------------------------===//
+//
+// SSI - This pass converts to Static Single Information form.
+//
+FunctionPass *createSSIPass();
+
 } // End llvm namespace
 
 #endif
diff --git a/include/llvm/Transforms/Utils/SSI.h b/include/llvm/Transforms/Utils/SSI.h
new file mode 100644
index 0000000..59dd6d0
--- /dev/null
+++ b/include/llvm/Transforms/Utils/SSI.h
@@ -0,0 +1,102 @@
+//===------------------- SSI.h - Creates SSI Representation -----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass converts a list of variables to the Static Single Information
+// form. This is a program representation described by Scott Ananian in his
+// Master Thesis: "The Static Single Information Form (1999)".
+// We are building an on-demand representation, that is, we do not convert
+// every single variable in the target function to SSI form. Rather, we receive
+// a list of target variables that must be converted. We also do not
+// completely convert a target variable to the SSI format. Instead, we only
+// change the variable in the points where new information can be attached
+// to its live range, that is, at branch points.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_SSI_H
+#define LLVM_TRANSFORMS_UTILS_SSI_H
+
+#include "llvm/Pass.h"
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+
+namespace llvm {
+
+  class DominatorTree;
+  class PHINode;
+  class Instruction;
+  class CmpInst;
+
+  class SSI : public FunctionPass {
+    public:
+      static char ID; // Pass identification, replacement for typeid.
+      SSI() :
+        FunctionPass(&ID) {
+      }
+
+      void getAnalysisUsage(AnalysisUsage &AU) const;
+
+      /// runOnMachineFunction - pass entry point
+      bool runOnFunction(Function&);
+
+      void createSSI(SmallVectorImpl<Instruction *> &value);
+
+    private:
+      // Variables always live
+      DominatorTree *DT_;
+
+      // Stores variables created by SSI
+      SmallPtrSet<Instruction *, 16> created;
+
+      // These variables are only live for each creation
+      unsigned num_values;
+
+      // Has a bit for each variable, true if it needs to be created
+      // and false otherwise
+      BitVector needConstruction;
+
+      // Phis created by SSI
+      DenseMap<PHINode *, unsigned> phis;
+
+      // Sigmas created by SSI
+      DenseMap<PHINode *, unsigned> sigmas;
+
+      // Phi nodes that have a phi as operand and has to be fixed
+      SmallPtrSet<PHINode *, 1> phisToFix;
+
+      // List of definition points for every variable
+      SmallVector<SmallVector<BasicBlock *, 1>, 0> defsites;
+
+      // Basic Block of the original definition of each variable
+      SmallVector<BasicBlock *, 0> value_original;
+
+      // Stack of last seen definition of a variable
+      SmallVector<SmallVector<Instruction *, 1>, 0> value_stack;
+
+      void insertSigmaFunctions(SmallVectorImpl<Instruction *> &value);
+      void insertPhiFunctions(SmallVectorImpl<Instruction *> &value);
+      void renameInit(SmallVectorImpl<Instruction *> &value);
+      void rename(BasicBlock *BB);
+
+      void substituteUse(Instruction *I);
+      bool dominateAny(BasicBlock *BB, Instruction *value);
+      void fixPhis();
+
+      unsigned getPositionPhi(PHINode *PN);
+      unsigned getPositionSigma(PHINode *PN);
+
+      unsigned isUsedInTerminator(CmpInst *CI);
+
+      void init(SmallVectorImpl<Instruction *> &value);
+      void clean();
+  };
+} // end namespace
+#endif