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