1 //===- ReduceOpcodes.cpp - Specialized Delta Pass -------------------------===//
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 // Try to replace instructions that are likely to codegen to simpler or smaller
10 // sequences. This is a fuzzy and target specific concept.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "ReduceOpcodes.h"
15 #include "Delta.h"
16 #include "llvm/IR/IRBuilder.h"
17 #include "llvm/IR/Instructions.h"
18 #include "llvm/IR/IntrinsicInst.h"
19 #include "llvm/IR/Intrinsics.h"
20 #include "llvm/IR/IntrinsicsAMDGPU.h"
21
22 using namespace llvm;
23
24 // Assume outgoing undef arguments aren't relevant.
25 // TODO: Maybe skip any trivial constant arguments.
shouldIgnoreArgument(const Value * V)26 static bool shouldIgnoreArgument(const Value *V) {
27 return isa<UndefValue>(V);
28 }
29
replaceIntrinsic(Module & M,IntrinsicInst * II,Intrinsic::ID NewIID,ArrayRef<Type * > Tys=std::nullopt)30 static Value *replaceIntrinsic(Module &M, IntrinsicInst *II,
31 Intrinsic::ID NewIID,
32 ArrayRef<Type *> Tys = std::nullopt) {
33 Function *NewFunc = Intrinsic::getDeclaration(&M, NewIID, Tys);
34 II->setCalledFunction(NewFunc);
35 return II;
36 }
37
reduceIntrinsic(Oracle & O,Module & M,IntrinsicInst * II)38 static Value *reduceIntrinsic(Oracle &O, Module &M, IntrinsicInst *II) {
39 IRBuilder<> B(II);
40 switch (II->getIntrinsicID()) {
41 case Intrinsic::sqrt:
42 if (O.shouldKeep())
43 return nullptr;
44
45 return B.CreateFMul(II->getArgOperand(0),
46 ConstantFP::get(II->getType(), 2.0));
47 case Intrinsic::minnum:
48 case Intrinsic::maxnum:
49 case Intrinsic::minimum:
50 case Intrinsic::maximum:
51 case Intrinsic::amdgcn_fmul_legacy:
52 if (O.shouldKeep())
53 return nullptr;
54 return B.CreateFMul(II->getArgOperand(0), II->getArgOperand(1));
55 case Intrinsic::amdgcn_workitem_id_y:
56 case Intrinsic::amdgcn_workitem_id_z:
57 if (O.shouldKeep())
58 return nullptr;
59 return replaceIntrinsic(M, II, Intrinsic::amdgcn_workitem_id_x);
60 case Intrinsic::amdgcn_workgroup_id_y:
61 case Intrinsic::amdgcn_workgroup_id_z:
62 if (O.shouldKeep())
63 return nullptr;
64 return replaceIntrinsic(M, II, Intrinsic::amdgcn_workgroup_id_x);
65 case Intrinsic::amdgcn_div_fixup:
66 case Intrinsic::amdgcn_fma_legacy:
67 if (O.shouldKeep())
68 return nullptr;
69 return replaceIntrinsic(M, II, Intrinsic::fma, {II->getType()});
70 default:
71 return nullptr;
72 }
73 }
74
75 /// Look for calls that look like they could be replaced with a load or store.
callLooksLikeLoadStore(CallBase * CB,Value * & DataArg,Value * & PtrArg)76 static bool callLooksLikeLoadStore(CallBase *CB, Value *&DataArg,
77 Value *&PtrArg) {
78 const bool IsStore = CB->getType()->isVoidTy();
79
80 PtrArg = nullptr;
81 DataArg = nullptr;
82 for (Value *Arg : CB->args()) {
83 if (shouldIgnoreArgument(Arg))
84 continue;
85
86 if (!Arg->getType()->isSized())
87 return false;
88
89 PointerType *PT = dyn_cast<PointerType>(Arg->getType());
90 if (!PtrArg && PT) {
91 // FIXME: Could create bitcast for typed pointers, but roll back unused
92 // replacement only erases one instruction.
93 if (!IsStore && !PT->isOpaqueOrPointeeTypeMatches(CB->getType()))
94 return false;
95
96 PtrArg = Arg;
97 continue;
98 }
99
100 if (!IsStore || DataArg)
101 return false;
102
103 DataArg = Arg;
104 }
105
106 if (IsStore && !DataArg) {
107 // FIXME: For typed pointers, use element type?
108 DataArg = ConstantInt::get(IntegerType::getInt32Ty(CB->getContext()), 0);
109 }
110
111 // If we didn't find any arguments, we can fill in the pointer.
112 if (!PtrArg) {
113 unsigned AS = CB->getModule()->getDataLayout().getAllocaAddrSpace();
114
115 PointerType *PtrTy =
116 PointerType::get(DataArg ? DataArg->getType()
117 : IntegerType::getInt32Ty(CB->getContext()),
118 AS);
119
120 PtrArg = ConstantPointerNull::get(PtrTy);
121 }
122
123 // Make sure we don't emit an invalid store with typed pointers.
124 if (IsStore && DataArg->getType()->getPointerTo(
125 cast<PointerType>(PtrArg->getType())->getAddressSpace()) !=
126 PtrArg->getType())
127 return false;
128
129 return true;
130 }
131
132 // TODO: Replace 2 pointer argument calls with memcpy
tryReplaceCallWithLoadStore(Oracle & O,Module & M,CallBase * CB)133 static Value *tryReplaceCallWithLoadStore(Oracle &O, Module &M, CallBase *CB) {
134 Value *PtrArg = nullptr;
135 Value *DataArg = nullptr;
136 if (!callLooksLikeLoadStore(CB, DataArg, PtrArg) || O.shouldKeep())
137 return nullptr;
138
139 IRBuilder<> B(CB);
140 if (DataArg)
141 return B.CreateStore(DataArg, PtrArg, true);
142 return B.CreateLoad(CB->getType(), PtrArg, true);
143 }
144
callLooksLikeOperator(CallBase * CB,SmallVectorImpl<Value * > & OperatorArgs)145 static bool callLooksLikeOperator(CallBase *CB,
146 SmallVectorImpl<Value *> &OperatorArgs) {
147 Type *ReturnTy = CB->getType();
148 if (!ReturnTy->isFirstClassType())
149 return false;
150
151 for (Value *Arg : CB->args()) {
152 if (shouldIgnoreArgument(Arg))
153 continue;
154
155 if (Arg->getType() != ReturnTy)
156 return false;
157
158 OperatorArgs.push_back(Arg);
159 }
160
161 return true;
162 }
163
tryReplaceCallWithOperator(Oracle & O,Module & M,CallBase * CB)164 static Value *tryReplaceCallWithOperator(Oracle &O, Module &M, CallBase *CB) {
165 SmallVector<Value *, 4> Arguments;
166
167 if (!callLooksLikeOperator(CB, Arguments) || Arguments.size() > 3)
168 return nullptr;
169
170 if (O.shouldKeep())
171 return nullptr;
172
173 IRBuilder<> B(CB);
174 if (CB->getType()->isFPOrFPVectorTy()) {
175 switch (Arguments.size()) {
176 case 1:
177 return B.CreateFNeg(Arguments[0]);
178 case 2:
179 return B.CreateFMul(Arguments[0], Arguments[1]);
180 case 3:
181 return B.CreateIntrinsic(Intrinsic::fma, {CB->getType()}, Arguments);
182 default:
183 return nullptr;
184 }
185
186 llvm_unreachable("all argument sizes handled");
187 }
188
189 if (CB->getType()->isIntOrIntVectorTy()) {
190 switch (Arguments.size()) {
191 case 1:
192 return B.CreateUnaryIntrinsic(Intrinsic::bswap, Arguments[0]);
193 case 2:
194 return B.CreateAnd(Arguments[0], Arguments[1]);
195 case 3:
196 return B.CreateIntrinsic(Intrinsic::fshl, {CB->getType()}, Arguments);
197 default:
198 return nullptr;
199 }
200
201 llvm_unreachable("all argument sizes handled");
202 }
203
204 return nullptr;
205 }
206
reduceInstruction(Oracle & O,Module & M,Instruction & I)207 static Value *reduceInstruction(Oracle &O, Module &M, Instruction &I) {
208 IRBuilder<> B(&I);
209
210 // TODO: fp binary operator with constant to fneg
211 switch (I.getOpcode()) {
212 case Instruction::FDiv:
213 case Instruction::FRem:
214 if (O.shouldKeep())
215 return nullptr;
216
217 // Divisions tends to codegen into a long sequence or a library call.
218 return B.CreateFMul(I.getOperand(0), I.getOperand(1));
219 case Instruction::UDiv:
220 case Instruction::SDiv:
221 case Instruction::URem:
222 case Instruction::SRem:
223 if (O.shouldKeep())
224 return nullptr;
225
226 // Divisions tends to codegen into a long sequence or a library call.
227 return B.CreateMul(I.getOperand(0), I.getOperand(1));
228 case Instruction::Add:
229 case Instruction::Sub: {
230 if (O.shouldKeep())
231 return nullptr;
232
233 // Add/sub are more likely codegen to instructions with carry out side
234 // effects.
235 return B.CreateOr(I.getOperand(0), I.getOperand(1));
236 }
237 case Instruction::Call: {
238 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(&I))
239 return reduceIntrinsic(O, M, II);
240
241 CallBase *CB = cast<CallBase>(&I);
242
243 if (Value *NewOp = tryReplaceCallWithOperator(O, M, CB))
244 return NewOp;
245
246 if (Value *NewOp = tryReplaceCallWithLoadStore(O, M, CB))
247 return NewOp;
248
249 return nullptr;
250 }
251 default:
252 return nullptr;
253 }
254
255 return nullptr;
256 }
257
replaceOpcodesInModule(Oracle & O,ReducerWorkItem & WorkItem)258 static void replaceOpcodesInModule(Oracle &O, ReducerWorkItem &WorkItem) {
259 Module &Mod = WorkItem.getModule();
260
261 for (Function &F : Mod) {
262 for (BasicBlock &BB : F)
263 for (Instruction &I : make_early_inc_range(BB)) {
264 Instruction *Replacement =
265 dyn_cast_or_null<Instruction>(reduceInstruction(O, Mod, I));
266 if (Replacement && Replacement != &I) {
267 if (isa<FPMathOperator>(Replacement))
268 Replacement->copyFastMathFlags(&I);
269
270 Replacement->copyIRFlags(&I);
271 Replacement->copyMetadata(I);
272 Replacement->takeName(&I);
273 I.replaceAllUsesWith(Replacement);
274 I.eraseFromParent();
275 }
276 }
277 }
278 }
279
reduceOpcodesDeltaPass(TestRunner & Test)280 void llvm::reduceOpcodesDeltaPass(TestRunner &Test) {
281 runDeltaPass(Test, replaceOpcodesInModule, "Reducing Opcodes");
282 }
283