1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "ReduceOperandsToArgs.h"
10#include "Utils.h"
11#include "llvm/ADT/Sequence.h"
12#include "llvm/IR/Constants.h"
13#include "llvm/IR/InstIterator.h"
14#include "llvm/IR/InstrTypes.h"
15#include "llvm/IR/Instructions.h"
16#include "llvm/IR/IntrinsicInst.h"
17#include "llvm/IR/Operator.h"
18#include "llvm/Transforms/Utils/BasicBlockUtils.h"
19#include "llvm/Transforms/Utils/Cloning.h"
20
21using namespace llvm;
22
23static bool canReplaceFunction(const Function &F) {
24 // TODO: Add controls to avoid ABI breaks (e.g. don't break main)
25 return true;
26}
27
28static bool canReduceUse(Use &Op) {
29 Value *Val = Op.get();
30 Type *Ty = Val->getType();
31
32 // Only replace operands that can be passed-by-value.
33 if (!Ty->isFirstClassType())
34 return false;
35
36 // Don't pass labels/metadata as arguments.
37 if (Ty->isLabelTy() || Ty->isMetadataTy() || Ty->isTokenTy() ||
38 Ty->isX86_AMXTy())
39 return false;
40
41 // No need to replace values that are already arguments.
42 if (isa<Argument>(Val))
43 return false;
44
45 // Do not replace literals.
46 if (isa<ConstantData>(Val))
47 return false;
48
49 // Do not convert direct function calls to indirect calls.
50 if (auto *CI = dyn_cast<CallBase>(Val: Op.getUser()))
51 if (&CI->getCalledOperandUse() == &Op)
52 return false;
53
54 // lifetime.start/lifetime.end require alloca argument.
55 if (isa<LifetimeIntrinsic>(Val: Op.getUser()))
56 return false;
57
58 // Landing pad clauses must remain constants.
59 if (isa<LandingPadInst>(Val: Op.getUser()))
60 return false;
61
62 return true;
63}
64
65/// Goes over OldF calls and replaces them with a call to NewF.
66static void replaceFunctionCalls(Function *OldF, Function *NewF) {
67 SmallVector<CallBase *> Callers;
68 for (Use &U : OldF->uses()) {
69 auto *CI = dyn_cast<CallBase>(Val: U.getUser());
70 if (!CI || !CI->isCallee(U: &U)) // RAUW can handle these fine.
71 continue;
72
73 Function *CalledF = CI->getCalledFunction();
74 if (CalledF == OldF) {
75 Callers.push_back(Elt: CI);
76 } else {
77 // The call may have undefined behavior by calling a function with a
78 // mismatched signature. In this case, do not bother adjusting the
79 // callsites to pad with any new arguments.
80
81 // TODO: Better QoI to try to add new arguments to the end, and ignore
82 // existing mismatches.
83 assert(!CalledF && CI->getCalledOperand()->stripPointerCasts() == OldF &&
84 "only expected call and function signature mismatch");
85 }
86 }
87
88 // Call arguments for NewF.
89 SmallVector<Value *> Args(NewF->arg_size(), nullptr);
90
91 // Fill up the additional parameters with default values.
92 for (auto ArgIdx : llvm::seq<size_t>(Begin: OldF->arg_size(), End: NewF->arg_size())) {
93 Type *NewArgTy = NewF->getArg(i: ArgIdx)->getType();
94 Args[ArgIdx] = getDefaultValue(T: NewArgTy);
95 }
96
97 for (CallBase *CI : Callers) {
98 // Preserve the original function arguments.
99 for (auto Z : zip_first(t: CI->args(), u&: Args))
100 std::get<1>(t&: Z) = std::get<0>(t&: Z);
101
102 // Also preserve operand bundles.
103 SmallVector<OperandBundleDef> OperandBundles;
104 CI->getOperandBundlesAsDefs(Defs&: OperandBundles);
105
106 // Create the new function call.
107 CallBase *NewCI;
108 if (auto *II = dyn_cast<InvokeInst>(Val: CI)) {
109 NewCI = InvokeInst::Create(Func: NewF, IfNormal: II->getNormalDest(), IfException: II->getUnwindDest(),
110 Args, Bundles: OperandBundles, NameStr: CI->getName());
111 } else {
112 assert(isa<CallInst>(CI));
113 NewCI = CallInst::Create(Func: NewF, Args, Bundles: OperandBundles, NameStr: CI->getName());
114 }
115 NewCI->setCallingConv(NewF->getCallingConv());
116 NewCI->setAttributes(CI->getAttributes());
117
118 if (isa<FPMathOperator>(Val: NewCI))
119 NewCI->setFastMathFlags(CI->getFastMathFlags());
120
121 NewCI->copyMetadata(SrcInst: *CI);
122
123 // Do the replacement for this use.
124 if (!CI->use_empty())
125 CI->replaceAllUsesWith(V: NewCI);
126 ReplaceInstWithInst(From: CI, To: NewCI);
127 }
128}
129
130/// Add a new function argument to @p F for each use in @OpsToReplace, and
131/// replace those operand values with the new function argument.
132static void substituteOperandWithArgument(Function *OldF,
133 ArrayRef<Use *> OpsToReplace) {
134 if (OpsToReplace.empty())
135 return;
136
137 SetVector<Value *> UniqueValues;
138 for (Use *Op : OpsToReplace)
139 UniqueValues.insert(X: Op->get());
140
141 // Determine the new function's signature.
142 SmallVector<Type *> NewArgTypes(OldF->getFunctionType()->params());
143 size_t ArgOffset = NewArgTypes.size();
144 for (Value *V : UniqueValues)
145 NewArgTypes.push_back(Elt: V->getType());
146 FunctionType *FTy =
147 FunctionType::get(Result: OldF->getFunctionType()->getReturnType(), Params: NewArgTypes,
148 isVarArg: OldF->getFunctionType()->isVarArg());
149
150 // Create the new function...
151 Function *NewF = Function::Create(
152 Ty: FTy, Linkage: OldF->getLinkage(), AddrSpace: OldF->getAddressSpace(), N: "", M: OldF->getParent());
153
154 // In order to preserve function order, we move NewF behind OldF
155 NewF->removeFromParent();
156 OldF->getParent()->getFunctionList().insertAfter(where: OldF->getIterator(), New: NewF);
157
158 // Preserve the parameters of OldF.
159 ValueToValueMapTy VMap;
160 for (auto Z : zip_first(t: OldF->args(), u: NewF->args())) {
161 Argument &OldArg = std::get<0>(t&: Z);
162 Argument &NewArg = std::get<1>(t&: Z);
163
164 NewArg.takeName(V: &OldArg); // Copy the name over...
165 VMap[&OldArg] = &NewArg; // Add mapping to VMap
166 }
167
168 LLVMContext &Ctx = OldF->getContext();
169
170 // Adjust the new parameters.
171 ValueToValueMapTy OldValMap;
172 for (auto Z : zip_first(t&: UniqueValues, u: drop_begin(RangeOrContainer: NewF->args(), N: ArgOffset))) {
173 Value *OldVal = std::get<0>(t&: Z);
174 Argument &NewArg = std::get<1>(t&: Z);
175
176 NewArg.setName(OldVal->getName());
177 OldValMap[OldVal] = &NewArg;
178 }
179
180 SmallVector<ReturnInst *, 8> Returns; // Ignore returns cloned.
181 CloneFunctionInto(NewFunc: NewF, OldFunc: OldF, VMap, Changes: CloneFunctionChangeType::LocalChangesOnly,
182 Returns, NameSuffix: "", /*CodeInfo=*/nullptr);
183
184 // Replace the actual operands.
185 for (Use *Op : OpsToReplace) {
186 Argument *NewArg = cast<Argument>(Val: OldValMap.lookup(Val: Op->get()));
187 auto *NewUser = cast<Instruction>(Val: VMap.lookup(Val: Op->getUser()));
188
189 // Try to preserve any information contained metadata annotations as the
190 // equivalent parameter attributes if possible.
191 if (auto *MDSrcInst = dyn_cast<Instruction>(Val: Op)) {
192 AttrBuilder AB(Ctx);
193 NewArg->addAttrs(B&: AB.addFromEquivalentMetadata(I: *MDSrcInst));
194 }
195
196 if (PHINode *NewPhi = dyn_cast<PHINode>(Val: NewUser)) {
197 PHINode *OldPhi = cast<PHINode>(Val: Op->getUser());
198 BasicBlock *OldBB = OldPhi->getIncomingBlock(U: *Op);
199 NewPhi->setIncomingValueForBlock(BB: cast<BasicBlock>(Val: VMap.lookup(Val: OldBB)),
200 V: NewArg);
201 } else
202 NewUser->setOperand(i: Op->getOperandNo(), Val: NewArg);
203 }
204
205 // Replace all OldF uses with NewF.
206 replaceFunctionCalls(OldF, NewF);
207
208 NewF->takeName(V: OldF);
209 OldF->replaceAllUsesWith(V: NewF);
210 OldF->eraseFromParent();
211}
212
213void llvm::reduceOperandsToArgsDeltaPass(Oracle &O, ReducerWorkItem &WorkItem) {
214 Module &Program = WorkItem.getModule();
215
216 SmallVector<Use *> OperandsToReduce;
217 for (Function &F : make_early_inc_range(Range: Program.functions())) {
218 if (!canReplaceFunction(F))
219 continue;
220 OperandsToReduce.clear();
221 for (Instruction &I : instructions(F: &F)) {
222 for (Use &Op : I.operands()) {
223 if (!canReduceUse(Op))
224 continue;
225 if (O.shouldKeep())
226 continue;
227
228 OperandsToReduce.push_back(Elt: &Op);
229 }
230 }
231
232 substituteOperandWithArgument(OldF: &F, OpsToReplace: OperandsToReduce);
233 }
234}
235