1 files changed, 190 insertions, 0 deletions
diff --git a/contrib/llvm/lib/Transforms/IPO/PartialSpecialization.cpp b/contrib/llvm/lib/Transforms/IPO/PartialSpecialization.cpp
new file mode 100644
index 0000000..084b94e
--- /dev/null
+++ b/contrib/llvm/lib/Transforms/IPO/PartialSpecialization.cpp
@@ -0,0 +1,190 @@
+//===-- PartialSpecialization.cpp - Specialize for common constants--------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass finds function arguments that are often a common constant and 
+// specializes a version of the called function for that constant.
+//
+// This pass simply does the cloning for functions it specializes.  It depends
+// on IPSCCP and DAE to clean up the results.
+//
+// The initial heuristic favors constant arguments that are used in control 
+// flow.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "partialspecialization"
+#include "llvm/Transforms/IPO.h"
+#include "llvm/Constant.h"
+#include "llvm/Instructions.h"
+#include "llvm/Module.h"
+#include "llvm/Pass.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+#include "llvm/Support/CallSite.h"
+#include "llvm/ADT/DenseSet.h"
+#include <map>
+using namespace llvm;
+
+STATISTIC(numSpecialized, "Number of specialized functions created");
+
+// Call must be used at least occasionally
+static const int CallsMin = 5;
+
+// Must have 10% of calls having the same constant to specialize on
+static const double ConstValPercent = .1;
+
+namespace {
+  class PartSpec : public ModulePass {
+    void scanForInterest(Function&, SmallVector<int, 6>&);
+    int scanDistribution(Function&, int, std::map<Constant*, int>&);
+  public :
+    static char ID; // Pass identification, replacement for typeid
+    PartSpec() : ModulePass(&ID) {}
+    bool runOnModule(Module &M);
+  };
+}
+
+char PartSpec::ID = 0;
+static RegisterPass<PartSpec>
+X("partialspecialization", "Partial Specialization");
+
+// Specialize F by replacing the arguments (keys) in replacements with the 
+// constants (values).  Replace all calls to F with those constants with
+// a call to the specialized function.  Returns the specialized function
+static Function* 
+SpecializeFunction(Function* F, 
+                   DenseMap<const Value*, Value*>& replacements) {
+  // arg numbers of deleted arguments
+  DenseSet<unsigned> deleted;
+  for (DenseMap<const Value*, Value*>::iterator 
+         repb = replacements.begin(), repe = replacements.end();
+       repb != repe; ++repb)
+    deleted.insert(cast<Argument>(repb->first)->getArgNo());
+
+  Function* NF = CloneFunction(F, replacements);
+  NF->setLinkage(GlobalValue::InternalLinkage);
+  F->getParent()->getFunctionList().push_back(NF);
+
+  for (Value::use_iterator ii = F->use_begin(), ee = F->use_end(); 
+       ii != ee; ) {
+    Value::use_iterator i = ii;
+    ++ii;
+    if (isa<CallInst>(i) || isa<InvokeInst>(i)) {
+      CallSite CS(cast<Instruction>(i));
+      if (CS.getCalledFunction() == F) {
+        
+        SmallVector<Value*, 6> args;
+        for (unsigned x = 0; x < CS.arg_size(); ++x)
+          if (!deleted.count(x))
+            args.push_back(CS.getArgument(x));
+        Value* NCall;
+        if (CallInst *CI = dyn_cast<CallInst>(i)) {
+          NCall = CallInst::Create(NF, args.begin(), args.end(), 
+                                   CI->getName(), CI);
+          cast<CallInst>(NCall)->setTailCall(CI->isTailCall());
+          cast<CallInst>(NCall)->setCallingConv(CI->getCallingConv());
+        } else {
+          InvokeInst *II = cast<InvokeInst>(i);
+          NCall = InvokeInst::Create(NF, II->getNormalDest(),
+                                     II->getUnwindDest(),
+                                     args.begin(), args.end(), 
+                                     II->getName(), II);
+          cast<InvokeInst>(NCall)->setCallingConv(II->getCallingConv());
+        }
+        CS.getInstruction()->replaceAllUsesWith(NCall);
+        CS.getInstruction()->eraseFromParent();
+      }
+    }
+  }
+  return NF;
+}
+
+
+bool PartSpec::runOnModule(Module &M) {
+  bool Changed = false;
+  for (Module::iterator I = M.begin(); I != M.end(); ++I) {
+    Function &F = *I;
+    if (F.isDeclaration() || F.mayBeOverridden()) continue;
+    SmallVector<int, 6> interestingArgs;
+    scanForInterest(F, interestingArgs);
+
+    // Find the first interesting Argument that we can specialize on
+    // If there are multiple interesting Arguments, then those will be found
+    // when processing the cloned function.
+    bool breakOuter = false;
+    for (unsigned int x = 0; !breakOuter && x < interestingArgs.size(); ++x) {
+      std::map<Constant*, int> distribution;
+      int total = scanDistribution(F, interestingArgs[x], distribution);
+      if (total > CallsMin) 
+        for (std::map<Constant*, int>::iterator ii = distribution.begin(),
+               ee = distribution.end(); ii != ee; ++ii)
+          if (total > ii->second && ii->first &&
+               ii->second > total * ConstValPercent) {
+            DenseMap<const Value*, Value*> m;
+            Function::arg_iterator arg = F.arg_begin();
+            for (int y = 0; y < interestingArgs[x]; ++y)
+              ++arg;
+            m[&*arg] = ii->first;
+            SpecializeFunction(&F, m);
+            ++numSpecialized;
+            breakOuter = true;
+            Changed = true;
+          }
+    }
+  }
+  return Changed;
+}
+
+/// scanForInterest - This function decides which arguments would be worth
+/// specializing on.
+void PartSpec::scanForInterest(Function& F, SmallVector<int, 6>& args) {
+  for(Function::arg_iterator ii = F.arg_begin(), ee = F.arg_end();
+      ii != ee; ++ii) {
+    for(Value::use_iterator ui = ii->use_begin(), ue = ii->use_end();
+        ui != ue; ++ui) {
+
+      bool interesting = false;
+
+      if (isa<CmpInst>(ui)) interesting = true;
+      else if (isa<CallInst>(ui))
+        interesting = ui->getOperand(0) == ii;
+      else if (isa<InvokeInst>(ui))
+        interesting = ui->getOperand(0) == ii;
+      else if (isa<SwitchInst>(ui)) interesting = true;
+      else if (isa<BranchInst>(ui)) interesting = true;
+
+      if (interesting) {
+        args.push_back(std::distance(F.arg_begin(), ii));
+        break;
+      }
+    }
+  }
+}
+
+/// scanDistribution - Construct a histogram of constants for arg of F at arg.
+int PartSpec::scanDistribution(Function& F, int arg, 
+                               std::map<Constant*, int>& dist) {
+  bool hasIndirect = false;
+  int total = 0;
+  for(Value::use_iterator ii = F.use_begin(), ee = F.use_end();
+      ii != ee; ++ii)
+    if ((isa<CallInst>(ii) || isa<InvokeInst>(ii))
+        && ii->getOperand(0) == &F) {
+      ++dist[dyn_cast<Constant>(ii->getOperand(arg + 1))];
+      ++total;
+    } else
+      hasIndirect = true;
+
+  // Preserve the original address taken function even if all other uses
+  // will be specialized.
+  if (hasIndirect) ++total;
+  return total;
+}
+
+ModulePass* llvm::createPartialSpecializationPass() { return new PartSpec(); }