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 return true;
59}
60
61/// Goes over OldF calls and replaces them with a call to NewF.
62static void replaceFunctionCalls(Function *OldF, Function *NewF) {
63 SmallVector<CallBase *> Callers;
64 for (Use &U : OldF->uses()) {
65 auto *CI = dyn_cast<CallBase>(Val: U.getUser());
66 if (!CI || !CI->isCallee(U: &U)) // RAUW can handle these fine.
67 continue;
68
69 Function *CalledF = CI->getCalledFunction();
70 if (CalledF == OldF) {
71 Callers.push_back(Elt: CI);
72 } else {
73 // The call may have undefined behavior by calling a function with a
74 // mismatched signature. In this case, do not bother adjusting the
75 // callsites to pad with any new arguments.
76
77 // TODO: Better QoI to try to add new arguments to the end, and ignore
78 // existing mismatches.
79 assert(!CalledF && CI->getCalledOperand()->stripPointerCasts() == OldF &&
80 "only expected call and function signature mismatch");
81 }
82 }
83
84 // Call arguments for NewF.
85 SmallVector<Value *> Args(NewF->arg_size(), nullptr);
86
87 // Fill up the additional parameters with default values.
88 for (auto ArgIdx : llvm::seq<size_t>(Begin: OldF->arg_size(), End: NewF->arg_size())) {
89 Type *NewArgTy = NewF->getArg(i: ArgIdx)->getType();
90 Args[ArgIdx] = getDefaultValue(T: NewArgTy);
91 }
92
93 for (CallBase *CI : Callers) {
94 // Preserve the original function arguments.
95 for (auto Z : zip_first(t: CI->args(), u&: Args))
96 std::get<1>(t&: Z) = std::get<0>(t&: Z);
97
98 // Also preserve operand bundles.
99 SmallVector<OperandBundleDef> OperandBundles;
100 CI->getOperandBundlesAsDefs(Defs&: OperandBundles);
101
102 // Create the new function call.
103 CallBase *NewCI;
104 if (auto *II = dyn_cast<InvokeInst>(Val: CI)) {
105 NewCI = InvokeInst::Create(Func: NewF, IfNormal: II->getNormalDest(), IfException: II->getUnwindDest(),
106 Args, Bundles: OperandBundles, NameStr: CI->getName());
107 } else {
108 assert(isa<CallInst>(CI));
109 NewCI = CallInst::Create(Func: NewF, Args, Bundles: OperandBundles, NameStr: CI->getName());
110 }
111 NewCI->setCallingConv(NewF->getCallingConv());
112 NewCI->setAttributes(CI->getAttributes());
113
114 if (isa<FPMathOperator>(Val: NewCI))
115 NewCI->setFastMathFlags(CI->getFastMathFlags());
116
117 NewCI->copyMetadata(SrcInst: *CI);
118
119 // Do the replacement for this use.
120 if (!CI->use_empty())
121 CI->replaceAllUsesWith(V: NewCI);
122 ReplaceInstWithInst(From: CI, To: NewCI);
123 }
124}
125
126/// Add a new function argument to @p F for each use in @OpsToReplace, and
127/// replace those operand values with the new function argument.
128static void substituteOperandWithArgument(Function *OldF,
129 ArrayRef<Use *> OpsToReplace) {
130 if (OpsToReplace.empty())
131 return;
132
133 SetVector<Value *> UniqueValues;
134 for (Use *Op : OpsToReplace)
135 UniqueValues.insert(X: Op->get());
136
137 // Determine the new function's signature.
138 SmallVector<Type *> NewArgTypes(OldF->getFunctionType()->params());
139 size_t ArgOffset = NewArgTypes.size();
140 for (Value *V : UniqueValues)
141 NewArgTypes.push_back(Elt: V->getType());
142 FunctionType *FTy =
143 FunctionType::get(Result: OldF->getFunctionType()->getReturnType(), Params: NewArgTypes,
144 isVarArg: OldF->getFunctionType()->isVarArg());
145
146 // Create the new function...
147 Function *NewF = Function::Create(
148 Ty: FTy, Linkage: OldF->getLinkage(), AddrSpace: OldF->getAddressSpace(), N: "", M: OldF->getParent());
149
150 // In order to preserve function order, we move NewF behind OldF
151 NewF->removeFromParent();
152 OldF->getParent()->getFunctionList().insertAfter(where: OldF->getIterator(), New: NewF);
153
154 // Preserve the parameters of OldF.
155 ValueToValueMapTy VMap;
156 for (auto Z : zip_first(t: OldF->args(), u: NewF->args())) {
157 Argument &OldArg = std::get<0>(t&: Z);
158 Argument &NewArg = std::get<1>(t&: Z);
159
160 NewArg.takeName(V: &OldArg); // Copy the name over...
161 VMap[&OldArg] = &NewArg; // Add mapping to VMap
162 }
163
164 LLVMContext &Ctx = OldF->getContext();
165
166 // Adjust the new parameters.
167 ValueToValueMapTy OldValMap;
168 for (auto Z : zip_first(t&: UniqueValues, u: drop_begin(RangeOrContainer: NewF->args(), N: ArgOffset))) {
169 Value *OldVal = std::get<0>(t&: Z);
170 Argument &NewArg = std::get<1>(t&: Z);
171
172 NewArg.setName(OldVal->getName());
173 OldValMap[OldVal] = &NewArg;
174 }
175
176 SmallVector<ReturnInst *, 8> Returns; // Ignore returns cloned.
177 CloneFunctionInto(NewFunc: NewF, OldFunc: OldF, VMap, Changes: CloneFunctionChangeType::LocalChangesOnly,
178 Returns, NameSuffix: "", /*CodeInfo=*/nullptr);
179
180 // Replace the actual operands.
181 for (Use *Op : OpsToReplace) {
182 Argument *NewArg = cast<Argument>(Val: OldValMap.lookup(Val: Op->get()));
183 auto *NewUser = cast<Instruction>(Val: VMap.lookup(Val: Op->getUser()));
184
185 // Try to preserve any information contained metadata annotations as the
186 // equivalent parameter attributes if possible.
187 if (auto *MDSrcInst = dyn_cast<Instruction>(Val: Op)) {
188 AttrBuilder AB(Ctx);
189 NewArg->addAttrs(B&: AB.addFromEquivalentMetadata(I: *MDSrcInst));
190 }
191
192 if (PHINode *NewPhi = dyn_cast<PHINode>(Val: NewUser)) {
193 PHINode *OldPhi = cast<PHINode>(Val: Op->getUser());
194 BasicBlock *OldBB = OldPhi->getIncomingBlock(U: *Op);
195 NewPhi->setIncomingValueForBlock(BB: cast<BasicBlock>(Val: VMap.lookup(Val: OldBB)),
196 V: NewArg);
197 } else
198 NewUser->setOperand(i: Op->getOperandNo(), Val: NewArg);
199 }
200
201 // Replace all OldF uses with NewF.
202 replaceFunctionCalls(OldF, NewF);
203
204 NewF->takeName(V: OldF);
205 OldF->replaceAllUsesWith(V: NewF);
206 OldF->eraseFromParent();
207}
208
209void llvm::reduceOperandsToArgsDeltaPass(Oracle &O, ReducerWorkItem &WorkItem) {
210 Module &Program = WorkItem.getModule();
211
212 SmallVector<Use *> OperandsToReduce;
213 for (Function &F : make_early_inc_range(Range: Program.functions())) {
214 if (!canReplaceFunction(F))
215 continue;
216 OperandsToReduce.clear();
217 for (Instruction &I : instructions(F: &F)) {
218 for (Use &Op : I.operands()) {
219 if (!canReduceUse(Op))
220 continue;
221 if (O.shouldKeep())
222 continue;
223
224 OperandsToReduce.push_back(Elt: &Op);
225 }
226 }
227
228 substituteOperandWithArgument(OldF: &F, OpsToReplace: OperandsToReduce);
229 }
230}
231