LLVM  9.0.0svn
CombinerHelper.cpp
Go to the documentation of this file.
1 //===-- lib/CodeGen/GlobalISel/GICombinerHelper.cpp -----------------------===//
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 //===----------------------------------------------------------------------===//
16 
17 #define DEBUG_TYPE "gi-combiner"
18 
19 using namespace llvm;
20 
23  : Builder(B), MRI(Builder.getMF().getRegInfo()), Observer(Observer) {}
24 
26  unsigned ToReg) const {
27  Observer.changingAllUsesOfReg(MRI, FromReg);
28 
29  if (MRI.constrainRegAttrs(ToReg, FromReg))
30  MRI.replaceRegWith(FromReg, ToReg);
31  else
32  Builder.buildCopy(ToReg, FromReg);
33 
35 }
36 
38  MachineOperand &FromRegOp,
39  unsigned ToReg) const {
40  assert(FromRegOp.getParent() && "Expected an operand in an MI");
41  Observer.changingInstr(*FromRegOp.getParent());
42 
43  FromRegOp.setReg(ToReg);
44 
45  Observer.changedInstr(*FromRegOp.getParent());
46 }
47 
49  if (matchCombineCopy(MI)) {
50  applyCombineCopy(MI);
51  return true;
52  }
53  return false;
54 }
56  if (MI.getOpcode() != TargetOpcode::COPY)
57  return false;
58  unsigned DstReg = MI.getOperand(0).getReg();
59  unsigned SrcReg = MI.getOperand(1).getReg();
60  LLT DstTy = MRI.getType(DstReg);
61  LLT SrcTy = MRI.getType(SrcReg);
62  // Simple Copy Propagation.
63  // a(sx) = COPY b(sx) -> Replace all uses of a with b.
64  if (DstTy.isValid() && SrcTy.isValid() && DstTy == SrcTy)
65  return true;
66  return false;
67 }
69  unsigned DstReg = MI.getOperand(0).getReg();
70  unsigned SrcReg = MI.getOperand(1).getReg();
71  MI.eraseFromParent();
72  replaceRegWith(MRI, DstReg, SrcReg);
73 }
74 
75 namespace {
76 
77 /// Select a preference between two uses. CurrentUse is the current preference
78 /// while *ForCandidate is attributes of the candidate under consideration.
79 PreferredTuple ChoosePreferredUse(PreferredTuple &CurrentUse,
80  const LLT &TyForCandidate,
81  unsigned OpcodeForCandidate,
82  MachineInstr *MIForCandidate) {
83  if (!CurrentUse.Ty.isValid()) {
84  if (CurrentUse.ExtendOpcode == OpcodeForCandidate ||
85  CurrentUse.ExtendOpcode == TargetOpcode::G_ANYEXT)
86  return {TyForCandidate, OpcodeForCandidate, MIForCandidate};
87  return CurrentUse;
88  }
89 
90  // We permit the extend to hoist through basic blocks but this is only
91  // sensible if the target has extending loads. If you end up lowering back
92  // into a load and extend during the legalizer then the end result is
93  // hoisting the extend up to the load.
94 
95  // Prefer defined extensions to undefined extensions as these are more
96  // likely to reduce the number of instructions.
97  if (OpcodeForCandidate == TargetOpcode::G_ANYEXT &&
98  CurrentUse.ExtendOpcode != TargetOpcode::G_ANYEXT)
99  return CurrentUse;
100  else if (CurrentUse.ExtendOpcode == TargetOpcode::G_ANYEXT &&
101  OpcodeForCandidate != TargetOpcode::G_ANYEXT)
102  return {TyForCandidate, OpcodeForCandidate, MIForCandidate};
103 
104  // Prefer sign extensions to zero extensions as sign-extensions tend to be
105  // more expensive.
106  if (CurrentUse.Ty == TyForCandidate) {
107  if (CurrentUse.ExtendOpcode == TargetOpcode::G_SEXT &&
108  OpcodeForCandidate == TargetOpcode::G_ZEXT)
109  return CurrentUse;
110  else if (CurrentUse.ExtendOpcode == TargetOpcode::G_ZEXT &&
111  OpcodeForCandidate == TargetOpcode::G_SEXT)
112  return {TyForCandidate, OpcodeForCandidate, MIForCandidate};
113  }
114 
115  // This is potentially target specific. We've chosen the largest type
116  // because G_TRUNC is usually free. One potential catch with this is that
117  // some targets have a reduced number of larger registers than smaller
118  // registers and this choice potentially increases the live-range for the
119  // larger value.
120  if (TyForCandidate.getSizeInBits() > CurrentUse.Ty.getSizeInBits()) {
121  return {TyForCandidate, OpcodeForCandidate, MIForCandidate};
122  }
123  return CurrentUse;
124 }
125 
126 /// Find a suitable place to insert some instructions and insert them. This
127 /// function accounts for special cases like inserting before a PHI node.
128 /// The current strategy for inserting before PHI's is to duplicate the
129 /// instructions for each predecessor. However, while that's ok for G_TRUNC
130 /// on most targets since it generally requires no code, other targets/cases may
131 /// want to try harder to find a dominating block.
132 static void InsertInsnsWithoutSideEffectsBeforeUse(
135  Inserter) {
136  MachineInstr &UseMI = *UseMO.getParent();
137 
138  MachineBasicBlock *InsertBB = UseMI.getParent();
139 
140  // If the use is a PHI then we want the predecessor block instead.
141  if (UseMI.isPHI()) {
142  MachineOperand *PredBB = std::next(&UseMO);
143  InsertBB = PredBB->getMBB();
144  }
145 
146  // If the block is the same block as the def then we want to insert just after
147  // the def instead of at the start of the block.
148  if (InsertBB == DefMI.getParent()) {
150  Inserter(InsertBB, std::next(InsertPt));
151  return;
152  }
153 
154  // Otherwise we want the start of the BB
155  Inserter(InsertBB, InsertBB->getFirstNonPHI());
156 }
157 } // end anonymous namespace
158 
160  PreferredTuple Preferred;
161  if (matchCombineExtendingLoads(MI, Preferred)) {
162  applyCombineExtendingLoads(MI, Preferred);
163  return true;
164  }
165  return false;
166 }
167 
169  PreferredTuple &Preferred) {
170  // We match the loads and follow the uses to the extend instead of matching
171  // the extends and following the def to the load. This is because the load
172  // must remain in the same position for correctness (unless we also add code
173  // to find a safe place to sink it) whereas the extend is freely movable.
174  // It also prevents us from duplicating the load for the volatile case or just
175  // for performance.
176 
177  if (MI.getOpcode() != TargetOpcode::G_LOAD &&
178  MI.getOpcode() != TargetOpcode::G_SEXTLOAD &&
179  MI.getOpcode() != TargetOpcode::G_ZEXTLOAD)
180  return false;
181 
182  auto &LoadValue = MI.getOperand(0);
183  assert(LoadValue.isReg() && "Result wasn't a register?");
184 
185  LLT LoadValueTy = MRI.getType(LoadValue.getReg());
186  if (!LoadValueTy.isScalar())
187  return false;
188 
189  // Most architectures are going to legalize <s8 loads into at least a 1 byte
190  // load, and the MMOs can only describe memory accesses in multiples of bytes.
191  // If we try to perform extload combining on those, we can end up with
192  // %a(s8) = extload %ptr (load 1 byte from %ptr)
193  // ... which is an illegal extload instruction.
194  if (LoadValueTy.getSizeInBits() < 8)
195  return false;
196 
197  // Find the preferred type aside from the any-extends (unless it's the only
198  // one) and non-extending ops. We'll emit an extending load to that type and
199  // and emit a variant of (extend (trunc X)) for the others according to the
200  // relative type sizes. At the same time, pick an extend to use based on the
201  // extend involved in the chosen type.
202  unsigned PreferredOpcode = MI.getOpcode() == TargetOpcode::G_LOAD
203  ? TargetOpcode::G_ANYEXT
204  : MI.getOpcode() == TargetOpcode::G_SEXTLOAD
205  ? TargetOpcode::G_SEXT
206  : TargetOpcode::G_ZEXT;
207  Preferred = {LLT(), PreferredOpcode, nullptr};
208  for (auto &UseMI : MRI.use_instructions(LoadValue.getReg())) {
209  if (UseMI.getOpcode() == TargetOpcode::G_SEXT ||
210  UseMI.getOpcode() == TargetOpcode::G_ZEXT ||
211  UseMI.getOpcode() == TargetOpcode::G_ANYEXT) {
212  Preferred = ChoosePreferredUse(Preferred,
213  MRI.getType(UseMI.getOperand(0).getReg()),
214  UseMI.getOpcode(), &UseMI);
215  }
216  }
217 
218  // There were no extends
219  if (!Preferred.MI)
220  return false;
221  // It should be impossible to chose an extend without selecting a different
222  // type since by definition the result of an extend is larger.
223  assert(Preferred.Ty != LoadValueTy && "Extending to same type?");
224 
225  LLVM_DEBUG(dbgs() << "Preferred use is: " << *Preferred.MI);
226  return true;
227 }
228 
230  PreferredTuple &Preferred) {
231  struct InsertionPoint {
232  MachineOperand *UseMO;
233  MachineBasicBlock *InsertIntoBB;
234  MachineBasicBlock::iterator InsertBefore;
235  InsertionPoint(MachineOperand *UseMO, MachineBasicBlock *InsertIntoBB,
236  MachineBasicBlock::iterator InsertBefore)
237  : UseMO(UseMO), InsertIntoBB(InsertIntoBB), InsertBefore(InsertBefore) {
238  }
239  };
240 
241  // Rewrite the load to the chosen extending load.
242  unsigned ChosenDstReg = Preferred.MI->getOperand(0).getReg();
243  Observer.changingInstr(MI);
244  MI.setDesc(
245  Builder.getTII().get(Preferred.ExtendOpcode == TargetOpcode::G_SEXT
246  ? TargetOpcode::G_SEXTLOAD
247  : Preferred.ExtendOpcode == TargetOpcode::G_ZEXT
248  ? TargetOpcode::G_ZEXTLOAD
249  : TargetOpcode::G_LOAD));
250 
251  // Rewrite all the uses to fix up the types.
252  SmallVector<MachineInstr *, 1> ScheduleForErase;
253  SmallVector<InsertionPoint, 4> ScheduleForInsert;
254  auto &LoadValue = MI.getOperand(0);
255  for (auto &UseMO : MRI.use_operands(LoadValue.getReg())) {
256  MachineInstr *UseMI = UseMO.getParent();
257 
258  // If the extend is compatible with the preferred extend then we should fix
259  // up the type and extend so that it uses the preferred use.
260  if (UseMI->getOpcode() == Preferred.ExtendOpcode ||
261  UseMI->getOpcode() == TargetOpcode::G_ANYEXT) {
262  unsigned UseDstReg = UseMI->getOperand(0).getReg();
263  MachineOperand &UseSrcMO = UseMI->getOperand(1);
264  const LLT &UseDstTy = MRI.getType(UseDstReg);
265  if (UseDstReg != ChosenDstReg) {
266  if (Preferred.Ty == UseDstTy) {
267  // If the use has the same type as the preferred use, then merge
268  // the vregs and erase the extend. For example:
269  // %1:_(s8) = G_LOAD ...
270  // %2:_(s32) = G_SEXT %1(s8)
271  // %3:_(s32) = G_ANYEXT %1(s8)
272  // ... = ... %3(s32)
273  // rewrites to:
274  // %2:_(s32) = G_SEXTLOAD ...
275  // ... = ... %2(s32)
276  replaceRegWith(MRI, UseDstReg, ChosenDstReg);
277  ScheduleForErase.push_back(UseMO.getParent());
278  } else if (Preferred.Ty.getSizeInBits() < UseDstTy.getSizeInBits()) {
279  // If the preferred size is smaller, then keep the extend but extend
280  // from the result of the extending load. For example:
281  // %1:_(s8) = G_LOAD ...
282  // %2:_(s32) = G_SEXT %1(s8)
283  // %3:_(s64) = G_ANYEXT %1(s8)
284  // ... = ... %3(s64)
285  /// rewrites to:
286  // %2:_(s32) = G_SEXTLOAD ...
287  // %3:_(s64) = G_ANYEXT %2:_(s32)
288  // ... = ... %3(s64)
289  replaceRegOpWith(MRI, UseSrcMO, ChosenDstReg);
290  } else {
291  // If the preferred size is large, then insert a truncate. For
292  // example:
293  // %1:_(s8) = G_LOAD ...
294  // %2:_(s64) = G_SEXT %1(s8)
295  // %3:_(s32) = G_ZEXT %1(s8)
296  // ... = ... %3(s32)
297  /// rewrites to:
298  // %2:_(s64) = G_SEXTLOAD ...
299  // %4:_(s8) = G_TRUNC %2:_(s32)
300  // %3:_(s64) = G_ZEXT %2:_(s8)
301  // ... = ... %3(s64)
302  InsertInsnsWithoutSideEffectsBeforeUse(
303  Builder, MI, UseMO,
304  [&](MachineBasicBlock *InsertIntoBB,
305  MachineBasicBlock::iterator InsertBefore) {
306  ScheduleForInsert.emplace_back(&UseMO, InsertIntoBB, InsertBefore);
307  });
308  }
309  continue;
310  }
311  // The use is (one of) the uses of the preferred use we chose earlier.
312  // We're going to update the load to def this value later so just erase
313  // the old extend.
314  ScheduleForErase.push_back(UseMO.getParent());
315  continue;
316  }
317 
318  // The use isn't an extend. Truncate back to the type we originally loaded.
319  // This is free on many targets.
320  InsertInsnsWithoutSideEffectsBeforeUse(
321  Builder, MI, UseMO,
322  [&](MachineBasicBlock *InsertIntoBB,
323  MachineBasicBlock::iterator InsertBefore) {
324  ScheduleForInsert.emplace_back(&UseMO, InsertIntoBB, InsertBefore);
325  });
326  }
327 
329  for (auto &InsertionInfo : ScheduleForInsert) {
330  MachineOperand *UseMO = InsertionInfo.UseMO;
331  MachineBasicBlock *InsertIntoBB = InsertionInfo.InsertIntoBB;
332  MachineBasicBlock::iterator InsertBefore = InsertionInfo.InsertBefore;
333 
334  MachineInstr *PreviouslyEmitted = EmittedInsns.lookup(InsertIntoBB);
335  if (PreviouslyEmitted) {
336  Observer.changingInstr(*UseMO->getParent());
337  UseMO->setReg(PreviouslyEmitted->getOperand(0).getReg());
338  Observer.changedInstr(*UseMO->getParent());
339  continue;
340  }
341 
342  Builder.setInsertPt(*InsertIntoBB, InsertBefore);
343  unsigned NewDstReg = MRI.cloneVirtualRegister(MI.getOperand(0).getReg());
344  MachineInstr *NewMI = Builder.buildTrunc(NewDstReg, ChosenDstReg);
345  EmittedInsns[InsertIntoBB] = NewMI;
346  replaceRegOpWith(MRI, *UseMO, NewDstReg);
347  }
348  for (auto &EraseMI : ScheduleForErase) {
349  Observer.erasingInstr(*EraseMI);
350  EraseMI->eraseFromParent();
351  }
352  MI.getOperand(0).setReg(ChosenDstReg);
353  Observer.changedInstr(MI);
354 }
355 
357  if (tryCombineCopy(MI))
358  return true;
359  return tryCombineExtendingLoads(MI);
360 }
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
bool matchCombineExtendingLoads(MachineInstr &MI, PreferredTuple &MatchInfo)
MachineBasicBlock * getMBB() const
This class represents lattice values for constants.
Definition: AllocatorList.h:23
unsigned getReg() const
getReg - Returns the register number.
bool tryCombine(MachineInstr &MI)
Try to transform MI by using all of the above combine functions.
bool constrainRegAttrs(unsigned Reg, unsigned ConstrainingReg, unsigned MinNumRegs=0)
Constrain the register class or the register bank of the virtual register Reg (and low-level type) to...
LLT getType(unsigned Reg) const
Get the low-level type of Reg or LLT{} if Reg is not a generic (target independent) virtual register...
bool isPHI() const
CombinerHelper(GISelChangeObserver &Observer, MachineIRBuilder &B)
void applyCombineCopy(MachineInstr &MI)
void applyCombineExtendingLoads(MachineInstr &MI, PreferredTuple &MatchInfo)
void eraseFromParent()
Unlink &#39;this&#39; from the containing basic block and delete it.
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:408
void finishedChangingAllUsesOfReg()
All instructions reported as changing by changingAllUsesOfReg() have finished being changed...
Abstract class that contains various methods for clients to notify about changes. ...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
unsigned const MachineRegisterInfo * MRI
void replaceRegWith(MachineRegisterInfo &MRI, unsigned FromReg, unsigned ToReg) const
MachineRegisterInfo::replaceRegWith() and inform the observer of the changes.
MachineInstrBuilder & UseMI
Helper class to build MachineInstr.
void replaceRegOpWith(MachineRegisterInfo &MRI, MachineOperand &FromRegOp, unsigned ToReg) const
Replace a single register operand with a new register and inform the observer of the changes...
bool isValid() const
bool tryCombineExtendingLoads(MachineInstr &MI)
If MI is extend that consumes the result of a load, try to combine it.
MachineInstrBuilder buildCopy(const DstOp &Res, const SrcOp &Op)
Build and insert Res = COPY Op.
bool tryCombineCopy(MachineInstr &MI)
If MI is COPY, try to combine it.
void changingAllUsesOfReg(const MachineRegisterInfo &MRI, unsigned Reg)
All the instructions using the given register are being changed.
void setDesc(const MCInstrDesc &tid)
Replace the instruction descriptor (thus opcode) of the current instruction with a new one...
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:839
MachineInstrBuilder MachineInstrBuilder & DefMI
bool matchCombineCopy(MachineInstr &MI)
unsigned getSizeInBits() const
Returns the total size of the type. Must only be called on sized types.
MachineInstr * MI
This file declares the MachineIRBuilder class.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
virtual void changingInstr(MachineInstr &MI)=0
This instruction is about to be mutated in some way.
void replaceRegWith(unsigned FromReg, unsigned ToReg)
replaceRegWith - Replace all instances of FromReg with ToReg in the machine function.
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:253
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
Definition: MachineInstr.h:63
void emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:644
void setReg(unsigned Reg)
Change the register this operand corresponds to.
iterator getFirstNonPHI()
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
iterator_range< use_instr_iterator > use_instructions(unsigned Reg) const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned getReg(unsigned Idx)
Get the register for the operand index.
print Print MemDeps of function
IRTranslator LLVM IR MI
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:413
virtual void changedInstr(MachineInstr &MI)=0
This instruction was mutated in some way.