LLVM  8.0.1
CombinerHelper.cpp
Go to the documentation of this file.
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 //===----------------------------------------------------------------------===//
17 
18 #define DEBUG_TYPE "gi-combiner"
19 
20 using namespace llvm;
21 
24  : Builder(B), MRI(Builder.getMF().getRegInfo()), Observer(Observer) {}
25 
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 
36 }
37 
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 
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;
64 }
65 
66 namespace {
67 struct PreferredTuple {
68  LLT Ty; // The result type of the extend.
69  unsigned ExtendOpcode; // G_ANYEXT/G_SEXT/G_ZEXT
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(
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()) {
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 
156  struct InsertionPoint {
157  MachineOperand *UseMO;
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
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 
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 
332  if (tryCombineCopy(MI))
333  return true;
334  return tryCombineExtendingLoads(MI);
335 }
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
MachineBasicBlock * getMBB() const
This class represents lattice values for constants.
Definition: AllocatorList.h:24
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 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:409
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:847
MachineInstrBuilder MachineInstrBuilder & DefMI
unsigned getSizeInBits() const
Returns the total size of the type. Must only be called on sized types.
This file declares the MachineIRBuilder class.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
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:254
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:64
void emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:652
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.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
print Print MemDeps of function
IRTranslator LLVM IR MI
#define LLVM_DEBUG(X)
Definition: Debug.h:123
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:414
virtual void changedInstr(MachineInstr &MI)=0
This instruction was mutated in some way.