1 //===-- lib/CodeGen/GlobalISel/GICombinerHelper.cpp -----------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 #include "llvm/CodeGen/GlobalISel/CombinerHelper.h"
10 #include "llvm/CodeGen/GlobalISel/Combiner.h"
11 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
12 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
13 #include "llvm/CodeGen/GlobalISel/Utils.h"
14 #include "llvm/CodeGen/MachineInstr.h"
15 #include "llvm/CodeGen/MachineRegisterInfo.h"
16 #include "llvm/CodeGen/TargetInstrInfo.h"
17
18 #define DEBUG_TYPE "gi-combiner"
19
20 using namespace llvm;
21
22 CombinerHelper::CombinerHelper(GISelChangeObserver &Observer,
23 MachineIRBuilder &B)
24 : Builder(B), MRI(Builder.getMF().getRegInfo()), Observer(Observer) {}
25
anchor()26 void CombinerHelper::replaceRegWith(MachineRegisterInfo &MRI, unsigned FromReg,
27 unsigned ToReg) const {
28 Observer.changingAllUsesOfReg(MRI, FromReg);
29
30 if (MRI.constrainRegAttrs(ToReg, FromReg))
31 MRI.replaceRegWith(FromReg, ToReg);
32 else
33 Builder.buildCopy(ToReg, FromReg);
34
35 Observer.finishedChangingAllUsesOfReg();
36 }
37
38 void CombinerHelper::replaceRegOpWith(MachineRegisterInfo &MRI,
39 MachineOperand &FromRegOp,
40 unsigned ToReg) const {
41 assert(FromRegOp.getParent() && "Expected an operand in an MI");
42 Observer.changingInstr(*FromRegOp.getParent());
43
44 FromRegOp.setReg(ToReg);
45
46 Observer.changedInstr(*FromRegOp.getParent());
47 }
48
49 bool CombinerHelper::tryCombineCopy(MachineInstr &MI) {
50 if (MI.getOpcode() != TargetOpcode::COPY)
51 return false;
52 unsigned DstReg = MI.getOperand(0).getReg();
53 unsigned SrcReg = MI.getOperand(1).getReg();
54 LLT DstTy = MRI.getType(DstReg);
55 LLT SrcTy = MRI.getType(SrcReg);
56 // Simple Copy Propagation.
57 // a(sx) = COPY b(sx) -> Replace all uses of a with b.
58 if (DstTy.isValid() && SrcTy.isValid() && DstTy == SrcTy) {
59 MI.eraseFromParent();
60 replaceRegWith(MRI, DstReg, SrcReg);
61 return true;
62 }
63 return false;
setArgFlags(CallLowering::ArgInfo & Arg,unsigned OpIdx,const DataLayout & DL,const FuncInfoTy & FuncInfo) const64 }
65
66 namespace {
67 struct PreferredTuple {
68 LLT Ty; // The result type of the extend.
69 unsigned ExtendOpcode; // G_ANYEXT/G_SEXT/G_ZEXT
70 MachineInstr *MI;
71 };
72
73 /// Select a preference between two uses. CurrentUse is the current preference
74 /// while *ForCandidate is attributes of the candidate under consideration.
75 PreferredTuple ChoosePreferredUse(PreferredTuple &CurrentUse,
76 const LLT &TyForCandidate,
77 unsigned OpcodeForCandidate,
78 MachineInstr *MIForCandidate) {
79 if (!CurrentUse.Ty.isValid()) {
80 if (CurrentUse.ExtendOpcode == OpcodeForCandidate ||
81 CurrentUse.ExtendOpcode == TargetOpcode::G_ANYEXT)
82 return {TyForCandidate, OpcodeForCandidate, MIForCandidate};
83 return CurrentUse;
84 }
85
86 // We permit the extend to hoist through basic blocks but this is only
87 // sensible if the target has extending loads. If you end up lowering back
88 // into a load and extend during the legalizer then the end result is
89 // hoisting the extend up to the load.
90
91 // Prefer defined extensions to undefined extensions as these are more
92 // likely to reduce the number of instructions.
93 if (OpcodeForCandidate == TargetOpcode::G_ANYEXT &&
94 CurrentUse.ExtendOpcode != TargetOpcode::G_ANYEXT)
95 return CurrentUse;
96 else if (CurrentUse.ExtendOpcode == TargetOpcode::G_ANYEXT &&
97 OpcodeForCandidate != TargetOpcode::G_ANYEXT)
98 return {TyForCandidate, OpcodeForCandidate, MIForCandidate};
99
100 // Prefer sign extensions to zero extensions as sign-extensions tend to be
101 // more expensive.
102 if (CurrentUse.Ty == TyForCandidate) {
103 if (CurrentUse.ExtendOpcode == TargetOpcode::G_SEXT &&
104 OpcodeForCandidate == TargetOpcode::G_ZEXT)
105 return CurrentUse;
106 else if (CurrentUse.ExtendOpcode == TargetOpcode::G_ZEXT &&
107 OpcodeForCandidate == TargetOpcode::G_SEXT)
108 return {TyForCandidate, OpcodeForCandidate, MIForCandidate};
109 }
110
111 // This is potentially target specific. We've chosen the largest type
112 // because G_TRUNC is usually free. One potential catch with this is that
113 // some targets have a reduced number of larger registers than smaller
114 // registers and this choice potentially increases the live-range for the
115 // larger value.
116 if (TyForCandidate.getSizeInBits() > CurrentUse.Ty.getSizeInBits()) {
117 return {TyForCandidate, OpcodeForCandidate, MIForCandidate};
118 }
119 return CurrentUse;
120 }
121
122 /// Find a suitable place to insert some instructions and insert them. This
123 /// function accounts for special cases like inserting before a PHI node.
124 /// The current strategy for inserting before PHI's is to duplicate the
125 /// instructions for each predecessor. However, while that's ok for G_TRUNC
126 /// on most targets since it generally requires no code, other targets/cases may
127 /// want to try harder to find a dominating block.
128 static void InsertInsnsWithoutSideEffectsBeforeUse(
129 MachineIRBuilder &Builder, MachineInstr &DefMI, MachineOperand &UseMO,
130 std::function<void(MachineBasicBlock *, MachineBasicBlock::iterator)>
131 Inserter) {
132 MachineInstr &UseMI = *UseMO.getParent();
133
134 MachineBasicBlock *InsertBB = UseMI.getParent();
135
136 // If the use is a PHI then we want the predecessor block instead.
137 if (UseMI.isPHI()) {
138 MachineOperand *PredBB = std::next(&UseMO);
139 InsertBB = PredBB->getMBB();
140 }
141
142 // If the block is the same block as the def then we want to insert just after
143 // the def instead of at the start of the block.
144 if (InsertBB == DefMI.getParent()) {
145 MachineBasicBlock::iterator InsertPt = &DefMI;
146 Inserter(InsertBB, std::next(InsertPt));
147 return;
148 }
149
150 // Otherwise we want the start of the BB
151 Inserter(InsertBB, InsertBB->getFirstNonPHI());
152 }
153 } // end anonymous namespace
154
155 bool CombinerHelper::tryCombineExtendingLoads(MachineInstr &MI) {
156 struct InsertionPoint {
157 MachineOperand *UseMO;
extendRegister(unsigned ValReg,CCValAssign & VA)158 MachineBasicBlock *InsertIntoBB;
159 MachineBasicBlock::iterator InsertBefore;
160 InsertionPoint(MachineOperand *UseMO, MachineBasicBlock *InsertIntoBB,
161 MachineBasicBlock::iterator InsertBefore)
162 : UseMO(UseMO), InsertIntoBB(InsertIntoBB), InsertBefore(InsertBefore) {
163 }
164 };
165
166 // We match the loads and follow the uses to the extend instead of matching
167 // the extends and following the def to the load. This is because the load
168 // must remain in the same position for correctness (unless we also add code
169 // to find a safe place to sink it) whereas the extend is freely movable.
170 // It also prevents us from duplicating the load for the volatile case or just
171 // for performance.
172
173 if (MI.getOpcode() != TargetOpcode::G_LOAD &&
174 MI.getOpcode() != TargetOpcode::G_SEXTLOAD &&
175 MI.getOpcode() != TargetOpcode::G_ZEXTLOAD)
176 return false;
177
178 auto &LoadValue = MI.getOperand(0);
179 assert(LoadValue.isReg() && "Result wasn't a register?");
180
181 LLT LoadValueTy = MRI.getType(LoadValue.getReg());
182 if (!LoadValueTy.isScalar())
183 return false;
184
185 // Find the preferred type aside from the any-extends (unless it's the only
anchor()186 // one) and non-extending ops. We'll emit an extending load to that type and
187 // and emit a variant of (extend (trunc X)) for the others according to the
188 // relative type sizes. At the same time, pick an extend to use based on the
189 // extend involved in the chosen type.
190 unsigned PreferredOpcode = MI.getOpcode() == TargetOpcode::G_LOAD
191 ? TargetOpcode::G_ANYEXT
192 : MI.getOpcode() == TargetOpcode::G_SEXTLOAD
193 ? TargetOpcode::G_SEXT
194 : TargetOpcode::G_ZEXT;
195 PreferredTuple Preferred = {LLT(), PreferredOpcode, nullptr};
196 for (auto &UseMI : MRI.use_instructions(LoadValue.getReg())) {
197 if (UseMI.getOpcode() == TargetOpcode::G_SEXT ||
198 UseMI.getOpcode() == TargetOpcode::G_ZEXT ||
199 UseMI.getOpcode() == TargetOpcode::G_ANYEXT) {
200 Preferred = ChoosePreferredUse(Preferred,
201 MRI.getType(UseMI.getOperand(0).getReg()),
202 UseMI.getOpcode(), &UseMI);
203 }
204 }
205
206 // There were no extends
207 if (!Preferred.MI)
208 return false;
209 // It should be impossible to chose an extend without selecting a different
210 // type since by definition the result of an extend is larger.
211 assert(Preferred.Ty != LoadValueTy && "Extending to same type?");
212
213 LLVM_DEBUG(dbgs() << "Preferred use is: " << *Preferred.MI);
214
215 // Rewrite the load to the chosen extending load.
216 unsigned ChosenDstReg = Preferred.MI->getOperand(0).getReg();
217 Observer.changingInstr(MI);
218 MI.setDesc(
219 Builder.getTII().get(Preferred.ExtendOpcode == TargetOpcode::G_SEXT
220 ? TargetOpcode::G_SEXTLOAD
221 : Preferred.ExtendOpcode == TargetOpcode::G_ZEXT
222 ? TargetOpcode::G_ZEXTLOAD
223 : TargetOpcode::G_LOAD));
224
225 // Rewrite all the uses to fix up the types.
226 SmallVector<MachineInstr *, 1> ScheduleForErase;
227 SmallVector<InsertionPoint, 4> ScheduleForInsert;
228 for (auto &UseMO : MRI.use_operands(LoadValue.getReg())) {
229 MachineInstr *UseMI = UseMO.getParent();
230
231 // If the extend is compatible with the preferred extend then we should fix
232 // up the type and extend so that it uses the preferred use.
233 if (UseMI->getOpcode() == Preferred.ExtendOpcode ||
234 UseMI->getOpcode() == TargetOpcode::G_ANYEXT) {
235 unsigned UseDstReg = UseMI->getOperand(0).getReg();
236 MachineOperand &UseSrcMO = UseMI->getOperand(1);
237 const LLT &UseDstTy = MRI.getType(UseDstReg);
238 if (UseDstReg != ChosenDstReg) {
239 if (Preferred.Ty == UseDstTy) {
240 // If the use has the same type as the preferred use, then merge
241 // the vregs and erase the extend. For example:
242 // %1:_(s8) = G_LOAD ...
243 // %2:_(s32) = G_SEXT %1(s8)
244 // %3:_(s32) = G_ANYEXT %1(s8)
245 // ... = ... %3(s32)
246 // rewrites to:
247 // %2:_(s32) = G_SEXTLOAD ...
248 // ... = ... %2(s32)
249 replaceRegWith(MRI, UseDstReg, ChosenDstReg);
250 ScheduleForErase.push_back(UseMO.getParent());
251 } else if (Preferred.Ty.getSizeInBits() < UseDstTy.getSizeInBits()) {
252 // If the preferred size is smaller, then keep the extend but extend
253 // from the result of the extending load. For example:
254 // %1:_(s8) = G_LOAD ...
255 // %2:_(s32) = G_SEXT %1(s8)
256 // %3:_(s64) = G_ANYEXT %1(s8)
257 // ... = ... %3(s64)
258 /// rewrites to:
259 // %2:_(s32) = G_SEXTLOAD ...
260 // %3:_(s64) = G_ANYEXT %2:_(s32)
261 // ... = ... %3(s64)
262 replaceRegOpWith(MRI, UseSrcMO, ChosenDstReg);
263 } else {
264 // If the preferred size is large, then insert a truncate. For
265 // example:
266 // %1:_(s8) = G_LOAD ...
267 // %2:_(s64) = G_SEXT %1(s8)
268 // %3:_(s32) = G_ZEXT %1(s8)
269 // ... = ... %3(s32)
270 /// rewrites to:
271 // %2:_(s64) = G_SEXTLOAD ...
272 // %4:_(s8) = G_TRUNC %2:_(s32)
273 // %3:_(s64) = G_ZEXT %2:_(s8)
274 // ... = ... %3(s64)
275 InsertInsnsWithoutSideEffectsBeforeUse(
276 Builder, MI, UseMO,
277 [&](MachineBasicBlock *InsertIntoBB,
278 MachineBasicBlock::iterator InsertBefore) {
279 ScheduleForInsert.emplace_back(&UseMO, InsertIntoBB, InsertBefore);
280 });
281 }
282 continue;
283 }
284 // The use is (one of) the uses of the preferred use we chose earlier.
285 // We're going to update the load to def this value later so just erase
286 // the old extend.
287 ScheduleForErase.push_back(UseMO.getParent());
288 continue;
289 }
290
291 // The use isn't an extend. Truncate back to the type we originally loaded.
292 // This is free on many targets.
293 InsertInsnsWithoutSideEffectsBeforeUse(
294 Builder, MI, UseMO,
295 [&](MachineBasicBlock *InsertIntoBB,
296 MachineBasicBlock::iterator InsertBefore) {
297 ScheduleForInsert.emplace_back(&UseMO, InsertIntoBB, InsertBefore);
298 });
299 }
300
301 DenseMap<MachineBasicBlock *, MachineInstr *> EmittedInsns;
302 for (auto &InsertionInfo : ScheduleForInsert) {
303 MachineOperand *UseMO = InsertionInfo.UseMO;
304 MachineBasicBlock *InsertIntoBB = InsertionInfo.InsertIntoBB;
305 MachineBasicBlock::iterator InsertBefore = InsertionInfo.InsertBefore;
306
307 MachineInstr *PreviouslyEmitted = EmittedInsns.lookup(InsertIntoBB);
308 if (PreviouslyEmitted) {
309 Observer.changingInstr(*UseMO->getParent());
310 UseMO->setReg(PreviouslyEmitted->getOperand(0).getReg());
311 Observer.changedInstr(*UseMO->getParent());
312 continue;
313 }
314
315 Builder.setInsertPt(*InsertIntoBB, InsertBefore);
316 unsigned NewDstReg = MRI.cloneVirtualRegister(MI.getOperand(0).getReg());
317 MachineInstr *NewMI = Builder.buildTrunc(NewDstReg, ChosenDstReg);
318 EmittedInsns[InsertIntoBB] = NewMI;
319 replaceRegOpWith(MRI, *UseMO, NewDstReg);
320 }
321 for (auto &EraseMI : ScheduleForErase) {
322 Observer.erasingInstr(*EraseMI);
323 EraseMI->eraseFromParent();
324 }
325 MI.getOperand(0).setReg(ChosenDstReg);
326 Observer.changedInstr(MI);
327
328 return true;
329 }
330
331 bool CombinerHelper::tryCombine(MachineInstr &MI) {
332 if (tryCombineCopy(MI))
333 return true;
334 return tryCombineExtendingLoads(MI);
335 }
336