1 //===-- PartialSpecialization.cpp - Specialize for common constants--------===//
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 finds function arguments that are often a common constant and
11 // specializes a version of the called function for that constant.
13 // This pass simply does the cloning for functions it specializes. It depends
14 // on IPSCCP and DAE to clean up the results.
16 // The initial heuristic favors constant arguments that are used in control
19 //===----------------------------------------------------------------------===//
21 #define DEBUG_TYPE "partialspecialization"
22 #include "llvm/Transforms/IPO.h"
23 #include "llvm/Constant.h"
24 #include "llvm/Instructions.h"
25 #include "llvm/Module.h"
26 #include "llvm/Pass.h"
27 #include "llvm/ADT/Statistic.h"
28 #include "llvm/Transforms/Utils/Cloning.h"
29 #include "llvm/Support/CallSite.h"
30 #include "llvm/ADT/DenseSet.h"
34 STATISTIC(numSpecialized
, "Number of specialized functions created");
36 // Call must be used at least occasionally
37 static const int CallsMin
= 5;
39 // Must have 10% of calls having the same constant to specialize on
40 static const double ConstValPercent
= .1;
43 class PartSpec
: public ModulePass
{
44 void scanForInterest(Function
&, SmallVector
<int, 6>&);
45 int scanDistribution(Function
&, int, std::map
<Constant
*, int>&);
47 static char ID
; // Pass identification, replacement for typeid
48 PartSpec() : ModulePass(&ID
) {}
49 bool runOnModule(Module
&M
);
53 char PartSpec::ID
= 0;
54 static RegisterPass
<PartSpec
>
55 X("partialspecialization", "Partial Specialization");
57 // Specialize F by replacing the arguments (keys) in replacements with the
58 // constants (values). Replace all calls to F with those constants with
59 // a call to the specialized function. Returns the specialized function
61 SpecializeFunction(Function
* F
,
62 DenseMap
<const Value
*, Value
*>& replacements
) {
63 // arg numbers of deleted arguments
64 DenseSet
<unsigned> deleted
;
65 for (DenseMap
<const Value
*, Value
*>::iterator
66 repb
= replacements
.begin(), repe
= replacements
.end();
68 deleted
.insert(cast
<Argument
>(repb
->first
)->getArgNo());
70 Function
* NF
= CloneFunction(F
, replacements
);
71 NF
->setLinkage(GlobalValue::InternalLinkage
);
72 F
->getParent()->getFunctionList().push_back(NF
);
74 for (Value::use_iterator ii
= F
->use_begin(), ee
= F
->use_end();
76 Value::use_iterator i
= ii
;
78 if (isa
<CallInst
>(i
) || isa
<InvokeInst
>(i
)) {
79 CallSite
CS(cast
<Instruction
>(i
));
80 if (CS
.getCalledFunction() == F
) {
82 SmallVector
<Value
*, 6> args
;
83 for (unsigned x
= 0; x
< CS
.arg_size(); ++x
)
84 if (!deleted
.count(x
))
85 args
.push_back(CS
.getArgument(x
));
87 if (CallInst
*CI
= dyn_cast
<CallInst
>(i
)) {
88 NCall
= CallInst::Create(NF
, args
.begin(), args
.end(),
90 cast
<CallInst
>(NCall
)->setTailCall(CI
->isTailCall());
91 cast
<CallInst
>(NCall
)->setCallingConv(CI
->getCallingConv());
93 InvokeInst
*II
= cast
<InvokeInst
>(i
);
94 NCall
= InvokeInst::Create(NF
, II
->getNormalDest(),
96 args
.begin(), args
.end(),
98 cast
<InvokeInst
>(NCall
)->setCallingConv(II
->getCallingConv());
100 CS
.getInstruction()->replaceAllUsesWith(NCall
);
101 CS
.getInstruction()->eraseFromParent();
109 bool PartSpec::runOnModule(Module
&M
) {
110 bool Changed
= false;
111 for (Module::iterator I
= M
.begin(); I
!= M
.end(); ++I
) {
113 if (F
.isDeclaration() || F
.mayBeOverridden()) continue;
114 SmallVector
<int, 6> interestingArgs
;
115 scanForInterest(F
, interestingArgs
);
117 // Find the first interesting Argument that we can specialize on
118 // If there are multiple interesting Arguments, then those will be found
119 // when processing the cloned function.
120 bool breakOuter
= false;
121 for (unsigned int x
= 0; !breakOuter
&& x
< interestingArgs
.size(); ++x
) {
122 std::map
<Constant
*, int> distribution
;
123 int total
= scanDistribution(F
, interestingArgs
[x
], distribution
);
124 if (total
> CallsMin
)
125 for (std::map
<Constant
*, int>::iterator ii
= distribution
.begin(),
126 ee
= distribution
.end(); ii
!= ee
; ++ii
)
127 if (total
> ii
->second
&& ii
->first
&&
128 ii
->second
> total
* ConstValPercent
) {
129 DenseMap
<const Value
*, Value
*> m
;
130 Function::arg_iterator arg
= F
.arg_begin();
131 for (int y
= 0; y
< interestingArgs
[x
]; ++y
)
133 m
[&*arg
] = ii
->first
;
134 SpecializeFunction(&F
, m
);
144 /// scanForInterest - This function decides which arguments would be worth
146 void PartSpec::scanForInterest(Function
& F
, SmallVector
<int, 6>& args
) {
147 for(Function::arg_iterator ii
= F
.arg_begin(), ee
= F
.arg_end();
149 for(Value::use_iterator ui
= ii
->use_begin(), ue
= ii
->use_end();
152 bool interesting
= false;
154 if (isa
<CmpInst
>(ui
)) interesting
= true;
155 else if (isa
<CallInst
>(ui
))
156 interesting
= ui
->getOperand(0) == ii
;
157 else if (isa
<InvokeInst
>(ui
))
158 interesting
= ui
->getOperand(0) == ii
;
159 else if (isa
<SwitchInst
>(ui
)) interesting
= true;
160 else if (isa
<BranchInst
>(ui
)) interesting
= true;
163 args
.push_back(std::distance(F
.arg_begin(), ii
));
170 /// scanDistribution - Construct a histogram of constants for arg of F at arg.
171 int PartSpec::scanDistribution(Function
& F
, int arg
,
172 std::map
<Constant
*, int>& dist
) {
173 bool hasIndirect
= false;
175 for(Value::use_iterator ii
= F
.use_begin(), ee
= F
.use_end();
177 if ((isa
<CallInst
>(ii
) || isa
<InvokeInst
>(ii
))
178 && ii
->getOperand(0) == &F
) {
179 ++dist
[dyn_cast
<Constant
>(ii
->getOperand(arg
+ 1))];
184 // Preserve the original address taken function even if all other uses
185 // will be specialized.
186 if (hasIndirect
) ++total
;
190 ModulePass
* llvm::createPartialSpecializationPass() { return new PartSpec(); }