LLVM  10.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  Register 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  Register 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  MachineOperand &UseMO)>
136  Inserter) {
137  MachineInstr &UseMI = *UseMO.getParent();
138 
139  MachineBasicBlock *InsertBB = UseMI.getParent();
140 
141  // If the use is a PHI then we want the predecessor block instead.
142  if (UseMI.isPHI()) {
143  MachineOperand *PredBB = std::next(&UseMO);
144  InsertBB = PredBB->getMBB();
145  }
146 
147  // If the block is the same block as the def then we want to insert just after
148  // the def instead of at the start of the block.
149  if (InsertBB == DefMI.getParent()) {
151  Inserter(InsertBB, std::next(InsertPt), UseMO);
152  return;
153  }
154 
155  // Otherwise we want the start of the BB
156  Inserter(InsertBB, InsertBB->getFirstNonPHI(), UseMO);
157 }
158 } // end anonymous namespace
159 
161  PreferredTuple Preferred;
162  if (matchCombineExtendingLoads(MI, Preferred)) {
163  applyCombineExtendingLoads(MI, Preferred);
164  return true;
165  }
166  return false;
167 }
168 
170  PreferredTuple &Preferred) {
171  // We match the loads and follow the uses to the extend instead of matching
172  // the extends and following the def to the load. This is because the load
173  // must remain in the same position for correctness (unless we also add code
174  // to find a safe place to sink it) whereas the extend is freely movable.
175  // It also prevents us from duplicating the load for the volatile case or just
176  // for performance.
177 
178  if (MI.getOpcode() != TargetOpcode::G_LOAD &&
179  MI.getOpcode() != TargetOpcode::G_SEXTLOAD &&
180  MI.getOpcode() != TargetOpcode::G_ZEXTLOAD)
181  return false;
182 
183  auto &LoadValue = MI.getOperand(0);
184  assert(LoadValue.isReg() && "Result wasn't a register?");
185 
186  LLT LoadValueTy = MRI.getType(LoadValue.getReg());
187  if (!LoadValueTy.isScalar())
188  return false;
189 
190  // Most architectures are going to legalize <s8 loads into at least a 1 byte
191  // load, and the MMOs can only describe memory accesses in multiples of bytes.
192  // If we try to perform extload combining on those, we can end up with
193  // %a(s8) = extload %ptr (load 1 byte from %ptr)
194  // ... which is an illegal extload instruction.
195  if (LoadValueTy.getSizeInBits() < 8)
196  return false;
197 
198  // For non power-of-2 types, they will very likely be legalized into multiple
199  // loads. Don't bother trying to match them into extending loads.
200  if (!isPowerOf2_32(LoadValueTy.getSizeInBits()))
201  return false;
202 
203  // Find the preferred type aside from the any-extends (unless it's the only
204  // one) and non-extending ops. We'll emit an extending load to that type and
205  // and emit a variant of (extend (trunc X)) for the others according to the
206  // relative type sizes. At the same time, pick an extend to use based on the
207  // extend involved in the chosen type.
208  unsigned PreferredOpcode = MI.getOpcode() == TargetOpcode::G_LOAD
209  ? TargetOpcode::G_ANYEXT
210  : MI.getOpcode() == TargetOpcode::G_SEXTLOAD
211  ? TargetOpcode::G_SEXT
212  : TargetOpcode::G_ZEXT;
213  Preferred = {LLT(), PreferredOpcode, nullptr};
214  for (auto &UseMI : MRI.use_instructions(LoadValue.getReg())) {
215  if (UseMI.getOpcode() == TargetOpcode::G_SEXT ||
216  UseMI.getOpcode() == TargetOpcode::G_ZEXT ||
217  UseMI.getOpcode() == TargetOpcode::G_ANYEXT) {
218  Preferred = ChoosePreferredUse(Preferred,
219  MRI.getType(UseMI.getOperand(0).getReg()),
220  UseMI.getOpcode(), &UseMI);
221  }
222  }
223 
224  // There were no extends
225  if (!Preferred.MI)
226  return false;
227  // It should be impossible to chose an extend without selecting a different
228  // type since by definition the result of an extend is larger.
229  assert(Preferred.Ty != LoadValueTy && "Extending to same type?");
230 
231  LLVM_DEBUG(dbgs() << "Preferred use is: " << *Preferred.MI);
232  return true;
233 }
234 
236  PreferredTuple &Preferred) {
237  // Rewrite the load to the chosen extending load.
238  Register ChosenDstReg = Preferred.MI->getOperand(0).getReg();
239 
240  // Inserter to insert a truncate back to the original type at a given point
241  // with some basic CSE to limit truncate duplication to one per BB.
243  auto InsertTruncAt = [&](MachineBasicBlock *InsertIntoBB,
244  MachineBasicBlock::iterator InsertBefore,
245  MachineOperand &UseMO) {
246  MachineInstr *PreviouslyEmitted = EmittedInsns.lookup(InsertIntoBB);
247  if (PreviouslyEmitted) {
248  Observer.changingInstr(*UseMO.getParent());
249  UseMO.setReg(PreviouslyEmitted->getOperand(0).getReg());
250  Observer.changedInstr(*UseMO.getParent());
251  return;
252  }
253 
254  Builder.setInsertPt(*InsertIntoBB, InsertBefore);
255  Register NewDstReg = MRI.cloneVirtualRegister(MI.getOperand(0).getReg());
256  MachineInstr *NewMI = Builder.buildTrunc(NewDstReg, ChosenDstReg);
257  EmittedInsns[InsertIntoBB] = NewMI;
258  replaceRegOpWith(MRI, UseMO, NewDstReg);
259  };
260 
261  Observer.changingInstr(MI);
262  MI.setDesc(
263  Builder.getTII().get(Preferred.ExtendOpcode == TargetOpcode::G_SEXT
264  ? TargetOpcode::G_SEXTLOAD
265  : Preferred.ExtendOpcode == TargetOpcode::G_ZEXT
266  ? TargetOpcode::G_ZEXTLOAD
267  : TargetOpcode::G_LOAD));
268 
269  // Rewrite all the uses to fix up the types.
270  auto &LoadValue = MI.getOperand(0);
272  for (auto &UseMO : MRI.use_operands(LoadValue.getReg()))
273  Uses.push_back(&UseMO);
274 
275  for (auto *UseMO : Uses) {
276  MachineInstr *UseMI = UseMO->getParent();
277 
278  // If the extend is compatible with the preferred extend then we should fix
279  // up the type and extend so that it uses the preferred use.
280  if (UseMI->getOpcode() == Preferred.ExtendOpcode ||
281  UseMI->getOpcode() == TargetOpcode::G_ANYEXT) {
282  unsigned UseDstReg = UseMI->getOperand(0).getReg();
283  MachineOperand &UseSrcMO = UseMI->getOperand(1);
284  const LLT &UseDstTy = MRI.getType(UseDstReg);
285  if (UseDstReg != ChosenDstReg) {
286  if (Preferred.Ty == UseDstTy) {
287  // If the use has the same type as the preferred use, then merge
288  // the vregs and erase the extend. For example:
289  // %1:_(s8) = G_LOAD ...
290  // %2:_(s32) = G_SEXT %1(s8)
291  // %3:_(s32) = G_ANYEXT %1(s8)
292  // ... = ... %3(s32)
293  // rewrites to:
294  // %2:_(s32) = G_SEXTLOAD ...
295  // ... = ... %2(s32)
296  replaceRegWith(MRI, UseDstReg, ChosenDstReg);
297  Observer.erasingInstr(*UseMO->getParent());
298  UseMO->getParent()->eraseFromParent();
299  } else if (Preferred.Ty.getSizeInBits() < UseDstTy.getSizeInBits()) {
300  // If the preferred size is smaller, then keep the extend but extend
301  // from the result of the extending load. For example:
302  // %1:_(s8) = G_LOAD ...
303  // %2:_(s32) = G_SEXT %1(s8)
304  // %3:_(s64) = G_ANYEXT %1(s8)
305  // ... = ... %3(s64)
306  /// rewrites to:
307  // %2:_(s32) = G_SEXTLOAD ...
308  // %3:_(s64) = G_ANYEXT %2:_(s32)
309  // ... = ... %3(s64)
310  replaceRegOpWith(MRI, UseSrcMO, ChosenDstReg);
311  } else {
312  // If the preferred size is large, then insert a truncate. For
313  // example:
314  // %1:_(s8) = G_LOAD ...
315  // %2:_(s64) = G_SEXT %1(s8)
316  // %3:_(s32) = G_ZEXT %1(s8)
317  // ... = ... %3(s32)
318  /// rewrites to:
319  // %2:_(s64) = G_SEXTLOAD ...
320  // %4:_(s8) = G_TRUNC %2:_(s32)
321  // %3:_(s64) = G_ZEXT %2:_(s8)
322  // ... = ... %3(s64)
323  InsertInsnsWithoutSideEffectsBeforeUse(Builder, MI, *UseMO,
324  InsertTruncAt);
325  }
326  continue;
327  }
328  // The use is (one of) the uses of the preferred use we chose earlier.
329  // We're going to update the load to def this value later so just erase
330  // the old extend.
331  Observer.erasingInstr(*UseMO->getParent());
332  UseMO->getParent()->eraseFromParent();
333  continue;
334  }
335 
336  // The use isn't an extend. Truncate back to the type we originally loaded.
337  // This is free on many targets.
338  InsertInsnsWithoutSideEffectsBeforeUse(Builder, MI, *UseMO, InsertTruncAt);
339  }
340 
341  MI.getOperand(0).setReg(ChosenDstReg);
342  Observer.changedInstr(MI);
343 }
344 
346  assert(MI.getOpcode() == TargetOpcode::G_BR && "Expected a G_BR");
347  // Try to match the following:
348  // bb1:
349  // %c(s32) = G_ICMP pred, %a, %b
350  // %c1(s1) = G_TRUNC %c(s32)
351  // G_BRCOND %c1, %bb2
352  // G_BR %bb3
353  // bb2:
354  // ...
355  // bb3:
356 
357  // The above pattern does not have a fall through to the successor bb2, always
358  // resulting in a branch no matter which path is taken. Here we try to find
359  // and replace that pattern with conditional branch to bb3 and otherwise
360  // fallthrough to bb2.
361 
362  MachineBasicBlock *MBB = MI.getParent();
364  if (BrIt == MBB->begin())
365  return false;
366  assert(std::next(BrIt) == MBB->end() && "expected G_BR to be a terminator");
367 
368  MachineInstr *BrCond = &*std::prev(BrIt);
369  if (BrCond->getOpcode() != TargetOpcode::G_BRCOND)
370  return false;
371 
372  // Check that the next block is the conditional branch target.
373  if (!MBB->isLayoutSuccessor(BrCond->getOperand(1).getMBB()))
374  return false;
375 
376  MachineInstr *CmpMI = MRI.getVRegDef(BrCond->getOperand(0).getReg());
377  if (!CmpMI || CmpMI->getOpcode() != TargetOpcode::G_ICMP ||
378  !MRI.hasOneUse(CmpMI->getOperand(0).getReg()))
379  return false;
380  return true;
381 }
382 
384  if (!matchCombineBr(MI))
385  return false;
386  MachineBasicBlock *BrTarget = MI.getOperand(0).getMBB();
388  MachineInstr *BrCond = &*std::prev(BrIt);
389  MachineInstr *CmpMI = MRI.getVRegDef(BrCond->getOperand(0).getReg());
390 
393 
394  // Invert the G_ICMP condition.
395  Observer.changingInstr(*CmpMI);
396  CmpMI->getOperand(1).setPredicate(InversePred);
397  Observer.changedInstr(*CmpMI);
398 
399  // Change the conditional branch target.
400  Observer.changingInstr(*BrCond);
401  BrCond->getOperand(1).setMBB(BrTarget);
402  Observer.changedInstr(*BrCond);
403  MI.eraseFromParent();
404  return true;
405 }
406 
408  if (tryCombineCopy(MI))
409  return true;
410  return tryCombineExtendingLoads(MI);
411 }
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
Register getReg(unsigned Idx) const
Get the register for the operand index.
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 setInsertPt(MachineBasicBlock &MBB, MachineBasicBlock::iterator II)
Set the insertion point before the specified position.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE, etc.
Definition: InstrTypes.h:831
void eraseFromParent()
Unlink &#39;this&#39; from the containing basic block and delete it.
bool tryCombineBr(MachineInstr &MI)
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:411
MachineInstr * getVRegDef(unsigned Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
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
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:428
MachineInstrBuilder & UseMI
Helper class to build MachineInstr.
void setMBB(MachineBasicBlock *MBB)
bool isValid() const
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:732
bool tryCombineExtendingLoads(MachineInstr &MI)
If MI is extend that consumes the result of a load, try to combine it.
virtual void erasingInstr(MachineInstr &MI)=0
An instruction is about to be erased.
MachineInstrBuilder buildCopy(const DstOp &Res, const SrcOp &Op)
Build and insert Res = COPY Op.
MachineInstrBuilder buildTrunc(const DstOp &Res, const SrcOp &Op)
Build and insert Res = G_TRUNC 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 replaceRegWith(MachineRegisterInfo &MRI, Register FromReg, Register ToReg) const
MachineRegisterInfo::replaceRegWith() and inform the observer of the changes.
void setDesc(const MCInstrDesc &tid)
Replace the instruction descriptor (thus opcode) of the current instruction with a new one...
iterator_range< use_iterator > use_operands(unsigned Reg) const
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:837
MachineInstrBuilder MachineInstrBuilder & DefMI
bool matchCombineCopy(MachineInstr &MI)
unsigned getSizeInBits() const
Returns the total size of the type. Must only be called on sized types.
const TargetInstrInfo & getTII()
MachineInstr * MI
Register cloneVirtualRegister(Register VReg, StringRef Name="")
Create and return a new virtual register in the function with the same attributes as the given regist...
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:256
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
void setPredicate(unsigned Predicate)
Representation of each machine instruction.
Definition: MachineInstr.h:64
bool hasOneUse(unsigned RegNo) const
hasOneUse - Return true if there is exactly one instruction using the specified register.
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode...
Definition: MCInstrInfo.h:44
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.
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:211
iterator_range< use_instr_iterator > use_instructions(unsigned Reg) const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool matchCombineBr(MachineInstr &MI)
print Print MemDeps of function
IRTranslator LLVM IR MI
Register getReg() const
getReg - Returns the register number.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:416
virtual void changedInstr(MachineInstr &MI)=0
This instruction was mutated in some way.
Wrapper class representing virtual and physical registers.
Definition: Register.h:18
void replaceRegOpWith(MachineRegisterInfo &MRI, MachineOperand &FromRegOp, Register ToReg) const
Replace a single register operand with a new register and inform the observer of the changes...
unsigned getPredicate() const