Bug Summary

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

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name RegisterCoalescer.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-eagerly-assume -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-7/lib/clang/7.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-7~svn329677/lib/CodeGen -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn329677/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0/backward -internal-isystem /usr/include/clang/7.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-7/lib/clang/7.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/lib/CodeGen -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-checker optin.performance.Padding -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-04-11-031539-24776-1 -x c++ /build/llvm-toolchain-snapshot-7~svn329677/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()) {
26
Taking false branch
40
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()) {
27
Taking true branch
41
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;
42
Returning without writing to 'Src'
326 return true;
28
Returning without writing to 'Src'
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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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 (almost sure it's) ok to move copy.
993 if (CopyLeftBB) {
994 // Position in CopyLeftBB where we should insert new copy.
995 auto InsPos = CopyLeftBB->getFirstTerminator();
996
997 // Make sure that B isn't referenced in the terminators (if any) at the end
998 // of the predecessor since we're about to insert a new definition of B
999 // before them.
1000 if (InsPos != CopyLeftBB->end()) {
1001 SlotIndex InsPosIdx = LIS->getInstructionIndex(*InsPos).getRegSlot(true);
1002 if (IntB.overlaps(InsPosIdx, LIS->getMBBEndIdx(CopyLeftBB)))
1003 return false;
1004 }
1005
1006 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)
1007 << printMBBReference(*CopyLeftBB) << '\t' << CopyMI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tremovePartialRedundancy: Move the copy to "
<< printMBBReference(*CopyLeftBB) << '\t' <<
CopyMI; } } while (false)
;
1008
1009 // Insert new copy to CopyLeftBB.
1010 MachineInstr *NewCopyMI = BuildMI(*CopyLeftBB, InsPos, CopyMI.getDebugLoc(),
1011 TII->get(TargetOpcode::COPY), IntB.reg)
1012 .addReg(IntA.reg);
1013 SlotIndex NewCopyIdx =
1014 LIS->InsertMachineInstrInMaps(*NewCopyMI).getRegSlot();
1015 IntB.createDeadDef(NewCopyIdx, LIS->getVNInfoAllocator());
1016 for (LiveInterval::SubRange &SR : IntB.subranges())
1017 SR.createDeadDef(NewCopyIdx, LIS->getVNInfoAllocator());
1018
1019 // If the newly created Instruction has an address of an instruction that was
1020 // deleted before (object recycled by the allocator) it needs to be removed from
1021 // the deleted list.
1022 ErasedInstrs.erase(NewCopyMI);
1023 } else {
1024 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)
1025 << printMBBReference(MBB) << '\t' << CopyMI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tremovePartialRedundancy: Remove the copy from "
<< printMBBReference(MBB) << '\t' << CopyMI
; } } while (false)
;
1026 }
1027
1028 // Remove CopyMI.
1029 // Note: This is fine to remove the copy before updating the live-ranges.
1030 // While updating the live-ranges, we only look at slot indices and
1031 // never go back to the instruction.
1032 // Mark instructions as deleted.
1033 deleteInstr(&CopyMI);
1034
1035 // Update the liveness.
1036 SmallVector<SlotIndex, 8> EndPoints;
1037 VNInfo *BValNo = IntB.Query(CopyIdx).valueOutOrDead();
1038 LIS->pruneValue(*static_cast<LiveRange *>(&IntB), CopyIdx.getRegSlot(),
1039 &EndPoints);
1040 BValNo->markUnused();
1041 // Extend IntB to the EndPoints of its original live interval.
1042 LIS->extendToIndices(IntB, EndPoints);
1043
1044 // Now, do the same for its subranges.
1045 for (LiveInterval::SubRange &SR : IntB.subranges()) {
1046 EndPoints.clear();
1047 VNInfo *BValNo = SR.Query(CopyIdx).valueOutOrDead();
1048 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 1048, __extension__ __PRETTY_FUNCTION__))
;
1049 LIS->pruneValue(SR, CopyIdx.getRegSlot(), &EndPoints);
1050 BValNo->markUnused();
1051 LIS->extendToIndices(SR, EndPoints);
1052 }
1053
1054 // Finally, update the live-range of IntA.
1055 shrinkToUses(&IntA);
1056 return true;
1057}
1058
1059/// Returns true if @p MI defines the full vreg @p Reg, as opposed to just
1060/// defining a subregister.
1061static bool definesFullReg(const MachineInstr &MI, unsigned Reg) {
1062 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 1063, __extension__ __PRETTY_FUNCTION__))
1063 "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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 1063, __extension__ __PRETTY_FUNCTION__))
;
1064 for (const MachineOperand &Op : MI.operands()) {
1065 if (!Op.isReg() || !Op.isDef() || Op.getReg() != Reg)
1066 continue;
1067 // Return true if we define the full register or don't care about the value
1068 // inside other subregisters.
1069 if (Op.getSubReg() == 0 || Op.isUndef())
1070 return true;
1071 }
1072 return false;
1073}
1074
1075bool RegisterCoalescer::reMaterializeTrivialDef(const CoalescerPair &CP,
1076 MachineInstr *CopyMI,
1077 bool &IsDefCopy) {
1078 IsDefCopy = false;
1079 unsigned SrcReg = CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg();
1080 unsigned SrcIdx = CP.isFlipped() ? CP.getDstIdx() : CP.getSrcIdx();
1081 unsigned DstReg = CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg();
1082 unsigned DstIdx = CP.isFlipped() ? CP.getSrcIdx() : CP.getDstIdx();
1083 if (TargetRegisterInfo::isPhysicalRegister(SrcReg))
1084 return false;
1085
1086 LiveInterval &SrcInt = LIS->getInterval(SrcReg);
1087 SlotIndex CopyIdx = LIS->getInstructionIndex(*CopyMI);
1088 VNInfo *ValNo = SrcInt.Query(CopyIdx).valueIn();
1089 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 1089, __extension__ __PRETTY_FUNCTION__))
;
1090 if (ValNo->isPHIDef() || ValNo->isUnused())
1091 return false;
1092 MachineInstr *DefMI = LIS->getInstructionFromIndex(ValNo->def);
1093 if (!DefMI)
1094 return false;
1095 if (DefMI->isCopyLike()) {
1096 IsDefCopy = true;
1097 return false;
1098 }
1099 if (!TII->isAsCheapAsAMove(*DefMI))
1100 return false;
1101 if (!TII->isTriviallyReMaterializable(*DefMI, AA))
1102 return false;
1103 if (!definesFullReg(*DefMI, SrcReg))
1104 return false;
1105 bool SawStore = false;
1106 if (!DefMI->isSafeToMove(AA, SawStore))
1107 return false;
1108 const MCInstrDesc &MCID = DefMI->getDesc();
1109 if (MCID.getNumDefs() != 1)
1110 return false;
1111 // Only support subregister destinations when the def is read-undef.
1112 MachineOperand &DstOperand = CopyMI->getOperand(0);
1113 unsigned CopyDstReg = DstOperand.getReg();
1114 if (DstOperand.getSubReg() && !DstOperand.isUndef())
1115 return false;
1116
1117 // If both SrcIdx and DstIdx are set, correct rematerialization would widen
1118 // the register substantially (beyond both source and dest size). This is bad
1119 // for performance since it can cascade through a function, introducing many
1120 // extra spills and fills (e.g. ARM can easily end up copying QQQQPR registers
1121 // around after a few subreg copies).
1122 if (SrcIdx && DstIdx)
1123 return false;
1124
1125 const TargetRegisterClass *DefRC = TII->getRegClass(MCID, 0, TRI, *MF);
1126 if (!DefMI->isImplicitDef()) {
1127 if (TargetRegisterInfo::isPhysicalRegister(DstReg)) {
1128 unsigned NewDstReg = DstReg;
1129
1130 unsigned NewDstIdx = TRI->composeSubRegIndices(CP.getSrcIdx(),
1131 DefMI->getOperand(0).getSubReg());
1132 if (NewDstIdx)
1133 NewDstReg = TRI->getSubReg(DstReg, NewDstIdx);
1134
1135 // Finally, make sure that the physical subregister that will be
1136 // constructed later is permitted for the instruction.
1137 if (!DefRC->contains(NewDstReg))
1138 return false;
1139 } else {
1140 // Theoretically, some stack frame reference could exist. Just make sure
1141 // it hasn't actually happened.
1142 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 1143, __extension__ __PRETTY_FUNCTION__))
1143 "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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 1143, __extension__ __PRETTY_FUNCTION__))
;
1144 }
1145 }
1146
1147 DebugLoc DL = CopyMI->getDebugLoc();
1148 MachineBasicBlock *MBB = CopyMI->getParent();
1149 MachineBasicBlock::iterator MII =
1150 std::next(MachineBasicBlock::iterator(CopyMI));
1151 TII->reMaterialize(*MBB, MII, DstReg, SrcIdx, *DefMI, *TRI);
1152 MachineInstr &NewMI = *std::prev(MII);
1153 NewMI.setDebugLoc(DL);
1154
1155 // In a situation like the following:
1156 // %0:subreg = instr ; DefMI, subreg = DstIdx
1157 // %1 = copy %0:subreg ; CopyMI, SrcIdx = 0
1158 // instead of widening %1 to the register class of %0 simply do:
1159 // %1 = instr
1160 const TargetRegisterClass *NewRC = CP.getNewRC();
1161 if (DstIdx != 0) {
1162 MachineOperand &DefMO = NewMI.getOperand(0);
1163 if (DefMO.getSubReg() == DstIdx) {
1164 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 1165, __extension__ __PRETTY_FUNCTION__))
1165 && "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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 1165, __extension__ __PRETTY_FUNCTION__))
;
1166 const TargetRegisterClass *DstRC = MRI->getRegClass(DstReg);
1167 const TargetRegisterClass *CommonRC =
1168 TRI->getCommonSubClass(DefRC, DstRC);
1169 if (CommonRC != nullptr) {
1170 NewRC = CommonRC;
1171 DstIdx = 0;
1172 DefMO.setSubReg(0);
1173 DefMO.setIsUndef(false); // Only subregs can have def+undef.
1174 }
1175 }
1176 }
1177
1178 // CopyMI may have implicit operands, save them so that we can transfer them
1179 // over to the newly materialized instruction after CopyMI is removed.
1180 SmallVector<MachineOperand, 4> ImplicitOps;
1181 ImplicitOps.reserve(CopyMI->getNumOperands() -
1182 CopyMI->getDesc().getNumOperands());
1183 for (unsigned I = CopyMI->getDesc().getNumOperands(),
1184 E = CopyMI->getNumOperands();
1185 I != E; ++I) {
1186 MachineOperand &MO = CopyMI->getOperand(I);
1187 if (MO.isReg()) {
1188 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 1188, __extension__ __PRETTY_FUNCTION__))
;
1189 // Discard VReg implicit defs.
1190 if (TargetRegisterInfo::isPhysicalRegister(MO.getReg()))
1191 ImplicitOps.push_back(MO);
1192 }
1193 }
1194
1195 LIS->ReplaceMachineInstrInMaps(*CopyMI, NewMI);
1196 CopyMI->eraseFromParent();
1197 ErasedInstrs.insert(CopyMI);
1198
1199 // NewMI may have dead implicit defs (E.g. EFLAGS for MOV<bits>r0 on X86).
1200 // We need to remember these so we can add intervals once we insert
1201 // NewMI into SlotIndexes.
1202 SmallVector<unsigned, 4> NewMIImplDefs;
1203 for (unsigned i = NewMI.getDesc().getNumOperands(),
1204 e = NewMI.getNumOperands();
1205 i != e; ++i) {
1206 MachineOperand &MO = NewMI.getOperand(i);
1207 if (MO.isReg() && MO.isDef()) {
1208 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 1209, __extension__ __PRETTY_FUNCTION__))
1209 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 1209, __extension__ __PRETTY_FUNCTION__))
;
1210 NewMIImplDefs.push_back(MO.getReg());
1211 }
1212 }
1213
1214 if (TargetRegisterInfo::isVirtualRegister(DstReg)) {
1215 unsigned NewIdx = NewMI.getOperand(0).getSubReg();
1216
1217 if (DefRC != nullptr) {
1218 if (NewIdx)
1219 NewRC = TRI->getMatchingSuperRegClass(NewRC, DefRC, NewIdx);
1220 else
1221 NewRC = TRI->getCommonSubClass(NewRC, DefRC);
1222 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 1222, __extension__ __PRETTY_FUNCTION__))
;
1223 }
1224 // Remap subranges to new lanemask and change register class.
1225 LiveInterval &DstInt = LIS->getInterval(DstReg);
1226 for (LiveInterval::SubRange &SR : DstInt.subranges()) {
1227 SR.LaneMask = TRI->composeSubRegIndexLaneMask(DstIdx, SR.LaneMask);
1228 }
1229 MRI->setRegClass(DstReg, NewRC);
1230
1231 // Update machine operands and add flags.
1232 updateRegDefsUses(DstReg, DstReg, DstIdx);
1233 NewMI.getOperand(0).setSubReg(NewIdx);
1234 // Add dead subregister definitions if we are defining the whole register
1235 // but only part of it is live.
1236 // This could happen if the rematerialization instruction is rematerializing
1237 // more than actually is used in the register.
1238 // An example would be:
1239 // %1 = LOAD CONSTANTS 5, 8 ; Loading both 5 and 8 in different subregs
1240 // ; Copying only part of the register here, but the rest is undef.
1241 // %2:sub_16bit<def, read-undef> = COPY %1:sub_16bit
1242 // ==>
1243 // ; Materialize all the constants but only using one
1244 // %2 = LOAD_CONSTANTS 5, 8
1245 //
1246 // at this point for the part that wasn't defined before we could have
1247 // subranges missing the definition.
1248 if (NewIdx == 0 && DstInt.hasSubRanges()) {
1249 SlotIndex CurrIdx = LIS->getInstructionIndex(NewMI);
1250 SlotIndex DefIndex =
1251 CurrIdx.getRegSlot(NewMI.getOperand(0).isEarlyClobber());
1252 LaneBitmask MaxMask = MRI->getMaxLaneMaskForVReg(DstReg);
1253 VNInfo::Allocator& Alloc = LIS->getVNInfoAllocator();
1254 for (LiveInterval::SubRange &SR : DstInt.subranges()) {
1255 if (!SR.liveAt(DefIndex))
1256 SR.createDeadDef(DefIndex, Alloc);
1257 MaxMask &= ~SR.LaneMask;
1258 }
1259 if (MaxMask.any()) {
1260 LiveInterval::SubRange *SR = DstInt.createSubRange(Alloc, MaxMask);
1261 SR->createDeadDef(DefIndex, Alloc);
1262 }
1263 }
1264
1265 // Make sure that the subrange for resultant undef is removed
1266 // For example:
1267 // %1:sub1<def,read-undef> = LOAD CONSTANT 1
1268 // %2 = COPY %1
1269 // ==>
1270 // %2:sub1<def, read-undef> = LOAD CONSTANT 1
1271 // ; Correct but need to remove the subrange for %2:sub0
1272 // ; as it is now undef
1273 if (NewIdx != 0 && DstInt.hasSubRanges()) {
1274 // The affected subregister segments can be removed.
1275 SlotIndex CurrIdx = LIS->getInstructionIndex(NewMI);
1276 LaneBitmask DstMask = TRI->getSubRegIndexLaneMask(NewIdx);
1277 bool UpdatedSubRanges = false;
1278 for (LiveInterval::SubRange &SR : DstInt.subranges()) {
1279 if ((SR.LaneMask & DstMask).none()) {
1280 DEBUG(dbgs() << "Removing undefined SubRange "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Removing undefined SubRange "
<< PrintLaneMask(SR.LaneMask) << " : " << SR
<< "\n"; } } while (false)
1281 << PrintLaneMask(SR.LaneMask) << " : " << SR << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Removing undefined SubRange "
<< PrintLaneMask(SR.LaneMask) << " : " << SR
<< "\n"; } } while (false)
;
1282 // VNI is in ValNo - remove any segments in this SubRange that have this ValNo
1283 if (VNInfo *RmValNo = SR.getVNInfoAt(CurrIdx.getRegSlot())) {
1284 SR.removeValNo(RmValNo);
1285 UpdatedSubRanges = true;
1286 }
1287 }
1288 }
1289 if (UpdatedSubRanges)
1290 DstInt.removeEmptySubRanges();
1291 }
1292 } else if (NewMI.getOperand(0).getReg() != CopyDstReg) {
1293 // The New instruction may be defining a sub-register of what's actually
1294 // been asked for. If so it must implicitly define the whole thing.
1295 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 1296, __extension__ __PRETTY_FUNCTION__))
1296 "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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 1296, __extension__ __PRETTY_FUNCTION__))
;
1297 NewMI.getOperand(0).setIsDead(true);
1298 NewMI.addOperand(MachineOperand::CreateReg(
1299 CopyDstReg, true /*IsDef*/, true /*IsImp*/, false /*IsKill*/));
1300 // Record small dead def live-ranges for all the subregisters
1301 // of the destination register.
1302 // Otherwise, variables that live through may miss some
1303 // interferences, thus creating invalid allocation.
1304 // E.g., i386 code:
1305 // %1 = somedef ; %1 GR8
1306 // %2 = remat ; %2 GR32
1307 // CL = COPY %2.sub_8bit
1308 // = somedef %1 ; %1 GR8
1309 // =>
1310 // %1 = somedef ; %1 GR8
1311 // dead ECX = remat ; implicit-def CL
1312 // = somedef %1 ; %1 GR8
1313 // %1 will see the inteferences with CL but not with CH since
1314 // no live-ranges would have been created for ECX.
1315 // Fix that!
1316 SlotIndex NewMIIdx = LIS->getInstructionIndex(NewMI);
1317 for (MCRegUnitIterator Units(NewMI.getOperand(0).getReg(), TRI);
1318 Units.isValid(); ++Units)
1319 if (LiveRange *LR = LIS->getCachedRegUnit(*Units))
1320 LR->createDeadDef(NewMIIdx.getRegSlot(), LIS->getVNInfoAllocator());
1321 }
1322
1323 if (NewMI.getOperand(0).getSubReg())
1324 NewMI.getOperand(0).setIsUndef();
1325
1326 // Transfer over implicit operands to the rematerialized instruction.
1327 for (MachineOperand &MO : ImplicitOps)
1328 NewMI.addOperand(MO);
1329
1330 SlotIndex NewMIIdx = LIS->getInstructionIndex(NewMI);
1331 for (unsigned i = 0, e = NewMIImplDefs.size(); i != e; ++i) {
1332 unsigned Reg = NewMIImplDefs[i];
1333 for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units)
1334 if (LiveRange *LR = LIS->getCachedRegUnit(*Units))
1335 LR->createDeadDef(NewMIIdx.getRegSlot(), LIS->getVNInfoAllocator());
1336 }
1337
1338 DEBUG(dbgs() << "Remat: " << NewMI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Remat: " << NewMI; } }
while (false)
;
1339 ++NumReMats;
1340
1341 // The source interval can become smaller because we removed a use.
1342 shrinkToUses(&SrcInt, &DeadDefs);
1343 if (!DeadDefs.empty()) {
1344 // If the virtual SrcReg is completely eliminated, update all DBG_VALUEs
1345 // to describe DstReg instead.
1346 for (MachineOperand &UseMO : MRI->use_operands(SrcReg)) {
1347 MachineInstr *UseMI = UseMO.getParent();
1348 if (UseMI->isDebugValue()) {
1349 UseMO.setReg(DstReg);
1350 // Move the debug value directly after the def of the rematerialized
1351 // value in DstReg.
1352 MBB->splice(std::next(NewMI.getIterator()), UseMI->getParent(), UseMI);
1353 DEBUG(dbgs() << "\t\tupdated: " << *UseMI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tupdated: " << *UseMI
; } } while (false)
;
1354 }
1355 }
1356 eliminateDeadDefs();
1357 }
1358
1359 return true;
1360}
1361
1362bool RegisterCoalescer::eliminateUndefCopy(MachineInstr *CopyMI) {
1363 // ProcessImpicitDefs may leave some copies of <undef> values, it only removes
1364 // local variables. When we have a copy like:
1365 //
1366 // %1 = COPY undef %2
1367 //
1368 // We delete the copy and remove the corresponding value number from %1.
1369 // Any uses of that value number are marked as <undef>.
1370
1371 // Note that we do not query CoalescerPair here but redo isMoveInstr as the
1372 // CoalescerPair may have a new register class with adjusted subreg indices
1373 // at this point.
1374 unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx;
1375 isMoveInstr(*TRI, CopyMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx);
1376
1377 SlotIndex Idx = LIS->getInstructionIndex(*CopyMI);
1378 const LiveInterval &SrcLI = LIS->getInterval(SrcReg);
1379 // CopyMI is undef iff SrcReg is not live before the instruction.
1380 if (SrcSubIdx != 0 && SrcLI.hasSubRanges()) {
1381 LaneBitmask SrcMask = TRI->getSubRegIndexLaneMask(SrcSubIdx);
1382 for (const LiveInterval::SubRange &SR : SrcLI.subranges()) {
1383 if ((SR.LaneMask & SrcMask).none())
1384 continue;
1385 if (SR.liveAt(Idx))
1386 return false;
1387 }
1388 } else if (SrcLI.liveAt(Idx))
1389 return false;
1390
1391 DEBUG(dbgs() << "\tEliminating copy of <undef> value\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tEliminating copy of <undef> value\n"
; } } while (false)
;
1392
1393 // Remove any DstReg segments starting at the instruction.
1394 LiveInterval &DstLI = LIS->getInterval(DstReg);
1395 SlotIndex RegIndex = Idx.getRegSlot();
1396 // Remove value or merge with previous one in case of a subregister def.
1397 if (VNInfo *PrevVNI = DstLI.getVNInfoAt(Idx)) {
1398 VNInfo *VNI = DstLI.getVNInfoAt(RegIndex);
1399 DstLI.MergeValueNumberInto(VNI, PrevVNI);
1400
1401 // The affected subregister segments can be removed.
1402 LaneBitmask DstMask = TRI->getSubRegIndexLaneMask(DstSubIdx);
1403 for (LiveInterval::SubRange &SR : DstLI.subranges()) {
1404 if ((SR.LaneMask & DstMask).none())
1405 continue;
1406
1407 VNInfo *SVNI = SR.getVNInfoAt(RegIndex);
1408 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 1408, __extension__ __PRETTY_FUNCTION__))
;
1409 SR.removeValNo(SVNI);
1410 }
1411 DstLI.removeEmptySubRanges();
1412 } else
1413 LIS->removeVRegDefAt(DstLI, RegIndex);
1414
1415 // Mark uses as undef.
1416 for (MachineOperand &MO : MRI->reg_nodbg_operands(DstReg)) {
1417 if (MO.isDef() /*|| MO.isUndef()*/)
1418 continue;
1419 const MachineInstr &MI = *MO.getParent();
1420 SlotIndex UseIdx = LIS->getInstructionIndex(MI);
1421 LaneBitmask UseMask = TRI->getSubRegIndexLaneMask(MO.getSubReg());
1422 bool isLive;
1423 if (!UseMask.all() && DstLI.hasSubRanges()) {
1424 isLive = false;
1425 for (const LiveInterval::SubRange &SR : DstLI.subranges()) {
1426 if ((SR.LaneMask & UseMask).none())
1427 continue;
1428 if (SR.liveAt(UseIdx)) {
1429 isLive = true;
1430 break;
1431 }
1432 }
1433 } else
1434 isLive = DstLI.liveAt(UseIdx);
1435 if (isLive)
1436 continue;
1437 MO.setIsUndef(true);
1438 DEBUG(dbgs() << "\tnew undef: " << UseIdx << '\t' << MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tnew undef: " << UseIdx
<< '\t' << MI; } } while (false)
;
1439 }
1440
1441 // A def of a subregister may be a use of the other subregisters, so
1442 // deleting a def of a subregister may also remove uses. Since CopyMI
1443 // is still part of the function (but about to be erased), mark all
1444 // defs of DstReg in it as <undef>, so that shrinkToUses would
1445 // ignore them.
1446 for (MachineOperand &MO : CopyMI->operands())
1447 if (MO.isReg() && MO.isDef() && MO.getReg() == DstReg)
1448 MO.setIsUndef(true);
1449 LIS->shrinkToUses(&DstLI);
1450
1451 return true;
1452}
1453
1454void RegisterCoalescer::addUndefFlag(const LiveInterval &Int, SlotIndex UseIdx,
1455 MachineOperand &MO, unsigned SubRegIdx) {
1456 LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubRegIdx);
1457 if (MO.isDef())
1458 Mask = ~Mask;
1459 bool IsUndef = true;
1460 for (const LiveInterval::SubRange &S : Int.subranges()) {
1461 if ((S.LaneMask & Mask).none())
1462 continue;
1463 if (S.liveAt(UseIdx)) {
1464 IsUndef = false;
1465 break;
1466 }
1467 }
1468 if (IsUndef) {
1469 MO.setIsUndef(true);
1470 // We found out some subregister use is actually reading an undefined
1471 // value. In some cases the whole vreg has become undefined at this
1472 // point so we have to potentially shrink the main range if the
1473 // use was ending a live segment there.
1474 LiveQueryResult Q = Int.Query(UseIdx);
1475 if (Q.valueOut() == nullptr)
1476 ShrinkMainRange = true;
1477 }
1478}
1479
1480void RegisterCoalescer::updateRegDefsUses(unsigned SrcReg,
1481 unsigned DstReg,
1482 unsigned SubIdx) {
1483 bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
1484 LiveInterval *DstInt = DstIsPhys ? nullptr : &LIS->getInterval(DstReg);
1485
1486 if (DstInt && DstInt->hasSubRanges() && DstReg != SrcReg) {
1487 for (MachineOperand &MO : MRI->reg_operands(DstReg)) {
1488 unsigned SubReg = MO.getSubReg();
1489 if (SubReg == 0 || MO.isUndef())
1490 continue;
1491 MachineInstr &MI = *MO.getParent();
1492 if (MI.isDebugValue())
1493 continue;
1494 SlotIndex UseIdx = LIS->getInstructionIndex(MI).getRegSlot(true);
1495 addUndefFlag(*DstInt, UseIdx, MO, SubReg);
1496 }
1497 }
1498
1499 SmallPtrSet<MachineInstr*, 8> Visited;
1500 for (MachineRegisterInfo::reg_instr_iterator
1501 I = MRI->reg_instr_begin(SrcReg), E = MRI->reg_instr_end();
1502 I != E; ) {
1503 MachineInstr *UseMI = &*(I++);
1504
1505 // Each instruction can only be rewritten once because sub-register
1506 // composition is not always idempotent. When SrcReg != DstReg, rewriting
1507 // the UseMI operands removes them from the SrcReg use-def chain, but when
1508 // SrcReg is DstReg we could encounter UseMI twice if it has multiple
1509 // operands mentioning the virtual register.
1510 if (SrcReg == DstReg && !Visited.insert(UseMI).second)
1511 continue;
1512
1513 SmallVector<unsigned,8> Ops;
1514 bool Reads, Writes;
1515 std::tie(Reads, Writes) = UseMI->readsWritesVirtualRegister(SrcReg, &Ops);
1516
1517 // If SrcReg wasn't read, it may still be the case that DstReg is live-in
1518 // because SrcReg is a sub-register.
1519 if (DstInt && !Reads && SubIdx && !UseMI->isDebugValue())
1520 Reads = DstInt->liveAt(LIS->getInstructionIndex(*UseMI));
1521
1522 // Replace SrcReg with DstReg in all UseMI operands.
1523 for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
1524 MachineOperand &MO = UseMI->getOperand(Ops[i]);
1525
1526 // Adjust <undef> flags in case of sub-register joins. We don't want to
1527 // turn a full def into a read-modify-write sub-register def and vice
1528 // versa.
1529 if (SubIdx && MO.isDef())
1530 MO.setIsUndef(!Reads);
1531
1532 // A subreg use of a partially undef (super) register may be a complete
1533 // undef use now and then has to be marked that way.
1534 if (SubIdx != 0 && MO.isUse() && MRI->shouldTrackSubRegLiveness(DstReg)) {
1535 if (!DstInt->hasSubRanges()) {
1536 BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
1537 LaneBitmask Mask = MRI->getMaxLaneMaskForVReg(DstInt->reg);
1538 DstInt->createSubRangeFrom(Allocator, Mask, *DstInt);
1539 }
1540 SlotIndex MIIdx = UseMI->isDebugValue()
1541 ? LIS->getSlotIndexes()->getIndexBefore(*UseMI)
1542 : LIS->getInstructionIndex(*UseMI);
1543 SlotIndex UseIdx = MIIdx.getRegSlot(true);
1544 addUndefFlag(*DstInt, UseIdx, MO, SubIdx);
1545 }
1546
1547 if (DstIsPhys)
1548 MO.substPhysReg(DstReg, *TRI);
1549 else
1550 MO.substVirtReg(DstReg, SubIdx, *TRI);
1551 }
1552
1553 DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\tupdated: "; if (!UseMI
->isDebugValue()) dbgs() << LIS->getInstructionIndex
(*UseMI) << "\t"; dbgs() << *UseMI; }; } } while (
false)
1554 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)
1555 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)
1556 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)
1557 dbgs() << *UseMI;do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\tupdated: "; if (!UseMI
->isDebugValue()) dbgs() << LIS->getInstructionIndex
(*UseMI) << "\t"; dbgs() << *UseMI; }; } } while (
false)
1558 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { { dbgs() << "\t\tupdated: "; if (!UseMI
->isDebugValue()) dbgs() << LIS->getInstructionIndex
(*UseMI) << "\t"; dbgs() << *UseMI; }; } } while (
false)
;
1559 }
1560}
1561
1562bool RegisterCoalescer::canJoinPhys(const CoalescerPair &CP) {
1563 // Always join simple intervals that are defined by a single copy from a
1564 // reserved register. This doesn't increase register pressure, so it is
1565 // always beneficial.
1566 if (!MRI->isReserved(CP.getDstReg())) {
1567 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)
;
1568 return false;
1569 }
1570
1571 LiveInterval &JoinVInt = LIS->getInterval(CP.getSrcReg());
1572 if (JoinVInt.containsOneValue())
1573 return true;
1574
1575 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)
;
1576 return false;
1577}
1578
1579bool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) {
1580 Again = false;
1581 DEBUG(dbgs() << LIS->getInstructionIndex(*CopyMI) << '\t' << *CopyMI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << LIS->getInstructionIndex(*
CopyMI) << '\t' << *CopyMI; } } while (false)
;
1582
1583 CoalescerPair CP(*TRI);
1584 if (!CP.setRegisters(CopyMI)) {
1585 DEBUG(dbgs() << "\tNot coalescable.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tNot coalescable.\n"; } } while
(false)
;
1586 return false;
1587 }
1588
1589 if (CP.getNewRC()) {
1590 auto SrcRC = MRI->getRegClass(CP.getSrcReg());
1591 auto DstRC = MRI->getRegClass(CP.getDstReg());
1592 unsigned SrcIdx = CP.getSrcIdx();
1593 unsigned DstIdx = CP.getDstIdx();
1594 if (CP.isFlipped()) {
1595 std::swap(SrcIdx, DstIdx);
1596 std::swap(SrcRC, DstRC);
1597 }
1598 if (!TRI->shouldCoalesce(CopyMI, SrcRC, SrcIdx, DstRC, DstIdx,
1599 CP.getNewRC(), *LIS)) {
1600 DEBUG(dbgs() << "\tSubtarget bailed on coalescing.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tSubtarget bailed on coalescing.\n"
; } } while (false)
;
1601 return false;
1602 }
1603 }
1604
1605 // Dead code elimination. This really should be handled by MachineDCE, but
1606 // sometimes dead copies slip through, and we can't generate invalid live
1607 // ranges.
1608 if (!CP.isPhys() && CopyMI->allDefsAreDead()) {
1609 DEBUG(dbgs() << "\tCopy is dead.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tCopy is dead.\n"; } } while
(false)
;
1610 DeadDefs.push_back(CopyMI);
1611 eliminateDeadDefs();
1612 return true;
1613 }
1614
1615 // Eliminate undefs.
1616 if (!CP.isPhys() && eliminateUndefCopy(CopyMI)) {
1617 deleteInstr(CopyMI);
1618 return false; // Not coalescable.
1619 }
1620
1621 // Coalesced copies are normally removed immediately, but transformations
1622 // like removeCopyByCommutingDef() can inadvertently create identity copies.
1623 // When that happens, just join the values and remove the copy.
1624 if (CP.getSrcReg() == CP.getDstReg()) {
1625 LiveInterval &LI = LIS->getInterval(CP.getSrcReg());
1626 DEBUG(dbgs() << "\tCopy already coalesced: " << LI << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tCopy already coalesced: " <<
LI << '\n'; } } while (false)
;
1627 const SlotIndex CopyIdx = LIS->getInstructionIndex(*CopyMI);
1628 LiveQueryResult LRQ = LI.Query(CopyIdx);
1629 if (VNInfo *DefVNI = LRQ.valueDefined()) {
1630 VNInfo *ReadVNI = LRQ.valueIn();
1631 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 1631, __extension__ __PRETTY_FUNCTION__))
;
1632 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 1632, __extension__ __PRETTY_FUNCTION__))
;
1633 LI.MergeValueNumberInto(DefVNI, ReadVNI);
1634
1635 // Process subregister liveranges.
1636 for (LiveInterval::SubRange &S : LI.subranges()) {
1637 LiveQueryResult SLRQ = S.Query(CopyIdx);
1638 if (VNInfo *SDefVNI = SLRQ.valueDefined()) {
1639 VNInfo *SReadVNI = SLRQ.valueIn();
1640 S.MergeValueNumberInto(SDefVNI, SReadVNI);
1641 }
1642 }
1643 DEBUG(dbgs() << "\tMerged values: " << LI << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tMerged values: " <<
LI << '\n'; } } while (false)
;
1644 }
1645 deleteInstr(CopyMI);
1646 return true;
1647 }
1648
1649 // Enforce policies.
1650 if (CP.isPhys()) {
1651 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)
1652 << " 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)
1653 << '\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)
;
1654 if (!canJoinPhys(CP)) {
1655 // Before giving up coalescing, if definition of source is defined by
1656 // trivial computation, try rematerializing it.
1657 bool IsDefCopy;
1658 if (reMaterializeTrivialDef(CP, CopyMI, IsDefCopy))
1659 return true;
1660 if (IsDefCopy)
1661 Again = true; // May be possible to coalesce later.
1662 return false;
1663 }
1664 } else {
1665 // When possible, let DstReg be the larger interval.
1666 if (!CP.isPartial() && LIS->getInterval(CP.getSrcReg()).size() >
1667 LIS->getInterval(CP.getDstReg()).size())
1668 CP.flip();
1669
1670 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)
1671 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)
1672 << 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)
1673 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)
1674 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)
1675 << 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)
1676 << 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)
1677 << 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)
1678 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)
1679 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)
1680 << 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)
1681 })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)
;
1682 }
1683
1684 ShrinkMask = LaneBitmask::getNone();
1685 ShrinkMainRange = false;
1686
1687 // Okay, attempt to join these two intervals. On failure, this returns false.
1688 // Otherwise, if one of the intervals being joined is a physreg, this method
1689 // always canonicalizes DstInt to be it. The output "SrcInt" will not have
1690 // been modified, so we can use this information below to update aliases.
1691 if (!joinIntervals(CP)) {
1692 // Coalescing failed.
1693
1694 // If definition of source is defined by trivial computation, try
1695 // rematerializing it.
1696 bool IsDefCopy;
1697 if (reMaterializeTrivialDef(CP, CopyMI, IsDefCopy))
1698 return true;
1699
1700 // If we can eliminate the copy without merging the live segments, do so
1701 // now.
1702 if (!CP.isPartial() && !CP.isPhys()) {
1703 if (adjustCopiesBackFrom(CP, CopyMI) ||
1704 removeCopyByCommutingDef(CP, CopyMI)) {
1705 deleteInstr(CopyMI);
1706 DEBUG(dbgs() << "\tTrivial!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tTrivial!\n"; } } while (false
)
;
1707 return true;
1708 }
1709 }
1710
1711 // Try and see if we can partially eliminate the copy by moving the copy to
1712 // its predecessor.
1713 if (!CP.isPartial() && !CP.isPhys())
1714 if (removePartialRedundancy(CP, *CopyMI))
1715 return true;
1716
1717 // Otherwise, we are unable to join the intervals.
1718 DEBUG(dbgs() << "\tInterference!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tInterference!\n"; } } while
(false)
;
1719 Again = true; // May be possible to coalesce later.
1720 return false;
1721 }
1722
1723 // Coalescing to a virtual register that is of a sub-register class of the
1724 // other. Make sure the resulting register is set to the right register class.
1725 if (CP.isCrossClass()) {
1726 ++numCrossRCs;
1727 MRI->setRegClass(CP.getDstReg(), CP.getNewRC());
1728 }
1729
1730 // Removing sub-register copies can ease the register class constraints.
1731 // Make sure we attempt to inflate the register class of DstReg.
1732 if (!CP.isPhys() && RegClassInfo.isProperSubClass(CP.getNewRC()))
1733 InflateRegs.push_back(CP.getDstReg());
1734
1735 // CopyMI has been erased by joinIntervals at this point. Remove it from
1736 // ErasedInstrs since copyCoalesceWorkList() won't add a successful join back
1737 // to the work list. This keeps ErasedInstrs from growing needlessly.
1738 ErasedInstrs.erase(CopyMI);
1739
1740 // Rewrite all SrcReg operands to DstReg.
1741 // Also update DstReg operands to include DstIdx if it is set.
1742 if (CP.getDstIdx())
1743 updateRegDefsUses(CP.getDstReg(), CP.getDstReg(), CP.getDstIdx());
1744 updateRegDefsUses(CP.getSrcReg(), CP.getDstReg(), CP.getSrcIdx());
1745
1746 // Shrink subregister ranges if necessary.
1747 if (ShrinkMask.any()) {
1748 LiveInterval &LI = LIS->getInterval(CP.getDstReg());
1749 for (LiveInterval::SubRange &S : LI.subranges()) {
1750 if ((S.LaneMask & ShrinkMask).none())
1751 continue;
1752 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)
1753 << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "Shrink LaneUses (Lane " <<
PrintLaneMask(S.LaneMask) << ")\n"; } } while (false)
;
1754 LIS->shrinkToUses(S, LI.reg);
1755 }
1756 LI.removeEmptySubRanges();
1757 }
1758 if (ShrinkMainRange) {
1759 LiveInterval &LI = LIS->getInterval(CP.getDstReg());
1760 shrinkToUses(&LI);
1761 }
1762
1763 // SrcReg is guaranteed to be the register whose live interval that is
1764 // being merged.
1765 LIS->removeInterval(CP.getSrcReg());
1766
1767 // Update regalloc hint.
1768 TRI->updateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *MF);
1769
1770 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)
1771 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)
1772 << " -> " << 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)
1773 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)
1774 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)
1775 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)
1776 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)
1777 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)
1778 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)
1779 })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)
;
1780
1781 ++numJoins;
1782 return true;
1783}
1784
1785bool RegisterCoalescer::joinReservedPhysReg(CoalescerPair &CP) {
1786 unsigned DstReg = CP.getDstReg();
1787 unsigned SrcReg = CP.getSrcReg();
1788 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 1788, __extension__ __PRETTY_FUNCTION__))
;
1789 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 1789, __extension__ __PRETTY_FUNCTION__))
;
1790 LiveInterval &RHS = LIS->getInterval(SrcReg);
1791 DEBUG(dbgs() << "\t\tRHS = " << RHS << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tRHS = " << RHS <<
'\n'; } } while (false)
;
1792
1793 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 1793, __extension__ __PRETTY_FUNCTION__))
;
1794
1795 // Optimization for reserved registers like ESP. We can only merge with a
1796 // reserved physreg if RHS has a single value that is a copy of DstReg.
1797 // The live range of the reserved register will look like a set of dead defs
1798 // - we don't properly track the live range of reserved registers.
1799
1800 // Deny any overlapping intervals. This depends on all the reserved
1801 // register live ranges to look like dead defs.
1802 if (!MRI->isConstantPhysReg(DstReg)) {
1803 for (MCRegUnitIterator UI(DstReg, TRI); UI.isValid(); ++UI) {
1804 // Abort if not all the regunits are reserved.
1805 for (MCRegUnitRootIterator RI(*UI, TRI); RI.isValid(); ++RI) {
1806 if (!MRI->isReserved(*RI))
1807 return false;
1808 }
1809 if (RHS.overlaps(LIS->getRegUnit(*UI))) {
1810 DEBUG(dbgs() << "\t\tInterference: " << printRegUnit(*UI, TRI) << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tInterference: " <<
printRegUnit(*UI, TRI) << '\n'; } } while (false)
;
1811 return false;
1812 }
1813 }
1814
1815 // We must also check for overlaps with regmask clobbers.
1816 BitVector RegMaskUsable;
1817 if (LIS->checkRegMaskInterference(RHS, RegMaskUsable) &&
1818 !RegMaskUsable.test(DstReg)) {
1819 DEBUG(dbgs() << "\t\tRegMask interference\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tRegMask interference\n";
} } while (false)
;
1820 return false;
1821 }
1822 }
1823
1824 // Skip any value computations, we are not adding new values to the
1825 // reserved register. Also skip merging the live ranges, the reserved
1826 // register live range doesn't need to be accurate as long as all the
1827 // defs are there.
1828
1829 // Delete the identity copy.
1830 MachineInstr *CopyMI;
1831 if (CP.isFlipped()) {
1832 // Physreg is copied into vreg
1833 // %y = COPY %physreg_x
1834 // ... //< no other def of %x here
1835 // use %y
1836 // =>
1837 // ...
1838 // use %x
1839 CopyMI = MRI->getVRegDef(SrcReg);
1840 } else {
1841 // VReg is copied into physreg:
1842 // %y = def
1843 // ... //< no other def or use of %y here
1844 // %y = COPY %physreg_x
1845 // =>
1846 // %y = def
1847 // ...
1848 if (!MRI->hasOneNonDBGUse(SrcReg)) {
1849 DEBUG(dbgs() << "\t\tMultiple vreg uses!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tMultiple vreg uses!\n"; }
} while (false)
;
1850 return false;
1851 }
1852
1853 if (!LIS->intervalIsInOneMBB(RHS)) {
1854 DEBUG(dbgs() << "\t\tComplex control flow!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tComplex control flow!\n"
; } } while (false)
;
1855 return false;
1856 }
1857
1858 MachineInstr &DestMI = *MRI->getVRegDef(SrcReg);
1859 CopyMI = &*MRI->use_instr_nodbg_begin(SrcReg);
1860 SlotIndex CopyRegIdx = LIS->getInstructionIndex(*CopyMI).getRegSlot();
1861 SlotIndex DestRegIdx = LIS->getInstructionIndex(DestMI).getRegSlot();
1862
1863 if (!MRI->isConstantPhysReg(DstReg)) {
1864 // We checked above that there are no interfering defs of the physical
1865 // register. However, for this case, where we intend to move up the def of
1866 // the physical register, we also need to check for interfering uses.
1867 SlotIndexes *Indexes = LIS->getSlotIndexes();
1868 for (SlotIndex SI = Indexes->getNextNonNullIndex(DestRegIdx);
1869 SI != CopyRegIdx; SI = Indexes->getNextNonNullIndex(SI)) {
1870 MachineInstr *MI = LIS->getInstructionFromIndex(SI);
1871 if (MI->readsRegister(DstReg, TRI)) {
1872 DEBUG(dbgs() << "\t\tInterference (read): " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tInterference (read): " <<
*MI; } } while (false)
;
1873 return false;
1874 }
1875 }
1876 }
1877
1878 // We're going to remove the copy which defines a physical reserved
1879 // register, so remove its valno, etc.
1880 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)
1881 << " 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)
;
1882
1883 LIS->removePhysRegDefAt(DstReg, CopyRegIdx);
1884 // Create a new dead def at the new def location.
1885 for (MCRegUnitIterator UI(DstReg, TRI); UI.isValid(); ++UI) {
1886 LiveRange &LR = LIS->getRegUnit(*UI);
1887 LR.createDeadDef(DestRegIdx, LIS->getVNInfoAllocator());
1888 }
1889 }
1890
1891 deleteInstr(CopyMI);
1892
1893 // We don't track kills for reserved registers.
1894 MRI->clearKillFlags(CP.getSrcReg());
1895
1896 return true;
1897}
1898
1899//===----------------------------------------------------------------------===//
1900// Interference checking and interval joining
1901//===----------------------------------------------------------------------===//
1902//
1903// In the easiest case, the two live ranges being joined are disjoint, and
1904// there is no interference to consider. It is quite common, though, to have
1905// overlapping live ranges, and we need to check if the interference can be
1906// resolved.
1907//
1908// The live range of a single SSA value forms a sub-tree of the dominator tree.
1909// This means that two SSA values overlap if and only if the def of one value
1910// is contained in the live range of the other value. As a special case, the
1911// overlapping values can be defined at the same index.
1912//
1913// The interference from an overlapping def can be resolved in these cases:
1914//
1915// 1. Coalescable copies. The value is defined by a copy that would become an
1916// identity copy after joining SrcReg and DstReg. The copy instruction will
1917// be removed, and the value will be merged with the source value.
1918//
1919// There can be several copies back and forth, causing many values to be
1920// merged into one. We compute a list of ultimate values in the joined live
1921// range as well as a mappings from the old value numbers.
1922//
1923// 2. IMPLICIT_DEF. This instruction is only inserted to ensure all PHI
1924// predecessors have a live out value. It doesn't cause real interference,
1925// and can be merged into the value it overlaps. Like a coalescable copy, it
1926// can be erased after joining.
1927//
1928// 3. Copy of external value. The overlapping def may be a copy of a value that
1929// is already in the other register. This is like a coalescable copy, but
1930// the live range of the source register must be trimmed after erasing the
1931// copy instruction:
1932//
1933// %src = COPY %ext
1934// %dst = COPY %ext <-- Remove this COPY, trim the live range of %ext.
1935//
1936// 4. Clobbering undefined lanes. Vector registers are sometimes built by
1937// defining one lane at a time:
1938//
1939// %dst:ssub0<def,read-undef> = FOO
1940// %src = BAR
1941// %dst:ssub1 = COPY %src
1942//
1943// The live range of %src overlaps the %dst value defined by FOO, but
1944// merging %src into %dst:ssub1 is only going to clobber the ssub1 lane
1945// which was undef anyway.
1946//
1947// The value mapping is more complicated in this case. The final live range
1948// will have different value numbers for both FOO and BAR, but there is no
1949// simple mapping from old to new values. It may even be necessary to add
1950// new PHI values.
1951//
1952// 5. Clobbering dead lanes. A def may clobber a lane of a vector register that
1953// is live, but never read. This can happen because we don't compute
1954// individual live ranges per lane.
1955//
1956// %dst = FOO
1957// %src = BAR
1958// %dst:ssub1 = COPY %src
1959//
1960// This kind of interference is only resolved locally. If the clobbered
1961// lane value escapes the block, the join is aborted.
1962
1963namespace {
1964
1965/// Track information about values in a single virtual register about to be
1966/// joined. Objects of this class are always created in pairs - one for each
1967/// side of the CoalescerPair (or one for each lane of a side of the coalescer
1968/// pair)
1969class JoinVals {
1970 /// Live range we work on.
1971 LiveRange &LR;
1972
1973 /// (Main) register we work on.
1974 const unsigned Reg;
1975
1976 /// Reg (and therefore the values in this liverange) will end up as
1977 /// subregister SubIdx in the coalesced register. Either CP.DstIdx or
1978 /// CP.SrcIdx.
1979 const unsigned SubIdx;
1980
1981 /// The LaneMask that this liverange will occupy the coalesced register. May
1982 /// be smaller than the lanemask produced by SubIdx when merging subranges.
1983 const LaneBitmask LaneMask;
1984
1985 /// This is true when joining sub register ranges, false when joining main
1986 /// ranges.
1987 const bool SubRangeJoin;
1988
1989 /// Whether the current LiveInterval tracks subregister liveness.
1990 const bool TrackSubRegLiveness;
1991
1992 /// Values that will be present in the final live range.
1993 SmallVectorImpl<VNInfo*> &NewVNInfo;
1994
1995 const CoalescerPair &CP;
1996 LiveIntervals *LIS;
1997 SlotIndexes *Indexes;
1998 const TargetRegisterInfo *TRI;
1999
2000 /// Value number assignments. Maps value numbers in LI to entries in
2001 /// NewVNInfo. This is suitable for passing to LiveInterval::join().
2002 SmallVector<int, 8> Assignments;
2003
2004 /// Conflict resolution for overlapping values.
2005 enum ConflictResolution {
2006 /// No overlap, simply keep this value.
2007 CR_Keep,
2008
2009 /// Merge this value into OtherVNI and erase the defining instruction.
2010 /// Used for IMPLICIT_DEF, coalescable copies, and copies from external
2011 /// values.
2012 CR_Erase,
2013
2014 /// Merge this value into OtherVNI but keep the defining instruction.
2015 /// This is for the special case where OtherVNI is defined by the same
2016 /// instruction.
2017 CR_Merge,
2018
2019 /// Keep this value, and have it replace OtherVNI where possible. This
2020 /// complicates value mapping since OtherVNI maps to two different values
2021 /// before and after this def.
2022 /// Used when clobbering undefined or dead lanes.
2023 CR_Replace,
2024
2025 /// Unresolved conflict. Visit later when all values have been mapped.
2026 CR_Unresolved,
2027
2028 /// Unresolvable conflict. Abort the join.
2029 CR_Impossible
2030 };
2031
2032 /// Per-value info for LI. The lane bit masks are all relative to the final
2033 /// joined register, so they can be compared directly between SrcReg and
2034 /// DstReg.
2035 struct Val {
2036 ConflictResolution Resolution = CR_Keep;
2037
2038 /// Lanes written by this def, 0 for unanalyzed values.
2039 LaneBitmask WriteLanes;
2040
2041 /// Lanes with defined values in this register. Other lanes are undef and
2042 /// safe to clobber.
2043 LaneBitmask ValidLanes;
2044
2045 /// Value in LI being redefined by this def.
2046 VNInfo *RedefVNI = nullptr;
2047
2048 /// Value in the other live range that overlaps this def, if any.
2049 VNInfo *OtherVNI = nullptr;
2050
2051 /// Is this value an IMPLICIT_DEF that can be erased?
2052 ///
2053 /// IMPLICIT_DEF values should only exist at the end of a basic block that
2054 /// is a predecessor to a phi-value. These IMPLICIT_DEF instructions can be
2055 /// safely erased if they are overlapping a live value in the other live
2056 /// interval.
2057 ///
2058 /// Weird control flow graphs and incomplete PHI handling in
2059 /// ProcessImplicitDefs can very rarely create IMPLICIT_DEF values with
2060 /// longer live ranges. Such IMPLICIT_DEF values should be treated like
2061 /// normal values.
2062 bool ErasableImplicitDef = false;
2063
2064 /// True when the live range of this value will be pruned because of an
2065 /// overlapping CR_Replace value in the other live range.
2066 bool Pruned = false;
2067
2068 /// True once Pruned above has been computed.
2069 bool PrunedComputed = false;
2070
2071 Val() = default;
2072
2073 bool isAnalyzed() const { return WriteLanes.any(); }
2074 };
2075
2076 /// One entry per value number in LI.
2077 SmallVector<Val, 8> Vals;
2078
2079 /// Compute the bitmask of lanes actually written by DefMI.
2080 /// Set Redef if there are any partial register definitions that depend on the
2081 /// previous value of the register.
2082 LaneBitmask computeWriteLanes(const MachineInstr *DefMI, bool &Redef) const;
2083
2084 /// Find the ultimate value that VNI was copied from.
2085 std::pair<const VNInfo*,unsigned> followCopyChain(const VNInfo *VNI) const;
2086
2087 bool valuesIdentical(VNInfo *Val0, VNInfo *Val1, const JoinVals &Other) const;
2088
2089 /// Analyze ValNo in this live range, and set all fields of Vals[ValNo].
2090 /// Return a conflict resolution when possible, but leave the hard cases as
2091 /// CR_Unresolved.
2092 /// Recursively calls computeAssignment() on this and Other, guaranteeing that
2093 /// both OtherVNI and RedefVNI have been analyzed and mapped before returning.
2094 /// The recursion always goes upwards in the dominator tree, making loops
2095 /// impossible.
2096 ConflictResolution analyzeValue(unsigned ValNo, JoinVals &Other);
2097
2098 /// Compute the value assignment for ValNo in RI.
2099 /// This may be called recursively by analyzeValue(), but never for a ValNo on
2100 /// the stack.
2101 void computeAssignment(unsigned ValNo, JoinVals &Other);
2102
2103 /// Assuming ValNo is going to clobber some valid lanes in Other.LR, compute
2104 /// the extent of the tainted lanes in the block.
2105 ///
2106 /// Multiple values in Other.LR can be affected since partial redefinitions
2107 /// can preserve previously tainted lanes.
2108 ///
2109 /// 1 %dst = VLOAD <-- Define all lanes in %dst
2110 /// 2 %src = FOO <-- ValNo to be joined with %dst:ssub0
2111 /// 3 %dst:ssub1 = BAR <-- Partial redef doesn't clear taint in ssub0
2112 /// 4 %dst:ssub0 = COPY %src <-- Conflict resolved, ssub0 wasn't read
2113 ///
2114 /// For each ValNo in Other that is affected, add an (EndIndex, TaintedLanes)
2115 /// entry to TaintedVals.
2116 ///
2117 /// Returns false if the tainted lanes extend beyond the basic block.
2118 bool
2119 taintExtent(unsigned ValNo, LaneBitmask TaintedLanes, JoinVals &Other,
2120 SmallVectorImpl<std::pair<SlotIndex, LaneBitmask>> &TaintExtent);
2121
2122 /// Return true if MI uses any of the given Lanes from Reg.
2123 /// This does not include partial redefinitions of Reg.
2124 bool usesLanes(const MachineInstr &MI, unsigned, unsigned, LaneBitmask) const;
2125
2126 /// Determine if ValNo is a copy of a value number in LR or Other.LR that will
2127 /// be pruned:
2128 ///
2129 /// %dst = COPY %src
2130 /// %src = COPY %dst <-- This value to be pruned.
2131 /// %dst = COPY %src <-- This value is a copy of a pruned value.
2132 bool isPrunedValue(unsigned ValNo, JoinVals &Other);
2133
2134public:
2135 JoinVals(LiveRange &LR, unsigned Reg, unsigned SubIdx, LaneBitmask LaneMask,
2136 SmallVectorImpl<VNInfo*> &newVNInfo, const CoalescerPair &cp,
2137 LiveIntervals *lis, const TargetRegisterInfo *TRI, bool SubRangeJoin,
2138 bool TrackSubRegLiveness)
2139 : LR(LR), Reg(Reg), SubIdx(SubIdx), LaneMask(LaneMask),
2140 SubRangeJoin(SubRangeJoin), TrackSubRegLiveness(TrackSubRegLiveness),
2141 NewVNInfo(newVNInfo), CP(cp), LIS(lis), Indexes(LIS->getSlotIndexes()),
2142 TRI(TRI), Assignments(LR.getNumValNums(), -1), Vals(LR.getNumValNums()) {}
2143
2144 /// Analyze defs in LR and compute a value mapping in NewVNInfo.
2145 /// Returns false if any conflicts were impossible to resolve.
2146 bool mapValues(JoinVals &Other);
2147
2148 /// Try to resolve conflicts that require all values to be mapped.
2149 /// Returns false if any conflicts were impossible to resolve.
2150 bool resolveConflicts(JoinVals &Other);
2151
2152 /// Prune the live range of values in Other.LR where they would conflict with
2153 /// CR_Replace values in LR. Collect end points for restoring the live range
2154 /// after joining.
2155 void pruneValues(JoinVals &Other, SmallVectorImpl<SlotIndex> &EndPoints,
2156 bool changeInstrs);
2157
2158 /// Removes subranges starting at copies that get removed. This sometimes
2159 /// happens when undefined subranges are copied around. These ranges contain
2160 /// no useful information and can be removed.
2161 void pruneSubRegValues(LiveInterval &LI, LaneBitmask &ShrinkMask);
2162
2163 /// Pruning values in subranges can lead to removing segments in these
2164 /// subranges started by IMPLICIT_DEFs. The corresponding segments in
2165 /// the main range also need to be removed. This function will mark
2166 /// the corresponding values in the main range as pruned, so that
2167 /// eraseInstrs can do the final cleanup.
2168 /// The parameter @p LI must be the interval whose main range is the
2169 /// live range LR.
2170 void pruneMainSegments(LiveInterval &LI, bool &ShrinkMainRange);
2171
2172 /// Erase any machine instructions that have been coalesced away.
2173 /// Add erased instructions to ErasedInstrs.
2174 /// Add foreign virtual registers to ShrinkRegs if their live range ended at
2175 /// the erased instrs.
2176 void eraseInstrs(SmallPtrSetImpl<MachineInstr*> &ErasedInstrs,
2177 SmallVectorImpl<unsigned> &ShrinkRegs,
2178 LiveInterval *LI = nullptr);
2179
2180 /// Remove liverange defs at places where implicit defs will be removed.
2181 void removeImplicitDefs();
2182
2183 /// Get the value assignments suitable for passing to LiveInterval::join.
2184 const int *getAssignments() const { return Assignments.data(); }
2185};
2186
2187} // end anonymous namespace
2188
2189LaneBitmask JoinVals::computeWriteLanes(const MachineInstr *DefMI, bool &Redef)
2190 const {
2191 LaneBitmask L;
2192 for (const MachineOperand &MO : DefMI->operands()) {
2193 if (!MO.isReg() || MO.getReg() != Reg || !MO.isDef())
2194 continue;
2195 L |= TRI->getSubRegIndexLaneMask(
2196 TRI->composeSubRegIndices(SubIdx, MO.getSubReg()));
2197 if (MO.readsReg())
2198 Redef = true;
2199 }
2200 return L;
2201}
2202
2203std::pair<const VNInfo*, unsigned> JoinVals::followCopyChain(
2204 const VNInfo *VNI) const {
2205 unsigned Reg = this->Reg;
2206
2207 while (!VNI->isPHIDef()) {
2208 SlotIndex Def = VNI->def;
2209 MachineInstr *MI = Indexes->getInstructionFromIndex(Def);
2210 assert(MI && "No defining instruction")(static_cast <bool> (MI && "No defining instruction"
) ? void (0) : __assert_fail ("MI && \"No defining instruction\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 2210, __extension__ __PRETTY_FUNCTION__))
;
2211 if (!MI->isFullCopy())
2212 return std::make_pair(VNI, Reg);
2213 unsigned SrcReg = MI->getOperand(1).getReg();
2214 if (!TargetRegisterInfo::isVirtualRegister(SrcReg))
2215 return std::make_pair(VNI, Reg);
2216
2217 const LiveInterval &LI = LIS->getInterval(SrcReg);
2218 const VNInfo *ValueIn;
2219 // No subrange involved.
2220 if (!SubRangeJoin || !LI.hasSubRanges()) {
2221 LiveQueryResult LRQ = LI.Query(Def);
2222 ValueIn = LRQ.valueIn();
2223 } else {
2224 // Query subranges. Pick the first matching one.
2225 ValueIn = nullptr;
2226 for (const LiveInterval::SubRange &S : LI.subranges()) {
2227 // Transform lanemask to a mask in the joined live interval.
2228 LaneBitmask SMask = TRI->composeSubRegIndexLaneMask(SubIdx, S.LaneMask);
2229 if ((SMask & LaneMask).none())
2230 continue;
2231 LiveQueryResult LRQ = S.Query(Def);
2232 ValueIn = LRQ.valueIn();
2233 break;
2234 }
2235 }
2236 if (ValueIn == nullptr)
2237 break;
2238 VNI = ValueIn;
2239 Reg = SrcReg;
2240 }
2241 return std::make_pair(VNI, Reg);
2242}
2243
2244bool JoinVals::valuesIdentical(VNInfo *Value0, VNInfo *Value1,
2245 const JoinVals &Other) const {
2246 const VNInfo *Orig0;
2247 unsigned Reg0;
2248 std::tie(Orig0, Reg0) = followCopyChain(Value0);
2249 if (Orig0 == Value1)
2250 return true;
2251
2252 const VNInfo *Orig1;
2253 unsigned Reg1;
2254 std::tie(Orig1, Reg1) = Other.followCopyChain(Value1);
2255
2256 // The values are equal if they are defined at the same place and use the
2257 // same register. Note that we cannot compare VNInfos directly as some of
2258 // them might be from a copy created in mergeSubRangeInto() while the other
2259 // is from the original LiveInterval.
2260 return Orig0->def == Orig1->def && Reg0 == Reg1;
2261}
2262
2263JoinVals::ConflictResolution
2264JoinVals::analyzeValue(unsigned ValNo, JoinVals &Other) {
2265 Val &V = Vals[ValNo];
2266 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 2266, __extension__ __PRETTY_FUNCTION__))
;
2267 VNInfo *VNI = LR.getValNumInfo(ValNo);
2268 if (VNI->isUnused()) {
2269 V.WriteLanes = LaneBitmask::getAll();
2270 return CR_Keep;
2271 }
2272
2273 // Get the instruction defining this value, compute the lanes written.
2274 const MachineInstr *DefMI = nullptr;
2275 if (VNI->isPHIDef()) {
2276 // Conservatively assume that all lanes in a PHI are valid.
2277 LaneBitmask Lanes = SubRangeJoin ? LaneBitmask::getLane(0)
2278 : TRI->getSubRegIndexLaneMask(SubIdx);
2279 V.ValidLanes = V.WriteLanes = Lanes;
2280 } else {
2281 DefMI = Indexes->getInstructionFromIndex(VNI->def);
2282 assert(DefMI != nullptr)(static_cast <bool> (DefMI != nullptr) ? void (0) : __assert_fail
("DefMI != nullptr", "/build/llvm-toolchain-snapshot-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 2282, __extension__ __PRETTY_FUNCTION__))
;
2283 if (SubRangeJoin) {
2284 // We don't care about the lanes when joining subregister ranges.
2285 V.WriteLanes = V.ValidLanes = LaneBitmask::getLane(0);
2286 if (DefMI->isImplicitDef()) {
2287 V.ValidLanes = LaneBitmask::getNone();
2288 V.ErasableImplicitDef = true;
2289 }
2290 } else {
2291 bool Redef = false;
2292 V.ValidLanes = V.WriteLanes = computeWriteLanes(DefMI, Redef);
2293
2294 // If this is a read-modify-write instruction, there may be more valid
2295 // lanes than the ones written by this instruction.
2296 // This only covers partial redef operands. DefMI may have normal use
2297 // operands reading the register. They don't contribute valid lanes.
2298 //
2299 // This adds ssub1 to the set of valid lanes in %src:
2300 //
2301 // %src:ssub1 = FOO
2302 //
2303 // This leaves only ssub1 valid, making any other lanes undef:
2304 //
2305 // %src:ssub1<def,read-undef> = FOO %src:ssub2
2306 //
2307 // The <read-undef> flag on the def operand means that old lane values are
2308 // not important.
2309 if (Redef) {
2310 V.RedefVNI = LR.Query(VNI->def).valueIn();
2311 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 2312, __extension__ __PRETTY_FUNCTION__))
2312 "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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 2312, __extension__ __PRETTY_FUNCTION__))
;
2313 if (V.RedefVNI != nullptr) {
2314 computeAssignment(V.RedefVNI->id, Other);
2315 V.ValidLanes |= Vals[V.RedefVNI->id].ValidLanes;
2316 }
2317 }
2318
2319 // An IMPLICIT_DEF writes undef values.
2320 if (DefMI->isImplicitDef()) {
2321 // We normally expect IMPLICIT_DEF values to be live only until the end
2322 // of their block. If the value is really live longer and gets pruned in
2323 // another block, this flag is cleared again.
2324 V.ErasableImplicitDef = true;
2325 V.ValidLanes &= ~V.WriteLanes;
2326 }
2327 }
2328 }
2329
2330 // Find the value in Other that overlaps VNI->def, if any.
2331 LiveQueryResult OtherLRQ = Other.LR.Query(VNI->def);
2332
2333 // It is possible that both values are defined by the same instruction, or
2334 // the values are PHIs defined in the same block. When that happens, the two
2335 // values should be merged into one, but not into any preceding value.
2336 // The first value defined or visited gets CR_Keep, the other gets CR_Merge.
2337 if (VNInfo *OtherVNI = OtherLRQ.valueDefined()) {
2338 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 2338, __extension__ __PRETTY_FUNCTION__))
;
2339
2340 // One value stays, the other is merged. Keep the earlier one, or the first
2341 // one we see.
2342 if (OtherVNI->def < VNI->def)
2343 Other.computeAssignment(OtherVNI->id, *this);
2344 else if (VNI->def < OtherVNI->def && OtherLRQ.valueIn()) {
2345 // This is an early-clobber def overlapping a live-in value in the other
2346 // register. Not mergeable.
2347 V.OtherVNI = OtherLRQ.valueIn();
2348 return CR_Impossible;
2349 }
2350 V.OtherVNI = OtherVNI;
2351 Val &OtherV = Other.Vals[OtherVNI->id];
2352 // Keep this value, check for conflicts when analyzing OtherVNI.
2353 if (!OtherV.isAnalyzed())
2354 return CR_Keep;
2355 // Both sides have been analyzed now.
2356 // Allow overlapping PHI values. Any real interference would show up in a
2357 // predecessor, the PHI itself can't introduce any conflicts.
2358 if (VNI->isPHIDef())
2359 return CR_Merge;
2360 if ((V.ValidLanes & OtherV.ValidLanes).any())
2361 // Overlapping lanes can't be resolved.
2362 return CR_Impossible;
2363 else
2364 return CR_Merge;
2365 }
2366
2367 // No simultaneous def. Is Other live at the def?
2368 V.OtherVNI = OtherLRQ.valueIn();
2369 if (!V.OtherVNI)
2370 // No overlap, no conflict.
2371 return CR_Keep;
2372
2373 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 2373, __extension__ __PRETTY_FUNCTION__))
;
2374
2375 // We have overlapping values, or possibly a kill of Other.
2376 // Recursively compute assignments up the dominator tree.
2377 Other.computeAssignment(V.OtherVNI->id, *this);
2378 Val &OtherV = Other.Vals[V.OtherVNI->id];
2379
2380 // Check if OtherV is an IMPLICIT_DEF that extends beyond its basic block.
2381 // This shouldn't normally happen, but ProcessImplicitDefs can leave such
2382 // IMPLICIT_DEF instructions behind, and there is nothing wrong with it
2383 // technically.
2384 //
2385 // When it happens, treat that IMPLICIT_DEF as a normal value, and don't try
2386 // to erase the IMPLICIT_DEF instruction.
2387 if (OtherV.ErasableImplicitDef && DefMI &&
2388 DefMI->getParent() != Indexes->getMBBFromIndex(V.OtherVNI->def)) {
2389 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)
2390 << " 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)
2391 << ", 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)
;
2392 OtherV.ErasableImplicitDef = false;
2393 }
2394
2395 // Allow overlapping PHI values. Any real interference would show up in a
2396 // predecessor, the PHI itself can't introduce any conflicts.
2397 if (VNI->isPHIDef())
2398 return CR_Replace;
2399
2400 // Check for simple erasable conflicts.
2401 if (DefMI->isImplicitDef()) {
2402 // We need the def for the subregister if there is nothing else live at the
2403 // subrange at this point.
2404 if (TrackSubRegLiveness
2405 && (V.WriteLanes & (OtherV.ValidLanes | OtherV.WriteLanes)).none())
2406 return CR_Replace;
2407 return CR_Erase;
2408 }
2409
2410 // Include the non-conflict where DefMI is a coalescable copy that kills
2411 // OtherVNI. We still want the copy erased and value numbers merged.
2412 if (CP.isCoalescable(DefMI)) {
2413 // Some of the lanes copied from OtherVNI may be undef, making them undef
2414 // here too.
2415 V.ValidLanes &= ~V.WriteLanes | OtherV.ValidLanes;
2416 return CR_Erase;
2417 }
2418
2419 // This may not be a real conflict if DefMI simply kills Other and defines
2420 // VNI.
2421 if (OtherLRQ.isKill() && OtherLRQ.endPoint() <= VNI->def)
2422 return CR_Keep;
2423
2424 // Handle the case where VNI and OtherVNI can be proven to be identical:
2425 //
2426 // %other = COPY %ext
2427 // %this = COPY %ext <-- Erase this copy
2428 //
2429 if (DefMI->isFullCopy() && !CP.isPartial()
2430 && valuesIdentical(VNI, V.OtherVNI, Other))
2431 return CR_Erase;
2432
2433 // If the lanes written by this instruction were all undef in OtherVNI, it is
2434 // still safe to join the live ranges. This can't be done with a simple value
2435 // mapping, though - OtherVNI will map to multiple values:
2436 //
2437 // 1 %dst:ssub0 = FOO <-- OtherVNI
2438 // 2 %src = BAR <-- VNI
2439 // 3 %dst:ssub1 = COPY killed %src <-- Eliminate this copy.
2440 // 4 BAZ killed %dst
2441 // 5 QUUX killed %src
2442 //
2443 // Here OtherVNI will map to itself in [1;2), but to VNI in [2;5). CR_Replace
2444 // handles this complex value mapping.
2445 if ((V.WriteLanes & OtherV.ValidLanes).none())
2446 return CR_Replace;
2447
2448 // If the other live range is killed by DefMI and the live ranges are still
2449 // overlapping, it must be because we're looking at an early clobber def:
2450 //
2451 // %dst<def,early-clobber> = ASM killed %src
2452 //
2453 // In this case, it is illegal to merge the two live ranges since the early
2454 // clobber def would clobber %src before it was read.
2455 if (OtherLRQ.isKill()) {
2456 // This case where the def doesn't overlap the kill is handled above.
2457 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 2458, __extension__ __PRETTY_FUNCTION__))
2458 "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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 2458, __extension__ __PRETTY_FUNCTION__))
;
2459 return CR_Impossible;
2460 }
2461
2462 // VNI is clobbering live lanes in OtherVNI, but there is still the
2463 // possibility that no instructions actually read the clobbered lanes.
2464 // If we're clobbering all the lanes in OtherVNI, at least one must be read.
2465 // Otherwise Other.RI wouldn't be live here.
2466 if ((TRI->getSubRegIndexLaneMask(Other.SubIdx) & ~V.WriteLanes).none())
2467 return CR_Impossible;
2468
2469 // We need to verify that no instructions are reading the clobbered lanes. To
2470 // save compile time, we'll only check that locally. Don't allow the tainted
2471 // value to escape the basic block.
2472 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def);
2473 if (OtherLRQ.endPoint() >= Indexes->getMBBEndIdx(MBB))
2474 return CR_Impossible;
2475
2476 // There are still some things that could go wrong besides clobbered lanes
2477 // being read, for example OtherVNI may be only partially redefined in MBB,
2478 // and some clobbered lanes could escape the block. Save this analysis for
2479 // resolveConflicts() when all values have been mapped. We need to know
2480 // RedefVNI and WriteLanes for any later defs in MBB, and we can't compute
2481 // that now - the recursive analyzeValue() calls must go upwards in the
2482 // dominator tree.
2483 return CR_Unresolved;
2484}
2485
2486void JoinVals::computeAssignment(unsigned ValNo, JoinVals &Other) {
2487 Val &V = Vals[ValNo];
2488 if (V.isAnalyzed()) {
2489 // Recursion should always move up the dominator tree, so ValNo is not
2490 // supposed to reappear before it has been assigned.
2491 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 2491, __extension__ __PRETTY_FUNCTION__))
;
2492 return;
2493 }
2494 switch ((V.Resolution = analyzeValue(ValNo, Other))) {
2495 case CR_Erase:
2496 case CR_Merge:
2497 // Merge this ValNo into OtherVNI.
2498 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 2498, __extension__ __PRETTY_FUNCTION__))
;
2499 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 2499, __extension__ __PRETTY_FUNCTION__))
;
2500 Assignments[ValNo] = Other.Assignments[V.OtherVNI->id];
2501 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)
2502 << 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)
2503 << 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)
2504 << 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)
2505 << 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)
;
2506 break;
2507 case CR_Replace:
2508 case CR_Unresolved: {
2509 // The other value is going to be pruned if this join is successful.
2510 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 2510, __extension__ __PRETTY_FUNCTION__))
;
2511 Val &OtherV = Other.Vals[V.OtherVNI->id];
2512 // We cannot erase an IMPLICIT_DEF if we don't have valid values for all
2513 // its lanes.
2514 if ((OtherV.WriteLanes & ~V.ValidLanes).any() && TrackSubRegLiveness)
2515 OtherV.ErasableImplicitDef = false;
2516 OtherV.Pruned = true;
2517 LLVM_FALLTHROUGH[[clang::fallthrough]];
2518 }
2519 default:
2520 // This value number needs to go in the final joined live range.
2521 Assignments[ValNo] = NewVNInfo.size();
2522 NewVNInfo.push_back(LR.getValNumInfo(ValNo));
2523 break;
2524 }
2525}
2526
2527bool JoinVals::mapValues(JoinVals &Other) {
2528 for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
2529 computeAssignment(i, Other);
2530 if (Vals[i].Resolution == CR_Impossible) {
2531 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)
2532 << '@' << 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)
;
2533 return false;
2534 }
2535 }
2536 return true;
2537}
2538
2539bool JoinVals::
2540taintExtent(unsigned ValNo, LaneBitmask TaintedLanes, JoinVals &Other,
2541 SmallVectorImpl<std::pair<SlotIndex, LaneBitmask>> &TaintExtent) {
2542 VNInfo *VNI = LR.getValNumInfo(ValNo);
2543 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def);
2544 SlotIndex MBBEnd = Indexes->getMBBEndIdx(MBB);
2545
2546 // Scan Other.LR from VNI.def to MBBEnd.
2547 LiveInterval::iterator OtherI = Other.LR.find(VNI->def);
2548 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 2548, __extension__ __PRETTY_FUNCTION__))
;
2549 do {
2550 // OtherI is pointing to a tainted value. Abort the join if the tainted
2551 // lanes escape the block.
2552 SlotIndex End = OtherI->end;
2553 if (End >= MBBEnd) {
2554 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)
2555 << 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)
;
2556 return false;
2557 }
2558 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)
2559 << 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)
2560 << " 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)
;
2561 // A dead def is not a problem.
2562 if (End.isDead())
2563 break;
2564 TaintExtent.push_back(std::make_pair(End, TaintedLanes));
2565
2566 // Check for another def in the MBB.
2567 if (++OtherI == Other.LR.end() || OtherI->start >= MBBEnd)
2568 break;
2569
2570 // Lanes written by the new def are no longer tainted.
2571 const Val &OV = Other.Vals[OtherI->valno->id];
2572 TaintedLanes &= ~OV.WriteLanes;
2573 if (!OV.RedefVNI)
2574 break;
2575 } while (TaintedLanes.any());
2576 return true;
2577}
2578
2579bool JoinVals::usesLanes(const MachineInstr &MI, unsigned Reg, unsigned SubIdx,
2580 LaneBitmask Lanes) const {
2581 if (MI.isDebugValue())
2582 return false;
2583 for (const MachineOperand &MO : MI.operands()) {
2584 if (!MO.isReg() || MO.isDef() || MO.getReg() != Reg)
2585 continue;
2586 if (!MO.readsReg())
2587 continue;
2588 unsigned S = TRI->composeSubRegIndices(SubIdx, MO.getSubReg());
2589 if ((Lanes & TRI->getSubRegIndexLaneMask(S)).any())
2590 return true;
2591 }
2592 return false;
2593}
2594
2595bool JoinVals::resolveConflicts(JoinVals &Other) {
2596 for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
2597 Val &V = Vals[i];
2598 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 2598, __extension__ __PRETTY_FUNCTION__))
;
2599 if (V.Resolution != CR_Unresolved)
2600 continue;
2601 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)
2602 << '@' << 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)
;
2603 if (SubRangeJoin)
2604 return false;
2605
2606 ++NumLaneConflicts;
2607 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 2607, __extension__ __PRETTY_FUNCTION__))
;
2608 VNInfo *VNI = LR.getValNumInfo(i);
2609 const Val &OtherV = Other.Vals[V.OtherVNI->id];
2610
2611 // VNI is known to clobber some lanes in OtherVNI. If we go ahead with the
2612 // join, those lanes will be tainted with a wrong value. Get the extent of
2613 // the tainted lanes.
2614 LaneBitmask TaintedLanes = V.WriteLanes & OtherV.ValidLanes;
2615 SmallVector<std::pair<SlotIndex, LaneBitmask>, 8> TaintExtent;
2616 if (!taintExtent(i, TaintedLanes, Other, TaintExtent))
2617 // Tainted lanes would extend beyond the basic block.
2618 return false;
2619
2620 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 2620, __extension__ __PRETTY_FUNCTION__))
;
2621
2622 // Now look at the instructions from VNI->def to TaintExtent (inclusive).
2623 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def);
2624 MachineBasicBlock::iterator MI = MBB->begin();
2625 if (!VNI->isPHIDef()) {
2626 MI = Indexes->getInstructionFromIndex(VNI->def);
2627 // No need to check the instruction defining VNI for reads.
2628 ++MI;
2629 }
2630 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 2631, __extension__ __PRETTY_FUNCTION__))
2631 "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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 2631, __extension__ __PRETTY_FUNCTION__))
;
2632 MachineInstr *LastMI =
2633 Indexes->getInstructionFromIndex(TaintExtent.front().first);
2634 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 2634, __extension__ __PRETTY_FUNCTION__))
;
2635 unsigned TaintNum = 0;
2636 while (true) {
2637 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 2637, __extension__ __PRETTY_FUNCTION__))
;
2638 if (usesLanes(*MI, Other.Reg, Other.SubIdx, TaintedLanes)) {
2639 DEBUG(dbgs() << "\t\ttainted lanes used by: " << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\ttainted lanes used by: "
<< *MI; } } while (false)
;
2640 return false;
2641 }
2642 // LastMI is the last instruction to use the current value.
2643 if (&*MI == LastMI) {
2644 if (++TaintNum == TaintExtent.size())
2645 break;
2646 LastMI = Indexes->getInstructionFromIndex(TaintExtent[TaintNum].first);
2647 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 2647, __extension__ __PRETTY_FUNCTION__))
;
2648 TaintedLanes = TaintExtent[TaintNum].second;
2649 }
2650 ++MI;
2651 }
2652
2653 // The tainted lanes are unused.
2654 V.Resolution = CR_Replace;
2655 ++NumLaneResolves;
2656 }
2657 return true;
2658}
2659
2660bool JoinVals::isPrunedValue(unsigned ValNo, JoinVals &Other) {
2661 Val &V = Vals[ValNo];
2662 if (V.Pruned || V.PrunedComputed)
2663 return V.Pruned;
2664
2665 if (V.Resolution != CR_Erase && V.Resolution != CR_Merge)
2666 return V.Pruned;
2667
2668 // Follow copies up the dominator tree and check if any intermediate value
2669 // has been pruned.
2670 V.PrunedComputed = true;
2671 V.Pruned = Other.isPrunedValue(V.OtherVNI->id, *this);
2672 return V.Pruned;
2673}
2674
2675void JoinVals::pruneValues(JoinVals &Other,
2676 SmallVectorImpl<SlotIndex> &EndPoints,
2677 bool changeInstrs) {
2678 for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
2679 SlotIndex Def = LR.getValNumInfo(i)->def;
2680 switch (Vals[i].Resolution) {
2681 case CR_Keep:
2682 break;
2683 case CR_Replace: {
2684 // This value takes precedence over the value in Other.LR.
2685 LIS->pruneValue(Other.LR, Def, &EndPoints);
2686 // Check if we're replacing an IMPLICIT_DEF value. The IMPLICIT_DEF
2687 // instructions are only inserted to provide a live-out value for PHI
2688 // predecessors, so the instruction should simply go away once its value
2689 // has been replaced.
2690 Val &OtherV = Other.Vals[Vals[i].OtherVNI->id];
2691 bool EraseImpDef = OtherV.ErasableImplicitDef &&
2692 OtherV.Resolution == CR_Keep;
2693 if (!Def.isBlock()) {
2694 if (changeInstrs) {
2695 // Remove <def,read-undef> flags. This def is now a partial redef.
2696 // Also remove dead flags since the joined live range will
2697 // continue past this instruction.
2698 for (MachineOperand &MO :
2699 Indexes->getInstructionFromIndex(Def)->operands()) {
2700 if (MO.isReg() && MO.isDef() && MO.getReg() == Reg) {
2701 if (MO.getSubReg() != 0 && MO.isUndef() && !EraseImpDef)
2702 MO.setIsUndef(false);
2703 MO.setIsDead(false);
2704 }
2705 }
2706 }
2707 // This value will reach instructions below, but we need to make sure
2708 // the live range also reaches the instruction at Def.
2709 if (!EraseImpDef)
2710 EndPoints.push_back(Def);
2711 }
2712 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)
2713 << ": " << Other.LR << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tpruned " << printReg
(Other.Reg) << " at " << Def << ": " <<
Other.LR << '\n'; } } while (false)
;
2714 break;
2715 }
2716 case CR_Erase:
2717 case CR_Merge:
2718 if (isPrunedValue(i, Other)) {
2719 // This value is ultimately a copy of a pruned value in LR or Other.LR.
2720 // We can no longer trust the value mapping computed by
2721 // computeAssignment(), the value that was originally copied could have
2722 // been replaced.
2723 LIS->pruneValue(LR, Def, &EndPoints);
2724 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)
2725 << Def << ": " << LR << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tpruned all of " <<
printReg(Reg) << " at " << Def << ": " <<
LR << '\n'; } } while (false)
;
2726 }
2727 break;
2728 case CR_Unresolved:
2729 case CR_Impossible:
2730 llvm_unreachable("Unresolved conflicts")::llvm::llvm_unreachable_internal("Unresolved conflicts", "/build/llvm-toolchain-snapshot-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 2730)
;
2731 }
2732 }
2733}
2734
2735void JoinVals::pruneSubRegValues(LiveInterval &LI, LaneBitmask &ShrinkMask) {
2736 // Look for values being erased.
2737 bool DidPrune = false;
2738 for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
2739 // We should trigger in all cases in which eraseInstrs() does something.
2740 // match what eraseInstrs() is doing, print a message so
2741 if (Vals[i].Resolution != CR_Erase &&
2742 (Vals[i].Resolution != CR_Keep || !Vals[i].ErasableImplicitDef ||
2743 !Vals[i].Pruned))
2744 continue;
2745
2746 // Check subranges at the point where the copy will be removed.
2747 SlotIndex Def = LR.getValNumInfo(i)->def;
2748 // Print message so mismatches with eraseInstrs() can be diagnosed.
2749 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)
;
2750 for (LiveInterval::SubRange &S : LI.subranges()) {
2751 LiveQueryResult Q = S.Query(Def);
2752
2753 // If a subrange starts at the copy then an undefined value has been
2754 // copied and we must remove that subrange value as well.
2755 VNInfo *ValueOut = Q.valueOutOrDead();
2756 if (ValueOut != nullptr && Q.valueIn() == nullptr) {
2757 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)
2758 << " at " << Def << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tPrune sublane " <<
PrintLaneMask(S.LaneMask) << " at " << Def <<
"\n"; } } while (false)
;
2759 LIS->pruneValue(S, Def, nullptr);
2760 DidPrune = true;
2761 // Mark value number as unused.
2762 ValueOut->markUnused();
2763 continue;
2764 }
2765 // If a subrange ends at the copy, then a value was copied but only
2766 // partially used later. Shrink the subregister range appropriately.
2767 if (Q.valueIn() != nullptr && Q.valueOut() == nullptr) {
2768 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)
2769 << " at " << Def << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tDead uses at sublane " <<
PrintLaneMask(S.LaneMask) << " at " << Def <<
"\n"; } } while (false)
;
2770 ShrinkMask |= S.LaneMask;
2771 }
2772 }
2773 }
2774 if (DidPrune)
2775 LI.removeEmptySubRanges();
2776}
2777
2778/// Check if any of the subranges of @p LI contain a definition at @p Def.
2779static bool isDefInSubRange(LiveInterval &LI, SlotIndex Def) {
2780 for (LiveInterval::SubRange &SR : LI.subranges()) {
2781 if (VNInfo *VNI = SR.Query(Def).valueOutOrDead())
2782 if (VNI->def == Def)
2783 return true;
2784 }
2785 return false;
2786}
2787
2788void JoinVals::pruneMainSegments(LiveInterval &LI, bool &ShrinkMainRange) {
2789 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 2789, __extension__ __PRETTY_FUNCTION__))
;
2790
2791 for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
2792 if (Vals[i].Resolution != CR_Keep)
2793 continue;
2794 VNInfo *VNI = LR.getValNumInfo(i);
2795 if (VNI->isUnused() || VNI->isPHIDef() || isDefInSubRange(LI, VNI->def))
2796 continue;
2797 Vals[i].Pruned = true;
2798 ShrinkMainRange = true;
2799 }
2800}
2801
2802void JoinVals::removeImplicitDefs() {
2803 for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
2804 Val &V = Vals[i];
2805 if (V.Resolution != CR_Keep || !V.ErasableImplicitDef || !V.Pruned)
2806 continue;
2807
2808 VNInfo *VNI = LR.getValNumInfo(i);
2809 VNI->markUnused();
2810 LR.removeValNo(VNI);
2811 }
2812}
2813
2814void JoinVals::eraseInstrs(SmallPtrSetImpl<MachineInstr*> &ErasedInstrs,
2815 SmallVectorImpl<unsigned> &ShrinkRegs,
2816 LiveInterval *LI) {
2817 for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) {
2818 // Get the def location before markUnused() below invalidates it.
2819 SlotIndex Def = LR.getValNumInfo(i)->def;
2820 switch (Vals[i].Resolution) {
2821 case CR_Keep: {
2822 // If an IMPLICIT_DEF value is pruned, it doesn't serve a purpose any
2823 // longer. The IMPLICIT_DEF instructions are only inserted by
2824 // PHIElimination to guarantee that all PHI predecessors have a value.
2825 if (!Vals[i].ErasableImplicitDef || !Vals[i].Pruned)
2826 break;
2827 // Remove value number i from LR.
2828 // For intervals with subranges, removing a segment from the main range
2829 // may require extending the previous segment: for each definition of
2830 // a subregister, there will be a corresponding def in the main range.
2831 // That def may fall in the middle of a segment from another subrange.
2832 // In such cases, removing this def from the main range must be
2833 // complemented by extending the main range to account for the liveness
2834 // of the other subrange.
2835 VNInfo *VNI = LR.getValNumInfo(i);
2836 SlotIndex Def = VNI->def;
2837 // The new end point of the main range segment to be extended.
2838 SlotIndex NewEnd;
2839 if (LI != nullptr) {
2840 LiveRange::iterator I = LR.FindSegmentContaining(Def);
2841 assert(I != LR.end())(static_cast <bool> (I != LR.end()) ? void (0) : __assert_fail
("I != LR.end()", "/build/llvm-toolchain-snapshot-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 2841, __extension__ __PRETTY_FUNCTION__))
;
2842 // Do not extend beyond the end of the segment being removed.
2843 // The segment may have been pruned in preparation for joining
2844 // live ranges.
2845 NewEnd = I->end;
2846 }
2847
2848 LR.removeValNo(VNI);
2849 // Note that this VNInfo is reused and still referenced in NewVNInfo,
2850 // make it appear like an unused value number.
2851 VNI->markUnused();
2852
2853 if (LI != nullptr && LI->hasSubRanges()) {
2854 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 2854, __extension__ __PRETTY_FUNCTION__))
;
2855 // Determine the end point based on the subrange information:
2856 // minimum of (earliest def of next segment,
2857 // latest end point of containing segment)
2858 SlotIndex ED, LE;
2859 for (LiveInterval::SubRange &SR : LI->subranges()) {
2860 LiveRange::iterator I = SR.find(Def);
2861 if (I == SR.end())
2862 continue;
2863 if (I->start > Def)
2864 ED = ED.isValid() ? std::min(ED, I->start) : I->start;
2865 else
2866 LE = LE.isValid() ? std::max(LE, I->end) : I->end;
2867 }
2868 if (LE.isValid())
2869 NewEnd = std::min(NewEnd, LE);
2870 if (ED.isValid())
2871 NewEnd = std::min(NewEnd, ED);
2872
2873 // We only want to do the extension if there was a subrange that
2874 // was live across Def.
2875 if (LE.isValid()) {
2876 LiveRange::iterator S = LR.find(Def);
2877 if (S != LR.begin())
2878 std::prev(S)->end = NewEnd;
2879 }
2880 }
2881 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)
2882 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)
2883 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)
2884 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)
2885 })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)
;
2886 LLVM_FALLTHROUGH[[clang::fallthrough]];
2887 }
2888
2889 case CR_Erase: {
2890 MachineInstr *MI = Indexes->getInstructionFromIndex(Def);
2891 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 2891, __extension__ __PRETTY_FUNCTION__))
;
2892 if (MI->isCopy()) {
2893 unsigned Reg = MI->getOperand(1).getReg();
2894 if (TargetRegisterInfo::isVirtualRegister(Reg) &&
2895 Reg != CP.getSrcReg() && Reg != CP.getDstReg())
2896 ShrinkRegs.push_back(Reg);
2897 }
2898 ErasedInstrs.insert(MI);
2899 DEBUG(dbgs() << "\t\terased:\t" << Def << '\t' << *MI)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\terased:\t" << Def <<
'\t' << *MI; } } while (false)
;
2900 LIS->RemoveMachineInstrFromMaps(*MI);
2901 MI->eraseFromParent();
2902 break;
2903 }
2904 default:
2905 break;
2906 }
2907 }
2908}
2909
2910void RegisterCoalescer::joinSubRegRanges(LiveRange &LRange, LiveRange &RRange,
2911 LaneBitmask LaneMask,
2912 const CoalescerPair &CP) {
2913 SmallVector<VNInfo*, 16> NewVNInfo;
2914 JoinVals RHSVals(RRange, CP.getSrcReg(), CP.getSrcIdx(), LaneMask,
2915 NewVNInfo, CP, LIS, TRI, true, true);
2916 JoinVals LHSVals(LRange, CP.getDstReg(), CP.getDstIdx(), LaneMask,
2917 NewVNInfo, CP, LIS, TRI, true, true);
2918
2919 // Compute NewVNInfo and resolve conflicts (see also joinVirtRegs())
2920 // We should be able to resolve all conflicts here as we could successfully do
2921 // it on the mainrange already. There is however a problem when multiple
2922 // ranges get mapped to the "overflow" lane mask bit which creates unexpected
2923 // interferences.
2924 if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals)) {
2925 // We already determined that it is legal to merge the intervals, so this
2926 // should never fail.
2927 llvm_unreachable("*** Couldn't join subrange!\n")::llvm::llvm_unreachable_internal("*** Couldn't join subrange!\n"
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 2927)
;
2928 }
2929 if (!LHSVals.resolveConflicts(RHSVals) ||
2930 !RHSVals.resolveConflicts(LHSVals)) {
2931 // We already determined that it is legal to merge the intervals, so this
2932 // should never fail.
2933 llvm_unreachable("*** Couldn't join subrange!\n")::llvm::llvm_unreachable_internal("*** Couldn't join subrange!\n"
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 2933)
;
2934 }
2935
2936 // The merging algorithm in LiveInterval::join() can't handle conflicting
2937 // value mappings, so we need to remove any live ranges that overlap a
2938 // CR_Replace resolution. Collect a set of end points that can be used to
2939 // restore the live range after joining.
2940 SmallVector<SlotIndex, 8> EndPoints;
2941 LHSVals.pruneValues(RHSVals, EndPoints, false);
2942 RHSVals.pruneValues(LHSVals, EndPoints, false);
2943
2944 LHSVals.removeImplicitDefs();
2945 RHSVals.removeImplicitDefs();
2946
2947 LRange.verify();
2948 RRange.verify();
2949
2950 // Join RRange into LHS.
2951 LRange.join(RRange, LHSVals.getAssignments(), RHSVals.getAssignments(),
2952 NewVNInfo);
2953
2954 DEBUG(dbgs() << "\t\tjoined lanes: " << LRange << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tjoined lanes: " <<
LRange << "\n"; } } while (false)
;
2955 if (EndPoints.empty())
2956 return;
2957
2958 // Recompute the parts of the live range we had to remove because of
2959 // CR_Replace conflicts.
2960 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)
2961 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)
2962 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)
2963 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)
2964 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)
2965 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)
2966 }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)
2967 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)
2968 })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)
;
2969 LIS->extendToIndices(LRange, EndPoints);
2970}
2971
2972void RegisterCoalescer::mergeSubRangeInto(LiveInterval &LI,
2973 const LiveRange &ToMerge,
2974 LaneBitmask LaneMask,
2975 CoalescerPair &CP) {
2976 BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
2977 LI.refineSubRanges(Allocator, LaneMask,
2978 [this,&Allocator,&ToMerge,&CP](LiveInterval::SubRange &SR) {
2979 if (SR.empty()) {
2980 SR.assign(ToMerge, Allocator);
2981 } else {
2982 // joinSubRegRange() destroys the merged range, so we need a copy.
2983 LiveRange RangeCopy(ToMerge, Allocator);
2984 joinSubRegRanges(SR, RangeCopy, SR.LaneMask, CP);
2985 }
2986 });
2987}
2988
2989bool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP) {
2990 SmallVector<VNInfo*, 16> NewVNInfo;
2991 LiveInterval &RHS = LIS->getInterval(CP.getSrcReg());
2992 LiveInterval &LHS = LIS->getInterval(CP.getDstReg());
2993 bool TrackSubRegLiveness = MRI->shouldTrackSubRegLiveness(*CP.getNewRC());
2994 JoinVals RHSVals(RHS, CP.getSrcReg(), CP.getSrcIdx(), LaneBitmask::getNone(),
2995 NewVNInfo, CP, LIS, TRI, false, TrackSubRegLiveness);
2996 JoinVals LHSVals(LHS, CP.getDstReg(), CP.getDstIdx(), LaneBitmask::getNone(),
2997 NewVNInfo, CP, LIS, TRI, false, TrackSubRegLiveness);
2998
2999 DEBUG(dbgs() << "\t\tRHS = " << RHSdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tRHS = " << RHS <<
"\n\t\tLHS = " << LHS << '\n'; } } while (false)
3000 << "\n\t\tLHS = " << LHSdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tRHS = " << RHS <<
"\n\t\tLHS = " << LHS << '\n'; } } while (false)
3001 << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tRHS = " << RHS <<
"\n\t\tLHS = " << LHS << '\n'; } } while (false)
;
3002
3003 // First compute NewVNInfo and the simple value mappings.
3004 // Detect impossible conflicts early.
3005 if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals))
3006 return false;
3007
3008 // Some conflicts can only be resolved after all values have been mapped.
3009 if (!LHSVals.resolveConflicts(RHSVals) || !RHSVals.resolveConflicts(LHSVals))
3010 return false;
3011
3012 // All clear, the live ranges can be merged.
3013 if (RHS.hasSubRanges() || LHS.hasSubRanges()) {
3014 BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
3015
3016 // Transform lanemasks from the LHS to masks in the coalesced register and
3017 // create initial subranges if necessary.
3018 unsigned DstIdx = CP.getDstIdx();
3019 if (!LHS.hasSubRanges()) {
3020 LaneBitmask Mask = DstIdx == 0 ? CP.getNewRC()->getLaneMask()
3021 : TRI->getSubRegIndexLaneMask(DstIdx);
3022 // LHS must support subregs or we wouldn't be in this codepath.
3023 assert(Mask.any())(static_cast <bool> (Mask.any()) ? void (0) : __assert_fail
("Mask.any()", "/build/llvm-toolchain-snapshot-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 3023, __extension__ __PRETTY_FUNCTION__))
;
3024 LHS.createSubRangeFrom(Allocator, Mask, LHS);
3025 } else if (DstIdx != 0) {
3026 // Transform LHS lanemasks to new register class if necessary.
3027 for (LiveInterval::SubRange &R : LHS.subranges()) {
3028 LaneBitmask Mask = TRI->composeSubRegIndexLaneMask(DstIdx, R.LaneMask);
3029 R.LaneMask = Mask;
3030 }
3031 }
3032 DEBUG(dbgs() << "\t\tLHST = " << printReg(CP.getDstReg())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tLHST = " << printReg
(CP.getDstReg()) << ' ' << LHS << '\n'; } }
while (false)
3033 << ' ' << LHS << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\t\tLHST = " << printReg
(CP.getDstReg()) << ' ' << LHS << '\n'; } }
while (false)
;
3034
3035 // Determine lanemasks of RHS in the coalesced register and merge subranges.
3036 unsigned SrcIdx = CP.getSrcIdx();
3037 if (!RHS.hasSubRanges()) {
3038 LaneBitmask Mask = SrcIdx == 0 ? CP.getNewRC()->getLaneMask()
3039 : TRI->getSubRegIndexLaneMask(SrcIdx);
3040 mergeSubRangeInto(LHS, RHS, Mask, CP);
3041 } else {
3042 // Pair up subranges and merge.
3043 for (LiveInterval::SubRange &R : RHS.subranges()) {
3044 LaneBitmask Mask = TRI->composeSubRegIndexLaneMask(SrcIdx, R.LaneMask);
3045 mergeSubRangeInto(LHS, R, Mask, CP);
3046 }
3047 }
3048 DEBUG(dbgs() << "\tJoined SubRanges " << LHS << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "\tJoined SubRanges " <<
LHS << "\n"; } } while (false)
;
3049
3050 // Pruning implicit defs from subranges may result in the main range
3051 // having stale segments.
3052 LHSVals.pruneMainSegments(LHS, ShrinkMainRange);
3053
3054 LHSVals.pruneSubRegValues(LHS, ShrinkMask);
3055 RHSVals.pruneSubRegValues(LHS, ShrinkMask);
3056 }
3057
3058 // The merging algorithm in LiveInterval::join() can't handle conflicting
3059 // value mappings, so we need to remove any live ranges that overlap a
3060 // CR_Replace resolution. Collect a set of end points that can be used to
3061 // restore the live range after joining.
3062 SmallVector<SlotIndex, 8> EndPoints;
3063 LHSVals.pruneValues(RHSVals, EndPoints, true);
3064 RHSVals.pruneValues(LHSVals, EndPoints, true);
3065
3066 // Erase COPY and IMPLICIT_DEF instructions. This may cause some external
3067 // registers to require trimming.
3068 SmallVector<unsigned, 8> ShrinkRegs;
3069 LHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs, &LHS);
3070 RHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs);
3071 while (!ShrinkRegs.empty())
3072 shrinkToUses(&LIS->getInterval(ShrinkRegs.pop_back_val()));
3073
3074 // Join RHS into LHS.
3075 LHS.join(RHS, LHSVals.getAssignments(), RHSVals.getAssignments(), NewVNInfo);
3076
3077 // Kill flags are going to be wrong if the live ranges were overlapping.
3078 // Eventually, we should simply clear all kill flags when computing live
3079 // ranges. They are reinserted after register allocation.
3080 MRI->clearKillFlags(LHS.reg);
3081 MRI->clearKillFlags(RHS.reg);
3082
3083 if (!EndPoints.empty()) {
3084 // Recompute the parts of the live range we had to remove because of
3085 // CR_Replace conflicts.
3086 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)
3087 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)
3088 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)
3089 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)
3090 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)
3091 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)
3092 }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)
3093 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)
3094 })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)
;
3095 LIS->extendToIndices((LiveRange&)LHS, EndPoints);
3096 }
3097
3098 return true;
3099}
3100
3101bool RegisterCoalescer::joinIntervals(CoalescerPair &CP) {
3102 return CP.isPhys() ? joinReservedPhysReg(CP) : joinVirtRegs(CP);
3103}
3104
3105namespace {
3106
3107/// Information concerning MBB coalescing priority.
3108struct MBBPriorityInfo {
3109 MachineBasicBlock *MBB;
3110 unsigned Depth;
3111 bool IsSplit;
3112
3113 MBBPriorityInfo(MachineBasicBlock *mbb, unsigned depth, bool issplit)
3114 : MBB(mbb), Depth(depth), IsSplit(issplit) {}
3115};
3116
3117} // end anonymous namespace
3118
3119/// C-style comparator that sorts first based on the loop depth of the basic
3120/// block (the unsigned), and then on the MBB number.
3121///
3122/// EnableGlobalCopies assumes that the primary sort key is loop depth.
3123static int compareMBBPriority(const MBBPriorityInfo *LHS,
3124 const MBBPriorityInfo *RHS) {
3125 // Deeper loops first
3126 if (LHS->Depth != RHS->Depth)
3127 return LHS->Depth > RHS->Depth ? -1 : 1;
3128
3129 // Try to unsplit critical edges next.
3130 if (LHS->IsSplit != RHS->IsSplit)
3131 return LHS->IsSplit ? -1 : 1;
3132
3133 // Prefer blocks that are more connected in the CFG. This takes care of
3134 // the most difficult copies first while intervals are short.
3135 unsigned cl = LHS->MBB->pred_size() + LHS->MBB->succ_size();
3136 unsigned cr = RHS->MBB->pred_size() + RHS->MBB->succ_size();
3137 if (cl != cr)
3138 return cl > cr ? -1 : 1;
3139
3140 // As a last resort, sort by block number.
3141 return LHS->MBB->getNumber() < RHS->MBB->getNumber() ? -1 : 1;
3142}
3143
3144/// \returns true if the given copy uses or defines a local live range.
3145static bool isLocalCopy(MachineInstr *Copy, const LiveIntervals *LIS) {
3146 if (!Copy->isCopy())
3147 return false;
3148
3149 if (Copy->getOperand(1).isUndef())
3150 return false;
3151
3152 unsigned SrcReg = Copy->getOperand(1).getReg();
3153 unsigned DstReg = Copy->getOperand(0).getReg();
3154 if (TargetRegisterInfo::isPhysicalRegister(SrcReg)
3155 || TargetRegisterInfo::isPhysicalRegister(DstReg))
3156 return false;
3157
3158 return LIS->intervalIsInOneMBB(LIS->getInterval(SrcReg))
3159 || LIS->intervalIsInOneMBB(LIS->getInterval(DstReg));
3160}
3161
3162bool RegisterCoalescer::
3163copyCoalesceWorkList(MutableArrayRef<MachineInstr*> CurrList) {
3164 bool Progress = false;
3165 for (unsigned i = 0, e = CurrList.size(); i != e; ++i) {
3166 if (!CurrList[i])
3167 continue;
3168 // Skip instruction pointers that have already been erased, for example by
3169 // dead code elimination.
3170 if (ErasedInstrs.count(CurrList[i])) {
3171 CurrList[i] = nullptr;
3172 continue;
3173 }
3174 bool Again = false;
3175 bool Success = joinCopy(CurrList[i], Again);
3176 Progress |= Success;
3177 if (Success || !Again)
3178 CurrList[i] = nullptr;
3179 }
3180 return Progress;
3181}
3182
3183/// Check if DstReg is a terminal node.
3184/// I.e., it does not have any affinity other than \p Copy.
3185static bool isTerminalReg(unsigned DstReg, const MachineInstr &Copy,
3186 const MachineRegisterInfo *MRI) {
3187 assert(Copy.isCopyLike())(static_cast <bool> (Copy.isCopyLike()) ? void (0) : __assert_fail
("Copy.isCopyLike()", "/build/llvm-toolchain-snapshot-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 3187, __extension__ __PRETTY_FUNCTION__))
;
3188 // Check if the destination of this copy as any other affinity.
3189 for (const MachineInstr &MI : MRI->reg_nodbg_instructions(DstReg))
3190 if (&MI != &Copy && MI.isCopyLike())
3191 return false;
3192 return true;
3193}
3194
3195bool RegisterCoalescer::applyTerminalRule(const MachineInstr &Copy) const {
3196 assert(Copy.isCopyLike())(static_cast <bool> (Copy.isCopyLike()) ? void (0) : __assert_fail
("Copy.isCopyLike()", "/build/llvm-toolchain-snapshot-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 3196, __extension__ __PRETTY_FUNCTION__))
;
3197 if (!UseTerminalRule)
19
Assuming the condition is false
20
Taking false branch
3198 return false;
3199 unsigned DstReg, DstSubReg, SrcReg, SrcSubReg;
3200 isMoveInstr(*TRI, &Copy, SrcReg, DstReg, SrcSubReg, DstSubReg);
3201 // Check if the destination of this copy has any other affinity.
3202 if (TargetRegisterInfo::isPhysicalRegister(DstReg) ||
21
Taking false branch
3203 // If SrcReg is a physical register, the copy won't be coalesced.
3204 // Ignoring it may have other side effect (like missing
3205 // rematerialization). So keep it.
3206 TargetRegisterInfo::isPhysicalRegister(SrcReg) ||
3207 !isTerminalReg(DstReg, Copy, MRI))
3208 return false;
3209
3210 // DstReg is a terminal node. Check if it interferes with any other
3211 // copy involving SrcReg.
3212 const MachineBasicBlock *OrigBB = Copy.getParent();
3213 const LiveInterval &DstLI = LIS->getInterval(DstReg);
3214 for (const MachineInstr &MI : MRI->reg_nodbg_instructions(SrcReg)) {
3215 // Technically we should check if the weight of the new copy is
3216 // interesting compared to the other one and update the weight
3217 // of the copies accordingly. However, this would only work if
3218 // we would gather all the copies first then coalesce, whereas
3219 // right now we interleave both actions.
3220 // For now, just consider the copies that are in the same block.
3221 if (&MI == &Copy || !MI.isCopyLike() || MI.getParent() != OrigBB)
22
Assuming the condition is false
23
Assuming the condition is false
24
Taking false branch
35
Assuming the condition is false
36
Assuming the condition is false
37
Taking false branch
3222 continue;
3223 unsigned OtherReg, OtherSubReg, OtherSrcReg, OtherSrcSubReg;
38
'OtherSrcReg' declared without an initial value
3224 isMoveInstr(*TRI, &Copy, OtherSrcReg, OtherReg, OtherSrcSubReg,
25
Calling 'isMoveInstr'
29
Returning from 'isMoveInstr'
39
Calling 'isMoveInstr'
43
Returning from 'isMoveInstr'
3225 OtherSubReg);
3226 if (OtherReg == SrcReg)
30
Assuming 'OtherReg' is equal to 'SrcReg'
31
Taking true branch
44
Taking true branch
3227 OtherReg = OtherSrcReg;
45
Assigned value is garbage or undefined
3228 // Check if OtherReg is a non-terminal.
3229 if (TargetRegisterInfo::isPhysicalRegister(OtherReg) ||
32
Taking false branch
3230 isTerminalReg(OtherReg, MI, MRI))
3231 continue;
3232 // Check that OtherReg interfere with DstReg.
3233 if (LIS->getInterval(OtherReg).overlaps(DstLI)) {
33
Assuming the condition is false
34
Taking false branch
3234 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)
;
3235 return true;
3236 }
3237 }
3238 return false;
3239}
3240
3241void
3242RegisterCoalescer::copyCoalesceInMBB(MachineBasicBlock *MBB) {
3243 DEBUG(dbgs() << MBB->getName() << ":\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << MBB->getName() << ":\n"
; } } while (false)
;
3244
3245 // Collect all copy-like instructions in MBB. Don't start coalescing anything
3246 // yet, it might invalidate the iterator.
3247 const unsigned PrevSize = WorkList.size();
3248 if (JoinGlobalCopies) {
15
Taking true branch
3249 SmallVector<MachineInstr*, 2> LocalTerminals;
3250 SmallVector<MachineInstr*, 2> GlobalTerminals;
3251 // Coalesce copies bottom-up to coalesce local defs before local uses. They
3252 // are not inherently easier to resolve, but slightly preferable until we
3253 // have local live range splitting. In particular this is required by
3254 // cmp+jmp macro fusion.
3255 for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end();
16
Loop condition is true. Entering loop body
3256 MII != E; ++MII) {
3257 if (!MII->isCopyLike())
17
Taking false branch
3258 continue;
3259 bool ApplyTerminalRule = applyTerminalRule(*MII);
18
Calling 'RegisterCoalescer::applyTerminalRule'
3260 if (isLocalCopy(&(*MII), LIS)) {
3261 if (ApplyTerminalRule)
3262 LocalTerminals.push_back(&(*MII));
3263 else
3264 LocalWorkList.push_back(&(*MII));
3265 } else {
3266 if (ApplyTerminalRule)
3267 GlobalTerminals.push_back(&(*MII));
3268 else
3269 WorkList.push_back(&(*MII));
3270 }
3271 }
3272 // Append the copies evicted by the terminal rule at the end of the list.
3273 LocalWorkList.append(LocalTerminals.begin(), LocalTerminals.end());
3274 WorkList.append(GlobalTerminals.begin(), GlobalTerminals.end());
3275 }
3276 else {
3277 SmallVector<MachineInstr*, 2> Terminals;
3278 for (MachineInstr &MII : *MBB)
3279 if (MII.isCopyLike()) {
3280 if (applyTerminalRule(MII))
3281 Terminals.push_back(&MII);
3282 else
3283 WorkList.push_back(&MII);
3284 }
3285 // Append the copies evicted by the terminal rule at the end of the list.
3286 WorkList.append(Terminals.begin(), Terminals.end());
3287 }
3288 // Try coalescing the collected copies immediately, and remove the nulls.
3289 // This prevents the WorkList from getting too large since most copies are
3290 // joinable on the first attempt.
3291 MutableArrayRef<MachineInstr*>
3292 CurrList(WorkList.begin() + PrevSize, WorkList.end());
3293 if (copyCoalesceWorkList(CurrList))
3294 WorkList.erase(std::remove(WorkList.begin() + PrevSize, WorkList.end(),
3295 nullptr), WorkList.end());
3296}
3297
3298void RegisterCoalescer::coalesceLocals() {
3299 copyCoalesceWorkList(LocalWorkList);
3300 for (unsigned j = 0, je = LocalWorkList.size(); j != je; ++j) {
3301 if (LocalWorkList[j])
3302 WorkList.push_back(LocalWorkList[j]);
3303 }
3304 LocalWorkList.clear();
3305}
3306
3307void RegisterCoalescer::joinAllIntervals() {
3308 DEBUG(dbgs() << "********** JOINING INTERVALS ***********\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "********** JOINING INTERVALS ***********\n"
; } } while (false)
;
3309 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-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 3309, __extension__ __PRETTY_FUNCTION__))
;
3310
3311 std::vector<MBBPriorityInfo> MBBs;
3312 MBBs.reserve(MF->size());
3313 for (MachineFunction::iterator I = MF->begin(), E = MF->end(); I != E; ++I) {
8
Loop condition is false. Execution continues on line 3318
3314 MachineBasicBlock *MBB = &*I;
3315 MBBs.push_back(MBBPriorityInfo(MBB, Loops->getLoopDepth(MBB),
3316 JoinSplitEdges && isSplitEdge(MBB)));
3317 }
3318 array_pod_sort(MBBs.begin(), MBBs.end(), compareMBBPriority);
3319
3320 // Coalesce intervals in MBB priority order.
3321 unsigned CurrDepth = std::numeric_limits<unsigned>::max();
3322 for (unsigned i = 0, e = MBBs.size(); i != e; ++i) {
9
Assuming 'i' is not equal to 'e'
10
Loop condition is true. Entering loop body
3323 // Try coalescing the collected local copies for deeper loops.
3324 if (JoinGlobalCopies && MBBs[i].Depth < CurrDepth) {
11
Assuming the condition is true
12
Assuming the condition is false
13
Taking false branch
3325 coalesceLocals();
3326 CurrDepth = MBBs[i].Depth;
3327 }
3328 copyCoalesceInMBB(MBBs[i].MBB);
14
Calling 'RegisterCoalescer::copyCoalesceInMBB'
3329 }
3330 coalesceLocals();
3331
3332 // Joining intervals can allow other intervals to be joined. Iteratively join
3333 // until we make no progress.
3334 while (copyCoalesceWorkList(WorkList))
3335 /* empty */ ;
3336}
3337
3338void RegisterCoalescer::releaseMemory() {
3339 ErasedInstrs.clear();
3340 WorkList.clear();
3341 DeadDefs.clear();
3342 InflateRegs.clear();
3343}
3344
3345bool RegisterCoalescer::runOnMachineFunction(MachineFunction &fn) {
3346 MF = &fn;
3347 MRI = &fn.getRegInfo();
3348 const TargetSubtargetInfo &STI = fn.getSubtarget();
3349 TRI = STI.getRegisterInfo();
3350 TII = STI.getInstrInfo();
3351 LIS = &getAnalysis<LiveIntervals>();
3352 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
3353 Loops = &getAnalysis<MachineLoopInfo>();
3354 if (EnableGlobalCopies == cl::BOU_UNSET)
1
Assuming the condition is true
2
Taking true branch
3355 JoinGlobalCopies = STI.enableJoinGlobalCopies();
3356 else
3357 JoinGlobalCopies = (EnableGlobalCopies == cl::BOU_TRUE);
3358
3359 // The MachineScheduler does not currently require JoinSplitEdges. This will
3360 // either be enabled unconditionally or replaced by a more general live range
3361 // splitting optimization.
3362 JoinSplitEdges = EnableJoinSplits;
3363
3364 DEBUG(dbgs() << "********** SIMPLE REGISTER COALESCING **********\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "********** SIMPLE REGISTER COALESCING **********\n"
<< "********** Function: " << MF->getName() <<
'\n'; } } while (false)
3365 << "********** Function: " << MF->getName() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dbgs() << "********** SIMPLE REGISTER COALESCING **********\n"
<< "********** Function: " << MF->getName() <<
'\n'; } } while (false)
;
3366
3367 if (VerifyCoalescing)
3
Assuming the condition is false
4
Taking false branch
3368 MF->verify(this, "Before register coalescing");
3369
3370 RegClassInfo.runOnMachineFunction(fn);
3371
3372 // Join (coalesce) intervals if requested.
3373 if (EnableJoining)
5
Assuming the condition is true
6
Taking true branch
3374 joinAllIntervals();
7
Calling 'RegisterCoalescer::joinAllIntervals'
3375
3376 // After deleting a lot of copies, register classes may be less constrained.
3377 // Removing sub-register operands may allow GR32_ABCD -> GR32 and DPR_VFP2 ->
3378 // DPR inflation.
3379 array_pod_sort(InflateRegs.begin(), InflateRegs.end());
3380 InflateRegs.erase(std::unique(InflateRegs.begin(), InflateRegs.end()),
3381 InflateRegs.end());
3382 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)
;
3383 for (unsigned i = 0, e = InflateRegs.size(); i != e; ++i) {
3384 unsigned Reg = InflateRegs[i];
3385 if (MRI->reg_nodbg_empty(Reg))
3386 continue;
3387 if (MRI->recomputeRegClass(Reg)) {
3388 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)
3389 << 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)
;
3390 ++NumInflated;
3391
3392 LiveInterval &LI = LIS->getInterval(Reg);
3393 if (LI.hasSubRanges()) {
3394 // If the inflated register class does not support subregisters anymore
3395 // remove the subranges.
3396 if (!MRI->shouldTrackSubRegLiveness(Reg)) {
3397 LI.clearSubRanges();
3398 } else {
3399#ifndef NDEBUG
3400 LaneBitmask MaxMask = MRI->getMaxLaneMaskForVReg(Reg);
3401 // If subranges are still supported, then the same subregs
3402 // should still be supported.
3403 for (LiveInterval::SubRange &S : LI.subranges()) {
3404 assert((S.LaneMask & ~MaxMask).none())(static_cast <bool> ((S.LaneMask & ~MaxMask).none()
) ? void (0) : __assert_fail ("(S.LaneMask & ~MaxMask).none()"
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/CodeGen/RegisterCoalescer.cpp"
, 3404, __extension__ __PRETTY_FUNCTION__))
;
3405 }
3406#endif
3407 }
3408 }
3409 }
3410 }
3411
3412 DEBUG(dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc")) { dump(); } } while (false)
;
3413 if (VerifyCoalescing)
3414 MF->verify(this, "After register coalescing");
3415 return true;
3416}
3417
3418void RegisterCoalescer::print(raw_ostream &O, const Module* m) const {
3419 LIS->print(O, m);
3420}