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");
35 STATISTIC(numReplaced
, "Number of callers replaced by specialization");
37 // Maximum number of arguments markable interested
38 static const int MaxInterests
= 6;
40 // Call must be used at least occasionally
41 static const int CallsMin
= 5;
43 // Must have 10% of calls having the same constant to specialize on
44 static const double ConstValPercent
= .1;
47 typedef SmallVector
<int, MaxInterests
> InterestingArgVector
;
48 class PartSpec
: public ModulePass
{
49 void scanForInterest(Function
&, InterestingArgVector
&);
50 int scanDistribution(Function
&, int, std::map
<Constant
*, int>&);
52 static char ID
; // Pass identification, replacement for typeid
53 PartSpec() : ModulePass(ID
) {}
54 bool runOnModule(Module
&M
);
58 char PartSpec::ID
= 0;
59 INITIALIZE_PASS(PartSpec
, "partialspecialization",
60 "Partial Specialization", false, false);
62 // Specialize F by replacing the arguments (keys) in replacements with the
63 // constants (values). Replace all calls to F with those constants with
64 // a call to the specialized function. Returns the specialized function
66 SpecializeFunction(Function
* F
,
67 ValueMap
<const Value
*, Value
*>& replacements
) {
68 // arg numbers of deleted arguments
69 DenseMap
<unsigned, const Argument
*> deleted
;
70 for (ValueMap
<const Value
*, Value
*>::iterator
71 repb
= replacements
.begin(), repe
= replacements
.end();
72 repb
!= repe
; ++repb
) {
73 Argument
const *arg
= cast
<const Argument
>(repb
->first
);
74 deleted
[arg
->getArgNo()] = arg
;
77 Function
* NF
= CloneFunction(F
, replacements
);
78 NF
->setLinkage(GlobalValue::InternalLinkage
);
79 F
->getParent()->getFunctionList().push_back(NF
);
81 for (Value::use_iterator ii
= F
->use_begin(), ee
= F
->use_end();
83 Value::use_iterator i
= ii
;
88 if (CS
.getCalledFunction() == F
) {
89 SmallVector
<Value
*, 6> args
;
90 // Assemble the non-specialized arguments for the updated callsite.
91 // In the process, make sure that the specialized arguments are
92 // constant and match the specialization. If that's not the case,
93 // this callsite needs to call the original or some other
94 // specialization; don't change it here.
95 CallSite::arg_iterator as
= CS
.arg_begin(), ae
= CS
.arg_end();
96 for (CallSite::arg_iterator ai
= as
; ai
!= ae
; ++ai
) {
97 DenseMap
<unsigned, const Argument
*>::iterator delit
= deleted
.find(
98 std::distance(as
, ai
));
99 if (delit
== deleted
.end())
100 args
.push_back(cast
<Value
>(ai
));
102 Constant
*ci
= dyn_cast
<Constant
>(ai
);
103 if (!(ci
&& ci
== replacements
[delit
->second
]))
108 if (CallInst
*CI
= dyn_cast
<CallInst
>(U
)) {
109 NCall
= CallInst::Create(NF
, args
.begin(), args
.end(),
111 cast
<CallInst
>(NCall
)->setTailCall(CI
->isTailCall());
112 cast
<CallInst
>(NCall
)->setCallingConv(CI
->getCallingConv());
114 InvokeInst
*II
= cast
<InvokeInst
>(U
);
115 NCall
= InvokeInst::Create(NF
, II
->getNormalDest(),
117 args
.begin(), args
.end(),
119 cast
<InvokeInst
>(NCall
)->setCallingConv(II
->getCallingConv());
121 CS
.getInstruction()->replaceAllUsesWith(NCall
);
122 CS
.getInstruction()->eraseFromParent();
132 bool PartSpec::runOnModule(Module
&M
) {
133 bool Changed
= false;
134 for (Module::iterator I
= M
.begin(); I
!= M
.end(); ++I
) {
136 if (F
.isDeclaration() || F
.mayBeOverridden()) continue;
137 InterestingArgVector interestingArgs
;
138 scanForInterest(F
, interestingArgs
);
140 // Find the first interesting Argument that we can specialize on
141 // If there are multiple interesting Arguments, then those will be found
142 // when processing the cloned function.
143 bool breakOuter
= false;
144 for (unsigned int x
= 0; !breakOuter
&& x
< interestingArgs
.size(); ++x
) {
145 std::map
<Constant
*, int> distribution
;
146 int total
= scanDistribution(F
, interestingArgs
[x
], distribution
);
147 if (total
> CallsMin
)
148 for (std::map
<Constant
*, int>::iterator ii
= distribution
.begin(),
149 ee
= distribution
.end(); ii
!= ee
; ++ii
)
150 if (total
> ii
->second
&& ii
->first
&&
151 ii
->second
> total
* ConstValPercent
) {
152 ValueMap
<const Value
*, Value
*> m
;
153 Function::arg_iterator arg
= F
.arg_begin();
154 for (int y
= 0; y
< interestingArgs
[x
]; ++y
)
156 m
[&*arg
] = ii
->first
;
157 SpecializeFunction(&F
, m
);
167 /// scanForInterest - This function decides which arguments would be worth
169 void PartSpec::scanForInterest(Function
& F
, InterestingArgVector
& args
) {
170 for(Function::arg_iterator ii
= F
.arg_begin(), ee
= F
.arg_end();
172 for(Value::use_iterator ui
= ii
->use_begin(), ue
= ii
->use_end();
175 bool interesting
= false;
177 if (isa
<CmpInst
>(U
)) interesting
= true;
178 else if (isa
<CallInst
>(U
))
179 interesting
= ui
->getOperand(0) == ii
;
180 else if (isa
<InvokeInst
>(U
))
181 interesting
= ui
->getOperand(0) == ii
;
182 else if (isa
<SwitchInst
>(U
)) interesting
= true;
183 else if (isa
<BranchInst
>(U
)) interesting
= true;
186 args
.push_back(std::distance(F
.arg_begin(), ii
));
193 /// scanDistribution - Construct a histogram of constants for arg of F at arg.
194 int PartSpec::scanDistribution(Function
& F
, int arg
,
195 std::map
<Constant
*, int>& dist
) {
196 bool hasIndirect
= false;
198 for (Value::use_iterator ii
= F
.use_begin(), ee
= F
.use_end();
202 if (CS
&& CS
.getCalledFunction() == &F
) {
203 ++dist
[dyn_cast
<Constant
>(CS
.getArgument(arg
))];
209 // Preserve the original address taken function even if all other uses
210 // will be specialized.
211 if (hasIndirect
) ++total
;
215 ModulePass
* llvm::createPartialSpecializationPass() { return new PartSpec(); }