4 files changed, 116 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/Cloning.h b/include/llvm/Transforms/Utils/Cloning.h
index 1e2bbaa..840d970 100644
--- a/include/llvm/Transforms/Utils/Cloning.h
+++ b/include/llvm/Transforms/Utils/Cloning.h
@@ -37,6 +37,7 @@ class Trace;
 class CallGraph;
 class TargetData;
 class LoopInfo;
+class LLVMContext;
 template<class N> class LoopBase;
 typedef LoopBase<BasicBlock> Loop;
 
diff --git a/include/llvm/Transforms/Utils/Local.h b/include/llvm/Transforms/Utils/Local.h
index 98a68f6..dd423fa 100644
--- a/include/llvm/Transforms/Utils/Local.h
+++ b/include/llvm/Transforms/Utils/Local.h
@@ -19,6 +19,7 @@ namespace llvm {
 
 class User;
 class BasicBlock;
+class BranchInst;
 class Instruction;
 class Value;
 class Pass;
@@ -94,6 +95,12 @@ void MergeBasicBlockIntoOnlyPred(BasicBlock *BB);
 ///
 bool SimplifyCFG(BasicBlock *BB);
 
+/// FoldBranchToCommonDest - If this basic block is ONLY a setcc and a branch,
+/// and if a predecessor branches to us and one of our successors, fold the
+/// setcc into the predecessor and use logical operations to pick the right
+/// destination.
+bool FoldBranchToCommonDest(BranchInst *BI);
+
 /// DemoteRegToStack - This function takes a virtual register computed by an
 /// Instruction and replaces it with a slot in the stack frame, allocated via
 /// alloca.  This allows the CFG to be changed around without fear of
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