xref: /llvm-project/llvm/lib/CodeGen/MachineInstr.cpp (revision 1d7b41361ffa208291119cd145a62a366adac569)
1 //===- lib/CodeGen/MachineInstr.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 //===----------------------------------------------------------------------===//
8 //
9 // Methods common to all machine instructions.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "llvm/CodeGen/MachineInstr.h"
14 #include "llvm/ADT/APFloat.h"
15 #include "llvm/ADT/ArrayRef.h"
16 #include "llvm/ADT/FoldingSet.h"
17 #include "llvm/ADT/Hashing.h"
18 #include "llvm/ADT/None.h"
19 #include "llvm/ADT/STLExtras.h"
20 #include "llvm/ADT/SmallBitVector.h"
21 #include "llvm/ADT/SmallString.h"
22 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/Analysis/AliasAnalysis.h"
24 #include "llvm/Analysis/Loads.h"
25 #include "llvm/Analysis/MemoryLocation.h"
26 #include "llvm/CodeGen/GlobalISel/RegisterBank.h"
27 #include "llvm/CodeGen/MachineBasicBlock.h"
28 #include "llvm/CodeGen/MachineFrameInfo.h"
29 #include "llvm/CodeGen/MachineFunction.h"
30 #include "llvm/CodeGen/MachineInstrBuilder.h"
31 #include "llvm/CodeGen/MachineInstrBundle.h"
32 #include "llvm/CodeGen/MachineMemOperand.h"
33 #include "llvm/CodeGen/MachineModuleInfo.h"
34 #include "llvm/CodeGen/MachineOperand.h"
35 #include "llvm/CodeGen/MachineRegisterInfo.h"
36 #include "llvm/CodeGen/PseudoSourceValue.h"
37 #include "llvm/CodeGen/TargetInstrInfo.h"
38 #include "llvm/CodeGen/TargetRegisterInfo.h"
39 #include "llvm/CodeGen/TargetSubtargetInfo.h"
40 #include "llvm/Config/llvm-config.h"
41 #include "llvm/IR/Constants.h"
42 #include "llvm/IR/DebugInfoMetadata.h"
43 #include "llvm/IR/DebugLoc.h"
44 #include "llvm/IR/DerivedTypes.h"
45 #include "llvm/IR/Function.h"
46 #include "llvm/IR/InlineAsm.h"
47 #include "llvm/IR/InstrTypes.h"
48 #include "llvm/IR/Intrinsics.h"
49 #include "llvm/IR/LLVMContext.h"
50 #include "llvm/IR/Metadata.h"
51 #include "llvm/IR/Module.h"
52 #include "llvm/IR/ModuleSlotTracker.h"
53 #include "llvm/IR/Operator.h"
54 #include "llvm/IR/Type.h"
55 #include "llvm/IR/Value.h"
56 #include "llvm/MC/MCInstrDesc.h"
57 #include "llvm/MC/MCRegisterInfo.h"
58 #include "llvm/MC/MCSymbol.h"
59 #include "llvm/Support/Casting.h"
60 #include "llvm/Support/CommandLine.h"
61 #include "llvm/Support/Compiler.h"
62 #include "llvm/Support/Debug.h"
63 #include "llvm/Support/ErrorHandling.h"
64 #include "llvm/Support/LowLevelTypeImpl.h"
65 #include "llvm/Support/MathExtras.h"
66 #include "llvm/Support/raw_ostream.h"
67 #include "llvm/Target/TargetIntrinsicInfo.h"
68 #include "llvm/Target/TargetMachine.h"
69 #include <algorithm>
70 #include <cassert>
71 #include <cstddef>
72 #include <cstdint>
73 #include <cstring>
74 #include <iterator>
75 #include <utility>
76 
77 using namespace llvm;
78 
79 static const MachineFunction *getMFIfAvailable(const MachineInstr &MI) {
80   if (const MachineBasicBlock *MBB = MI.getParent())
81     if (const MachineFunction *MF = MBB->getParent())
82       return MF;
83   return nullptr;
84 }
85 
86 // Try to crawl up to the machine function and get TRI and IntrinsicInfo from
87 // it.
88 static void tryToGetTargetInfo(const MachineInstr &MI,
89                                const TargetRegisterInfo *&TRI,
90                                const MachineRegisterInfo *&MRI,
91                                const TargetIntrinsicInfo *&IntrinsicInfo,
92                                const TargetInstrInfo *&TII) {
93 
94   if (const MachineFunction *MF = getMFIfAvailable(MI)) {
95     TRI = MF->getSubtarget().getRegisterInfo();
96     MRI = &MF->getRegInfo();
97     IntrinsicInfo = MF->getTarget().getIntrinsicInfo();
98     TII = MF->getSubtarget().getInstrInfo();
99   }
100 }
101 
102 void MachineInstr::addImplicitDefUseOperands(MachineFunction &MF) {
103   if (MCID->ImplicitDefs)
104     for (const MCPhysReg *ImpDefs = MCID->getImplicitDefs(); *ImpDefs;
105            ++ImpDefs)
106       addOperand(MF, MachineOperand::CreateReg(*ImpDefs, true, true));
107   if (MCID->ImplicitUses)
108     for (const MCPhysReg *ImpUses = MCID->getImplicitUses(); *ImpUses;
109            ++ImpUses)
110       addOperand(MF, MachineOperand::CreateReg(*ImpUses, false, true));
111 }
112 
113 /// MachineInstr ctor - This constructor creates a MachineInstr and adds the
114 /// implicit operands. It reserves space for the number of operands specified by
115 /// the MCInstrDesc.
116 MachineInstr::MachineInstr(MachineFunction &MF, const MCInstrDesc &tid,
117                            DebugLoc dl, bool NoImp)
118     : MCID(&tid), debugLoc(std::move(dl)) {
119   assert(debugLoc.hasTrivialDestructor() && "Expected trivial destructor");
120 
121   // Reserve space for the expected number of operands.
122   if (unsigned NumOps = MCID->getNumOperands() +
123     MCID->getNumImplicitDefs() + MCID->getNumImplicitUses()) {
124     CapOperands = OperandCapacity::get(NumOps);
125     Operands = MF.allocateOperandArray(CapOperands);
126   }
127 
128   if (!NoImp)
129     addImplicitDefUseOperands(MF);
130 }
131 
132 /// MachineInstr ctor - Copies MachineInstr arg exactly
133 ///
134 MachineInstr::MachineInstr(MachineFunction &MF, const MachineInstr &MI)
135     : MCID(&MI.getDesc()), Info(MI.Info), debugLoc(MI.getDebugLoc()) {
136   assert(debugLoc.hasTrivialDestructor() && "Expected trivial destructor");
137 
138   CapOperands = OperandCapacity::get(MI.getNumOperands());
139   Operands = MF.allocateOperandArray(CapOperands);
140 
141   // Copy operands.
142   for (const MachineOperand &MO : MI.operands())
143     addOperand(MF, MO);
144 
145   // Copy all the sensible flags.
146   setFlags(MI.Flags);
147 }
148 
149 /// getRegInfo - If this instruction is embedded into a MachineFunction,
150 /// return the MachineRegisterInfo object for the current function, otherwise
151 /// return null.
152 MachineRegisterInfo *MachineInstr::getRegInfo() {
153   if (MachineBasicBlock *MBB = getParent())
154     return &MBB->getParent()->getRegInfo();
155   return nullptr;
156 }
157 
158 /// RemoveRegOperandsFromUseLists - Unlink all of the register operands in
159 /// this instruction from their respective use lists.  This requires that the
160 /// operands already be on their use lists.
161 void MachineInstr::RemoveRegOperandsFromUseLists(MachineRegisterInfo &MRI) {
162   for (MachineOperand &MO : operands())
163     if (MO.isReg())
164       MRI.removeRegOperandFromUseList(&MO);
165 }
166 
167 /// AddRegOperandsToUseLists - Add all of the register operands in
168 /// this instruction from their respective use lists.  This requires that the
169 /// operands not be on their use lists yet.
170 void MachineInstr::AddRegOperandsToUseLists(MachineRegisterInfo &MRI) {
171   for (MachineOperand &MO : operands())
172     if (MO.isReg())
173       MRI.addRegOperandToUseList(&MO);
174 }
175 
176 void MachineInstr::addOperand(const MachineOperand &Op) {
177   MachineBasicBlock *MBB = getParent();
178   assert(MBB && "Use MachineInstrBuilder to add operands to dangling instrs");
179   MachineFunction *MF = MBB->getParent();
180   assert(MF && "Use MachineInstrBuilder to add operands to dangling instrs");
181   addOperand(*MF, Op);
182 }
183 
184 /// Move NumOps MachineOperands from Src to Dst, with support for overlapping
185 /// ranges. If MRI is non-null also update use-def chains.
186 static void moveOperands(MachineOperand *Dst, MachineOperand *Src,
187                          unsigned NumOps, MachineRegisterInfo *MRI) {
188   if (MRI)
189     return MRI->moveOperands(Dst, Src, NumOps);
190 
191   // MachineOperand is a trivially copyable type so we can just use memmove.
192   std::memmove(Dst, Src, NumOps * sizeof(MachineOperand));
193 }
194 
195 /// addOperand - Add the specified operand to the instruction.  If it is an
196 /// implicit operand, it is added to the end of the operand list.  If it is
197 /// an explicit operand it is added at the end of the explicit operand list
198 /// (before the first implicit operand).
199 void MachineInstr::addOperand(MachineFunction &MF, const MachineOperand &Op) {
200   assert(MCID && "Cannot add operands before providing an instr descriptor");
201 
202   // Check if we're adding one of our existing operands.
203   if (&Op >= Operands && &Op < Operands + NumOperands) {
204     // This is unusual: MI->addOperand(MI->getOperand(i)).
205     // If adding Op requires reallocating or moving existing operands around,
206     // the Op reference could go stale. Support it by copying Op.
207     MachineOperand CopyOp(Op);
208     return addOperand(MF, CopyOp);
209   }
210 
211   // Find the insert location for the new operand.  Implicit registers go at
212   // the end, everything else goes before the implicit regs.
213   //
214   // FIXME: Allow mixed explicit and implicit operands on inline asm.
215   // InstrEmitter::EmitSpecialNode() is marking inline asm clobbers as
216   // implicit-defs, but they must not be moved around.  See the FIXME in
217   // InstrEmitter.cpp.
218   unsigned OpNo = getNumOperands();
219   bool isImpReg = Op.isReg() && Op.isImplicit();
220   if (!isImpReg && !isInlineAsm()) {
221     while (OpNo && Operands[OpNo-1].isReg() && Operands[OpNo-1].isImplicit()) {
222       --OpNo;
223       assert(!Operands[OpNo].isTied() && "Cannot move tied operands");
224     }
225   }
226 
227 #ifndef NDEBUG
228   bool isDebugOp = Op.getType() == MachineOperand::MO_Metadata ||
229                    Op.getType() == MachineOperand::MO_MCSymbol;
230   // OpNo now points as the desired insertion point.  Unless this is a variadic
231   // instruction, only implicit regs are allowed beyond MCID->getNumOperands().
232   // RegMask operands go between the explicit and implicit operands.
233   assert((isImpReg || Op.isRegMask() || MCID->isVariadic() ||
234           OpNo < MCID->getNumOperands() || isDebugOp) &&
235          "Trying to add an operand to a machine instr that is already done!");
236 #endif
237 
238   MachineRegisterInfo *MRI = getRegInfo();
239 
240   // Determine if the Operands array needs to be reallocated.
241   // Save the old capacity and operand array.
242   OperandCapacity OldCap = CapOperands;
243   MachineOperand *OldOperands = Operands;
244   if (!OldOperands || OldCap.getSize() == getNumOperands()) {
245     CapOperands = OldOperands ? OldCap.getNext() : OldCap.get(1);
246     Operands = MF.allocateOperandArray(CapOperands);
247     // Move the operands before the insertion point.
248     if (OpNo)
249       moveOperands(Operands, OldOperands, OpNo, MRI);
250   }
251 
252   // Move the operands following the insertion point.
253   if (OpNo != NumOperands)
254     moveOperands(Operands + OpNo + 1, OldOperands + OpNo, NumOperands - OpNo,
255                  MRI);
256   ++NumOperands;
257 
258   // Deallocate the old operand array.
259   if (OldOperands != Operands && OldOperands)
260     MF.deallocateOperandArray(OldCap, OldOperands);
261 
262   // Copy Op into place. It still needs to be inserted into the MRI use lists.
263   MachineOperand *NewMO = new (Operands + OpNo) MachineOperand(Op);
264   NewMO->ParentMI = this;
265 
266   // When adding a register operand, tell MRI about it.
267   if (NewMO->isReg()) {
268     // Ensure isOnRegUseList() returns false, regardless of Op's status.
269     NewMO->Contents.Reg.Prev = nullptr;
270     // Ignore existing ties. This is not a property that can be copied.
271     NewMO->TiedTo = 0;
272     // Add the new operand to MRI, but only for instructions in an MBB.
273     if (MRI)
274       MRI->addRegOperandToUseList(NewMO);
275     // The MCID operand information isn't accurate until we start adding
276     // explicit operands. The implicit operands are added first, then the
277     // explicits are inserted before them.
278     if (!isImpReg) {
279       // Tie uses to defs as indicated in MCInstrDesc.
280       if (NewMO->isUse()) {
281         int DefIdx = MCID->getOperandConstraint(OpNo, MCOI::TIED_TO);
282         if (DefIdx != -1)
283           tieOperands(DefIdx, OpNo);
284       }
285       // If the register operand is flagged as early, mark the operand as such.
286       if (MCID->getOperandConstraint(OpNo, MCOI::EARLY_CLOBBER) != -1)
287         NewMO->setIsEarlyClobber(true);
288     }
289   }
290 }
291 
292 /// RemoveOperand - Erase an operand  from an instruction, leaving it with one
293 /// fewer operand than it started with.
294 ///
295 void MachineInstr::RemoveOperand(unsigned OpNo) {
296   assert(OpNo < getNumOperands() && "Invalid operand number");
297   untieRegOperand(OpNo);
298 
299 #ifndef NDEBUG
300   // Moving tied operands would break the ties.
301   for (unsigned i = OpNo + 1, e = getNumOperands(); i != e; ++i)
302     if (Operands[i].isReg())
303       assert(!Operands[i].isTied() && "Cannot move tied operands");
304 #endif
305 
306   MachineRegisterInfo *MRI = getRegInfo();
307   if (MRI && Operands[OpNo].isReg())
308     MRI->removeRegOperandFromUseList(Operands + OpNo);
309 
310   // Don't call the MachineOperand destructor. A lot of this code depends on
311   // MachineOperand having a trivial destructor anyway, and adding a call here
312   // wouldn't make it 'destructor-correct'.
313 
314   if (unsigned N = NumOperands - 1 - OpNo)
315     moveOperands(Operands + OpNo, Operands + OpNo + 1, N, MRI);
316   --NumOperands;
317 }
318 
319 void MachineInstr::dropMemRefs(MachineFunction &MF) {
320   if (memoperands_empty())
321     return;
322 
323   // See if we can just drop all of our extra info.
324   if (!getPreInstrSymbol() && !getPostInstrSymbol()) {
325     Info.clear();
326     return;
327   }
328   if (!getPostInstrSymbol()) {
329     Info.set<EIIK_PreInstrSymbol>(getPreInstrSymbol());
330     return;
331   }
332   if (!getPreInstrSymbol()) {
333     Info.set<EIIK_PostInstrSymbol>(getPostInstrSymbol());
334     return;
335   }
336 
337   // Otherwise allocate a fresh extra info with just these symbols.
338   Info.set<EIIK_OutOfLine>(
339       MF.createMIExtraInfo({}, getPreInstrSymbol(), getPostInstrSymbol()));
340 }
341 
342 void MachineInstr::setMemRefs(MachineFunction &MF,
343                               ArrayRef<MachineMemOperand *> MMOs) {
344   if (MMOs.empty()) {
345     dropMemRefs(MF);
346     return;
347   }
348 
349   // Try to store a single MMO inline.
350   if (MMOs.size() == 1 && !getPreInstrSymbol() && !getPostInstrSymbol()) {
351     Info.set<EIIK_MMO>(MMOs[0]);
352     return;
353   }
354 
355   // Otherwise create an extra info struct with all of our info.
356   Info.set<EIIK_OutOfLine>(
357       MF.createMIExtraInfo(MMOs, getPreInstrSymbol(), getPostInstrSymbol()));
358 }
359 
360 void MachineInstr::addMemOperand(MachineFunction &MF,
361                                  MachineMemOperand *MO) {
362   SmallVector<MachineMemOperand *, 2> MMOs;
363   MMOs.append(memoperands_begin(), memoperands_end());
364   MMOs.push_back(MO);
365   setMemRefs(MF, MMOs);
366 }
367 
368 void MachineInstr::cloneMemRefs(MachineFunction &MF, const MachineInstr &MI) {
369   if (this == &MI)
370     // Nothing to do for a self-clone!
371     return;
372 
373   assert(&MF == MI.getMF() &&
374          "Invalid machine functions when cloning memory refrences!");
375   // See if we can just steal the extra info already allocated for the
376   // instruction. We can do this whenever the pre- and post-instruction symbols
377   // are the same (including null).
378   if (getPreInstrSymbol() == MI.getPreInstrSymbol() &&
379       getPostInstrSymbol() == MI.getPostInstrSymbol()) {
380     Info = MI.Info;
381     return;
382   }
383 
384   // Otherwise, fall back on a copy-based clone.
385   setMemRefs(MF, MI.memoperands());
386 }
387 
388 /// Check to see if the MMOs pointed to by the two MemRefs arrays are
389 /// identical.
390 static bool hasIdenticalMMOs(ArrayRef<MachineMemOperand *> LHS,
391                              ArrayRef<MachineMemOperand *> RHS) {
392   if (LHS.size() != RHS.size())
393     return false;
394 
395   auto LHSPointees = make_pointee_range(LHS);
396   auto RHSPointees = make_pointee_range(RHS);
397   return std::equal(LHSPointees.begin(), LHSPointees.end(),
398                     RHSPointees.begin());
399 }
400 
401 void MachineInstr::cloneMergedMemRefs(MachineFunction &MF,
402                                       ArrayRef<const MachineInstr *> MIs) {
403   // Try handling easy numbers of MIs with simpler mechanisms.
404   if (MIs.empty()) {
405     dropMemRefs(MF);
406     return;
407   }
408   if (MIs.size() == 1) {
409     cloneMemRefs(MF, *MIs[0]);
410     return;
411   }
412   // Because an empty memoperands list provides *no* information and must be
413   // handled conservatively (assuming the instruction can do anything), the only
414   // way to merge with it is to drop all other memoperands.
415   if (MIs[0]->memoperands_empty()) {
416     dropMemRefs(MF);
417     return;
418   }
419 
420   // Handle the general case.
421   SmallVector<MachineMemOperand *, 2> MergedMMOs;
422   // Start with the first instruction.
423   assert(&MF == MIs[0]->getMF() &&
424          "Invalid machine functions when cloning memory references!");
425   MergedMMOs.append(MIs[0]->memoperands_begin(), MIs[0]->memoperands_end());
426   // Now walk all the other instructions and accumulate any different MMOs.
427   for (const MachineInstr &MI : make_pointee_range(MIs.slice(1))) {
428     assert(&MF == MI.getMF() &&
429            "Invalid machine functions when cloning memory references!");
430 
431     // Skip MIs with identical operands to the first. This is a somewhat
432     // arbitrary hack but will catch common cases without being quadratic.
433     // TODO: We could fully implement merge semantics here if needed.
434     if (hasIdenticalMMOs(MIs[0]->memoperands(), MI.memoperands()))
435       continue;
436 
437     // Because an empty memoperands list provides *no* information and must be
438     // handled conservatively (assuming the instruction can do anything), the
439     // only way to merge with it is to drop all other memoperands.
440     if (MI.memoperands_empty()) {
441       dropMemRefs(MF);
442       return;
443     }
444 
445     // Otherwise accumulate these into our temporary buffer of the merged state.
446     MergedMMOs.append(MI.memoperands_begin(), MI.memoperands_end());
447   }
448 
449   setMemRefs(MF, MergedMMOs);
450 }
451 
452 void MachineInstr::setPreInstrSymbol(MachineFunction &MF, MCSymbol *Symbol) {
453   MCSymbol *OldSymbol = getPreInstrSymbol();
454   if (OldSymbol == Symbol)
455     return;
456   if (OldSymbol && !Symbol) {
457     // We're removing a symbol rather than adding one. Try to clean up any
458     // extra info carried around.
459     if (Info.is<EIIK_PreInstrSymbol>()) {
460       Info.clear();
461       return;
462     }
463 
464     if (memoperands_empty()) {
465       assert(getPostInstrSymbol() &&
466              "Should never have only a single symbol allocated out-of-line!");
467       Info.set<EIIK_PostInstrSymbol>(getPostInstrSymbol());
468       return;
469     }
470 
471     // Otherwise fallback on the generic update.
472   } else if (!Info || Info.is<EIIK_PreInstrSymbol>()) {
473     // If we don't have any other extra info, we can store this inline.
474     Info.set<EIIK_PreInstrSymbol>(Symbol);
475     return;
476   }
477 
478   // Otherwise, allocate a full new set of extra info.
479   // FIXME: Maybe we should make the symbols in the extra info mutable?
480   Info.set<EIIK_OutOfLine>(
481       MF.createMIExtraInfo(memoperands(), Symbol, getPostInstrSymbol()));
482 }
483 
484 void MachineInstr::setPostInstrSymbol(MachineFunction &MF, MCSymbol *Symbol) {
485   MCSymbol *OldSymbol = getPostInstrSymbol();
486   if (OldSymbol == Symbol)
487     return;
488   if (OldSymbol && !Symbol) {
489     // We're removing a symbol rather than adding one. Try to clean up any
490     // extra info carried around.
491     if (Info.is<EIIK_PostInstrSymbol>()) {
492       Info.clear();
493       return;
494     }
495 
496     if (memoperands_empty()) {
497       assert(getPreInstrSymbol() &&
498              "Should never have only a single symbol allocated out-of-line!");
499       Info.set<EIIK_PreInstrSymbol>(getPreInstrSymbol());
500       return;
501     }
502 
503     // Otherwise fallback on the generic update.
504   } else if (!Info || Info.is<EIIK_PostInstrSymbol>()) {
505     // If we don't have any other extra info, we can store this inline.
506     Info.set<EIIK_PostInstrSymbol>(Symbol);
507     return;
508   }
509 
510   // Otherwise, allocate a full new set of extra info.
511   // FIXME: Maybe we should make the symbols in the extra info mutable?
512   Info.set<EIIK_OutOfLine>(
513       MF.createMIExtraInfo(memoperands(), getPreInstrSymbol(), Symbol));
514 }
515 
516 void MachineInstr::cloneInstrSymbols(MachineFunction &MF,
517                                      const MachineInstr &MI) {
518   if (this == &MI)
519     // Nothing to do for a self-clone!
520     return;
521 
522   assert(&MF == MI.getMF() &&
523          "Invalid machine functions when cloning instruction symbols!");
524 
525   setPreInstrSymbol(MF, MI.getPreInstrSymbol());
526   setPostInstrSymbol(MF, MI.getPostInstrSymbol());
527 }
528 
529 uint16_t MachineInstr::mergeFlagsWith(const MachineInstr &Other) const {
530   // For now, the just return the union of the flags. If the flags get more
531   // complicated over time, we might need more logic here.
532   return getFlags() | Other.getFlags();
533 }
534 
535 uint16_t MachineInstr::copyFlagsFromInstruction(const Instruction &I) {
536   uint16_t MIFlags = 0;
537   // Copy the wrapping flags.
538   if (const OverflowingBinaryOperator *OB =
539           dyn_cast<OverflowingBinaryOperator>(&I)) {
540     if (OB->hasNoSignedWrap())
541       MIFlags |= MachineInstr::MIFlag::NoSWrap;
542     if (OB->hasNoUnsignedWrap())
543       MIFlags |= MachineInstr::MIFlag::NoUWrap;
544   }
545 
546   // Copy the exact flag.
547   if (const PossiblyExactOperator *PE = dyn_cast<PossiblyExactOperator>(&I))
548     if (PE->isExact())
549       MIFlags |= MachineInstr::MIFlag::IsExact;
550 
551   // Copy the fast-math flags.
552   if (const FPMathOperator *FP = dyn_cast<FPMathOperator>(&I)) {
553     const FastMathFlags Flags = FP->getFastMathFlags();
554     if (Flags.noNaNs())
555       MIFlags |= MachineInstr::MIFlag::FmNoNans;
556     if (Flags.noInfs())
557       MIFlags |= MachineInstr::MIFlag::FmNoInfs;
558     if (Flags.noSignedZeros())
559       MIFlags |= MachineInstr::MIFlag::FmNsz;
560     if (Flags.allowReciprocal())
561       MIFlags |= MachineInstr::MIFlag::FmArcp;
562     if (Flags.allowContract())
563       MIFlags |= MachineInstr::MIFlag::FmContract;
564     if (Flags.approxFunc())
565       MIFlags |= MachineInstr::MIFlag::FmAfn;
566     if (Flags.allowReassoc())
567       MIFlags |= MachineInstr::MIFlag::FmReassoc;
568   }
569 
570   return MIFlags;
571 }
572 
573 void MachineInstr::copyIRFlags(const Instruction &I) {
574   Flags = copyFlagsFromInstruction(I);
575 }
576 
577 bool MachineInstr::hasPropertyInBundle(uint64_t Mask, QueryType Type) const {
578   assert(!isBundledWithPred() && "Must be called on bundle header");
579   for (MachineBasicBlock::const_instr_iterator MII = getIterator();; ++MII) {
580     if (MII->getDesc().getFlags() & Mask) {
581       if (Type == AnyInBundle)
582         return true;
583     } else {
584       if (Type == AllInBundle && !MII->isBundle())
585         return false;
586     }
587     // This was the last instruction in the bundle.
588     if (!MII->isBundledWithSucc())
589       return Type == AllInBundle;
590   }
591 }
592 
593 bool MachineInstr::isIdenticalTo(const MachineInstr &Other,
594                                  MICheckType Check) const {
595   // If opcodes or number of operands are not the same then the two
596   // instructions are obviously not identical.
597   if (Other.getOpcode() != getOpcode() ||
598       Other.getNumOperands() != getNumOperands())
599     return false;
600 
601   if (isBundle()) {
602     // We have passed the test above that both instructions have the same
603     // opcode, so we know that both instructions are bundles here. Let's compare
604     // MIs inside the bundle.
605     assert(Other.isBundle() && "Expected that both instructions are bundles.");
606     MachineBasicBlock::const_instr_iterator I1 = getIterator();
607     MachineBasicBlock::const_instr_iterator I2 = Other.getIterator();
608     // Loop until we analysed the last intruction inside at least one of the
609     // bundles.
610     while (I1->isBundledWithSucc() && I2->isBundledWithSucc()) {
611       ++I1;
612       ++I2;
613       if (!I1->isIdenticalTo(*I2, Check))
614         return false;
615     }
616     // If we've reached the end of just one of the two bundles, but not both,
617     // the instructions are not identical.
618     if (I1->isBundledWithSucc() || I2->isBundledWithSucc())
619       return false;
620   }
621 
622   // Check operands to make sure they match.
623   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
624     const MachineOperand &MO = getOperand(i);
625     const MachineOperand &OMO = Other.getOperand(i);
626     if (!MO.isReg()) {
627       if (!MO.isIdenticalTo(OMO))
628         return false;
629       continue;
630     }
631 
632     // Clients may or may not want to ignore defs when testing for equality.
633     // For example, machine CSE pass only cares about finding common
634     // subexpressions, so it's safe to ignore virtual register defs.
635     if (MO.isDef()) {
636       if (Check == IgnoreDefs)
637         continue;
638       else if (Check == IgnoreVRegDefs) {
639         if (!Register::isVirtualRegister(MO.getReg()) ||
640             !Register::isVirtualRegister(OMO.getReg()))
641           if (!MO.isIdenticalTo(OMO))
642             return false;
643       } else {
644         if (!MO.isIdenticalTo(OMO))
645           return false;
646         if (Check == CheckKillDead && MO.isDead() != OMO.isDead())
647           return false;
648       }
649     } else {
650       if (!MO.isIdenticalTo(OMO))
651         return false;
652       if (Check == CheckKillDead && MO.isKill() != OMO.isKill())
653         return false;
654     }
655   }
656   // If DebugLoc does not match then two debug instructions are not identical.
657   if (isDebugInstr())
658     if (getDebugLoc() && Other.getDebugLoc() &&
659         getDebugLoc() != Other.getDebugLoc())
660       return false;
661   return true;
662 }
663 
664 const MachineFunction *MachineInstr::getMF() const {
665   return getParent()->getParent();
666 }
667 
668 MachineInstr *MachineInstr::removeFromParent() {
669   assert(getParent() && "Not embedded in a basic block!");
670   return getParent()->remove(this);
671 }
672 
673 MachineInstr *MachineInstr::removeFromBundle() {
674   assert(getParent() && "Not embedded in a basic block!");
675   return getParent()->remove_instr(this);
676 }
677 
678 void MachineInstr::eraseFromParent() {
679   assert(getParent() && "Not embedded in a basic block!");
680   getParent()->erase(this);
681 }
682 
683 void MachineInstr::eraseFromParentAndMarkDBGValuesForRemoval() {
684   assert(getParent() && "Not embedded in a basic block!");
685   MachineBasicBlock *MBB = getParent();
686   MachineFunction *MF = MBB->getParent();
687   assert(MF && "Not embedded in a function!");
688 
689   MachineInstr *MI = (MachineInstr *)this;
690   MachineRegisterInfo &MRI = MF->getRegInfo();
691 
692   for (const MachineOperand &MO : MI->operands()) {
693     if (!MO.isReg() || !MO.isDef())
694       continue;
695     Register Reg = MO.getReg();
696     if (!Reg.isVirtual())
697       continue;
698     MRI.markUsesInDebugValueAsUndef(Reg);
699   }
700   MI->eraseFromParent();
701 }
702 
703 void MachineInstr::eraseFromBundle() {
704   assert(getParent() && "Not embedded in a basic block!");
705   getParent()->erase_instr(this);
706 }
707 
708 unsigned MachineInstr::getNumExplicitOperands() const {
709   unsigned NumOperands = MCID->getNumOperands();
710   if (!MCID->isVariadic())
711     return NumOperands;
712 
713   for (unsigned I = NumOperands, E = getNumOperands(); I != E; ++I) {
714     const MachineOperand &MO = getOperand(I);
715     // The operands must always be in the following order:
716     // - explicit reg defs,
717     // - other explicit operands (reg uses, immediates, etc.),
718     // - implicit reg defs
719     // - implicit reg uses
720     if (MO.isReg() && MO.isImplicit())
721       break;
722     ++NumOperands;
723   }
724   return NumOperands;
725 }
726 
727 unsigned MachineInstr::getNumExplicitDefs() const {
728   unsigned NumDefs = MCID->getNumDefs();
729   if (!MCID->isVariadic())
730     return NumDefs;
731 
732   for (unsigned I = NumDefs, E = getNumOperands(); I != E; ++I) {
733     const MachineOperand &MO = getOperand(I);
734     if (!MO.isReg() || !MO.isDef() || MO.isImplicit())
735       break;
736     ++NumDefs;
737   }
738   return NumDefs;
739 }
740 
741 void MachineInstr::bundleWithPred() {
742   assert(!isBundledWithPred() && "MI is already bundled with its predecessor");
743   setFlag(BundledPred);
744   MachineBasicBlock::instr_iterator Pred = getIterator();
745   --Pred;
746   assert(!Pred->isBundledWithSucc() && "Inconsistent bundle flags");
747   Pred->setFlag(BundledSucc);
748 }
749 
750 void MachineInstr::bundleWithSucc() {
751   assert(!isBundledWithSucc() && "MI is already bundled with its successor");
752   setFlag(BundledSucc);
753   MachineBasicBlock::instr_iterator Succ = getIterator();
754   ++Succ;
755   assert(!Succ->isBundledWithPred() && "Inconsistent bundle flags");
756   Succ->setFlag(BundledPred);
757 }
758 
759 void MachineInstr::unbundleFromPred() {
760   assert(isBundledWithPred() && "MI isn't bundled with its predecessor");
761   clearFlag(BundledPred);
762   MachineBasicBlock::instr_iterator Pred = getIterator();
763   --Pred;
764   assert(Pred->isBundledWithSucc() && "Inconsistent bundle flags");
765   Pred->clearFlag(BundledSucc);
766 }
767 
768 void MachineInstr::unbundleFromSucc() {
769   assert(isBundledWithSucc() && "MI isn't bundled with its successor");
770   clearFlag(BundledSucc);
771   MachineBasicBlock::instr_iterator Succ = getIterator();
772   ++Succ;
773   assert(Succ->isBundledWithPred() && "Inconsistent bundle flags");
774   Succ->clearFlag(BundledPred);
775 }
776 
777 bool MachineInstr::isStackAligningInlineAsm() const {
778   if (isInlineAsm()) {
779     unsigned ExtraInfo = getOperand(InlineAsm::MIOp_ExtraInfo).getImm();
780     if (ExtraInfo & InlineAsm::Extra_IsAlignStack)
781       return true;
782   }
783   return false;
784 }
785 
786 InlineAsm::AsmDialect MachineInstr::getInlineAsmDialect() const {
787   assert(isInlineAsm() && "getInlineAsmDialect() only works for inline asms!");
788   unsigned ExtraInfo = getOperand(InlineAsm::MIOp_ExtraInfo).getImm();
789   return InlineAsm::AsmDialect((ExtraInfo & InlineAsm::Extra_AsmDialect) != 0);
790 }
791 
792 int MachineInstr::findInlineAsmFlagIdx(unsigned OpIdx,
793                                        unsigned *GroupNo) const {
794   assert(isInlineAsm() && "Expected an inline asm instruction");
795   assert(OpIdx < getNumOperands() && "OpIdx out of range");
796 
797   // Ignore queries about the initial operands.
798   if (OpIdx < InlineAsm::MIOp_FirstOperand)
799     return -1;
800 
801   unsigned Group = 0;
802   unsigned NumOps;
803   for (unsigned i = InlineAsm::MIOp_FirstOperand, e = getNumOperands(); i < e;
804        i += NumOps) {
805     const MachineOperand &FlagMO = getOperand(i);
806     // If we reach the implicit register operands, stop looking.
807     if (!FlagMO.isImm())
808       return -1;
809     NumOps = 1 + InlineAsm::getNumOperandRegisters(FlagMO.getImm());
810     if (i + NumOps > OpIdx) {
811       if (GroupNo)
812         *GroupNo = Group;
813       return i;
814     }
815     ++Group;
816   }
817   return -1;
818 }
819 
820 const DILabel *MachineInstr::getDebugLabel() const {
821   assert(isDebugLabel() && "not a DBG_LABEL");
822   return cast<DILabel>(getOperand(0).getMetadata());
823 }
824 
825 const DILocalVariable *MachineInstr::getDebugVariable() const {
826   assert(isDebugValue() && "not a DBG_VALUE");
827   return cast<DILocalVariable>(getOperand(2).getMetadata());
828 }
829 
830 const DIExpression *MachineInstr::getDebugExpression() const {
831   assert(isDebugValue() && "not a DBG_VALUE");
832   return cast<DIExpression>(getOperand(3).getMetadata());
833 }
834 
835 bool MachineInstr::isDebugEntryValue() const {
836   return isDebugValue() && getDebugExpression()->isEntryValue();
837 }
838 
839 const TargetRegisterClass*
840 MachineInstr::getRegClassConstraint(unsigned OpIdx,
841                                     const TargetInstrInfo *TII,
842                                     const TargetRegisterInfo *TRI) const {
843   assert(getParent() && "Can't have an MBB reference here!");
844   assert(getMF() && "Can't have an MF reference here!");
845   const MachineFunction &MF = *getMF();
846 
847   // Most opcodes have fixed constraints in their MCInstrDesc.
848   if (!isInlineAsm())
849     return TII->getRegClass(getDesc(), OpIdx, TRI, MF);
850 
851   if (!getOperand(OpIdx).isReg())
852     return nullptr;
853 
854   // For tied uses on inline asm, get the constraint from the def.
855   unsigned DefIdx;
856   if (getOperand(OpIdx).isUse() && isRegTiedToDefOperand(OpIdx, &DefIdx))
857     OpIdx = DefIdx;
858 
859   // Inline asm stores register class constraints in the flag word.
860   int FlagIdx = findInlineAsmFlagIdx(OpIdx);
861   if (FlagIdx < 0)
862     return nullptr;
863 
864   unsigned Flag = getOperand(FlagIdx).getImm();
865   unsigned RCID;
866   if ((InlineAsm::getKind(Flag) == InlineAsm::Kind_RegUse ||
867        InlineAsm::getKind(Flag) == InlineAsm::Kind_RegDef ||
868        InlineAsm::getKind(Flag) == InlineAsm::Kind_RegDefEarlyClobber) &&
869       InlineAsm::hasRegClassConstraint(Flag, RCID))
870     return TRI->getRegClass(RCID);
871 
872   // Assume that all registers in a memory operand are pointers.
873   if (InlineAsm::getKind(Flag) == InlineAsm::Kind_Mem)
874     return TRI->getPointerRegClass(MF);
875 
876   return nullptr;
877 }
878 
879 const TargetRegisterClass *MachineInstr::getRegClassConstraintEffectForVReg(
880     Register Reg, const TargetRegisterClass *CurRC, const TargetInstrInfo *TII,
881     const TargetRegisterInfo *TRI, bool ExploreBundle) const {
882   // Check every operands inside the bundle if we have
883   // been asked to.
884   if (ExploreBundle)
885     for (ConstMIBundleOperands OpndIt(*this); OpndIt.isValid() && CurRC;
886          ++OpndIt)
887       CurRC = OpndIt->getParent()->getRegClassConstraintEffectForVRegImpl(
888           OpndIt.getOperandNo(), Reg, CurRC, TII, TRI);
889   else
890     // Otherwise, just check the current operands.
891     for (unsigned i = 0, e = NumOperands; i < e && CurRC; ++i)
892       CurRC = getRegClassConstraintEffectForVRegImpl(i, Reg, CurRC, TII, TRI);
893   return CurRC;
894 }
895 
896 const TargetRegisterClass *MachineInstr::getRegClassConstraintEffectForVRegImpl(
897     unsigned OpIdx, Register Reg, const TargetRegisterClass *CurRC,
898     const TargetInstrInfo *TII, const TargetRegisterInfo *TRI) const {
899   assert(CurRC && "Invalid initial register class");
900   // Check if Reg is constrained by some of its use/def from MI.
901   const MachineOperand &MO = getOperand(OpIdx);
902   if (!MO.isReg() || MO.getReg() != Reg)
903     return CurRC;
904   // If yes, accumulate the constraints through the operand.
905   return getRegClassConstraintEffect(OpIdx, CurRC, TII, TRI);
906 }
907 
908 const TargetRegisterClass *MachineInstr::getRegClassConstraintEffect(
909     unsigned OpIdx, const TargetRegisterClass *CurRC,
910     const TargetInstrInfo *TII, const TargetRegisterInfo *TRI) const {
911   const TargetRegisterClass *OpRC = getRegClassConstraint(OpIdx, TII, TRI);
912   const MachineOperand &MO = getOperand(OpIdx);
913   assert(MO.isReg() &&
914          "Cannot get register constraints for non-register operand");
915   assert(CurRC && "Invalid initial register class");
916   if (unsigned SubIdx = MO.getSubReg()) {
917     if (OpRC)
918       CurRC = TRI->getMatchingSuperRegClass(CurRC, OpRC, SubIdx);
919     else
920       CurRC = TRI->getSubClassWithSubReg(CurRC, SubIdx);
921   } else if (OpRC)
922     CurRC = TRI->getCommonSubClass(CurRC, OpRC);
923   return CurRC;
924 }
925 
926 /// Return the number of instructions inside the MI bundle, not counting the
927 /// header instruction.
928 unsigned MachineInstr::getBundleSize() const {
929   MachineBasicBlock::const_instr_iterator I = getIterator();
930   unsigned Size = 0;
931   while (I->isBundledWithSucc()) {
932     ++Size;
933     ++I;
934   }
935   return Size;
936 }
937 
938 /// Returns true if the MachineInstr has an implicit-use operand of exactly
939 /// the given register (not considering sub/super-registers).
940 bool MachineInstr::hasRegisterImplicitUseOperand(Register Reg) const {
941   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
942     const MachineOperand &MO = getOperand(i);
943     if (MO.isReg() && MO.isUse() && MO.isImplicit() && MO.getReg() == Reg)
944       return true;
945   }
946   return false;
947 }
948 
949 /// findRegisterUseOperandIdx() - Returns the MachineOperand that is a use of
950 /// the specific register or -1 if it is not found. It further tightens
951 /// the search criteria to a use that kills the register if isKill is true.
952 int MachineInstr::findRegisterUseOperandIdx(
953     Register Reg, bool isKill, const TargetRegisterInfo *TRI) const {
954   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
955     const MachineOperand &MO = getOperand(i);
956     if (!MO.isReg() || !MO.isUse())
957       continue;
958     Register MOReg = MO.getReg();
959     if (!MOReg)
960       continue;
961     if (MOReg == Reg || (TRI && Reg && MOReg && TRI->regsOverlap(MOReg, Reg)))
962       if (!isKill || MO.isKill())
963         return i;
964   }
965   return -1;
966 }
967 
968 /// readsWritesVirtualRegister - Return a pair of bools (reads, writes)
969 /// indicating if this instruction reads or writes Reg. This also considers
970 /// partial defines.
971 std::pair<bool,bool>
972 MachineInstr::readsWritesVirtualRegister(Register Reg,
973                                          SmallVectorImpl<unsigned> *Ops) const {
974   bool PartDef = false; // Partial redefine.
975   bool FullDef = false; // Full define.
976   bool Use = false;
977 
978   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
979     const MachineOperand &MO = getOperand(i);
980     if (!MO.isReg() || MO.getReg() != Reg)
981       continue;
982     if (Ops)
983       Ops->push_back(i);
984     if (MO.isUse())
985       Use |= !MO.isUndef();
986     else if (MO.getSubReg() && !MO.isUndef())
987       // A partial def undef doesn't count as reading the register.
988       PartDef = true;
989     else
990       FullDef = true;
991   }
992   // A partial redefine uses Reg unless there is also a full define.
993   return std::make_pair(Use || (PartDef && !FullDef), PartDef || FullDef);
994 }
995 
996 /// findRegisterDefOperandIdx() - Returns the operand index that is a def of
997 /// the specified register or -1 if it is not found. If isDead is true, defs
998 /// that are not dead are skipped. If TargetRegisterInfo is non-null, then it
999 /// also checks if there is a def of a super-register.
1000 int
1001 MachineInstr::findRegisterDefOperandIdx(Register Reg, bool isDead, bool Overlap,
1002                                         const TargetRegisterInfo *TRI) const {
1003   bool isPhys = Register::isPhysicalRegister(Reg);
1004   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
1005     const MachineOperand &MO = getOperand(i);
1006     // Accept regmask operands when Overlap is set.
1007     // Ignore them when looking for a specific def operand (Overlap == false).
1008     if (isPhys && Overlap && MO.isRegMask() && MO.clobbersPhysReg(Reg))
1009       return i;
1010     if (!MO.isReg() || !MO.isDef())
1011       continue;
1012     Register MOReg = MO.getReg();
1013     bool Found = (MOReg == Reg);
1014     if (!Found && TRI && isPhys && Register::isPhysicalRegister(MOReg)) {
1015       if (Overlap)
1016         Found = TRI->regsOverlap(MOReg, Reg);
1017       else
1018         Found = TRI->isSubRegister(MOReg, Reg);
1019     }
1020     if (Found && (!isDead || MO.isDead()))
1021       return i;
1022   }
1023   return -1;
1024 }
1025 
1026 /// findFirstPredOperandIdx() - Find the index of the first operand in the
1027 /// operand list that is used to represent the predicate. It returns -1 if
1028 /// none is found.
1029 int MachineInstr::findFirstPredOperandIdx() const {
1030   // Don't call MCID.findFirstPredOperandIdx() because this variant
1031   // is sometimes called on an instruction that's not yet complete, and
1032   // so the number of operands is less than the MCID indicates. In
1033   // particular, the PTX target does this.
1034   const MCInstrDesc &MCID = getDesc();
1035   if (MCID.isPredicable()) {
1036     for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
1037       if (MCID.OpInfo[i].isPredicate())
1038         return i;
1039   }
1040 
1041   return -1;
1042 }
1043 
1044 // MachineOperand::TiedTo is 4 bits wide.
1045 const unsigned TiedMax = 15;
1046 
1047 /// tieOperands - Mark operands at DefIdx and UseIdx as tied to each other.
1048 ///
1049 /// Use and def operands can be tied together, indicated by a non-zero TiedTo
1050 /// field. TiedTo can have these values:
1051 ///
1052 /// 0:              Operand is not tied to anything.
1053 /// 1 to TiedMax-1: Tied to getOperand(TiedTo-1).
1054 /// TiedMax:        Tied to an operand >= TiedMax-1.
1055 ///
1056 /// The tied def must be one of the first TiedMax operands on a normal
1057 /// instruction. INLINEASM instructions allow more tied defs.
1058 ///
1059 void MachineInstr::tieOperands(unsigned DefIdx, unsigned UseIdx) {
1060   MachineOperand &DefMO = getOperand(DefIdx);
1061   MachineOperand &UseMO = getOperand(UseIdx);
1062   assert(DefMO.isDef() && "DefIdx must be a def operand");
1063   assert(UseMO.isUse() && "UseIdx must be a use operand");
1064   assert(!DefMO.isTied() && "Def is already tied to another use");
1065   assert(!UseMO.isTied() && "Use is already tied to another def");
1066 
1067   if (DefIdx < TiedMax)
1068     UseMO.TiedTo = DefIdx + 1;
1069   else {
1070     // Inline asm can use the group descriptors to find tied operands, but on
1071     // normal instruction, the tied def must be within the first TiedMax
1072     // operands.
1073     assert(isInlineAsm() && "DefIdx out of range");
1074     UseMO.TiedTo = TiedMax;
1075   }
1076 
1077   // UseIdx can be out of range, we'll search for it in findTiedOperandIdx().
1078   DefMO.TiedTo = std::min(UseIdx + 1, TiedMax);
1079 }
1080 
1081 /// Given the index of a tied register operand, find the operand it is tied to.
1082 /// Defs are tied to uses and vice versa. Returns the index of the tied operand
1083 /// which must exist.
1084 unsigned MachineInstr::findTiedOperandIdx(unsigned OpIdx) const {
1085   const MachineOperand &MO = getOperand(OpIdx);
1086   assert(MO.isTied() && "Operand isn't tied");
1087 
1088   // Normally TiedTo is in range.
1089   if (MO.TiedTo < TiedMax)
1090     return MO.TiedTo - 1;
1091 
1092   // Uses on normal instructions can be out of range.
1093   if (!isInlineAsm()) {
1094     // Normal tied defs must be in the 0..TiedMax-1 range.
1095     if (MO.isUse())
1096       return TiedMax - 1;
1097     // MO is a def. Search for the tied use.
1098     for (unsigned i = TiedMax - 1, e = getNumOperands(); i != e; ++i) {
1099       const MachineOperand &UseMO = getOperand(i);
1100       if (UseMO.isReg() && UseMO.isUse() && UseMO.TiedTo == OpIdx + 1)
1101         return i;
1102     }
1103     llvm_unreachable("Can't find tied use");
1104   }
1105 
1106   // Now deal with inline asm by parsing the operand group descriptor flags.
1107   // Find the beginning of each operand group.
1108   SmallVector<unsigned, 8> GroupIdx;
1109   unsigned OpIdxGroup = ~0u;
1110   unsigned NumOps;
1111   for (unsigned i = InlineAsm::MIOp_FirstOperand, e = getNumOperands(); i < e;
1112        i += NumOps) {
1113     const MachineOperand &FlagMO = getOperand(i);
1114     assert(FlagMO.isImm() && "Invalid tied operand on inline asm");
1115     unsigned CurGroup = GroupIdx.size();
1116     GroupIdx.push_back(i);
1117     NumOps = 1 + InlineAsm::getNumOperandRegisters(FlagMO.getImm());
1118     // OpIdx belongs to this operand group.
1119     if (OpIdx > i && OpIdx < i + NumOps)
1120       OpIdxGroup = CurGroup;
1121     unsigned TiedGroup;
1122     if (!InlineAsm::isUseOperandTiedToDef(FlagMO.getImm(), TiedGroup))
1123       continue;
1124     // Operands in this group are tied to operands in TiedGroup which must be
1125     // earlier. Find the number of operands between the two groups.
1126     unsigned Delta = i - GroupIdx[TiedGroup];
1127 
1128     // OpIdx is a use tied to TiedGroup.
1129     if (OpIdxGroup == CurGroup)
1130       return OpIdx - Delta;
1131 
1132     // OpIdx is a def tied to this use group.
1133     if (OpIdxGroup == TiedGroup)
1134       return OpIdx + Delta;
1135   }
1136   llvm_unreachable("Invalid tied operand on inline asm");
1137 }
1138 
1139 /// clearKillInfo - Clears kill flags on all operands.
1140 ///
1141 void MachineInstr::clearKillInfo() {
1142   for (MachineOperand &MO : operands()) {
1143     if (MO.isReg() && MO.isUse())
1144       MO.setIsKill(false);
1145   }
1146 }
1147 
1148 void MachineInstr::substituteRegister(Register FromReg, Register ToReg,
1149                                       unsigned SubIdx,
1150                                       const TargetRegisterInfo &RegInfo) {
1151   if (Register::isPhysicalRegister(ToReg)) {
1152     if (SubIdx)
1153       ToReg = RegInfo.getSubReg(ToReg, SubIdx);
1154     for (MachineOperand &MO : operands()) {
1155       if (!MO.isReg() || MO.getReg() != FromReg)
1156         continue;
1157       MO.substPhysReg(ToReg, RegInfo);
1158     }
1159   } else {
1160     for (MachineOperand &MO : operands()) {
1161       if (!MO.isReg() || MO.getReg() != FromReg)
1162         continue;
1163       MO.substVirtReg(ToReg, SubIdx, RegInfo);
1164     }
1165   }
1166 }
1167 
1168 /// isSafeToMove - Return true if it is safe to move this instruction. If
1169 /// SawStore is set to true, it means that there is a store (or call) between
1170 /// the instruction's location and its intended destination.
1171 bool MachineInstr::isSafeToMove(AAResults *AA, bool &SawStore) const {
1172   // Ignore stuff that we obviously can't move.
1173   //
1174   // Treat volatile loads as stores. This is not strictly necessary for
1175   // volatiles, but it is required for atomic loads. It is not allowed to move
1176   // a load across an atomic load with Ordering > Monotonic.
1177   if (mayStore() || isCall() || isPHI() ||
1178       (mayLoad() && hasOrderedMemoryRef())) {
1179     SawStore = true;
1180     return false;
1181   }
1182 
1183   if (isPosition() || isDebugInstr() || isTerminator() ||
1184       mayRaiseFPException() || hasUnmodeledSideEffects())
1185     return false;
1186 
1187   // See if this instruction does a load.  If so, we have to guarantee that the
1188   // loaded value doesn't change between the load and the its intended
1189   // destination. The check for isInvariantLoad gives the targe the chance to
1190   // classify the load as always returning a constant, e.g. a constant pool
1191   // load.
1192   if (mayLoad() && !isDereferenceableInvariantLoad(AA))
1193     // Otherwise, this is a real load.  If there is a store between the load and
1194     // end of block, we can't move it.
1195     return !SawStore;
1196 
1197   return true;
1198 }
1199 
1200 bool MachineInstr::mayAlias(AAResults *AA, const MachineInstr &Other,
1201                             bool UseTBAA) const {
1202   const MachineFunction *MF = getMF();
1203   const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
1204   const MachineFrameInfo &MFI = MF->getFrameInfo();
1205 
1206   // If neither instruction stores to memory, they can't alias in any
1207   // meaningful way, even if they read from the same address.
1208   if (!mayStore() && !Other.mayStore())
1209     return false;
1210 
1211   // Let the target decide if memory accesses cannot possibly overlap.
1212   if (TII->areMemAccessesTriviallyDisjoint(*this, Other))
1213     return false;
1214 
1215   // FIXME: Need to handle multiple memory operands to support all targets.
1216   if (!hasOneMemOperand() || !Other.hasOneMemOperand())
1217     return true;
1218 
1219   MachineMemOperand *MMOa = *memoperands_begin();
1220   MachineMemOperand *MMOb = *Other.memoperands_begin();
1221 
1222   // The following interface to AA is fashioned after DAGCombiner::isAlias
1223   // and operates with MachineMemOperand offset with some important
1224   // assumptions:
1225   //   - LLVM fundamentally assumes flat address spaces.
1226   //   - MachineOperand offset can *only* result from legalization and
1227   //     cannot affect queries other than the trivial case of overlap
1228   //     checking.
1229   //   - These offsets never wrap and never step outside
1230   //     of allocated objects.
1231   //   - There should never be any negative offsets here.
1232   //
1233   // FIXME: Modify API to hide this math from "user"
1234   // Even before we go to AA we can reason locally about some
1235   // memory objects. It can save compile time, and possibly catch some
1236   // corner cases not currently covered.
1237 
1238   int64_t OffsetA = MMOa->getOffset();
1239   int64_t OffsetB = MMOb->getOffset();
1240   int64_t MinOffset = std::min(OffsetA, OffsetB);
1241 
1242   uint64_t WidthA = MMOa->getSize();
1243   uint64_t WidthB = MMOb->getSize();
1244   bool KnownWidthA = WidthA != MemoryLocation::UnknownSize;
1245   bool KnownWidthB = WidthB != MemoryLocation::UnknownSize;
1246 
1247   const Value *ValA = MMOa->getValue();
1248   const Value *ValB = MMOb->getValue();
1249   bool SameVal = (ValA && ValB && (ValA == ValB));
1250   if (!SameVal) {
1251     const PseudoSourceValue *PSVa = MMOa->getPseudoValue();
1252     const PseudoSourceValue *PSVb = MMOb->getPseudoValue();
1253     if (PSVa && ValB && !PSVa->mayAlias(&MFI))
1254       return false;
1255     if (PSVb && ValA && !PSVb->mayAlias(&MFI))
1256       return false;
1257     if (PSVa && PSVb && (PSVa == PSVb))
1258       SameVal = true;
1259   }
1260 
1261   if (SameVal) {
1262     if (!KnownWidthA || !KnownWidthB)
1263       return true;
1264     int64_t MaxOffset = std::max(OffsetA, OffsetB);
1265     int64_t LowWidth = (MinOffset == OffsetA) ? WidthA : WidthB;
1266     return (MinOffset + LowWidth > MaxOffset);
1267   }
1268 
1269   if (!AA)
1270     return true;
1271 
1272   if (!ValA || !ValB)
1273     return true;
1274 
1275   assert((OffsetA >= 0) && "Negative MachineMemOperand offset");
1276   assert((OffsetB >= 0) && "Negative MachineMemOperand offset");
1277 
1278   int64_t OverlapA = KnownWidthA ? WidthA + OffsetA - MinOffset
1279                                  : MemoryLocation::UnknownSize;
1280   int64_t OverlapB = KnownWidthB ? WidthB + OffsetB - MinOffset
1281                                  : MemoryLocation::UnknownSize;
1282 
1283   AliasResult AAResult = AA->alias(
1284       MemoryLocation(ValA, OverlapA,
1285                      UseTBAA ? MMOa->getAAInfo() : AAMDNodes()),
1286       MemoryLocation(ValB, OverlapB,
1287                      UseTBAA ? MMOb->getAAInfo() : AAMDNodes()));
1288 
1289   return (AAResult != NoAlias);
1290 }
1291 
1292 /// hasOrderedMemoryRef - Return true if this instruction may have an ordered
1293 /// or volatile memory reference, or if the information describing the memory
1294 /// reference is not available. Return false if it is known to have no ordered
1295 /// memory references.
1296 bool MachineInstr::hasOrderedMemoryRef() const {
1297   // An instruction known never to access memory won't have a volatile access.
1298   if (!mayStore() &&
1299       !mayLoad() &&
1300       !isCall() &&
1301       !hasUnmodeledSideEffects())
1302     return false;
1303 
1304   // Otherwise, if the instruction has no memory reference information,
1305   // conservatively assume it wasn't preserved.
1306   if (memoperands_empty())
1307     return true;
1308 
1309   // Check if any of our memory operands are ordered.
1310   return llvm::any_of(memoperands(), [](const MachineMemOperand *MMO) {
1311     return !MMO->isUnordered();
1312   });
1313 }
1314 
1315 /// isDereferenceableInvariantLoad - Return true if this instruction will never
1316 /// trap and is loading from a location whose value is invariant across a run of
1317 /// this function.
1318 bool MachineInstr::isDereferenceableInvariantLoad(AAResults *AA) const {
1319   // If the instruction doesn't load at all, it isn't an invariant load.
1320   if (!mayLoad())
1321     return false;
1322 
1323   // If the instruction has lost its memoperands, conservatively assume that
1324   // it may not be an invariant load.
1325   if (memoperands_empty())
1326     return false;
1327 
1328   const MachineFrameInfo &MFI = getParent()->getParent()->getFrameInfo();
1329 
1330   for (MachineMemOperand *MMO : memoperands()) {
1331     if (!MMO->isUnordered())
1332       // If the memory operand has ordering side effects, we can't move the
1333       // instruction.  Such an instruction is technically an invariant load,
1334       // but the caller code would need updated to expect that.
1335       return false;
1336     if (MMO->isStore()) return false;
1337     if (MMO->isInvariant() && MMO->isDereferenceable())
1338       continue;
1339 
1340     // A load from a constant PseudoSourceValue is invariant.
1341     if (const PseudoSourceValue *PSV = MMO->getPseudoValue())
1342       if (PSV->isConstant(&MFI))
1343         continue;
1344 
1345     if (const Value *V = MMO->getValue()) {
1346       // If we have an AliasAnalysis, ask it whether the memory is constant.
1347       if (AA &&
1348           AA->pointsToConstantMemory(
1349               MemoryLocation(V, MMO->getSize(), MMO->getAAInfo())))
1350         continue;
1351     }
1352 
1353     // Otherwise assume conservatively.
1354     return false;
1355   }
1356 
1357   // Everything checks out.
1358   return true;
1359 }
1360 
1361 /// isConstantValuePHI - If the specified instruction is a PHI that always
1362 /// merges together the same virtual register, return the register, otherwise
1363 /// return 0.
1364 unsigned MachineInstr::isConstantValuePHI() const {
1365   if (!isPHI())
1366     return 0;
1367   assert(getNumOperands() >= 3 &&
1368          "It's illegal to have a PHI without source operands");
1369 
1370   Register Reg = getOperand(1).getReg();
1371   for (unsigned i = 3, e = getNumOperands(); i < e; i += 2)
1372     if (getOperand(i).getReg() != Reg)
1373       return 0;
1374   return Reg;
1375 }
1376 
1377 bool MachineInstr::hasUnmodeledSideEffects() const {
1378   if (hasProperty(MCID::UnmodeledSideEffects))
1379     return true;
1380   if (isInlineAsm()) {
1381     unsigned ExtraInfo = getOperand(InlineAsm::MIOp_ExtraInfo).getImm();
1382     if (ExtraInfo & InlineAsm::Extra_HasSideEffects)
1383       return true;
1384   }
1385 
1386   return false;
1387 }
1388 
1389 bool MachineInstr::isLoadFoldBarrier() const {
1390   return mayStore() || isCall() || hasUnmodeledSideEffects();
1391 }
1392 
1393 /// allDefsAreDead - Return true if all the defs of this instruction are dead.
1394 ///
1395 bool MachineInstr::allDefsAreDead() const {
1396   for (const MachineOperand &MO : operands()) {
1397     if (!MO.isReg() || MO.isUse())
1398       continue;
1399     if (!MO.isDead())
1400       return false;
1401   }
1402   return true;
1403 }
1404 
1405 /// copyImplicitOps - Copy implicit register operands from specified
1406 /// instruction to this instruction.
1407 void MachineInstr::copyImplicitOps(MachineFunction &MF,
1408                                    const MachineInstr &MI) {
1409   for (unsigned i = MI.getDesc().getNumOperands(), e = MI.getNumOperands();
1410        i != e; ++i) {
1411     const MachineOperand &MO = MI.getOperand(i);
1412     if ((MO.isReg() && MO.isImplicit()) || MO.isRegMask())
1413       addOperand(MF, MO);
1414   }
1415 }
1416 
1417 bool MachineInstr::hasComplexRegisterTies() const {
1418   const MCInstrDesc &MCID = getDesc();
1419   for (unsigned I = 0, E = getNumOperands(); I < E; ++I) {
1420     const auto &Operand = getOperand(I);
1421     if (!Operand.isReg() || Operand.isDef())
1422       // Ignore the defined registers as MCID marks only the uses as tied.
1423       continue;
1424     int ExpectedTiedIdx = MCID.getOperandConstraint(I, MCOI::TIED_TO);
1425     int TiedIdx = Operand.isTied() ? int(findTiedOperandIdx(I)) : -1;
1426     if (ExpectedTiedIdx != TiedIdx)
1427       return true;
1428   }
1429   return false;
1430 }
1431 
1432 LLT MachineInstr::getTypeToPrint(unsigned OpIdx, SmallBitVector &PrintedTypes,
1433                                  const MachineRegisterInfo &MRI) const {
1434   const MachineOperand &Op = getOperand(OpIdx);
1435   if (!Op.isReg())
1436     return LLT{};
1437 
1438   if (isVariadic() || OpIdx >= getNumExplicitOperands())
1439     return MRI.getType(Op.getReg());
1440 
1441   auto &OpInfo = getDesc().OpInfo[OpIdx];
1442   if (!OpInfo.isGenericType())
1443     return MRI.getType(Op.getReg());
1444 
1445   if (PrintedTypes[OpInfo.getGenericTypeIndex()])
1446     return LLT{};
1447 
1448   LLT TypeToPrint = MRI.getType(Op.getReg());
1449   // Don't mark the type index printed if it wasn't actually printed: maybe
1450   // another operand with the same type index has an actual type attached:
1451   if (TypeToPrint.isValid())
1452     PrintedTypes.set(OpInfo.getGenericTypeIndex());
1453   return TypeToPrint;
1454 }
1455 
1456 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1457 LLVM_DUMP_METHOD void MachineInstr::dump() const {
1458   dbgs() << "  ";
1459   print(dbgs());
1460 }
1461 #endif
1462 
1463 void MachineInstr::print(raw_ostream &OS, bool IsStandalone, bool SkipOpers,
1464                          bool SkipDebugLoc, bool AddNewLine,
1465                          const TargetInstrInfo *TII) const {
1466   const Module *M = nullptr;
1467   const Function *F = nullptr;
1468   if (const MachineFunction *MF = getMFIfAvailable(*this)) {
1469     F = &MF->getFunction();
1470     M = F->getParent();
1471     if (!TII)
1472       TII = MF->getSubtarget().getInstrInfo();
1473   }
1474 
1475   ModuleSlotTracker MST(M);
1476   if (F)
1477     MST.incorporateFunction(*F);
1478   print(OS, MST, IsStandalone, SkipOpers, SkipDebugLoc, AddNewLine, TII);
1479 }
1480 
1481 void MachineInstr::print(raw_ostream &OS, ModuleSlotTracker &MST,
1482                          bool IsStandalone, bool SkipOpers, bool SkipDebugLoc,
1483                          bool AddNewLine, const TargetInstrInfo *TII) const {
1484   // We can be a bit tidier if we know the MachineFunction.
1485   const MachineFunction *MF = nullptr;
1486   const TargetRegisterInfo *TRI = nullptr;
1487   const MachineRegisterInfo *MRI = nullptr;
1488   const TargetIntrinsicInfo *IntrinsicInfo = nullptr;
1489   tryToGetTargetInfo(*this, TRI, MRI, IntrinsicInfo, TII);
1490 
1491   if (isCFIInstruction())
1492     assert(getNumOperands() == 1 && "Expected 1 operand in CFI instruction");
1493 
1494   SmallBitVector PrintedTypes(8);
1495   bool ShouldPrintRegisterTies = IsStandalone || hasComplexRegisterTies();
1496   auto getTiedOperandIdx = [&](unsigned OpIdx) {
1497     if (!ShouldPrintRegisterTies)
1498       return 0U;
1499     const MachineOperand &MO = getOperand(OpIdx);
1500     if (MO.isReg() && MO.isTied() && !MO.isDef())
1501       return findTiedOperandIdx(OpIdx);
1502     return 0U;
1503   };
1504   unsigned StartOp = 0;
1505   unsigned e = getNumOperands();
1506 
1507   // Print explicitly defined operands on the left of an assignment syntax.
1508   while (StartOp < e) {
1509     const MachineOperand &MO = getOperand(StartOp);
1510     if (!MO.isReg() || !MO.isDef() || MO.isImplicit())
1511       break;
1512 
1513     if (StartOp != 0)
1514       OS << ", ";
1515 
1516     LLT TypeToPrint = MRI ? getTypeToPrint(StartOp, PrintedTypes, *MRI) : LLT{};
1517     unsigned TiedOperandIdx = getTiedOperandIdx(StartOp);
1518     MO.print(OS, MST, TypeToPrint, /*PrintDef=*/false, IsStandalone,
1519              ShouldPrintRegisterTies, TiedOperandIdx, TRI, IntrinsicInfo);
1520     ++StartOp;
1521   }
1522 
1523   if (StartOp != 0)
1524     OS << " = ";
1525 
1526   if (getFlag(MachineInstr::FrameSetup))
1527     OS << "frame-setup ";
1528   if (getFlag(MachineInstr::FrameDestroy))
1529     OS << "frame-destroy ";
1530   if (getFlag(MachineInstr::FmNoNans))
1531     OS << "nnan ";
1532   if (getFlag(MachineInstr::FmNoInfs))
1533     OS << "ninf ";
1534   if (getFlag(MachineInstr::FmNsz))
1535     OS << "nsz ";
1536   if (getFlag(MachineInstr::FmArcp))
1537     OS << "arcp ";
1538   if (getFlag(MachineInstr::FmContract))
1539     OS << "contract ";
1540   if (getFlag(MachineInstr::FmAfn))
1541     OS << "afn ";
1542   if (getFlag(MachineInstr::FmReassoc))
1543     OS << "reassoc ";
1544   if (getFlag(MachineInstr::NoUWrap))
1545     OS << "nuw ";
1546   if (getFlag(MachineInstr::NoSWrap))
1547     OS << "nsw ";
1548   if (getFlag(MachineInstr::IsExact))
1549     OS << "exact ";
1550   if (getFlag(MachineInstr::FPExcept))
1551     OS << "fpexcept ";
1552 
1553   // Print the opcode name.
1554   if (TII)
1555     OS << TII->getName(getOpcode());
1556   else
1557     OS << "UNKNOWN";
1558 
1559   if (SkipOpers)
1560     return;
1561 
1562   // Print the rest of the operands.
1563   bool FirstOp = true;
1564   unsigned AsmDescOp = ~0u;
1565   unsigned AsmOpCount = 0;
1566 
1567   if (isInlineAsm() && e >= InlineAsm::MIOp_FirstOperand) {
1568     // Print asm string.
1569     OS << " ";
1570     const unsigned OpIdx = InlineAsm::MIOp_AsmString;
1571     LLT TypeToPrint = MRI ? getTypeToPrint(OpIdx, PrintedTypes, *MRI) : LLT{};
1572     unsigned TiedOperandIdx = getTiedOperandIdx(OpIdx);
1573     getOperand(OpIdx).print(OS, MST, TypeToPrint, /*PrintDef=*/true, IsStandalone,
1574                             ShouldPrintRegisterTies, TiedOperandIdx, TRI,
1575                             IntrinsicInfo);
1576 
1577     // Print HasSideEffects, MayLoad, MayStore, IsAlignStack
1578     unsigned ExtraInfo = getOperand(InlineAsm::MIOp_ExtraInfo).getImm();
1579     if (ExtraInfo & InlineAsm::Extra_HasSideEffects)
1580       OS << " [sideeffect]";
1581     if (ExtraInfo & InlineAsm::Extra_MayLoad)
1582       OS << " [mayload]";
1583     if (ExtraInfo & InlineAsm::Extra_MayStore)
1584       OS << " [maystore]";
1585     if (ExtraInfo & InlineAsm::Extra_IsConvergent)
1586       OS << " [isconvergent]";
1587     if (ExtraInfo & InlineAsm::Extra_IsAlignStack)
1588       OS << " [alignstack]";
1589     if (getInlineAsmDialect() == InlineAsm::AD_ATT)
1590       OS << " [attdialect]";
1591     if (getInlineAsmDialect() == InlineAsm::AD_Intel)
1592       OS << " [inteldialect]";
1593 
1594     StartOp = AsmDescOp = InlineAsm::MIOp_FirstOperand;
1595     FirstOp = false;
1596   }
1597 
1598   for (unsigned i = StartOp, e = getNumOperands(); i != e; ++i) {
1599     const MachineOperand &MO = getOperand(i);
1600 
1601     if (FirstOp) FirstOp = false; else OS << ",";
1602     OS << " ";
1603 
1604     if (isDebugValue() && MO.isMetadata()) {
1605       // Pretty print DBG_VALUE instructions.
1606       auto *DIV = dyn_cast<DILocalVariable>(MO.getMetadata());
1607       if (DIV && !DIV->getName().empty())
1608         OS << "!\"" << DIV->getName() << '\"';
1609       else {
1610         LLT TypeToPrint = MRI ? getTypeToPrint(i, PrintedTypes, *MRI) : LLT{};
1611         unsigned TiedOperandIdx = getTiedOperandIdx(i);
1612         MO.print(OS, MST, TypeToPrint, /*PrintDef=*/true, IsStandalone,
1613                  ShouldPrintRegisterTies, TiedOperandIdx, TRI, IntrinsicInfo);
1614       }
1615     } else if (isDebugLabel() && MO.isMetadata()) {
1616       // Pretty print DBG_LABEL instructions.
1617       auto *DIL = dyn_cast<DILabel>(MO.getMetadata());
1618       if (DIL && !DIL->getName().empty())
1619         OS << "\"" << DIL->getName() << '\"';
1620       else {
1621         LLT TypeToPrint = MRI ? getTypeToPrint(i, PrintedTypes, *MRI) : LLT{};
1622         unsigned TiedOperandIdx = getTiedOperandIdx(i);
1623         MO.print(OS, MST, TypeToPrint, /*PrintDef=*/true, IsStandalone,
1624                  ShouldPrintRegisterTies, TiedOperandIdx, TRI, IntrinsicInfo);
1625       }
1626     } else if (i == AsmDescOp && MO.isImm()) {
1627       // Pretty print the inline asm operand descriptor.
1628       OS << '$' << AsmOpCount++;
1629       unsigned Flag = MO.getImm();
1630       switch (InlineAsm::getKind(Flag)) {
1631       case InlineAsm::Kind_RegUse:             OS << ":[reguse"; break;
1632       case InlineAsm::Kind_RegDef:             OS << ":[regdef"; break;
1633       case InlineAsm::Kind_RegDefEarlyClobber: OS << ":[regdef-ec"; break;
1634       case InlineAsm::Kind_Clobber:            OS << ":[clobber"; break;
1635       case InlineAsm::Kind_Imm:                OS << ":[imm"; break;
1636       case InlineAsm::Kind_Mem:                OS << ":[mem"; break;
1637       default: OS << ":[??" << InlineAsm::getKind(Flag); break;
1638       }
1639 
1640       unsigned RCID = 0;
1641       if (!InlineAsm::isImmKind(Flag) && !InlineAsm::isMemKind(Flag) &&
1642           InlineAsm::hasRegClassConstraint(Flag, RCID)) {
1643         if (TRI) {
1644           OS << ':' << TRI->getRegClassName(TRI->getRegClass(RCID));
1645         } else
1646           OS << ":RC" << RCID;
1647       }
1648 
1649       if (InlineAsm::isMemKind(Flag)) {
1650         unsigned MCID = InlineAsm::getMemoryConstraintID(Flag);
1651         switch (MCID) {
1652         case InlineAsm::Constraint_es: OS << ":es"; break;
1653         case InlineAsm::Constraint_i:  OS << ":i"; break;
1654         case InlineAsm::Constraint_m:  OS << ":m"; break;
1655         case InlineAsm::Constraint_o:  OS << ":o"; break;
1656         case InlineAsm::Constraint_v:  OS << ":v"; break;
1657         case InlineAsm::Constraint_Q:  OS << ":Q"; break;
1658         case InlineAsm::Constraint_R:  OS << ":R"; break;
1659         case InlineAsm::Constraint_S:  OS << ":S"; break;
1660         case InlineAsm::Constraint_T:  OS << ":T"; break;
1661         case InlineAsm::Constraint_Um: OS << ":Um"; break;
1662         case InlineAsm::Constraint_Un: OS << ":Un"; break;
1663         case InlineAsm::Constraint_Uq: OS << ":Uq"; break;
1664         case InlineAsm::Constraint_Us: OS << ":Us"; break;
1665         case InlineAsm::Constraint_Ut: OS << ":Ut"; break;
1666         case InlineAsm::Constraint_Uv: OS << ":Uv"; break;
1667         case InlineAsm::Constraint_Uy: OS << ":Uy"; break;
1668         case InlineAsm::Constraint_X:  OS << ":X"; break;
1669         case InlineAsm::Constraint_Z:  OS << ":Z"; break;
1670         case InlineAsm::Constraint_ZC: OS << ":ZC"; break;
1671         case InlineAsm::Constraint_Zy: OS << ":Zy"; break;
1672         default: OS << ":?"; break;
1673         }
1674       }
1675 
1676       unsigned TiedTo = 0;
1677       if (InlineAsm::isUseOperandTiedToDef(Flag, TiedTo))
1678         OS << " tiedto:$" << TiedTo;
1679 
1680       OS << ']';
1681 
1682       // Compute the index of the next operand descriptor.
1683       AsmDescOp += 1 + InlineAsm::getNumOperandRegisters(Flag);
1684     } else {
1685       LLT TypeToPrint = MRI ? getTypeToPrint(i, PrintedTypes, *MRI) : LLT{};
1686       unsigned TiedOperandIdx = getTiedOperandIdx(i);
1687       if (MO.isImm() && isOperandSubregIdx(i))
1688         MachineOperand::printSubRegIdx(OS, MO.getImm(), TRI);
1689       else
1690         MO.print(OS, MST, TypeToPrint, /*PrintDef=*/true, IsStandalone,
1691                  ShouldPrintRegisterTies, TiedOperandIdx, TRI, IntrinsicInfo);
1692     }
1693   }
1694 
1695   // Print any optional symbols attached to this instruction as-if they were
1696   // operands.
1697   if (MCSymbol *PreInstrSymbol = getPreInstrSymbol()) {
1698     if (!FirstOp) {
1699       FirstOp = false;
1700       OS << ',';
1701     }
1702     OS << " pre-instr-symbol ";
1703     MachineOperand::printSymbol(OS, *PreInstrSymbol);
1704   }
1705   if (MCSymbol *PostInstrSymbol = getPostInstrSymbol()) {
1706     if (!FirstOp) {
1707       FirstOp = false;
1708       OS << ',';
1709     }
1710     OS << " post-instr-symbol ";
1711     MachineOperand::printSymbol(OS, *PostInstrSymbol);
1712   }
1713 
1714   if (!SkipDebugLoc) {
1715     if (const DebugLoc &DL = getDebugLoc()) {
1716       if (!FirstOp)
1717         OS << ',';
1718       OS << " debug-location ";
1719       DL->printAsOperand(OS, MST);
1720     }
1721   }
1722 
1723   if (!memoperands_empty()) {
1724     SmallVector<StringRef, 0> SSNs;
1725     const LLVMContext *Context = nullptr;
1726     std::unique_ptr<LLVMContext> CtxPtr;
1727     const MachineFrameInfo *MFI = nullptr;
1728     if (const MachineFunction *MF = getMFIfAvailable(*this)) {
1729       MFI = &MF->getFrameInfo();
1730       Context = &MF->getFunction().getContext();
1731     } else {
1732       CtxPtr = std::make_unique<LLVMContext>();
1733       Context = CtxPtr.get();
1734     }
1735 
1736     OS << " :: ";
1737     bool NeedComma = false;
1738     for (const MachineMemOperand *Op : memoperands()) {
1739       if (NeedComma)
1740         OS << ", ";
1741       Op->print(OS, MST, SSNs, *Context, MFI, TII);
1742       NeedComma = true;
1743     }
1744   }
1745 
1746   if (SkipDebugLoc)
1747     return;
1748 
1749   bool HaveSemi = false;
1750 
1751   // Print debug location information.
1752   if (const DebugLoc &DL = getDebugLoc()) {
1753     if (!HaveSemi) {
1754       OS << ';';
1755       HaveSemi = true;
1756     }
1757     OS << ' ';
1758     DL.print(OS);
1759   }
1760 
1761   // Print extra comments for DEBUG_VALUE.
1762   if (isDebugValue() && getOperand(e - 2).isMetadata()) {
1763     if (!HaveSemi) {
1764       OS << ";";
1765       HaveSemi = true;
1766     }
1767     auto *DV = cast<DILocalVariable>(getOperand(e - 2).getMetadata());
1768     OS << " line no:" <<  DV->getLine();
1769     if (auto *InlinedAt = debugLoc->getInlinedAt()) {
1770       DebugLoc InlinedAtDL(InlinedAt);
1771       if (InlinedAtDL && MF) {
1772         OS << " inlined @[ ";
1773         InlinedAtDL.print(OS);
1774         OS << " ]";
1775       }
1776     }
1777     if (isIndirectDebugValue())
1778       OS << " indirect";
1779   }
1780   // TODO: DBG_LABEL
1781 
1782   if (AddNewLine)
1783     OS << '\n';
1784 }
1785 
1786 bool MachineInstr::addRegisterKilled(Register IncomingReg,
1787                                      const TargetRegisterInfo *RegInfo,
1788                                      bool AddIfNotFound) {
1789   bool isPhysReg = Register::isPhysicalRegister(IncomingReg);
1790   bool hasAliases = isPhysReg &&
1791     MCRegAliasIterator(IncomingReg, RegInfo, false).isValid();
1792   bool Found = false;
1793   SmallVector<unsigned,4> DeadOps;
1794   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
1795     MachineOperand &MO = getOperand(i);
1796     if (!MO.isReg() || !MO.isUse() || MO.isUndef())
1797       continue;
1798 
1799     // DEBUG_VALUE nodes do not contribute to code generation and should
1800     // always be ignored. Failure to do so may result in trying to modify
1801     // KILL flags on DEBUG_VALUE nodes.
1802     if (MO.isDebug())
1803       continue;
1804 
1805     Register Reg = MO.getReg();
1806     if (!Reg)
1807       continue;
1808 
1809     if (Reg == IncomingReg) {
1810       if (!Found) {
1811         if (MO.isKill())
1812           // The register is already marked kill.
1813           return true;
1814         if (isPhysReg && isRegTiedToDefOperand(i))
1815           // Two-address uses of physregs must not be marked kill.
1816           return true;
1817         MO.setIsKill();
1818         Found = true;
1819       }
1820     } else if (hasAliases && MO.isKill() && Register::isPhysicalRegister(Reg)) {
1821       // A super-register kill already exists.
1822       if (RegInfo->isSuperRegister(IncomingReg, Reg))
1823         return true;
1824       if (RegInfo->isSubRegister(IncomingReg, Reg))
1825         DeadOps.push_back(i);
1826     }
1827   }
1828 
1829   // Trim unneeded kill operands.
1830   while (!DeadOps.empty()) {
1831     unsigned OpIdx = DeadOps.back();
1832     if (getOperand(OpIdx).isImplicit() &&
1833         (!isInlineAsm() || findInlineAsmFlagIdx(OpIdx) < 0))
1834       RemoveOperand(OpIdx);
1835     else
1836       getOperand(OpIdx).setIsKill(false);
1837     DeadOps.pop_back();
1838   }
1839 
1840   // If not found, this means an alias of one of the operands is killed. Add a
1841   // new implicit operand if required.
1842   if (!Found && AddIfNotFound) {
1843     addOperand(MachineOperand::CreateReg(IncomingReg,
1844                                          false /*IsDef*/,
1845                                          true  /*IsImp*/,
1846                                          true  /*IsKill*/));
1847     return true;
1848   }
1849   return Found;
1850 }
1851 
1852 void MachineInstr::clearRegisterKills(Register Reg,
1853                                       const TargetRegisterInfo *RegInfo) {
1854   if (!Register::isPhysicalRegister(Reg))
1855     RegInfo = nullptr;
1856   for (MachineOperand &MO : operands()) {
1857     if (!MO.isReg() || !MO.isUse() || !MO.isKill())
1858       continue;
1859     Register OpReg = MO.getReg();
1860     if ((RegInfo && RegInfo->regsOverlap(Reg, OpReg)) || Reg == OpReg)
1861       MO.setIsKill(false);
1862   }
1863 }
1864 
1865 bool MachineInstr::addRegisterDead(Register Reg,
1866                                    const TargetRegisterInfo *RegInfo,
1867                                    bool AddIfNotFound) {
1868   bool isPhysReg = Register::isPhysicalRegister(Reg);
1869   bool hasAliases = isPhysReg &&
1870     MCRegAliasIterator(Reg, RegInfo, false).isValid();
1871   bool Found = false;
1872   SmallVector<unsigned,4> DeadOps;
1873   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
1874     MachineOperand &MO = getOperand(i);
1875     if (!MO.isReg() || !MO.isDef())
1876       continue;
1877     Register MOReg = MO.getReg();
1878     if (!MOReg)
1879       continue;
1880 
1881     if (MOReg == Reg) {
1882       MO.setIsDead();
1883       Found = true;
1884     } else if (hasAliases && MO.isDead() &&
1885                Register::isPhysicalRegister(MOReg)) {
1886       // There exists a super-register that's marked dead.
1887       if (RegInfo->isSuperRegister(Reg, MOReg))
1888         return true;
1889       if (RegInfo->isSubRegister(Reg, MOReg))
1890         DeadOps.push_back(i);
1891     }
1892   }
1893 
1894   // Trim unneeded dead operands.
1895   while (!DeadOps.empty()) {
1896     unsigned OpIdx = DeadOps.back();
1897     if (getOperand(OpIdx).isImplicit() &&
1898         (!isInlineAsm() || findInlineAsmFlagIdx(OpIdx) < 0))
1899       RemoveOperand(OpIdx);
1900     else
1901       getOperand(OpIdx).setIsDead(false);
1902     DeadOps.pop_back();
1903   }
1904 
1905   // If not found, this means an alias of one of the operands is dead. Add a
1906   // new implicit operand if required.
1907   if (Found || !AddIfNotFound)
1908     return Found;
1909 
1910   addOperand(MachineOperand::CreateReg(Reg,
1911                                        true  /*IsDef*/,
1912                                        true  /*IsImp*/,
1913                                        false /*IsKill*/,
1914                                        true  /*IsDead*/));
1915   return true;
1916 }
1917 
1918 void MachineInstr::clearRegisterDeads(Register Reg) {
1919   for (MachineOperand &MO : operands()) {
1920     if (!MO.isReg() || !MO.isDef() || MO.getReg() != Reg)
1921       continue;
1922     MO.setIsDead(false);
1923   }
1924 }
1925 
1926 void MachineInstr::setRegisterDefReadUndef(Register Reg, bool IsUndef) {
1927   for (MachineOperand &MO : operands()) {
1928     if (!MO.isReg() || !MO.isDef() || MO.getReg() != Reg || MO.getSubReg() == 0)
1929       continue;
1930     MO.setIsUndef(IsUndef);
1931   }
1932 }
1933 
1934 void MachineInstr::addRegisterDefined(Register Reg,
1935                                       const TargetRegisterInfo *RegInfo) {
1936   if (Register::isPhysicalRegister(Reg)) {
1937     MachineOperand *MO = findRegisterDefOperand(Reg, false, false, RegInfo);
1938     if (MO)
1939       return;
1940   } else {
1941     for (const MachineOperand &MO : operands()) {
1942       if (MO.isReg() && MO.getReg() == Reg && MO.isDef() &&
1943           MO.getSubReg() == 0)
1944         return;
1945     }
1946   }
1947   addOperand(MachineOperand::CreateReg(Reg,
1948                                        true  /*IsDef*/,
1949                                        true  /*IsImp*/));
1950 }
1951 
1952 void MachineInstr::setPhysRegsDeadExcept(ArrayRef<Register> UsedRegs,
1953                                          const TargetRegisterInfo &TRI) {
1954   bool HasRegMask = false;
1955   for (MachineOperand &MO : operands()) {
1956     if (MO.isRegMask()) {
1957       HasRegMask = true;
1958       continue;
1959     }
1960     if (!MO.isReg() || !MO.isDef()) continue;
1961     Register Reg = MO.getReg();
1962     if (!Reg.isPhysical())
1963       continue;
1964     // If there are no uses, including partial uses, the def is dead.
1965     if (llvm::none_of(UsedRegs,
1966                       [&](MCRegister Use) { return TRI.regsOverlap(Use, Reg); }))
1967       MO.setIsDead();
1968   }
1969 
1970   // This is a call with a register mask operand.
1971   // Mask clobbers are always dead, so add defs for the non-dead defines.
1972   if (HasRegMask)
1973     for (ArrayRef<Register>::iterator I = UsedRegs.begin(), E = UsedRegs.end();
1974          I != E; ++I)
1975       addRegisterDefined(*I, &TRI);
1976 }
1977 
1978 unsigned
1979 MachineInstrExpressionTrait::getHashValue(const MachineInstr* const &MI) {
1980   // Build up a buffer of hash code components.
1981   SmallVector<size_t, 8> HashComponents;
1982   HashComponents.reserve(MI->getNumOperands() + 1);
1983   HashComponents.push_back(MI->getOpcode());
1984   for (const MachineOperand &MO : MI->operands()) {
1985     if (MO.isReg() && MO.isDef() && Register::isVirtualRegister(MO.getReg()))
1986       continue;  // Skip virtual register defs.
1987 
1988     HashComponents.push_back(hash_value(MO));
1989   }
1990   return hash_combine_range(HashComponents.begin(), HashComponents.end());
1991 }
1992 
1993 void MachineInstr::emitError(StringRef Msg) const {
1994   // Find the source location cookie.
1995   unsigned LocCookie = 0;
1996   const MDNode *LocMD = nullptr;
1997   for (unsigned i = getNumOperands(); i != 0; --i) {
1998     if (getOperand(i-1).isMetadata() &&
1999         (LocMD = getOperand(i-1).getMetadata()) &&
2000         LocMD->getNumOperands() != 0) {
2001       if (const ConstantInt *CI =
2002               mdconst::dyn_extract<ConstantInt>(LocMD->getOperand(0))) {
2003         LocCookie = CI->getZExtValue();
2004         break;
2005       }
2006     }
2007   }
2008 
2009   if (const MachineBasicBlock *MBB = getParent())
2010     if (const MachineFunction *MF = MBB->getParent())
2011       return MF->getMMI().getModule()->getContext().emitError(LocCookie, Msg);
2012   report_fatal_error(Msg);
2013 }
2014 
2015 MachineInstrBuilder llvm::BuildMI(MachineFunction &MF, const DebugLoc &DL,
2016                                   const MCInstrDesc &MCID, bool IsIndirect,
2017                                   Register Reg, const MDNode *Variable,
2018                                   const MDNode *Expr) {
2019   assert(isa<DILocalVariable>(Variable) && "not a variable");
2020   assert(cast<DIExpression>(Expr)->isValid() && "not an expression");
2021   assert(cast<DILocalVariable>(Variable)->isValidLocationForIntrinsic(DL) &&
2022          "Expected inlined-at fields to agree");
2023   auto MIB = BuildMI(MF, DL, MCID).addReg(Reg, RegState::Debug);
2024   if (IsIndirect)
2025     MIB.addImm(0U);
2026   else
2027     MIB.addReg(0U, RegState::Debug);
2028   return MIB.addMetadata(Variable).addMetadata(Expr);
2029 }
2030 
2031 MachineInstrBuilder llvm::BuildMI(MachineFunction &MF, const DebugLoc &DL,
2032                                   const MCInstrDesc &MCID, bool IsIndirect,
2033                                   MachineOperand &MO, const MDNode *Variable,
2034                                   const MDNode *Expr) {
2035   assert(isa<DILocalVariable>(Variable) && "not a variable");
2036   assert(cast<DIExpression>(Expr)->isValid() && "not an expression");
2037   assert(cast<DILocalVariable>(Variable)->isValidLocationForIntrinsic(DL) &&
2038          "Expected inlined-at fields to agree");
2039   if (MO.isReg())
2040     return BuildMI(MF, DL, MCID, IsIndirect, MO.getReg(), Variable, Expr);
2041 
2042   auto MIB = BuildMI(MF, DL, MCID).add(MO);
2043   if (IsIndirect)
2044     MIB.addImm(0U);
2045   else
2046     MIB.addReg(0U, RegState::Debug);
2047   return MIB.addMetadata(Variable).addMetadata(Expr);
2048  }
2049 
2050 MachineInstrBuilder llvm::BuildMI(MachineBasicBlock &BB,
2051                                   MachineBasicBlock::iterator I,
2052                                   const DebugLoc &DL, const MCInstrDesc &MCID,
2053                                   bool IsIndirect, Register Reg,
2054                                   const MDNode *Variable, const MDNode *Expr) {
2055   MachineFunction &MF = *BB.getParent();
2056   MachineInstr *MI = BuildMI(MF, DL, MCID, IsIndirect, Reg, Variable, Expr);
2057   BB.insert(I, MI);
2058   return MachineInstrBuilder(MF, MI);
2059 }
2060 
2061 MachineInstrBuilder llvm::BuildMI(MachineBasicBlock &BB,
2062                                   MachineBasicBlock::iterator I,
2063                                   const DebugLoc &DL, const MCInstrDesc &MCID,
2064                                   bool IsIndirect, MachineOperand &MO,
2065                                   const MDNode *Variable, const MDNode *Expr) {
2066   MachineFunction &MF = *BB.getParent();
2067   MachineInstr *MI = BuildMI(MF, DL, MCID, IsIndirect, MO, Variable, Expr);
2068   BB.insert(I, MI);
2069   return MachineInstrBuilder(MF, *MI);
2070 }
2071 
2072 /// Compute the new DIExpression to use with a DBG_VALUE for a spill slot.
2073 /// This prepends DW_OP_deref when spilling an indirect DBG_VALUE.
2074 static const DIExpression *computeExprForSpill(const MachineInstr &MI) {
2075   assert(MI.getOperand(0).isReg() && "can't spill non-register");
2076   assert(MI.getDebugVariable()->isValidLocationForIntrinsic(MI.getDebugLoc()) &&
2077          "Expected inlined-at fields to agree");
2078 
2079   const DIExpression *Expr = MI.getDebugExpression();
2080   if (MI.isIndirectDebugValue()) {
2081     assert(MI.getOperand(1).getImm() == 0 && "DBG_VALUE with nonzero offset");
2082     Expr = DIExpression::prepend(Expr, DIExpression::DerefBefore);
2083   }
2084   return Expr;
2085 }
2086 
2087 MachineInstr *llvm::buildDbgValueForSpill(MachineBasicBlock &BB,
2088                                           MachineBasicBlock::iterator I,
2089                                           const MachineInstr &Orig,
2090                                           int FrameIndex) {
2091   const DIExpression *Expr = computeExprForSpill(Orig);
2092   return BuildMI(BB, I, Orig.getDebugLoc(), Orig.getDesc())
2093       .addFrameIndex(FrameIndex)
2094       .addImm(0U)
2095       .addMetadata(Orig.getDebugVariable())
2096       .addMetadata(Expr);
2097 }
2098 
2099 void llvm::updateDbgValueForSpill(MachineInstr &Orig, int FrameIndex) {
2100   const DIExpression *Expr = computeExprForSpill(Orig);
2101   Orig.getOperand(0).ChangeToFrameIndex(FrameIndex);
2102   Orig.getOperand(1).ChangeToImmediate(0U);
2103   Orig.getOperand(3).setMetadata(Expr);
2104 }
2105 
2106 void MachineInstr::collectDebugValues(
2107                                 SmallVectorImpl<MachineInstr *> &DbgValues) {
2108   MachineInstr &MI = *this;
2109   if (!MI.getOperand(0).isReg())
2110     return;
2111 
2112   MachineBasicBlock::iterator DI = MI; ++DI;
2113   for (MachineBasicBlock::iterator DE = MI.getParent()->end();
2114        DI != DE; ++DI) {
2115     if (!DI->isDebugValue())
2116       return;
2117     if (DI->getOperand(0).isReg() &&
2118         DI->getOperand(0).getReg() == MI.getOperand(0).getReg())
2119       DbgValues.push_back(&*DI);
2120   }
2121 }
2122 
2123 void MachineInstr::changeDebugValuesDefReg(Register Reg) {
2124   // Collect matching debug values.
2125   SmallVector<MachineInstr *, 2> DbgValues;
2126 
2127   if (!getOperand(0).isReg())
2128     return;
2129 
2130   unsigned DefReg = getOperand(0).getReg();
2131   auto *MRI = getRegInfo();
2132   for (auto &MO : MRI->use_operands(DefReg)) {
2133     auto *DI = MO.getParent();
2134     if (!DI->isDebugValue())
2135       continue;
2136     if (DI->getOperand(0).isReg() &&
2137         DI->getOperand(0).getReg() == DefReg){
2138       DbgValues.push_back(DI);
2139     }
2140   }
2141 
2142   // Propagate Reg to debug value instructions.
2143   for (auto *DBI : DbgValues)
2144     DBI->getOperand(0).setReg(Reg);
2145 }
2146 
2147 using MMOList = SmallVector<const MachineMemOperand *, 2>;
2148 
2149 static unsigned getSpillSlotSize(MMOList &Accesses,
2150                                  const MachineFrameInfo &MFI) {
2151   unsigned Size = 0;
2152   for (auto A : Accesses)
2153     if (MFI.isSpillSlotObjectIndex(
2154             cast<FixedStackPseudoSourceValue>(A->getPseudoValue())
2155                 ->getFrameIndex()))
2156       Size += A->getSize();
2157   return Size;
2158 }
2159 
2160 Optional<unsigned>
2161 MachineInstr::getSpillSize(const TargetInstrInfo *TII) const {
2162   int FI;
2163   if (TII->isStoreToStackSlotPostFE(*this, FI)) {
2164     const MachineFrameInfo &MFI = getMF()->getFrameInfo();
2165     if (MFI.isSpillSlotObjectIndex(FI))
2166       return (*memoperands_begin())->getSize();
2167   }
2168   return None;
2169 }
2170 
2171 Optional<unsigned>
2172 MachineInstr::getFoldedSpillSize(const TargetInstrInfo *TII) const {
2173   MMOList Accesses;
2174   if (TII->hasStoreToStackSlot(*this, Accesses))
2175     return getSpillSlotSize(Accesses, getMF()->getFrameInfo());
2176   return None;
2177 }
2178 
2179 Optional<unsigned>
2180 MachineInstr::getRestoreSize(const TargetInstrInfo *TII) const {
2181   int FI;
2182   if (TII->isLoadFromStackSlotPostFE(*this, FI)) {
2183     const MachineFrameInfo &MFI = getMF()->getFrameInfo();
2184     if (MFI.isSpillSlotObjectIndex(FI))
2185       return (*memoperands_begin())->getSize();
2186   }
2187   return None;
2188 }
2189 
2190 Optional<unsigned>
2191 MachineInstr::getFoldedRestoreSize(const TargetInstrInfo *TII) const {
2192   MMOList Accesses;
2193   if (TII->hasLoadFromStackSlot(*this, Accesses))
2194     return getSpillSlotSize(Accesses, getMF()->getFrameInfo());
2195   return None;
2196 }
2197