Bug Summary

File:lib/CodeGen/RegisterCoalescer.cpp
Warning:line 3216, column 16
Assigned value is garbage or undefined

Annotated Source Code

[?] Use j/k keys for keyboard navigation

/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp

1//===- RegisterCoalescer.cpp - Generic Register Coalescing Interface ------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements the generic RegisterCoalescer interface which
11// is used as the common interface used by all clients and
12// implementations of register coalescing.
13//
14//===----------------------------------------------------------------------===//
15
16#include "RegisterCoalescer.h"
17#include "llvm/ADT/ArrayRef.h"
18#include "llvm/ADT/BitVector.h"
19#include "llvm/ADT/STLExtras.h"
20#include "llvm/ADT/SmallPtrSet.h"
21#include "llvm/ADT/SmallVector.h"
22#include "llvm/ADT/Statistic.h"
23#include "llvm/Analysis/AliasAnalysis.h"
24#include "llvm/CodeGen/LiveInterval.h"
25#include "llvm/CodeGen/LiveIntervals.h"
26#include "llvm/CodeGen/LiveRangeEdit.h"
27#include "llvm/CodeGen/MachineBasicBlock.h"
28#include "llvm/CodeGen/MachineFunction.h"
29#include "llvm/CodeGen/MachineFunctionPass.h"
30#include "llvm/CodeGen/MachineInstr.h"
31#include "llvm/CodeGen/MachineInstrBuilder.h"
32#include "llvm/CodeGen/MachineLoopInfo.h"
33#include "llvm/CodeGen/MachineOperand.h"
34#include "llvm/CodeGen/MachineRegisterInfo.h"
35#include "llvm/CodeGen/Passes.h"
36#include "llvm/CodeGen/RegisterClassInfo.h"
37#include "llvm/CodeGen/SlotIndexes.h"
38#include "llvm/CodeGen/TargetInstrInfo.h"
39#include "llvm/CodeGen/TargetOpcodes.h"
40#include "llvm/CodeGen/TargetRegisterInfo.h"
41#include "llvm/CodeGen/TargetSubtargetInfo.h"
42#include "llvm/IR/DebugLoc.h"
43#include "llvm/MC/LaneBitmask.h"
44#include "llvm/MC/MCInstrDesc.h"
45#include "llvm/MC/MCRegisterInfo.h"
46#include "llvm/Pass.h"
47#include "llvm/Support/CommandLine.h"
48#include "llvm/Support/Compiler.h"
49#include "llvm/Support/Debug.h"
50#include "llvm/Support/ErrorHandling.h"
51#include "llvm/Support/raw_ostream.h"
52#include <algorithm>
53#include <cassert>
54#include <iterator>
55#include <limits>
56#include <tuple>
57#include <utility>
58#include <vector>
59
60using namespace llvm;
61
62#define DEBUG_TYPE"regalloc" "regalloc"
63
64STATISTIC(numJoins , "Number of interval joins performed")static llvm::Statistic numJoins = {"regalloc", "numJoins", "Number of interval joins performed"
, {0}, false}
;
65STATISTIC(numCrossRCs , "Number of cross class joins performed")static llvm::Statistic numCrossRCs = {"regalloc", "numCrossRCs"
, "Number of cross class joins performed", {0}, false}
;
66STATISTIC(numCommutes , "Number of instruction commuting performed")static llvm::Statistic numCommutes = {"regalloc", "numCommutes"
, "Number of instruction commuting performed", {0}, false}
;
67STATISTIC(numExtends , "Number of copies extended")static llvm::Statistic numExtends = {"regalloc", "numExtends"
, "Number of copies extended", {0}, false}
;
68STATISTIC(NumReMats , "Number of instructions re-materialized")static llvm::Statistic NumReMats = {"regalloc", "NumReMats", "Number of instructions re-materialized"
, {0}, false}
;
69STATISTIC(NumInflated , "Number of register classes inflated")static llvm::Statistic NumInflated = {"regalloc", "NumInflated"
, "Number of register classes inflated", {0}, false}
;
70STATISTIC(NumLaneConflicts, "Number of dead lane conflicts tested")static llvm::Statistic NumLaneConflicts = {"regalloc", "NumLaneConflicts"
, "Number of dead lane conflicts tested", {0}, false}
;
71STATISTIC(NumLaneResolves, "Number of dead lane conflicts resolved")static llvm::Statistic NumLaneResolves = {"regalloc", "NumLaneResolves"
, "Number of dead lane conflicts resolved", {0}, false}
;
72
73static cl::opt<bool> EnableJoining("join-liveintervals",
74 cl::desc("Coalesce copies (default=true)"),
75 cl::init(true), cl::Hidden);
76
77static cl::opt<bool> UseTerminalRule("terminal-rule",
78 cl::desc("Apply the terminal rule"),
79 cl::init(false), cl::Hidden);
80
81/// Temporary flag to test critical edge unsplitting.
82static cl::opt<bool>
83EnableJoinSplits("join-splitedges",
84 cl::desc("Coalesce copies on split edges (default=subtarget)"), cl::Hidden);
85
86/// Temporary flag to test global copy optimization.
87static cl::opt<cl::boolOrDefault>
88EnableGlobalCopies("join-globalcopies",
89 cl::desc("Coalesce copies that span blocks (default=subtarget)"),
90 cl::init(cl::BOU_UNSET), cl::Hidden);
91
92static cl::opt<bool>
93VerifyCoalescing("verify-coalescing",
94 cl::desc("Verify machine instrs before and after register coalescing"),
95 cl::Hidden);
96
97namespace {
98
99 class RegisterCoalescer : public MachineFunctionPass,
100 private LiveRangeEdit::Delegate {
101 MachineFunction* MF;
102 MachineRegisterInfo* MRI;
103 const TargetRegisterInfo* TRI;
104 const TargetInstrInfo* TII;
105 LiveIntervals *LIS;
106 const MachineLoopInfo* Loops;
107 AliasAnalysis *AA;
108 RegisterClassInfo RegClassInfo;
109
110 /// A LaneMask to remember on which subregister live ranges we need to call
111 /// shrinkToUses() later.
112 LaneBitmask ShrinkMask;
113
114 /// True if the main range of the currently coalesced intervals should be
115 /// checked for smaller live intervals.
116 bool ShrinkMainRange;
117
118 /// \brief True if the coalescer should aggressively coalesce global copies
119 /// in favor of keeping local copies.
120 bool JoinGlobalCopies;
121
122 /// \brief True if the coalescer should aggressively coalesce fall-thru
123 /// blocks exclusively containing copies.
124 bool JoinSplitEdges;
125
126 /// Copy instructions yet to be coalesced.
127 SmallVector<MachineInstr*, 8> WorkList;
128 SmallVector<MachineInstr*, 8> LocalWorkList;
129
130 /// Set of instruction pointers that have been erased, and
131 /// that may be present in WorkList.
132 SmallPtrSet<MachineInstr*, 8> ErasedInstrs;
133
134 /// Dead instructions that are about to be deleted.
135 SmallVector<MachineInstr*, 8> DeadDefs;
136
137 /// Virtual registers to be considered for register class inflation.
138 SmallVector<unsigned, 8> InflateRegs;
139
140 /// Recursively eliminate dead defs in DeadDefs.
141 void eliminateDeadDefs();
142
143 /// LiveRangeEdit callback for eliminateDeadDefs().
144 void LRE_WillEraseInstruction(MachineInstr *MI) override;
145
146 /// Coalesce the LocalWorkList.
147 void coalesceLocals();
148
149 /// Join compatible live intervals
150 void joinAllIntervals();
151
152 /// Coalesce copies in the specified MBB, putting
153 /// copies that cannot yet be coalesced into WorkList.
154 void copyCoalesceInMBB(MachineBasicBlock *MBB);
155
156 /// Tries to coalesce all copies in CurrList. Returns true if any progress
157 /// was made.
158 bool copyCoalesceWorkList(MutableArrayRef<MachineInstr*> CurrList);
159
160 /// Attempt to join intervals corresponding to SrcReg/DstReg, which are the
161 /// src/dst of the copy instruction CopyMI. This returns true if the copy
162 /// was successfully coalesced away. If it is not currently possible to
163 /// coalesce this interval, but it may be possible if other things get
164 /// coalesced, then it returns true by reference in 'Again'.
165 bool joinCopy(MachineInstr *TheCopy, bool &Again);
166
167 /// Attempt to join these two intervals. On failure, this
168 /// returns false. The output "SrcInt" will not have been modified, so we
169 /// can use this information below to update aliases.
170 bool joinIntervals(CoalescerPair &CP);
171
172 /// Attempt joining two virtual registers. Return true on success.
173 bool joinVirtRegs(CoalescerPair &CP);
174
175 /// Attempt joining with a reserved physreg.
176 bool joinReservedPhysReg(CoalescerPair &CP);
177
178 /// Add the LiveRange @p ToMerge as a subregister liverange of @p LI.
179 /// Subranges in @p LI which only partially interfere with the desired
180 /// LaneMask are split as necessary. @p LaneMask are the lanes that
181 /// @p ToMerge will occupy in the coalescer register. @p LI has its subrange
182 /// lanemasks already adjusted to the coalesced register.
183 void mergeSubRangeInto(LiveInterval &LI, const LiveRange &ToMerge,
184 LaneBitmask LaneMask, CoalescerPair &CP);
185
186 /// Join the liveranges of two subregisters. Joins @p RRange into
187 /// @p LRange, @p RRange may be invalid afterwards.
188 void joinSubRegRanges(LiveRange &LRange, LiveRange &RRange,
189 LaneBitmask LaneMask, const CoalescerPair &CP);
190
191 /// We found a non-trivially-coalescable copy. If the source value number is
192 /// defined by a copy from the destination reg see if we can merge these two
193 /// destination reg valno# into a single value number, eliminating a copy.
194 /// This returns true if an interval was modified.
195 bool adjustCopiesBackFrom(const CoalescerPair &CP, MachineInstr *CopyMI);
196
197 /// Return true if there are definitions of IntB
198 /// other than BValNo val# that can reach uses of AValno val# of IntA.
199 bool hasOtherReachingDefs(LiveInterval &IntA, LiveInterval &IntB,
200 VNInfo *AValNo, VNInfo *BValNo);
201
202 /// We found a non-trivially-coalescable copy.
203 /// If the source value number is defined by a commutable instruction and
204 /// its other operand is coalesced to the copy dest register, see if we
205 /// can transform the copy into a noop by commuting the definition.
206 /// This returns true if an interval was modified.
207 bool removeCopyByCommutingDef(const CoalescerPair &CP,MachineInstr *CopyMI);
208
209 /// We found a copy which can be moved to its less frequent predecessor.
210 bool removePartialRedundancy(const CoalescerPair &CP, MachineInstr &CopyMI);
211
212 /// If the source of a copy is defined by a
213 /// trivial computation, replace the copy by rematerialize the definition.
214 bool reMaterializeTrivialDef(const CoalescerPair &CP, MachineInstr *CopyMI,
215 bool &IsDefCopy);
216
217 /// Return true if a copy involving a physreg should be joined.
218 bool canJoinPhys(const CoalescerPair &CP);
219
220 /// Replace all defs and uses of SrcReg to DstReg and update the subregister
221 /// number if it is not zero. If DstReg is a physical register and the
222 /// existing subregister number of the def / use being updated is not zero,
223 /// make sure to set it to the correct physical subregister.
224 void updateRegDefsUses(unsigned SrcReg, unsigned DstReg, unsigned SubIdx);
225
226 /// If the given machine operand reads only undefined lanes add an undef
227 /// flag.
228 /// This can happen when undef uses were previously concealed by a copy
229 /// which we coalesced. Example:
230 /// %0:sub0<def,read-undef> = ...
231 /// %1 = COPY %0 <-- Coalescing COPY reveals undef
232 /// = use %1:sub1 <-- hidden undef use
233 void addUndefFlag(const LiveInterval &Int, SlotIndex UseIdx,
234 MachineOperand &MO, unsigned SubRegIdx);
235
236 /// Handle copies of undef values.
237 /// Returns true if @p CopyMI was a copy of an undef value and eliminated.
238 bool eliminateUndefCopy(MachineInstr *CopyMI);
239
240 /// Check whether or not we should apply the terminal rule on the
241 /// destination (Dst) of \p Copy.
242 /// When the terminal rule applies, Copy is not profitable to
243 /// coalesce.
244 /// Dst is terminal if it has exactly one affinity (Dst, Src) and
245 /// at least one interference (Dst, Dst2). If Dst is terminal, the
246 /// terminal rule consists in checking that at least one of
247 /// interfering node, say Dst2, has an affinity of equal or greater
248 /// weight with Src.
249 /// In that case, Dst2 and Dst will not be able to be both coalesced
250 /// with Src. Since Dst2 exposes more coalescing opportunities than
251 /// Dst, we can drop \p Copy.
252 bool applyTerminalRule(const MachineInstr &Copy) const;
253
254 /// Wrapper method for \see LiveIntervals::shrinkToUses.
255 /// This method does the proper fixing of the live-ranges when the afore
256 /// mentioned method returns true.
257 void shrinkToUses(LiveInterval *LI,
258 SmallVectorImpl<MachineInstr * > *Dead = nullptr) {
259 if (LIS->shrinkToUses(LI, Dead)) {
260 /// Check whether or not \p LI is composed by multiple connected
261 /// components and if that is the case, fix that.
262 SmallVector<LiveInterval*, 8> SplitLIs;
263 LIS->splitSeparateComponents(*LI, SplitLIs);
264 }
265 }
266
267 /// Wrapper Method to do all the necessary work when an Instruction is
268 /// deleted.
269 /// Optimizations should use this to make sure that deleted instructions
270 /// are always accounted for.
271 void deleteInstr(MachineInstr* MI) {
272 ErasedInstrs.insert(MI);
273 LIS->RemoveMachineInstrFromMaps(*MI);
274 MI->eraseFromParent();
275 }
276
277 public:
278 static char ID; ///< Class identification, replacement for typeinfo
279
280 RegisterCoalescer() : MachineFunctionPass(ID) {
281 initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry());
282 }
283
284 void getAnalysisUsage(AnalysisUsage &AU) const override;
285
286 void releaseMemory() override;
287
288 /// This is the pass entry point.
289 bool runOnMachineFunction(MachineFunction&) override;
290
291 /// Implement the dump method.
292 void print(raw_ostream &O, const Module* = nullptr) const override;
293 };
294
295} // end anonymous namespace
296
297char RegisterCoalescer::ID = 0;
298
299char &llvm::RegisterCoalescerID = RegisterCoalescer::ID;
300
301INITIALIZE_PASS_BEGIN(RegisterCoalescer, "simple-register-coalescing",static void *initializeRegisterCoalescerPassOnce(PassRegistry
&Registry) {
302 "Simple Register Coalescing", false, false)static void *initializeRegisterCoalescerPassOnce(PassRegistry
&Registry) {
303INITIALIZE_PASS_DEPENDENCY(LiveIntervals)initializeLiveIntervalsPass(Registry);
304INITIALIZE_PASS_DEPENDENCY(SlotIndexes)initializeSlotIndexesPass(Registry);
305INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)initializeMachineLoopInfoPass(Registry);
306INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)initializeAAResultsWrapperPassPass(Registry);
307INITIALIZE_PASS_END(RegisterCoalescer, "simple-register-coalescing",PassInfo *PI = new PassInfo( "Simple Register Coalescing", "simple-register-coalescing"
, &RegisterCoalescer::ID, PassInfo::NormalCtor_t(callDefaultCtor
<RegisterCoalescer>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeRegisterCoalescerPassFlag
; void llvm::initializeRegisterCoalescerPass(PassRegistry &
Registry) { llvm::call_once(InitializeRegisterCoalescerPassFlag
, initializeRegisterCoalescerPassOnce, std::ref(Registry)); }
308 "Simple Register Coalescing", false, false)PassInfo *PI = new PassInfo( "Simple Register Coalescing", "simple-register-coalescing"
, &RegisterCoalescer::ID, PassInfo::NormalCtor_t(callDefaultCtor
<RegisterCoalescer>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeRegisterCoalescerPassFlag
; void llvm::initializeRegisterCoalescerPass(PassRegistry &
Registry) { llvm::call_once(InitializeRegisterCoalescerPassFlag
, initializeRegisterCoalescerPassOnce, std::ref(Registry)); }
309
310static bool isMoveInstr(const TargetRegisterInfo &tri, const MachineInstr *MI,
311 unsigned &Src, unsigned &Dst,
312 unsigned &SrcSub, unsigned &DstSub) {
313 if (MI->isCopy()) {
27
Calling 'MachineInstr::isCopy'
31
Returning from 'MachineInstr::isCopy'
32
Taking false branch
50
Calling 'MachineInstr::isCopy'
54
Returning from 'MachineInstr::isCopy'
55
Taking false branch
314 Dst = MI->getOperand(0).getReg();
315 DstSub = MI->getOperand(0).getSubReg();
316 Src = MI->getOperand(1).getReg();
317 SrcSub = MI->getOperand(1).getSubReg();
318 } else if (MI->isSubregToReg()) {
33
Calling 'MachineInstr::isSubregToReg'
37
Returning from 'MachineInstr::isSubregToReg'
38
Taking true branch
56
Calling 'MachineInstr::isSubregToReg'
60
Returning from 'MachineInstr::isSubregToReg'
61
Taking false branch
319 Dst = MI->getOperand(0).getReg();
320 DstSub = tri.composeSubRegIndices(MI->getOperand(0).getSubReg(),
321 MI->getOperand(3).getImm());
322 Src = MI->getOperand(2).getReg();
323 SrcSub = MI->getOperand(2).getSubReg();
324 } else
325 return false;
326 return true;
327}
328
329/// Return true if this block should be vacated by the coalescer to eliminate
330/// branches. The important cases to handle in the coalescer are critical edges
331/// split during phi elimination which contain only copies. Simple blocks that
332/// contain non-branches should also be vacated, but this can be handled by an
333/// earlier pass similar to early if-conversion.
334static bool isSplitEdge(const MachineBasicBlock *MBB) {
335 if (MBB->pred_size() != 1 || MBB->succ_size() != 1)
336 return false;
337
338 for (const auto &MI : *MBB) {
339 if (!MI.isCopyLike() && !MI.isUnconditionalBranch())
340 return false;
341 }
342 return true;
343}
344
345bool CoalescerPair::setRegisters(const MachineInstr *MI) {
346 SrcReg = DstReg = 0;
347 SrcIdx = DstIdx = 0;
348 NewRC = nullptr;
349 Flipped = CrossClass = false;
350
351 unsigned Src, Dst, SrcSub, DstSub;
352 if (!isMoveInstr(TRI, MI, Src, Dst, SrcSub, DstSub))
353 return false;
354 Partial = SrcSub || DstSub;
355
356 // If one register is a physreg, it must be Dst.
357 if (TargetRegisterInfo::isPhysicalRegister(Src)) {
358 if (TargetRegisterInfo::isPhysicalRegister(Dst))
359 return false;
360 std::swap(Src, Dst);
361 std::swap(SrcSub, DstSub);
362 Flipped = true;
363 }
364
365 const MachineRegisterInfo &MRI = MI->getMF()->getRegInfo();
366
367 if (TargetRegisterInfo::isPhysicalRegister(Dst)) {
368 // Eliminate DstSub on a physreg.
369 if (DstSub) {
370 Dst = TRI.getSubReg(Dst, DstSub);
371 if (!Dst) return false;
372 DstSub = 0;
373 }
374
375 // Eliminate SrcSub by picking a corresponding Dst superregister.
376 if (SrcSub) {
377 Dst = TRI.getMatchingSuperReg(Dst, SrcSub, MRI.getRegClass(Src));
378 if (!Dst) return false;
379 } else if (!MRI.getRegClass(Src)->contains(Dst)) {
380 return false;
381 }
382 } else {
383 // Both registers are virtual.
384 const TargetRegisterClass *SrcRC = MRI.getRegClass(Src);
385 const TargetRegisterClass *DstRC = MRI.getRegClass(Dst);
386
387 // Both registers have subreg indices.
388 if (SrcSub && DstSub) {
389 // Copies between different sub-registers are never coalescable.
390 if (Src == Dst && SrcSub != DstSub)
391 return false;
392
393 NewRC = TRI.getCommonSuperRegClass(SrcRC, SrcSub, DstRC, DstSub,
394 SrcIdx, DstIdx);
395 if (!NewRC)
396 return false;
397 } else if (DstSub) {
398 // SrcReg will be merged with a sub-register of DstReg.
399 SrcIdx = DstSub;
400 NewRC = TRI.getMatchingSuperRegClass(DstRC, SrcRC, DstSub);
401 } else if (SrcSub) {
402 // DstReg will be merged with a sub-register of SrcReg.
403 DstIdx = SrcSub;
404 NewRC = TRI.getMatchingSuperRegClass(SrcRC, DstRC, SrcSub);
405 } else {
406 // This is a straight copy without sub-registers.
407 NewRC = TRI.getCommonSubClass(DstRC, SrcRC);
408 }
409
410 // The combined constraint may be impossible to satisfy.
411 if (!NewRC)
412 return false;
413
414 // Prefer SrcReg to be a sub-register of DstReg.
415 // FIXME: Coalescer should support subregs symmetrically.
416 if (DstIdx && !SrcIdx) {
417 std::swap(Src, Dst);
418 std::swap(SrcIdx, DstIdx);
419 Flipped = !Flipped;
420 }
421
422 CrossClass = NewRC != DstRC || NewRC != SrcRC;
423 }
424 // Check our invariants
425 assert(TargetRegisterInfo::isVirtualRegister(Src) && "Src must be virtual")(static_cast <bool> (TargetRegisterInfo::isVirtualRegister
(Src) && "Src must be virtual") ? void (0) : __assert_fail
("TargetRegisterInfo::isVirtualRegister(Src) && \"Src must be virtual\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 425, __extension__ __PRETTY_FUNCTION__))
;
426 assert(!(TargetRegisterInfo::isPhysicalRegister(Dst) && DstSub) &&(static_cast <bool> (!(TargetRegisterInfo::isPhysicalRegister
(Dst) && DstSub) && "Cannot have a physical SubIdx"
) ? void (0) : __assert_fail ("!(TargetRegisterInfo::isPhysicalRegister(Dst) && DstSub) && \"Cannot have a physical SubIdx\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 427, __extension__ __PRETTY_FUNCTION__))
427 "Cannot have a physical SubIdx")(static_cast <bool> (!(TargetRegisterInfo::isPhysicalRegister
(Dst) && DstSub) && "Cannot have a physical SubIdx"
) ? void (0) : __assert_fail ("!(TargetRegisterInfo::isPhysicalRegister(Dst) && DstSub) && \"Cannot have a physical SubIdx\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 427, __extension__ __PRETTY_FUNCTION__))
;
428 SrcReg = Src;
429 DstReg = Dst;
430 return true;
431}
432
433bool CoalescerPair::flip() {
434 if (TargetRegisterInfo::isPhysicalRegister(DstReg))
435 return false;
436 std::swap(SrcReg, DstReg);
437 std::swap(SrcIdx, DstIdx);
438 Flipped = !Flipped;
439 return true;
440}
441
442bool CoalescerPair::isCoalescable(const MachineInstr *MI) const {
443 if (!MI)
444 return false;
445 unsigned Src, Dst, SrcSub, DstSub;
446 if (!isMoveInstr(TRI, MI, Src, Dst, SrcSub, DstSub))
447 return false;
448
449 // Find the virtual register that is SrcReg.
450 if (Dst == SrcReg) {
451 std::swap(Src, Dst);
452 std::swap(SrcSub, DstSub);
453 } else if (Src != SrcReg) {
454 return false;
455 }
456
457 // Now check that Dst matches DstReg.
458 if (TargetRegisterInfo::isPhysicalRegister(DstReg)) {
459 if (!TargetRegisterInfo::isPhysicalRegister(Dst))
460 return false;
461 assert(!DstIdx && !SrcIdx && "Inconsistent CoalescerPair state.")(static_cast <bool> (!DstIdx && !SrcIdx &&
"Inconsistent CoalescerPair state.") ? void (0) : __assert_fail
("!DstIdx && !SrcIdx && \"Inconsistent CoalescerPair state.\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 461, __extension__ __PRETTY_FUNCTION__))
;
462 // DstSub could be set for a physreg from INSERT_SUBREG.
463 if (DstSub)
464 Dst = TRI.getSubReg(Dst, DstSub);
465 // Full copy of Src.
466 if (!SrcSub)
467 return DstReg == Dst;
468 // This is a partial register copy. Check that the parts match.
469 return TRI.getSubReg(DstReg, SrcSub) == Dst;
470 } else {
471 // DstReg is virtual.
472 if (DstReg != Dst)
473 return false;
474 // Registers match, do the subregisters line up?
475 return TRI.composeSubRegIndices(SrcIdx, SrcSub) ==
476 TRI.composeSubRegIndices(DstIdx, DstSub);
477 }
478}
479
480void RegisterCoalescer::getAnalysisUsage(AnalysisUsage &AU) const {
481 AU.setPreservesCFG();
482 AU.addRequired<AAResultsWrapperPass>();
483 AU.addRequired<LiveIntervals>();
484 AU.addPreserved<LiveIntervals>();
485 AU.addPreserved<SlotIndexes>();
486 AU.addRequired<MachineLoopInfo>();
487 AU.addPreserved<MachineLoopInfo>();
488 AU.addPreservedID(MachineDominatorsID);
489 MachineFunctionPass::getAnalysisUsage(AU);
490}
491
492void RegisterCoalescer::eliminateDeadDefs() {
493 SmallVector<unsigned, 8> NewRegs;
494 LiveRangeEdit(nullptr, NewRegs, *MF, *LIS,
495 nullptr, this).eliminateDeadDefs(DeadDefs);
496}
497
498void RegisterCoalescer::LRE_WillEraseInstruction(MachineInstr *MI) {
499 // MI may be in WorkList. Make sure we don't visit it.
500 ErasedInstrs.insert(MI);
501}
502
503bool RegisterCoalescer::adjustCopiesBackFrom(const CoalescerPair &CP,
504 MachineInstr *CopyMI) {
505 assert(!CP.isPartial() && "This doesn't work for partial copies.")(static_cast <bool> (!CP.isPartial() && "This doesn't work for partial copies."
) ? void (0) : __assert_fail ("!CP.isPartial() && \"This doesn't work for partial copies.\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 505, __extension__ __PRETTY_FUNCTION__))
;
506 assert(!CP.isPhys() && "This doesn't work for physreg copies.")(static_cast <bool> (!CP.isPhys() && "This doesn't work for physreg copies."
) ? void (0) : __assert_fail ("!CP.isPhys() && \"This doesn't work for physreg copies.\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 506, __extension__ __PRETTY_FUNCTION__))
;
507
508 LiveInterval &IntA =
509 LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg());
510 LiveInterval &IntB =
511 LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg());
512 SlotIndex CopyIdx = LIS->getInstructionIndex(*CopyMI).getRegSlot();
513
514 // We have a non-trivially-coalescable copy with IntA being the source and
515 // IntB being the dest, thus this defines a value number in IntB. If the
516 // source value number (in IntA) is defined by a copy from B, see if we can
517 // merge these two pieces of B into a single value number, eliminating a copy.
518 // For example:
519 //
520 // A3 = B0
521 // ...
522 // B1 = A3 <- this copy
523 //
524 // In this case, B0 can be extended to where the B1 copy lives, allowing the
525 // B1 value number to be replaced with B0 (which simplifies the B
526 // liveinterval).
527
528 // BValNo is a value number in B that is defined by a copy from A. 'B1' in
529 // the example above.
530 LiveInterval::iterator BS = IntB.FindSegmentContaining(CopyIdx);
531 if (BS == IntB.end()) return false;
532 VNInfo *BValNo = BS->valno;
533
534 // Get the location that B is defined at. Two options: either this value has
535 // an unknown definition point or it is defined at CopyIdx. If unknown, we
536 // can't process it.
537 if (BValNo->def != CopyIdx) return false;
538
539 // AValNo is the value number in A that defines the copy, A3 in the example.
540 SlotIndex CopyUseIdx = CopyIdx.getRegSlot(true);
541 LiveInterval::iterator AS = IntA.FindSegmentContaining(CopyUseIdx);
542 // The live segment might not exist after fun with physreg coalescing.
543 if (AS == IntA.end()) return false;
544 VNInfo *AValNo = AS->valno;
545
546 // If AValNo is defined as a copy from IntB, we can potentially process this.
547 // Get the instruction that defines this value number.
548 MachineInstr *ACopyMI = LIS->getInstructionFromIndex(AValNo->def);
549 // Don't allow any partial copies, even if isCoalescable() allows them.
550 if (!CP.isCoalescable(ACopyMI) || !ACopyMI->isFullCopy())
551 return false;
552
553 // Get the Segment in IntB that this value number starts with.
554 LiveInterval::iterator ValS =
555 IntB.FindSegmentContaining(AValNo->def.getPrevSlot());
556 if (ValS == IntB.end())
557 return false;
558
559 // Make sure that the end of the live segment is inside the same block as
560 // CopyMI.
561 MachineInstr *ValSEndInst =
562 LIS->getInstructionFromIndex(ValS->end.getPrevSlot());
563 if (!ValSEndInst || ValSEndInst->getParent() != CopyMI->getParent())
564 return false;
565
566 // Okay, we now know that ValS ends in the same block that the CopyMI
567 // live-range starts. If there are no intervening live segments between them
568 // in IntB, we can merge them.
569 if (ValS+1 != BS) return false;
570
571 DEBUG(dbgs() << "Extending: " << printReg(IntB.reg, TRI))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Extending: " << printReg
(IntB.reg, TRI); } } while (false)
;
572
573 SlotIndex FillerStart = ValS->end, FillerEnd = BS->start;
574 // We are about to delete CopyMI, so need to remove it as the 'instruction
575 // that defines this value #'. Update the valnum with the new defining
576 // instruction #.
577 BValNo->def = FillerStart;
578
579 // Okay, we can merge them. We need to insert a new liverange:
580 // [ValS.end, BS.begin) of either value number, then we merge the
581 // two value numbers.
582 IntB.addSegment(LiveInterval::Segment(FillerStart, FillerEnd, BValNo));
583
584 // Okay, merge "B1" into the same value number as "B0".
585 if (BValNo != ValS->valno)
586 IntB.MergeValueNumberInto(BValNo, ValS->valno);
587
588 // Do the same for the subregister segments.
589 for (LiveInterval::SubRange &S : IntB.subranges()) {
590 VNInfo *SubBValNo = S.getVNInfoAt(CopyIdx);
591 S.addSegment(LiveInterval::Segment(FillerStart, FillerEnd, SubBValNo));
592 VNInfo *SubValSNo = S.getVNInfoAt(AValNo->def.getPrevSlot());
593 if (SubBValNo != SubValSNo)
594 S.MergeValueNumberInto(SubBValNo, SubValSNo);
595 }
596
597 DEBUG(dbgs() << " result = " << IntB << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << " result = " << IntB <<
'\n'; } } while (false)
;
598
599 // If the source instruction was killing the source register before the
600 // merge, unset the isKill marker given the live range has been extended.
601 int UIdx = ValSEndInst->findRegisterUseOperandIdx(IntB.reg, true);
602 if (UIdx != -1) {
603 ValSEndInst->getOperand(UIdx).setIsKill(false);
604 }
605
606 // Rewrite the copy. If the copy instruction was killing the destination
607 // register before the merge, find the last use and trim the live range. That
608 // will also add the isKill marker.
609 CopyMI->substituteRegister(IntA.reg, IntB.reg, 0, *TRI);
610 if (AS->end == CopyIdx)
611 shrinkToUses(&IntA);
612
613 ++numExtends;
614 return true;
615}
616
617bool RegisterCoalescer::hasOtherReachingDefs(LiveInterval &IntA,
618 LiveInterval &IntB,
619 VNInfo *AValNo,
620 VNInfo *BValNo) {
621 // If AValNo has PHI kills, conservatively assume that IntB defs can reach
622 // the PHI values.
623 if (LIS->hasPHIKill(IntA, AValNo))
624 return true;
625
626 for (LiveRange::Segment &ASeg : IntA.segments) {
627 if (ASeg.valno != AValNo) continue;
628 LiveInterval::iterator BI =
629 std::upper_bound(IntB.begin(), IntB.end(), ASeg.start);
630 if (BI != IntB.begin())
631 --BI;
632 for (; BI != IntB.end() && ASeg.end >= BI->start; ++BI) {
633 if (BI->valno == BValNo)
634 continue;
635 if (BI->start <= ASeg.start && BI->end > ASeg.start)
636 return true;
637 if (BI->start > ASeg.start && BI->start < ASeg.end)
638 return true;
639 }
640 }
641 return false;
642}
643
644/// Copy segements with value number @p SrcValNo from liverange @p Src to live
645/// range @Dst and use value number @p DstValNo there.
646static void addSegmentsWithValNo(LiveRange &Dst, VNInfo *DstValNo,
647 const LiveRange &Src, const VNInfo *SrcValNo) {
648 for (const LiveRange::Segment &S : Src.segments) {
649 if (S.valno != SrcValNo)
650 continue;
651 Dst.addSegment(LiveRange::Segment(S.start, S.end, DstValNo));
652 }
653}
654
655bool RegisterCoalescer::removeCopyByCommutingDef(const CoalescerPair &CP,
656 MachineInstr *CopyMI) {
657 assert(!CP.isPhys())(static_cast <bool> (!CP.isPhys()) ? void (0) : __assert_fail
("!CP.isPhys()", "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 657, __extension__ __PRETTY_FUNCTION__))
;
658
659 LiveInterval &IntA =
660 LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg());
661 LiveInterval &IntB =
662 LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg());
663
664 // We found a non-trivially-coalescable copy with IntA being the source and
665 // IntB being the dest, thus this defines a value number in IntB. If the
666 // source value number (in IntA) is defined by a commutable instruction and
667 // its other operand is coalesced to the copy dest register, see if we can
668 // transform the copy into a noop by commuting the definition. For example,
669 //
670 // A3 = op A2 killed B0
671 // ...
672 // B1 = A3 <- this copy
673 // ...
674 // = op A3 <- more uses
675 //
676 // ==>
677 //
678 // B2 = op B0 killed A2
679 // ...
680 // B1 = B2 <- now an identity copy
681 // ...
682 // = op B2 <- more uses
683
684 // BValNo is a value number in B that is defined by a copy from A. 'B1' in
685 // the example above.
686 SlotIndex CopyIdx = LIS->getInstructionIndex(*CopyMI).getRegSlot();
687 VNInfo *BValNo = IntB.getVNInfoAt(CopyIdx);
688 assert(BValNo != nullptr && BValNo->def == CopyIdx)(static_cast <bool> (BValNo != nullptr && BValNo
->def == CopyIdx) ? void (0) : __assert_fail ("BValNo != nullptr && BValNo->def == CopyIdx"
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 688, __extension__ __PRETTY_FUNCTION__))
;
689
690 // AValNo is the value number in A that defines the copy, A3 in the example.
691 VNInfo *AValNo = IntA.getVNInfoAt(CopyIdx.getRegSlot(true));
692 assert(AValNo && !AValNo->isUnused() && "COPY source not live")(static_cast <bool> (AValNo && !AValNo->isUnused
() && "COPY source not live") ? void (0) : __assert_fail
("AValNo && !AValNo->isUnused() && \"COPY source not live\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 692, __extension__ __PRETTY_FUNCTION__))
;
693 if (AValNo->isPHIDef())
694 return false;
695 MachineInstr *DefMI = LIS->getInstructionFromIndex(AValNo->def);
696 if (!DefMI)
697 return false;
698 if (!DefMI->isCommutable())
699 return false;
700 // If DefMI is a two-address instruction then commuting it will change the
701 // destination register.
702 int DefIdx = DefMI->findRegisterDefOperandIdx(IntA.reg);
703 assert(DefIdx != -1)(static_cast <bool> (DefIdx != -1) ? void (0) : __assert_fail
("DefIdx != -1", "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 703, __extension__ __PRETTY_FUNCTION__))
;
704 unsigned UseOpIdx;
705 if (!DefMI->isRegTiedToUseOperand(DefIdx, &UseOpIdx))
706 return false;
707
708 // FIXME: The code below tries to commute 'UseOpIdx' operand with some other
709 // commutable operand which is expressed by 'CommuteAnyOperandIndex'value
710 // passed to the method. That _other_ operand is chosen by
711 // the findCommutedOpIndices() method.
712 //
713 // That is obviously an area for improvement in case of instructions having
714 // more than 2 operands. For example, if some instruction has 3 commutable
715 // operands then all possible variants (i.e. op#1<->op#2, op#1<->op#3,
716 // op#2<->op#3) of commute transformation should be considered/tried here.
717 unsigned NewDstIdx = TargetInstrInfo::CommuteAnyOperandIndex;
718 if (!TII->findCommutedOpIndices(*DefMI, UseOpIdx, NewDstIdx))
719 return false;
720
721 MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx);
722 unsigned NewReg = NewDstMO.getReg();
723 if (NewReg != IntB.reg || !IntB.Query(AValNo->def).isKill())
724 return false;
725
726 // Make sure there are no other definitions of IntB that would reach the
727 // uses which the new definition can reach.
728 if (hasOtherReachingDefs(IntA, IntB, AValNo, BValNo))
729 return false;
730
731 // If some of the uses of IntA.reg is already coalesced away, return false.
732 // It's not possible to determine whether it's safe to perform the coalescing.
733 for (MachineOperand &MO : MRI->use_nodbg_operands(IntA.reg)) {
734 MachineInstr *UseMI = MO.getParent();
735 unsigned OpNo = &MO - &UseMI->getOperand(0);
736 SlotIndex UseIdx = LIS->getInstructionIndex(*UseMI);
737 LiveInterval::iterator US = IntA.FindSegmentContaining(UseIdx);
738 if (US == IntA.end() || US->valno != AValNo)
739 continue;
740 // If this use is tied to a def, we can't rewrite the register.
741 if (UseMI->isRegTiedToDefOperand(OpNo))
742 return false;
743 }
744
745 DEBUG(dbgs() << "\tremoveCopyByCommutingDef: " << AValNo->def << '\t'do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tremoveCopyByCommutingDef: "
<< AValNo->def << '\t' << *DefMI; } } while
(false)
746 << *DefMI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tremoveCopyByCommutingDef: "
<< AValNo->def << '\t' << *DefMI; } } while
(false)
;
747
748 // At this point we have decided that it is legal to do this
749 // transformation. Start by commuting the instruction.
750 MachineBasicBlock *MBB = DefMI->getParent();
751 MachineInstr *NewMI =
752 TII->commuteInstruction(*DefMI, false, UseOpIdx, NewDstIdx);
753 if (!NewMI)
754 return false;
755 if (TargetRegisterInfo::isVirtualRegister(IntA.reg) &&
756 TargetRegisterInfo::isVirtualRegister(IntB.reg) &&
757 !MRI->constrainRegClass(IntB.reg, MRI->getRegClass(IntA.reg)))
758 return false;
759 if (NewMI != DefMI) {
760 LIS->ReplaceMachineInstrInMaps(*DefMI, *NewMI);
761 MachineBasicBlock::iterator Pos = DefMI;
762 MBB->insert(Pos, NewMI);
763 MBB->erase(DefMI);
764 }
765
766 // If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g.
767 // A = or A, B
768 // ...
769 // B = A
770 // ...
771 // C = killed A
772 // ...
773 // = B
774
775 // Update uses of IntA of the specific Val# with IntB.
776 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(IntA.reg),
777 UE = MRI->use_end();
778 UI != UE; /* ++UI is below because of possible MI removal */) {
779 MachineOperand &UseMO = *UI;
780 ++UI;
781 if (UseMO.isUndef())
782 continue;
783 MachineInstr *UseMI = UseMO.getParent();
784 if (UseMI->isDebugValue()) {
785 // FIXME These don't have an instruction index. Not clear we have enough
786 // info to decide whether to do this replacement or not. For now do it.
787 UseMO.setReg(NewReg);
788 continue;
789 }
790 SlotIndex UseIdx = LIS->getInstructionIndex(*UseMI).getRegSlot(true);
791 LiveInterval::iterator US = IntA.FindSegmentContaining(UseIdx);
792 assert(US != IntA.end() && "Use must be live")(static_cast <bool> (US != IntA.end() && "Use must be live"
) ? void (0) : __assert_fail ("US != IntA.end() && \"Use must be live\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 792, __extension__ __PRETTY_FUNCTION__))
;
793 if (US->valno != AValNo)
794 continue;
795 // Kill flags are no longer accurate. They are recomputed after RA.
796 UseMO.setIsKill(false);
797 if (TargetRegisterInfo::isPhysicalRegister(NewReg))
798 UseMO.substPhysReg(NewReg, *TRI);
799 else
800 UseMO.setReg(NewReg);
801 if (UseMI == CopyMI)
802 continue;
803 if (!UseMI->isCopy())
804 continue;
805 if (UseMI->getOperand(0).getReg() != IntB.reg ||
806 UseMI->getOperand(0).getSubReg())
807 continue;
808
809 // This copy will become a noop. If it's defining a new val#, merge it into
810 // BValNo.
811 SlotIndex DefIdx = UseIdx.getRegSlot();
812 VNInfo *DVNI = IntB.getVNInfoAt(DefIdx);
813 if (!DVNI)
814 continue;
815 DEBUG(dbgs() << "\t\tnoop: " << DefIdx << '\t' << *UseMI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tnoop: " << DefIdx <<
'\t' << *UseMI; } } while (false)
;
816 assert(DVNI->def == DefIdx)(static_cast <bool> (DVNI->def == DefIdx) ? void (0)
: __assert_fail ("DVNI->def == DefIdx", "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 816, __extension__ __PRETTY_FUNCTION__))
;
817 BValNo = IntB.MergeValueNumberInto(DVNI, BValNo);
818 for (LiveInterval::SubRange &S : IntB.subranges()) {
819 VNInfo *SubDVNI = S.getVNInfoAt(DefIdx);
820 if (!SubDVNI)
821 continue;
822 VNInfo *SubBValNo = S.getVNInfoAt(CopyIdx);
823 assert(SubBValNo->def == CopyIdx)(static_cast <bool> (SubBValNo->def == CopyIdx) ? void
(0) : __assert_fail ("SubBValNo->def == CopyIdx", "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 823, __extension__ __PRETTY_FUNCTION__))
;
824 S.MergeValueNumberInto(SubDVNI, SubBValNo);
825 }
826
827 deleteInstr(UseMI);
828 }
829
830 // Extend BValNo by merging in IntA live segments of AValNo. Val# definition
831 // is updated.
832 BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
833 if (IntB.hasSubRanges()) {
834 if (!IntA.hasSubRanges()) {
835 LaneBitmask Mask = MRI->getMaxLaneMaskForVReg(IntA.reg);
836 IntA.createSubRangeFrom(Allocator, Mask, IntA);
837 }
838 SlotIndex AIdx = CopyIdx.getRegSlot(true);
839 for (LiveInterval::SubRange &SA : IntA.subranges()) {
840 VNInfo *ASubValNo = SA.getVNInfoAt(AIdx);
841 assert(ASubValNo != nullptr)(static_cast <bool> (ASubValNo != nullptr) ? void (0) :
__assert_fail ("ASubValNo != nullptr", "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 841, __extension__ __PRETTY_FUNCTION__))
;
842
843 IntB.refineSubRanges(Allocator, SA.LaneMask,
844 [&Allocator,&SA,CopyIdx,ASubValNo](LiveInterval::SubRange &SR) {
845 VNInfo *BSubValNo = SR.empty()
846 ? SR.getNextValue(CopyIdx, Allocator)
847 : SR.getVNInfoAt(CopyIdx);
848 assert(BSubValNo != nullptr)(static_cast <bool> (BSubValNo != nullptr) ? void (0) :
__assert_fail ("BSubValNo != nullptr", "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 848, __extension__ __PRETTY_FUNCTION__))
;
849 addSegmentsWithValNo(SR, BSubValNo, SA, ASubValNo);
850 });
851 }
852 }
853
854 BValNo->def = AValNo->def;
855 addSegmentsWithValNo(IntB, BValNo, IntA, AValNo);
856 DEBUG(dbgs() << "\t\textended: " << IntB << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\textended: " << IntB
<< '\n'; } } while (false)
;
857
858 LIS->removeVRegDefAt(IntA, AValNo->def);
859
860 DEBUG(dbgs() << "\t\ttrimmed: " << IntA << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\ttrimmed: " << IntA
<< '\n'; } } while (false)
;
861 ++numCommutes;
862 return true;
863}
864
865/// For copy B = A in BB2, if A is defined by A = B in BB0 which is a
866/// predecessor of BB2, and if B is not redefined on the way from A = B
867/// in BB2 to B = A in BB2, B = A in BB2 is partially redundant if the
868/// execution goes through the path from BB0 to BB2. We may move B = A
869/// to the predecessor without such reversed copy.
870/// So we will transform the program from:
871/// BB0:
872/// A = B; BB1:
873/// ... ...
874/// / \ /
875/// BB2:
876/// ...
877/// B = A;
878///
879/// to:
880///
881/// BB0: BB1:
882/// A = B; ...
883/// ... B = A;
884/// / \ /
885/// BB2:
886/// ...
887///
888/// A special case is when BB0 and BB2 are the same BB which is the only
889/// BB in a loop:
890/// BB1:
891/// ...
892/// BB0/BB2: ----
893/// B = A; |
894/// ... |
895/// A = B; |
896/// |-------
897/// |
898/// We may hoist B = A from BB0/BB2 to BB1.
899///
900/// The major preconditions for correctness to remove such partial
901/// redundancy include:
902/// 1. A in B = A in BB2 is defined by a PHI in BB2, and one operand of
903/// the PHI is defined by the reversed copy A = B in BB0.
904/// 2. No B is referenced from the start of BB2 to B = A.
905/// 3. No B is defined from A = B to the end of BB0.
906/// 4. BB1 has only one successor.
907///
908/// 2 and 4 implicitly ensure B is not live at the end of BB1.
909/// 4 guarantees BB2 is hotter than BB1, so we can only move a copy to a
910/// colder place, which not only prevent endless loop, but also make sure
911/// the movement of copy is beneficial.
912bool RegisterCoalescer::removePartialRedundancy(const CoalescerPair &CP,
913 MachineInstr &CopyMI) {
914 assert(!CP.isPhys())(static_cast <bool> (!CP.isPhys()) ? void (0) : __assert_fail
("!CP.isPhys()", "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 914, __extension__ __PRETTY_FUNCTION__))
;
915 if (!CopyMI.isFullCopy())
916 return false;
917
918 MachineBasicBlock &MBB = *CopyMI.getParent();
919 if (MBB.isEHPad())
920 return false;
921
922 if (MBB.pred_size() != 2)
923 return false;
924
925 LiveInterval &IntA =
926 LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg());
927 LiveInterval &IntB =
928 LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg());
929
930 // A is defined by PHI at the entry of MBB.
931 SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(true);
932 VNInfo *AValNo = IntA.getVNInfoAt(CopyIdx);
933 assert(AValNo && !AValNo->isUnused() && "COPY source not live")(static_cast <bool> (AValNo && !AValNo->isUnused
() && "COPY source not live") ? void (0) : __assert_fail
("AValNo && !AValNo->isUnused() && \"COPY source not live\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 933, __extension__ __PRETTY_FUNCTION__))
;
934 if (!AValNo->isPHIDef())
935 return false;
936
937 // No B is referenced before CopyMI in MBB.
938 if (IntB.overlaps(LIS->getMBBStartIdx(&MBB), CopyIdx))
939 return false;
940
941 // MBB has two predecessors: one contains A = B so no copy will be inserted
942 // for it. The other one will have a copy moved from MBB.
943 bool FoundReverseCopy = false;
944 MachineBasicBlock *CopyLeftBB = nullptr;
945 for (MachineBasicBlock *Pred : MBB.predecessors()) {
946 VNInfo *PVal = IntA.getVNInfoBefore(LIS->getMBBEndIdx(Pred));
947 MachineInstr *DefMI = LIS->getInstructionFromIndex(PVal->def);
948 if (!DefMI || !DefMI->isFullCopy()) {
949 CopyLeftBB = Pred;
950 continue;
951 }
952 // Check DefMI is a reverse copy and it is in BB Pred.
953 if (DefMI->getOperand(0).getReg() != IntA.reg ||
954 DefMI->getOperand(1).getReg() != IntB.reg ||
955 DefMI->getParent() != Pred) {
956 CopyLeftBB = Pred;
957 continue;
958 }
959 // If there is any other def of B after DefMI and before the end of Pred,
960 // we need to keep the copy of B = A at the end of Pred if we remove
961 // B = A from MBB.
962 bool ValB_Changed = false;
963 for (auto VNI : IntB.valnos) {
964 if (VNI->isUnused())
965 continue;
966 if (PVal->def < VNI->def && VNI->def < LIS->getMBBEndIdx(Pred)) {
967 ValB_Changed = true;
968 break;
969 }
970 }
971 if (ValB_Changed) {
972 CopyLeftBB = Pred;
973 continue;
974 }
975 FoundReverseCopy = true;
976 }
977
978 // If no reverse copy is found in predecessors, nothing to do.
979 if (!FoundReverseCopy)
980 return false;
981
982 // If CopyLeftBB is nullptr, it means every predecessor of MBB contains
983 // reverse copy, CopyMI can be removed trivially if only IntA/IntB is updated.
984 // If CopyLeftBB is not nullptr, move CopyMI from MBB to CopyLeftBB and
985 // update IntA/IntB.
986 //
987 // If CopyLeftBB is not nullptr, ensure CopyLeftBB has a single succ so
988 // MBB is hotter than CopyLeftBB.
989 if (CopyLeftBB && CopyLeftBB->succ_size() > 1)
990 return false;
991
992 // Now ok to move copy.
993 if (CopyLeftBB) {
994 DEBUG(dbgs() << "\tremovePartialRedundancy: Move the copy to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tremovePartialRedundancy: Move the copy to "
<< printMBBReference(*CopyLeftBB) << '\t' <<
CopyMI; } } while (false)
995 << printMBBReference(*CopyLeftBB) << '\t' << CopyMI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tremovePartialRedundancy: Move the copy to "
<< printMBBReference(*CopyLeftBB) << '\t' <<
CopyMI; } } while (false)
;
996
997 // Insert new copy to CopyLeftBB.
998 auto InsPos = CopyLeftBB->getFirstTerminator();
999 MachineInstr *NewCopyMI = BuildMI(*CopyLeftBB, InsPos, CopyMI.getDebugLoc(),
1000 TII->get(TargetOpcode::COPY), IntB.reg)
1001 .addReg(IntA.reg);
1002 SlotIndex NewCopyIdx =
1003 LIS->InsertMachineInstrInMaps(*NewCopyMI).getRegSlot();
1004 IntB.createDeadDef(NewCopyIdx, LIS->getVNInfoAllocator());
1005 for (LiveInterval::SubRange &SR : IntB.subranges())
1006 SR.createDeadDef(NewCopyIdx, LIS->getVNInfoAllocator());
1007
1008 // If the newly created Instruction has an address of an instruction that was
1009 // deleted before (object recycled by the allocator) it needs to be removed from
1010 // the deleted list.
1011 ErasedInstrs.erase(NewCopyMI);
1012 } else {
1013 DEBUG(dbgs() << "\tremovePartialRedundancy: Remove the copy from "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tremovePartialRedundancy: Remove the copy from "
<< printMBBReference(MBB) << '\t' << CopyMI
; } } while (false)
1014 << printMBBReference(MBB) << '\t' << CopyMI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tremovePartialRedundancy: Remove the copy from "
<< printMBBReference(MBB) << '\t' << CopyMI
; } } while (false)
;
1015 }
1016
1017 // Remove CopyMI.
1018 // Note: This is fine to remove the copy before updating the live-ranges.
1019 // While updating the live-ranges, we only look at slot indices and
1020 // never go back to the instruction.
1021 // Mark instructions as deleted.
1022 deleteInstr(&CopyMI);
1023
1024 // Update the liveness.
1025 SmallVector<SlotIndex, 8> EndPoints;
1026 VNInfo *BValNo = IntB.Query(CopyIdx).valueOutOrDead();
1027 LIS->pruneValue(*static_cast<LiveRange *>(&IntB), CopyIdx.getRegSlot(),
1028 &EndPoints);
1029 BValNo->markUnused();
1030 // Extend IntB to the EndPoints of its original live interval.
1031 LIS->extendToIndices(IntB, EndPoints);
1032
1033 // Now, do the same for its subranges.
1034 for (LiveInterval::SubRange &SR : IntB.subranges()) {
1035 EndPoints.clear();
1036 VNInfo *BValNo = SR.Query(CopyIdx).valueOutOrDead();
1037 assert(BValNo && "All sublanes should be live")(static_cast <bool> (BValNo && "All sublanes should be live"
) ? void (0) : __assert_fail ("BValNo && \"All sublanes should be live\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 1037, __extension__ __PRETTY_FUNCTION__))
;
1038 LIS->pruneValue(SR, CopyIdx.getRegSlot(), &EndPoints);
1039 BValNo->markUnused();
1040 LIS->extendToIndices(SR, EndPoints);
1041 }
1042
1043 // Finally, update the live-range of IntA.
1044 shrinkToUses(&IntA);
1045 return true;
1046}
1047
1048/// Returns true if @p MI defines the full vreg @p Reg, as opposed to just
1049/// defining a subregister.
1050static bool definesFullReg(const MachineInstr &MI, unsigned Reg) {
1051 assert(!TargetRegisterInfo::isPhysicalRegister(Reg) &&(static_cast <bool> (!TargetRegisterInfo::isPhysicalRegister
(Reg) && "This code cannot handle physreg aliasing") ?
void (0) : __assert_fail ("!TargetRegisterInfo::isPhysicalRegister(Reg) && \"This code cannot handle physreg aliasing\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 1052, __extension__ __PRETTY_FUNCTION__))
1052 "This code cannot handle physreg aliasing")(static_cast <bool> (!TargetRegisterInfo::isPhysicalRegister
(Reg) && "This code cannot handle physreg aliasing") ?
void (0) : __assert_fail ("!TargetRegisterInfo::isPhysicalRegister(Reg) && \"This code cannot handle physreg aliasing\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 1052, __extension__ __PRETTY_FUNCTION__))
;
1053 for (const MachineOperand &Op : MI.operands()) {
1054 if (!Op.isReg() || !Op.isDef() || Op.getReg() != Reg)
1055 continue;
1056 // Return true if we define the full register or don't care about the value
1057 // inside other subregisters.
1058 if (Op.getSubReg() == 0 || Op.isUndef())
1059 return true;
1060 }
1061 return false;
1062}
1063
1064bool RegisterCoalescer::reMaterializeTrivialDef(const CoalescerPair &CP,
1065 MachineInstr *CopyMI,
1066 bool &IsDefCopy) {
1067 IsDefCopy = false;
1068 unsigned SrcReg = CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg();
1069 unsigned SrcIdx = CP.isFlipped() ? CP.getDstIdx() : CP.getSrcIdx();
1070 unsigned DstReg = CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg();
1071 unsigned DstIdx = CP.isFlipped() ? CP.getSrcIdx() : CP.getDstIdx();
1072 if (TargetRegisterInfo::isPhysicalRegister(SrcReg))
1073 return false;
1074
1075 LiveInterval &SrcInt = LIS->getInterval(SrcReg);
1076 SlotIndex CopyIdx = LIS->getInstructionIndex(*CopyMI);
1077 VNInfo *ValNo = SrcInt.Query(CopyIdx).valueIn();
1078 assert(ValNo && "CopyMI input register not live")(static_cast <bool> (ValNo && "CopyMI input register not live"
) ? void (0) : __assert_fail ("ValNo && \"CopyMI input register not live\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 1078, __extension__ __PRETTY_FUNCTION__))
;
1079 if (ValNo->isPHIDef() || ValNo->isUnused())
1080 return false;
1081 MachineInstr *DefMI = LIS->getInstructionFromIndex(ValNo->def);
1082 if (!DefMI)
1083 return false;
1084 if (DefMI->isCopyLike()) {
1085 IsDefCopy = true;
1086 return false;
1087 }
1088 if (!TII->isAsCheapAsAMove(*DefMI))
1089 return false;
1090 if (!TII->isTriviallyReMaterializable(*DefMI, AA))
1091 return false;
1092 if (!definesFullReg(*DefMI, SrcReg))
1093 return false;
1094 bool SawStore = false;
1095 if (!DefMI->isSafeToMove(AA, SawStore))
1096 return false;
1097 const MCInstrDesc &MCID = DefMI->getDesc();
1098 if (MCID.getNumDefs() != 1)
1099 return false;
1100 // Only support subregister destinations when the def is read-undef.
1101 MachineOperand &DstOperand = CopyMI->getOperand(0);
1102 unsigned CopyDstReg = DstOperand.getReg();
1103 if (DstOperand.getSubReg() && !DstOperand.isUndef())
1104 return false;
1105
1106 // If both SrcIdx and DstIdx are set, correct rematerialization would widen
1107 // the register substantially (beyond both source and dest size). This is bad
1108 // for performance since it can cascade through a function, introducing many
1109 // extra spills and fills (e.g. ARM can easily end up copying QQQQPR registers
1110 // around after a few subreg copies).
1111 if (SrcIdx && DstIdx)
1112 return false;
1113
1114 const TargetRegisterClass *DefRC = TII->getRegClass(MCID, 0, TRI, *MF);
1115 if (!DefMI->isImplicitDef()) {
1116 if (TargetRegisterInfo::isPhysicalRegister(DstReg)) {
1117 unsigned NewDstReg = DstReg;
1118
1119 unsigned NewDstIdx = TRI->composeSubRegIndices(CP.getSrcIdx(),
1120 DefMI->getOperand(0).getSubReg());
1121 if (NewDstIdx)
1122 NewDstReg = TRI->getSubReg(DstReg, NewDstIdx);
1123
1124 // Finally, make sure that the physical subregister that will be
1125 // constructed later is permitted for the instruction.
1126 if (!DefRC->contains(NewDstReg))
1127 return false;
1128 } else {
1129 // Theoretically, some stack frame reference could exist. Just make sure
1130 // it hasn't actually happened.
1131 assert(TargetRegisterInfo::isVirtualRegister(DstReg) &&(static_cast <bool> (TargetRegisterInfo::isVirtualRegister
(DstReg) && "Only expect to deal with virtual or physical registers"
) ? void (0) : __assert_fail ("TargetRegisterInfo::isVirtualRegister(DstReg) && \"Only expect to deal with virtual or physical registers\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 1132, __extension__ __PRETTY_FUNCTION__))
1132 "Only expect to deal with virtual or physical registers")(static_cast <bool> (TargetRegisterInfo::isVirtualRegister
(DstReg) && "Only expect to deal with virtual or physical registers"
) ? void (0) : __assert_fail ("TargetRegisterInfo::isVirtualRegister(DstReg) && \"Only expect to deal with virtual or physical registers\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 1132, __extension__ __PRETTY_FUNCTION__))
;
1133 }
1134 }
1135
1136 DebugLoc DL = CopyMI->getDebugLoc();
1137 MachineBasicBlock *MBB = CopyMI->getParent();
1138 MachineBasicBlock::iterator MII =
1139 std::next(MachineBasicBlock::iterator(CopyMI));
1140 TII->reMaterialize(*MBB, MII, DstReg, SrcIdx, *DefMI, *TRI);
1141 MachineInstr &NewMI = *std::prev(MII);
1142 NewMI.setDebugLoc(DL);
1143
1144 // In a situation like the following:
1145 // %0:subreg = instr ; DefMI, subreg = DstIdx
1146 // %1 = copy %0:subreg ; CopyMI, SrcIdx = 0
1147 // instead of widening %1 to the register class of %0 simply do:
1148 // %1 = instr
1149 const TargetRegisterClass *NewRC = CP.getNewRC();
1150 if (DstIdx != 0) {
1151 MachineOperand &DefMO = NewMI.getOperand(0);
1152 if (DefMO.getSubReg() == DstIdx) {
1153 assert(SrcIdx == 0 && CP.isFlipped()(static_cast <bool> (SrcIdx == 0 && CP.isFlipped
() && "Shouldn't have SrcIdx+DstIdx at this point") ?
void (0) : __assert_fail ("SrcIdx == 0 && CP.isFlipped() && \"Shouldn't have SrcIdx+DstIdx at this point\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 1154, __extension__ __PRETTY_FUNCTION__))
1154 && "Shouldn't have SrcIdx+DstIdx at this point")(static_cast <bool> (SrcIdx == 0 && CP.isFlipped
() && "Shouldn't have SrcIdx+DstIdx at this point") ?
void (0) : __assert_fail ("SrcIdx == 0 && CP.isFlipped() && \"Shouldn't have SrcIdx+DstIdx at this point\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 1154, __extension__ __PRETTY_FUNCTION__))
;
1155 const TargetRegisterClass *DstRC = MRI->getRegClass(DstReg);
1156 const TargetRegisterClass *CommonRC =
1157 TRI->getCommonSubClass(DefRC, DstRC);
1158 if (CommonRC != nullptr) {
1159 NewRC = CommonRC;
1160 DstIdx = 0;
1161 DefMO.setSubReg(0);
1162 DefMO.setIsUndef(false); // Only subregs can have def+undef.
1163 }
1164 }
1165 }
1166
1167 // CopyMI may have implicit operands, save them so that we can transfer them
1168 // over to the newly materialized instruction after CopyMI is removed.
1169 SmallVector<MachineOperand, 4> ImplicitOps;
1170 ImplicitOps.reserve(CopyMI->getNumOperands() -
1171 CopyMI->getDesc().getNumOperands());
1172 for (unsigned I = CopyMI->getDesc().getNumOperands(),
1173 E = CopyMI->getNumOperands();
1174 I != E; ++I) {
1175 MachineOperand &MO = CopyMI->getOperand(I);
1176 if (MO.isReg()) {
1177 assert(MO.isImplicit() && "No explicit operands after implict operands.")(static_cast <bool> (MO.isImplicit() && "No explicit operands after implict operands."
) ? void (0) : __assert_fail ("MO.isImplicit() && \"No explicit operands after implict operands.\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 1177, __extension__ __PRETTY_FUNCTION__))
;
1178 // Discard VReg implicit defs.
1179 if (TargetRegisterInfo::isPhysicalRegister(MO.getReg()))
1180 ImplicitOps.push_back(MO);
1181 }
1182 }
1183
1184 LIS->ReplaceMachineInstrInMaps(*CopyMI, NewMI);
1185 CopyMI->eraseFromParent();
1186 ErasedInstrs.insert(CopyMI);
1187
1188 // NewMI may have dead implicit defs (E.g. EFLAGS for MOV<bits>r0 on X86).
1189 // We need to remember these so we can add intervals once we insert
1190 // NewMI into SlotIndexes.
1191 SmallVector<unsigned, 4> NewMIImplDefs;
1192 for (unsigned i = NewMI.getDesc().getNumOperands(),
1193 e = NewMI.getNumOperands();
1194 i != e; ++i) {
1195 MachineOperand &MO = NewMI.getOperand(i);
1196 if (MO.isReg() && MO.isDef()) {
1197 assert(MO.isImplicit() && MO.isDead() &&(static_cast <bool> (MO.isImplicit() && MO.isDead
() && TargetRegisterInfo::isPhysicalRegister(MO.getReg
())) ? void (0) : __assert_fail ("MO.isImplicit() && MO.isDead() && TargetRegisterInfo::isPhysicalRegister(MO.getReg())"
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 1198, __extension__ __PRETTY_FUNCTION__))
1198 TargetRegisterInfo::isPhysicalRegister(MO.getReg()))(static_cast <bool> (MO.isImplicit() && MO.isDead
() && TargetRegisterInfo::isPhysicalRegister(MO.getReg
())) ? void (0) : __assert_fail ("MO.isImplicit() && MO.isDead() && TargetRegisterInfo::isPhysicalRegister(MO.getReg())"
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 1198, __extension__ __PRETTY_FUNCTION__))
;
1199 NewMIImplDefs.push_back(MO.getReg());
1200 }
1201 }
1202
1203 if (TargetRegisterInfo::isVirtualRegister(DstReg)) {
1204 unsigned NewIdx = NewMI.getOperand(0).getSubReg();
1205
1206 if (DefRC != nullptr) {
1207 if (NewIdx)
1208 NewRC = TRI->getMatchingSuperRegClass(NewRC, DefRC, NewIdx);
1209 else
1210 NewRC = TRI->getCommonSubClass(NewRC, DefRC);
1211 assert(NewRC && "subreg chosen for remat incompatible with instruction")(static_cast <bool> (NewRC && "subreg chosen for remat incompatible with instruction"
) ? void (0) : __assert_fail ("NewRC && \"subreg chosen for remat incompatible with instruction\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 1211, __extension__ __PRETTY_FUNCTION__))
;
1212 }
1213 // Remap subranges to new lanemask and change register class.
1214 LiveInterval &DstInt = LIS->getInterval(DstReg);
1215 for (LiveInterval::SubRange &SR : DstInt.subranges()) {
1216 SR.LaneMask = TRI->composeSubRegIndexLaneMask(DstIdx, SR.LaneMask);
1217 }
1218 MRI->setRegClass(DstReg, NewRC);
1219
1220 // Update machine operands and add flags.
1221 updateRegDefsUses(DstReg, DstReg, DstIdx);
1222 NewMI.getOperand(0).setSubReg(NewIdx);
1223 // Add dead subregister definitions if we are defining the whole register
1224 // but only part of it is live.
1225 // This could happen if the rematerialization instruction is rematerializing
1226 // more than actually is used in the register.
1227 // An example would be:
1228 // %1 = LOAD CONSTANTS 5, 8 ; Loading both 5 and 8 in different subregs
1229 // ; Copying only part of the register here, but the rest is undef.
1230 // %2:sub_16bit<def, read-undef> = COPY %1:sub_16bit
1231 // ==>
1232 // ; Materialize all the constants but only using one
1233 // %2 = LOAD_CONSTANTS 5, 8
1234 //
1235 // at this point for the part that wasn't defined before we could have
1236 // subranges missing the definition.
1237 if (NewIdx == 0 && DstInt.hasSubRanges()) {
1238 SlotIndex CurrIdx = LIS->getInstructionIndex(NewMI);
1239 SlotIndex DefIndex =
1240 CurrIdx.getRegSlot(NewMI.getOperand(0).isEarlyClobber());
1241 LaneBitmask MaxMask = MRI->getMaxLaneMaskForVReg(DstReg);
1242 VNInfo::Allocator& Alloc = LIS->getVNInfoAllocator();
1243 for (LiveInterval::SubRange &SR : DstInt.subranges()) {
1244 if (!SR.liveAt(DefIndex))
1245 SR.createDeadDef(DefIndex, Alloc);
1246 MaxMask &= ~SR.LaneMask;
1247 }
1248 if (MaxMask.any()) {
1249 LiveInterval::SubRange *SR = DstInt.createSubRange(Alloc, MaxMask);
1250 SR->createDeadDef(DefIndex, Alloc);
1251 }
1252 }
1253
1254 // Make sure that the subrange for resultant undef is removed
1255 // For example:
1256 // %1:sub1<def,read-undef> = LOAD CONSTANT 1
1257 // %2 = COPY %1
1258 // ==>
1259 // %2:sub1<def, read-undef> = LOAD CONSTANT 1
1260 // ; Correct but need to remove the subrange for %2:sub0
1261 // ; as it is now undef
1262 if (NewIdx != 0 && DstInt.hasSubRanges()) {
1263 // The affected subregister segments can be removed.
1264 SlotIndex CurrIdx = LIS->getInstructionIndex(NewMI);
1265 LaneBitmask DstMask = TRI->getSubRegIndexLaneMask(NewIdx);
1266 bool UpdatedSubRanges = false;
1267 for (LiveInterval::SubRange &SR : DstInt.subranges()) {
1268 if ((SR.LaneMask & DstMask).none()) {
1269 DEBUG(dbgs() << "Removing undefined SubRange "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Removing undefined SubRange "
<< PrintLaneMask(SR.LaneMask) << " : " << SR
<< "\n"; } } while (false)
1270 << PrintLaneMask(SR.LaneMask) << " : " << SR << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Removing undefined SubRange "
<< PrintLaneMask(SR.LaneMask) << " : " << SR
<< "\n"; } } while (false)
;
1271 // VNI is in ValNo - remove any segments in this SubRange that have this ValNo
1272 if (VNInfo *RmValNo = SR.getVNInfoAt(CurrIdx.getRegSlot())) {
1273 SR.removeValNo(RmValNo);
1274 UpdatedSubRanges = true;
1275 }
1276 }
1277 }
1278 if (UpdatedSubRanges)
1279 DstInt.removeEmptySubRanges();
1280 }
1281 } else if (NewMI.getOperand(0).getReg() != CopyDstReg) {
1282 // The New instruction may be defining a sub-register of what's actually
1283 // been asked for. If so it must implicitly define the whole thing.
1284 assert(TargetRegisterInfo::isPhysicalRegister(DstReg) &&(static_cast <bool> (TargetRegisterInfo::isPhysicalRegister
(DstReg) && "Only expect virtual or physical registers in remat"
) ? void (0) : __assert_fail ("TargetRegisterInfo::isPhysicalRegister(DstReg) && \"Only expect virtual or physical registers in remat\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 1285, __extension__ __PRETTY_FUNCTION__))
1285 "Only expect virtual or physical registers in remat")(static_cast <bool> (TargetRegisterInfo::isPhysicalRegister
(DstReg) && "Only expect virtual or physical registers in remat"
) ? void (0) : __assert_fail ("TargetRegisterInfo::isPhysicalRegister(DstReg) && \"Only expect virtual or physical registers in remat\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 1285, __extension__ __PRETTY_FUNCTION__))
;
1286 NewMI.getOperand(0).setIsDead(true);
1287 NewMI.addOperand(MachineOperand::CreateReg(
1288 CopyDstReg, true /*IsDef*/, true /*IsImp*/, false /*IsKill*/));
1289 // Record small dead def live-ranges for all the subregisters
1290 // of the destination register.
1291 // Otherwise, variables that live through may miss some
1292 // interferences, thus creating invalid allocation.
1293 // E.g., i386 code:
1294 // %1 = somedef ; %1 GR8
1295 // %2 = remat ; %2 GR32
1296 // CL = COPY %2.sub_8bit
1297 // = somedef %1 ; %1 GR8
1298 // =>
1299 // %1 = somedef ; %1 GR8
1300 // dead ECX = remat ; implicit-def CL
1301 // = somedef %1 ; %1 GR8
1302 // %1 will see the inteferences with CL but not with CH since
1303 // no live-ranges would have been created for ECX.
1304 // Fix that!
1305 SlotIndex NewMIIdx = LIS->getInstructionIndex(NewMI);
1306 for (MCRegUnitIterator Units(NewMI.getOperand(0).getReg(), TRI);
1307 Units.isValid(); ++Units)
1308 if (LiveRange *LR = LIS->getCachedRegUnit(*Units))
1309 LR->createDeadDef(NewMIIdx.getRegSlot(), LIS->getVNInfoAllocator());
1310 }
1311
1312 if (NewMI.getOperand(0).getSubReg())
1313 NewMI.getOperand(0).setIsUndef();
1314
1315 // Transfer over implicit operands to the rematerialized instruction.
1316 for (MachineOperand &MO : ImplicitOps)
1317 NewMI.addOperand(MO);
1318
1319 SlotIndex NewMIIdx = LIS->getInstructionIndex(NewMI);
1320 for (unsigned i = 0, e = NewMIImplDefs.size(); i != e; ++i) {
1321 unsigned Reg = NewMIImplDefs[i];
1322 for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units)
1323 if (LiveRange *LR = LIS->getCachedRegUnit(*Units))
1324 LR->createDeadDef(NewMIIdx.getRegSlot(), LIS->getVNInfoAllocator());
1325 }
1326
1327 DEBUG(dbgs() << "Remat: " << NewMI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Remat: " << NewMI; } }
while (false)
;
1328 ++NumReMats;
1329
1330 // The source interval can become smaller because we removed a use.
1331 shrinkToUses(&SrcInt, &DeadDefs);
1332 if (!DeadDefs.empty()) {
1333 // If the virtual SrcReg is completely eliminated, update all DBG_VALUEs
1334 // to describe DstReg instead.
1335 for (MachineOperand &UseMO : MRI->use_operands(SrcReg)) {
1336 MachineInstr *UseMI = UseMO.getParent();
1337 if (UseMI->isDebugValue()) {
1338 UseMO.setReg(DstReg);
1339 // Move the debug value directly after the def of the rematerialized
1340 // value in DstReg.
1341 MBB->splice(std::next(NewMI.getIterator()), UseMI->getParent(), UseMI);
1342 DEBUG(dbgs() << "\t\tupdated: " << *UseMI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tupdated: " << *UseMI
; } } while (false)
;
1343 }
1344 }
1345 eliminateDeadDefs();
1346 }
1347
1348 return true;
1349}
1350
1351bool RegisterCoalescer::eliminateUndefCopy(MachineInstr *CopyMI) {
1352 // ProcessImpicitDefs may leave some copies of <undef> values, it only removes
1353 // local variables. When we have a copy like:
1354 //
1355 // %1 = COPY undef %2
1356 //
1357 // We delete the copy and remove the corresponding value number from %1.
1358 // Any uses of that value number are marked as <undef>.
1359
1360 // Note that we do not query CoalescerPair here but redo isMoveInstr as the
1361 // CoalescerPair may have a new register class with adjusted subreg indices
1362 // at this point.
1363 unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
1364 isMoveInstr(*TRI, CopyMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx);
1365
1366 SlotIndex Idx = LIS->getInstructionIndex(*CopyMI);
1367 const LiveInterval &SrcLI = LIS->getInterval(SrcReg);
1368 // CopyMI is undef iff SrcReg is not live before the instruction.
1369 if (SrcSubIdx != 0 && SrcLI.hasSubRanges()) {
1370 LaneBitmask SrcMask = TRI->getSubRegIndexLaneMask(SrcSubIdx);
1371 for (const LiveInterval::SubRange &SR : SrcLI.subranges()) {
1372 if ((SR.LaneMask & SrcMask).none())
1373 continue;
1374 if (SR.liveAt(Idx))
1375 return false;
1376 }
1377 } else if (SrcLI.liveAt(Idx))
1378 return false;
1379
1380 DEBUG(dbgs() << "\tEliminating copy of <undef> value\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tEliminating copy of <undef> value\n"
; } } while (false)
;
1381
1382 // Remove any DstReg segments starting at the instruction.
1383 LiveInterval &DstLI = LIS->getInterval(DstReg);
1384 SlotIndex RegIndex = Idx.getRegSlot();
1385 // Remove value or merge with previous one in case of a subregister def.
1386 if (VNInfo *PrevVNI = DstLI.getVNInfoAt(Idx)) {
1387 VNInfo *VNI = DstLI.getVNInfoAt(RegIndex);
1388 DstLI.MergeValueNumberInto(VNI, PrevVNI);
1389
1390 // The affected subregister segments can be removed.
1391 LaneBitmask DstMask = TRI->getSubRegIndexLaneMask(DstSubIdx);
1392 for (LiveInterval::SubRange &SR : DstLI.subranges()) {
1393 if ((SR.LaneMask & DstMask).none())
1394 continue;
1395
1396 VNInfo *SVNI = SR.getVNInfoAt(RegIndex);
1397 assert(SVNI != nullptr && SlotIndex::isSameInstr(SVNI->def, RegIndex))(static_cast <bool> (SVNI != nullptr && SlotIndex
::isSameInstr(SVNI->def, RegIndex)) ? void (0) : __assert_fail
("SVNI != nullptr && SlotIndex::isSameInstr(SVNI->def, RegIndex)"
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 1397, __extension__ __PRETTY_FUNCTION__))
;
1398 SR.removeValNo(SVNI);
1399 }
1400 DstLI.removeEmptySubRanges();
1401 } else
1402 LIS->removeVRegDefAt(DstLI, RegIndex);
1403
1404 // Mark uses as undef.
1405 for (MachineOperand &MO : MRI->reg_nodbg_operands(DstReg)) {
1406 if (MO.isDef() /*|| MO.isUndef()*/)
1407 continue;
1408 const MachineInstr &MI = *MO.getParent();
1409 SlotIndex UseIdx = LIS->getInstructionIndex(MI);
1410 LaneBitmask UseMask = TRI->getSubRegIndexLaneMask(MO.getSubReg());
1411 bool isLive;
1412 if (!UseMask.all() && DstLI.hasSubRanges()) {
1413 isLive = false;
1414 for (const LiveInterval::SubRange &SR : DstLI.subranges()) {
1415 if ((SR.LaneMask & UseMask).none())
1416 continue;
1417 if (SR.liveAt(UseIdx)) {
1418 isLive = true;
1419 break;
1420 }
1421 }
1422 } else
1423 isLive = DstLI.liveAt(UseIdx);
1424 if (isLive)
1425 continue;
1426 MO.setIsUndef(true);
1427 DEBUG(dbgs() << "\tnew undef: " << UseIdx << '\t' << MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tnew undef: " << UseIdx
<< '\t' << MI; } } while (false)
;
1428 }
1429
1430 // A def of a subregister may be a use of the other subregisters, so
1431 // deleting a def of a subregister may also remove uses. Since CopyMI
1432 // is still part of the function (but about to be erased), mark all
1433 // defs of DstReg in it as <undef>, so that shrinkToUses would
1434 // ignore them.
1435 for (MachineOperand &MO : CopyMI->operands())
1436 if (MO.isReg() && MO.isDef() && MO.getReg() == DstReg)
1437 MO.setIsUndef(true);
1438 LIS->shrinkToUses(&DstLI);
1439
1440 return true;
1441}
1442
1443void RegisterCoalescer::addUndefFlag(const LiveInterval &Int, SlotIndex UseIdx,
1444 MachineOperand &MO, unsigned SubRegIdx) {
1445 LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubRegIdx);
1446 if (MO.isDef())
1447 Mask = ~Mask;
1448 bool IsUndef = true;
1449 for (const LiveInterval::SubRange &S : Int.subranges()) {
1450 if ((S.LaneMask & Mask).none())
1451 continue;
1452 if (S.liveAt(UseIdx)) {
1453 IsUndef = false;
1454 break;
1455 }
1456 }
1457 if (IsUndef) {
1458 MO.setIsUndef(true);
1459 // We found out some subregister use is actually reading an undefined
1460 // value. In some cases the whole vreg has become undefined at this
1461 // point so we have to potentially shrink the main range if the
1462 // use was ending a live segment there.
1463 LiveQueryResult Q = Int.Query(UseIdx);
1464 if (Q.valueOut() == nullptr)
1465 ShrinkMainRange = true;
1466 }
1467}
1468
1469void RegisterCoalescer::updateRegDefsUses(unsigned SrcReg,
1470 unsigned DstReg,
1471 unsigned SubIdx) {
1472 bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
1473 LiveInterval *DstInt = DstIsPhys ? nullptr : &LIS->getInterval(DstReg);
1474
1475 if (DstInt && DstInt->hasSubRanges() && DstReg != SrcReg) {
1476 for (MachineOperand &MO : MRI->reg_operands(DstReg)) {
1477 unsigned SubReg = MO.getSubReg();
1478 if (SubReg == 0 || MO.isUndef())
1479 continue;
1480 MachineInstr &MI = *MO.getParent();
1481 if (MI.isDebugValue())
1482 continue;
1483 SlotIndex UseIdx = LIS->getInstructionIndex(MI).getRegSlot(true);
1484 addUndefFlag(*DstInt, UseIdx, MO, SubReg);
1485 }
1486 }
1487
1488 SmallPtrSet<MachineInstr*, 8> Visited;
1489 for (MachineRegisterInfo::reg_instr_iterator
1490 I = MRI->reg_instr_begin(SrcReg), E = MRI->reg_instr_end();
1491 I != E; ) {
1492 MachineInstr *UseMI = &*(I++);
1493
1494 // Each instruction can only be rewritten once because sub-register
1495 // composition is not always idempotent. When SrcReg != DstReg, rewriting
1496 // the UseMI operands removes them from the SrcReg use-def chain, but when
1497 // SrcReg is DstReg we could encounter UseMI twice if it has multiple
1498 // operands mentioning the virtual register.
1499 if (SrcReg == DstReg && !Visited.insert(UseMI).second)
1500 continue;
1501
1502 SmallVector<unsigned,8> Ops;
1503 bool Reads, Writes;
1504 std::tie(Reads, Writes) = UseMI->readsWritesVirtualRegister(SrcReg, &Ops);
1505
1506 // If SrcReg wasn't read, it may still be the case that DstReg is live-in
1507 // because SrcReg is a sub-register.
1508 if (DstInt && !Reads && SubIdx && !UseMI->isDebugValue())
1509 Reads = DstInt->liveAt(LIS->getInstructionIndex(*UseMI));
1510
1511 // Replace SrcReg with DstReg in all UseMI operands.
1512 for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
1513 MachineOperand &MO = UseMI->getOperand(Ops[i]);
1514
1515 // Adjust <undef> flags in case of sub-register joins. We don't want to
1516 // turn a full def into a read-modify-write sub-register def and vice
1517 // versa.
1518 if (SubIdx && MO.isDef())
1519 MO.setIsUndef(!Reads);
1520
1521 // A subreg use of a partially undef (super) register may be a complete
1522 // undef use now and then has to be marked that way.
1523 if (SubIdx != 0 && MO.isUse() && MRI->shouldTrackSubRegLiveness(DstReg)) {
1524 if (!DstInt->hasSubRanges()) {
1525 BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
1526 LaneBitmask Mask = MRI->getMaxLaneMaskForVReg(DstInt->reg);
1527 DstInt->createSubRangeFrom(Allocator, Mask, *DstInt);
1528 }
1529 SlotIndex MIIdx = UseMI->isDebugValue()
1530 ? LIS->getSlotIndexes()->getIndexBefore(*UseMI)
1531 : LIS->getInstructionIndex(*UseMI);
1532 SlotIndex UseIdx = MIIdx.getRegSlot(true);
1533 addUndefFlag(*DstInt, UseIdx, MO, SubIdx);
1534 }
1535
1536 if (DstIsPhys)
1537 MO.substPhysReg(DstReg, *TRI);
1538 else
1539 MO.substVirtReg(DstReg, SubIdx, *TRI);
1540 }
1541
1542 DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\tupdated: "; if (!UseMI
->isDebugValue()) dbgs() << LIS->getInstructionIndex
(*UseMI) << "\t"; dbgs() << *UseMI; }; } } while (
false)
1543 dbgs() << "\t\tupdated: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\tupdated: "; if (!UseMI
->isDebugValue()) dbgs() << LIS->getInstructionIndex
(*UseMI) << "\t"; dbgs() << *UseMI; }; } } while (
false)
1544 if (!UseMI->isDebugValue())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\tupdated: "; if (!UseMI
->isDebugValue()) dbgs() << LIS->getInstructionIndex
(*UseMI) << "\t"; dbgs() << *UseMI; }; } } while (
false)
1545 dbgs() << LIS->getInstructionIndex(*UseMI) << "\t";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\tupdated: "; if (!UseMI
->isDebugValue()) dbgs() << LIS->getInstructionIndex
(*UseMI) << "\t"; dbgs() << *UseMI; }; } } while (
false)
1546 dbgs() << *UseMI;do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\tupdated: "; if (!UseMI
->isDebugValue()) dbgs() << LIS->getInstructionIndex
(*UseMI) << "\t"; dbgs() << *UseMI; }; } } while (
false)
1547 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\tupdated: "; if (!UseMI
->isDebugValue()) dbgs() << LIS->getInstructionIndex
(*UseMI) << "\t"; dbgs() << *UseMI; }; } } while (
false)
;
1548 }
1549}
1550
1551bool RegisterCoalescer::canJoinPhys(const CoalescerPair &CP) {
1552 // Always join simple intervals that are defined by a single copy from a
1553 // reserved register. This doesn't increase register pressure, so it is
1554 // always beneficial.
1555 if (!MRI->isReserved(CP.getDstReg())) {
1556 DEBUG(dbgs() << "\tCan only merge into reserved registers.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tCan only merge into reserved registers.\n"
; } } while (false)
;
1557 return false;
1558 }
1559
1560 LiveInterval &JoinVInt = LIS->getInterval(CP.getSrcReg());
1561 if (JoinVInt.containsOneValue())
1562 return true;
1563
1564 DEBUG(dbgs() << "\tCannot join complex intervals into reserved register.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tCannot join complex intervals into reserved register.\n"
; } } while (false)
;
1565 return false;
1566}
1567
1568bool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) {
1569 Again = false;
1570 DEBUG(dbgs() << LIS->getInstructionIndex(*CopyMI) << '\t' << *CopyMI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << LIS->getInstructionIndex(*
CopyMI) << '\t' << *CopyMI; } } while (false)
;
1571
1572 CoalescerPair CP(*TRI);
1573 if (!CP.setRegisters(CopyMI)) {
1574 DEBUG(dbgs() << "\tNot coalescable.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tNot coalescable.\n"; } } while
(false)
;
1575 return false;
1576 }
1577
1578 if (CP.getNewRC()) {
1579 auto SrcRC = MRI->getRegClass(CP.getSrcReg());
1580 auto DstRC = MRI->getRegClass(CP.getDstReg());
1581 unsigned SrcIdx = CP.getSrcIdx();
1582 unsigned DstIdx = CP.getDstIdx();
1583 if (CP.isFlipped()) {
1584 std::swap(SrcIdx, DstIdx);
1585 std::swap(SrcRC, DstRC);
1586 }
1587 if (!TRI->shouldCoalesce(CopyMI, SrcRC, SrcIdx, DstRC, DstIdx,
1588 CP.getNewRC(), *LIS)) {
1589 DEBUG(dbgs() << "\tSubtarget bailed on coalescing.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tSubtarget bailed on coalescing.\n"
; } } while (false)
;
1590 return false;
1591 }
1592 }
1593
1594 // Dead code elimination. This really should be handled by MachineDCE, but
1595 // sometimes dead copies slip through, and we can't generate invalid live
1596 // ranges.
1597 if (!CP.isPhys() && CopyMI->allDefsAreDead()) {
1598 DEBUG(dbgs() << "\tCopy is dead.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tCopy is dead.\n"; } } while
(false)
;
1599 DeadDefs.push_back(CopyMI);
1600 eliminateDeadDefs();
1601 return true;
1602 }
1603
1604 // Eliminate undefs.
1605 if (!CP.isPhys() && eliminateUndefCopy(CopyMI)) {
1606 deleteInstr(CopyMI);
1607 return false; // Not coalescable.
1608 }
1609
1610 // Coalesced copies are normally removed immediately, but transformations
1611 // like removeCopyByCommutingDef() can inadvertently create identity copies.
1612 // When that happens, just join the values and remove the copy.
1613 if (CP.getSrcReg() == CP.getDstReg()) {
1614 LiveInterval &LI = LIS->getInterval(CP.getSrcReg());
1615 DEBUG(dbgs() << "\tCopy already coalesced: " << LI << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tCopy already coalesced: " <<
LI << '\n'; } } while (false)
;
1616 const SlotIndex CopyIdx = LIS->getInstructionIndex(*CopyMI);
1617 LiveQueryResult LRQ = LI.Query(CopyIdx);
1618 if (VNInfo *DefVNI = LRQ.valueDefined()) {
1619 VNInfo *ReadVNI = LRQ.valueIn();
1620 assert(ReadVNI && "No value before copy and no <undef> flag.")(static_cast <bool> (ReadVNI && "No value before copy and no <undef> flag."
) ? void (0) : __assert_fail ("ReadVNI && \"No value before copy and no <undef> flag.\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 1620, __extension__ __PRETTY_FUNCTION__))
;
1621 assert(ReadVNI != DefVNI && "Cannot read and define the same value.")(static_cast <bool> (ReadVNI != DefVNI && "Cannot read and define the same value."
) ? void (0) : __assert_fail ("ReadVNI != DefVNI && \"Cannot read and define the same value.\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 1621, __extension__ __PRETTY_FUNCTION__))
;
1622 LI.MergeValueNumberInto(DefVNI, ReadVNI);
1623
1624 // Process subregister liveranges.
1625 for (LiveInterval::SubRange &S : LI.subranges()) {
1626 LiveQueryResult SLRQ = S.Query(CopyIdx);
1627 if (VNInfo *SDefVNI = SLRQ.valueDefined()) {
1628 VNInfo *SReadVNI = SLRQ.valueIn();
1629 S.MergeValueNumberInto(SDefVNI, SReadVNI);
1630 }
1631 }
1632 DEBUG(dbgs() << "\tMerged values: " << LI << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tMerged values: " <<
LI << '\n'; } } while (false)
;
1633 }
1634 deleteInstr(CopyMI);
1635 return true;
1636 }
1637
1638 // Enforce policies.
1639 if (CP.isPhys()) {
1640 DEBUG(dbgs() << "\tConsidering merging " << printReg(CP.getSrcReg(), TRI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tConsidering merging " <<
printReg(CP.getSrcReg(), TRI) << " with " << printReg
(CP.getDstReg(), TRI, CP.getSrcIdx()) << '\n'; } } while
(false)
1641 << " with " << printReg(CP.getDstReg(), TRI, CP.getSrcIdx())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tConsidering merging " <<
printReg(CP.getSrcReg(), TRI) << " with " << printReg
(CP.getDstReg(), TRI, CP.getSrcIdx()) << '\n'; } } while
(false)
1642 << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tConsidering merging " <<
printReg(CP.getSrcReg(), TRI) << " with " << printReg
(CP.getDstReg(), TRI, CP.getSrcIdx()) << '\n'; } } while
(false)
;
1643 if (!canJoinPhys(CP)) {
1644 // Before giving up coalescing, if definition of source is defined by
1645 // trivial computation, try rematerializing it.
1646 bool IsDefCopy;
1647 if (reMaterializeTrivialDef(CP, CopyMI, IsDefCopy))
1648 return true;
1649 if (IsDefCopy)
1650 Again = true; // May be possible to coalesce later.
1651 return false;
1652 }
1653 } else {
1654 // When possible, let DstReg be the larger interval.
1655 if (!CP.isPartial() && LIS->getInterval(CP.getSrcReg()).size() >
1656 LIS->getInterval(CP.getDstReg()).size())
1657 CP.flip();
1658
1659 DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\tConsidering merging to "
<< TRI->getRegClassName(CP.getNewRC()) << " with "
; if (CP.getDstIdx() && CP.getSrcIdx()) dbgs() <<
printReg(CP.getDstReg()) << " in " << TRI->getSubRegIndexName
(CP.getDstIdx()) << " and " << printReg(CP.getSrcReg
()) << " in " << TRI->getSubRegIndexName(CP.getSrcIdx
()) << '\n'; else dbgs() << printReg(CP.getSrcReg
(), TRI) << " in " << printReg(CP.getDstReg(), TRI
, CP.getSrcIdx()) << '\n'; }; } } while (false)
1660 dbgs() << "\tConsidering merging to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\tConsidering merging to "
<< TRI->getRegClassName(CP.getNewRC()) << " with "
; if (CP.getDstIdx() && CP.getSrcIdx()) dbgs() <<
printReg(CP.getDstReg()) << " in " << TRI->getSubRegIndexName
(CP.getDstIdx()) << " and " << printReg(CP.getSrcReg
()) << " in " << TRI->getSubRegIndexName(CP.getSrcIdx
()) << '\n'; else dbgs() << printReg(CP.getSrcReg
(), TRI) << " in " << printReg(CP.getDstReg(), TRI
, CP.getSrcIdx()) << '\n'; }; } } while (false)
1661 << TRI->getRegClassName(CP.getNewRC()) << " with ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\tConsidering merging to "
<< TRI->getRegClassName(CP.getNewRC()) << " with "
; if (CP.getDstIdx() && CP.getSrcIdx()) dbgs() <<
printReg(CP.getDstReg()) << " in " << TRI->getSubRegIndexName
(CP.getDstIdx()) << " and " << printReg(CP.getSrcReg
()) << " in " << TRI->getSubRegIndexName(CP.getSrcIdx
()) << '\n'; else dbgs() << printReg(CP.getSrcReg
(), TRI) << " in " << printReg(CP.getDstReg(), TRI
, CP.getSrcIdx()) << '\n'; }; } } while (false)
1662 if (CP.getDstIdx() && CP.getSrcIdx())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\tConsidering merging to "
<< TRI->getRegClassName(CP.getNewRC()) << " with "
; if (CP.getDstIdx() && CP.getSrcIdx()) dbgs() <<
printReg(CP.getDstReg()) << " in " << TRI->getSubRegIndexName
(CP.getDstIdx()) << " and " << printReg(CP.getSrcReg
()) << " in " << TRI->getSubRegIndexName(CP.getSrcIdx
()) << '\n'; else dbgs() << printReg(CP.getSrcReg
(), TRI) << " in " << printReg(CP.getDstReg(), TRI
, CP.getSrcIdx()) << '\n'; }; } } while (false)
1663 dbgs() << printReg(CP.getDstReg()) << " in "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\tConsidering merging to "
<< TRI->getRegClassName(CP.getNewRC()) << " with "
; if (CP.getDstIdx() && CP.getSrcIdx()) dbgs() <<
printReg(CP.getDstReg()) << " in " << TRI->getSubRegIndexName
(CP.getDstIdx()) << " and " << printReg(CP.getSrcReg
()) << " in " << TRI->getSubRegIndexName(CP.getSrcIdx
()) << '\n'; else dbgs() << printReg(CP.getSrcReg
(), TRI) << " in " << printReg(CP.getDstReg(), TRI
, CP.getSrcIdx()) << '\n'; }; } } while (false)
1664 << TRI->getSubRegIndexName(CP.getDstIdx()) << " and "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\tConsidering merging to "
<< TRI->getRegClassName(CP.getNewRC()) << " with "
; if (CP.getDstIdx() && CP.getSrcIdx()) dbgs() <<
printReg(CP.getDstReg()) << " in " << TRI->getSubRegIndexName
(CP.getDstIdx()) << " and " << printReg(CP.getSrcReg
()) << " in " << TRI->getSubRegIndexName(CP.getSrcIdx
()) << '\n'; else dbgs() << printReg(CP.getSrcReg
(), TRI) << " in " << printReg(CP.getDstReg(), TRI
, CP.getSrcIdx()) << '\n'; }; } } while (false)
1665 << printReg(CP.getSrcReg()) << " in "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\tConsidering merging to "
<< TRI->getRegClassName(CP.getNewRC()) << " with "
; if (CP.getDstIdx() && CP.getSrcIdx()) dbgs() <<
printReg(CP.getDstReg()) << " in " << TRI->getSubRegIndexName
(CP.getDstIdx()) << " and " << printReg(CP.getSrcReg
()) << " in " << TRI->getSubRegIndexName(CP.getSrcIdx
()) << '\n'; else dbgs() << printReg(CP.getSrcReg
(), TRI) << " in " << printReg(CP.getDstReg(), TRI
, CP.getSrcIdx()) << '\n'; }; } } while (false)
1666 << TRI->getSubRegIndexName(CP.getSrcIdx()) << '\n';do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\tConsidering merging to "
<< TRI->getRegClassName(CP.getNewRC()) << " with "
; if (CP.getDstIdx() && CP.getSrcIdx()) dbgs() <<
printReg(CP.getDstReg()) << " in " << TRI->getSubRegIndexName
(CP.getDstIdx()) << " and " << printReg(CP.getSrcReg
()) << " in " << TRI->getSubRegIndexName(CP.getSrcIdx
()) << '\n'; else dbgs() << printReg(CP.getSrcReg
(), TRI) << " in " << printReg(CP.getDstReg(), TRI
, CP.getSrcIdx()) << '\n'; }; } } while (false)
1667 elsedo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\tConsidering merging to "
<< TRI->getRegClassName(CP.getNewRC()) << " with "
; if (CP.getDstIdx() && CP.getSrcIdx()) dbgs() <<
printReg(CP.getDstReg()) << " in " << TRI->getSubRegIndexName
(CP.getDstIdx()) << " and " << printReg(CP.getSrcReg
()) << " in " << TRI->getSubRegIndexName(CP.getSrcIdx
()) << '\n'; else dbgs() << printReg(CP.getSrcReg
(), TRI) << " in " << printReg(CP.getDstReg(), TRI
, CP.getSrcIdx()) << '\n'; }; } } while (false)
1668 dbgs() << printReg(CP.getSrcReg(), TRI) << " in "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\tConsidering merging to "
<< TRI->getRegClassName(CP.getNewRC()) << " with "
; if (CP.getDstIdx() && CP.getSrcIdx()) dbgs() <<
printReg(CP.getDstReg()) << " in " << TRI->getSubRegIndexName
(CP.getDstIdx()) << " and " << printReg(CP.getSrcReg
()) << " in " << TRI->getSubRegIndexName(CP.getSrcIdx
()) << '\n'; else dbgs() << printReg(CP.getSrcReg
(), TRI) << " in " << printReg(CP.getDstReg(), TRI
, CP.getSrcIdx()) << '\n'; }; } } while (false)
1669 << printReg(CP.getDstReg(), TRI, CP.getSrcIdx()) << '\n';do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\tConsidering merging to "
<< TRI->getRegClassName(CP.getNewRC()) << " with "
; if (CP.getDstIdx() && CP.getSrcIdx()) dbgs() <<
printReg(CP.getDstReg()) << " in " << TRI->getSubRegIndexName
(CP.getDstIdx()) << " and " << printReg(CP.getSrcReg
()) << " in " << TRI->getSubRegIndexName(CP.getSrcIdx
()) << '\n'; else dbgs() << printReg(CP.getSrcReg
(), TRI) << " in " << printReg(CP.getDstReg(), TRI
, CP.getSrcIdx()) << '\n'; }; } } while (false)
1670 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\tConsidering merging to "
<< TRI->getRegClassName(CP.getNewRC()) << " with "
; if (CP.getDstIdx() && CP.getSrcIdx()) dbgs() <<
printReg(CP.getDstReg()) << " in " << TRI->getSubRegIndexName
(CP.getDstIdx()) << " and " << printReg(CP.getSrcReg
()) << " in " << TRI->getSubRegIndexName(CP.getSrcIdx
()) << '\n'; else dbgs() << printReg(CP.getSrcReg
(), TRI) << " in " << printReg(CP.getDstReg(), TRI
, CP.getSrcIdx()) << '\n'; }; } } while (false)
;
1671 }
1672
1673 ShrinkMask = LaneBitmask::getNone();
1674 ShrinkMainRange = false;
1675
1676 // Okay, attempt to join these two intervals. On failure, this returns false.
1677 // Otherwise, if one of the intervals being joined is a physreg, this method
1678 // always canonicalizes DstInt to be it. The output "SrcInt" will not have
1679 // been modified, so we can use this information below to update aliases.
1680 if (!joinIntervals(CP)) {
1681 // Coalescing failed.
1682
1683 // If definition of source is defined by trivial computation, try
1684 // rematerializing it.
1685 bool IsDefCopy;
1686 if (reMaterializeTrivialDef(CP, CopyMI, IsDefCopy))
1687 return true;
1688
1689 // If we can eliminate the copy without merging the live segments, do so
1690 // now.
1691 if (!CP.isPartial() && !CP.isPhys()) {
1692 if (adjustCopiesBackFrom(CP, CopyMI) ||
1693 removeCopyByCommutingDef(CP, CopyMI)) {
1694 deleteInstr(CopyMI);
1695 DEBUG(dbgs() << "\tTrivial!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tTrivial!\n"; } } while (false
)
;
1696 return true;
1697 }
1698 }
1699
1700 // Try and see if we can partially eliminate the copy by moving the copy to
1701 // its predecessor.
1702 if (!CP.isPartial() && !CP.isPhys())
1703 if (removePartialRedundancy(CP, *CopyMI))
1704 return true;
1705
1706 // Otherwise, we are unable to join the intervals.
1707 DEBUG(dbgs() << "\tInterference!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tInterference!\n"; } } while
(false)
;
1708 Again = true; // May be possible to coalesce later.
1709 return false;
1710 }
1711
1712 // Coalescing to a virtual register that is of a sub-register class of the
1713 // other. Make sure the resulting register is set to the right register class.
1714 if (CP.isCrossClass()) {
1715 ++numCrossRCs;
1716 MRI->setRegClass(CP.getDstReg(), CP.getNewRC());
1717 }
1718
1719 // Removing sub-register copies can ease the register class constraints.
1720 // Make sure we attempt to inflate the register class of DstReg.
1721 if (!CP.isPhys() && RegClassInfo.isProperSubClass(CP.getNewRC()))
1722 InflateRegs.push_back(CP.getDstReg());
1723
1724 // CopyMI has been erased by joinIntervals at this point. Remove it from
1725 // ErasedInstrs since copyCoalesceWorkList() won't add a successful join back
1726 // to the work list. This keeps ErasedInstrs from growing needlessly.
1727 ErasedInstrs.erase(CopyMI);
1728
1729 // Rewrite all SrcReg operands to DstReg.
1730 // Also update DstReg operands to include DstIdx if it is set.
1731 if (CP.getDstIdx())
1732 updateRegDefsUses(CP.getDstReg(), CP.getDstReg(), CP.getDstIdx());
1733 updateRegDefsUses(CP.getSrcReg(), CP.getDstReg(), CP.getSrcIdx());
1734
1735 // Shrink subregister ranges if necessary.
1736 if (ShrinkMask.any()) {
1737 LiveInterval &LI = LIS->getInterval(CP.getDstReg());
1738 for (LiveInterval::SubRange &S : LI.subranges()) {
1739 if ((S.LaneMask & ShrinkMask).none())
1740 continue;
1741 DEBUG(dbgs() << "Shrink LaneUses (Lane " << PrintLaneMask(S.LaneMask)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Shrink LaneUses (Lane " <<
PrintLaneMask(S.LaneMask) << ")\n"; } } while (false)
1742 << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Shrink LaneUses (Lane " <<
PrintLaneMask(S.LaneMask) << ")\n"; } } while (false)
;
1743 LIS->shrinkToUses(S, LI.reg);
1744 }
1745 LI.removeEmptySubRanges();
1746 }
1747 if (ShrinkMainRange) {
1748 LiveInterval &LI = LIS->getInterval(CP.getDstReg());
1749 shrinkToUses(&LI);
1750 }
1751
1752 // SrcReg is guaranteed to be the register whose live interval that is
1753 // being merged.
1754 LIS->removeInterval(CP.getSrcReg());
1755
1756 // Update regalloc hint.
1757 TRI->updateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *MF);
1758
1759 DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\tSuccess: " << printReg
(CP.getSrcReg(), TRI, CP.getSrcIdx()) << " -> " <<
printReg(CP.getDstReg(), TRI, CP.getDstIdx()) << '\n';
dbgs() << "\tResult = "; if (CP.isPhys()) dbgs() <<
printReg(CP.getDstReg(), TRI); else dbgs() << LIS->
getInterval(CP.getDstReg()); dbgs() << '\n'; }; } } while
(false)
1760 dbgs() << "\tSuccess: " << printReg(CP.getSrcReg(), TRI, CP.getSrcIdx())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\tSuccess: " << printReg
(CP.getSrcReg(), TRI, CP.getSrcIdx()) << " -> " <<
printReg(CP.getDstReg(), TRI, CP.getDstIdx()) << '\n';
dbgs() << "\tResult = "; if (CP.isPhys()) dbgs() <<
printReg(CP.getDstReg(), TRI); else dbgs() << LIS->
getInterval(CP.getDstReg()); dbgs() << '\n'; }; } } while
(false)
1761 << " -> " << printReg(CP.getDstReg(), TRI, CP.getDstIdx()) << '\n';do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\tSuccess: " << printReg
(CP.getSrcReg(), TRI, CP.getSrcIdx()) << " -> " <<
printReg(CP.getDstReg(), TRI, CP.getDstIdx()) << '\n';
dbgs() << "\tResult = "; if (CP.isPhys()) dbgs() <<
printReg(CP.getDstReg(), TRI); else dbgs() << LIS->
getInterval(CP.getDstReg()); dbgs() << '\n'; }; } } while
(false)
1762 dbgs() << "\tResult = ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\tSuccess: " << printReg
(CP.getSrcReg(), TRI, CP.getSrcIdx()) << " -> " <<
printReg(CP.getDstReg(), TRI, CP.getDstIdx()) << '\n';
dbgs() << "\tResult = "; if (CP.isPhys()) dbgs() <<
printReg(CP.getDstReg(), TRI); else dbgs() << LIS->
getInterval(CP.getDstReg()); dbgs() << '\n'; }; } } while
(false)
1763 if (CP.isPhys())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\tSuccess: " << printReg
(CP.getSrcReg(), TRI, CP.getSrcIdx()) << " -> " <<
printReg(CP.getDstReg(), TRI, CP.getDstIdx()) << '\n';
dbgs() << "\tResult = "; if (CP.isPhys()) dbgs() <<
printReg(CP.getDstReg(), TRI); else dbgs() << LIS->
getInterval(CP.getDstReg()); dbgs() << '\n'; }; } } while
(false)
1764 dbgs() << printReg(CP.getDstReg(), TRI);do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\tSuccess: " << printReg
(CP.getSrcReg(), TRI, CP.getSrcIdx()) << " -> " <<
printReg(CP.getDstReg(), TRI, CP.getDstIdx()) << '\n';
dbgs() << "\tResult = "; if (CP.isPhys()) dbgs() <<
printReg(CP.getDstReg(), TRI); else dbgs() << LIS->
getInterval(CP.getDstReg()); dbgs() << '\n'; }; } } while
(false)
1765 elsedo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\tSuccess: " << printReg
(CP.getSrcReg(), TRI, CP.getSrcIdx()) << " -> " <<
printReg(CP.getDstReg(), TRI, CP.getDstIdx()) << '\n';
dbgs() << "\tResult = "; if (CP.isPhys()) dbgs() <<
printReg(CP.getDstReg(), TRI); else dbgs() << LIS->
getInterval(CP.getDstReg()); dbgs() << '\n'; }; } } while
(false)
1766 dbgs() << LIS->getInterval(CP.getDstReg());do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\tSuccess: " << printReg
(CP.getSrcReg(), TRI, CP.getSrcIdx()) << " -> " <<
printReg(CP.getDstReg(), TRI, CP.getDstIdx()) << '\n';
dbgs() << "\tResult = "; if (CP.isPhys()) dbgs() <<
printReg(CP.getDstReg(), TRI); else dbgs() << LIS->
getInterval(CP.getDstReg()); dbgs() << '\n'; }; } } while
(false)
1767 dbgs() << '\n';do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\tSuccess: " << printReg
(CP.getSrcReg(), TRI, CP.getSrcIdx()) << " -> " <<
printReg(CP.getDstReg(), TRI, CP.getDstIdx()) << '\n';
dbgs() << "\tResult = "; if (CP.isPhys()) dbgs() <<
printReg(CP.getDstReg(), TRI); else dbgs() << LIS->
getInterval(CP.getDstReg()); dbgs() << '\n'; }; } } while
(false)
1768 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\tSuccess: " << printReg
(CP.getSrcReg(), TRI, CP.getSrcIdx()) << " -> " <<
printReg(CP.getDstReg(), TRI, CP.getDstIdx()) << '\n';
dbgs() << "\tResult = "; if (CP.isPhys()) dbgs() <<
printReg(CP.getDstReg(), TRI); else dbgs() << LIS->
getInterval(CP.getDstReg()); dbgs() << '\n'; }; } } while
(false)
;
1769
1770 ++numJoins;
1771 return true;
1772}
1773
1774bool RegisterCoalescer::joinReservedPhysReg(CoalescerPair &CP) {
1775 unsigned DstReg = CP.getDstReg();
1776 unsigned SrcReg = CP.getSrcReg();
1777 assert(CP.isPhys() && "Must be a physreg copy")(static_cast <bool> (CP.isPhys() && "Must be a physreg copy"
) ? void (0) : __assert_fail ("CP.isPhys() && \"Must be a physreg copy\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 1777, __extension__ __PRETTY_FUNCTION__))
;
1778 assert(MRI->isReserved(DstReg) && "Not a reserved register")(static_cast <bool> (MRI->isReserved(DstReg) &&
"Not a reserved register") ? void (0) : __assert_fail ("MRI->isReserved(DstReg) && \"Not a reserved register\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 1778, __extension__ __PRETTY_FUNCTION__))
;
1779 LiveInterval &RHS = LIS->getInterval(SrcReg);
1780 DEBUG(dbgs() << "\t\tRHS = " << RHS << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tRHS = " << RHS <<
'\n'; } } while (false)
;
1781
1782 assert(RHS.containsOneValue() && "Invalid join with reserved register")(static_cast <bool> (RHS.containsOneValue() && "Invalid join with reserved register"
) ? void (0) : __assert_fail ("RHS.containsOneValue() && \"Invalid join with reserved register\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 1782, __extension__ __PRETTY_FUNCTION__))
;
1783
1784 // Optimization for reserved registers like ESP. We can only merge with a
1785 // reserved physreg if RHS has a single value that is a copy of DstReg.
1786 // The live range of the reserved register will look like a set of dead defs
1787 // - we don't properly track the live range of reserved registers.
1788
1789 // Deny any overlapping intervals. This depends on all the reserved
1790 // register live ranges to look like dead defs.
1791 if (!MRI->isConstantPhysReg(DstReg)) {
1792 for (MCRegUnitIterator UI(DstReg, TRI); UI.isValid(); ++UI) {
1793 // Abort if not all the regunits are reserved.
1794 for (MCRegUnitRootIterator RI(*UI, TRI); RI.isValid(); ++RI) {
1795 if (!MRI->isReserved(*RI))
1796 return false;
1797 }
1798 if (RHS.overlaps(LIS->getRegUnit(*UI))) {
1799 DEBUG(dbgs() << "\t\tInterference: " << printRegUnit(*UI, TRI) << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tInterference: " <<
printRegUnit(*UI, TRI) << '\n'; } } while (false)
;
1800 return false;
1801 }
1802 }
1803
1804 // We must also check for overlaps with regmask clobbers.
1805 BitVector RegMaskUsable;
1806 if (LIS->checkRegMaskInterference(RHS, RegMaskUsable) &&
1807 !RegMaskUsable.test(DstReg)) {
1808 DEBUG(dbgs() << "\t\tRegMask interference\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tRegMask interference\n";
} } while (false)
;
1809 return false;
1810 }
1811 }
1812
1813 // Skip any value computations, we are not adding new values to the
1814 // reserved register. Also skip merging the live ranges, the reserved
1815 // register live range doesn't need to be accurate as long as all the
1816 // defs are there.
1817
1818 // Delete the identity copy.
1819 MachineInstr *CopyMI;
1820 if (CP.isFlipped()) {
1821 // Physreg is copied into vreg
1822 // %y = COPY %physreg_x
1823 // ... //< no other def of %x here
1824 // use %y
1825 // =>
1826 // ...
1827 // use %x
1828 CopyMI = MRI->getVRegDef(SrcReg);
1829 } else {
1830 // VReg is copied into physreg:
1831 // %y = def
1832 // ... //< no other def or use of %y here
1833 // %y = COPY %physreg_x
1834 // =>
1835 // %y = def
1836 // ...
1837 if (!MRI->hasOneNonDBGUse(SrcReg)) {
1838 DEBUG(dbgs() << "\t\tMultiple vreg uses!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tMultiple vreg uses!\n"; }
} while (false)
;
1839 return false;
1840 }
1841
1842 if (!LIS->intervalIsInOneMBB(RHS)) {
1843 DEBUG(dbgs() << "\t\tComplex control flow!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tComplex control flow!\n"
; } } while (false)
;
1844 return false;
1845 }
1846
1847 MachineInstr &DestMI = *MRI->getVRegDef(SrcReg);
1848 CopyMI = &*MRI->use_instr_nodbg_begin(SrcReg);
1849 SlotIndex CopyRegIdx = LIS->getInstructionIndex(*CopyMI).getRegSlot();
1850 SlotIndex DestRegIdx = LIS->getInstructionIndex(DestMI).getRegSlot();
1851
1852 if (!MRI->isConstantPhysReg(DstReg)) {
1853 // We checked above that there are no interfering defs of the physical
1854 // register. However, for this case, where we intend to move up the def of
1855 // the physical register, we also need to check for interfering uses.
1856 SlotIndexes *Indexes = LIS->getSlotIndexes();
1857 for (SlotIndex SI = Indexes->getNextNonNullIndex(DestRegIdx);
1858 SI != CopyRegIdx; SI = Indexes->getNextNonNullIndex(SI)) {
1859 MachineInstr *MI = LIS->getInstructionFromIndex(SI);
1860 if (MI->readsRegister(DstReg, TRI)) {
1861 DEBUG(dbgs() << "\t\tInterference (read): " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tInterference (read): " <<
*MI; } } while (false)
;
1862 return false;
1863 }
1864 }
1865 }
1866
1867 // We're going to remove the copy which defines a physical reserved
1868 // register, so remove its valno, etc.
1869 DEBUG(dbgs() << "\t\tRemoving phys reg def of " << printReg(DstReg, TRI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tRemoving phys reg def of "
<< printReg(DstReg, TRI) << " at " << CopyRegIdx
<< "\n"; } } while (false)
1870 << " at " << CopyRegIdx << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tRemoving phys reg def of "
<< printReg(DstReg, TRI) << " at " << CopyRegIdx
<< "\n"; } } while (false)
;
1871
1872 LIS->removePhysRegDefAt(DstReg, CopyRegIdx);
1873 // Create a new dead def at the new def location.
1874 for (MCRegUnitIterator UI(DstReg, TRI); UI.isValid(); ++UI) {
1875 LiveRange &LR = LIS->getRegUnit(*UI);
1876 LR.createDeadDef(DestRegIdx, LIS->getVNInfoAllocator());
1877 }
1878 }
1879
1880 deleteInstr(CopyMI);
1881
1882 // We don't track kills for reserved registers.
1883 MRI->clearKillFlags(CP.getSrcReg());
1884
1885 return true;
1886}
1887
1888//===----------------------------------------------------------------------===//
1889// Interference checking and interval joining
1890//===----------------------------------------------------------------------===//
1891//
1892// In the easiest case, the two live ranges being joined are disjoint, and
1893// there is no interference to consider. It is quite common, though, to have
1894// overlapping live ranges, and we need to check if the interference can be
1895// resolved.
1896//
1897// The live range of a single SSA value forms a sub-tree of the dominator tree.
1898// This means that two SSA values overlap if and only if the def of one value
1899// is contained in the live range of the other value. As a special case, the
1900// overlapping values can be defined at the same index.
1901//
1902// The interference from an overlapping def can be resolved in these cases:
1903//
1904// 1. Coalescable copies. The value is defined by a copy that would become an
1905// identity copy after joining SrcReg and DstReg. The copy instruction will
1906// be removed, and the value will be merged with the source value.
1907//
1908// There can be several copies back and forth, causing many values to be
1909// merged into one. We compute a list of ultimate values in the joined live
1910// range as well as a mappings from the old value numbers.
1911//
1912// 2. IMPLICIT_DEF. This instruction is only inserted to ensure all PHI
1913// predecessors have a live out value. It doesn't cause real interference,
1914// and can be merged into the value it overlaps. Like a coalescable copy, it
1915// can be erased after joining.
1916//
1917// 3. Copy of external value. The overlapping def may be a copy of a value that
1918// is already in the other register. This is like a coalescable copy, but
1919// the live range of the source register must be trimmed after erasing the
1920// copy instruction:
1921//
1922// %src = COPY %ext
1923// %dst = COPY %ext <-- Remove this COPY, trim the live range of %ext.
1924//
1925// 4. Clobbering undefined lanes. Vector registers are sometimes built by
1926// defining one lane at a time:
1927//
1928// %dst:ssub0<def,read-undef> = FOO
1929// %src = BAR
1930// %dst:ssub1 = COPY %src
1931//
1932// The live range of %src overlaps the %dst value defined by FOO, but
1933// merging %src into %dst:ssub1 is only going to clobber the ssub1 lane
1934// which was undef anyway.
1935//
1936// The value mapping is more complicated in this case. The final live range
1937// will have different value numbers for both FOO and BAR, but there is no
1938// simple mapping from old to new values. It may even be necessary to add
1939// new PHI values.
1940//
1941// 5. Clobbering dead lanes. A def may clobber a lane of a vector register that
1942// is live, but never read. This can happen because we don't compute
1943// individual live ranges per lane.
1944//
1945// %dst = FOO
1946// %src = BAR
1947// %dst:ssub1 = COPY %src
1948//
1949// This kind of interference is only resolved locally. If the clobbered
1950// lane value escapes the block, the join is aborted.
1951
1952namespace {
1953
1954/// Track information about values in a single virtual register about to be
1955/// joined. Objects of this class are always created in pairs - one for each
1956/// side of the CoalescerPair (or one for each lane of a side of the coalescer
1957/// pair)
1958class JoinVals {
1959 /// Live range we work on.
1960 LiveRange &LR;
1961
1962 /// (Main) register we work on.
1963 const unsigned Reg;
1964
1965 /// Reg (and therefore the values in this liverange) will end up as
1966 /// subregister SubIdx in the coalesced register. Either CP.DstIdx or
1967 /// CP.SrcIdx.
1968 const unsigned SubIdx;
1969
1970 /// The LaneMask that this liverange will occupy the coalesced register. May
1971 /// be smaller than the lanemask produced by SubIdx when merging subranges.
1972 const LaneBitmask LaneMask;
1973
1974 /// This is true when joining sub register ranges, false when joining main
1975 /// ranges.
1976 const bool SubRangeJoin;
1977
1978 /// Whether the current LiveInterval tracks subregister liveness.
1979 const bool TrackSubRegLiveness;
1980
1981 /// Values that will be present in the final live range.
1982 SmallVectorImpl<VNInfo*> &NewVNInfo;
1983
1984 const CoalescerPair &CP;
1985 LiveIntervals *LIS;
1986 SlotIndexes *Indexes;
1987 const TargetRegisterInfo *TRI;
1988
1989 /// Value number assignments. Maps value numbers in LI to entries in
1990 /// NewVNInfo. This is suitable for passing to LiveInterval::join().
1991 SmallVector<int, 8> Assignments;
1992
1993 /// Conflict resolution for overlapping values.
1994 enum ConflictResolution {
1995 /// No overlap, simply keep this value.
1996 CR_Keep,
1997
1998 /// Merge this value into OtherVNI and erase the defining instruction.
1999 /// Used for IMPLICIT_DEF, coalescable copies, and copies from external
2000 /// values.
2001 CR_Erase,
2002
2003 /// Merge this value into OtherVNI but keep the defining instruction.
2004 /// This is for the special case where OtherVNI is defined by the same
2005 /// instruction.
2006 CR_Merge,
2007
2008 /// Keep this value, and have it replace OtherVNI where possible. This
2009 /// complicates value mapping since OtherVNI maps to two different values
2010 /// before and after this def.
2011 /// Used when clobbering undefined or dead lanes.
2012 CR_Replace,
2013
2014 /// Unresolved conflict. Visit later when all values have been mapped.
2015 CR_Unresolved,
2016
2017 /// Unresolvable conflict. Abort the join.
2018 CR_Impossible
2019 };
2020
2021 /// Per-value info for LI. The lane bit masks are all relative to the final
2022 /// joined register, so they can be compared directly between SrcReg and
2023 /// DstReg.
2024 struct Val {
2025 ConflictResolution Resolution = CR_Keep;
2026
2027 /// Lanes written by this def, 0 for unanalyzed values.
2028 LaneBitmask WriteLanes;
2029
2030 /// Lanes with defined values in this register. Other lanes are undef and
2031 /// safe to clobber.
2032 LaneBitmask ValidLanes;
2033
2034 /// Value in LI being redefined by this def.
2035 VNInfo *RedefVNI = nullptr;
2036
2037 /// Value in the other live range that overlaps this def, if any.
2038 VNInfo *OtherVNI = nullptr;
2039
2040 /// Is this value an IMPLICIT_DEF that can be erased?
2041 ///
2042 /// IMPLICIT_DEF values should only exist at the end of a basic block that
2043 /// is a predecessor to a phi-value. These IMPLICIT_DEF instructions can be
2044 /// safely erased if they are overlapping a live value in the other live
2045 /// interval.
2046 ///
2047 /// Weird control flow graphs and incomplete PHI handling in
2048 /// ProcessImplicitDefs can very rarely create IMPLICIT_DEF values with
2049 /// longer live ranges. Such IMPLICIT_DEF values should be treated like
2050 /// normal values.
2051 bool ErasableImplicitDef = false;
2052
2053 /// True when the live range of this value will be pruned because of an
2054 /// overlapping CR_Replace value in the other live range.
2055 bool Pruned = false;
2056
2057 /// True once Pruned above has been computed.
2058 bool PrunedComputed = false;
2059
2060 Val() = default;
2061
2062 bool isAnalyzed() const { return WriteLanes.any(); }
2063 };
2064
2065 /// One entry per value number in LI.
2066 SmallVector<Val, 8> Vals;
2067
2068 /// Compute the bitmask of lanes actually written by DefMI.
2069 /// Set Redef if there are any partial register definitions that depend on the
2070 /// previous value of the register.
2071 LaneBitmask computeWriteLanes(const MachineInstr *DefMI, bool &Redef) const;
2072
2073 /// Find the ultimate value that VNI was copied from.
2074 std::pair<const VNInfo*,unsigned> followCopyChain(const VNInfo *VNI) const;
2075
2076 bool valuesIdentical(VNInfo *Val0, VNInfo *Val1, const JoinVals &Other) const;
2077
2078 /// Analyze ValNo in this live range, and set all fields of Vals[ValNo].
2079 /// Return a conflict resolution when possible, but leave the hard cases as
2080 /// CR_Unresolved.
2081 /// Recursively calls computeAssignment() on this and Other, guaranteeing that
2082 /// both OtherVNI and RedefVNI have been analyzed and mapped before returning.
2083 /// The recursion always goes upwards in the dominator tree, making loops
2084 /// impossible.
2085 ConflictResolution analyzeValue(unsigned ValNo, JoinVals &Other);
2086
2087 /// Compute the value assignment for ValNo in RI.
2088 /// This may be called recursively by analyzeValue(), but never for a ValNo on
2089 /// the stack.
2090 void computeAssignment(unsigned ValNo, JoinVals &Other);
2091
2092 /// Assuming ValNo is going to clobber some valid lanes in Other.LR, compute
2093 /// the extent of the tainted lanes in the block.
2094 ///
2095 /// Multiple values in Other.LR can be affected since partial redefinitions
2096 /// can preserve previously tainted lanes.
2097 ///
2098 /// 1 %dst = VLOAD <-- Define all lanes in %dst
2099 /// 2 %src = FOO <-- ValNo to be joined with %dst:ssub0
2100 /// 3 %dst:ssub1 = BAR <-- Partial redef doesn't clear taint in ssub0
2101 /// 4 %dst:ssub0 = COPY %src <-- Conflict resolved, ssub0 wasn't read
2102 ///
2103 /// For each ValNo in Other that is affected, add an (EndIndex, TaintedLanes)
2104 /// entry to TaintedVals.
2105 ///
2106 /// Returns false if the tainted lanes extend beyond the basic block.
2107 bool
2108 taintExtent(unsigned ValNo, LaneBitmask TaintedLanes, JoinVals &Other,
2109 SmallVectorImpl<std::pair<SlotIndex, LaneBitmask>> &TaintExtent);
2110
2111 /// Return true if MI uses any of the given Lanes from Reg.
2112 /// This does not include partial redefinitions of Reg.
2113 bool usesLanes(const MachineInstr &MI, unsigned, unsigned, LaneBitmask) const;
2114
2115 /// Determine if ValNo is a copy of a value number in LR or Other.LR that will
2116 /// be pruned:
2117 ///
2118 /// %dst = COPY %src
2119 /// %src = COPY %dst <-- This value to be pruned.
2120 /// %dst = COPY %src <-- This value is a copy of a pruned value.
2121 bool isPrunedValue(unsigned ValNo, JoinVals &Other);
2122
2123public:
2124 JoinVals(LiveRange &LR, unsigned Reg, unsigned SubIdx, LaneBitmask LaneMask,
2125 SmallVectorImpl<VNInfo*> &newVNInfo, const CoalescerPair &cp,
2126 LiveIntervals *lis, const TargetRegisterInfo *TRI, bool SubRangeJoin,
2127 bool TrackSubRegLiveness)
2128 : LR(LR), Reg(Reg), SubIdx(SubIdx), LaneMask(LaneMask),
2129 SubRangeJoin(SubRangeJoin), TrackSubRegLiveness(TrackSubRegLiveness),
2130 NewVNInfo(newVNInfo), CP(cp), LIS(lis), Indexes(LIS->getSlotIndexes()),
2131 TRI(TRI), Assignments(LR.getNumValNums(), -1), Vals(LR.getNumValNums()) {}
2132
2133 /// Analyze defs in LR and compute a value mapping in NewVNInfo.
2134 /// Returns false if any conflicts were impossible to resolve.
2135 bool mapValues(JoinVals &Other);
2136
2137 /// Try to resolve conflicts that require all values to be mapped.
2138 /// Returns false if any conflicts were impossible to resolve.
2139 bool resolveConflicts(JoinVals &Other);
2140
2141 /// Prune the live range of values in Other.LR where they would conflict with
2142 /// CR_Replace values in LR. Collect end points for restoring the live range
2143 /// after joining.
2144 void pruneValues(JoinVals &Other, SmallVectorImpl<SlotIndex> &EndPoints,
2145 bool changeInstrs);
2146
2147 /// Removes subranges starting at copies that get removed. This sometimes
2148 /// happens when undefined subranges are copied around. These ranges contain
2149 /// no useful information and can be removed.
2150 void pruneSubRegValues(LiveInterval &LI, LaneBitmask &ShrinkMask);
2151
2152 /// Pruning values in subranges can lead to removing segments in these
2153 /// subranges started by IMPLICIT_DEFs. The corresponding segments in
2154 /// the main range also need to be removed. This function will mark
2155 /// the corresponding values in the main range as pruned, so that
2156 /// eraseInstrs can do the final cleanup.
2157 /// The parameter @p LI must be the interval whose main range is the
2158 /// live range LR.
2159 void pruneMainSegments(LiveInterval &LI, bool &ShrinkMainRange);
2160
2161 /// Erase any machine instructions that have been coalesced away.
2162 /// Add erased instructions to ErasedInstrs.
2163 /// Add foreign virtual registers to ShrinkRegs if their live range ended at
2164 /// the erased instrs.
2165 void eraseInstrs(SmallPtrSetImpl<MachineInstr*> &ErasedInstrs,
2166 SmallVectorImpl<unsigned> &ShrinkRegs,
2167 LiveInterval *LI = nullptr);
2168
2169 /// Remove liverange defs at places where implicit defs will be removed.
2170 void removeImplicitDefs();
2171
2172 /// Get the value assignments suitable for passing to LiveInterval::join.
2173 const int *getAssignments() const { return Assignments.data(); }
2174};
2175
2176} // end anonymous namespace
2177
2178LaneBitmask JoinVals::computeWriteLanes(const MachineInstr *DefMI, bool &Redef)
2179 const {
2180 LaneBitmask L;
2181 for (const MachineOperand &MO : DefMI->operands()) {
2182 if (!MO.isReg() || MO.getReg() != Reg || !MO.isDef())
2183 continue;
2184 L |= TRI->getSubRegIndexLaneMask(
2185 TRI->composeSubRegIndices(SubIdx, MO.getSubReg()));
2186 if (MO.readsReg())
2187 Redef = true;
2188 }
2189 return L;
2190}
2191
2192std::pair<const VNInfo*, unsigned> JoinVals::followCopyChain(
2193 const VNInfo *VNI) const {
2194 unsigned Reg = this->Reg;
2195
2196 while (!VNI->isPHIDef()) {
2197 SlotIndex Def = VNI->def;
2198 MachineInstr *MI = Indexes->getInstructionFromIndex(Def);
2199 assert(MI && "No defining instruction")(static_cast <bool> (MI && "No defining instruction"
) ? void (0) : __assert_fail ("MI && \"No defining instruction\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 2199, __extension__ __PRETTY_FUNCTION__))
;
2200 if (!MI->isFullCopy())
2201 return std::make_pair(VNI, Reg);
2202 unsigned SrcReg = MI->getOperand(1).getReg();
2203 if (!TargetRegisterInfo::isVirtualRegister(SrcReg))
2204 return std::make_pair(VNI, Reg);
2205
2206 const LiveInterval &LI = LIS->getInterval(SrcReg);
2207 const VNInfo *ValueIn;
2208 // No subrange involved.
2209 if (!SubRangeJoin || !LI.hasSubRanges()) {
2210 LiveQueryResult LRQ = LI.Query(Def);
2211 ValueIn = LRQ.valueIn();
2212 } else {
2213 // Query subranges. Pick the first matching one.
2214 ValueIn = nullptr;
2215 for (const LiveInterval::SubRange &S : LI.subranges()) {
2216 // Transform lanemask to a mask in the joined live interval.
2217 LaneBitmask SMask = TRI->composeSubRegIndexLaneMask(SubIdx, S.LaneMask);
2218 if ((SMask & LaneMask).none())
2219 continue;
2220 LiveQueryResult LRQ = S.Query(Def);
2221 ValueIn = LRQ.valueIn();
2222 break;
2223 }
2224 }
2225 if (ValueIn == nullptr)
2226 break;
2227 VNI = ValueIn;
2228 Reg = SrcReg;
2229 }
2230 return std::make_pair(VNI, Reg);
2231}
2232
2233bool JoinVals::valuesIdentical(VNInfo *Value0, VNInfo *Value1,
2234 const JoinVals &Other) const {
2235 const VNInfo *Orig0;
2236 unsigned Reg0;
2237 std::tie(Orig0, Reg0) = followCopyChain(Value0);
2238 if (Orig0 == Value1)
2239 return true;
2240
2241 const VNInfo *Orig1;
2242 unsigned Reg1;
2243 std::tie(Orig1, Reg1) = Other.followCopyChain(Value1);
2244
2245 // The values are equal if they are defined at the same place and use the
2246 // same register. Note that we cannot compare VNInfos directly as some of
2247 // them might be from a copy created in mergeSubRangeInto() while the other
2248 // is from the original LiveInterval.
2249 return Orig0->def == Orig1->def && Reg0 == Reg1;
2250}
2251
2252JoinVals::ConflictResolution
2253JoinVals::analyzeValue(unsigned ValNo, JoinVals &Other) {
2254 Val &V = Vals[ValNo];
2255 assert(!V.isAnalyzed() && "Value has already been analyzed!")(static_cast <bool> (!V.isAnalyzed() && "Value has already been analyzed!"
) ? void (0) : __assert_fail ("!V.isAnalyzed() && \"Value has already been analyzed!\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 2255, __extension__ __PRETTY_FUNCTION__))
;
2256 VNInfo *VNI = LR.getValNumInfo(ValNo);
2257 if (VNI->isUnused()) {
2258 V.WriteLanes = LaneBitmask::getAll();
2259 return CR_Keep;
2260 }
2261
2262 // Get the instruction defining this value, compute the lanes written.
2263 const MachineInstr *DefMI = nullptr;
2264 if (VNI->isPHIDef()) {
2265 // Conservatively assume that all lanes in a PHI are valid.
2266 LaneBitmask Lanes = SubRangeJoin ? LaneBitmask::getLane(0)
2267 : TRI->getSubRegIndexLaneMask(SubIdx);
2268 V.ValidLanes = V.WriteLanes = Lanes;
2269 } else {
2270 DefMI = Indexes->getInstructionFromIndex(VNI->def);
2271 assert(DefMI != nullptr)(static_cast <bool> (DefMI != nullptr) ? void (0) : __assert_fail
("DefMI != nullptr", "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 2271, __extension__ __PRETTY_FUNCTION__))
;
2272 if (SubRangeJoin) {
2273 // We don't care about the lanes when joining subregister ranges.
2274 V.WriteLanes = V.ValidLanes = LaneBitmask::getLane(0);
2275 if (DefMI->isImplicitDef()) {
2276 V.ValidLanes = LaneBitmask::getNone();
2277 V.ErasableImplicitDef = true;
2278 }
2279 } else {
2280 bool Redef = false;
2281 V.ValidLanes = V.WriteLanes = computeWriteLanes(DefMI, Redef);
2282
2283 // If this is a read-modify-write instruction, there may be more valid
2284 // lanes than the ones written by this instruction.
2285 // This only covers partial redef operands. DefMI may have normal use
2286 // operands reading the register. They don't contribute valid lanes.
2287 //
2288 // This adds ssub1 to the set of valid lanes in %src:
2289 //
2290 // %src:ssub1 = FOO
2291 //
2292 // This leaves only ssub1 valid, making any other lanes undef:
2293 //
2294 // %src:ssub1<def,read-undef> = FOO %src:ssub2
2295 //
2296 // The <read-undef> flag on the def operand means that old lane values are
2297 // not important.
2298 if (Redef) {
2299 V.RedefVNI = LR.Query(VNI->def).valueIn();
2300 assert((TrackSubRegLiveness || V.RedefVNI) &&(static_cast <bool> ((TrackSubRegLiveness || V.RedefVNI
) && "Instruction is reading nonexistent value") ? void
(0) : __assert_fail ("(TrackSubRegLiveness || V.RedefVNI) && \"Instruction is reading nonexistent value\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 2301, __extension__ __PRETTY_FUNCTION__))
2301 "Instruction is reading nonexistent value")(static_cast <bool> ((TrackSubRegLiveness || V.RedefVNI
) && "Instruction is reading nonexistent value") ? void
(0) : __assert_fail ("(TrackSubRegLiveness || V.RedefVNI) && \"Instruction is reading nonexistent value\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 2301, __extension__ __PRETTY_FUNCTION__))
;
2302 if (V.RedefVNI != nullptr) {
2303 computeAssignment(V.RedefVNI->id, Other);
2304 V.ValidLanes |= Vals[V.RedefVNI->id].ValidLanes;
2305 }
2306 }
2307
2308 // An IMPLICIT_DEF writes undef values.
2309 if (DefMI->isImplicitDef()) {
2310 // We normally expect IMPLICIT_DEF values to be live only until the end
2311 // of their block. If the value is really live longer and gets pruned in
2312 // another block, this flag is cleared again.
2313 V.ErasableImplicitDef = true;
2314 V.ValidLanes &= ~V.WriteLanes;
2315 }
2316 }
2317 }
2318
2319 // Find the value in Other that overlaps VNI->def, if any.
2320 LiveQueryResult OtherLRQ = Other.LR.Query(VNI->def);
2321
2322 // It is possible that both values are defined by the same instruction, or
2323 // the values are PHIs defined in the same block. When that happens, the two
2324 // values should be merged into one, but not into any preceding value.
2325 // The first value defined or visited gets CR_Keep, the other gets CR_Merge.
2326 if (VNInfo *OtherVNI = OtherLRQ.valueDefined()) {
2327 assert(SlotIndex::isSameInstr(VNI->def, OtherVNI->def) && "Broken LRQ")(static_cast <bool> (SlotIndex::isSameInstr(VNI->def
, OtherVNI->def) && "Broken LRQ") ? void (0) : __assert_fail
("SlotIndex::isSameInstr(VNI->def, OtherVNI->def) && \"Broken LRQ\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 2327, __extension__ __PRETTY_FUNCTION__))
;
2328
2329 // One value stays, the other is merged. Keep the earlier one, or the first
2330 // one we see.
2331 if (OtherVNI->def < VNI->def)
2332 Other.computeAssignment(OtherVNI->id, *this);
2333 else if (VNI->def < OtherVNI->def && OtherLRQ.valueIn()) {
2334 // This is an early-clobber def overlapping a live-in value in the other
2335 // register. Not mergeable.
2336 V.OtherVNI = OtherLRQ.valueIn();
2337 return CR_Impossible;
2338 }
2339 V.OtherVNI = OtherVNI;
2340 Val &OtherV = Other.Vals[OtherVNI->id];
2341 // Keep this value, check for conflicts when analyzing OtherVNI.
2342 if (!OtherV.isAnalyzed())
2343 return CR_Keep;
2344 // Both sides have been analyzed now.
2345 // Allow overlapping PHI values. Any real interference would show up in a
2346 // predecessor, the PHI itself can't introduce any conflicts.
2347 if (VNI->isPHIDef())
2348 return CR_Merge;
2349 if ((V.ValidLanes & OtherV.ValidLanes).any())
2350 // Overlapping lanes can't be resolved.
2351 return CR_Impossible;
2352 else
2353 return CR_Merge;
2354 }
2355
2356 // No simultaneous def. Is Other live at the def?
2357 V.OtherVNI = OtherLRQ.valueIn();
2358 if (!V.OtherVNI)
2359 // No overlap, no conflict.
2360 return CR_Keep;
2361
2362 assert(!SlotIndex::isSameInstr(VNI->def, V.OtherVNI->def) && "Broken LRQ")(static_cast <bool> (!SlotIndex::isSameInstr(VNI->def
, V.OtherVNI->def) && "Broken LRQ") ? void (0) : __assert_fail
("!SlotIndex::isSameInstr(VNI->def, V.OtherVNI->def) && \"Broken LRQ\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 2362, __extension__ __PRETTY_FUNCTION__))
;
2363
2364 // We have overlapping values, or possibly a kill of Other.
2365 // Recursively compute assignments up the dominator tree.
2366 Other.computeAssignment(V.OtherVNI->id, *this);
2367 Val &OtherV = Other.Vals[V.OtherVNI->id];
2368
2369 // Check if OtherV is an IMPLICIT_DEF that extends beyond its basic block.
2370 // This shouldn't normally happen, but ProcessImplicitDefs can leave such
2371 // IMPLICIT_DEF instructions behind, and there is nothing wrong with it
2372 // technically.
2373 //
2374 // When it happens, treat that IMPLICIT_DEF as a normal value, and don't try
2375 // to erase the IMPLICIT_DEF instruction.
2376 if (OtherV.ErasableImplicitDef && DefMI &&
2377 DefMI->getParent() != Indexes->getMBBFromIndex(V.OtherVNI->def)) {
2378 DEBUG(dbgs() << "IMPLICIT_DEF defined at " << V.OtherVNI->defdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "IMPLICIT_DEF defined at " <<
V.OtherVNI->def << " extends into " << printMBBReference
(*DefMI->getParent()) << ", keeping it.\n"; } } while
(false)
2379 << " extends into " << printMBBReference(*DefMI->getParent())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "IMPLICIT_DEF defined at " <<
V.OtherVNI->def << " extends into " << printMBBReference
(*DefMI->getParent()) << ", keeping it.\n"; } } while
(false)
2380 << ", keeping it.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "IMPLICIT_DEF defined at " <<
V.OtherVNI->def << " extends into " << printMBBReference
(*DefMI->getParent()) << ", keeping it.\n"; } } while
(false)
;
2381 OtherV.ErasableImplicitDef = false;
2382 }
2383
2384 // Allow overlapping PHI values. Any real interference would show up in a
2385 // predecessor, the PHI itself can't introduce any conflicts.
2386 if (VNI->isPHIDef())
2387 return CR_Replace;
2388
2389 // Check for simple erasable conflicts.
2390 if (DefMI->isImplicitDef()) {
2391 // We need the def for the subregister if there is nothing else live at the
2392 // subrange at this point.
2393 if (TrackSubRegLiveness
2394 && (V.WriteLanes & (OtherV.ValidLanes | OtherV.WriteLanes)).none())
2395 return CR_Replace;
2396 return CR_Erase;
2397 }
2398
2399 // Include the non-conflict where DefMI is a coalescable copy that kills
2400 // OtherVNI. We still want the copy erased and value numbers merged.
2401 if (CP.isCoalescable(DefMI)) {
2402 // Some of the lanes copied from OtherVNI may be undef, making them undef
2403 // here too.
2404 V.ValidLanes &= ~V.WriteLanes | OtherV.ValidLanes;
2405 return CR_Erase;
2406 }
2407
2408 // This may not be a real conflict if DefMI simply kills Other and defines
2409 // VNI.
2410 if (OtherLRQ.isKill() && OtherLRQ.endPoint() <= VNI->def)
2411 return CR_Keep;
2412
2413 // Handle the case where VNI and OtherVNI can be proven to be identical:
2414 //
2415 // %other = COPY %ext
2416 // %this = COPY %ext <-- Erase this copy
2417 //
2418 if (DefMI->isFullCopy() && !CP.isPartial()
2419 && valuesIdentical(VNI, V.OtherVNI, Other))
2420 return CR_Erase;
2421
2422 // If the lanes written by this instruction were all undef in OtherVNI, it is
2423 // still safe to join the live ranges. This can't be done with a simple value
2424 // mapping, though - OtherVNI will map to multiple values:
2425 //
2426 // 1 %dst:ssub0 = FOO <-- OtherVNI
2427 // 2 %src = BAR <-- VNI
2428 // 3 %dst:ssub1 = COPY killed %src <-- Eliminate this copy.
2429 // 4 BAZ killed %dst
2430 // 5 QUUX killed %src
2431 //
2432 // Here OtherVNI will map to itself in [1;2), but to VNI in [2;5). CR_Replace
2433 // handles this complex value mapping.
2434 if ((V.WriteLanes & OtherV.ValidLanes).none())
2435 return CR_Replace;
2436
2437 // If the other live range is killed by DefMI and the live ranges are still
2438 // overlapping, it must be because we're looking at an early clobber def:
2439 //
2440 // %dst<def,early-clobber> = ASM killed %src
2441 //
2442 // In this case, it is illegal to merge the two live ranges since the early
2443 // clobber def would clobber %src before it was read.
2444 if (OtherLRQ.isKill()) {
2445 // This case where the def doesn't overlap the kill is handled above.
2446 assert(VNI->def.isEarlyClobber() &&(static_cast <bool> (VNI->def.isEarlyClobber() &&
"Only early clobber defs can overlap a kill") ? void (0) : __assert_fail
("VNI->def.isEarlyClobber() && \"Only early clobber defs can overlap a kill\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 2447, __extension__ __PRETTY_FUNCTION__))
2447 "Only early clobber defs can overlap a kill")(static_cast <bool> (VNI->def.isEarlyClobber() &&
"Only early clobber defs can overlap a kill") ? void (0) : __assert_fail
("VNI->def.isEarlyClobber() && \"Only early clobber defs can overlap a kill\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 2447, __extension__ __PRETTY_FUNCTION__))
;
2448 return CR_Impossible;
2449 }
2450
2451 // VNI is clobbering live lanes in OtherVNI, but there is still the
2452 // possibility that no instructions actually read the clobbered lanes.
2453 // If we're clobbering all the lanes in OtherVNI, at least one must be read.
2454 // Otherwise Other.RI wouldn't be live here.
2455 if ((TRI->getSubRegIndexLaneMask(Other.SubIdx) & ~V.WriteLanes).none())
2456 return CR_Impossible;
2457
2458 // We need to verify that no instructions are reading the clobbered lanes. To
2459 // save compile time, we'll only check that locally. Don't allow the tainted
2460 // value to escape the basic block.
2461 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def);
2462 if (OtherLRQ.endPoint() >= Indexes->getMBBEndIdx(MBB))
2463 return CR_Impossible;
2464
2465 // There are still some things that could go wrong besides clobbered lanes
2466 // being read, for example OtherVNI may be only partially redefined in MBB,
2467 // and some clobbered lanes could escape the block. Save this analysis for
2468 // resolveConflicts() when all values have been mapped. We need to know
2469 // RedefVNI and WriteLanes for any later defs in MBB, and we can't compute
2470 // that now - the recursive analyzeValue() calls must go upwards in the
2471 // dominator tree.
2472 return CR_Unresolved;
2473}
2474
2475void JoinVals::computeAssignment(unsigned ValNo, JoinVals &Other) {
2476 Val &V = Vals[ValNo];
2477 if (V.isAnalyzed()) {
2478 // Recursion should always move up the dominator tree, so ValNo is not
2479 // supposed to reappear before it has been assigned.
2480 assert(Assignments[ValNo] != -1 && "Bad recursion?")(static_cast <bool> (Assignments[ValNo] != -1 &&
"Bad recursion?") ? void (0) : __assert_fail ("Assignments[ValNo] != -1 && \"Bad recursion?\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 2480, __extension__ __PRETTY_FUNCTION__))
;
2481 return;
2482 }
2483 switch ((V.Resolution = analyzeValue(ValNo, Other))) {
2484 case CR_Erase:
2485 case CR_Merge:
2486 // Merge this ValNo into OtherVNI.
2487 assert(V.OtherVNI && "OtherVNI not assigned, can't merge.")(static_cast <bool> (V.OtherVNI && "OtherVNI not assigned, can't merge."
) ? void (0) : __assert_fail ("V.OtherVNI && \"OtherVNI not assigned, can't merge.\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 2487, __extension__ __PRETTY_FUNCTION__))
;
2488 assert(Other.Vals[V.OtherVNI->id].isAnalyzed() && "Missing recursion")(static_cast <bool> (Other.Vals[V.OtherVNI->id].isAnalyzed
() && "Missing recursion") ? void (0) : __assert_fail
("Other.Vals[V.OtherVNI->id].isAnalyzed() && \"Missing recursion\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 2488, __extension__ __PRETTY_FUNCTION__))
;
2489 Assignments[ValNo] = Other.Assignments[V.OtherVNI->id];
2490 DEBUG(dbgs() << "\t\tmerge " << printReg(Reg) << ':' << ValNo << '@'do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tmerge " << printReg
(Reg) << ':' << ValNo << '@' << LR.getValNumInfo
(ValNo)->def << " into " << printReg(Other.Reg
) << ':' << V.OtherVNI->id << '@' <<
V.OtherVNI->def << " --> @" << NewVNInfo[Assignments
[ValNo]]->def << '\n'; } } while (false)
2491 << LR.getValNumInfo(ValNo)->def << " into "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tmerge " << printReg
(Reg) << ':' << ValNo << '@' << LR.getValNumInfo
(ValNo)->def << " into " << printReg(Other.Reg
) << ':' << V.OtherVNI->id << '@' <<
V.OtherVNI->def << " --> @" << NewVNInfo[Assignments
[ValNo]]->def << '\n'; } } while (false)
2492 << printReg(Other.Reg) << ':' << V.OtherVNI->id << '@'do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tmerge " << printReg
(Reg) << ':' << ValNo << '@' << LR.getValNumInfo
(ValNo)->def << " into " << printReg(Other.Reg
) << ':' << V.OtherVNI->id << '@' <<
V.OtherVNI->def << " --> @" << NewVNInfo[Assignments
[ValNo]]->def << '\n'; } } while (false)
2493 << V.OtherVNI->def << " --> @"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tmerge " << printReg
(Reg) << ':' << ValNo << '@' << LR.getValNumInfo
(ValNo)->def << " into " << printReg(Other.Reg
) << ':' << V.OtherVNI->id << '@' <<
V.OtherVNI->def << " --> @" << NewVNInfo[Assignments
[ValNo]]->def << '\n'; } } while (false)
2494 << NewVNInfo[Assignments[ValNo]]->def << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tmerge " << printReg
(Reg) << ':' << ValNo << '@' << LR.getValNumInfo
(ValNo)->def << " into " << printReg(Other.Reg
) << ':' << V.OtherVNI->id << '@' <<
V.OtherVNI->def << " --> @" << NewVNInfo[Assignments
[ValNo]]->def << '\n'; } } while (false)
;
2495 break;
2496 case CR_Replace:
2497 case CR_Unresolved: {
2498 // The other value is going to be pruned if this join is successful.
2499 assert(V.OtherVNI && "OtherVNI not assigned, can't prune")(static_cast <bool> (V.OtherVNI && "OtherVNI not assigned, can't prune"
) ? void (0) : __assert_fail ("V.OtherVNI && \"OtherVNI not assigned, can't prune\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 2499, __extension__ __PRETTY_FUNCTION__))
;
2500 Val &OtherV = Other.Vals[V.OtherVNI->id];
2501 // We cannot erase an IMPLICIT_DEF if we don't have valid values for all
2502 // its lanes.
2503 if ((OtherV.WriteLanes & ~V.ValidLanes).any() && TrackSubRegLiveness)
2504 OtherV.ErasableImplicitDef = false;
2505 OtherV.Pruned = true;
2506 LLVM_FALLTHROUGH[[clang::fallthrough]];
2507 }
2508 default:
2509 // This value number needs to go in the final joined live range.
2510 Assignments[ValNo] = NewVNInfo.size();
2511 NewVNInfo.push_back(LR.getValNumInfo(ValNo));
2512 break;
2513 }
2514}
2515
2516bool JoinVals::mapValues(JoinVals &Other) {
2517 for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
2518 computeAssignment(i, Other);
2519 if (Vals[i].Resolution == CR_Impossible) {
2520 DEBUG(dbgs() << "\t\tinterference at " << printReg(Reg) << ':' << ido { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tinterference at " <<
printReg(Reg) << ':' << i << '@' << LR
.getValNumInfo(i)->def << '\n'; } } while (false)
2521 << '@' << LR.getValNumInfo(i)->def << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tinterference at " <<
printReg(Reg) << ':' << i << '@' << LR
.getValNumInfo(i)->def << '\n'; } } while (false)
;
2522 return false;
2523 }
2524 }
2525 return true;
2526}
2527
2528bool JoinVals::
2529taintExtent(unsigned ValNo, LaneBitmask TaintedLanes, JoinVals &Other,
2530 SmallVectorImpl<std::pair<SlotIndex, LaneBitmask>> &TaintExtent) {
2531 VNInfo *VNI = LR.getValNumInfo(ValNo);
2532 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def);
2533 SlotIndex MBBEnd = Indexes->getMBBEndIdx(MBB);
2534
2535 // Scan Other.LR from VNI.def to MBBEnd.
2536 LiveInterval::iterator OtherI = Other.LR.find(VNI->def);
2537 assert(OtherI != Other.LR.end() && "No conflict?")(static_cast <bool> (OtherI != Other.LR.end() &&
"No conflict?") ? void (0) : __assert_fail ("OtherI != Other.LR.end() && \"No conflict?\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 2537, __extension__ __PRETTY_FUNCTION__))
;
2538 do {
2539 // OtherI is pointing to a tainted value. Abort the join if the tainted
2540 // lanes escape the block.
2541 SlotIndex End = OtherI->end;
2542 if (End >= MBBEnd) {
2543 DEBUG(dbgs() << "\t\ttaints global " << printReg(Other.Reg) << ':'do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\ttaints global " <<
printReg(Other.Reg) << ':' << OtherI->valno->
id << '@' << OtherI->start << '\n'; } } while
(false)
2544 << OtherI->valno->id << '@' << OtherI->start << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\ttaints global " <<
printReg(Other.Reg) << ':' << OtherI->valno->
id << '@' << OtherI->start << '\n'; } } while
(false)
;
2545 return false;
2546 }
2547 DEBUG(dbgs() << "\t\ttaints local " << printReg(Other.Reg) << ':'do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\ttaints local " << printReg
(Other.Reg) << ':' << OtherI->valno->id <<
'@' << OtherI->start << " to " << End <<
'\n'; } } while (false)
2548 << OtherI->valno->id << '@' << OtherI->startdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\ttaints local " << printReg
(Other.Reg) << ':' << OtherI->valno->id <<
'@' << OtherI->start << " to " << End <<
'\n'; } } while (false)
2549 << " to " << End << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\ttaints local " << printReg
(Other.Reg) << ':' << OtherI->valno->id <<
'@' << OtherI->start << " to " << End <<
'\n'; } } while (false)
;
2550 // A dead def is not a problem.
2551 if (End.isDead())
2552 break;
2553 TaintExtent.push_back(std::make_pair(End, TaintedLanes));
2554
2555 // Check for another def in the MBB.
2556 if (++OtherI == Other.LR.end() || OtherI->start >= MBBEnd)
2557 break;
2558
2559 // Lanes written by the new def are no longer tainted.
2560 const Val &OV = Other.Vals[OtherI->valno->id];
2561 TaintedLanes &= ~OV.WriteLanes;
2562 if (!OV.RedefVNI)
2563 break;
2564 } while (TaintedLanes.any());
2565 return true;
2566}
2567
2568bool JoinVals::usesLanes(const MachineInstr &MI, unsigned Reg, unsigned SubIdx,
2569 LaneBitmask Lanes) const {
2570 if (MI.isDebugValue())
2571 return false;
2572 for (const MachineOperand &MO : MI.operands()) {
2573 if (!MO.isReg() || MO.isDef() || MO.getReg() != Reg)
2574 continue;
2575 if (!MO.readsReg())
2576 continue;
2577 unsigned S = TRI->composeSubRegIndices(SubIdx, MO.getSubReg());
2578 if ((Lanes & TRI->getSubRegIndexLaneMask(S)).any())
2579 return true;
2580 }
2581 return false;
2582}
2583
2584bool JoinVals::resolveConflicts(JoinVals &Other) {
2585 for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
2586 Val &V = Vals[i];
2587 assert(V.Resolution != CR_Impossible && "Unresolvable conflict")(static_cast <bool> (V.Resolution != CR_Impossible &&
"Unresolvable conflict") ? void (0) : __assert_fail ("V.Resolution != CR_Impossible && \"Unresolvable conflict\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 2587, __extension__ __PRETTY_FUNCTION__))
;
2588 if (V.Resolution != CR_Unresolved)
2589 continue;
2590 DEBUG(dbgs() << "\t\tconflict at " << printReg(Reg) << ':' << ido { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tconflict at " << printReg
(Reg) << ':' << i << '@' << LR.getValNumInfo
(i)->def << '\n'; } } while (false)
2591 << '@' << LR.getValNumInfo(i)->def << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tconflict at " << printReg
(Reg) << ':' << i << '@' << LR.getValNumInfo
(i)->def << '\n'; } } while (false)
;
2592 if (SubRangeJoin)
2593 return false;
2594
2595 ++NumLaneConflicts;
2596 assert(V.OtherVNI && "Inconsistent conflict resolution.")(static_cast <bool> (V.OtherVNI && "Inconsistent conflict resolution."
) ? void (0) : __assert_fail ("V.OtherVNI && \"Inconsistent conflict resolution.\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 2596, __extension__ __PRETTY_FUNCTION__))
;
2597 VNInfo *VNI = LR.getValNumInfo(i);
2598 const Val &OtherV = Other.Vals[V.OtherVNI->id];
2599
2600 // VNI is known to clobber some lanes in OtherVNI. If we go ahead with the
2601 // join, those lanes will be tainted with a wrong value. Get the extent of
2602 // the tainted lanes.
2603 LaneBitmask TaintedLanes = V.WriteLanes & OtherV.ValidLanes;
2604 SmallVector<std::pair<SlotIndex, LaneBitmask>, 8> TaintExtent;
2605 if (!taintExtent(i, TaintedLanes, Other, TaintExtent))
2606 // Tainted lanes would extend beyond the basic block.
2607 return false;
2608
2609 assert(!TaintExtent.empty() && "There should be at least one conflict.")(static_cast <bool> (!TaintExtent.empty() && "There should be at least one conflict."
) ? void (0) : __assert_fail ("!TaintExtent.empty() && \"There should be at least one conflict.\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 2609, __extension__ __PRETTY_FUNCTION__))
;
2610
2611 // Now look at the instructions from VNI->def to TaintExtent (inclusive).
2612 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def);
2613 MachineBasicBlock::iterator MI = MBB->begin();
2614 if (!VNI->isPHIDef()) {
2615 MI = Indexes->getInstructionFromIndex(VNI->def);
2616 // No need to check the instruction defining VNI for reads.
2617 ++MI;
2618 }
2619 assert(!SlotIndex::isSameInstr(VNI->def, TaintExtent.front().first) &&(static_cast <bool> (!SlotIndex::isSameInstr(VNI->def
, TaintExtent.front().first) && "Interference ends on VNI->def. Should have been handled earlier"
) ? void (0) : __assert_fail ("!SlotIndex::isSameInstr(VNI->def, TaintExtent.front().first) && \"Interference ends on VNI->def. Should have been handled earlier\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 2620, __extension__ __PRETTY_FUNCTION__))
2620 "Interference ends on VNI->def. Should have been handled earlier")(static_cast <bool> (!SlotIndex::isSameInstr(VNI->def
, TaintExtent.front().first) && "Interference ends on VNI->def. Should have been handled earlier"
) ? void (0) : __assert_fail ("!SlotIndex::isSameInstr(VNI->def, TaintExtent.front().first) && \"Interference ends on VNI->def. Should have been handled earlier\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 2620, __extension__ __PRETTY_FUNCTION__))
;
2621 MachineInstr *LastMI =
2622 Indexes->getInstructionFromIndex(TaintExtent.front().first);
2623 assert(LastMI && "Range must end at a proper instruction")(static_cast <bool> (LastMI && "Range must end at a proper instruction"
) ? void (0) : __assert_fail ("LastMI && \"Range must end at a proper instruction\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 2623, __extension__ __PRETTY_FUNCTION__))
;
2624 unsigned TaintNum = 0;
2625 while (true) {
2626 assert(MI != MBB->end() && "Bad LastMI")(static_cast <bool> (MI != MBB->end() && "Bad LastMI"
) ? void (0) : __assert_fail ("MI != MBB->end() && \"Bad LastMI\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 2626, __extension__ __PRETTY_FUNCTION__))
;
2627 if (usesLanes(*MI, Other.Reg, Other.SubIdx, TaintedLanes)) {
2628 DEBUG(dbgs() << "\t\ttainted lanes used by: " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\ttainted lanes used by: "
<< *MI; } } while (false)
;
2629 return false;
2630 }
2631 // LastMI is the last instruction to use the current value.
2632 if (&*MI == LastMI) {
2633 if (++TaintNum == TaintExtent.size())
2634 break;
2635 LastMI = Indexes->getInstructionFromIndex(TaintExtent[TaintNum].first);
2636 assert(LastMI && "Range must end at a proper instruction")(static_cast <bool> (LastMI && "Range must end at a proper instruction"
) ? void (0) : __assert_fail ("LastMI && \"Range must end at a proper instruction\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 2636, __extension__ __PRETTY_FUNCTION__))
;
2637 TaintedLanes = TaintExtent[TaintNum].second;
2638 }
2639 ++MI;
2640 }
2641
2642 // The tainted lanes are unused.
2643 V.Resolution = CR_Replace;
2644 ++NumLaneResolves;
2645 }
2646 return true;
2647}
2648
2649bool JoinVals::isPrunedValue(unsigned ValNo, JoinVals &Other) {
2650 Val &V = Vals[ValNo];
2651 if (V.Pruned || V.PrunedComputed)
2652 return V.Pruned;
2653
2654 if (V.Resolution != CR_Erase && V.Resolution != CR_Merge)
2655 return V.Pruned;
2656
2657 // Follow copies up the dominator tree and check if any intermediate value
2658 // has been pruned.
2659 V.PrunedComputed = true;
2660 V.Pruned = Other.isPrunedValue(V.OtherVNI->id, *this);
2661 return V.Pruned;
2662}
2663
2664void JoinVals::pruneValues(JoinVals &Other,
2665 SmallVectorImpl<SlotIndex> &EndPoints,
2666 bool changeInstrs) {
2667 for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
2668 SlotIndex Def = LR.getValNumInfo(i)->def;
2669 switch (Vals[i].Resolution) {
2670 case CR_Keep:
2671 break;
2672 case CR_Replace: {
2673 // This value takes precedence over the value in Other.LR.
2674 LIS->pruneValue(Other.LR, Def, &EndPoints);
2675 // Check if we're replacing an IMPLICIT_DEF value. The IMPLICIT_DEF
2676 // instructions are only inserted to provide a live-out value for PHI
2677 // predecessors, so the instruction should simply go away once its value
2678 // has been replaced.
2679 Val &OtherV = Other.Vals[Vals[i].OtherVNI->id];
2680 bool EraseImpDef = OtherV.ErasableImplicitDef &&
2681 OtherV.Resolution == CR_Keep;
2682 if (!Def.isBlock()) {
2683 if (changeInstrs) {
2684 // Remove <def,read-undef> flags. This def is now a partial redef.
2685 // Also remove dead flags since the joined live range will
2686 // continue past this instruction.
2687 for (MachineOperand &MO :
2688 Indexes->getInstructionFromIndex(Def)->operands()) {
2689 if (MO.isReg() && MO.isDef() && MO.getReg() == Reg) {
2690 if (MO.getSubReg() != 0 && MO.isUndef() && !EraseImpDef)
2691 MO.setIsUndef(false);
2692 MO.setIsDead(false);
2693 }
2694 }
2695 }
2696 // This value will reach instructions below, but we need to make sure
2697 // the live range also reaches the instruction at Def.
2698 if (!EraseImpDef)
2699 EndPoints.push_back(Def);
2700 }
2701 DEBUG(dbgs() << "\t\tpruned " << printReg(Other.Reg) << " at " << Defdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tpruned " << printReg
(Other.Reg) << " at " << Def << ": " <<
Other.LR << '\n'; } } while (false)
2702 << ": " << Other.LR << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tpruned " << printReg
(Other.Reg) << " at " << Def << ": " <<
Other.LR << '\n'; } } while (false)
;
2703 break;
2704 }
2705 case CR_Erase:
2706 case CR_Merge:
2707 if (isPrunedValue(i, Other)) {
2708 // This value is ultimately a copy of a pruned value in LR or Other.LR.
2709 // We can no longer trust the value mapping computed by
2710 // computeAssignment(), the value that was originally copied could have
2711 // been replaced.
2712 LIS->pruneValue(LR, Def, &EndPoints);
2713 DEBUG(dbgs() << "\t\tpruned all of " << printReg(Reg) << " at "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tpruned all of " <<
printReg(Reg) << " at " << Def << ": " <<
LR << '\n'; } } while (false)
2714 << Def << ": " << LR << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tpruned all of " <<
printReg(Reg) << " at " << Def << ": " <<
LR << '\n'; } } while (false)
;
2715 }
2716 break;
2717 case CR_Unresolved:
2718 case CR_Impossible:
2719 llvm_unreachable("Unresolved conflicts")::llvm::llvm_unreachable_internal("Unresolved conflicts", "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 2719)
;
2720 }
2721 }
2722}
2723
2724void JoinVals::pruneSubRegValues(LiveInterval &LI, LaneBitmask &ShrinkMask) {
2725 // Look for values being erased.
2726 bool DidPrune = false;
2727 for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
2728 // We should trigger in all cases in which eraseInstrs() does something.
2729 // match what eraseInstrs() is doing, print a message so
2730 if (Vals[i].Resolution != CR_Erase &&
2731 (Vals[i].Resolution != CR_Keep || !Vals[i].ErasableImplicitDef ||
2732 !Vals[i].Pruned))
2733 continue;
2734
2735 // Check subranges at the point where the copy will be removed.
2736 SlotIndex Def = LR.getValNumInfo(i)->def;
2737 // Print message so mismatches with eraseInstrs() can be diagnosed.
2738 DEBUG(dbgs() << "\t\tExpecting instruction removal at " << Def << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tExpecting instruction removal at "
<< Def << '\n'; } } while (false)
;
2739 for (LiveInterval::SubRange &S : LI.subranges()) {
2740 LiveQueryResult Q = S.Query(Def);
2741
2742 // If a subrange starts at the copy then an undefined value has been
2743 // copied and we must remove that subrange value as well.
2744 VNInfo *ValueOut = Q.valueOutOrDead();
2745 if (ValueOut != nullptr && Q.valueIn() == nullptr) {
2746 DEBUG(dbgs() << "\t\tPrune sublane " << PrintLaneMask(S.LaneMask)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tPrune sublane " <<
PrintLaneMask(S.LaneMask) << " at " << Def <<
"\n"; } } while (false)
2747 << " at " << Def << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tPrune sublane " <<
PrintLaneMask(S.LaneMask) << " at " << Def <<
"\n"; } } while (false)
;
2748 LIS->pruneValue(S, Def, nullptr);
2749 DidPrune = true;
2750 // Mark value number as unused.
2751 ValueOut->markUnused();
2752 continue;
2753 }
2754 // If a subrange ends at the copy, then a value was copied but only
2755 // partially used later. Shrink the subregister range appropriately.
2756 if (Q.valueIn() != nullptr && Q.valueOut() == nullptr) {
2757 DEBUG(dbgs() << "\t\tDead uses at sublane " << PrintLaneMask(S.LaneMask)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tDead uses at sublane " <<
PrintLaneMask(S.LaneMask) << " at " << Def <<
"\n"; } } while (false)
2758 << " at " << Def << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tDead uses at sublane " <<
PrintLaneMask(S.LaneMask) << " at " << Def <<
"\n"; } } while (false)
;
2759 ShrinkMask |= S.LaneMask;
2760 }
2761 }
2762 }
2763 if (DidPrune)
2764 LI.removeEmptySubRanges();
2765}
2766
2767/// Check if any of the subranges of @p LI contain a definition at @p Def.
2768static bool isDefInSubRange(LiveInterval &LI, SlotIndex Def) {
2769 for (LiveInterval::SubRange &SR : LI.subranges()) {
2770 if (VNInfo *VNI = SR.Query(Def).valueOutOrDead())
2771 if (VNI->def == Def)
2772 return true;
2773 }
2774 return false;
2775}
2776
2777void JoinVals::pruneMainSegments(LiveInterval &LI, bool &ShrinkMainRange) {
2778 assert(&static_cast<LiveRange&>(LI) == &LR)(static_cast <bool> (&static_cast<LiveRange&
>(LI) == &LR) ? void (0) : __assert_fail ("&static_cast<LiveRange&>(LI) == &LR"
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 2778, __extension__ __PRETTY_FUNCTION__))
;
2779
2780 for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
2781 if (Vals[i].Resolution != CR_Keep)
2782 continue;
2783 VNInfo *VNI = LR.getValNumInfo(i);
2784 if (VNI->isUnused() || VNI->isPHIDef() || isDefInSubRange(LI, VNI->def))
2785 continue;
2786 Vals[i].Pruned = true;
2787 ShrinkMainRange = true;
2788 }
2789}
2790
2791void JoinVals::removeImplicitDefs() {
2792 for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
2793 Val &V = Vals[i];
2794 if (V.Resolution != CR_Keep || !V.ErasableImplicitDef || !V.Pruned)
2795 continue;
2796
2797 VNInfo *VNI = LR.getValNumInfo(i);
2798 VNI->markUnused();
2799 LR.removeValNo(VNI);
2800 }
2801}
2802
2803void JoinVals::eraseInstrs(SmallPtrSetImpl<MachineInstr*> &ErasedInstrs,
2804 SmallVectorImpl<unsigned> &ShrinkRegs,
2805 LiveInterval *LI) {
2806 for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
2807 // Get the def location before markUnused() below invalidates it.
2808 SlotIndex Def = LR.getValNumInfo(i)->def;
2809 switch (Vals[i].Resolution) {
2810 case CR_Keep: {
2811 // If an IMPLICIT_DEF value is pruned, it doesn't serve a purpose any
2812 // longer. The IMPLICIT_DEF instructions are only inserted by
2813 // PHIElimination to guarantee that all PHI predecessors have a value.
2814 if (!Vals[i].ErasableImplicitDef || !Vals[i].Pruned)
2815 break;
2816 // Remove value number i from LR.
2817 // For intervals with subranges, removing a segment from the main range
2818 // may require extending the previous segment: for each definition of
2819 // a subregister, there will be a corresponding def in the main range.
2820 // That def may fall in the middle of a segment from another subrange.
2821 // In such cases, removing this def from the main range must be
2822 // complemented by extending the main range to account for the liveness
2823 // of the other subrange.
2824 VNInfo *VNI = LR.getValNumInfo(i);
2825 SlotIndex Def = VNI->def;
2826 // The new end point of the main range segment to be extended.
2827 SlotIndex NewEnd;
2828 if (LI != nullptr) {
2829 LiveRange::iterator I = LR.FindSegmentContaining(Def);
2830 assert(I != LR.end())(static_cast <bool> (I != LR.end()) ? void (0) : __assert_fail
("I != LR.end()", "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 2830, __extension__ __PRETTY_FUNCTION__))
;
2831 // Do not extend beyond the end of the segment being removed.
2832 // The segment may have been pruned in preparation for joining
2833 // live ranges.
2834 NewEnd = I->end;
2835 }
2836
2837 LR.removeValNo(VNI);
2838 // Note that this VNInfo is reused and still referenced in NewVNInfo,
2839 // make it appear like an unused value number.
2840 VNI->markUnused();
2841
2842 if (LI != nullptr && LI->hasSubRanges()) {
2843 assert(static_cast<LiveRange*>(LI) == &LR)(static_cast <bool> (static_cast<LiveRange*>(LI) ==
&LR) ? void (0) : __assert_fail ("static_cast<LiveRange*>(LI) == &LR"
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 2843, __extension__ __PRETTY_FUNCTION__))
;
2844 // Determine the end point based on the subrange information:
2845 // minimum of (earliest def of next segment,
2846 // latest end point of containing segment)
2847 SlotIndex ED, LE;
2848 for (LiveInterval::SubRange &SR : LI->subranges()) {
2849 LiveRange::iterator I = SR.find(Def);
2850 if (I == SR.end())
2851 continue;
2852 if (I->start > Def)
2853 ED = ED.isValid() ? std::min(ED, I->start) : I->start;
2854 else
2855 LE = LE.isValid() ? std::max(LE, I->end) : I->end;
2856 }
2857 if (LE.isValid())
2858 NewEnd = std::min(NewEnd, LE);
2859 if (ED.isValid())
2860 NewEnd = std::min(NewEnd, ED);
2861
2862 // We only want to do the extension if there was a subrange that
2863 // was live across Def.
2864 if (LE.isValid()) {
2865 LiveRange::iterator S = LR.find(Def);
2866 if (S != LR.begin())
2867 std::prev(S)->end = NewEnd;
2868 }
2869 }
2870 DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\tremoved " << i <<
'@' << Def << ": " << LR << '\n'; if
(LI != nullptr) dbgs() << "\t\t LHS = " << *LI <<
'\n'; }; } } while (false)
2871 dbgs() << "\t\tremoved " << i << '@' << Def << ": " << LR << '\n';do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\tremoved " << i <<
'@' << Def << ": " << LR << '\n'; if
(LI != nullptr) dbgs() << "\t\t LHS = " << *LI <<
'\n'; }; } } while (false)
2872 if (LI != nullptr)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\tremoved " << i <<
'@' << Def << ": " << LR << '\n'; if
(LI != nullptr) dbgs() << "\t\t LHS = " << *LI <<
'\n'; }; } } while (false)
2873 dbgs() << "\t\t LHS = " << *LI << '\n';do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\tremoved " << i <<
'@' << Def << ": " << LR << '\n'; if
(LI != nullptr) dbgs() << "\t\t LHS = " << *LI <<
'\n'; }; } } while (false)
2874 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\tremoved " << i <<
'@' << Def << ": " << LR << '\n'; if
(LI != nullptr) dbgs() << "\t\t LHS = " << *LI <<
'\n'; }; } } while (false)
;
2875 LLVM_FALLTHROUGH[[clang::fallthrough]];
2876 }
2877
2878 case CR_Erase: {
2879 MachineInstr *MI = Indexes->getInstructionFromIndex(Def);
2880 assert(MI && "No instruction to erase")(static_cast <bool> (MI && "No instruction to erase"
) ? void (0) : __assert_fail ("MI && \"No instruction to erase\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 2880, __extension__ __PRETTY_FUNCTION__))
;
2881 if (MI->isCopy()) {
2882 unsigned Reg = MI->getOperand(1).getReg();
2883 if (TargetRegisterInfo::isVirtualRegister(Reg) &&
2884 Reg != CP.getSrcReg() && Reg != CP.getDstReg())
2885 ShrinkRegs.push_back(Reg);
2886 }
2887 ErasedInstrs.insert(MI);
2888 DEBUG(dbgs() << "\t\terased:\t" << Def << '\t' << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\terased:\t" << Def <<
'\t' << *MI; } } while (false)
;
2889 LIS->RemoveMachineInstrFromMaps(*MI);
2890 MI->eraseFromParent();
2891 break;
2892 }
2893 default:
2894 break;
2895 }
2896 }
2897}
2898
2899void RegisterCoalescer::joinSubRegRanges(LiveRange &LRange, LiveRange &RRange,
2900 LaneBitmask LaneMask,
2901 const CoalescerPair &CP) {
2902 SmallVector<VNInfo*, 16> NewVNInfo;
2903 JoinVals RHSVals(RRange, CP.getSrcReg(), CP.getSrcIdx(), LaneMask,
2904 NewVNInfo, CP, LIS, TRI, true, true);
2905 JoinVals LHSVals(LRange, CP.getDstReg(), CP.getDstIdx(), LaneMask,
2906 NewVNInfo, CP, LIS, TRI, true, true);
2907
2908 // Compute NewVNInfo and resolve conflicts (see also joinVirtRegs())
2909 // We should be able to resolve all conflicts here as we could successfully do
2910 // it on the mainrange already. There is however a problem when multiple
2911 // ranges get mapped to the "overflow" lane mask bit which creates unexpected
2912 // interferences.
2913 if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals)) {
2914 // We already determined that it is legal to merge the intervals, so this
2915 // should never fail.
2916 llvm_unreachable("*** Couldn't join subrange!\n")::llvm::llvm_unreachable_internal("*** Couldn't join subrange!\n"
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 2916)
;
2917 }
2918 if (!LHSVals.resolveConflicts(RHSVals) ||
2919 !RHSVals.resolveConflicts(LHSVals)) {
2920 // We already determined that it is legal to merge the intervals, so this
2921 // should never fail.
2922 llvm_unreachable("*** Couldn't join subrange!\n")::llvm::llvm_unreachable_internal("*** Couldn't join subrange!\n"
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 2922)
;
2923 }
2924
2925 // The merging algorithm in LiveInterval::join() can't handle conflicting
2926 // value mappings, so we need to remove any live ranges that overlap a
2927 // CR_Replace resolution. Collect a set of end points that can be used to
2928 // restore the live range after joining.
2929 SmallVector<SlotIndex, 8> EndPoints;
2930 LHSVals.pruneValues(RHSVals, EndPoints, false);
2931 RHSVals.pruneValues(LHSVals, EndPoints, false);
2932
2933 LHSVals.removeImplicitDefs();
2934 RHSVals.removeImplicitDefs();
2935
2936 LRange.verify();
2937 RRange.verify();
2938
2939 // Join RRange into LHS.
2940 LRange.join(RRange, LHSVals.getAssignments(), RHSVals.getAssignments(),
2941 NewVNInfo);
2942
2943 DEBUG(dbgs() << "\t\tjoined lanes: " << LRange << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tjoined lanes: " <<
LRange << "\n"; } } while (false)
;
2944 if (EndPoints.empty())
2945 return;
2946
2947 // Recompute the parts of the live range we had to remove because of
2948 // CR_Replace conflicts.
2949 DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\trestoring liveness to "
<< EndPoints.size() << " points: "; for (unsigned
i = 0, n = EndPoints.size(); i != n; ++i) { dbgs() << EndPoints
[i]; if (i != n-1) dbgs() << ','; } dbgs() << ": "
<< LRange << '\n'; }; } } while (false)
2950 dbgs() << "\t\trestoring liveness to " << EndPoints.size() << " points: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\trestoring liveness to "
<< EndPoints.size() << " points: "; for (unsigned
i = 0, n = EndPoints.size(); i != n; ++i) { dbgs() << EndPoints
[i]; if (i != n-1) dbgs() << ','; } dbgs() << ": "
<< LRange << '\n'; }; } } while (false)
2951 for (unsigned i = 0, n = EndPoints.size(); i != n; ++i) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\trestoring liveness to "
<< EndPoints.size() << " points: "; for (unsigned
i = 0, n = EndPoints.size(); i != n; ++i) { dbgs() << EndPoints
[i]; if (i != n-1) dbgs() << ','; } dbgs() << ": "
<< LRange << '\n'; }; } } while (false)
2952 dbgs() << EndPoints[i];do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\trestoring liveness to "
<< EndPoints.size() << " points: "; for (unsigned
i = 0, n = EndPoints.size(); i != n; ++i) { dbgs() << EndPoints
[i]; if (i != n-1) dbgs() << ','; } dbgs() << ": "
<< LRange << '\n'; }; } } while (false)
2953 if (i != n-1)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\trestoring liveness to "
<< EndPoints.size() << " points: "; for (unsigned
i = 0, n = EndPoints.size(); i != n; ++i) { dbgs() << EndPoints
[i]; if (i != n-1) dbgs() << ','; } dbgs() << ": "
<< LRange << '\n'; }; } } while (false)
2954 dbgs() << ',';do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\trestoring liveness to "
<< EndPoints.size() << " points: "; for (unsigned
i = 0, n = EndPoints.size(); i != n; ++i) { dbgs() << EndPoints
[i]; if (i != n-1) dbgs() << ','; } dbgs() << ": "
<< LRange << '\n'; }; } } while (false)
2955 }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\trestoring liveness to "
<< EndPoints.size() << " points: "; for (unsigned
i = 0, n = EndPoints.size(); i != n; ++i) { dbgs() << EndPoints
[i]; if (i != n-1) dbgs() << ','; } dbgs() << ": "
<< LRange << '\n'; }; } } while (false)
2956 dbgs() << ": " << LRange << '\n';do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\trestoring liveness to "
<< EndPoints.size() << " points: "; for (unsigned
i = 0, n = EndPoints.size(); i != n; ++i) { dbgs() << EndPoints
[i]; if (i != n-1) dbgs() << ','; } dbgs() << ": "
<< LRange << '\n'; }; } } while (false)
2957 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\trestoring liveness to "
<< EndPoints.size() << " points: "; for (unsigned
i = 0, n = EndPoints.size(); i != n; ++i) { dbgs() << EndPoints
[i]; if (i != n-1) dbgs() << ','; } dbgs() << ": "
<< LRange << '\n'; }; } } while (false)
;
2958 LIS->extendToIndices(LRange, EndPoints);
2959}
2960
2961void RegisterCoalescer::mergeSubRangeInto(LiveInterval &LI,
2962 const LiveRange &ToMerge,
2963 LaneBitmask LaneMask,
2964 CoalescerPair &CP) {
2965 BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
2966 LI.refineSubRanges(Allocator, LaneMask,
2967 [this,&Allocator,&ToMerge,&CP](LiveInterval::SubRange &SR) {
2968 if (SR.empty()) {
2969 SR.assign(ToMerge, Allocator);
2970 } else {
2971 // joinSubRegRange() destroys the merged range, so we need a copy.
2972 LiveRange RangeCopy(ToMerge, Allocator);
2973 joinSubRegRanges(SR, RangeCopy, SR.LaneMask, CP);
2974 }
2975 });
2976}
2977
2978bool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP) {
2979 SmallVector<VNInfo*, 16> NewVNInfo;
2980 LiveInterval &RHS = LIS->getInterval(CP.getSrcReg());
2981 LiveInterval &LHS = LIS->getInterval(CP.getDstReg());
2982 bool TrackSubRegLiveness = MRI->shouldTrackSubRegLiveness(*CP.getNewRC());
2983 JoinVals RHSVals(RHS, CP.getSrcReg(), CP.getSrcIdx(), LaneBitmask::getNone(),
2984 NewVNInfo, CP, LIS, TRI, false, TrackSubRegLiveness);
2985 JoinVals LHSVals(LHS, CP.getDstReg(), CP.getDstIdx(), LaneBitmask::getNone(),
2986 NewVNInfo, CP, LIS, TRI, false, TrackSubRegLiveness);
2987
2988 DEBUG(dbgs() << "\t\tRHS = " << RHSdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tRHS = " << RHS <<
"\n\t\tLHS = " << LHS << '\n'; } } while (false)
2989 << "\n\t\tLHS = " << LHSdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tRHS = " << RHS <<
"\n\t\tLHS = " << LHS << '\n'; } } while (false)
2990 << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tRHS = " << RHS <<
"\n\t\tLHS = " << LHS << '\n'; } } while (false)
;
2991
2992 // First compute NewVNInfo and the simple value mappings.
2993 // Detect impossible conflicts early.
2994 if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals))
2995 return false;
2996
2997 // Some conflicts can only be resolved after all values have been mapped.
2998 if (!LHSVals.resolveConflicts(RHSVals) || !RHSVals.resolveConflicts(LHSVals))
2999 return false;
3000
3001 // All clear, the live ranges can be merged.
3002 if (RHS.hasSubRanges() || LHS.hasSubRanges()) {
3003 BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
3004
3005 // Transform lanemasks from the LHS to masks in the coalesced register and
3006 // create initial subranges if necessary.
3007 unsigned DstIdx = CP.getDstIdx();
3008 if (!LHS.hasSubRanges()) {
3009 LaneBitmask Mask = DstIdx == 0 ? CP.getNewRC()->getLaneMask()
3010 : TRI->getSubRegIndexLaneMask(DstIdx);
3011 // LHS must support subregs or we wouldn't be in this codepath.
3012 assert(Mask.any())(static_cast <bool> (Mask.any()) ? void (0) : __assert_fail
("Mask.any()", "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 3012, __extension__ __PRETTY_FUNCTION__))
;
3013 LHS.createSubRangeFrom(Allocator, Mask, LHS);
3014 } else if (DstIdx != 0) {
3015 // Transform LHS lanemasks to new register class if necessary.
3016 for (LiveInterval::SubRange &R : LHS.subranges()) {
3017 LaneBitmask Mask = TRI->composeSubRegIndexLaneMask(DstIdx, R.LaneMask);
3018 R.LaneMask = Mask;
3019 }
3020 }
3021 DEBUG(dbgs() << "\t\tLHST = " << printReg(CP.getDstReg())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tLHST = " << printReg
(CP.getDstReg()) << ' ' << LHS << '\n'; } }
while (false)
3022 << ' ' << LHS << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tLHST = " << printReg
(CP.getDstReg()) << ' ' << LHS << '\n'; } }
while (false)
;
3023
3024 // Determine lanemasks of RHS in the coalesced register and merge subranges.
3025 unsigned SrcIdx = CP.getSrcIdx();
3026 if (!RHS.hasSubRanges()) {
3027 LaneBitmask Mask = SrcIdx == 0 ? CP.getNewRC()->getLaneMask()
3028 : TRI->getSubRegIndexLaneMask(SrcIdx);
3029 mergeSubRangeInto(LHS, RHS, Mask, CP);
3030 } else {
3031 // Pair up subranges and merge.
3032 for (LiveInterval::SubRange &R : RHS.subranges()) {
3033 LaneBitmask Mask = TRI->composeSubRegIndexLaneMask(SrcIdx, R.LaneMask);
3034 mergeSubRangeInto(LHS, R, Mask, CP);
3035 }
3036 }
3037 DEBUG(dbgs() << "\tJoined SubRanges " << LHS << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tJoined SubRanges " <<
LHS << "\n"; } } while (false)
;
3038
3039 // Pruning implicit defs from subranges may result in the main range
3040 // having stale segments.
3041 LHSVals.pruneMainSegments(LHS, ShrinkMainRange);
3042
3043 LHSVals.pruneSubRegValues(LHS, ShrinkMask);
3044 RHSVals.pruneSubRegValues(LHS, ShrinkMask);
3045 }
3046
3047 // The merging algorithm in LiveInterval::join() can't handle conflicting
3048 // value mappings, so we need to remove any live ranges that overlap a
3049 // CR_Replace resolution. Collect a set of end points that can be used to
3050 // restore the live range after joining.
3051 SmallVector<SlotIndex, 8> EndPoints;
3052 LHSVals.pruneValues(RHSVals, EndPoints, true);
3053 RHSVals.pruneValues(LHSVals, EndPoints, true);
3054
3055 // Erase COPY and IMPLICIT_DEF instructions. This may cause some external
3056 // registers to require trimming.
3057 SmallVector<unsigned, 8> ShrinkRegs;
3058 LHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs, &LHS);
3059 RHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs);
3060 while (!ShrinkRegs.empty())
3061 shrinkToUses(&LIS->getInterval(ShrinkRegs.pop_back_val()));
3062
3063 // Join RHS into LHS.
3064 LHS.join(RHS, LHSVals.getAssignments(), RHSVals.getAssignments(), NewVNInfo);
3065
3066 // Kill flags are going to be wrong if the live ranges were overlapping.
3067 // Eventually, we should simply clear all kill flags when computing live
3068 // ranges. They are reinserted after register allocation.
3069 MRI->clearKillFlags(LHS.reg);
3070 MRI->clearKillFlags(RHS.reg);
3071
3072 if (!EndPoints.empty()) {
3073 // Recompute the parts of the live range we had to remove because of
3074 // CR_Replace conflicts.
3075 DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\trestoring liveness to "
<< EndPoints.size() << " points: "; for (unsigned
i = 0, n = EndPoints.size(); i != n; ++i) { dbgs() << EndPoints
[i]; if (i != n-1) dbgs() << ','; } dbgs() << ": "
<< LHS << '\n'; }; } } while (false)
3076 dbgs() << "\t\trestoring liveness to " << EndPoints.size() << " points: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\trestoring liveness to "
<< EndPoints.size() << " points: "; for (unsigned
i = 0, n = EndPoints.size(); i != n; ++i) { dbgs() << EndPoints
[i]; if (i != n-1) dbgs() << ','; } dbgs() << ": "
<< LHS << '\n'; }; } } while (false)
3077 for (unsigned i = 0, n = EndPoints.size(); i != n; ++i) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\trestoring liveness to "
<< EndPoints.size() << " points: "; for (unsigned
i = 0, n = EndPoints.size(); i != n; ++i) { dbgs() << EndPoints
[i]; if (i != n-1) dbgs() << ','; } dbgs() << ": "
<< LHS << '\n'; }; } } while (false)
3078 dbgs() << EndPoints[i];do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\trestoring liveness to "
<< EndPoints.size() << " points: "; for (unsigned
i = 0, n = EndPoints.size(); i != n; ++i) { dbgs() << EndPoints
[i]; if (i != n-1) dbgs() << ','; } dbgs() << ": "
<< LHS << '\n'; }; } } while (false)
3079 if (i != n-1)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\trestoring liveness to "
<< EndPoints.size() << " points: "; for (unsigned
i = 0, n = EndPoints.size(); i != n; ++i) { dbgs() << EndPoints
[i]; if (i != n-1) dbgs() << ','; } dbgs() << ": "
<< LHS << '\n'; }; } } while (false)
3080 dbgs() << ',';do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\trestoring liveness to "
<< EndPoints.size() << " points: "; for (unsigned
i = 0, n = EndPoints.size(); i != n; ++i) { dbgs() << EndPoints
[i]; if (i != n-1) dbgs() << ','; } dbgs() << ": "
<< LHS << '\n'; }; } } while (false)
3081 }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\trestoring liveness to "
<< EndPoints.size() << " points: "; for (unsigned
i = 0, n = EndPoints.size(); i != n; ++i) { dbgs() << EndPoints
[i]; if (i != n-1) dbgs() << ','; } dbgs() << ": "
<< LHS << '\n'; }; } } while (false)
3082 dbgs() << ": " << LHS << '\n';do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\trestoring liveness to "
<< EndPoints.size() << " points: "; for (unsigned
i = 0, n = EndPoints.size(); i != n; ++i) { dbgs() << EndPoints
[i]; if (i != n-1) dbgs() << ','; } dbgs() << ": "
<< LHS << '\n'; }; } } while (false)
3083 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\trestoring liveness to "
<< EndPoints.size() << " points: "; for (unsigned
i = 0, n = EndPoints.size(); i != n; ++i) { dbgs() << EndPoints
[i]; if (i != n-1) dbgs() << ','; } dbgs() << ": "
<< LHS << '\n'; }; } } while (false)
;
3084 LIS->extendToIndices((LiveRange&)LHS, EndPoints);
3085 }
3086
3087 return true;
3088}
3089
3090bool RegisterCoalescer::joinIntervals(CoalescerPair &CP) {
3091 return CP.isPhys() ? joinReservedPhysReg(CP) : joinVirtRegs(CP);
3092}
3093
3094namespace {
3095
3096/// Information concerning MBB coalescing priority.
3097struct MBBPriorityInfo {
3098 MachineBasicBlock *MBB;
3099 unsigned Depth;
3100 bool IsSplit;
3101
3102 MBBPriorityInfo(MachineBasicBlock *mbb, unsigned depth, bool issplit)
3103 : MBB(mbb), Depth(depth), IsSplit(issplit) {}
3104};
3105
3106} // end anonymous namespace
3107
3108/// C-style comparator that sorts first based on the loop depth of the basic
3109/// block (the unsigned), and then on the MBB number.
3110///
3111/// EnableGlobalCopies assumes that the primary sort key is loop depth.
3112static int compareMBBPriority(const MBBPriorityInfo *LHS,
3113 const MBBPriorityInfo *RHS) {
3114 // Deeper loops first
3115 if (LHS->Depth != RHS->Depth)
3116 return LHS->Depth > RHS->Depth ? -1 : 1;
3117
3118 // Try to unsplit critical edges next.
3119 if (LHS->IsSplit != RHS->IsSplit)
3120 return LHS->IsSplit ? -1 : 1;
3121
3122 // Prefer blocks that are more connected in the CFG. This takes care of
3123 // the most difficult copies first while intervals are short.
3124 unsigned cl = LHS->MBB->pred_size() + LHS->MBB->succ_size();
3125 unsigned cr = RHS->MBB->pred_size() + RHS->MBB->succ_size();
3126 if (cl != cr)
3127 return cl > cr ? -1 : 1;
3128
3129 // As a last resort, sort by block number.
3130 return LHS->MBB->getNumber() < RHS->MBB->getNumber() ? -1 : 1;
3131}
3132
3133/// \returns true if the given copy uses or defines a local live range.
3134static bool isLocalCopy(MachineInstr *Copy, const LiveIntervals *LIS) {
3135 if (!Copy->isCopy())
3136 return false;
3137
3138 if (Copy->getOperand(1).isUndef())
3139 return false;
3140
3141 unsigned SrcReg = Copy->getOperand(1).getReg();
3142 unsigned DstReg = Copy->getOperand(0).getReg();
3143 if (TargetRegisterInfo::isPhysicalRegister(SrcReg)
3144 || TargetRegisterInfo::isPhysicalRegister(DstReg))
3145 return false;
3146
3147 return LIS->intervalIsInOneMBB(LIS->getInterval(SrcReg))
3148 || LIS->intervalIsInOneMBB(LIS->getInterval(DstReg));
3149}
3150
3151bool RegisterCoalescer::
3152copyCoalesceWorkList(MutableArrayRef<MachineInstr*> CurrList) {
3153 bool Progress = false;
3154 for (unsigned i = 0, e = CurrList.size(); i != e; ++i) {
3155 if (!CurrList[i])
3156 continue;
3157 // Skip instruction pointers that have already been erased, for example by
3158 // dead code elimination.
3159 if (ErasedInstrs.count(CurrList[i])) {
3160 CurrList[i] = nullptr;
3161 continue;
3162 }
3163 bool Again = false;
3164 bool Success = joinCopy(CurrList[i], Again);
3165 Progress |= Success;
3166 if (Success || !Again)
3167 CurrList[i] = nullptr;
3168 }
3169 return Progress;
3170}
3171
3172/// Check if DstReg is a terminal node.
3173/// I.e., it does not have any affinity other than \p Copy.
3174static bool isTerminalReg(unsigned DstReg, const MachineInstr &Copy,
3175 const MachineRegisterInfo *MRI) {
3176 assert(Copy.isCopyLike())(static_cast <bool> (Copy.isCopyLike()) ? void (0) : __assert_fail
("Copy.isCopyLike()", "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 3176, __extension__ __PRETTY_FUNCTION__))
;
3177 // Check if the destination of this copy as any other affinity.
3178 for (const MachineInstr &MI : MRI->reg_nodbg_instructions(DstReg))
3179 if (&MI != &Copy && MI.isCopyLike())
3180 return false;
3181 return true;
3182}
3183
3184bool RegisterCoalescer::applyTerminalRule(const MachineInstr &Copy) const {
3185 assert(Copy.isCopyLike())(static_cast <bool> (Copy.isCopyLike()) ? void (0) : __assert_fail
("Copy.isCopyLike()", "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 3185, __extension__ __PRETTY_FUNCTION__))
;
3186 if (!UseTerminalRule)
20
Assuming the condition is false
21
Taking false branch
3187 return false;
3188 unsigned DstReg, DstSubReg, SrcReg, SrcSubReg;
3189 isMoveInstr(*TRI, &Copy, SrcReg, DstReg, SrcSubReg, DstSubReg);
3190 // Check if the destination of this copy has any other affinity.
3191 if (TargetRegisterInfo::isPhysicalRegister(DstReg) ||
22
Taking false branch
3192 // If SrcReg is a physical register, the copy won't be coalesced.
3193 // Ignoring it may have other side effect (like missing
3194 // rematerialization). So keep it.
3195 TargetRegisterInfo::isPhysicalRegister(SrcReg) ||
3196 !isTerminalReg(DstReg, Copy, MRI))
3197 return false;
3198
3199 // DstReg is a terminal node. Check if it interferes with any other
3200 // copy involving SrcReg.
3201 const MachineBasicBlock *OrigBB = Copy.getParent();
3202 const LiveInterval &DstLI = LIS->getInterval(DstReg);
3203 for (const MachineInstr &MI : MRI->reg_nodbg_instructions(SrcReg)) {
3204 // Technically we should check if the weight of the new copy is
3205 // interesting compared to the other one and update the weight
3206 // of the copies accordingly. However, this would only work if
3207 // we would gather all the copies first then coalesce, whereas
3208 // right now we interleave both actions.
3209 // For now, just consider the copies that are in the same block.
3210 if (&MI == &Copy || !MI.isCopyLike() || MI.getParent() != OrigBB)
23
Assuming the condition is false
24
Assuming the condition is false
25
Taking false branch
45
Assuming the condition is false
46
Assuming the condition is false
47
Taking false branch
3211 continue;
3212 unsigned OtherReg, OtherSubReg, OtherSrcReg, OtherSrcSubReg;
48
'OtherSrcReg' declared without an initial value
3213 isMoveInstr(*TRI, &Copy, OtherSrcReg, OtherReg, OtherSrcSubReg,
26
Calling 'isMoveInstr'
39
Returning from 'isMoveInstr'
49
Calling 'isMoveInstr'
62
Returning from 'isMoveInstr'
3214 OtherSubReg);
3215 if (OtherReg == SrcReg)
40
Assuming 'OtherReg' is equal to 'SrcReg'
41
Taking true branch
63
Taking true branch
3216 OtherReg = OtherSrcReg;
64
Assigned value is garbage or undefined
3217 // Check if OtherReg is a non-terminal.
3218 if (TargetRegisterInfo::isPhysicalRegister(OtherReg) ||
43
Taking true branch
3219 isTerminalReg(OtherReg, MI, MRI))
42
Assuming the condition is true
3220 continue;
44
Execution continues on line 3203
3221 // Check that OtherReg interfere with DstReg.
3222 if (LIS->getInterval(OtherReg).overlaps(DstLI)) {
3223 DEBUG(dbgs() << "Apply terminal rule for: " << printReg(DstReg) << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Apply terminal rule for: " <<
printReg(DstReg) << '\n'; } } while (false)
;
3224 return true;
3225 }
3226 }
3227 return false;
3228}
3229
3230void
3231RegisterCoalescer::copyCoalesceInMBB(MachineBasicBlock *MBB) {
3232 DEBUG(dbgs() << MBB->getName() << ":\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << MBB->getName() << ":\n"
; } } while (false)
;
3233
3234 // Collect all copy-like instructions in MBB. Don't start coalescing anything
3235 // yet, it might invalidate the iterator.
3236 const unsigned PrevSize = WorkList.size();
3237 if (JoinGlobalCopies) {
14
Taking false branch
3238 SmallVector<MachineInstr*, 2> LocalTerminals;
3239 SmallVector<MachineInstr*, 2> GlobalTerminals;
3240 // Coalesce copies bottom-up to coalesce local defs before local uses. They
3241 // are not inherently easier to resolve, but slightly preferable until we
3242 // have local live range splitting. In particular this is required by
3243 // cmp+jmp macro fusion.
3244 for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end();
3245 MII != E; ++MII) {
3246 if (!MII->isCopyLike())
3247 continue;
3248 bool ApplyTerminalRule = applyTerminalRule(*MII);
3249 if (isLocalCopy(&(*MII), LIS)) {
3250 if (ApplyTerminalRule)
3251 LocalTerminals.push_back(&(*MII));
3252 else
3253 LocalWorkList.push_back(&(*MII));
3254 } else {
3255 if (ApplyTerminalRule)
3256 GlobalTerminals.push_back(&(*MII));
3257 else
3258 WorkList.push_back(&(*MII));
3259 }
3260 }
3261 // Append the copies evicted by the terminal rule at the end of the list.
3262 LocalWorkList.append(LocalTerminals.begin(), LocalTerminals.end());
3263 WorkList.append(GlobalTerminals.begin(), GlobalTerminals.end());
3264 }
3265 else {
3266 SmallVector<MachineInstr*, 2> Terminals;
3267 for (MachineInstr &MII : *MBB)
3268 if (MII.isCopyLike()) {
15
Taking false branch
16
Taking false branch
17
Taking false branch
18
Taking true branch
3269 if (applyTerminalRule(MII))
19
Calling 'RegisterCoalescer::applyTerminalRule'
3270 Terminals.push_back(&MII);
3271 else
3272 WorkList.push_back(&MII);
3273 }
3274 // Append the copies evicted by the terminal rule at the end of the list.
3275 WorkList.append(Terminals.begin(), Terminals.end());
3276 }
3277 // Try coalescing the collected copies immediately, and remove the nulls.
3278 // This prevents the WorkList from getting too large since most copies are
3279 // joinable on the first attempt.
3280 MutableArrayRef<MachineInstr*>
3281 CurrList(WorkList.begin() + PrevSize, WorkList.end());
3282 if (copyCoalesceWorkList(CurrList))
3283 WorkList.erase(std::remove(WorkList.begin() + PrevSize, WorkList.end(),
3284 nullptr), WorkList.end());
3285}
3286
3287void RegisterCoalescer::coalesceLocals() {
3288 copyCoalesceWorkList(LocalWorkList);
3289 for (unsigned j = 0, je = LocalWorkList.size(); j != je; ++j) {
3290 if (LocalWorkList[j])
3291 WorkList.push_back(LocalWorkList[j]);
3292 }
3293 LocalWorkList.clear();
3294}
3295
3296void RegisterCoalescer::joinAllIntervals() {
3297 DEBUG(dbgs() << "********** JOINING INTERVALS ***********\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "********** JOINING INTERVALS ***********\n"
; } } while (false)
;
3298 assert(WorkList.empty() && LocalWorkList.empty() && "Old data still around.")(static_cast <bool> (WorkList.empty() && LocalWorkList
.empty() && "Old data still around.") ? void (0) : __assert_fail
("WorkList.empty() && LocalWorkList.empty() && \"Old data still around.\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 3298, __extension__ __PRETTY_FUNCTION__))
;
3299
3300 std::vector<MBBPriorityInfo> MBBs;
3301 MBBs.reserve(MF->size());
3302 for (MachineFunction::iterator I = MF->begin(), E = MF->end(); I != E; ++I) {
9
Loop condition is false. Execution continues on line 3307
3303 MachineBasicBlock *MBB = &*I;
3304 MBBs.push_back(MBBPriorityInfo(MBB, Loops->getLoopDepth(MBB),
3305 JoinSplitEdges && isSplitEdge(MBB)));
3306 }
3307 array_pod_sort(MBBs.begin(), MBBs.end(), compareMBBPriority);
3308
3309 // Coalesce intervals in MBB priority order.
3310 unsigned CurrDepth = std::numeric_limits<unsigned>::max();
3311 for (unsigned i = 0, e = MBBs.size(); i != e; ++i) {
10
Assuming 'i' is not equal to 'e'
11
Loop condition is true. Entering loop body
3312 // Try coalescing the collected local copies for deeper loops.
3313 if (JoinGlobalCopies && MBBs[i].Depth < CurrDepth) {
12
Assuming the condition is false
3314 coalesceLocals();
3315 CurrDepth = MBBs[i].Depth;
3316 }
3317 copyCoalesceInMBB(MBBs[i].MBB);
13
Calling 'RegisterCoalescer::copyCoalesceInMBB'
3318 }
3319 coalesceLocals();
3320
3321 // Joining intervals can allow other intervals to be joined. Iteratively join
3322 // until we make no progress.
3323 while (copyCoalesceWorkList(WorkList))
3324 /* empty */ ;
3325}
3326
3327void RegisterCoalescer::releaseMemory() {
3328 ErasedInstrs.clear();
3329 WorkList.clear();
3330 DeadDefs.clear();
3331 InflateRegs.clear();
3332}
3333
3334bool RegisterCoalescer::runOnMachineFunction(MachineFunction &fn) {
3335 MF = &fn;
3336 MRI = &fn.getRegInfo();
3337 const TargetSubtargetInfo &STI = fn.getSubtarget();
3338 TRI = STI.getRegisterInfo();
3339 TII = STI.getInstrInfo();
3340 LIS = &getAnalysis<LiveIntervals>();
3341 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
3342 Loops = &getAnalysis<MachineLoopInfo>();
3343 if (EnableGlobalCopies == cl::BOU_UNSET)
1
Assuming the condition is false
2
Taking false branch
3344 JoinGlobalCopies = STI.enableJoinGlobalCopies();
3345 else
3346 JoinGlobalCopies = (EnableGlobalCopies == cl::BOU_TRUE);
3
Assuming the condition is false
3347
3348 // The MachineScheduler does not currently require JoinSplitEdges. This will
3349 // either be enabled unconditionally or replaced by a more general live range
3350 // splitting optimization.
3351 JoinSplitEdges = EnableJoinSplits;
3352
3353 DEBUG(dbgs() << "********** SIMPLE REGISTER COALESCING **********\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "********** SIMPLE REGISTER COALESCING **********\n"
<< "********** Function: " << MF->getName() <<
'\n'; } } while (false)
3354 << "********** Function: " << MF->getName() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "********** SIMPLE REGISTER COALESCING **********\n"
<< "********** Function: " << MF->getName() <<
'\n'; } } while (false)
;
3355
3356 if (VerifyCoalescing)
4
Assuming the condition is false
5
Taking false branch
3357 MF->verify(this, "Before register coalescing");
3358
3359 RegClassInfo.runOnMachineFunction(fn);
3360
3361 // Join (coalesce) intervals if requested.
3362 if (EnableJoining)
6
Assuming the condition is true
7
Taking true branch
3363 joinAllIntervals();
8
Calling 'RegisterCoalescer::joinAllIntervals'
3364
3365 // After deleting a lot of copies, register classes may be less constrained.
3366 // Removing sub-register operands may allow GR32_ABCD -> GR32 and DPR_VFP2 ->
3367 // DPR inflation.
3368 array_pod_sort(InflateRegs.begin(), InflateRegs.end());
3369 InflateRegs.erase(std::unique(InflateRegs.begin(), InflateRegs.end()),
3370 InflateRegs.end());
3371 DEBUG(dbgs() << "Trying to inflate " << InflateRegs.size() << " regs.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Trying to inflate " <<
InflateRegs.size() << " regs.\n"; } } while (false)
;
3372 for (unsigned i = 0, e = InflateRegs.size(); i != e; ++i) {
3373 unsigned Reg = InflateRegs[i];
3374 if (MRI->reg_nodbg_empty(Reg))
3375 continue;
3376 if (MRI->recomputeRegClass(Reg)) {
3377 DEBUG(dbgs() << printReg(Reg) << " inflated to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << printReg(Reg) << " inflated to "
<< TRI->getRegClassName(MRI->getRegClass(Reg)) <<
'\n'; } } while (false)
3378 << TRI->getRegClassName(MRI->getRegClass(Reg)) << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << printReg(Reg) << " inflated to "
<< TRI->getRegClassName(MRI->getRegClass(Reg)) <<
'\n'; } } while (false)
;
3379 ++NumInflated;
3380
3381 LiveInterval &LI = LIS->getInterval(Reg);
3382 if (LI.hasSubRanges()) {
3383 // If the inflated register class does not support subregisters anymore
3384 // remove the subranges.
3385 if (!MRI->shouldTrackSubRegLiveness(Reg)) {
3386 LI.clearSubRanges();
3387 } else {
3388#ifndef NDEBUG
3389 LaneBitmask MaxMask = MRI->getMaxLaneMaskForVReg(Reg);
3390 // If subranges are still supported, then the same subregs
3391 // should still be supported.
3392 for (LiveInterval::SubRange &S : LI.subranges()) {
3393 assert((S.LaneMask & ~MaxMask).none())(static_cast <bool> ((S.LaneMask & ~MaxMask).none()
) ? void (0) : __assert_fail ("(S.LaneMask & ~MaxMask).none()"
, "/build/llvm-toolchain-snapshot-6.0~svn321639/lib/CodeGen/RegisterCoalescer.cpp"
, 3393, __extension__ __PRETTY_FUNCTION__))
;
3394 }
3395#endif
3396 }
3397 }
3398 }
3399 }
3400
3401 DEBUG(dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dump(); } } while (false)
;
3402 if (VerifyCoalescing)
3403 MF->verify(this, "After register coalescing");
3404 return true;
3405}
3406
3407void RegisterCoalescer::print(raw_ostream &O, const Module* m) const {
3408 LIS->print(O, m);
3409}

/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/CodeGen/MachineInstr.h

1//===- llvm/CodeGen/MachineInstr.h - MachineInstr class ---------*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file contains the declaration of the MachineInstr class, which is the
11// basic representation for all target dependent machine instructions used by
12// the back end.
13//
14//===----------------------------------------------------------------------===//
15
16#ifndef LLVM_CODEGEN_MACHINEINSTR_H
17#define LLVM_CODEGEN_MACHINEINSTR_H
18
19#include "llvm/ADT/DenseMapInfo.h"
20#include "llvm/ADT/ilist.h"
21#include "llvm/ADT/ilist_node.h"
22#include "llvm/ADT/iterator_range.h"
23#include "llvm/Analysis/AliasAnalysis.h"
24#include "llvm/CodeGen/MachineOperand.h"
25#include "llvm/CodeGen/TargetOpcodes.h"
26#include "llvm/IR/DebugLoc.h"
27#include "llvm/IR/InlineAsm.h"
28#include "llvm/MC/MCInstrDesc.h"
29#include "llvm/Support/ArrayRecycler.h"
30#include <algorithm>
31#include <cassert>
32#include <cstdint>
33#include <utility>
34
35namespace llvm {
36
37template <typename T> class ArrayRef;
38class DIExpression;
39class DILocalVariable;
40class MachineBasicBlock;
41class MachineFunction;
42class MachineMemOperand;
43class MachineRegisterInfo;
44class ModuleSlotTracker;
45class raw_ostream;
46template <typename T> class SmallVectorImpl;
47class SmallBitVector;
48class StringRef;
49class TargetInstrInfo;
50class TargetRegisterClass;
51class TargetRegisterInfo;
52
53//===----------------------------------------------------------------------===//
54/// Representation of each machine instruction.
55///
56/// This class isn't a POD type, but it must have a trivial destructor. When a
57/// MachineFunction is deleted, all the contained MachineInstrs are deallocated
58/// without having their destructor called.
59///
60class MachineInstr
61 : public ilist_node_with_parent<MachineInstr, MachineBasicBlock,
62 ilist_sentinel_tracking<true>> {
63public:
64 using mmo_iterator = MachineMemOperand **;
65
66 /// Flags to specify different kinds of comments to output in
67 /// assembly code. These flags carry semantic information not
68 /// otherwise easily derivable from the IR text.
69 ///
70 enum CommentFlag {
71 ReloadReuse = 0x1, // higher bits are reserved for target dep comments.
72 NoSchedComment = 0x2,
73 TAsmComments = 0x4 // Target Asm comments should start from this value.
74 };
75
76 enum MIFlag {
77 NoFlags = 0,
78 FrameSetup = 1 << 0, // Instruction is used as a part of
79 // function frame setup code.
80 FrameDestroy = 1 << 1, // Instruction is used as a part of
81 // function frame destruction code.
82 BundledPred = 1 << 2, // Instruction has bundled predecessors.
83 BundledSucc = 1 << 3 // Instruction has bundled successors.
84 };
85
86private:
87 const MCInstrDesc *MCID; // Instruction descriptor.
88 MachineBasicBlock *Parent = nullptr; // Pointer to the owning basic block.
89
90 // Operands are allocated by an ArrayRecycler.
91 MachineOperand *Operands = nullptr; // Pointer to the first operand.
92 unsigned NumOperands = 0; // Number of operands on instruction.
93 using OperandCapacity = ArrayRecycler<MachineOperand>::Capacity;
94 OperandCapacity CapOperands; // Capacity of the Operands array.
95
96 uint8_t Flags = 0; // Various bits of additional
97 // information about machine
98 // instruction.
99
100 uint8_t AsmPrinterFlags = 0; // Various bits of information used by
101 // the AsmPrinter to emit helpful
102 // comments. This is *not* semantic
103 // information. Do not use this for
104 // anything other than to convey comment
105 // information to AsmPrinter.
106
107 uint8_t NumMemRefs = 0; // Information on memory references.
108 // Note that MemRefs == nullptr, means 'don't know', not 'no memory access'.
109 // Calling code must treat missing information conservatively. If the number
110 // of memory operands required to be precise exceeds the maximum value of
111 // NumMemRefs - currently 256 - we remove the operands entirely. Note also
112 // that this is a non-owning reference to a shared copy on write buffer owned
113 // by the MachineFunction and created via MF.allocateMemRefsArray.
114 mmo_iterator MemRefs = nullptr;
115
116 DebugLoc debugLoc; // Source line information.
117
118 // Intrusive list support
119 friend struct ilist_traits<MachineInstr>;
120 friend struct ilist_callback_traits<MachineBasicBlock>;
121 void setParent(MachineBasicBlock *P) { Parent = P; }
122
123 /// This constructor creates a copy of the given
124 /// MachineInstr in the given MachineFunction.
125 MachineInstr(MachineFunction &, const MachineInstr &);
126
127 /// This constructor create a MachineInstr and add the implicit operands.
128 /// It reserves space for number of operands specified by
129 /// MCInstrDesc. An explicit DebugLoc is supplied.
130 MachineInstr(MachineFunction &, const MCInstrDesc &MCID, DebugLoc dl,
131 bool NoImp = false);
132
133 // MachineInstrs are pool-allocated and owned by MachineFunction.
134 friend class MachineFunction;
135
136public:
137 MachineInstr(const MachineInstr &) = delete;
138 MachineInstr &operator=(const MachineInstr &) = delete;
139 // Use MachineFunction::DeleteMachineInstr() instead.
140 ~MachineInstr() = delete;
141
142 const MachineBasicBlock* getParent() const { return Parent; }
143 MachineBasicBlock* getParent() { return Parent; }
144
145 /// Return the function that contains the basic block that this instruction
146 /// belongs to.
147 ///
148 /// Note: this is undefined behaviour if the instruction does not have a
149 /// parent.
150 const MachineFunction *getMF() const;
151 MachineFunction *getMF() {
152 return const_cast<MachineFunction *>(
153 static_cast<const MachineInstr *>(this)->getMF());
154 }
155
156 /// Return the asm printer flags bitvector.
157 uint8_t getAsmPrinterFlags() const { return AsmPrinterFlags; }
158
159 /// Clear the AsmPrinter bitvector.
160 void clearAsmPrinterFlags() { AsmPrinterFlags = 0; }
161
162 /// Return whether an AsmPrinter flag is set.
163 bool getAsmPrinterFlag(CommentFlag Flag) const {
164 return AsmPrinterFlags & Flag;
165 }
166
167 /// Set a flag for the AsmPrinter.
168 void setAsmPrinterFlag(uint8_t Flag) {
169 AsmPrinterFlags |= Flag;
170 }
171
172 /// Clear specific AsmPrinter flags.
173 void clearAsmPrinterFlag(CommentFlag Flag) {
174 AsmPrinterFlags &= ~Flag;
175 }
176
177 /// Return the MI flags bitvector.
178 uint8_t getFlags() const {
179 return Flags;
180 }
181
182 /// Return whether an MI flag is set.
183 bool getFlag(MIFlag Flag) const {
184 return Flags & Flag;
185 }
186
187 /// Set a MI flag.
188 void setFlag(MIFlag Flag) {
189 Flags |= (uint8_t)Flag;
190 }
191
192 void setFlags(unsigned flags) {
193 // Filter out the automatically maintained flags.
194 unsigned Mask = BundledPred | BundledSucc;
195 Flags = (Flags & Mask) | (flags & ~Mask);
196 }
197
198 /// clearFlag - Clear a MI flag.
199 void clearFlag(MIFlag Flag) {
200 Flags &= ~((uint8_t)Flag);
201 }
202
203 /// Return true if MI is in a bundle (but not the first MI in a bundle).
204 ///
205 /// A bundle looks like this before it's finalized:
206 /// ----------------
207 /// | MI |
208 /// ----------------
209 /// |
210 /// ----------------
211 /// | MI * |
212 /// ----------------
213 /// |
214 /// ----------------
215 /// | MI * |
216 /// ----------------
217 /// In this case, the first MI starts a bundle but is not inside a bundle, the
218 /// next 2 MIs are considered "inside" the bundle.
219 ///
220 /// After a bundle is finalized, it looks like this:
221 /// ----------------
222 /// | Bundle |
223 /// ----------------
224 /// |
225 /// ----------------
226 /// | MI * |
227 /// ----------------
228 /// |
229 /// ----------------
230 /// | MI * |
231 /// ----------------
232 /// |
233 /// ----------------
234 /// | MI * |
235 /// ----------------
236 /// The first instruction has the special opcode "BUNDLE". It's not "inside"
237 /// a bundle, but the next three MIs are.
238 bool isInsideBundle() const {
239 return getFlag(BundledPred);
240 }
241
242 /// Return true if this instruction part of a bundle. This is true
243 /// if either itself or its following instruction is marked "InsideBundle".
244 bool isBundled() const {
245 return isBundledWithPred() || isBundledWithSucc();
246 }
247
248 /// Return true if this instruction is part of a bundle, and it is not the
249 /// first instruction in the bundle.
250 bool isBundledWithPred() const { return getFlag(BundledPred); }
251
252 /// Return true if this instruction is part of a bundle, and it is not the
253 /// last instruction in the bundle.
254 bool isBundledWithSucc() const { return getFlag(BundledSucc); }
255
256 /// Bundle this instruction with its predecessor. This can be an unbundled
257 /// instruction, or it can be the first instruction in a bundle.
258 void bundleWithPred();
259
260 /// Bundle this instruction with its successor. This can be an unbundled
261 /// instruction, or it can be the last instruction in a bundle.
262 void bundleWithSucc();
263
264 /// Break bundle above this instruction.
265 void unbundleFromPred();
266
267 /// Break bundle below this instruction.
268 void unbundleFromSucc();
269
270 /// Returns the debug location id of this MachineInstr.
271 const DebugLoc &getDebugLoc() const { return debugLoc; }
272
273 /// Return the debug variable referenced by
274 /// this DBG_VALUE instruction.
275 const DILocalVariable *getDebugVariable() const;
276
277 /// Return the complex address expression referenced by
278 /// this DBG_VALUE instruction.
279 const DIExpression *getDebugExpression() const;
280
281 /// Emit an error referring to the source location of this instruction.
282 /// This should only be used for inline assembly that is somehow
283 /// impossible to compile. Other errors should have been handled much
284 /// earlier.
285 ///
286 /// If this method returns, the caller should try to recover from the error.
287 void emitError(StringRef Msg) const;
288
289 /// Returns the target instruction descriptor of this MachineInstr.
290 const MCInstrDesc &getDesc() const { return *MCID; }
291
292 /// Returns the opcode of this MachineInstr.
293 unsigned getOpcode() const { return MCID->Opcode; }
294
295 /// Access to explicit operands of the instruction.
296 unsigned getNumOperands() const { return NumOperands; }
297
298 const MachineOperand& getOperand(unsigned i) const {
299 assert(i < getNumOperands() && "getOperand() out of range!")(static_cast <bool> (i < getNumOperands() &&
"getOperand() out of range!") ? void (0) : __assert_fail ("i < getNumOperands() && \"getOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/CodeGen/MachineInstr.h"
, 299, __extension__ __PRETTY_FUNCTION__))
;
300 return Operands[i];
301 }
302 MachineOperand& getOperand(unsigned i) {
303 assert(i < getNumOperands() && "getOperand() out of range!")(static_cast <bool> (i < getNumOperands() &&
"getOperand() out of range!") ? void (0) : __assert_fail ("i < getNumOperands() && \"getOperand() out of range!\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/CodeGen/MachineInstr.h"
, 303, __extension__ __PRETTY_FUNCTION__))
;
304 return Operands[i];
305 }
306
307 /// Return true if operand \p OpIdx is a subregister index.
308 bool isOperandSubregIdx(unsigned OpIdx) const {
309 assert(getOperand(OpIdx).getType() == MachineOperand::MO_Immediate &&(static_cast <bool> (getOperand(OpIdx).getType() == MachineOperand
::MO_Immediate && "Expected MO_Immediate operand type."
) ? void (0) : __assert_fail ("getOperand(OpIdx).getType() == MachineOperand::MO_Immediate && \"Expected MO_Immediate operand type.\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/CodeGen/MachineInstr.h"
, 310, __extension__ __PRETTY_FUNCTION__))
310 "Expected MO_Immediate operand type.")(static_cast <bool> (getOperand(OpIdx).getType() == MachineOperand
::MO_Immediate && "Expected MO_Immediate operand type."
) ? void (0) : __assert_fail ("getOperand(OpIdx).getType() == MachineOperand::MO_Immediate && \"Expected MO_Immediate operand type.\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/CodeGen/MachineInstr.h"
, 310, __extension__ __PRETTY_FUNCTION__))
;
311 if (isExtractSubreg() && OpIdx == 2)
312 return true;
313 if (isInsertSubreg() && OpIdx == 3)
314 return true;
315 if (isRegSequence() && OpIdx > 1 && (OpIdx % 2) == 0)
316 return true;
317 if (isSubregToReg() && OpIdx == 3)
318 return true;
319 return false;
320 }
321
322 /// Returns the number of non-implicit operands.
323 unsigned getNumExplicitOperands() const;
324
325 /// iterator/begin/end - Iterate over all operands of a machine instruction.
326 using mop_iterator = MachineOperand *;
327 using const_mop_iterator = const MachineOperand *;
328
329 mop_iterator operands_begin() { return Operands; }
330 mop_iterator operands_end() { return Operands + NumOperands; }
331
332 const_mop_iterator operands_begin() const { return Operands; }
333 const_mop_iterator operands_end() const { return Operands + NumOperands; }
334
335 iterator_range<mop_iterator> operands() {
336 return make_range(operands_begin(), operands_end());
337 }
338 iterator_range<const_mop_iterator> operands() const {
339 return make_range(operands_begin(), operands_end());
340 }
341 iterator_range<mop_iterator> explicit_operands() {
342 return make_range(operands_begin(),
343 operands_begin() + getNumExplicitOperands());
344 }
345 iterator_range<const_mop_iterator> explicit_operands() const {
346 return make_range(operands_begin(),
347 operands_begin() + getNumExplicitOperands());
348 }
349 iterator_range<mop_iterator> implicit_operands() {
350 return make_range(explicit_operands().end(), operands_end());
351 }
352 iterator_range<const_mop_iterator> implicit_operands() const {
353 return make_range(explicit_operands().end(), operands_end());
354 }
355 /// Returns a range over all explicit operands that are register definitions.
356 /// Implicit definition are not included!
357 iterator_range<mop_iterator> defs() {
358 return make_range(operands_begin(),
359 operands_begin() + getDesc().getNumDefs());
360 }
361 /// \copydoc defs()
362 iterator_range<const_mop_iterator> defs() const {
363 return make_range(operands_begin(),
364 operands_begin() + getDesc().getNumDefs());
365 }
366 /// Returns a range that includes all operands that are register uses.
367 /// This may include unrelated operands which are not register uses.
368 iterator_range<mop_iterator> uses() {
369 return make_range(operands_begin() + getDesc().getNumDefs(),
370 operands_end());
371 }
372 /// \copydoc uses()
373 iterator_range<const_mop_iterator> uses() const {
374 return make_range(operands_begin() + getDesc().getNumDefs(),
375 operands_end());
376 }
377 iterator_range<mop_iterator> explicit_uses() {
378 return make_range(operands_begin() + getDesc().getNumDefs(),
379 operands_begin() + getNumExplicitOperands() );
380 }
381 iterator_range<const_mop_iterator> explicit_uses() const {
382 return make_range(operands_begin() + getDesc().getNumDefs(),
383 operands_begin() + getNumExplicitOperands() );
384 }
385
386 /// Returns the number of the operand iterator \p I points to.
387 unsigned getOperandNo(const_mop_iterator I) const {
388 return I - operands_begin();
389 }
390
391 /// Access to memory operands of the instruction
392 mmo_iterator memoperands_begin() const { return MemRefs; }
393 mmo_iterator memoperands_end() const { return MemRefs + NumMemRefs; }
394 /// Return true if we don't have any memory operands which described the the
395 /// memory access done by this instruction. If this is true, calling code
396 /// must be conservative.
397 bool memoperands_empty() const { return NumMemRefs == 0; }
398
399 iterator_range<mmo_iterator> memoperands() {
400 return make_range(memoperands_begin(), memoperands_end());
401 }
402 iterator_range<mmo_iterator> memoperands() const {
403 return make_range(memoperands_begin(), memoperands_end());
404 }
405
406 /// Return true if this instruction has exactly one MachineMemOperand.
407 bool hasOneMemOperand() const {
408 return NumMemRefs == 1;
409 }
410
411 /// Return the number of memory operands.
412 unsigned getNumMemOperands() const { return NumMemRefs; }
413
414 /// API for querying MachineInstr properties. They are the same as MCInstrDesc
415 /// queries but they are bundle aware.
416
417 enum QueryType {
418 IgnoreBundle, // Ignore bundles
419 AnyInBundle, // Return true if any instruction in bundle has property
420 AllInBundle // Return true if all instructions in bundle have property
421 };
422
423 /// Return true if the instruction (or in the case of a bundle,
424 /// the instructions inside the bundle) has the specified property.
425 /// The first argument is the property being queried.
426 /// The second argument indicates whether the query should look inside
427 /// instruction bundles.
428 bool hasProperty(unsigned MCFlag, QueryType Type = AnyInBundle) const {
429 // Inline the fast path for unbundled or bundle-internal instructions.
430 if (Type == IgnoreBundle || !isBundled() || isBundledWithPred())
431 return getDesc().getFlags() & (1ULL << MCFlag);
432
433 // If this is the first instruction in a bundle, take the slow path.
434 return hasPropertyInBundle(1ULL << MCFlag, Type);
435 }
436
437 /// Return true if this instruction can have a variable number of operands.
438 /// In this case, the variable operands will be after the normal
439 /// operands but before the implicit definitions and uses (if any are
440 /// present).
441 bool isVariadic(QueryType Type = IgnoreBundle) const {
442 return hasProperty(MCID::Variadic, Type);
443 }
444
445 /// Set if this instruction has an optional definition, e.g.
446 /// ARM instructions which can set condition code if 's' bit is set.
447 bool hasOptionalDef(QueryType Type = IgnoreBundle) const {
448 return hasProperty(MCID::HasOptionalDef, Type);
449 }
450
451 /// Return true if this is a pseudo instruction that doesn't
452 /// correspond to a real machine instruction.
453 bool isPseudo(QueryType Type = IgnoreBundle) const {
454 return hasProperty(MCID::Pseudo, Type);
455 }
456
457 bool isReturn(QueryType Type = AnyInBundle) const {
458 return hasProperty(MCID::Return, Type);
459 }
460
461 bool isCall(QueryType Type = AnyInBundle) const {
462 return hasProperty(MCID::Call, Type);
463 }
464
465 /// Returns true if the specified instruction stops control flow
466 /// from executing the instruction immediately following it. Examples include
467 /// unconditional branches and return instructions.
468 bool isBarrier(QueryType Type = AnyInBundle) const {
469 return hasProperty(MCID::Barrier, Type);
470 }
471
472 /// Returns true if this instruction part of the terminator for a basic block.
473 /// Typically this is things like return and branch instructions.
474 ///
475 /// Various passes use this to insert code into the bottom of a basic block,
476 /// but before control flow occurs.
477 bool isTerminator(QueryType Type = AnyInBundle) const {
478 return hasProperty(MCID::Terminator, Type);
479 }
480
481 /// Returns true if this is a conditional, unconditional, or indirect branch.
482 /// Predicates below can be used to discriminate between
483 /// these cases, and the TargetInstrInfo::AnalyzeBranch method can be used to
484 /// get more information.
485 bool isBranch(QueryType Type = AnyInBundle) const {
486 return hasProperty(MCID::Branch, Type);
487 }
488
489 /// Return true if this is an indirect branch, such as a
490 /// branch through a register.
491 bool isIndirectBranch(QueryType Type = AnyInBundle) const {
492 return hasProperty(MCID::IndirectBranch, Type);
493 }
494
495 /// Return true if this is a branch which may fall
496 /// through to the next instruction or may transfer control flow to some other
497 /// block. The TargetInstrInfo::AnalyzeBranch method can be used to get more
498 /// information about this branch.
499 bool isConditionalBranch(QueryType Type = AnyInBundle) const {
500 return isBranch(Type) & !isBarrier(Type) & !isIndirectBranch(Type);
501 }
502
503 /// Return true if this is a branch which always
504 /// transfers control flow to some other block. The
505 /// TargetInstrInfo::AnalyzeBranch method can be used to get more information
506 /// about this branch.
507 bool isUnconditionalBranch(QueryType Type = AnyInBundle) const {
508 return isBranch(Type) & isBarrier(Type) & !isIndirectBranch(Type);
509 }
510
511 /// Return true if this instruction has a predicate operand that
512 /// controls execution. It may be set to 'always', or may be set to other
513 /// values. There are various methods in TargetInstrInfo that can be used to
514 /// control and modify the predicate in this instruction.
515 bool isPredicable(QueryType Type = AllInBundle) const {
516 // If it's a bundle than all bundled instructions must be predicable for this
517 // to return true.
518 return hasProperty(MCID::Predicable, Type);
519 }
520
521 /// Return true if this instruction is a comparison.
522 bool isCompare(QueryType Type = IgnoreBundle) const {
523 return hasProperty(MCID::Compare, Type);
524 }
525
526 /// Return true if this instruction is a move immediate
527 /// (including conditional moves) instruction.
528 bool isMoveImmediate(QueryType Type = IgnoreBundle) const {
529 return hasProperty(MCID::MoveImm, Type);
530 }
531
532 /// Return true if this instruction is a bitcast instruction.
533 bool isBitcast(QueryType Type = IgnoreBundle) const {
534 return hasProperty(MCID::Bitcast, Type);
535 }
536
537 /// Return true if this instruction is a select instruction.
538 bool isSelect(QueryType Type = IgnoreBundle) const {
539 return hasProperty(MCID::Select, Type);
540 }
541
542 /// Return true if this instruction cannot be safely duplicated.
543 /// For example, if the instruction has a unique labels attached
544 /// to it, duplicating it would cause multiple definition errors.
545 bool isNotDuplicable(QueryType Type = AnyInBundle) const {
546 return hasProperty(MCID::NotDuplicable, Type);
547 }
548
549 /// Return true if this instruction is convergent.
550 /// Convergent instructions can not be made control-dependent on any
551 /// additional values.
552 bool isConvergent(QueryType Type = AnyInBundle) const {
553 if (isInlineAsm()) {
554 unsigned ExtraInfo = getOperand(InlineAsm::MIOp_ExtraInfo).getImm();
555 if (ExtraInfo & InlineAsm::Extra_IsConvergent)
556 return true;
557 }
558 return hasProperty(MCID::Convergent, Type);
559 }
560
561 /// Returns true if the specified instruction has a delay slot
562 /// which must be filled by the code generator.
563 bool hasDelaySlot(QueryType Type = AnyInBundle) const {
564 return hasProperty(MCID::DelaySlot, Type);
565 }
566
567 /// Return true for instructions that can be folded as
568 /// memory operands in other instructions. The most common use for this
569 /// is instructions that are simple loads from memory that don't modify
570 /// the loaded value in any way, but it can also be used for instructions
571 /// that can be expressed as constant-pool loads, such as V_SETALLONES
572 /// on x86, to allow them to be folded when it is beneficial.
573 /// This should only be set on instructions that return a value in their
574 /// only virtual register definition.
575 bool canFoldAsLoad(QueryType Type = IgnoreBundle) const {
576 return hasProperty(MCID::FoldableAsLoad, Type);
577 }
578
579 /// \brief Return true if this instruction behaves
580 /// the same way as the generic REG_SEQUENCE instructions.
581 /// E.g., on ARM,
582 /// dX VMOVDRR rY, rZ
583 /// is equivalent to
584 /// dX = REG_SEQUENCE rY, ssub_0, rZ, ssub_1.
585 ///
586 /// Note that for the optimizers to be able to take advantage of
587 /// this property, TargetInstrInfo::getRegSequenceLikeInputs has to be
588 /// override accordingly.
589 bool isRegSequenceLike(QueryType Type = IgnoreBundle) const {
590 return hasProperty(MCID::RegSequence, Type);
591 }
592
593 /// \brief Return true if this instruction behaves
594 /// the same way as the generic EXTRACT_SUBREG instructions.
595 /// E.g., on ARM,
596 /// rX, rY VMOVRRD dZ
597 /// is equivalent to two EXTRACT_SUBREG:
598 /// rX = EXTRACT_SUBREG dZ, ssub_0
599 /// rY = EXTRACT_SUBREG dZ, ssub_1
600 ///
601 /// Note that for the optimizers to be able to take advantage of
602 /// this property, TargetInstrInfo::getExtractSubregLikeInputs has to be
603 /// override accordingly.
604 bool isExtractSubregLike(QueryType Type = IgnoreBundle) const {
605 return hasProperty(MCID::ExtractSubreg, Type);
606 }
607
608 /// \brief Return true if this instruction behaves
609 /// the same way as the generic INSERT_SUBREG instructions.
610 /// E.g., on ARM,
611 /// dX = VSETLNi32 dY, rZ, Imm
612 /// is equivalent to a INSERT_SUBREG:
613 /// dX = INSERT_SUBREG dY, rZ, translateImmToSubIdx(Imm)
614 ///
615 /// Note that for the optimizers to be able to take advantage of
616 /// this property, TargetInstrInfo::getInsertSubregLikeInputs has to be
617 /// override accordingly.
618 bool isInsertSubregLike(QueryType Type = IgnoreBundle) const {
619 return hasProperty(MCID::InsertSubreg, Type);
620 }
621
622 //===--------------------------------------------------------------------===//
623 // Side Effect Analysis
624 //===--------------------------------------------------------------------===//
625
626 /// Return true if this instruction could possibly read memory.
627 /// Instructions with this flag set are not necessarily simple load
628 /// instructions, they may load a value and modify it, for example.
629 bool mayLoad(QueryType Type = AnyInBundle) const {
630 if (isInlineAsm()) {
631 unsigned ExtraInfo = getOperand(InlineAsm::MIOp_ExtraInfo).getImm();
632 if (ExtraInfo & InlineAsm::Extra_MayLoad)
633 return true;
634 }
635 return hasProperty(MCID::MayLoad, Type);
636 }
637
638 /// Return true if this instruction could possibly modify memory.
639 /// Instructions with this flag set are not necessarily simple store
640 /// instructions, they may store a modified value based on their operands, or
641 /// may not actually modify anything, for example.
642 bool mayStore(QueryType Type = AnyInBundle) const {
643 if (isInlineAsm()) {
644 unsigned ExtraInfo = getOperand(InlineAsm::MIOp_ExtraInfo).getImm();
645 if (ExtraInfo & InlineAsm::Extra_MayStore)
646 return true;
647 }
648 return hasProperty(MCID::MayStore, Type);
649 }
650
651 /// Return true if this instruction could possibly read or modify memory.
652 bool mayLoadOrStore(QueryType Type = AnyInBundle) const {
653 return mayLoad(Type) || mayStore(Type);
654 }
655
656 //===--------------------------------------------------------------------===//
657 // Flags that indicate whether an instruction can be modified by a method.
658 //===--------------------------------------------------------------------===//
659
660 /// Return true if this may be a 2- or 3-address
661 /// instruction (of the form "X = op Y, Z, ..."), which produces the same
662 /// result if Y and Z are exchanged. If this flag is set, then the
663 /// TargetInstrInfo::commuteInstruction method may be used to hack on the
664 /// instruction.
665 ///
666 /// Note that this flag may be set on instructions that are only commutable
667 /// sometimes. In these cases, the call to commuteInstruction will fail.
668 /// Also note that some instructions require non-trivial modification to
669 /// commute them.
670 bool isCommutable(QueryType Type = IgnoreBundle) const {
671 return hasProperty(MCID::Commutable, Type);
672 }
673
674 /// Return true if this is a 2-address instruction
675 /// which can be changed into a 3-address instruction if needed. Doing this
676 /// transformation can be profitable in the register allocator, because it
677 /// means that the instruction can use a 2-address form if possible, but
678 /// degrade into a less efficient form if the source and dest register cannot
679 /// be assigned to the same register. For example, this allows the x86
680 /// backend to turn a "shl reg, 3" instruction into an LEA instruction, which
681 /// is the same speed as the shift but has bigger code size.
682 ///
683 /// If this returns true, then the target must implement the
684 /// TargetInstrInfo::convertToThreeAddress method for this instruction, which
685 /// is allowed to fail if the transformation isn't valid for this specific
686 /// instruction (e.g. shl reg, 4 on x86).
687 ///
688 bool isConvertibleTo3Addr(QueryType Type = IgnoreBundle) const {
689 return hasProperty(MCID::ConvertibleTo3Addr, Type);
690 }
691
692 /// Return true if this instruction requires
693 /// custom insertion support when the DAG scheduler is inserting it into a
694 /// machine basic block. If this is true for the instruction, it basically
695 /// means that it is a pseudo instruction used at SelectionDAG time that is
696 /// expanded out into magic code by the target when MachineInstrs are formed.
697 ///
698 /// If this is true, the TargetLoweringInfo::InsertAtEndOfBasicBlock method
699 /// is used to insert this into the MachineBasicBlock.
700 bool usesCustomInsertionHook(QueryType Type = IgnoreBundle) const {
701 return hasProperty(MCID::UsesCustomInserter, Type);
702 }
703
704 /// Return true if this instruction requires *adjustment*
705 /// after instruction selection by calling a target hook. For example, this
706 /// can be used to fill in ARM 's' optional operand depending on whether
707 /// the conditional flag register is used.
708 bool hasPostISelHook(QueryType Type = IgnoreBundle) const {
709 return hasProperty(MCID::HasPostISelHook, Type);
710 }
711
712 /// Returns true if this instruction is a candidate for remat.
713 /// This flag is deprecated, please don't use it anymore. If this
714 /// flag is set, the isReallyTriviallyReMaterializable() method is called to
715 /// verify the instruction is really rematable.
716 bool isRematerializable(QueryType Type = AllInBundle) const {
717 // It's only possible to re-mat a bundle if all bundled instructions are
718 // re-materializable.
719 return hasProperty(MCID::Rematerializable, Type);
720 }
721
722 /// Returns true if this instruction has the same cost (or less) than a move
723 /// instruction. This is useful during certain types of optimizations
724 /// (e.g., remat during two-address conversion or machine licm)
725 /// where we would like to remat or hoist the instruction, but not if it costs
726 /// more than moving the instruction into the appropriate register. Note, we
727 /// are not marking copies from and to the same register class with this flag.
728 bool isAsCheapAsAMove(QueryType Type = AllInBundle) const {
729 // Only returns true for a bundle if all bundled instructions are cheap.
730 return hasProperty(MCID::CheapAsAMove, Type);
731 }
732
733 /// Returns true if this instruction source operands
734 /// have special register allocation requirements that are not captured by the
735 /// operand register classes. e.g. ARM::STRD's two source registers must be an
736 /// even / odd pair, ARM::STM registers have to be in ascending order.
737 /// Post-register allocation passes should not attempt to change allocations
738 /// for sources of instructions with this flag.
739 bool hasExtraSrcRegAllocReq(QueryType Type = AnyInBundle) const {
740 return hasProperty(MCID::ExtraSrcRegAllocReq, Type);
741 }
742
743 /// Returns true if this instruction def operands
744 /// have special register allocation requirements that are not captured by the
745 /// operand register classes. e.g. ARM::LDRD's two def registers must be an
746 /// even / odd pair, ARM::LDM registers have to be in ascending order.
747 /// Post-register allocation passes should not attempt to change allocations
748 /// for definitions of instructions with this flag.
749 bool hasExtraDefRegAllocReq(QueryType Type = AnyInBundle) const {
750 return hasProperty(MCID::ExtraDefRegAllocReq, Type);
751 }
752
753 enum MICheckType {
754 CheckDefs, // Check all operands for equality
755 CheckKillDead, // Check all operands including kill / dead markers
756 IgnoreDefs, // Ignore all definitions
757 IgnoreVRegDefs // Ignore virtual register definitions
758 };
759
760 /// Return true if this instruction is identical to \p Other.
761 /// Two instructions are identical if they have the same opcode and all their
762 /// operands are identical (with respect to MachineOperand::isIdenticalTo()).
763 /// Note that this means liveness related flags (dead, undef, kill) do not
764 /// affect the notion of identical.
765 bool isIdenticalTo(const MachineInstr &Other,
766 MICheckType Check = CheckDefs) const;
767
768 /// Unlink 'this' from the containing basic block, and return it without
769 /// deleting it.
770 ///
771 /// This function can not be used on bundled instructions, use
772 /// removeFromBundle() to remove individual instructions from a bundle.
773 MachineInstr *removeFromParent();
774
775 /// Unlink this instruction from its basic block and return it without
776 /// deleting it.
777 ///
778 /// If the instruction is part of a bundle, the other instructions in the
779 /// bundle remain bundled.
780 MachineInstr *removeFromBundle();
781
782 /// Unlink 'this' from the containing basic block and delete it.
783 ///
784 /// If this instruction is the header of a bundle, the whole bundle is erased.
785 /// This function can not be used for instructions inside a bundle, use
786 /// eraseFromBundle() to erase individual bundled instructions.
787 void eraseFromParent();
788
789 /// Unlink 'this' from the containing basic block and delete it.
790 ///
791 /// For all definitions mark their uses in DBG_VALUE nodes
792 /// as undefined. Otherwise like eraseFromParent().
793 void eraseFromParentAndMarkDBGValuesForRemoval();
794
795 /// Unlink 'this' form its basic block and delete it.
796 ///
797 /// If the instruction is part of a bundle, the other instructions in the
798 /// bundle remain bundled.
799 void eraseFromBundle();
800
801 bool isEHLabel() const { return getOpcode() == TargetOpcode::EH_LABEL; }
802 bool isGCLabel() const { return getOpcode() == TargetOpcode::GC_LABEL; }
803 bool isAnnotationLabel() const {
804 return getOpcode() == TargetOpcode::ANNOTATION_LABEL;
805 }
806
807 /// Returns true if the MachineInstr represents a label.
808 bool isLabel() const {
809 return isEHLabel() || isGCLabel() || isAnnotationLabel();
810 }
811
812 bool isCFIInstruction() const {
813 return getOpcode() == TargetOpcode::CFI_INSTRUCTION;
814 }
815
816 // True if the instruction represents a position in the function.
817 bool isPosition() const { return isLabel() || isCFIInstruction(); }
818
819 bool isDebugValue() const { return getOpcode() == TargetOpcode::DBG_VALUE; }
820
821 /// A DBG_VALUE is indirect iff the first operand is a register and
822 /// the second operand is an immediate.
823 bool isIndirectDebugValue() const {
824 return isDebugValue()
825 && getOperand(0).isReg()
826 && getOperand(1).isImm();
827 }
828
829 bool isPHI() const {
830 return getOpcode() == TargetOpcode::PHI ||
831 getOpcode() == TargetOpcode::G_PHI;
832 }
833 bool isKill() const { return getOpcode() == TargetOpcode::KILL; }
834 bool isImplicitDef() const { return getOpcode()==TargetOpcode::IMPLICIT_DEF; }
835 bool isInlineAsm() const { return getOpcode() == TargetOpcode::INLINEASM; }
836
837 bool isMSInlineAsm() const {
838 return getOpcode() == TargetOpcode::INLINEASM && getInlineAsmDialect();
839 }
840
841 bool isStackAligningInlineAsm() const;
842 InlineAsm::AsmDialect getInlineAsmDialect() const;
843
844 bool isInsertSubreg() const {
845 return getOpcode() == TargetOpcode::INSERT_SUBREG;
846 }
847
848 bool isSubregToReg() const {
849 return getOpcode() == TargetOpcode::SUBREG_TO_REG;
34
Calling 'MachineInstr::getOpcode'
35
Returning from 'MachineInstr::getOpcode'
36
Assuming the condition is true
57
Calling 'MachineInstr::getOpcode'
58
Returning from 'MachineInstr::getOpcode'
59
Assuming the condition is false
850 }
851
852 bool isRegSequence() const {
853 return getOpcode() == TargetOpcode::REG_SEQUENCE;
854 }
855
856 bool isBundle() const {
857 return getOpcode() == TargetOpcode::BUNDLE;
858 }
859
860 bool isCopy() const {
861 return getOpcode() == TargetOpcode::COPY;
28
Calling 'MachineInstr::getOpcode'
29
Returning from 'MachineInstr::getOpcode'
30
Assuming the condition is false
51
Calling 'MachineInstr::getOpcode'
52
Returning from 'MachineInstr::getOpcode'
53
Assuming the condition is false
862 }
863
864 bool isFullCopy() const {
865 return isCopy() && !getOperand(0).getSubReg() && !getOperand(1).getSubReg();
866 }
867
868 bool isExtractSubreg() const {
869 return getOpcode() == TargetOpcode::EXTRACT_SUBREG;
870 }
871
872 /// Return true if the instruction behaves like a copy.
873 /// This does not include native copy instructions.
874 bool isCopyLike() const {
875 return isCopy() || isSubregToReg();
876 }
877
878 /// Return true is the instruction is an identity copy.
879 bool isIdentityCopy() const {
880 return isCopy() && getOperand(0).getReg() == getOperand(1).getReg() &&
881 getOperand(0).getSubReg() == getOperand(1).getSubReg();
882 }
883
884 /// Return true if this instruction doesn't produce any output in the form of
885 /// executable instructions.
886 bool isMetaInstruction() const {
887 switch (getOpcode()) {
888 default:
889 return false;
890 case TargetOpcode::IMPLICIT_DEF:
891 case TargetOpcode::KILL:
892 case TargetOpcode::CFI_INSTRUCTION:
893 case TargetOpcode::EH_LABEL:
894 case TargetOpcode::GC_LABEL:
895 case TargetOpcode::DBG_VALUE:
896 return true;
897 }
898 }
899
900 /// Return true if this is a transient instruction that is either very likely
901 /// to be eliminated during register allocation (such as copy-like
902 /// instructions), or if this instruction doesn't have an execution-time cost.
903 bool isTransient() const {
904 switch (getOpcode()) {
905 default:
906 return isMetaInstruction();
907 // Copy-like instructions are usually eliminated during register allocation.
908 case TargetOpcode::PHI:
909 case TargetOpcode::G_PHI:
910 case TargetOpcode::COPY:
911 case TargetOpcode::INSERT_SUBREG:
912 case TargetOpcode::SUBREG_TO_REG:
913 case TargetOpcode::REG_SEQUENCE:
914 return true;
915 }
916 }
917
918 /// Return the number of instructions inside the MI bundle, excluding the
919 /// bundle header.
920 ///
921 /// This is the number of instructions that MachineBasicBlock::iterator
922 /// skips, 0 for unbundled instructions.
923 unsigned getBundleSize() const;
924
925 /// Return true if the MachineInstr reads the specified register.
926 /// If TargetRegisterInfo is passed, then it also checks if there
927 /// is a read of a super-register.
928 /// This does not count partial redefines of virtual registers as reads:
929 /// %reg1024:6 = OP.
930 bool readsRegister(unsigned Reg,
931 const TargetRegisterInfo *TRI = nullptr) const {
932 return findRegisterUseOperandIdx(Reg, false, TRI) != -1;
933 }
934
935 /// Return true if the MachineInstr reads the specified virtual register.
936 /// Take into account that a partial define is a
937 /// read-modify-write operation.
938 bool readsVirtualRegister(unsigned Reg) const {
939 return readsWritesVirtualRegister(Reg).first;
940 }
941
942 /// Return a pair of bools (reads, writes) indicating if this instruction
943 /// reads or writes Reg. This also considers partial defines.
944 /// If Ops is not null, all operand indices for Reg are added.
945 std::pair<bool,bool> readsWritesVirtualRegister(unsigned Reg,
946 SmallVectorImpl<unsigned> *Ops = nullptr) const;
947
948 /// Return true if the MachineInstr kills the specified register.
949 /// If TargetRegisterInfo is passed, then it also checks if there is
950 /// a kill of a super-register.
951 bool killsRegister(unsigned Reg,
952 const TargetRegisterInfo *TRI = nullptr) const {
953 return findRegisterUseOperandIdx(Reg, true, TRI) != -1;
954 }
955
956 /// Return true if the MachineInstr fully defines the specified register.
957 /// If TargetRegisterInfo is passed, then it also checks
958 /// if there is a def of a super-register.
959 /// NOTE: It's ignoring subreg indices on virtual registers.
960 bool definesRegister(unsigned Reg,
961 const TargetRegisterInfo *TRI = nullptr) const {
962 return findRegisterDefOperandIdx(Reg, false, false, TRI) != -1;
963 }
964
965 /// Return true if the MachineInstr modifies (fully define or partially
966 /// define) the specified register.
967 /// NOTE: It's ignoring subreg indices on virtual registers.
968 bool modifiesRegister(unsigned Reg, const TargetRegisterInfo *TRI) const {
969 return findRegisterDefOperandIdx(Reg, false, true, TRI) != -1;
970 }
971
972 /// Returns true if the register is dead in this machine instruction.
973 /// If TargetRegisterInfo is passed, then it also checks
974 /// if there is a dead def of a super-register.
975 bool registerDefIsDead(unsigned Reg,
976 const TargetRegisterInfo *TRI = nullptr) const {
977 return findRegisterDefOperandIdx(Reg, true, false, TRI) != -1;
978 }
979
980 /// Returns true if the MachineInstr has an implicit-use operand of exactly
981 /// the given register (not considering sub/super-registers).
982 bool hasRegisterImplicitUseOperand(unsigned Reg) const;
983
984 /// Returns the operand index that is a use of the specific register or -1
985 /// if it is not found. It further tightens the search criteria to a use
986 /// that kills the register if isKill is true.
987 int findRegisterUseOperandIdx(unsigned Reg, bool isKill = false,
988 const TargetRegisterInfo *TRI = nullptr) const;
989
990 /// Wrapper for findRegisterUseOperandIdx, it returns
991 /// a pointer to the MachineOperand rather than an index.
992 MachineOperand *findRegisterUseOperand(unsigned Reg, bool isKill = false,
993 const TargetRegisterInfo *TRI = nullptr) {
994 int Idx = findRegisterUseOperandIdx(Reg, isKill, TRI);
995 return (Idx == -1) ? nullptr : &getOperand(Idx);
996 }
997
998 const MachineOperand *findRegisterUseOperand(
999 unsigned Reg, bool isKill = false,
1000 const TargetRegisterInfo *TRI = nullptr) const {
1001 return const_cast<MachineInstr *>(this)->
1002 findRegisterUseOperand(Reg, isKill, TRI);
1003 }
1004
1005 /// Returns the operand index that is a def of the specified register or
1006 /// -1 if it is not found. If isDead is true, defs that are not dead are
1007 /// skipped. If Overlap is true, then it also looks for defs that merely
1008 /// overlap the specified register. If TargetRegisterInfo is non-null,
1009 /// then it also checks if there is a def of a super-register.
1010 /// This may also return a register mask operand when Overlap is true.
1011 int findRegisterDefOperandIdx(unsigned Reg,
1012 bool isDead = false, bool Overlap = false,
1013 const TargetRegisterInfo *TRI = nullptr) const;
1014
1015 /// Wrapper for findRegisterDefOperandIdx, it returns
1016 /// a pointer to the MachineOperand rather than an index.
1017 MachineOperand *findRegisterDefOperand(unsigned Reg, bool isDead = false,
1018 const TargetRegisterInfo *TRI = nullptr) {
1019 int Idx = findRegisterDefOperandIdx(Reg, isDead, false, TRI);
1020 return (Idx == -1) ? nullptr : &getOperand(Idx);
1021 }
1022
1023 /// Find the index of the first operand in the
1024 /// operand list that is used to represent the predicate. It returns -1 if
1025 /// none is found.
1026 int findFirstPredOperandIdx() const;
1027
1028 /// Find the index of the flag word operand that
1029 /// corresponds to operand OpIdx on an inline asm instruction. Returns -1 if
1030 /// getOperand(OpIdx) does not belong to an inline asm operand group.
1031 ///
1032 /// If GroupNo is not NULL, it will receive the number of the operand group
1033 /// containing OpIdx.
1034 ///
1035 /// The flag operand is an immediate that can be decoded with methods like
1036 /// InlineAsm::hasRegClassConstraint().
1037 int findInlineAsmFlagIdx(unsigned OpIdx, unsigned *GroupNo = nullptr) const;
1038
1039 /// Compute the static register class constraint for operand OpIdx.
1040 /// For normal instructions, this is derived from the MCInstrDesc.
1041 /// For inline assembly it is derived from the flag words.
1042 ///
1043 /// Returns NULL if the static register class constraint cannot be
1044 /// determined.
1045 const TargetRegisterClass*
1046 getRegClassConstraint(unsigned OpIdx,
1047 const TargetInstrInfo *TII,
1048 const TargetRegisterInfo *TRI) const;
1049
1050 /// \brief Applies the constraints (def/use) implied by this MI on \p Reg to
1051 /// the given \p CurRC.
1052 /// If \p ExploreBundle is set and MI is part of a bundle, all the
1053 /// instructions inside the bundle will be taken into account. In other words,
1054 /// this method accumulates all the constraints of the operand of this MI and
1055 /// the related bundle if MI is a bundle or inside a bundle.
1056 ///
1057 /// Returns the register class that satisfies both \p CurRC and the
1058 /// constraints set by MI. Returns NULL if such a register class does not
1059 /// exist.
1060 ///
1061 /// \pre CurRC must not be NULL.
1062 const TargetRegisterClass *getRegClassConstraintEffectForVReg(
1063 unsigned Reg, const TargetRegisterClass *CurRC,
1064 const TargetInstrInfo *TII, const TargetRegisterInfo *TRI,
1065 bool ExploreBundle = false) const;
1066
1067 /// \brief Applies the constraints (def/use) implied by the \p OpIdx operand
1068 /// to the given \p CurRC.
1069 ///
1070 /// Returns the register class that satisfies both \p CurRC and the
1071 /// constraints set by \p OpIdx MI. Returns NULL if such a register class
1072 /// does not exist.
1073 ///
1074 /// \pre CurRC must not be NULL.
1075 /// \pre The operand at \p OpIdx must be a register.
1076 const TargetRegisterClass *
1077 getRegClassConstraintEffect(unsigned OpIdx, const TargetRegisterClass *CurRC,
1078 const TargetInstrInfo *TII,
1079 const TargetRegisterInfo *TRI) const;
1080
1081 /// Add a tie between the register operands at DefIdx and UseIdx.
1082 /// The tie will cause the register allocator to ensure that the two
1083 /// operands are assigned the same physical register.
1084 ///
1085 /// Tied operands are managed automatically for explicit operands in the
1086 /// MCInstrDesc. This method is for exceptional cases like inline asm.
1087 void tieOperands(unsigned DefIdx, unsigned UseIdx);
1088
1089 /// Given the index of a tied register operand, find the
1090 /// operand it is tied to. Defs are tied to uses and vice versa. Returns the
1091 /// index of the tied operand which must exist.
1092 unsigned findTiedOperandIdx(unsigned OpIdx) const;
1093
1094 /// Given the index of a register def operand,
1095 /// check if the register def is tied to a source operand, due to either
1096 /// two-address elimination or inline assembly constraints. Returns the
1097 /// first tied use operand index by reference if UseOpIdx is not null.
1098 bool isRegTiedToUseOperand(unsigned DefOpIdx,
1099 unsigned *UseOpIdx = nullptr) const {
1100 const MachineOperand &MO = getOperand(DefOpIdx);
1101 if (!MO.isReg() || !MO.isDef() || !MO.isTied())
1102 return false;
1103 if (UseOpIdx)
1104 *UseOpIdx = findTiedOperandIdx(DefOpIdx);
1105 return true;
1106 }
1107
1108 /// Return true if the use operand of the specified index is tied to a def
1109 /// operand. It also returns the def operand index by reference if DefOpIdx
1110 /// is not null.
1111 bool isRegTiedToDefOperand(unsigned UseOpIdx,
1112 unsigned *DefOpIdx = nullptr) const {
1113 const MachineOperand &MO = getOperand(UseOpIdx);
1114 if (!MO.isReg() || !MO.isUse() || !MO.isTied())
1115 return false;
1116 if (DefOpIdx)
1117 *DefOpIdx = findTiedOperandIdx(UseOpIdx);
1118 return true;
1119 }
1120
1121 /// Clears kill flags on all operands.
1122 void clearKillInfo();
1123
1124 /// Replace all occurrences of FromReg with ToReg:SubIdx,
1125 /// properly composing subreg indices where necessary.
1126 void substituteRegister(unsigned FromReg, unsigned ToReg, unsigned SubIdx,
1127 const TargetRegisterInfo &RegInfo);
1128
1129 /// We have determined MI kills a register. Look for the
1130 /// operand that uses it and mark it as IsKill. If AddIfNotFound is true,
1131 /// add a implicit operand if it's not found. Returns true if the operand
1132 /// exists / is added.
1133 bool addRegisterKilled(unsigned IncomingReg,
1134 const TargetRegisterInfo *RegInfo,
1135 bool AddIfNotFound = false);
1136
1137 /// Clear all kill flags affecting Reg. If RegInfo is provided, this includes
1138 /// all aliasing registers.
1139 void clearRegisterKills(unsigned Reg, const TargetRegisterInfo *RegInfo);
1140
1141 /// We have determined MI defined a register without a use.
1142 /// Look for the operand that defines it and mark it as IsDead. If
1143 /// AddIfNotFound is true, add a implicit operand if it's not found. Returns
1144 /// true if the operand exists / is added.
1145 bool addRegisterDead(unsigned Reg, const TargetRegisterInfo *RegInfo,
1146 bool AddIfNotFound = false);
1147
1148 /// Clear all dead flags on operands defining register @p Reg.
1149 void clearRegisterDeads(unsigned Reg);
1150
1151 /// Mark all subregister defs of register @p Reg with the undef flag.
1152 /// This function is used when we determined to have a subregister def in an
1153 /// otherwise undefined super register.
1154 void setRegisterDefReadUndef(unsigned Reg, bool IsUndef = true);
1155
1156 /// We have determined MI defines a register. Make sure there is an operand
1157 /// defining Reg.
1158 void addRegisterDefined(unsigned Reg,
1159 const TargetRegisterInfo *RegInfo = nullptr);
1160
1161 /// Mark every physreg used by this instruction as
1162 /// dead except those in the UsedRegs list.
1163 ///
1164 /// On instructions with register mask operands, also add implicit-def
1165 /// operands for all registers in UsedRegs.
1166 void setPhysRegsDeadExcept(ArrayRef<unsigned> UsedRegs,
1167 const TargetRegisterInfo &TRI);
1168
1169 /// Return true if it is safe to move this instruction. If
1170 /// SawStore is set to true, it means that there is a store (or call) between
1171 /// the instruction's location and its intended destination.
1172 bool isSafeToMove(AliasAnalysis *AA, bool &SawStore) const;
1173
1174 /// Returns true if this instruction's memory access aliases the memory
1175 /// access of Other.
1176 //
1177 /// Assumes any physical registers used to compute addresses
1178 /// have the same value for both instructions. Returns false if neither
1179 /// instruction writes to memory.
1180 ///
1181 /// @param AA Optional alias analysis, used to compare memory operands.
1182 /// @param Other MachineInstr to check aliasing against.
1183 /// @param UseTBAA Whether to pass TBAA information to alias analysis.
1184 bool mayAlias(AliasAnalysis *AA, MachineInstr &Other, bool UseTBAA);
1185
1186 /// Return true if this instruction may have an ordered
1187 /// or volatile memory reference, or if the information describing the memory
1188 /// reference is not available. Return false if it is known to have no
1189 /// ordered or volatile memory references.
1190 bool hasOrderedMemoryRef() const;
1191
1192 /// Return true if this load instruction never traps and points to a memory
1193 /// location whose value doesn't change during the execution of this function.
1194 ///
1195 /// Examples include loading a value from the constant pool or from the
1196 /// argument area of a function (if it does not change). If the instruction
1197 /// does multiple loads, this returns true only if all of the loads are
1198 /// dereferenceable and invariant.
1199 bool isDereferenceableInvariantLoad(AliasAnalysis *AA) const;
1200
1201 /// If the specified instruction is a PHI that always merges together the
1202 /// same virtual register, return the register, otherwise return 0.
1203 unsigned isConstantValuePHI() const;
1204
1205 /// Return true if this instruction has side effects that are not modeled
1206 /// by mayLoad / mayStore, etc.
1207 /// For all instructions, the property is encoded in MCInstrDesc::Flags
1208 /// (see MCInstrDesc::hasUnmodeledSideEffects(). The only exception is
1209 /// INLINEASM instruction, in which case the side effect property is encoded
1210 /// in one of its operands (see InlineAsm::Extra_HasSideEffect).
1211 ///
1212 bool hasUnmodeledSideEffects() const;
1213
1214 /// Returns true if it is illegal to fold a load across this instruction.
1215 bool isLoadFoldBarrier() const;
1216
1217 /// Return true if all the defs of this instruction are dead.
1218 bool allDefsAreDead() const;
1219
1220 /// Copy implicit register operands from specified
1221 /// instruction to this instruction.
1222 void copyImplicitOps(MachineFunction &MF, const MachineInstr &MI);
1223
1224 /// Debugging support
1225 /// @{
1226 /// Determine the generic type to be printed (if needed) on uses and defs.
1227 LLT getTypeToPrint(unsigned OpIdx, SmallBitVector &PrintedTypes,
1228 const MachineRegisterInfo &MRI) const;
1229
1230 /// Return true when an instruction has tied register that can't be determined
1231 /// by the instruction's descriptor. This is useful for MIR printing, to
1232 /// determine whether we need to print the ties or not.
1233 bool hasComplexRegisterTies() const;
1234
1235 /// Print this MI to \p OS.
1236 /// Only print the defs and the opcode if \p SkipOpers is true.
1237 /// Otherwise, also print operands if \p SkipDebugLoc is true.
1238 /// Otherwise, also print the debug loc, with a terminating newline.
1239 /// \p TII is used to print the opcode name. If it's not present, but the
1240 /// MI is in a function, the opcode will be printed using the function's TII.
1241 void print(raw_ostream &OS, bool SkipOpers = false, bool SkipDebugLoc = false,
1242 const TargetInstrInfo *TII = nullptr) const;
1243 void print(raw_ostream &OS, ModuleSlotTracker &MST, bool SkipOpers = false,
1244 bool SkipDebugLoc = false,
1245 const TargetInstrInfo *TII = nullptr) const;
1246 void dump() const;
1247 /// @}
1248
1249 //===--------------------------------------------------------------------===//
1250 // Accessors used to build up machine instructions.
1251
1252 /// Add the specified operand to the instruction. If it is an implicit
1253 /// operand, it is added to the end of the operand list. If it is an
1254 /// explicit operand it is added at the end of the explicit operand list
1255 /// (before the first implicit operand).
1256 ///
1257 /// MF must be the machine function that was used to allocate this
1258 /// instruction.
1259 ///
1260 /// MachineInstrBuilder provides a more convenient interface for creating
1261 /// instructions and adding operands.
1262 void addOperand(MachineFunction &MF, const MachineOperand &Op);
1263
1264 /// Add an operand without providing an MF reference. This only works for
1265 /// instructions that are inserted in a basic block.
1266 ///
1267 /// MachineInstrBuilder and the two-argument addOperand(MF, MO) should be
1268 /// preferred.
1269 void addOperand(const MachineOperand &Op);
1270
1271 /// Replace the instruction descriptor (thus opcode) of
1272 /// the current instruction with a new one.
1273 void setDesc(const MCInstrDesc &tid) { MCID = &tid; }
1274
1275 /// Replace current source information with new such.
1276 /// Avoid using this, the constructor argument is preferable.
1277 void setDebugLoc(DebugLoc dl) {
1278 debugLoc = std::move(dl);
1279 assert(debugLoc.hasTrivialDestructor() && "Expected trivial destructor")(static_cast <bool> (debugLoc.hasTrivialDestructor() &&
"Expected trivial destructor") ? void (0) : __assert_fail ("debugLoc.hasTrivialDestructor() && \"Expected trivial destructor\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/CodeGen/MachineInstr.h"
, 1279, __extension__ __PRETTY_FUNCTION__))
;
1280 }
1281
1282 /// Erase an operand from an instruction, leaving it with one
1283 /// fewer operand than it started with.
1284 void RemoveOperand(unsigned i);
1285
1286 /// Add a MachineMemOperand to the machine instruction.
1287 /// This function should be used only occasionally. The setMemRefs function
1288 /// is the primary method for setting up a MachineInstr's MemRefs list.
1289 void addMemOperand(MachineFunction &MF, MachineMemOperand *MO);
1290
1291 /// Assign this MachineInstr's memory reference descriptor list.
1292 /// This does not transfer ownership.
1293 void setMemRefs(mmo_iterator NewMemRefs, mmo_iterator NewMemRefsEnd) {
1294 setMemRefs(std::make_pair(NewMemRefs, NewMemRefsEnd-NewMemRefs));
1295 }
1296
1297 /// Assign this MachineInstr's memory reference descriptor list. First
1298 /// element in the pair is the begin iterator/pointer to the array; the
1299 /// second is the number of MemoryOperands. This does not transfer ownership
1300 /// of the underlying memory.
1301 void setMemRefs(std::pair<mmo_iterator, unsigned> NewMemRefs) {
1302 MemRefs = NewMemRefs.first;
1303 NumMemRefs = uint8_t(NewMemRefs.second);
1304 assert(NumMemRefs == NewMemRefs.second &&(static_cast <bool> (NumMemRefs == NewMemRefs.second &&
"Too many memrefs - must drop memory operands") ? void (0) :
__assert_fail ("NumMemRefs == NewMemRefs.second && \"Too many memrefs - must drop memory operands\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/CodeGen/MachineInstr.h"
, 1305, __extension__ __PRETTY_FUNCTION__))
1305 "Too many memrefs - must drop memory operands")(static_cast <bool> (NumMemRefs == NewMemRefs.second &&
"Too many memrefs - must drop memory operands") ? void (0) :
__assert_fail ("NumMemRefs == NewMemRefs.second && \"Too many memrefs - must drop memory operands\""
, "/build/llvm-toolchain-snapshot-6.0~svn321639/include/llvm/CodeGen/MachineInstr.h"
, 1305, __extension__ __PRETTY_FUNCTION__))
;
1306 }
1307
1308 /// Return a set of memrefs (begin iterator, size) which conservatively
1309 /// describe the memory behavior of both MachineInstrs. This is appropriate
1310 /// for use when merging two MachineInstrs into one. This routine does not
1311 /// modify the memrefs of the this MachineInstr.
1312 std::pair<mmo_iterator, unsigned> mergeMemRefsWith(const MachineInstr& Other);
1313
1314 /// Clear this MachineInstr's memory reference descriptor list. This resets
1315 /// the memrefs to their most conservative state. This should be used only
1316 /// as a last resort since it greatly pessimizes our knowledge of the memory
1317 /// access performed by the instruction.
1318 void dropMemRefs() {
1319 MemRefs = nullptr;
1320 NumMemRefs = 0;
1321 }
1322
1323 /// Break any tie involving OpIdx.
1324 void untieRegOperand(unsigned OpIdx) {
1325 MachineOperand &MO = getOperand(OpIdx);
1326 if (MO.isReg() && MO.isTied()) {
1327 getOperand(findTiedOperandIdx(OpIdx)).TiedTo = 0;
1328 MO.TiedTo = 0;
1329 }
1330 }
1331
1332 /// Add all implicit def and use operands to this instruction.
1333 void addImplicitDefUseOperands(MachineFunction &MF);
1334
1335private:
1336 /// If this instruction is embedded into a MachineFunction, return the
1337 /// MachineRegisterInfo object for the current function, otherwise
1338 /// return null.
1339 MachineRegisterInfo *getRegInfo();
1340
1341 /// Unlink all of the register operands in this instruction from their
1342 /// respective use lists. This requires that the operands already be on their
1343 /// use lists.
1344 void RemoveRegOperandsFromUseLists(MachineRegisterInfo&);
1345
1346 /// Add all of the register operands in this instruction from their
1347 /// respective use lists. This requires that the operands not be on their
1348 /// use lists yet.
1349 void AddRegOperandsToUseLists(MachineRegisterInfo&);
1350
1351 /// Slow path for hasProperty when we're dealing with a bundle.
1352 bool hasPropertyInBundle(unsigned Mask, QueryType Type) const;
1353
1354 /// \brief Implements the logic of getRegClassConstraintEffectForVReg for the
1355 /// this MI and the given operand index \p OpIdx.
1356 /// If the related operand does not constrained Reg, this returns CurRC.
1357 const TargetRegisterClass *getRegClassConstraintEffectForVRegImpl(
1358 unsigned OpIdx, unsigned Reg, const TargetRegisterClass *CurRC,
1359 const TargetInstrInfo *TII, const TargetRegisterInfo *TRI) const;
1360};
1361
1362/// Special DenseMapInfo traits to compare MachineInstr* by *value* of the
1363/// instruction rather than by pointer value.
1364/// The hashing and equality testing functions ignore definitions so this is
1365/// useful for CSE, etc.
1366struct MachineInstrExpressionTrait : DenseMapInfo<MachineInstr*> {
1367 static inline MachineInstr *getEmptyKey() {
1368 return nullptr;
1369 }
1370
1371 static inline MachineInstr *getTombstoneKey() {
1372 return reinterpret_cast<MachineInstr*>(-1);
1373 }
1374
1375 static unsigned getHashValue(const MachineInstr* const &MI);
1376
1377 static bool isEqual(const MachineInstr* const &LHS,
1378 const MachineInstr* const &RHS) {
1379 if (RHS == getEmptyKey() || RHS == getTombstoneKey() ||
1380 LHS == getEmptyKey() || LHS == getTombstoneKey())
1381 return LHS == RHS;
1382 return LHS->isIdenticalTo(*RHS, MachineInstr::IgnoreVRegDefs);
1383 }
1384};
1385
1386//===----------------------------------------------------------------------===//
1387// Debugging Support
1388
1389inline raw_ostream& operator<<(raw_ostream &OS, const MachineInstr &MI) {
1390 MI.print(OS);
1391 return OS;
1392}
1393
1394} // end namespace llvm
1395
1396#endif // LLVM_CODEGEN_MACHINEINSTR_H