David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1 | //===-- SimpleRegisterCoalescing.cpp - Register Coalescing ----------------===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Chris Lattner | 4ee451d | 2007-12-29 20:36:04 +0000 | [diff] [blame] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This file implements a simple register coalescing pass that attempts to |
| 11 | // aggressively coalesce every register copy that it can. |
| 12 | // |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
Evan Cheng | 3b1f55e | 2007-07-31 22:37:44 +0000 | [diff] [blame] | 15 | #define DEBUG_TYPE "regcoalescing" |
Evan Cheng | a461c4d | 2007-11-05 17:41:38 +0000 | [diff] [blame] | 16 | #include "SimpleRegisterCoalescing.h" |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 17 | #include "VirtRegMap.h" |
Evan Cheng | a461c4d | 2007-11-05 17:41:38 +0000 | [diff] [blame] | 18 | #include "llvm/CodeGen/LiveIntervalAnalysis.h" |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 19 | #include "llvm/Value.h" |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 20 | #include "llvm/CodeGen/MachineFrameInfo.h" |
| 21 | #include "llvm/CodeGen/MachineInstr.h" |
Evan Cheng | 22f07ff | 2007-12-11 02:09:15 +0000 | [diff] [blame] | 22 | #include "llvm/CodeGen/MachineLoopInfo.h" |
Chris Lattner | 84bc542 | 2007-12-31 04:13:23 +0000 | [diff] [blame] | 23 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 24 | #include "llvm/CodeGen/Passes.h" |
David Greene | 2c17c4d | 2007-09-06 16:18:45 +0000 | [diff] [blame] | 25 | #include "llvm/CodeGen/RegisterCoalescer.h" |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 26 | #include "llvm/Target/TargetInstrInfo.h" |
| 27 | #include "llvm/Target/TargetMachine.h" |
Owen Anderson | 95dad83 | 2008-10-07 20:22:28 +0000 | [diff] [blame] | 28 | #include "llvm/Target/TargetOptions.h" |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 29 | #include "llvm/Support/CommandLine.h" |
| 30 | #include "llvm/Support/Debug.h" |
Torok Edwin | c25e758 | 2009-07-11 20:10:48 +0000 | [diff] [blame] | 31 | #include "llvm/Support/ErrorHandling.h" |
Daniel Dunbar | ce63ffb | 2009-07-25 00:23:56 +0000 | [diff] [blame] | 32 | #include "llvm/Support/raw_ostream.h" |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 33 | #include "llvm/ADT/SmallSet.h" |
| 34 | #include "llvm/ADT/Statistic.h" |
| 35 | #include "llvm/ADT/STLExtras.h" |
| 36 | #include <algorithm> |
| 37 | #include <cmath> |
| 38 | using namespace llvm; |
| 39 | |
| 40 | STATISTIC(numJoins , "Number of interval joins performed"); |
Evan Cheng | 8c08d8c | 2009-01-23 02:15:19 +0000 | [diff] [blame] | 41 | STATISTIC(numCrossRCs , "Number of cross class joins performed"); |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 42 | STATISTIC(numCommutes , "Number of instruction commuting performed"); |
| 43 | STATISTIC(numExtends , "Number of copies extended"); |
Evan Cheng | cd04708 | 2008-08-30 09:09:33 +0000 | [diff] [blame] | 44 | STATISTIC(NumReMats , "Number of instructions re-materialized"); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 45 | STATISTIC(numPeep , "Number of identity moves eliminated after coalescing"); |
| 46 | STATISTIC(numAborts , "Number of times interval joining aborted"); |
Evan Cheng | 77fde2c | 2009-02-08 07:48:37 +0000 | [diff] [blame] | 47 | STATISTIC(numDeadValNo, "Number of valno def marked dead"); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 48 | |
| 49 | char SimpleRegisterCoalescing::ID = 0; |
Dan Gohman | 844731a | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 50 | static cl::opt<bool> |
| 51 | EnableJoining("join-liveintervals", |
| 52 | cl::desc("Coalesce copies (default=true)"), |
| 53 | cl::init(true)); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 54 | |
Dan Gohman | 844731a | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 55 | static cl::opt<bool> |
Evan Cheng | c95be59 | 2009-07-21 00:22:59 +0000 | [diff] [blame] | 56 | DisableCrossClassJoin("disable-cross-class-join", |
| 57 | cl::desc("Avoid coalescing cross register class copies"), |
| 58 | cl::init(false), cl::Hidden); |
Evan Cheng | 8fc9a10 | 2007-11-06 08:52:21 +0000 | [diff] [blame] | 59 | |
Evan Cheng | 0490dcb | 2009-04-30 18:39:57 +0000 | [diff] [blame] | 60 | static cl::opt<bool> |
| 61 | PhysJoinTweak("tweak-phys-join-heuristics", |
| 62 | cl::desc("Tweak heuristics for joining phys reg with vr"), |
| 63 | cl::init(false), cl::Hidden); |
| 64 | |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 65 | static RegisterPass<SimpleRegisterCoalescing> |
Dan Gohman | 844731a | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 66 | X("simple-register-coalescing", "Simple Register Coalescing"); |
David Greene | 2c17c4d | 2007-09-06 16:18:45 +0000 | [diff] [blame] | 67 | |
Dan Gohman | 844731a | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 68 | // Declare that we implement the RegisterCoalescer interface |
| 69 | static RegisterAnalysisGroup<RegisterCoalescer, true/*The Default*/> V(X); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 70 | |
Dan Gohman | 6ddba2b | 2008-05-13 02:05:11 +0000 | [diff] [blame] | 71 | const PassInfo *const llvm::SimpleRegisterCoalescingID = &X; |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 72 | |
| 73 | void SimpleRegisterCoalescing::getAnalysisUsage(AnalysisUsage &AU) const { |
Dan Gohman | 845012e | 2009-07-31 23:37:33 +0000 | [diff] [blame] | 74 | AU.setPreservesCFG(); |
Evan Cheng | bbeeb2a | 2008-09-22 20:58:04 +0000 | [diff] [blame] | 75 | AU.addRequired<LiveIntervals>(); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 76 | AU.addPreserved<LiveIntervals>(); |
Evan Cheng | bbeeb2a | 2008-09-22 20:58:04 +0000 | [diff] [blame] | 77 | AU.addRequired<MachineLoopInfo>(); |
Bill Wendling | 67d65bb | 2008-01-04 20:54:55 +0000 | [diff] [blame] | 78 | AU.addPreserved<MachineLoopInfo>(); |
| 79 | AU.addPreservedID(MachineDominatorsID); |
Owen Anderson | 95dad83 | 2008-10-07 20:22:28 +0000 | [diff] [blame] | 80 | if (StrongPHIElim) |
| 81 | AU.addPreservedID(StrongPHIEliminationID); |
| 82 | else |
| 83 | AU.addPreservedID(PHIEliminationID); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 84 | AU.addPreservedID(TwoAddressInstructionPassID); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 85 | MachineFunctionPass::getAnalysisUsage(AU); |
| 86 | } |
| 87 | |
Gabor Greif | e510b3a | 2007-07-09 12:00:59 +0000 | [diff] [blame] | 88 | /// AdjustCopiesBackFrom - We found a non-trivially-coalescable copy with IntA |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 89 | /// being the source and IntB being the dest, thus this defines a value number |
| 90 | /// in IntB. If the source value number (in IntA) is defined by a copy from B, |
| 91 | /// see if we can merge these two pieces of B into a single value number, |
| 92 | /// eliminating a copy. For example: |
| 93 | /// |
| 94 | /// A3 = B0 |
| 95 | /// ... |
| 96 | /// B1 = A3 <- this copy |
| 97 | /// |
| 98 | /// In this case, B0 can be extended to where the B1 copy lives, allowing the B1 |
| 99 | /// value number to be replaced with B0 (which simplifies the B liveinterval). |
| 100 | /// |
| 101 | /// This returns true if an interval was modified. |
| 102 | /// |
Bill Wendling | 2674d71 | 2008-01-04 08:59:18 +0000 | [diff] [blame] | 103 | bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA, |
| 104 | LiveInterval &IntB, |
| 105 | MachineInstr *CopyMI) { |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 106 | MachineInstrIndex CopyIdx = li_->getDefIndex(li_->getInstructionIndex(CopyMI)); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 107 | |
| 108 | // BValNo is a value number in B that is defined by a copy from A. 'B3' in |
| 109 | // the example above. |
| 110 | LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx); |
Dan Gohman | fd246e5 | 2009-01-13 20:25:24 +0000 | [diff] [blame] | 111 | assert(BLR != IntB.end() && "Live range not found!"); |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 112 | VNInfo *BValNo = BLR->valno; |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 113 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 114 | // Get the location that B is defined at. Two options: either this value has |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 115 | // an unknown definition point or it is defined at CopyIdx. If unknown, we |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 116 | // can't process it. |
Lang Hames | 52c1afc | 2009-08-10 23:43:28 +0000 | [diff] [blame] | 117 | if (!BValNo->getCopy()) return false; |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 118 | assert(BValNo->def == CopyIdx && "Copy doesn't define the value?"); |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 119 | |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 120 | // AValNo is the value number in A that defines the copy, A3 in the example. |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 121 | MachineInstrIndex CopyUseIdx = li_->getUseIndex(CopyIdx); |
Evan Cheng | eed0ff1 | 2009-08-03 08:41:59 +0000 | [diff] [blame] | 122 | LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyUseIdx); |
Dan Gohman | fd246e5 | 2009-01-13 20:25:24 +0000 | [diff] [blame] | 123 | assert(ALR != IntA.end() && "Live range not found!"); |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 124 | VNInfo *AValNo = ALR->valno; |
Evan Cheng | 5379f41 | 2008-12-19 20:58:01 +0000 | [diff] [blame] | 125 | // If it's re-defined by an early clobber somewhere in the live range, then |
| 126 | // it's not safe to eliminate the copy. FIXME: This is a temporary workaround. |
| 127 | // See PR3149: |
| 128 | // 172 %ECX<def> = MOV32rr %reg1039<kill> |
| 129 | // 180 INLINEASM <es:subl $5,$1 |
| 130 | // sbbl $3,$0>, 10, %EAX<def>, 14, %ECX<earlyclobber,def>, 9, %EAX<kill>, |
| 131 | // 36, <fi#0>, 1, %reg0, 0, 9, %ECX<kill>, 36, <fi#1>, 1, %reg0, 0 |
| 132 | // 188 %EAX<def> = MOV32rr %EAX<kill> |
| 133 | // 196 %ECX<def> = MOV32rr %ECX<kill> |
| 134 | // 204 %ECX<def> = MOV32rr %ECX<kill> |
| 135 | // 212 %EAX<def> = MOV32rr %EAX<kill> |
| 136 | // 220 %EAX<def> = MOV32rr %EAX |
| 137 | // 228 %reg1039<def> = MOV32rr %ECX<kill> |
| 138 | // The early clobber operand ties ECX input to the ECX def. |
| 139 | // |
| 140 | // The live interval of ECX is represented as this: |
| 141 | // %reg20,inf = [46,47:1)[174,230:0) 0@174-(230) 1@46-(47) |
| 142 | // The coalescer has no idea there was a def in the middle of [174,230]. |
Lang Hames | 857c4e0 | 2009-06-17 21:01:20 +0000 | [diff] [blame] | 143 | if (AValNo->hasRedefByEC()) |
Evan Cheng | 5379f41 | 2008-12-19 20:58:01 +0000 | [diff] [blame] | 144 | return false; |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 145 | |
| 146 | // If AValNo is defined as a copy from IntB, we can potentially process this. |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 147 | // Get the instruction that defines this value number. |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 148 | unsigned SrcReg = li_->getVNInfoSourceReg(AValNo); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 149 | if (!SrcReg) return false; // Not defined by a copy. |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 150 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 151 | // If the value number is not defined by a copy instruction, ignore it. |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 152 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 153 | // If the source register comes from an interval other than IntB, we can't |
| 154 | // handle this. |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 155 | if (SrcReg != IntB.reg) return false; |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 156 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 157 | // Get the LiveRange in IntB that this value number starts with. |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 158 | LiveInterval::iterator ValLR = |
| 159 | IntB.FindLiveRangeContaining(li_->getPrevSlot(AValNo->def)); |
Dan Gohman | fd246e5 | 2009-01-13 20:25:24 +0000 | [diff] [blame] | 160 | assert(ValLR != IntB.end() && "Live range not found!"); |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 161 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 162 | // Make sure that the end of the live range is inside the same block as |
| 163 | // CopyMI. |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 164 | MachineInstr *ValLREndInst = |
| 165 | li_->getInstructionFromIndex(li_->getPrevSlot(ValLR->end)); |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 166 | if (!ValLREndInst || |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 167 | ValLREndInst->getParent() != CopyMI->getParent()) return false; |
| 168 | |
| 169 | // Okay, we now know that ValLR ends in the same block that the CopyMI |
| 170 | // live-range starts. If there are no intervening live ranges between them in |
| 171 | // IntB, we can merge them. |
| 172 | if (ValLR+1 != BLR) return false; |
Evan Cheng | dc5294f | 2007-08-14 23:19:28 +0000 | [diff] [blame] | 173 | |
| 174 | // If a live interval is a physical register, conservatively check if any |
| 175 | // of its sub-registers is overlapping the live interval of the virtual |
| 176 | // register. If so, do not coalesce. |
Dan Gohman | 6f0d024 | 2008-02-10 18:45:23 +0000 | [diff] [blame] | 177 | if (TargetRegisterInfo::isPhysicalRegister(IntB.reg) && |
| 178 | *tri_->getSubRegisters(IntB.reg)) { |
| 179 | for (const unsigned* SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR) |
Evan Cheng | dc5294f | 2007-08-14 23:19:28 +0000 | [diff] [blame] | 180 | if (li_->hasInterval(*SR) && IntA.overlaps(li_->getInterval(*SR))) { |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 181 | DEBUG({ |
| 182 | errs() << "Interfere with sub-register "; |
| 183 | li_->getInterval(*SR).print(errs(), tri_); |
| 184 | }); |
Evan Cheng | dc5294f | 2007-08-14 23:19:28 +0000 | [diff] [blame] | 185 | return false; |
| 186 | } |
| 187 | } |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 188 | |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 189 | DEBUG({ |
| 190 | errs() << "\nExtending: "; |
| 191 | IntB.print(errs(), tri_); |
| 192 | }); |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 193 | |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 194 | MachineInstrIndex FillerStart = ValLR->end, FillerEnd = BLR->start; |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 195 | // We are about to delete CopyMI, so need to remove it as the 'instruction |
Evan Cheng | a8d94f1 | 2007-08-07 23:49:57 +0000 | [diff] [blame] | 196 | // that defines this value #'. Update the the valnum with the new defining |
| 197 | // instruction #. |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 198 | BValNo->def = FillerStart; |
Lang Hames | 52c1afc | 2009-08-10 23:43:28 +0000 | [diff] [blame] | 199 | BValNo->setCopy(0); |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 200 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 201 | // Okay, we can merge them. We need to insert a new liverange: |
| 202 | // [ValLR.end, BLR.begin) of either value number, then we merge the |
| 203 | // two value numbers. |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 204 | IntB.addRange(LiveRange(FillerStart, FillerEnd, BValNo)); |
| 205 | |
| 206 | // If the IntB live range is assigned to a physical register, and if that |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 207 | // physreg has sub-registers, update their live intervals as well. |
Dan Gohman | 6f0d024 | 2008-02-10 18:45:23 +0000 | [diff] [blame] | 208 | if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) { |
Evan Cheng | a2e6435 | 2009-03-11 00:03:21 +0000 | [diff] [blame] | 209 | for (const unsigned *SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR) { |
| 210 | LiveInterval &SRLI = li_->getInterval(*SR); |
| 211 | SRLI.addRange(LiveRange(FillerStart, FillerEnd, |
Lang Hames | 857c4e0 | 2009-06-17 21:01:20 +0000 | [diff] [blame] | 212 | SRLI.getNextValue(FillerStart, 0, true, |
| 213 | li_->getVNInfoAllocator()))); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 214 | } |
| 215 | } |
| 216 | |
| 217 | // Okay, merge "B1" into the same value number as "B0". |
Evan Cheng | 25f34a3 | 2008-09-15 06:28:41 +0000 | [diff] [blame] | 218 | if (BValNo != ValLR->valno) { |
| 219 | IntB.addKills(ValLR->valno, BValNo->kills); |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 220 | IntB.MergeValueNumberInto(BValNo, ValLR->valno); |
Evan Cheng | 25f34a3 | 2008-09-15 06:28:41 +0000 | [diff] [blame] | 221 | } |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 222 | DEBUG({ |
| 223 | errs() << " result = "; |
| 224 | IntB.print(errs(), tri_); |
| 225 | errs() << "\n"; |
| 226 | }); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 227 | |
| 228 | // If the source instruction was killing the source register before the |
| 229 | // merge, unset the isKill marker given the live range has been extended. |
| 230 | int UIdx = ValLREndInst->findRegisterUseOperandIdx(IntB.reg, true); |
Evan Cheng | 25f34a3 | 2008-09-15 06:28:41 +0000 | [diff] [blame] | 231 | if (UIdx != -1) { |
Chris Lattner | f738230 | 2007-12-30 21:56:09 +0000 | [diff] [blame] | 232 | ValLREndInst->getOperand(UIdx).setIsKill(false); |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 233 | ValLR->valno->removeKill(FillerStart); |
Evan Cheng | 25f34a3 | 2008-09-15 06:28:41 +0000 | [diff] [blame] | 234 | } |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 235 | |
Evan Cheng | eed0ff1 | 2009-08-03 08:41:59 +0000 | [diff] [blame] | 236 | // If the copy instruction was killing the destination register before the |
| 237 | // merge, find the last use and trim the live range. That will also add the |
| 238 | // isKill marker. |
| 239 | if (CopyMI->killsRegister(IntA.reg)) |
| 240 | TrimLiveIntervalToLastUse(CopyUseIdx, CopyMI->getParent(), IntA, ALR); |
| 241 | |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 242 | ++numExtends; |
| 243 | return true; |
| 244 | } |
| 245 | |
Evan Cheng | 559f422 | 2008-02-16 02:32:17 +0000 | [diff] [blame] | 246 | /// HasOtherReachingDefs - Return true if there are definitions of IntB |
| 247 | /// other than BValNo val# that can reach uses of AValno val# of IntA. |
| 248 | bool SimpleRegisterCoalescing::HasOtherReachingDefs(LiveInterval &IntA, |
| 249 | LiveInterval &IntB, |
| 250 | VNInfo *AValNo, |
| 251 | VNInfo *BValNo) { |
| 252 | for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); |
| 253 | AI != AE; ++AI) { |
| 254 | if (AI->valno != AValNo) continue; |
| 255 | LiveInterval::Ranges::iterator BI = |
| 256 | std::upper_bound(IntB.ranges.begin(), IntB.ranges.end(), AI->start); |
| 257 | if (BI != IntB.ranges.begin()) |
| 258 | --BI; |
| 259 | for (; BI != IntB.ranges.end() && AI->end >= BI->start; ++BI) { |
| 260 | if (BI->valno == BValNo) |
| 261 | continue; |
| 262 | if (BI->start <= AI->start && BI->end > AI->start) |
| 263 | return true; |
| 264 | if (BI->start > AI->start && BI->start < AI->end) |
| 265 | return true; |
| 266 | } |
| 267 | } |
| 268 | return false; |
| 269 | } |
| 270 | |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 271 | /// RemoveCopyByCommutingDef - We found a non-trivially-coalescable copy with IntA |
| 272 | /// being the source and IntB being the dest, thus this defines a value number |
| 273 | /// in IntB. If the source value number (in IntA) is defined by a commutable |
| 274 | /// instruction and its other operand is coalesced to the copy dest register, |
| 275 | /// see if we can transform the copy into a noop by commuting the definition. For |
| 276 | /// example, |
| 277 | /// |
| 278 | /// A3 = op A2 B0<kill> |
| 279 | /// ... |
| 280 | /// B1 = A3 <- this copy |
| 281 | /// ... |
| 282 | /// = op A3 <- more uses |
| 283 | /// |
| 284 | /// ==> |
| 285 | /// |
| 286 | /// B2 = op B0 A2<kill> |
| 287 | /// ... |
| 288 | /// B1 = B2 <- now an identify copy |
| 289 | /// ... |
| 290 | /// = op B2 <- more uses |
| 291 | /// |
| 292 | /// This returns true if an interval was modified. |
| 293 | /// |
| 294 | bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA, |
| 295 | LiveInterval &IntB, |
| 296 | MachineInstr *CopyMI) { |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 297 | MachineInstrIndex CopyIdx = |
| 298 | li_->getDefIndex(li_->getInstructionIndex(CopyMI)); |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 299 | |
Evan Cheng | a9407f5 | 2008-02-18 18:56:31 +0000 | [diff] [blame] | 300 | // FIXME: For now, only eliminate the copy by commuting its def when the |
| 301 | // source register is a virtual register. We want to guard against cases |
| 302 | // where the copy is a back edge copy and commuting the def lengthen the |
| 303 | // live interval of the source register to the entire loop. |
| 304 | if (TargetRegisterInfo::isPhysicalRegister(IntA.reg)) |
Evan Cheng | 96cfff0 | 2008-02-18 08:40:53 +0000 | [diff] [blame] | 305 | return false; |
| 306 | |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 307 | // BValNo is a value number in B that is defined by a copy from A. 'B3' in |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 308 | // the example above. |
| 309 | LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx); |
Dan Gohman | fd246e5 | 2009-01-13 20:25:24 +0000 | [diff] [blame] | 310 | assert(BLR != IntB.end() && "Live range not found!"); |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 311 | VNInfo *BValNo = BLR->valno; |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 312 | |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 313 | // Get the location that B is defined at. Two options: either this value has |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 314 | // an unknown definition point or it is defined at CopyIdx. If unknown, we |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 315 | // can't process it. |
Lang Hames | 52c1afc | 2009-08-10 23:43:28 +0000 | [diff] [blame] | 316 | if (!BValNo->getCopy()) return false; |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 317 | assert(BValNo->def == CopyIdx && "Copy doesn't define the value?"); |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 318 | |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 319 | // AValNo is the value number in A that defines the copy, A3 in the example. |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 320 | LiveInterval::iterator ALR = |
| 321 | IntA.FindLiveRangeContaining(li_->getPrevSlot(CopyIdx)); |
| 322 | |
Dan Gohman | fd246e5 | 2009-01-13 20:25:24 +0000 | [diff] [blame] | 323 | assert(ALR != IntA.end() && "Live range not found!"); |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 324 | VNInfo *AValNo = ALR->valno; |
Evan Cheng | e35a6d1 | 2008-02-13 08:41:08 +0000 | [diff] [blame] | 325 | // If other defs can reach uses of this def, then it's not safe to perform |
Lang Hames | 857c4e0 | 2009-06-17 21:01:20 +0000 | [diff] [blame] | 326 | // the optimization. FIXME: Do isPHIDef and isDefAccurate both need to be |
| 327 | // tested? |
| 328 | if (AValNo->isPHIDef() || !AValNo->isDefAccurate() || |
| 329 | AValNo->isUnused() || AValNo->hasPHIKill()) |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 330 | return false; |
| 331 | MachineInstr *DefMI = li_->getInstructionFromIndex(AValNo->def); |
| 332 | const TargetInstrDesc &TID = DefMI->getDesc(); |
Evan Cheng | 261ce1d | 2009-07-10 19:15:51 +0000 | [diff] [blame] | 333 | if (!TID.isCommutable()) |
| 334 | return false; |
| 335 | // If DefMI is a two-address instruction then commuting it will change the |
| 336 | // destination register. |
| 337 | int DefIdx = DefMI->findRegisterDefOperandIdx(IntA.reg); |
| 338 | assert(DefIdx != -1); |
| 339 | unsigned UseOpIdx; |
| 340 | if (!DefMI->isRegTiedToUseOperand(DefIdx, &UseOpIdx)) |
| 341 | return false; |
| 342 | unsigned Op1, Op2, NewDstIdx; |
| 343 | if (!tii_->findCommutedOpIndices(DefMI, Op1, Op2)) |
| 344 | return false; |
| 345 | if (Op1 == UseOpIdx) |
| 346 | NewDstIdx = Op2; |
| 347 | else if (Op2 == UseOpIdx) |
| 348 | NewDstIdx = Op1; |
| 349 | else |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 350 | return false; |
| 351 | |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 352 | MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx); |
| 353 | unsigned NewReg = NewDstMO.getReg(); |
| 354 | if (NewReg != IntB.reg || !NewDstMO.isKill()) |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 355 | return false; |
| 356 | |
| 357 | // Make sure there are no other definitions of IntB that would reach the |
| 358 | // uses which the new definition can reach. |
Evan Cheng | 559f422 | 2008-02-16 02:32:17 +0000 | [diff] [blame] | 359 | if (HasOtherReachingDefs(IntA, IntB, AValNo, BValNo)) |
| 360 | return false; |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 361 | |
Evan Cheng | ed70cbb3 | 2008-03-26 19:03:01 +0000 | [diff] [blame] | 362 | // If some of the uses of IntA.reg is already coalesced away, return false. |
| 363 | // It's not possible to determine whether it's safe to perform the coalescing. |
| 364 | for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(IntA.reg), |
| 365 | UE = mri_->use_end(); UI != UE; ++UI) { |
| 366 | MachineInstr *UseMI = &*UI; |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 367 | MachineInstrIndex UseIdx = li_->getInstructionIndex(UseMI); |
Evan Cheng | ed70cbb3 | 2008-03-26 19:03:01 +0000 | [diff] [blame] | 368 | LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx); |
Evan Cheng | ff7a3e5 | 2008-04-16 18:48:43 +0000 | [diff] [blame] | 369 | if (ULR == IntA.end()) |
| 370 | continue; |
Evan Cheng | ed70cbb3 | 2008-03-26 19:03:01 +0000 | [diff] [blame] | 371 | if (ULR->valno == AValNo && JoinedCopies.count(UseMI)) |
| 372 | return false; |
| 373 | } |
| 374 | |
Evan Cheng | cdbcfcc | 2008-02-13 09:56:03 +0000 | [diff] [blame] | 375 | // At this point we have decided that it is legal to do this |
| 376 | // transformation. Start by commuting the instruction. |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 377 | MachineBasicBlock *MBB = DefMI->getParent(); |
| 378 | MachineInstr *NewMI = tii_->commuteInstruction(DefMI); |
Evan Cheng | 559f422 | 2008-02-16 02:32:17 +0000 | [diff] [blame] | 379 | if (!NewMI) |
| 380 | return false; |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 381 | if (NewMI != DefMI) { |
| 382 | li_->ReplaceMachineInstrInMaps(DefMI, NewMI); |
| 383 | MBB->insert(DefMI, NewMI); |
| 384 | MBB->erase(DefMI); |
| 385 | } |
Evan Cheng | 6130f66 | 2008-03-05 00:59:57 +0000 | [diff] [blame] | 386 | unsigned OpIdx = NewMI->findRegisterUseOperandIdx(IntA.reg, false); |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 387 | NewMI->getOperand(OpIdx).setIsKill(); |
| 388 | |
Lang Hames | 857c4e0 | 2009-06-17 21:01:20 +0000 | [diff] [blame] | 389 | bool BHasPHIKill = BValNo->hasPHIKill(); |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 390 | SmallVector<VNInfo*, 4> BDeadValNos; |
Lang Hames | ffd1326 | 2009-07-09 03:57:02 +0000 | [diff] [blame] | 391 | VNInfo::KillSet BKills; |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 392 | std::map<MachineInstrIndex, MachineInstrIndex> BExtend; |
Evan Cheng | 4ff3f1c | 2008-03-10 08:11:32 +0000 | [diff] [blame] | 393 | |
| 394 | // If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g. |
| 395 | // A = or A, B |
| 396 | // ... |
| 397 | // B = A |
| 398 | // ... |
| 399 | // C = A<kill> |
| 400 | // ... |
| 401 | // = B |
| 402 | // |
| 403 | // then do not add kills of A to the newly created B interval. |
| 404 | bool Extended = BLR->end > ALR->end && ALR->end != ALR->start; |
| 405 | if (Extended) |
| 406 | BExtend[ALR->end] = BLR->end; |
| 407 | |
| 408 | // Update uses of IntA of the specific Val# with IntB. |
Evan Cheng | a2e6435 | 2009-03-11 00:03:21 +0000 | [diff] [blame] | 409 | bool BHasSubRegs = false; |
| 410 | if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) |
| 411 | BHasSubRegs = *tri_->getSubRegisters(IntB.reg); |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 412 | for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(IntA.reg), |
| 413 | UE = mri_->use_end(); UI != UE;) { |
| 414 | MachineOperand &UseMO = UI.getOperand(); |
Evan Cheng | cdbcfcc | 2008-02-13 09:56:03 +0000 | [diff] [blame] | 415 | MachineInstr *UseMI = &*UI; |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 416 | ++UI; |
Evan Cheng | cdbcfcc | 2008-02-13 09:56:03 +0000 | [diff] [blame] | 417 | if (JoinedCopies.count(UseMI)) |
Evan Cheng | ed70cbb3 | 2008-03-26 19:03:01 +0000 | [diff] [blame] | 418 | continue; |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 419 | MachineInstrIndex UseIdx = li_->getInstructionIndex(UseMI); |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 420 | LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx); |
Evan Cheng | ff7a3e5 | 2008-04-16 18:48:43 +0000 | [diff] [blame] | 421 | if (ULR == IntA.end() || ULR->valno != AValNo) |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 422 | continue; |
| 423 | UseMO.setReg(NewReg); |
Evan Cheng | cdbcfcc | 2008-02-13 09:56:03 +0000 | [diff] [blame] | 424 | if (UseMI == CopyMI) |
| 425 | continue; |
Evan Cheng | 4ff3f1c | 2008-03-10 08:11:32 +0000 | [diff] [blame] | 426 | if (UseMO.isKill()) { |
| 427 | if (Extended) |
| 428 | UseMO.setIsKill(false); |
| 429 | else |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 430 | BKills.push_back(li_->getNextSlot(li_->getUseIndex(UseIdx))); |
Evan Cheng | 4ff3f1c | 2008-03-10 08:11:32 +0000 | [diff] [blame] | 431 | } |
Evan Cheng | 04ee5a1 | 2009-01-20 19:12:24 +0000 | [diff] [blame] | 432 | unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; |
| 433 | if (!tii_->isMoveInstr(*UseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)) |
Evan Cheng | cdbcfcc | 2008-02-13 09:56:03 +0000 | [diff] [blame] | 434 | continue; |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 435 | if (DstReg == IntB.reg) { |
Evan Cheng | cdbcfcc | 2008-02-13 09:56:03 +0000 | [diff] [blame] | 436 | // This copy will become a noop. If it's defining a new val#, |
| 437 | // remove that val# as well. However this live range is being |
| 438 | // extended to the end of the existing live range defined by the copy. |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 439 | MachineInstrIndex DefIdx = li_->getDefIndex(UseIdx); |
Evan Cheng | ff7a3e5 | 2008-04-16 18:48:43 +0000 | [diff] [blame] | 440 | const LiveRange *DLR = IntB.getLiveRangeContaining(DefIdx); |
Lang Hames | 857c4e0 | 2009-06-17 21:01:20 +0000 | [diff] [blame] | 441 | BHasPHIKill |= DLR->valno->hasPHIKill(); |
Evan Cheng | cdbcfcc | 2008-02-13 09:56:03 +0000 | [diff] [blame] | 442 | assert(DLR->valno->def == DefIdx); |
| 443 | BDeadValNos.push_back(DLR->valno); |
| 444 | BExtend[DLR->start] = DLR->end; |
| 445 | JoinedCopies.insert(UseMI); |
| 446 | // If this is a kill but it's going to be removed, the last use |
| 447 | // of the same val# is the new kill. |
Evan Cheng | 4ff3f1c | 2008-03-10 08:11:32 +0000 | [diff] [blame] | 448 | if (UseMO.isKill()) |
Evan Cheng | cdbcfcc | 2008-02-13 09:56:03 +0000 | [diff] [blame] | 449 | BKills.pop_back(); |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 450 | } |
| 451 | } |
| 452 | |
| 453 | // We need to insert a new liverange: [ALR.start, LastUse). It may be we can |
| 454 | // simply extend BLR if CopyMI doesn't end the range. |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 455 | DEBUG({ |
| 456 | errs() << "\nExtending: "; |
| 457 | IntB.print(errs(), tri_); |
| 458 | }); |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 459 | |
Evan Cheng | 739583b | 2008-06-17 20:11:16 +0000 | [diff] [blame] | 460 | // Remove val#'s defined by copies that will be coalesced away. |
Evan Cheng | a597a97 | 2009-03-11 22:18:44 +0000 | [diff] [blame] | 461 | for (unsigned i = 0, e = BDeadValNos.size(); i != e; ++i) { |
| 462 | VNInfo *DeadVNI = BDeadValNos[i]; |
| 463 | if (BHasSubRegs) { |
| 464 | for (const unsigned *SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR) { |
| 465 | LiveInterval &SRLI = li_->getInterval(*SR); |
| 466 | const LiveRange *SRLR = SRLI.getLiveRangeContaining(DeadVNI->def); |
| 467 | SRLI.removeValNo(SRLR->valno); |
| 468 | } |
| 469 | } |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 470 | IntB.removeValNo(BDeadValNos[i]); |
Evan Cheng | a597a97 | 2009-03-11 22:18:44 +0000 | [diff] [blame] | 471 | } |
Evan Cheng | 739583b | 2008-06-17 20:11:16 +0000 | [diff] [blame] | 472 | |
| 473 | // Extend BValNo by merging in IntA live ranges of AValNo. Val# definition |
| 474 | // is updated. Kills are also updated. |
| 475 | VNInfo *ValNo = BValNo; |
| 476 | ValNo->def = AValNo->def; |
Lang Hames | 52c1afc | 2009-08-10 23:43:28 +0000 | [diff] [blame] | 477 | ValNo->setCopy(0); |
Evan Cheng | 739583b | 2008-06-17 20:11:16 +0000 | [diff] [blame] | 478 | for (unsigned j = 0, ee = ValNo->kills.size(); j != ee; ++j) { |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 479 | if (ValNo->kills[j] != BLR->end) |
| 480 | BKills.push_back(ValNo->kills[j]); |
Evan Cheng | 739583b | 2008-06-17 20:11:16 +0000 | [diff] [blame] | 481 | } |
| 482 | ValNo->kills.clear(); |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 483 | for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); |
| 484 | AI != AE; ++AI) { |
| 485 | if (AI->valno != AValNo) continue; |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 486 | MachineInstrIndex End = AI->end; |
| 487 | std::map<MachineInstrIndex, MachineInstrIndex>::iterator |
| 488 | EI = BExtend.find(End); |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 489 | if (EI != BExtend.end()) |
| 490 | End = EI->second; |
| 491 | IntB.addRange(LiveRange(AI->start, End, ValNo)); |
Evan Cheng | a2e6435 | 2009-03-11 00:03:21 +0000 | [diff] [blame] | 492 | |
| 493 | // If the IntB live range is assigned to a physical register, and if that |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 494 | // physreg has sub-registers, update their live intervals as well. |
Evan Cheng | a597a97 | 2009-03-11 22:18:44 +0000 | [diff] [blame] | 495 | if (BHasSubRegs) { |
Evan Cheng | a2e6435 | 2009-03-11 00:03:21 +0000 | [diff] [blame] | 496 | for (const unsigned *SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR) { |
| 497 | LiveInterval &SRLI = li_->getInterval(*SR); |
| 498 | SRLI.MergeInClobberRange(AI->start, End, li_->getVNInfoAllocator()); |
| 499 | } |
| 500 | } |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 501 | } |
| 502 | IntB.addKills(ValNo, BKills); |
Lang Hames | 857c4e0 | 2009-06-17 21:01:20 +0000 | [diff] [blame] | 503 | ValNo->setHasPHIKill(BHasPHIKill); |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 504 | |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 505 | DEBUG({ |
| 506 | errs() << " result = "; |
| 507 | IntB.print(errs(), tri_); |
| 508 | errs() << '\n'; |
| 509 | errs() << "\nShortening: "; |
| 510 | IntA.print(errs(), tri_); |
| 511 | }); |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 512 | |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 513 | IntA.removeValNo(AValNo); |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 514 | |
| 515 | DEBUG({ |
| 516 | errs() << " result = "; |
| 517 | IntA.print(errs(), tri_); |
| 518 | errs() << '\n'; |
| 519 | }); |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 520 | |
| 521 | ++numCommutes; |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 522 | return true; |
| 523 | } |
| 524 | |
Evan Cheng | 961154f | 2009-02-05 08:45:04 +0000 | [diff] [blame] | 525 | /// isSameOrFallThroughBB - Return true if MBB == SuccMBB or MBB simply |
| 526 | /// fallthoughs to SuccMBB. |
| 527 | static bool isSameOrFallThroughBB(MachineBasicBlock *MBB, |
| 528 | MachineBasicBlock *SuccMBB, |
| 529 | const TargetInstrInfo *tii_) { |
| 530 | if (MBB == SuccMBB) |
| 531 | return true; |
| 532 | MachineBasicBlock *TBB = 0, *FBB = 0; |
| 533 | SmallVector<MachineOperand, 4> Cond; |
| 534 | return !tii_->AnalyzeBranch(*MBB, TBB, FBB, Cond) && !TBB && !FBB && |
| 535 | MBB->isSuccessor(SuccMBB); |
| 536 | } |
| 537 | |
| 538 | /// removeRange - Wrapper for LiveInterval::removeRange. This removes a range |
| 539 | /// from a physical register live interval as well as from the live intervals |
| 540 | /// of its sub-registers. |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 541 | static void removeRange(LiveInterval &li, |
| 542 | MachineInstrIndex Start, MachineInstrIndex End, |
Evan Cheng | 961154f | 2009-02-05 08:45:04 +0000 | [diff] [blame] | 543 | LiveIntervals *li_, const TargetRegisterInfo *tri_) { |
| 544 | li.removeRange(Start, End, true); |
| 545 | if (TargetRegisterInfo::isPhysicalRegister(li.reg)) { |
| 546 | for (const unsigned* SR = tri_->getSubRegisters(li.reg); *SR; ++SR) { |
| 547 | if (!li_->hasInterval(*SR)) |
| 548 | continue; |
| 549 | LiveInterval &sli = li_->getInterval(*SR); |
Evan Cheng | 5cf732e | 2009-09-17 00:57:15 +0000 | [diff] [blame] | 550 | MachineInstrIndex RemoveStart = Start; |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 551 | MachineInstrIndex RemoveEnd = Start; |
Evan Cheng | 961154f | 2009-02-05 08:45:04 +0000 | [diff] [blame] | 552 | while (RemoveEnd != End) { |
Evan Cheng | 5cf732e | 2009-09-17 00:57:15 +0000 | [diff] [blame] | 553 | LiveInterval::iterator LR = sli.FindLiveRangeContaining(RemoveStart); |
Evan Cheng | 961154f | 2009-02-05 08:45:04 +0000 | [diff] [blame] | 554 | if (LR == sli.end()) |
| 555 | break; |
| 556 | RemoveEnd = (LR->end < End) ? LR->end : End; |
Evan Cheng | 5cf732e | 2009-09-17 00:57:15 +0000 | [diff] [blame] | 557 | sli.removeRange(RemoveStart, RemoveEnd, true); |
| 558 | RemoveStart = RemoveEnd; |
Evan Cheng | 961154f | 2009-02-05 08:45:04 +0000 | [diff] [blame] | 559 | } |
| 560 | } |
| 561 | } |
| 562 | } |
| 563 | |
| 564 | /// TrimLiveIntervalToLastUse - If there is a last use in the same basic block |
Evan Cheng | 86fb9fd | 2009-02-08 08:24:28 +0000 | [diff] [blame] | 565 | /// as the copy instruction, trim the live interval to the last use and return |
Evan Cheng | 961154f | 2009-02-05 08:45:04 +0000 | [diff] [blame] | 566 | /// true. |
| 567 | bool |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 568 | SimpleRegisterCoalescing::TrimLiveIntervalToLastUse(MachineInstrIndex CopyIdx, |
Evan Cheng | 961154f | 2009-02-05 08:45:04 +0000 | [diff] [blame] | 569 | MachineBasicBlock *CopyMBB, |
| 570 | LiveInterval &li, |
| 571 | const LiveRange *LR) { |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 572 | MachineInstrIndex MBBStart = li_->getMBBStartIdx(CopyMBB); |
| 573 | MachineInstrIndex LastUseIdx; |
| 574 | MachineOperand *LastUse = |
| 575 | lastRegisterUse(LR->start, li_->getPrevSlot(CopyIdx), li.reg, LastUseIdx); |
Evan Cheng | 961154f | 2009-02-05 08:45:04 +0000 | [diff] [blame] | 576 | if (LastUse) { |
| 577 | MachineInstr *LastUseMI = LastUse->getParent(); |
| 578 | if (!isSameOrFallThroughBB(LastUseMI->getParent(), CopyMBB, tii_)) { |
| 579 | // r1024 = op |
| 580 | // ... |
| 581 | // BB1: |
| 582 | // = r1024 |
| 583 | // |
| 584 | // BB2: |
| 585 | // r1025<dead> = r1024<kill> |
| 586 | if (MBBStart < LR->end) |
| 587 | removeRange(li, MBBStart, LR->end, li_, tri_); |
| 588 | return true; |
| 589 | } |
| 590 | |
| 591 | // There are uses before the copy, just shorten the live range to the end |
| 592 | // of last use. |
| 593 | LastUse->setIsKill(); |
| 594 | removeRange(li, li_->getDefIndex(LastUseIdx), LR->end, li_, tri_); |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 595 | LR->valno->addKill(li_->getNextSlot(LastUseIdx)); |
Evan Cheng | 961154f | 2009-02-05 08:45:04 +0000 | [diff] [blame] | 596 | unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; |
| 597 | if (tii_->isMoveInstr(*LastUseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) && |
| 598 | DstReg == li.reg) { |
| 599 | // Last use is itself an identity code. |
| 600 | int DeadIdx = LastUseMI->findRegisterDefOperandIdx(li.reg, false, tri_); |
| 601 | LastUseMI->getOperand(DeadIdx).setIsDead(); |
| 602 | } |
| 603 | return true; |
| 604 | } |
| 605 | |
| 606 | // Is it livein? |
| 607 | if (LR->start <= MBBStart && LR->end > MBBStart) { |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 608 | if (LR->start == MachineInstrIndex()) { |
Evan Cheng | 961154f | 2009-02-05 08:45:04 +0000 | [diff] [blame] | 609 | assert(TargetRegisterInfo::isPhysicalRegister(li.reg)); |
| 610 | // Live-in to the function but dead. Remove it from entry live-in set. |
| 611 | mf_->begin()->removeLiveIn(li.reg); |
| 612 | } |
| 613 | // FIXME: Shorten intervals in BBs that reaches this BB. |
| 614 | } |
| 615 | |
| 616 | return false; |
| 617 | } |
| 618 | |
Evan Cheng | cd04708 | 2008-08-30 09:09:33 +0000 | [diff] [blame] | 619 | /// ReMaterializeTrivialDef - If the source of a copy is defined by a trivial |
| 620 | /// computation, replace the copy by rematerialize the definition. |
| 621 | bool SimpleRegisterCoalescing::ReMaterializeTrivialDef(LiveInterval &SrcInt, |
| 622 | unsigned DstReg, |
Evan Cheng | 3784453 | 2009-07-16 09:20:10 +0000 | [diff] [blame] | 623 | unsigned DstSubIdx, |
Evan Cheng | cd04708 | 2008-08-30 09:09:33 +0000 | [diff] [blame] | 624 | MachineInstr *CopyMI) { |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 625 | MachineInstrIndex CopyIdx = li_->getUseIndex(li_->getInstructionIndex(CopyMI)); |
Evan Cheng | cd04708 | 2008-08-30 09:09:33 +0000 | [diff] [blame] | 626 | LiveInterval::iterator SrcLR = SrcInt.FindLiveRangeContaining(CopyIdx); |
Dan Gohman | fd246e5 | 2009-01-13 20:25:24 +0000 | [diff] [blame] | 627 | assert(SrcLR != SrcInt.end() && "Live range not found!"); |
Evan Cheng | cd04708 | 2008-08-30 09:09:33 +0000 | [diff] [blame] | 628 | VNInfo *ValNo = SrcLR->valno; |
| 629 | // If other defs can reach uses of this def, then it's not safe to perform |
Lang Hames | 857c4e0 | 2009-06-17 21:01:20 +0000 | [diff] [blame] | 630 | // the optimization. FIXME: Do isPHIDef and isDefAccurate both need to be |
| 631 | // tested? |
| 632 | if (ValNo->isPHIDef() || !ValNo->isDefAccurate() || |
| 633 | ValNo->isUnused() || ValNo->hasPHIKill()) |
Evan Cheng | cd04708 | 2008-08-30 09:09:33 +0000 | [diff] [blame] | 634 | return false; |
| 635 | MachineInstr *DefMI = li_->getInstructionFromIndex(ValNo->def); |
| 636 | const TargetInstrDesc &TID = DefMI->getDesc(); |
| 637 | if (!TID.isAsCheapAsAMove()) |
| 638 | return false; |
Evan Cheng | 54801f78 | 2009-02-05 22:24:17 +0000 | [diff] [blame] | 639 | if (!DefMI->getDesc().isRematerializable() || |
| 640 | !tii_->isTriviallyReMaterializable(DefMI)) |
| 641 | return false; |
Evan Cheng | cd04708 | 2008-08-30 09:09:33 +0000 | [diff] [blame] | 642 | bool SawStore = false; |
| 643 | if (!DefMI->isSafeToMove(tii_, SawStore)) |
| 644 | return false; |
Evan Cheng | 5ad1472 | 2009-07-14 00:51:06 +0000 | [diff] [blame] | 645 | if (TID.getNumDefs() != 1) |
| 646 | return false; |
Evan Cheng | 753480a | 2009-07-20 19:47:55 +0000 | [diff] [blame] | 647 | if (DefMI->getOpcode() != TargetInstrInfo::IMPLICIT_DEF) { |
| 648 | // Make sure the copy destination register class fits the instruction |
| 649 | // definition register class. The mismatch can happen as a result of earlier |
| 650 | // extract_subreg, insert_subreg, subreg_to_reg coalescing. |
Chris Lattner | 2a38688 | 2009-07-29 21:36:49 +0000 | [diff] [blame] | 651 | const TargetRegisterClass *RC = TID.OpInfo[0].getRegClass(tri_); |
Evan Cheng | 753480a | 2009-07-20 19:47:55 +0000 | [diff] [blame] | 652 | if (TargetRegisterInfo::isVirtualRegister(DstReg)) { |
| 653 | if (mri_->getRegClass(DstReg) != RC) |
| 654 | return false; |
| 655 | } else if (!RC->contains(DstReg)) |
Evan Cheng | 5ad1472 | 2009-07-14 00:51:06 +0000 | [diff] [blame] | 656 | return false; |
Evan Cheng | 753480a | 2009-07-20 19:47:55 +0000 | [diff] [blame] | 657 | } |
Evan Cheng | cd04708 | 2008-08-30 09:09:33 +0000 | [diff] [blame] | 658 | |
Evan Cheng | 8bdb0de | 2009-09-08 06:39:07 +0000 | [diff] [blame] | 659 | // If destination register has a sub-register index on it, make sure it mtches |
| 660 | // the instruction register class. |
| 661 | if (DstSubIdx) { |
| 662 | const TargetInstrDesc &TID = DefMI->getDesc(); |
| 663 | if (TID.getNumDefs() != 1) |
| 664 | return false; |
| 665 | const TargetRegisterClass *DstRC = mri_->getRegClass(DstReg); |
| 666 | const TargetRegisterClass *DstSubRC = |
| 667 | DstRC->getSubRegisterRegClass(DstSubIdx); |
| 668 | const TargetRegisterClass *DefRC = TID.OpInfo[0].getRegClass(tri_); |
| 669 | if (DefRC == DstRC) |
| 670 | DstSubIdx = 0; |
| 671 | else if (DefRC != DstSubRC) |
| 672 | return false; |
| 673 | } |
| 674 | |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 675 | MachineInstrIndex DefIdx = li_->getDefIndex(CopyIdx); |
Evan Cheng | cd04708 | 2008-08-30 09:09:33 +0000 | [diff] [blame] | 676 | const LiveRange *DLR= li_->getInterval(DstReg).getLiveRangeContaining(DefIdx); |
Lang Hames | 52c1afc | 2009-08-10 23:43:28 +0000 | [diff] [blame] | 677 | DLR->valno->setCopy(0); |
Evan Cheng | 195cd3a | 2008-10-13 18:35:52 +0000 | [diff] [blame] | 678 | // Don't forget to update sub-register intervals. |
| 679 | if (TargetRegisterInfo::isPhysicalRegister(DstReg)) { |
| 680 | for (const unsigned* SR = tri_->getSubRegisters(DstReg); *SR; ++SR) { |
| 681 | if (!li_->hasInterval(*SR)) |
| 682 | continue; |
| 683 | DLR = li_->getInterval(*SR).getLiveRangeContaining(DefIdx); |
Lang Hames | 52c1afc | 2009-08-10 23:43:28 +0000 | [diff] [blame] | 684 | if (DLR && DLR->valno->getCopy() == CopyMI) |
| 685 | DLR->valno->setCopy(0); |
Evan Cheng | 195cd3a | 2008-10-13 18:35:52 +0000 | [diff] [blame] | 686 | } |
| 687 | } |
Evan Cheng | cd04708 | 2008-08-30 09:09:33 +0000 | [diff] [blame] | 688 | |
Evan Cheng | 961154f | 2009-02-05 08:45:04 +0000 | [diff] [blame] | 689 | // If copy kills the source register, find the last use and propagate |
| 690 | // kill. |
Lang Hames | 9c992f1 | 2009-05-11 23:14:13 +0000 | [diff] [blame] | 691 | bool checkForDeadDef = false; |
Evan Cheng | cd04708 | 2008-08-30 09:09:33 +0000 | [diff] [blame] | 692 | MachineBasicBlock *MBB = CopyMI->getParent(); |
Evan Cheng | 961154f | 2009-02-05 08:45:04 +0000 | [diff] [blame] | 693 | if (CopyMI->killsRegister(SrcInt.reg)) |
Lang Hames | 9c992f1 | 2009-05-11 23:14:13 +0000 | [diff] [blame] | 694 | if (!TrimLiveIntervalToLastUse(CopyIdx, MBB, SrcInt, SrcLR)) { |
| 695 | checkForDeadDef = true; |
| 696 | } |
Evan Cheng | 961154f | 2009-02-05 08:45:04 +0000 | [diff] [blame] | 697 | |
Dan Gohman | 3afda6e | 2008-10-21 03:24:31 +0000 | [diff] [blame] | 698 | MachineBasicBlock::iterator MII = next(MachineBasicBlock::iterator(CopyMI)); |
Evan Cheng | 3784453 | 2009-07-16 09:20:10 +0000 | [diff] [blame] | 699 | tii_->reMaterialize(*MBB, MII, DstReg, DstSubIdx, DefMI); |
Evan Cheng | cd04708 | 2008-08-30 09:09:33 +0000 | [diff] [blame] | 700 | MachineInstr *NewMI = prior(MII); |
Lang Hames | 9c992f1 | 2009-05-11 23:14:13 +0000 | [diff] [blame] | 701 | |
| 702 | if (checkForDeadDef) { |
Evan Cheng | 67fcf56 | 2009-06-16 07:12:58 +0000 | [diff] [blame] | 703 | // PR4090 fix: Trim interval failed because there was no use of the |
| 704 | // source interval in this MBB. If the def is in this MBB too then we |
| 705 | // should mark it dead: |
| 706 | if (DefMI->getParent() == MBB) { |
| 707 | DefMI->addRegisterDead(SrcInt.reg, tri_); |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 708 | SrcLR->end = li_->getNextSlot(SrcLR->start); |
Evan Cheng | 67fcf56 | 2009-06-16 07:12:58 +0000 | [diff] [blame] | 709 | } |
Lang Hames | 9c992f1 | 2009-05-11 23:14:13 +0000 | [diff] [blame] | 710 | } |
| 711 | |
Chris Lattner | 99cbdff | 2008-10-11 23:59:03 +0000 | [diff] [blame] | 712 | // CopyMI may have implicit operands, transfer them over to the newly |
Evan Cheng | cd04708 | 2008-08-30 09:09:33 +0000 | [diff] [blame] | 713 | // rematerialized instruction. And update implicit def interval valnos. |
| 714 | for (unsigned i = CopyMI->getDesc().getNumOperands(), |
| 715 | e = CopyMI->getNumOperands(); i != e; ++i) { |
| 716 | MachineOperand &MO = CopyMI->getOperand(i); |
Dan Gohman | d735b80 | 2008-10-03 15:45:36 +0000 | [diff] [blame] | 717 | if (MO.isReg() && MO.isImplicit()) |
Evan Cheng | cd04708 | 2008-08-30 09:09:33 +0000 | [diff] [blame] | 718 | NewMI->addOperand(MO); |
Owen Anderson | 369e987 | 2008-09-10 20:41:13 +0000 | [diff] [blame] | 719 | if (MO.isDef() && li_->hasInterval(MO.getReg())) { |
Evan Cheng | cd04708 | 2008-08-30 09:09:33 +0000 | [diff] [blame] | 720 | unsigned Reg = MO.getReg(); |
| 721 | DLR = li_->getInterval(Reg).getLiveRangeContaining(DefIdx); |
Lang Hames | 52c1afc | 2009-08-10 23:43:28 +0000 | [diff] [blame] | 722 | if (DLR && DLR->valno->getCopy() == CopyMI) |
| 723 | DLR->valno->setCopy(0); |
Evan Cheng | cd04708 | 2008-08-30 09:09:33 +0000 | [diff] [blame] | 724 | } |
| 725 | } |
| 726 | |
| 727 | li_->ReplaceMachineInstrInMaps(CopyMI, NewMI); |
Evan Cheng | 67fcf56 | 2009-06-16 07:12:58 +0000 | [diff] [blame] | 728 | CopyMI->eraseFromParent(); |
Evan Cheng | cd04708 | 2008-08-30 09:09:33 +0000 | [diff] [blame] | 729 | ReMatCopies.insert(CopyMI); |
Evan Cheng | 20580a1 | 2008-09-19 17:38:47 +0000 | [diff] [blame] | 730 | ReMatDefs.insert(DefMI); |
Evan Cheng | cd04708 | 2008-08-30 09:09:33 +0000 | [diff] [blame] | 731 | ++NumReMats; |
| 732 | return true; |
| 733 | } |
| 734 | |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 735 | /// UpdateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and |
| 736 | /// update the subregister number if it is not zero. If DstReg is a |
| 737 | /// physical register and the existing subregister number of the def / use |
| 738 | /// being updated is not zero, make sure to set it to the correct physical |
| 739 | /// subregister. |
| 740 | void |
| 741 | SimpleRegisterCoalescing::UpdateRegDefsUses(unsigned SrcReg, unsigned DstReg, |
| 742 | unsigned SubIdx) { |
| 743 | bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); |
| 744 | if (DstIsPhys && SubIdx) { |
| 745 | // Figure out the real physical register we are updating with. |
| 746 | DstReg = tri_->getSubReg(DstReg, SubIdx); |
| 747 | SubIdx = 0; |
| 748 | } |
| 749 | |
| 750 | for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(SrcReg), |
| 751 | E = mri_->reg_end(); I != E; ) { |
| 752 | MachineOperand &O = I.getOperand(); |
Evan Cheng | 70366b9 | 2008-03-21 19:09:30 +0000 | [diff] [blame] | 753 | MachineInstr *UseMI = &*I; |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 754 | ++I; |
Evan Cheng | 621d157 | 2008-04-17 00:06:42 +0000 | [diff] [blame] | 755 | unsigned OldSubIdx = O.getSubReg(); |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 756 | if (DstIsPhys) { |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 757 | unsigned UseDstReg = DstReg; |
Evan Cheng | 621d157 | 2008-04-17 00:06:42 +0000 | [diff] [blame] | 758 | if (OldSubIdx) |
| 759 | UseDstReg = tri_->getSubReg(DstReg, OldSubIdx); |
Evan Cheng | cd04708 | 2008-08-30 09:09:33 +0000 | [diff] [blame] | 760 | |
Evan Cheng | 04ee5a1 | 2009-01-20 19:12:24 +0000 | [diff] [blame] | 761 | unsigned CopySrcReg, CopyDstReg, CopySrcSubIdx, CopyDstSubIdx; |
| 762 | if (tii_->isMoveInstr(*UseMI, CopySrcReg, CopyDstReg, |
| 763 | CopySrcSubIdx, CopyDstSubIdx) && |
Evan Cheng | cd04708 | 2008-08-30 09:09:33 +0000 | [diff] [blame] | 764 | CopySrcReg != CopyDstReg && |
| 765 | CopySrcReg == SrcReg && CopyDstReg != UseDstReg) { |
| 766 | // If the use is a copy and it won't be coalesced away, and its source |
| 767 | // is defined by a trivial computation, try to rematerialize it instead. |
Evan Cheng | 3784453 | 2009-07-16 09:20:10 +0000 | [diff] [blame] | 768 | if (ReMaterializeTrivialDef(li_->getInterval(SrcReg), CopyDstReg, |
| 769 | CopyDstSubIdx, UseMI)) |
Evan Cheng | cd04708 | 2008-08-30 09:09:33 +0000 | [diff] [blame] | 770 | continue; |
| 771 | } |
| 772 | |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 773 | O.setReg(UseDstReg); |
| 774 | O.setSubReg(0); |
Evan Cheng | ee9e1b0 | 2008-09-12 18:13:14 +0000 | [diff] [blame] | 775 | continue; |
| 776 | } |
| 777 | |
| 778 | // Sub-register indexes goes from small to large. e.g. |
| 779 | // RAX: 1 -> AL, 2 -> AX, 3 -> EAX |
| 780 | // EAX: 1 -> AL, 2 -> AX |
| 781 | // So RAX's sub-register 2 is AX, RAX's sub-regsiter 3 is EAX, whose |
| 782 | // sub-register 2 is also AX. |
| 783 | if (SubIdx && OldSubIdx && SubIdx != OldSubIdx) |
| 784 | assert(OldSubIdx < SubIdx && "Conflicting sub-register index!"); |
| 785 | else if (SubIdx) |
| 786 | O.setSubReg(SubIdx); |
| 787 | // Remove would-be duplicated kill marker. |
| 788 | if (O.isKill() && UseMI->killsRegister(DstReg)) |
| 789 | O.setIsKill(false); |
| 790 | O.setReg(DstReg); |
| 791 | |
| 792 | // After updating the operand, check if the machine instruction has |
| 793 | // become a copy. If so, update its val# information. |
Evan Cheng | 81909b7 | 2009-06-22 20:49:32 +0000 | [diff] [blame] | 794 | if (JoinedCopies.count(UseMI)) |
| 795 | continue; |
| 796 | |
Evan Cheng | ee9e1b0 | 2008-09-12 18:13:14 +0000 | [diff] [blame] | 797 | const TargetInstrDesc &TID = UseMI->getDesc(); |
Evan Cheng | 04ee5a1 | 2009-01-20 19:12:24 +0000 | [diff] [blame] | 798 | unsigned CopySrcReg, CopyDstReg, CopySrcSubIdx, CopyDstSubIdx; |
Evan Cheng | ee9e1b0 | 2008-09-12 18:13:14 +0000 | [diff] [blame] | 799 | if (TID.getNumDefs() == 1 && TID.getNumOperands() > 2 && |
Evan Cheng | 04ee5a1 | 2009-01-20 19:12:24 +0000 | [diff] [blame] | 800 | tii_->isMoveInstr(*UseMI, CopySrcReg, CopyDstReg, |
| 801 | CopySrcSubIdx, CopyDstSubIdx) && |
Evan Cheng | 870e4be | 2008-09-17 18:36:25 +0000 | [diff] [blame] | 802 | CopySrcReg != CopyDstReg && |
| 803 | (TargetRegisterInfo::isVirtualRegister(CopyDstReg) || |
| 804 | allocatableRegs_[CopyDstReg])) { |
Evan Cheng | ee9e1b0 | 2008-09-12 18:13:14 +0000 | [diff] [blame] | 805 | LiveInterval &LI = li_->getInterval(CopyDstReg); |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 806 | MachineInstrIndex DefIdx = |
| 807 | li_->getDefIndex(li_->getInstructionIndex(UseMI)); |
Evan Cheng | 81909b7 | 2009-06-22 20:49:32 +0000 | [diff] [blame] | 808 | if (const LiveRange *DLR = LI.getLiveRangeContaining(DefIdx)) { |
| 809 | if (DLR->valno->def == DefIdx) |
Lang Hames | 52c1afc | 2009-08-10 23:43:28 +0000 | [diff] [blame] | 810 | DLR->valno->setCopy(UseMI); |
Evan Cheng | 81909b7 | 2009-06-22 20:49:32 +0000 | [diff] [blame] | 811 | } |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 812 | } |
| 813 | } |
| 814 | } |
| 815 | |
Evan Cheng | 4ff3f1c | 2008-03-10 08:11:32 +0000 | [diff] [blame] | 816 | /// RemoveUnnecessaryKills - Remove kill markers that are no longer accurate |
| 817 | /// due to live range lengthening as the result of coalescing. |
| 818 | void SimpleRegisterCoalescing::RemoveUnnecessaryKills(unsigned Reg, |
| 819 | LiveInterval &LI) { |
| 820 | for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(Reg), |
| 821 | UE = mri_->use_end(); UI != UE; ++UI) { |
| 822 | MachineOperand &UseMO = UI.getOperand(); |
Evan Cheng | 9cd1632 | 2009-08-05 07:05:41 +0000 | [diff] [blame] | 823 | if (!UseMO.isKill()) |
| 824 | continue; |
| 825 | MachineInstr *UseMI = UseMO.getParent(); |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 826 | MachineInstrIndex UseIdx = |
| 827 | li_->getUseIndex(li_->getInstructionIndex(UseMI)); |
Benjamin Kramer | 0ffc470 | 2009-08-05 16:08:58 +0000 | [diff] [blame] | 828 | const LiveRange *LR = LI.getLiveRangeContaining(UseIdx); |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 829 | if (!LR || !LR->valno->isKill(li_->getNextSlot(UseIdx))) { |
| 830 | if (LR->valno->def != li_->getNextSlot(UseIdx)) { |
Evan Cheng | 9cd1632 | 2009-08-05 07:05:41 +0000 | [diff] [blame] | 831 | // Interesting problem. After coalescing reg1027's def and kill are both |
| 832 | // at the same point: %reg1027,0.000000e+00 = [56,814:0) 0@70-(814) |
| 833 | // |
| 834 | // bb5: |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 835 | // 60 %reg1027<def> = t2MOVr %reg1027, 14, %reg0, %reg0 |
| 836 | // 68 %reg1027<def> = t2LDRi12 %reg1027<kill>, 8, 14, %reg0 |
| 837 | // 76 t2CMPzri %reg1038<kill,undef>, 0, 14, %reg0, %CPSR<imp-def> |
| 838 | // 84 %reg1027<def> = t2MOVr %reg1027, 14, %reg0, %reg0 |
| 839 | // 96 t2Bcc mbb<bb5,0x2030910>, 1, %CPSR<kill> |
Evan Cheng | 9cd1632 | 2009-08-05 07:05:41 +0000 | [diff] [blame] | 840 | // |
| 841 | // Do not remove the kill marker on t2LDRi12. |
Evan Cheng | 4ff3f1c | 2008-03-10 08:11:32 +0000 | [diff] [blame] | 842 | UseMO.setIsKill(false); |
Evan Cheng | 9cd1632 | 2009-08-05 07:05:41 +0000 | [diff] [blame] | 843 | } |
Evan Cheng | 4ff3f1c | 2008-03-10 08:11:32 +0000 | [diff] [blame] | 844 | } |
| 845 | } |
| 846 | } |
| 847 | |
Evan Cheng | 3c88d74 | 2008-03-18 08:26:47 +0000 | [diff] [blame] | 848 | /// removeIntervalIfEmpty - Check if the live interval of a physical register |
| 849 | /// is empty, if so remove it and also remove the empty intervals of its |
Evan Cheng | 9c1e06e | 2008-04-16 20:24:25 +0000 | [diff] [blame] | 850 | /// sub-registers. Return true if live interval is removed. |
| 851 | static bool removeIntervalIfEmpty(LiveInterval &li, LiveIntervals *li_, |
Evan Cheng | 3c88d74 | 2008-03-18 08:26:47 +0000 | [diff] [blame] | 852 | const TargetRegisterInfo *tri_) { |
| 853 | if (li.empty()) { |
Evan Cheng | 3c88d74 | 2008-03-18 08:26:47 +0000 | [diff] [blame] | 854 | if (TargetRegisterInfo::isPhysicalRegister(li.reg)) |
| 855 | for (const unsigned* SR = tri_->getSubRegisters(li.reg); *SR; ++SR) { |
| 856 | if (!li_->hasInterval(*SR)) |
| 857 | continue; |
| 858 | LiveInterval &sli = li_->getInterval(*SR); |
| 859 | if (sli.empty()) |
| 860 | li_->removeInterval(*SR); |
| 861 | } |
Evan Cheng | d94950c | 2008-04-16 01:22:28 +0000 | [diff] [blame] | 862 | li_->removeInterval(li.reg); |
Evan Cheng | 9c1e06e | 2008-04-16 20:24:25 +0000 | [diff] [blame] | 863 | return true; |
Evan Cheng | 3c88d74 | 2008-03-18 08:26:47 +0000 | [diff] [blame] | 864 | } |
Evan Cheng | 9c1e06e | 2008-04-16 20:24:25 +0000 | [diff] [blame] | 865 | return false; |
Evan Cheng | 3c88d74 | 2008-03-18 08:26:47 +0000 | [diff] [blame] | 866 | } |
| 867 | |
| 868 | /// ShortenDeadCopyLiveRange - Shorten a live range defined by a dead copy. |
Evan Cheng | 9c1e06e | 2008-04-16 20:24:25 +0000 | [diff] [blame] | 869 | /// Return true if live interval is removed. |
| 870 | bool SimpleRegisterCoalescing::ShortenDeadCopyLiveRange(LiveInterval &li, |
Evan Cheng | ecb2a8b | 2008-03-05 22:09:42 +0000 | [diff] [blame] | 871 | MachineInstr *CopyMI) { |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 872 | MachineInstrIndex CopyIdx = li_->getInstructionIndex(CopyMI); |
Evan Cheng | ecb2a8b | 2008-03-05 22:09:42 +0000 | [diff] [blame] | 873 | LiveInterval::iterator MLR = |
| 874 | li.FindLiveRangeContaining(li_->getDefIndex(CopyIdx)); |
Evan Cheng | 3c88d74 | 2008-03-18 08:26:47 +0000 | [diff] [blame] | 875 | if (MLR == li.end()) |
Evan Cheng | 9c1e06e | 2008-04-16 20:24:25 +0000 | [diff] [blame] | 876 | return false; // Already removed by ShortenDeadCopySrcLiveRange. |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 877 | MachineInstrIndex RemoveStart = MLR->start; |
| 878 | MachineInstrIndex RemoveEnd = MLR->end; |
| 879 | MachineInstrIndex DefIdx = li_->getDefIndex(CopyIdx); |
Evan Cheng | 3c88d74 | 2008-03-18 08:26:47 +0000 | [diff] [blame] | 880 | // Remove the liverange that's defined by this. |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 881 | if (RemoveStart == DefIdx && RemoveEnd == li_->getNextSlot(DefIdx)) { |
Evan Cheng | 3c88d74 | 2008-03-18 08:26:47 +0000 | [diff] [blame] | 882 | removeRange(li, RemoveStart, RemoveEnd, li_, tri_); |
Evan Cheng | 9c1e06e | 2008-04-16 20:24:25 +0000 | [diff] [blame] | 883 | return removeIntervalIfEmpty(li, li_, tri_); |
Evan Cheng | ecb2a8b | 2008-03-05 22:09:42 +0000 | [diff] [blame] | 884 | } |
Evan Cheng | 9c1e06e | 2008-04-16 20:24:25 +0000 | [diff] [blame] | 885 | return false; |
Evan Cheng | 3c88d74 | 2008-03-18 08:26:47 +0000 | [diff] [blame] | 886 | } |
| 887 | |
Evan Cheng | b3990d5 | 2008-10-27 23:21:01 +0000 | [diff] [blame] | 888 | /// RemoveDeadDef - If a def of a live interval is now determined dead, remove |
| 889 | /// the val# it defines. If the live interval becomes empty, remove it as well. |
| 890 | bool SimpleRegisterCoalescing::RemoveDeadDef(LiveInterval &li, |
| 891 | MachineInstr *DefMI) { |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 892 | MachineInstrIndex DefIdx = li_->getDefIndex(li_->getInstructionIndex(DefMI)); |
Evan Cheng | b3990d5 | 2008-10-27 23:21:01 +0000 | [diff] [blame] | 893 | LiveInterval::iterator MLR = li.FindLiveRangeContaining(DefIdx); |
| 894 | if (DefIdx != MLR->valno->def) |
| 895 | return false; |
| 896 | li.removeValNo(MLR->valno); |
| 897 | return removeIntervalIfEmpty(li, li_, tri_); |
| 898 | } |
| 899 | |
Evan Cheng | 0c28432 | 2008-03-26 20:15:49 +0000 | [diff] [blame] | 900 | /// PropagateDeadness - Propagate the dead marker to the instruction which |
| 901 | /// defines the val#. |
| 902 | static void PropagateDeadness(LiveInterval &li, MachineInstr *CopyMI, |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 903 | MachineInstrIndex &LRStart, LiveIntervals *li_, |
Evan Cheng | 0c28432 | 2008-03-26 20:15:49 +0000 | [diff] [blame] | 904 | const TargetRegisterInfo* tri_) { |
| 905 | MachineInstr *DefMI = |
| 906 | li_->getInstructionFromIndex(li_->getDefIndex(LRStart)); |
| 907 | if (DefMI && DefMI != CopyMI) { |
Evan Cheng | 15c592d | 2009-08-07 07:14:14 +0000 | [diff] [blame] | 908 | int DeadIdx = DefMI->findRegisterDefOperandIdx(li.reg, false); |
| 909 | if (DeadIdx != -1) |
Evan Cheng | 0c28432 | 2008-03-26 20:15:49 +0000 | [diff] [blame] | 910 | DefMI->getOperand(DeadIdx).setIsDead(); |
Evan Cheng | 15c592d | 2009-08-07 07:14:14 +0000 | [diff] [blame] | 911 | else |
| 912 | DefMI->addOperand(MachineOperand::CreateReg(li.reg, |
| 913 | true, true, false, true)); |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 914 | LRStart = li_->getNextSlot(LRStart); |
Evan Cheng | 0c28432 | 2008-03-26 20:15:49 +0000 | [diff] [blame] | 915 | } |
| 916 | } |
| 917 | |
Bill Wendling | f231778 | 2008-04-17 05:20:39 +0000 | [diff] [blame] | 918 | /// ShortenDeadCopySrcLiveRange - Shorten a live range as it's artificially |
| 919 | /// extended by a dead copy. Mark the last use (if any) of the val# as kill as |
| 920 | /// ends the live range there. If there isn't another use, then this live range |
| 921 | /// is dead. Return true if live interval is removed. |
Evan Cheng | 9c1e06e | 2008-04-16 20:24:25 +0000 | [diff] [blame] | 922 | bool |
Evan Cheng | 3c88d74 | 2008-03-18 08:26:47 +0000 | [diff] [blame] | 923 | SimpleRegisterCoalescing::ShortenDeadCopySrcLiveRange(LiveInterval &li, |
| 924 | MachineInstr *CopyMI) { |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 925 | MachineInstrIndex CopyIdx = li_->getInstructionIndex(CopyMI); |
| 926 | if (CopyIdx == MachineInstrIndex()) { |
Evan Cheng | 3c88d74 | 2008-03-18 08:26:47 +0000 | [diff] [blame] | 927 | // FIXME: special case: function live in. It can be a general case if the |
| 928 | // first instruction index starts at > 0 value. |
| 929 | assert(TargetRegisterInfo::isPhysicalRegister(li.reg)); |
| 930 | // Live-in to the function but dead. Remove it from entry live-in set. |
Evan Cheng | a971dbd | 2008-04-24 09:06:33 +0000 | [diff] [blame] | 931 | if (mf_->begin()->isLiveIn(li.reg)) |
| 932 | mf_->begin()->removeLiveIn(li.reg); |
Evan Cheng | ff7a3e5 | 2008-04-16 18:48:43 +0000 | [diff] [blame] | 933 | const LiveRange *LR = li.getLiveRangeContaining(CopyIdx); |
Evan Cheng | 3c88d74 | 2008-03-18 08:26:47 +0000 | [diff] [blame] | 934 | removeRange(li, LR->start, LR->end, li_, tri_); |
Evan Cheng | 9c1e06e | 2008-04-16 20:24:25 +0000 | [diff] [blame] | 935 | return removeIntervalIfEmpty(li, li_, tri_); |
Evan Cheng | 3c88d74 | 2008-03-18 08:26:47 +0000 | [diff] [blame] | 936 | } |
| 937 | |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 938 | LiveInterval::iterator LR = |
| 939 | li.FindLiveRangeContaining(li_->getPrevSlot(CopyIdx)); |
Evan Cheng | 3c88d74 | 2008-03-18 08:26:47 +0000 | [diff] [blame] | 940 | if (LR == li.end()) |
| 941 | // Livein but defined by a phi. |
Evan Cheng | 9c1e06e | 2008-04-16 20:24:25 +0000 | [diff] [blame] | 942 | return false; |
Evan Cheng | 3c88d74 | 2008-03-18 08:26:47 +0000 | [diff] [blame] | 943 | |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 944 | MachineInstrIndex RemoveStart = LR->start; |
| 945 | MachineInstrIndex RemoveEnd = li_->getNextSlot(li_->getDefIndex(CopyIdx)); |
Evan Cheng | 3c88d74 | 2008-03-18 08:26:47 +0000 | [diff] [blame] | 946 | if (LR->end > RemoveEnd) |
| 947 | // More uses past this copy? Nothing to do. |
Evan Cheng | 9c1e06e | 2008-04-16 20:24:25 +0000 | [diff] [blame] | 948 | return false; |
Evan Cheng | 3c88d74 | 2008-03-18 08:26:47 +0000 | [diff] [blame] | 949 | |
Evan Cheng | 961154f | 2009-02-05 08:45:04 +0000 | [diff] [blame] | 950 | // If there is a last use in the same bb, we can't remove the live range. |
| 951 | // Shorten the live interval and return. |
Evan Cheng | 190424e | 2009-02-09 08:37:45 +0000 | [diff] [blame] | 952 | MachineBasicBlock *CopyMBB = CopyMI->getParent(); |
| 953 | if (TrimLiveIntervalToLastUse(CopyIdx, CopyMBB, li, LR)) |
Evan Cheng | 9c1e06e | 2008-04-16 20:24:25 +0000 | [diff] [blame] | 954 | return false; |
Evan Cheng | 3c88d74 | 2008-03-18 08:26:47 +0000 | [diff] [blame] | 955 | |
Evan Cheng | a499eff | 2009-07-15 21:39:50 +0000 | [diff] [blame] | 956 | // There are other kills of the val#. Nothing to do. |
| 957 | if (!li.isOnlyLROfValNo(LR)) |
| 958 | return false; |
| 959 | |
Evan Cheng | 190424e | 2009-02-09 08:37:45 +0000 | [diff] [blame] | 960 | MachineBasicBlock *StartMBB = li_->getMBBFromIndex(RemoveStart); |
| 961 | if (!isSameOrFallThroughBB(StartMBB, CopyMBB, tii_)) |
| 962 | // If the live range starts in another mbb and the copy mbb is not a fall |
| 963 | // through mbb, then we can only cut the range from the beginning of the |
| 964 | // copy mbb. |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 965 | RemoveStart = li_->getNextSlot(li_->getMBBStartIdx(CopyMBB)); |
Evan Cheng | 190424e | 2009-02-09 08:37:45 +0000 | [diff] [blame] | 966 | |
Evan Cheng | 77fde2c | 2009-02-08 07:48:37 +0000 | [diff] [blame] | 967 | if (LR->valno->def == RemoveStart) { |
| 968 | // If the def MI defines the val# and this copy is the only kill of the |
| 969 | // val#, then propagate the dead marker. |
Evan Cheng | 3784453 | 2009-07-16 09:20:10 +0000 | [diff] [blame] | 970 | PropagateDeadness(li, CopyMI, RemoveStart, li_, tri_); |
| 971 | ++numDeadValNo; |
| 972 | |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 973 | if (LR->valno->isKill(RemoveEnd)) |
| 974 | LR->valno->removeKill(RemoveEnd); |
Evan Cheng | 77fde2c | 2009-02-08 07:48:37 +0000 | [diff] [blame] | 975 | } |
Evan Cheng | 0c28432 | 2008-03-26 20:15:49 +0000 | [diff] [blame] | 976 | |
Evan Cheng | 190424e | 2009-02-09 08:37:45 +0000 | [diff] [blame] | 977 | removeRange(li, RemoveStart, RemoveEnd, li_, tri_); |
Evan Cheng | 9c1e06e | 2008-04-16 20:24:25 +0000 | [diff] [blame] | 978 | return removeIntervalIfEmpty(li, li_, tri_); |
Evan Cheng | ecb2a8b | 2008-03-05 22:09:42 +0000 | [diff] [blame] | 979 | } |
| 980 | |
Evan Cheng | 7e073ba | 2008-04-09 20:57:25 +0000 | [diff] [blame] | 981 | /// CanCoalesceWithImpDef - Returns true if the specified copy instruction |
| 982 | /// from an implicit def to another register can be coalesced away. |
| 983 | bool SimpleRegisterCoalescing::CanCoalesceWithImpDef(MachineInstr *CopyMI, |
| 984 | LiveInterval &li, |
| 985 | LiveInterval &ImpLi) const{ |
| 986 | if (!CopyMI->killsRegister(ImpLi.reg)) |
| 987 | return false; |
Evan Cheng | 0768f0e | 2009-07-17 21:06:58 +0000 | [diff] [blame] | 988 | // Make sure this is the only use. |
| 989 | for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(ImpLi.reg), |
Evan Cheng | 7e073ba | 2008-04-09 20:57:25 +0000 | [diff] [blame] | 990 | UE = mri_->use_end(); UI != UE;) { |
| 991 | MachineInstr *UseMI = &*UI; |
| 992 | ++UI; |
Evan Cheng | 0768f0e | 2009-07-17 21:06:58 +0000 | [diff] [blame] | 993 | if (CopyMI == UseMI || JoinedCopies.count(UseMI)) |
Evan Cheng | 7e073ba | 2008-04-09 20:57:25 +0000 | [diff] [blame] | 994 | continue; |
Evan Cheng | 0768f0e | 2009-07-17 21:06:58 +0000 | [diff] [blame] | 995 | return false; |
Evan Cheng | 7e073ba | 2008-04-09 20:57:25 +0000 | [diff] [blame] | 996 | } |
| 997 | return true; |
| 998 | } |
| 999 | |
| 1000 | |
Evan Cheng | 0490dcb | 2009-04-30 18:39:57 +0000 | [diff] [blame] | 1001 | /// isWinToJoinVRWithSrcPhysReg - Return true if it's worth while to join a |
| 1002 | /// a virtual destination register with physical source register. |
| 1003 | bool |
| 1004 | SimpleRegisterCoalescing::isWinToJoinVRWithSrcPhysReg(MachineInstr *CopyMI, |
| 1005 | MachineBasicBlock *CopyMBB, |
| 1006 | LiveInterval &DstInt, |
| 1007 | LiveInterval &SrcInt) { |
| 1008 | // If the virtual register live interval is long but it has low use desity, |
| 1009 | // do not join them, instead mark the physical register as its allocation |
| 1010 | // preference. |
| 1011 | const TargetRegisterClass *RC = mri_->getRegClass(DstInt.reg); |
| 1012 | unsigned Threshold = allocatableRCRegs_[RC].count() * 2; |
| 1013 | unsigned Length = li_->getApproximateInstructionCount(DstInt); |
| 1014 | if (Length > Threshold && |
| 1015 | (((float)std::distance(mri_->use_begin(DstInt.reg), |
| 1016 | mri_->use_end()) / Length) < (1.0 / Threshold))) |
| 1017 | return false; |
| 1018 | |
| 1019 | // If the virtual register live interval extends into a loop, turn down |
| 1020 | // aggressiveness. |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 1021 | MachineInstrIndex CopyIdx = |
| 1022 | li_->getDefIndex(li_->getInstructionIndex(CopyMI)); |
Evan Cheng | 0490dcb | 2009-04-30 18:39:57 +0000 | [diff] [blame] | 1023 | const MachineLoop *L = loopInfo->getLoopFor(CopyMBB); |
| 1024 | if (!L) { |
| 1025 | // Let's see if the virtual register live interval extends into the loop. |
| 1026 | LiveInterval::iterator DLR = DstInt.FindLiveRangeContaining(CopyIdx); |
| 1027 | assert(DLR != DstInt.end() && "Live range not found!"); |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 1028 | DLR = DstInt.FindLiveRangeContaining(li_->getNextSlot(DLR->end)); |
Evan Cheng | 0490dcb | 2009-04-30 18:39:57 +0000 | [diff] [blame] | 1029 | if (DLR != DstInt.end()) { |
| 1030 | CopyMBB = li_->getMBBFromIndex(DLR->start); |
| 1031 | L = loopInfo->getLoopFor(CopyMBB); |
| 1032 | } |
| 1033 | } |
| 1034 | |
| 1035 | if (!L || Length <= Threshold) |
| 1036 | return true; |
| 1037 | |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 1038 | MachineInstrIndex UseIdx = li_->getUseIndex(CopyIdx); |
Evan Cheng | 0490dcb | 2009-04-30 18:39:57 +0000 | [diff] [blame] | 1039 | LiveInterval::iterator SLR = SrcInt.FindLiveRangeContaining(UseIdx); |
| 1040 | MachineBasicBlock *SMBB = li_->getMBBFromIndex(SLR->start); |
| 1041 | if (loopInfo->getLoopFor(SMBB) != L) { |
| 1042 | if (!loopInfo->isLoopHeader(CopyMBB)) |
| 1043 | return false; |
| 1044 | // If vr's live interval extends pass the loop header, do not join. |
| 1045 | for (MachineBasicBlock::succ_iterator SI = CopyMBB->succ_begin(), |
| 1046 | SE = CopyMBB->succ_end(); SI != SE; ++SI) { |
| 1047 | MachineBasicBlock *SuccMBB = *SI; |
| 1048 | if (SuccMBB == CopyMBB) |
| 1049 | continue; |
| 1050 | if (DstInt.overlaps(li_->getMBBStartIdx(SuccMBB), |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 1051 | li_->getNextSlot(li_->getMBBEndIdx(SuccMBB)))) |
Evan Cheng | 0490dcb | 2009-04-30 18:39:57 +0000 | [diff] [blame] | 1052 | return false; |
| 1053 | } |
| 1054 | } |
| 1055 | return true; |
| 1056 | } |
| 1057 | |
| 1058 | /// isWinToJoinVRWithDstPhysReg - Return true if it's worth while to join a |
| 1059 | /// copy from a virtual source register to a physical destination register. |
| 1060 | bool |
| 1061 | SimpleRegisterCoalescing::isWinToJoinVRWithDstPhysReg(MachineInstr *CopyMI, |
| 1062 | MachineBasicBlock *CopyMBB, |
| 1063 | LiveInterval &DstInt, |
| 1064 | LiveInterval &SrcInt) { |
| 1065 | // If the virtual register live interval is long but it has low use desity, |
| 1066 | // do not join them, instead mark the physical register as its allocation |
| 1067 | // preference. |
| 1068 | const TargetRegisterClass *RC = mri_->getRegClass(SrcInt.reg); |
| 1069 | unsigned Threshold = allocatableRCRegs_[RC].count() * 2; |
| 1070 | unsigned Length = li_->getApproximateInstructionCount(SrcInt); |
| 1071 | if (Length > Threshold && |
| 1072 | (((float)std::distance(mri_->use_begin(SrcInt.reg), |
| 1073 | mri_->use_end()) / Length) < (1.0 / Threshold))) |
| 1074 | return false; |
| 1075 | |
| 1076 | if (SrcInt.empty()) |
| 1077 | // Must be implicit_def. |
| 1078 | return false; |
| 1079 | |
| 1080 | // If the virtual register live interval is defined or cross a loop, turn |
| 1081 | // down aggressiveness. |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 1082 | MachineInstrIndex CopyIdx = |
| 1083 | li_->getDefIndex(li_->getInstructionIndex(CopyMI)); |
| 1084 | MachineInstrIndex UseIdx = li_->getUseIndex(CopyIdx); |
Evan Cheng | 0490dcb | 2009-04-30 18:39:57 +0000 | [diff] [blame] | 1085 | LiveInterval::iterator SLR = SrcInt.FindLiveRangeContaining(UseIdx); |
| 1086 | assert(SLR != SrcInt.end() && "Live range not found!"); |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 1087 | SLR = SrcInt.FindLiveRangeContaining(li_->getPrevSlot(SLR->start)); |
Evan Cheng | 0490dcb | 2009-04-30 18:39:57 +0000 | [diff] [blame] | 1088 | if (SLR == SrcInt.end()) |
| 1089 | return true; |
| 1090 | MachineBasicBlock *SMBB = li_->getMBBFromIndex(SLR->start); |
| 1091 | const MachineLoop *L = loopInfo->getLoopFor(SMBB); |
| 1092 | |
| 1093 | if (!L || Length <= Threshold) |
| 1094 | return true; |
| 1095 | |
| 1096 | if (loopInfo->getLoopFor(CopyMBB) != L) { |
| 1097 | if (SMBB != L->getLoopLatch()) |
| 1098 | return false; |
| 1099 | // If vr's live interval is extended from before the loop latch, do not |
| 1100 | // join. |
| 1101 | for (MachineBasicBlock::pred_iterator PI = SMBB->pred_begin(), |
| 1102 | PE = SMBB->pred_end(); PI != PE; ++PI) { |
| 1103 | MachineBasicBlock *PredMBB = *PI; |
| 1104 | if (PredMBB == SMBB) |
| 1105 | continue; |
| 1106 | if (SrcInt.overlaps(li_->getMBBStartIdx(PredMBB), |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 1107 | li_->getNextSlot(li_->getMBBEndIdx(PredMBB)))) |
Evan Cheng | 0490dcb | 2009-04-30 18:39:57 +0000 | [diff] [blame] | 1108 | return false; |
| 1109 | } |
| 1110 | } |
| 1111 | return true; |
| 1112 | } |
| 1113 | |
Evan Cheng | 8c08d8c | 2009-01-23 02:15:19 +0000 | [diff] [blame] | 1114 | /// isWinToJoinCrossClass - Return true if it's profitable to coalesce |
| 1115 | /// two virtual registers from different register classes. |
Evan Cheng | e00f5de | 2008-06-19 01:39:21 +0000 | [diff] [blame] | 1116 | bool |
Evan Cheng | 8c08d8c | 2009-01-23 02:15:19 +0000 | [diff] [blame] | 1117 | SimpleRegisterCoalescing::isWinToJoinCrossClass(unsigned LargeReg, |
| 1118 | unsigned SmallReg, |
| 1119 | unsigned Threshold) { |
Evan Cheng | e00f5de | 2008-06-19 01:39:21 +0000 | [diff] [blame] | 1120 | // Then make sure the intervals are *short*. |
Evan Cheng | 8c08d8c | 2009-01-23 02:15:19 +0000 | [diff] [blame] | 1121 | LiveInterval &LargeInt = li_->getInterval(LargeReg); |
| 1122 | LiveInterval &SmallInt = li_->getInterval(SmallReg); |
| 1123 | unsigned LargeSize = li_->getApproximateInstructionCount(LargeInt); |
| 1124 | unsigned SmallSize = li_->getApproximateInstructionCount(SmallInt); |
| 1125 | if (SmallSize > Threshold || LargeSize > Threshold) |
| 1126 | if ((float)std::distance(mri_->use_begin(SmallReg), |
| 1127 | mri_->use_end()) / SmallSize < |
| 1128 | (float)std::distance(mri_->use_begin(LargeReg), |
| 1129 | mri_->use_end()) / LargeSize) |
| 1130 | return false; |
| 1131 | return true; |
Evan Cheng | e00f5de | 2008-06-19 01:39:21 +0000 | [diff] [blame] | 1132 | } |
| 1133 | |
Evan Cheng | 8db8668 | 2008-09-11 20:07:10 +0000 | [diff] [blame] | 1134 | /// HasIncompatibleSubRegDefUse - If we are trying to coalesce a virtual |
| 1135 | /// register with a physical register, check if any of the virtual register |
| 1136 | /// operand is a sub-register use or def. If so, make sure it won't result |
| 1137 | /// in an illegal extract_subreg or insert_subreg instruction. e.g. |
| 1138 | /// vr1024 = extract_subreg vr1025, 1 |
| 1139 | /// ... |
| 1140 | /// vr1024 = mov8rr AH |
| 1141 | /// If vr1024 is coalesced with AH, the extract_subreg is now illegal since |
| 1142 | /// AH does not have a super-reg whose sub-register 1 is AH. |
| 1143 | bool |
| 1144 | SimpleRegisterCoalescing::HasIncompatibleSubRegDefUse(MachineInstr *CopyMI, |
| 1145 | unsigned VirtReg, |
| 1146 | unsigned PhysReg) { |
| 1147 | for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(VirtReg), |
| 1148 | E = mri_->reg_end(); I != E; ++I) { |
| 1149 | MachineOperand &O = I.getOperand(); |
| 1150 | MachineInstr *MI = &*I; |
| 1151 | if (MI == CopyMI || JoinedCopies.count(MI)) |
| 1152 | continue; |
| 1153 | unsigned SubIdx = O.getSubReg(); |
| 1154 | if (SubIdx && !tri_->getSubReg(PhysReg, SubIdx)) |
| 1155 | return true; |
| 1156 | if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) { |
| 1157 | SubIdx = MI->getOperand(2).getImm(); |
| 1158 | if (O.isUse() && !tri_->getSubReg(PhysReg, SubIdx)) |
| 1159 | return true; |
| 1160 | if (O.isDef()) { |
| 1161 | unsigned SrcReg = MI->getOperand(1).getReg(); |
| 1162 | const TargetRegisterClass *RC = |
| 1163 | TargetRegisterInfo::isPhysicalRegister(SrcReg) |
| 1164 | ? tri_->getPhysicalRegisterRegClass(SrcReg) |
| 1165 | : mri_->getRegClass(SrcReg); |
Evan Cheng | 8a8a0df | 2009-04-28 18:29:27 +0000 | [diff] [blame] | 1166 | if (!tri_->getMatchingSuperReg(PhysReg, SubIdx, RC)) |
Evan Cheng | 8db8668 | 2008-09-11 20:07:10 +0000 | [diff] [blame] | 1167 | return true; |
| 1168 | } |
| 1169 | } |
Dan Gohman | 97121ba | 2009-04-08 00:15:30 +0000 | [diff] [blame] | 1170 | if (MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG || |
| 1171 | MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG) { |
Evan Cheng | 8db8668 | 2008-09-11 20:07:10 +0000 | [diff] [blame] | 1172 | SubIdx = MI->getOperand(3).getImm(); |
| 1173 | if (VirtReg == MI->getOperand(0).getReg()) { |
| 1174 | if (!tri_->getSubReg(PhysReg, SubIdx)) |
| 1175 | return true; |
| 1176 | } else { |
| 1177 | unsigned DstReg = MI->getOperand(0).getReg(); |
| 1178 | const TargetRegisterClass *RC = |
| 1179 | TargetRegisterInfo::isPhysicalRegister(DstReg) |
| 1180 | ? tri_->getPhysicalRegisterRegClass(DstReg) |
| 1181 | : mri_->getRegClass(DstReg); |
Evan Cheng | 8a8a0df | 2009-04-28 18:29:27 +0000 | [diff] [blame] | 1182 | if (!tri_->getMatchingSuperReg(PhysReg, SubIdx, RC)) |
Evan Cheng | 8db8668 | 2008-09-11 20:07:10 +0000 | [diff] [blame] | 1183 | return true; |
| 1184 | } |
| 1185 | } |
| 1186 | } |
| 1187 | return false; |
| 1188 | } |
| 1189 | |
Evan Cheng | e00f5de | 2008-06-19 01:39:21 +0000 | [diff] [blame] | 1190 | |
Evan Cheng | e08eb9c | 2009-01-20 06:44:16 +0000 | [diff] [blame] | 1191 | /// CanJoinExtractSubRegToPhysReg - Return true if it's possible to coalesce |
| 1192 | /// an extract_subreg where dst is a physical register, e.g. |
| 1193 | /// cl = EXTRACT_SUBREG reg1024, 1 |
| 1194 | bool |
Evan Cheng | 8c08d8c | 2009-01-23 02:15:19 +0000 | [diff] [blame] | 1195 | SimpleRegisterCoalescing::CanJoinExtractSubRegToPhysReg(unsigned DstReg, |
| 1196 | unsigned SrcReg, unsigned SubIdx, |
| 1197 | unsigned &RealDstReg) { |
Evan Cheng | e08eb9c | 2009-01-20 06:44:16 +0000 | [diff] [blame] | 1198 | const TargetRegisterClass *RC = mri_->getRegClass(SrcReg); |
Evan Cheng | 8a8a0df | 2009-04-28 18:29:27 +0000 | [diff] [blame] | 1199 | RealDstReg = tri_->getMatchingSuperReg(DstReg, SubIdx, RC); |
Evan Cheng | e08eb9c | 2009-01-20 06:44:16 +0000 | [diff] [blame] | 1200 | assert(RealDstReg && "Invalid extract_subreg instruction!"); |
| 1201 | |
| 1202 | // For this type of EXTRACT_SUBREG, conservatively |
| 1203 | // check if the live interval of the source register interfere with the |
| 1204 | // actual super physical register we are trying to coalesce with. |
| 1205 | LiveInterval &RHS = li_->getInterval(SrcReg); |
| 1206 | if (li_->hasInterval(RealDstReg) && |
| 1207 | RHS.overlaps(li_->getInterval(RealDstReg))) { |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 1208 | DEBUG({ |
| 1209 | errs() << "Interfere with register "; |
| 1210 | li_->getInterval(RealDstReg).print(errs(), tri_); |
| 1211 | }); |
Evan Cheng | e08eb9c | 2009-01-20 06:44:16 +0000 | [diff] [blame] | 1212 | return false; // Not coalescable |
| 1213 | } |
| 1214 | for (const unsigned* SR = tri_->getSubRegisters(RealDstReg); *SR; ++SR) |
| 1215 | if (li_->hasInterval(*SR) && RHS.overlaps(li_->getInterval(*SR))) { |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 1216 | DEBUG({ |
| 1217 | errs() << "Interfere with sub-register "; |
| 1218 | li_->getInterval(*SR).print(errs(), tri_); |
| 1219 | }); |
Evan Cheng | e08eb9c | 2009-01-20 06:44:16 +0000 | [diff] [blame] | 1220 | return false; // Not coalescable |
| 1221 | } |
| 1222 | return true; |
| 1223 | } |
| 1224 | |
| 1225 | /// CanJoinInsertSubRegToPhysReg - Return true if it's possible to coalesce |
| 1226 | /// an insert_subreg where src is a physical register, e.g. |
| 1227 | /// reg1024 = INSERT_SUBREG reg1024, c1, 0 |
| 1228 | bool |
Evan Cheng | 8c08d8c | 2009-01-23 02:15:19 +0000 | [diff] [blame] | 1229 | SimpleRegisterCoalescing::CanJoinInsertSubRegToPhysReg(unsigned DstReg, |
| 1230 | unsigned SrcReg, unsigned SubIdx, |
| 1231 | unsigned &RealSrcReg) { |
Evan Cheng | e08eb9c | 2009-01-20 06:44:16 +0000 | [diff] [blame] | 1232 | const TargetRegisterClass *RC = mri_->getRegClass(DstReg); |
Evan Cheng | 8a8a0df | 2009-04-28 18:29:27 +0000 | [diff] [blame] | 1233 | RealSrcReg = tri_->getMatchingSuperReg(SrcReg, SubIdx, RC); |
Evan Cheng | e08eb9c | 2009-01-20 06:44:16 +0000 | [diff] [blame] | 1234 | assert(RealSrcReg && "Invalid extract_subreg instruction!"); |
| 1235 | |
| 1236 | LiveInterval &RHS = li_->getInterval(DstReg); |
| 1237 | if (li_->hasInterval(RealSrcReg) && |
| 1238 | RHS.overlaps(li_->getInterval(RealSrcReg))) { |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 1239 | DEBUG({ |
| 1240 | errs() << "Interfere with register "; |
| 1241 | li_->getInterval(RealSrcReg).print(errs(), tri_); |
| 1242 | }); |
Evan Cheng | e08eb9c | 2009-01-20 06:44:16 +0000 | [diff] [blame] | 1243 | return false; // Not coalescable |
| 1244 | } |
| 1245 | for (const unsigned* SR = tri_->getSubRegisters(RealSrcReg); *SR; ++SR) |
| 1246 | if (li_->hasInterval(*SR) && RHS.overlaps(li_->getInterval(*SR))) { |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 1247 | DEBUG({ |
| 1248 | errs() << "Interfere with sub-register "; |
| 1249 | li_->getInterval(*SR).print(errs(), tri_); |
| 1250 | }); |
Evan Cheng | e08eb9c | 2009-01-20 06:44:16 +0000 | [diff] [blame] | 1251 | return false; // Not coalescable |
| 1252 | } |
| 1253 | return true; |
| 1254 | } |
| 1255 | |
Evan Cheng | 90f95f8 | 2009-06-14 20:22:55 +0000 | [diff] [blame] | 1256 | /// getRegAllocPreference - Return register allocation preference register. |
| 1257 | /// |
| 1258 | static unsigned getRegAllocPreference(unsigned Reg, MachineFunction &MF, |
| 1259 | MachineRegisterInfo *MRI, |
| 1260 | const TargetRegisterInfo *TRI) { |
| 1261 | if (TargetRegisterInfo::isPhysicalRegister(Reg)) |
| 1262 | return 0; |
Evan Cheng | 358dec5 | 2009-06-15 08:28:29 +0000 | [diff] [blame] | 1263 | std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(Reg); |
| 1264 | return TRI->ResolveRegAllocHint(Hint.first, Hint.second, MF); |
Evan Cheng | 90f95f8 | 2009-06-14 20:22:55 +0000 | [diff] [blame] | 1265 | } |
| 1266 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1267 | /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, |
| 1268 | /// which are the src/dst of the copy instruction CopyMI. This returns true |
Evan Cheng | 0547bab | 2007-11-01 06:22:48 +0000 | [diff] [blame] | 1269 | /// if the copy was successfully coalesced away. If it is not currently |
| 1270 | /// possible to coalesce this interval, but it may be possible if other |
| 1271 | /// things get coalesced, then it returns true by reference in 'Again'. |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 1272 | bool SimpleRegisterCoalescing::JoinCopy(CopyRec &TheCopy, bool &Again) { |
Evan Cheng | 8fc9a10 | 2007-11-06 08:52:21 +0000 | [diff] [blame] | 1273 | MachineInstr *CopyMI = TheCopy.MI; |
| 1274 | |
| 1275 | Again = false; |
Evan Cheng | cd04708 | 2008-08-30 09:09:33 +0000 | [diff] [blame] | 1276 | if (JoinedCopies.count(CopyMI) || ReMatCopies.count(CopyMI)) |
Evan Cheng | 8fc9a10 | 2007-11-06 08:52:21 +0000 | [diff] [blame] | 1277 | return false; // Already done. |
| 1278 | |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 1279 | DEBUG(errs() << li_->getInstructionIndex(CopyMI) << '\t' << *CopyMI); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1280 | |
Jakob Stoklund Olesen | 08e791f | 2009-04-28 16:34:35 +0000 | [diff] [blame] | 1281 | unsigned SrcReg, DstReg, SrcSubIdx = 0, DstSubIdx = 0; |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 1282 | bool isExtSubReg = CopyMI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG; |
Evan Cheng | 7e073ba | 2008-04-09 20:57:25 +0000 | [diff] [blame] | 1283 | bool isInsSubReg = CopyMI->getOpcode() == TargetInstrInfo::INSERT_SUBREG; |
Dan Gohman | 97121ba | 2009-04-08 00:15:30 +0000 | [diff] [blame] | 1284 | bool isSubRegToReg = CopyMI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG; |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 1285 | unsigned SubIdx = 0; |
| 1286 | if (isExtSubReg) { |
Jakob Stoklund Olesen | 08e791f | 2009-04-28 16:34:35 +0000 | [diff] [blame] | 1287 | DstReg = CopyMI->getOperand(0).getReg(); |
| 1288 | DstSubIdx = CopyMI->getOperand(0).getSubReg(); |
| 1289 | SrcReg = CopyMI->getOperand(1).getReg(); |
| 1290 | SrcSubIdx = CopyMI->getOperand(2).getImm(); |
Dan Gohman | 97121ba | 2009-04-08 00:15:30 +0000 | [diff] [blame] | 1291 | } else if (isInsSubReg || isSubRegToReg) { |
Evan Cheng | 438d990 | 2009-07-18 04:52:23 +0000 | [diff] [blame] | 1292 | DstReg = CopyMI->getOperand(0).getReg(); |
| 1293 | DstSubIdx = CopyMI->getOperand(3).getImm(); |
| 1294 | SrcReg = CopyMI->getOperand(2).getReg(); |
| 1295 | SrcSubIdx = CopyMI->getOperand(2).getSubReg(); |
| 1296 | if (SrcSubIdx && SrcSubIdx != DstSubIdx) { |
| 1297 | // r1025 = INSERT_SUBREG r1025, r1024<2>, 2 Then r1024 has already been |
| 1298 | // coalesced to a larger register so the subreg indices cancel out. |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 1299 | DEBUG(errs() << "\tSource of insert_subreg is already coalesced " |
| 1300 | << "to another register.\n"); |
Evan Cheng | 7e073ba | 2008-04-09 20:57:25 +0000 | [diff] [blame] | 1301 | return false; // Not coalescable. |
| 1302 | } |
Evan Cheng | 04ee5a1 | 2009-01-20 19:12:24 +0000 | [diff] [blame] | 1303 | } else if (!tii_->isMoveInstr(*CopyMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)){ |
Torok Edwin | c23197a | 2009-07-14 16:55:14 +0000 | [diff] [blame] | 1304 | llvm_unreachable("Unrecognized copy instruction!"); |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 1305 | } |
| 1306 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1307 | // If they are already joined we continue. |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 1308 | if (SrcReg == DstReg) { |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 1309 | DEBUG(errs() << "\tCopy already coalesced.\n"); |
Evan Cheng | 0547bab | 2007-11-01 06:22:48 +0000 | [diff] [blame] | 1310 | return false; // Not coalescable. |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1311 | } |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 1312 | |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 1313 | bool SrcIsPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg); |
| 1314 | bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1315 | |
| 1316 | // If they are both physical registers, we cannot join them. |
| 1317 | if (SrcIsPhys && DstIsPhys) { |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 1318 | DEBUG(errs() << "\tCan not coalesce physregs.\n"); |
Evan Cheng | 0547bab | 2007-11-01 06:22:48 +0000 | [diff] [blame] | 1319 | return false; // Not coalescable. |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1320 | } |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 1321 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1322 | // We only join virtual registers with allocatable physical registers. |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 1323 | if (SrcIsPhys && !allocatableRegs_[SrcReg]) { |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 1324 | DEBUG(errs() << "\tSrc reg is unallocatable physreg.\n"); |
Evan Cheng | 0547bab | 2007-11-01 06:22:48 +0000 | [diff] [blame] | 1325 | return false; // Not coalescable. |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1326 | } |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 1327 | if (DstIsPhys && !allocatableRegs_[DstReg]) { |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 1328 | DEBUG(errs() << "\tDst reg is unallocatable physreg.\n"); |
Evan Cheng | 0547bab | 2007-11-01 06:22:48 +0000 | [diff] [blame] | 1329 | return false; // Not coalescable. |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1330 | } |
Evan Cheng | 32dfbea | 2007-10-12 08:50:34 +0000 | [diff] [blame] | 1331 | |
Jakob Stoklund Olesen | 08e791f | 2009-04-28 16:34:35 +0000 | [diff] [blame] | 1332 | // Check that a physical source register is compatible with dst regclass |
| 1333 | if (SrcIsPhys) { |
| 1334 | unsigned SrcSubReg = SrcSubIdx ? |
| 1335 | tri_->getSubReg(SrcReg, SrcSubIdx) : SrcReg; |
| 1336 | const TargetRegisterClass *DstRC = mri_->getRegClass(DstReg); |
| 1337 | const TargetRegisterClass *DstSubRC = DstRC; |
| 1338 | if (DstSubIdx) |
| 1339 | DstSubRC = DstRC->getSubRegisterRegClass(DstSubIdx); |
| 1340 | assert(DstSubRC && "Illegal subregister index"); |
| 1341 | if (!DstSubRC->contains(SrcSubReg)) { |
Daniel Dunbar | ce63ffb | 2009-07-25 00:23:56 +0000 | [diff] [blame] | 1342 | DEBUG(errs() << "\tIncompatible destination regclass: " |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 1343 | << tri_->getName(SrcSubReg) << " not in " |
| 1344 | << DstSubRC->getName() << ".\n"); |
Jakob Stoklund Olesen | 08e791f | 2009-04-28 16:34:35 +0000 | [diff] [blame] | 1345 | return false; // Not coalescable. |
| 1346 | } |
| 1347 | } |
| 1348 | |
| 1349 | // Check that a physical dst register is compatible with source regclass |
| 1350 | if (DstIsPhys) { |
| 1351 | unsigned DstSubReg = DstSubIdx ? |
| 1352 | tri_->getSubReg(DstReg, DstSubIdx) : DstReg; |
| 1353 | const TargetRegisterClass *SrcRC = mri_->getRegClass(SrcReg); |
| 1354 | const TargetRegisterClass *SrcSubRC = SrcRC; |
| 1355 | if (SrcSubIdx) |
| 1356 | SrcSubRC = SrcRC->getSubRegisterRegClass(SrcSubIdx); |
| 1357 | assert(SrcSubRC && "Illegal subregister index"); |
| 1358 | if (!SrcSubRC->contains(DstReg)) { |
Daniel Dunbar | ce63ffb | 2009-07-25 00:23:56 +0000 | [diff] [blame] | 1359 | DEBUG(errs() << "\tIncompatible source regclass: " |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 1360 | << tri_->getName(DstSubReg) << " not in " |
| 1361 | << SrcSubRC->getName() << ".\n"); |
Mike Stump | 02efa78 | 2009-07-27 23:14:11 +0000 | [diff] [blame] | 1362 | (void)DstSubReg; |
Jakob Stoklund Olesen | 08e791f | 2009-04-28 16:34:35 +0000 | [diff] [blame] | 1363 | return false; // Not coalescable. |
| 1364 | } |
| 1365 | } |
| 1366 | |
Evan Cheng | e00f5de | 2008-06-19 01:39:21 +0000 | [diff] [blame] | 1367 | // Should be non-null only when coalescing to a sub-register class. |
Evan Cheng | 8c08d8c | 2009-01-23 02:15:19 +0000 | [diff] [blame] | 1368 | bool CrossRC = false; |
Evan Cheng | 5248468 | 2009-07-18 02:10:10 +0000 | [diff] [blame] | 1369 | const TargetRegisterClass *SrcRC= SrcIsPhys ? 0 : mri_->getRegClass(SrcReg); |
| 1370 | const TargetRegisterClass *DstRC= DstIsPhys ? 0 : mri_->getRegClass(DstReg); |
Evan Cheng | 8c08d8c | 2009-01-23 02:15:19 +0000 | [diff] [blame] | 1371 | const TargetRegisterClass *NewRC = NULL; |
Evan Cheng | e00f5de | 2008-06-19 01:39:21 +0000 | [diff] [blame] | 1372 | MachineBasicBlock *CopyMBB = CopyMI->getParent(); |
Evan Cheng | 32dfbea | 2007-10-12 08:50:34 +0000 | [diff] [blame] | 1373 | unsigned RealDstReg = 0; |
Evan Cheng | 7e073ba | 2008-04-09 20:57:25 +0000 | [diff] [blame] | 1374 | unsigned RealSrcReg = 0; |
Dan Gohman | 97121ba | 2009-04-08 00:15:30 +0000 | [diff] [blame] | 1375 | if (isExtSubReg || isInsSubReg || isSubRegToReg) { |
Evan Cheng | 7e073ba | 2008-04-09 20:57:25 +0000 | [diff] [blame] | 1376 | SubIdx = CopyMI->getOperand(isExtSubReg ? 2 : 3).getImm(); |
| 1377 | if (SrcIsPhys && isExtSubReg) { |
Evan Cheng | 32dfbea | 2007-10-12 08:50:34 +0000 | [diff] [blame] | 1378 | // r1024 = EXTRACT_SUBREG EAX, 0 then r1024 is really going to be |
| 1379 | // coalesced with AX. |
Evan Cheng | 621d157 | 2008-04-17 00:06:42 +0000 | [diff] [blame] | 1380 | unsigned DstSubIdx = CopyMI->getOperand(0).getSubReg(); |
Evan Cheng | 639f493 | 2008-04-17 07:58:04 +0000 | [diff] [blame] | 1381 | if (DstSubIdx) { |
| 1382 | // r1024<2> = EXTRACT_SUBREG EAX, 2. Then r1024 has already been |
| 1383 | // coalesced to a larger register so the subreg indices cancel out. |
| 1384 | if (DstSubIdx != SubIdx) { |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 1385 | DEBUG(errs() << "\t Sub-register indices mismatch.\n"); |
Evan Cheng | 639f493 | 2008-04-17 07:58:04 +0000 | [diff] [blame] | 1386 | return false; // Not coalescable. |
| 1387 | } |
| 1388 | } else |
Evan Cheng | 621d157 | 2008-04-17 00:06:42 +0000 | [diff] [blame] | 1389 | SrcReg = tri_->getSubReg(SrcReg, SubIdx); |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 1390 | SubIdx = 0; |
Dan Gohman | 97121ba | 2009-04-08 00:15:30 +0000 | [diff] [blame] | 1391 | } else if (DstIsPhys && (isInsSubReg || isSubRegToReg)) { |
Evan Cheng | 7e073ba | 2008-04-09 20:57:25 +0000 | [diff] [blame] | 1392 | // EAX = INSERT_SUBREG EAX, r1024, 0 |
Evan Cheng | 621d157 | 2008-04-17 00:06:42 +0000 | [diff] [blame] | 1393 | unsigned SrcSubIdx = CopyMI->getOperand(2).getSubReg(); |
Evan Cheng | 639f493 | 2008-04-17 07:58:04 +0000 | [diff] [blame] | 1394 | if (SrcSubIdx) { |
| 1395 | // EAX = INSERT_SUBREG EAX, r1024<2>, 2 Then r1024 has already been |
| 1396 | // coalesced to a larger register so the subreg indices cancel out. |
| 1397 | if (SrcSubIdx != SubIdx) { |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 1398 | DEBUG(errs() << "\t Sub-register indices mismatch.\n"); |
Evan Cheng | 639f493 | 2008-04-17 07:58:04 +0000 | [diff] [blame] | 1399 | return false; // Not coalescable. |
| 1400 | } |
| 1401 | } else |
| 1402 | DstReg = tri_->getSubReg(DstReg, SubIdx); |
Evan Cheng | 7e073ba | 2008-04-09 20:57:25 +0000 | [diff] [blame] | 1403 | SubIdx = 0; |
Dan Gohman | 97121ba | 2009-04-08 00:15:30 +0000 | [diff] [blame] | 1404 | } else if ((DstIsPhys && isExtSubReg) || |
| 1405 | (SrcIsPhys && (isInsSubReg || isSubRegToReg))) { |
| 1406 | if (!isSubRegToReg && CopyMI->getOperand(1).getSubReg()) { |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 1407 | DEBUG(errs() << "\tSrc of extract_subreg already coalesced with reg" |
| 1408 | << " of a super-class.\n"); |
Evan Cheng | 8c08d8c | 2009-01-23 02:15:19 +0000 | [diff] [blame] | 1409 | return false; // Not coalescable. |
| 1410 | } |
| 1411 | |
Evan Cheng | 7e073ba | 2008-04-09 20:57:25 +0000 | [diff] [blame] | 1412 | if (isExtSubReg) { |
Evan Cheng | 8c08d8c | 2009-01-23 02:15:19 +0000 | [diff] [blame] | 1413 | if (!CanJoinExtractSubRegToPhysReg(DstReg, SrcReg, SubIdx, RealDstReg)) |
Evan Cheng | 0547bab | 2007-11-01 06:22:48 +0000 | [diff] [blame] | 1414 | return false; // Not coalescable |
Evan Cheng | e08eb9c | 2009-01-20 06:44:16 +0000 | [diff] [blame] | 1415 | } else { |
Evan Cheng | 8c08d8c | 2009-01-23 02:15:19 +0000 | [diff] [blame] | 1416 | if (!CanJoinInsertSubRegToPhysReg(DstReg, SrcReg, SubIdx, RealSrcReg)) |
Evan Cheng | e08eb9c | 2009-01-20 06:44:16 +0000 | [diff] [blame] | 1417 | return false; // Not coalescable |
| 1418 | } |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 1419 | SubIdx = 0; |
Evan Cheng | 0547bab | 2007-11-01 06:22:48 +0000 | [diff] [blame] | 1420 | } else { |
Evan Cheng | 639f493 | 2008-04-17 07:58:04 +0000 | [diff] [blame] | 1421 | unsigned OldSubIdx = isExtSubReg ? CopyMI->getOperand(0).getSubReg() |
| 1422 | : CopyMI->getOperand(2).getSubReg(); |
| 1423 | if (OldSubIdx) { |
Evan Cheng | 8c08d8c | 2009-01-23 02:15:19 +0000 | [diff] [blame] | 1424 | if (OldSubIdx == SubIdx && !differingRegisterClasses(SrcReg, DstReg)) |
Evan Cheng | 639f493 | 2008-04-17 07:58:04 +0000 | [diff] [blame] | 1425 | // r1024<2> = EXTRACT_SUBREG r1025, 2. Then r1024 has already been |
| 1426 | // coalesced to a larger register so the subreg indices cancel out. |
Evan Cheng | 8509fcf | 2008-04-29 01:41:44 +0000 | [diff] [blame] | 1427 | // Also check if the other larger register is of the same register |
| 1428 | // class as the would be resulting register. |
Evan Cheng | 639f493 | 2008-04-17 07:58:04 +0000 | [diff] [blame] | 1429 | SubIdx = 0; |
| 1430 | else { |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 1431 | DEBUG(errs() << "\t Sub-register indices mismatch.\n"); |
Evan Cheng | 639f493 | 2008-04-17 07:58:04 +0000 | [diff] [blame] | 1432 | return false; // Not coalescable. |
| 1433 | } |
| 1434 | } |
| 1435 | if (SubIdx) { |
Evan Cheng | 753480a | 2009-07-20 19:47:55 +0000 | [diff] [blame] | 1436 | if (!DstIsPhys && !SrcIsPhys) { |
| 1437 | if (isInsSubReg || isSubRegToReg) { |
Evan Cheng | 5248468 | 2009-07-18 02:10:10 +0000 | [diff] [blame] | 1438 | NewRC = tri_->getMatchingSuperRegClass(DstRC, SrcRC, SubIdx); |
Evan Cheng | 753480a | 2009-07-20 19:47:55 +0000 | [diff] [blame] | 1439 | } else // extract_subreg { |
| 1440 | NewRC = tri_->getMatchingSuperRegClass(SrcRC, DstRC, SubIdx); |
Evan Cheng | 5248468 | 2009-07-18 02:10:10 +0000 | [diff] [blame] | 1441 | } |
Evan Cheng | 753480a | 2009-07-20 19:47:55 +0000 | [diff] [blame] | 1442 | if (!NewRC) { |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 1443 | DEBUG(errs() << "\t Conflicting sub-register indices.\n"); |
Evan Cheng | 753480a | 2009-07-20 19:47:55 +0000 | [diff] [blame] | 1444 | return false; // Not coalescable |
Evan Cheng | 5248468 | 2009-07-18 02:10:10 +0000 | [diff] [blame] | 1445 | } |
Evan Cheng | 753480a | 2009-07-20 19:47:55 +0000 | [diff] [blame] | 1446 | |
Evan Cheng | 639f493 | 2008-04-17 07:58:04 +0000 | [diff] [blame] | 1447 | unsigned LargeReg = isExtSubReg ? SrcReg : DstReg; |
| 1448 | unsigned SmallReg = isExtSubReg ? DstReg : SrcReg; |
Evan Cheng | 8c08d8c | 2009-01-23 02:15:19 +0000 | [diff] [blame] | 1449 | unsigned Limit= allocatableRCRegs_[mri_->getRegClass(SmallReg)].count(); |
| 1450 | if (!isWinToJoinCrossClass(LargeReg, SmallReg, Limit)) { |
| 1451 | Again = true; // May be possible to coalesce later. |
| 1452 | return false; |
Evan Cheng | 0547bab | 2007-11-01 06:22:48 +0000 | [diff] [blame] | 1453 | } |
| 1454 | } |
Evan Cheng | 32dfbea | 2007-10-12 08:50:34 +0000 | [diff] [blame] | 1455 | } |
Evan Cheng | 8c08d8c | 2009-01-23 02:15:19 +0000 | [diff] [blame] | 1456 | } else if (differingRegisterClasses(SrcReg, DstReg)) { |
Evan Cheng | c95be59 | 2009-07-21 00:22:59 +0000 | [diff] [blame] | 1457 | if (DisableCrossClassJoin) |
Evan Cheng | 8c08d8c | 2009-01-23 02:15:19 +0000 | [diff] [blame] | 1458 | return false; |
| 1459 | CrossRC = true; |
| 1460 | |
| 1461 | // FIXME: What if the result of a EXTRACT_SUBREG is then coalesced |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 1462 | // with another? If it's the resulting destination register, then |
| 1463 | // the subidx must be propagated to uses (but only those defined |
| 1464 | // by the EXTRACT_SUBREG). If it's being coalesced into another |
| 1465 | // register, it should be safe because register is assumed to have |
| 1466 | // the register class of the super-register. |
| 1467 | |
Evan Cheng | 8c08d8c | 2009-01-23 02:15:19 +0000 | [diff] [blame] | 1468 | // Process moves where one of the registers have a sub-register index. |
| 1469 | MachineOperand *DstMO = CopyMI->findRegisterDefOperand(DstReg); |
Evan Cheng | 8c08d8c | 2009-01-23 02:15:19 +0000 | [diff] [blame] | 1470 | MachineOperand *SrcMO = CopyMI->findRegisterUseOperand(SrcReg); |
Dan Gohman | 97121ba | 2009-04-08 00:15:30 +0000 | [diff] [blame] | 1471 | SubIdx = DstMO->getSubReg(); |
Evan Cheng | 8c08d8c | 2009-01-23 02:15:19 +0000 | [diff] [blame] | 1472 | if (SubIdx) { |
Dan Gohman | 97121ba | 2009-04-08 00:15:30 +0000 | [diff] [blame] | 1473 | if (SrcMO->getSubReg()) |
| 1474 | // FIXME: can we handle this? |
| 1475 | return false; |
| 1476 | // This is not an insert_subreg but it looks like one. |
Evan Cheng | aa809fb | 2009-04-23 20:39:31 +0000 | [diff] [blame] | 1477 | // e.g. %reg1024:4 = MOV32rr %EAX |
Dan Gohman | 97121ba | 2009-04-08 00:15:30 +0000 | [diff] [blame] | 1478 | isInsSubReg = true; |
| 1479 | if (SrcIsPhys) { |
| 1480 | if (!CanJoinInsertSubRegToPhysReg(DstReg, SrcReg, SubIdx, RealSrcReg)) |
Evan Cheng | 8c08d8c | 2009-01-23 02:15:19 +0000 | [diff] [blame] | 1481 | return false; // Not coalescable |
| 1482 | SubIdx = 0; |
| 1483 | } |
Dan Gohman | 97121ba | 2009-04-08 00:15:30 +0000 | [diff] [blame] | 1484 | } else { |
| 1485 | SubIdx = SrcMO->getSubReg(); |
| 1486 | if (SubIdx) { |
| 1487 | // This is not a extract_subreg but it looks like one. |
Evan Cheng | aa809fb | 2009-04-23 20:39:31 +0000 | [diff] [blame] | 1488 | // e.g. %cl = MOV16rr %reg1024:1 |
Dan Gohman | 97121ba | 2009-04-08 00:15:30 +0000 | [diff] [blame] | 1489 | isExtSubReg = true; |
| 1490 | if (DstIsPhys) { |
| 1491 | if (!CanJoinExtractSubRegToPhysReg(DstReg, SrcReg, SubIdx,RealDstReg)) |
| 1492 | return false; // Not coalescable |
| 1493 | SubIdx = 0; |
| 1494 | } |
| 1495 | } |
Evan Cheng | 8c08d8c | 2009-01-23 02:15:19 +0000 | [diff] [blame] | 1496 | } |
| 1497 | |
Evan Cheng | 8c08d8c | 2009-01-23 02:15:19 +0000 | [diff] [blame] | 1498 | unsigned LargeReg = SrcReg; |
| 1499 | unsigned SmallReg = DstReg; |
Evan Cheng | 8c08d8c | 2009-01-23 02:15:19 +0000 | [diff] [blame] | 1500 | |
| 1501 | // Now determine the register class of the joined register. |
| 1502 | if (isExtSubReg) { |
| 1503 | if (SubIdx && DstRC && DstRC->isASubClass()) { |
| 1504 | // This is a move to a sub-register class. However, the source is a |
| 1505 | // sub-register of a larger register class. We don't know what should |
| 1506 | // the register class be. FIXME. |
| 1507 | Again = true; |
| 1508 | return false; |
| 1509 | } |
Evan Cheng | 5248468 | 2009-07-18 02:10:10 +0000 | [diff] [blame] | 1510 | if (!DstIsPhys && !SrcIsPhys) |
| 1511 | NewRC = SrcRC; |
Evan Cheng | c2cee14 | 2009-04-23 20:18:13 +0000 | [diff] [blame] | 1512 | } else if (!SrcIsPhys && !DstIsPhys) { |
Jakob Stoklund Olesen | 3a155f0 | 2009-04-30 21:24:03 +0000 | [diff] [blame] | 1513 | NewRC = getCommonSubClass(SrcRC, DstRC); |
| 1514 | if (!NewRC) { |
Daniel Dunbar | ce63ffb | 2009-07-25 00:23:56 +0000 | [diff] [blame] | 1515 | DEBUG(errs() << "\tDisjoint regclasses: " |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 1516 | << SrcRC->getName() << ", " |
| 1517 | << DstRC->getName() << ".\n"); |
Jakob Stoklund Olesen | 3a155f0 | 2009-04-30 21:24:03 +0000 | [diff] [blame] | 1518 | return false; // Not coalescable. |
Evan Cheng | 8c08d8c | 2009-01-23 02:15:19 +0000 | [diff] [blame] | 1519 | } |
Jakob Stoklund Olesen | 3a155f0 | 2009-04-30 21:24:03 +0000 | [diff] [blame] | 1520 | if (DstRC->getSize() > SrcRC->getSize()) |
| 1521 | std::swap(LargeReg, SmallReg); |
Evan Cheng | 8c08d8c | 2009-01-23 02:15:19 +0000 | [diff] [blame] | 1522 | } |
| 1523 | |
Evan Cheng | c16d37e | 2009-01-23 05:48:59 +0000 | [diff] [blame] | 1524 | // If we are joining two virtual registers and the resulting register |
| 1525 | // class is more restrictive (fewer register, smaller size). Check if it's |
| 1526 | // worth doing the merge. |
Evan Cheng | 8c08d8c | 2009-01-23 02:15:19 +0000 | [diff] [blame] | 1527 | if (!SrcIsPhys && !DstIsPhys && |
Evan Cheng | c16d37e | 2009-01-23 05:48:59 +0000 | [diff] [blame] | 1528 | (isExtSubReg || DstRC->isASubClass()) && |
| 1529 | !isWinToJoinCrossClass(LargeReg, SmallReg, |
| 1530 | allocatableRCRegs_[NewRC].count())) { |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 1531 | DEBUG(errs() << "\tSrc/Dest are different register classes.\n"); |
Evan Cheng | e00f5de | 2008-06-19 01:39:21 +0000 | [diff] [blame] | 1532 | // Allow the coalescer to try again in case either side gets coalesced to |
| 1533 | // a physical register that's compatible with the other side. e.g. |
| 1534 | // r1024 = MOV32to32_ r1025 |
Evan Cheng | 8c08d8c | 2009-01-23 02:15:19 +0000 | [diff] [blame] | 1535 | // But later r1024 is assigned EAX then r1025 may be coalesced with EAX. |
Evan Cheng | e00f5de | 2008-06-19 01:39:21 +0000 | [diff] [blame] | 1536 | Again = true; // May be possible to coalesce later. |
| 1537 | return false; |
| 1538 | } |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1539 | } |
Evan Cheng | 8db8668 | 2008-09-11 20:07:10 +0000 | [diff] [blame] | 1540 | |
| 1541 | // Will it create illegal extract_subreg / insert_subreg? |
| 1542 | if (SrcIsPhys && HasIncompatibleSubRegDefUse(CopyMI, DstReg, SrcReg)) |
| 1543 | return false; |
| 1544 | if (DstIsPhys && HasIncompatibleSubRegDefUse(CopyMI, SrcReg, DstReg)) |
| 1545 | return false; |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 1546 | |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 1547 | LiveInterval &SrcInt = li_->getInterval(SrcReg); |
| 1548 | LiveInterval &DstInt = li_->getInterval(DstReg); |
| 1549 | assert(SrcInt.reg == SrcReg && DstInt.reg == DstReg && |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1550 | "Register mapping is horribly broken!"); |
| 1551 | |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 1552 | DEBUG({ |
| 1553 | errs() << "\t\tInspecting "; SrcInt.print(errs(), tri_); |
| 1554 | errs() << " and "; DstInt.print(errs(), tri_); |
| 1555 | errs() << ": "; |
| 1556 | }); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1557 | |
Evan Cheng | 0a1fcce | 2009-02-08 11:04:35 +0000 | [diff] [blame] | 1558 | // Save a copy of the virtual register live interval. We'll manually |
| 1559 | // merge this into the "real" physical register live interval this is |
| 1560 | // coalesced with. |
| 1561 | LiveInterval *SavedLI = 0; |
| 1562 | if (RealDstReg) |
| 1563 | SavedLI = li_->dupInterval(&SrcInt); |
| 1564 | else if (RealSrcReg) |
| 1565 | SavedLI = li_->dupInterval(&DstInt); |
| 1566 | |
Evan Cheng | 3c88d74 | 2008-03-18 08:26:47 +0000 | [diff] [blame] | 1567 | // Check if it is necessary to propagate "isDead" property. |
Dan Gohman | 97121ba | 2009-04-08 00:15:30 +0000 | [diff] [blame] | 1568 | if (!isExtSubReg && !isInsSubReg && !isSubRegToReg) { |
Evan Cheng | 7e073ba | 2008-04-09 20:57:25 +0000 | [diff] [blame] | 1569 | MachineOperand *mopd = CopyMI->findRegisterDefOperand(DstReg, false); |
| 1570 | bool isDead = mopd->isDead(); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1571 | |
Evan Cheng | 7e073ba | 2008-04-09 20:57:25 +0000 | [diff] [blame] | 1572 | // We need to be careful about coalescing a source physical register with a |
| 1573 | // virtual register. Once the coalescing is done, it cannot be broken and |
| 1574 | // these are not spillable! If the destination interval uses are far away, |
| 1575 | // think twice about coalescing them! |
| 1576 | if (!isDead && (SrcIsPhys || DstIsPhys)) { |
Evan Cheng | 0490dcb | 2009-04-30 18:39:57 +0000 | [diff] [blame] | 1577 | // If the copy is in a loop, take care not to coalesce aggressively if the |
| 1578 | // src is coming in from outside the loop (or the dst is out of the loop). |
| 1579 | // If it's not in a loop, then determine whether to join them base purely |
| 1580 | // by the length of the interval. |
| 1581 | if (PhysJoinTweak) { |
| 1582 | if (SrcIsPhys) { |
| 1583 | if (!isWinToJoinVRWithSrcPhysReg(CopyMI, CopyMBB, DstInt, SrcInt)) { |
Evan Cheng | 358dec5 | 2009-06-15 08:28:29 +0000 | [diff] [blame] | 1584 | mri_->setRegAllocationHint(DstInt.reg, 0, SrcReg); |
Evan Cheng | 0490dcb | 2009-04-30 18:39:57 +0000 | [diff] [blame] | 1585 | ++numAborts; |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 1586 | DEBUG(errs() << "\tMay tie down a physical register, abort!\n"); |
Evan Cheng | 0490dcb | 2009-04-30 18:39:57 +0000 | [diff] [blame] | 1587 | Again = true; // May be possible to coalesce later. |
| 1588 | return false; |
| 1589 | } |
| 1590 | } else { |
| 1591 | if (!isWinToJoinVRWithDstPhysReg(CopyMI, CopyMBB, DstInt, SrcInt)) { |
Evan Cheng | 358dec5 | 2009-06-15 08:28:29 +0000 | [diff] [blame] | 1592 | mri_->setRegAllocationHint(SrcInt.reg, 0, DstReg); |
Evan Cheng | 0490dcb | 2009-04-30 18:39:57 +0000 | [diff] [blame] | 1593 | ++numAborts; |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 1594 | DEBUG(errs() << "\tMay tie down a physical register, abort!\n"); |
Evan Cheng | 0490dcb | 2009-04-30 18:39:57 +0000 | [diff] [blame] | 1595 | Again = true; // May be possible to coalesce later. |
| 1596 | return false; |
| 1597 | } |
| 1598 | } |
| 1599 | } else { |
| 1600 | // If the virtual register live interval is long but it has low use desity, |
| 1601 | // do not join them, instead mark the physical register as its allocation |
| 1602 | // preference. |
| 1603 | LiveInterval &JoinVInt = SrcIsPhys ? DstInt : SrcInt; |
| 1604 | unsigned JoinVReg = SrcIsPhys ? DstReg : SrcReg; |
| 1605 | unsigned JoinPReg = SrcIsPhys ? SrcReg : DstReg; |
| 1606 | const TargetRegisterClass *RC = mri_->getRegClass(JoinVReg); |
| 1607 | unsigned Threshold = allocatableRCRegs_[RC].count() * 2; |
Evan Cheng | 0490dcb | 2009-04-30 18:39:57 +0000 | [diff] [blame] | 1608 | unsigned Length = li_->getApproximateInstructionCount(JoinVInt); |
| 1609 | float Ratio = 1.0 / Threshold; |
| 1610 | if (Length > Threshold && |
| 1611 | (((float)std::distance(mri_->use_begin(JoinVReg), |
| 1612 | mri_->use_end()) / Length) < Ratio)) { |
Evan Cheng | 358dec5 | 2009-06-15 08:28:29 +0000 | [diff] [blame] | 1613 | mri_->setRegAllocationHint(JoinVInt.reg, 0, JoinPReg); |
Evan Cheng | 0490dcb | 2009-04-30 18:39:57 +0000 | [diff] [blame] | 1614 | ++numAborts; |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 1615 | DEBUG(errs() << "\tMay tie down a physical register, abort!\n"); |
Evan Cheng | 0490dcb | 2009-04-30 18:39:57 +0000 | [diff] [blame] | 1616 | Again = true; // May be possible to coalesce later. |
| 1617 | return false; |
| 1618 | } |
Evan Cheng | 7e073ba | 2008-04-09 20:57:25 +0000 | [diff] [blame] | 1619 | } |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1620 | } |
| 1621 | } |
| 1622 | |
| 1623 | // Okay, attempt to join these two intervals. On failure, this returns false. |
| 1624 | // Otherwise, if one of the intervals being joined is a physreg, this method |
| 1625 | // always canonicalizes DstInt to be it. The output "SrcInt" will not have |
| 1626 | // been modified, so we can use this information below to update aliases. |
Evan Cheng | 1a66f0a | 2007-08-28 08:28:51 +0000 | [diff] [blame] | 1627 | bool Swapped = false; |
Evan Cheng | db9b1c3 | 2008-04-03 16:41:54 +0000 | [diff] [blame] | 1628 | // If SrcInt is implicitly defined, it's safe to coalesce. |
| 1629 | bool isEmpty = SrcInt.empty(); |
Evan Cheng | 7e073ba | 2008-04-09 20:57:25 +0000 | [diff] [blame] | 1630 | if (isEmpty && !CanCoalesceWithImpDef(CopyMI, DstInt, SrcInt)) { |
Evan Cheng | db9b1c3 | 2008-04-03 16:41:54 +0000 | [diff] [blame] | 1631 | // Only coalesce an empty interval (defined by implicit_def) with |
Evan Cheng | 7e073ba | 2008-04-09 20:57:25 +0000 | [diff] [blame] | 1632 | // another interval which has a valno defined by the CopyMI and the CopyMI |
| 1633 | // is a kill of the implicit def. |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 1634 | DEBUG(errs() << "Not profitable!\n"); |
Evan Cheng | db9b1c3 | 2008-04-03 16:41:54 +0000 | [diff] [blame] | 1635 | return false; |
| 1636 | } |
| 1637 | |
| 1638 | if (!isEmpty && !JoinIntervals(DstInt, SrcInt, Swapped)) { |
Gabor Greif | e510b3a | 2007-07-09 12:00:59 +0000 | [diff] [blame] | 1639 | // Coalescing failed. |
Evan Cheng | cd04708 | 2008-08-30 09:09:33 +0000 | [diff] [blame] | 1640 | |
| 1641 | // If definition of source is defined by trivial computation, try |
| 1642 | // rematerializing it. |
Dan Gohman | 97121ba | 2009-04-08 00:15:30 +0000 | [diff] [blame] | 1643 | if (!isExtSubReg && !isInsSubReg && !isSubRegToReg && |
Evan Cheng | 3784453 | 2009-07-16 09:20:10 +0000 | [diff] [blame] | 1644 | ReMaterializeTrivialDef(SrcInt, DstReg, DstSubIdx, CopyMI)) |
Evan Cheng | cd04708 | 2008-08-30 09:09:33 +0000 | [diff] [blame] | 1645 | return true; |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 1646 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1647 | // If we can eliminate the copy without merging the live ranges, do so now. |
Dan Gohman | 97121ba | 2009-04-08 00:15:30 +0000 | [diff] [blame] | 1648 | if (!isExtSubReg && !isInsSubReg && !isSubRegToReg && |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 1649 | (AdjustCopiesBackFrom(SrcInt, DstInt, CopyMI) || |
| 1650 | RemoveCopyByCommutingDef(SrcInt, DstInt, CopyMI))) { |
Evan Cheng | 8fc9a10 | 2007-11-06 08:52:21 +0000 | [diff] [blame] | 1651 | JoinedCopies.insert(CopyMI); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1652 | return true; |
Evan Cheng | 8fc9a10 | 2007-11-06 08:52:21 +0000 | [diff] [blame] | 1653 | } |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 1654 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1655 | // Otherwise, we are unable to join the intervals. |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 1656 | DEBUG(errs() << "Interference!\n"); |
Evan Cheng | 0547bab | 2007-11-01 06:22:48 +0000 | [diff] [blame] | 1657 | Again = true; // May be possible to coalesce later. |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1658 | return false; |
| 1659 | } |
| 1660 | |
Evan Cheng | 1a66f0a | 2007-08-28 08:28:51 +0000 | [diff] [blame] | 1661 | LiveInterval *ResSrcInt = &SrcInt; |
| 1662 | LiveInterval *ResDstInt = &DstInt; |
| 1663 | if (Swapped) { |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 1664 | std::swap(SrcReg, DstReg); |
Evan Cheng | 1a66f0a | 2007-08-28 08:28:51 +0000 | [diff] [blame] | 1665 | std::swap(ResSrcInt, ResDstInt); |
| 1666 | } |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 1667 | assert(TargetRegisterInfo::isVirtualRegister(SrcReg) && |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1668 | "LiveInterval::join didn't work right!"); |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 1669 | |
Evan Cheng | 8f90b6e | 2009-01-07 02:08:57 +0000 | [diff] [blame] | 1670 | // If we're about to merge live ranges into a physical register live interval, |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1671 | // we have to update any aliased register's live ranges to indicate that they |
| 1672 | // have clobbered values for this range. |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 1673 | if (TargetRegisterInfo::isPhysicalRegister(DstReg)) { |
Evan Cheng | 32dfbea | 2007-10-12 08:50:34 +0000 | [diff] [blame] | 1674 | // If this is a extract_subreg where dst is a physical register, e.g. |
| 1675 | // cl = EXTRACT_SUBREG reg1024, 1 |
| 1676 | // then create and update the actual physical register allocated to RHS. |
Evan Cheng | 7e073ba | 2008-04-09 20:57:25 +0000 | [diff] [blame] | 1677 | if (RealDstReg || RealSrcReg) { |
| 1678 | LiveInterval &RealInt = |
| 1679 | li_->getOrCreateInterval(RealDstReg ? RealDstReg : RealSrcReg); |
Evan Cheng | 0a1fcce | 2009-02-08 11:04:35 +0000 | [diff] [blame] | 1680 | for (LiveInterval::const_vni_iterator I = SavedLI->vni_begin(), |
| 1681 | E = SavedLI->vni_end(); I != E; ++I) { |
| 1682 | const VNInfo *ValNo = *I; |
Lang Hames | 52c1afc | 2009-08-10 23:43:28 +0000 | [diff] [blame] | 1683 | VNInfo *NewValNo = RealInt.getNextValue(ValNo->def, ValNo->getCopy(), |
Lang Hames | 857c4e0 | 2009-06-17 21:01:20 +0000 | [diff] [blame] | 1684 | false, // updated at * |
Evan Cheng | 0a1fcce | 2009-02-08 11:04:35 +0000 | [diff] [blame] | 1685 | li_->getVNInfoAllocator()); |
Lang Hames | 857c4e0 | 2009-06-17 21:01:20 +0000 | [diff] [blame] | 1686 | NewValNo->setFlags(ValNo->getFlags()); // * updated here. |
Evan Cheng | 0a1fcce | 2009-02-08 11:04:35 +0000 | [diff] [blame] | 1687 | RealInt.addKills(NewValNo, ValNo->kills); |
| 1688 | RealInt.MergeValueInAsValue(*SavedLI, ValNo, NewValNo); |
Evan Cheng | 3472925 | 2007-10-14 10:08:34 +0000 | [diff] [blame] | 1689 | } |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 1690 | RealInt.weight += SavedLI->weight; |
Evan Cheng | 7e073ba | 2008-04-09 20:57:25 +0000 | [diff] [blame] | 1691 | DstReg = RealDstReg ? RealDstReg : RealSrcReg; |
Evan Cheng | 32dfbea | 2007-10-12 08:50:34 +0000 | [diff] [blame] | 1692 | } |
| 1693 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1694 | // Update the liveintervals of sub-registers. |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 1695 | for (const unsigned *AS = tri_->getSubRegisters(DstReg); *AS; ++AS) |
Evan Cheng | 32dfbea | 2007-10-12 08:50:34 +0000 | [diff] [blame] | 1696 | li_->getOrCreateInterval(*AS).MergeInClobberRanges(*ResSrcInt, |
Evan Cheng | f3bb2e6 | 2007-09-05 21:46:51 +0000 | [diff] [blame] | 1697 | li_->getVNInfoAllocator()); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1698 | } |
| 1699 | |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 1700 | // If this is a EXTRACT_SUBREG, make sure the result of coalescing is the |
| 1701 | // larger super-register. |
Dan Gohman | 97121ba | 2009-04-08 00:15:30 +0000 | [diff] [blame] | 1702 | if ((isExtSubReg || isInsSubReg || isSubRegToReg) && |
| 1703 | !SrcIsPhys && !DstIsPhys) { |
| 1704 | if ((isExtSubReg && !Swapped) || |
| 1705 | ((isInsSubReg || isSubRegToReg) && Swapped)) { |
Evan Cheng | 90f95f8 | 2009-06-14 20:22:55 +0000 | [diff] [blame] | 1706 | ResSrcInt->Copy(*ResDstInt, mri_, li_->getVNInfoAllocator()); |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 1707 | std::swap(SrcReg, DstReg); |
Evan Cheng | 32dfbea | 2007-10-12 08:50:34 +0000 | [diff] [blame] | 1708 | std::swap(ResSrcInt, ResDstInt); |
| 1709 | } |
Evan Cheng | 32dfbea | 2007-10-12 08:50:34 +0000 | [diff] [blame] | 1710 | } |
| 1711 | |
Evan Cheng | e00f5de | 2008-06-19 01:39:21 +0000 | [diff] [blame] | 1712 | // Coalescing to a virtual register that is of a sub-register class of the |
| 1713 | // other. Make sure the resulting register is set to the right register class. |
Evan Cheng | 5248468 | 2009-07-18 02:10:10 +0000 | [diff] [blame] | 1714 | if (CrossRC) |
| 1715 | ++numCrossRCs; |
| 1716 | |
| 1717 | // This may happen even if it's cross-rc coalescing. e.g. |
| 1718 | // %reg1026<def> = SUBREG_TO_REG 0, %reg1037<kill>, 4 |
| 1719 | // reg1026 -> GR64, reg1037 -> GR32_ABCD. The resulting register will have to |
| 1720 | // be allocate a register from GR64_ABCD. |
| 1721 | if (NewRC) |
| 1722 | mri_->setRegClass(DstReg, NewRC); |
Evan Cheng | e00f5de | 2008-06-19 01:39:21 +0000 | [diff] [blame] | 1723 | |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 1724 | // Remember to delete the copy instruction. |
Evan Cheng | 8fc9a10 | 2007-11-06 08:52:21 +0000 | [diff] [blame] | 1725 | JoinedCopies.insert(CopyMI); |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 1726 | |
Evan Cheng | 4ff3f1c | 2008-03-10 08:11:32 +0000 | [diff] [blame] | 1727 | // Some live range has been lengthened due to colaescing, eliminate the |
| 1728 | // unnecessary kills. |
| 1729 | RemoveUnnecessaryKills(SrcReg, *ResDstInt); |
| 1730 | if (TargetRegisterInfo::isVirtualRegister(DstReg)) |
| 1731 | RemoveUnnecessaryKills(DstReg, *ResDstInt); |
| 1732 | |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 1733 | UpdateRegDefsUses(SrcReg, DstReg, SubIdx); |
| 1734 | |
Evan Cheng | cd04708 | 2008-08-30 09:09:33 +0000 | [diff] [blame] | 1735 | // SrcReg is guarateed to be the register whose live interval that is |
| 1736 | // being merged. |
| 1737 | li_->removeInterval(SrcReg); |
| 1738 | |
Evan Cheng | f9f1da1 | 2009-06-18 02:04:01 +0000 | [diff] [blame] | 1739 | // Update regalloc hint. |
| 1740 | tri_->UpdateRegAllocHint(SrcReg, DstReg, *mf_); |
| 1741 | |
Evan Cheng | 0a1fcce | 2009-02-08 11:04:35 +0000 | [diff] [blame] | 1742 | // Manually deleted the live interval copy. |
| 1743 | if (SavedLI) { |
| 1744 | SavedLI->clear(); |
| 1745 | delete SavedLI; |
| 1746 | } |
| 1747 | |
Evan Cheng | 3ef2d60 | 2008-09-09 21:44:23 +0000 | [diff] [blame] | 1748 | // If resulting interval has a preference that no longer fits because of subreg |
| 1749 | // coalescing, just clear the preference. |
Evan Cheng | 90f95f8 | 2009-06-14 20:22:55 +0000 | [diff] [blame] | 1750 | unsigned Preference = getRegAllocPreference(ResDstInt->reg, *mf_, mri_, tri_); |
| 1751 | if (Preference && (isExtSubReg || isInsSubReg || isSubRegToReg) && |
Evan Cheng | 4086906 | 2008-09-11 18:40:32 +0000 | [diff] [blame] | 1752 | TargetRegisterInfo::isVirtualRegister(ResDstInt->reg)) { |
Evan Cheng | 3ef2d60 | 2008-09-09 21:44:23 +0000 | [diff] [blame] | 1753 | const TargetRegisterClass *RC = mri_->getRegClass(ResDstInt->reg); |
Evan Cheng | 90f95f8 | 2009-06-14 20:22:55 +0000 | [diff] [blame] | 1754 | if (!RC->contains(Preference)) |
Evan Cheng | 358dec5 | 2009-06-15 08:28:29 +0000 | [diff] [blame] | 1755 | mri_->setRegAllocationHint(ResDstInt->reg, 0, 0); |
Evan Cheng | 3ef2d60 | 2008-09-09 21:44:23 +0000 | [diff] [blame] | 1756 | } |
| 1757 | |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 1758 | DEBUG({ |
| 1759 | errs() << "\n\t\tJoined. Result = "; |
| 1760 | ResDstInt->print(errs(), tri_); |
| 1761 | errs() << "\n"; |
| 1762 | }); |
Evan Cheng | db9b1c3 | 2008-04-03 16:41:54 +0000 | [diff] [blame] | 1763 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1764 | ++numJoins; |
| 1765 | return true; |
| 1766 | } |
| 1767 | |
| 1768 | /// ComputeUltimateVN - Assuming we are going to join two live intervals, |
| 1769 | /// compute what the resultant value numbers for each value in the input two |
| 1770 | /// ranges will be. This is complicated by copies between the two which can |
| 1771 | /// and will commonly cause multiple value numbers to be merged into one. |
| 1772 | /// |
| 1773 | /// VN is the value number that we're trying to resolve. InstDefiningValue |
| 1774 | /// keeps track of the new InstDefiningValue assignment for the result |
| 1775 | /// LiveInterval. ThisFromOther/OtherFromThis are sets that keep track of |
| 1776 | /// whether a value in this or other is a copy from the opposite set. |
| 1777 | /// ThisValNoAssignments/OtherValNoAssignments keep track of value #'s that have |
| 1778 | /// already been assigned. |
| 1779 | /// |
| 1780 | /// ThisFromOther[x] - If x is defined as a copy from the other interval, this |
| 1781 | /// contains the value number the copy is from. |
| 1782 | /// |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 1783 | static unsigned ComputeUltimateVN(VNInfo *VNI, |
| 1784 | SmallVector<VNInfo*, 16> &NewVNInfo, |
Evan Cheng | fadfb5b | 2007-08-31 21:23:06 +0000 | [diff] [blame] | 1785 | DenseMap<VNInfo*, VNInfo*> &ThisFromOther, |
| 1786 | DenseMap<VNInfo*, VNInfo*> &OtherFromThis, |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1787 | SmallVector<int, 16> &ThisValNoAssignments, |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 1788 | SmallVector<int, 16> &OtherValNoAssignments) { |
| 1789 | unsigned VN = VNI->id; |
| 1790 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1791 | // If the VN has already been computed, just return it. |
| 1792 | if (ThisValNoAssignments[VN] >= 0) |
| 1793 | return ThisValNoAssignments[VN]; |
| 1794 | // assert(ThisValNoAssignments[VN] != -2 && "Cyclic case?"); |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 1795 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1796 | // If this val is not a copy from the other val, then it must be a new value |
| 1797 | // number in the destination. |
Evan Cheng | fadfb5b | 2007-08-31 21:23:06 +0000 | [diff] [blame] | 1798 | DenseMap<VNInfo*, VNInfo*>::iterator I = ThisFromOther.find(VNI); |
Evan Cheng | c14b144 | 2007-08-31 08:04:17 +0000 | [diff] [blame] | 1799 | if (I == ThisFromOther.end()) { |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 1800 | NewVNInfo.push_back(VNI); |
| 1801 | return ThisValNoAssignments[VN] = NewVNInfo.size()-1; |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1802 | } |
Evan Cheng | c14b144 | 2007-08-31 08:04:17 +0000 | [diff] [blame] | 1803 | VNInfo *OtherValNo = I->second; |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1804 | |
| 1805 | // Otherwise, this *is* a copy from the RHS. If the other side has already |
| 1806 | // been computed, return it. |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 1807 | if (OtherValNoAssignments[OtherValNo->id] >= 0) |
| 1808 | return ThisValNoAssignments[VN] = OtherValNoAssignments[OtherValNo->id]; |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 1809 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1810 | // Mark this value number as currently being computed, then ask what the |
| 1811 | // ultimate value # of the other value is. |
| 1812 | ThisValNoAssignments[VN] = -2; |
| 1813 | unsigned UltimateVN = |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 1814 | ComputeUltimateVN(OtherValNo, NewVNInfo, OtherFromThis, ThisFromOther, |
| 1815 | OtherValNoAssignments, ThisValNoAssignments); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1816 | return ThisValNoAssignments[VN] = UltimateVN; |
| 1817 | } |
| 1818 | |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 1819 | static bool InVector(VNInfo *Val, const SmallVector<VNInfo*, 8> &V) { |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1820 | return std::find(V.begin(), V.end(), Val) != V.end(); |
| 1821 | } |
| 1822 | |
Evan Cheng | 7e073ba | 2008-04-09 20:57:25 +0000 | [diff] [blame] | 1823 | /// RangeIsDefinedByCopyFromReg - Return true if the specified live range of |
| 1824 | /// the specified live interval is defined by a copy from the specified |
| 1825 | /// register. |
| 1826 | bool SimpleRegisterCoalescing::RangeIsDefinedByCopyFromReg(LiveInterval &li, |
| 1827 | LiveRange *LR, |
| 1828 | unsigned Reg) { |
| 1829 | unsigned SrcReg = li_->getVNInfoSourceReg(LR->valno); |
| 1830 | if (SrcReg == Reg) |
| 1831 | return true; |
Lang Hames | 857c4e0 | 2009-06-17 21:01:20 +0000 | [diff] [blame] | 1832 | // FIXME: Do isPHIDef and isDefAccurate both need to be tested? |
| 1833 | if ((LR->valno->isPHIDef() || !LR->valno->isDefAccurate()) && |
Evan Cheng | 7e073ba | 2008-04-09 20:57:25 +0000 | [diff] [blame] | 1834 | TargetRegisterInfo::isPhysicalRegister(li.reg) && |
| 1835 | *tri_->getSuperRegisters(li.reg)) { |
| 1836 | // It's a sub-register live interval, we may not have precise information. |
| 1837 | // Re-compute it. |
| 1838 | MachineInstr *DefMI = li_->getInstructionFromIndex(LR->start); |
Evan Cheng | 04ee5a1 | 2009-01-20 19:12:24 +0000 | [diff] [blame] | 1839 | unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; |
| 1840 | if (DefMI && |
| 1841 | tii_->isMoveInstr(*DefMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) && |
Evan Cheng | 7e073ba | 2008-04-09 20:57:25 +0000 | [diff] [blame] | 1842 | DstReg == li.reg && SrcReg == Reg) { |
| 1843 | // Cache computed info. |
| 1844 | LR->valno->def = LR->start; |
Lang Hames | 52c1afc | 2009-08-10 23:43:28 +0000 | [diff] [blame] | 1845 | LR->valno->setCopy(DefMI); |
Evan Cheng | 7e073ba | 2008-04-09 20:57:25 +0000 | [diff] [blame] | 1846 | return true; |
| 1847 | } |
| 1848 | } |
| 1849 | return false; |
| 1850 | } |
| 1851 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1852 | /// SimpleJoin - Attempt to joint the specified interval into this one. The |
| 1853 | /// caller of this method must guarantee that the RHS only contains a single |
| 1854 | /// value number and that the RHS is not defined by a copy from this |
| 1855 | /// interval. This returns false if the intervals are not joinable, or it |
| 1856 | /// joins them and returns true. |
Bill Wendling | 2674d71 | 2008-01-04 08:59:18 +0000 | [diff] [blame] | 1857 | bool SimpleRegisterCoalescing::SimpleJoin(LiveInterval &LHS, LiveInterval &RHS){ |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1858 | assert(RHS.containsOneValue()); |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 1859 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1860 | // Some number (potentially more than one) value numbers in the current |
| 1861 | // interval may be defined as copies from the RHS. Scan the overlapping |
| 1862 | // portions of the LHS and RHS, keeping track of this and looking for |
| 1863 | // overlapping live ranges that are NOT defined as copies. If these exist, we |
Gabor Greif | e510b3a | 2007-07-09 12:00:59 +0000 | [diff] [blame] | 1864 | // cannot coalesce. |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 1865 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1866 | LiveInterval::iterator LHSIt = LHS.begin(), LHSEnd = LHS.end(); |
| 1867 | LiveInterval::iterator RHSIt = RHS.begin(), RHSEnd = RHS.end(); |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 1868 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1869 | if (LHSIt->start < RHSIt->start) { |
| 1870 | LHSIt = std::upper_bound(LHSIt, LHSEnd, RHSIt->start); |
| 1871 | if (LHSIt != LHS.begin()) --LHSIt; |
| 1872 | } else if (RHSIt->start < LHSIt->start) { |
| 1873 | RHSIt = std::upper_bound(RHSIt, RHSEnd, LHSIt->start); |
| 1874 | if (RHSIt != RHS.begin()) --RHSIt; |
| 1875 | } |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 1876 | |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 1877 | SmallVector<VNInfo*, 8> EliminatedLHSVals; |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 1878 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1879 | while (1) { |
| 1880 | // Determine if these live intervals overlap. |
| 1881 | bool Overlaps = false; |
| 1882 | if (LHSIt->start <= RHSIt->start) |
| 1883 | Overlaps = LHSIt->end > RHSIt->start; |
| 1884 | else |
| 1885 | Overlaps = RHSIt->end > LHSIt->start; |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 1886 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1887 | // If the live intervals overlap, there are two interesting cases: if the |
| 1888 | // LHS interval is defined by a copy from the RHS, it's ok and we record |
| 1889 | // that the LHS value # is the same as the RHS. If it's not, then we cannot |
Gabor Greif | e510b3a | 2007-07-09 12:00:59 +0000 | [diff] [blame] | 1890 | // coalesce these live ranges and we bail out. |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1891 | if (Overlaps) { |
| 1892 | // If we haven't already recorded that this value # is safe, check it. |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 1893 | if (!InVector(LHSIt->valno, EliminatedLHSVals)) { |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1894 | // Copy from the RHS? |
Evan Cheng | 7e073ba | 2008-04-09 20:57:25 +0000 | [diff] [blame] | 1895 | if (!RangeIsDefinedByCopyFromReg(LHS, LHSIt, RHS.reg)) |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1896 | return false; // Nope, bail out. |
Evan Cheng | f4ea510 | 2008-05-21 22:34:12 +0000 | [diff] [blame] | 1897 | |
| 1898 | if (LHSIt->contains(RHSIt->valno->def)) |
| 1899 | // Here is an interesting situation: |
| 1900 | // BB1: |
| 1901 | // vr1025 = copy vr1024 |
| 1902 | // .. |
| 1903 | // BB2: |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 1904 | // vr1024 = op |
Evan Cheng | f4ea510 | 2008-05-21 22:34:12 +0000 | [diff] [blame] | 1905 | // = vr1025 |
| 1906 | // Even though vr1025 is copied from vr1024, it's not safe to |
Bill Wendling | 430d423 | 2009-03-30 20:30:02 +0000 | [diff] [blame] | 1907 | // coalesce them since the live range of vr1025 intersects the |
Evan Cheng | f4ea510 | 2008-05-21 22:34:12 +0000 | [diff] [blame] | 1908 | // def of vr1024. This happens because vr1025 is assigned the |
| 1909 | // value of the previous iteration of vr1024. |
| 1910 | return false; |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 1911 | EliminatedLHSVals.push_back(LHSIt->valno); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1912 | } |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 1913 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1914 | // We know this entire LHS live range is okay, so skip it now. |
| 1915 | if (++LHSIt == LHSEnd) break; |
| 1916 | continue; |
| 1917 | } |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 1918 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1919 | if (LHSIt->end < RHSIt->end) { |
| 1920 | if (++LHSIt == LHSEnd) break; |
| 1921 | } else { |
| 1922 | // One interesting case to check here. It's possible that we have |
| 1923 | // something like "X3 = Y" which defines a new value number in the LHS, |
| 1924 | // and is the last use of this liverange of the RHS. In this case, we |
Gabor Greif | e510b3a | 2007-07-09 12:00:59 +0000 | [diff] [blame] | 1925 | // want to notice this copy (so that it gets coalesced away) even though |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1926 | // the live ranges don't actually overlap. |
| 1927 | if (LHSIt->start == RHSIt->end) { |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 1928 | if (InVector(LHSIt->valno, EliminatedLHSVals)) { |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1929 | // We already know that this value number is going to be merged in |
Gabor Greif | e510b3a | 2007-07-09 12:00:59 +0000 | [diff] [blame] | 1930 | // if coalescing succeeds. Just skip the liverange. |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1931 | if (++LHSIt == LHSEnd) break; |
| 1932 | } else { |
| 1933 | // Otherwise, if this is a copy from the RHS, mark it as being merged |
| 1934 | // in. |
Evan Cheng | 7e073ba | 2008-04-09 20:57:25 +0000 | [diff] [blame] | 1935 | if (RangeIsDefinedByCopyFromReg(LHS, LHSIt, RHS.reg)) { |
Evan Cheng | f4ea510 | 2008-05-21 22:34:12 +0000 | [diff] [blame] | 1936 | if (LHSIt->contains(RHSIt->valno->def)) |
| 1937 | // Here is an interesting situation: |
| 1938 | // BB1: |
| 1939 | // vr1025 = copy vr1024 |
| 1940 | // .. |
| 1941 | // BB2: |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 1942 | // vr1024 = op |
Evan Cheng | f4ea510 | 2008-05-21 22:34:12 +0000 | [diff] [blame] | 1943 | // = vr1025 |
| 1944 | // Even though vr1025 is copied from vr1024, it's not safe to |
| 1945 | // coalesced them since live range of vr1025 intersects the |
| 1946 | // def of vr1024. This happens because vr1025 is assigned the |
| 1947 | // value of the previous iteration of vr1024. |
| 1948 | return false; |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 1949 | EliminatedLHSVals.push_back(LHSIt->valno); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1950 | |
| 1951 | // We know this entire LHS live range is okay, so skip it now. |
| 1952 | if (++LHSIt == LHSEnd) break; |
| 1953 | } |
| 1954 | } |
| 1955 | } |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 1956 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1957 | if (++RHSIt == RHSEnd) break; |
| 1958 | } |
| 1959 | } |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 1960 | |
Gabor Greif | e510b3a | 2007-07-09 12:00:59 +0000 | [diff] [blame] | 1961 | // If we got here, we know that the coalescing will be successful and that |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1962 | // the value numbers in EliminatedLHSVals will all be merged together. Since |
| 1963 | // the most common case is that EliminatedLHSVals has a single number, we |
| 1964 | // optimize for it: if there is more than one value, we merge them all into |
| 1965 | // the lowest numbered one, then handle the interval as if we were merging |
| 1966 | // with one value number. |
Devang Patel | 8a84e44 | 2009-01-05 17:31:22 +0000 | [diff] [blame] | 1967 | VNInfo *LHSValNo = NULL; |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1968 | if (EliminatedLHSVals.size() > 1) { |
| 1969 | // Loop through all the equal value numbers merging them into the smallest |
| 1970 | // one. |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 1971 | VNInfo *Smallest = EliminatedLHSVals[0]; |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1972 | for (unsigned i = 1, e = EliminatedLHSVals.size(); i != e; ++i) { |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 1973 | if (EliminatedLHSVals[i]->id < Smallest->id) { |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1974 | // Merge the current notion of the smallest into the smaller one. |
| 1975 | LHS.MergeValueNumberInto(Smallest, EliminatedLHSVals[i]); |
| 1976 | Smallest = EliminatedLHSVals[i]; |
| 1977 | } else { |
| 1978 | // Merge into the smallest. |
| 1979 | LHS.MergeValueNumberInto(EliminatedLHSVals[i], Smallest); |
| 1980 | } |
| 1981 | } |
| 1982 | LHSValNo = Smallest; |
Evan Cheng | 7e073ba | 2008-04-09 20:57:25 +0000 | [diff] [blame] | 1983 | } else if (EliminatedLHSVals.empty()) { |
| 1984 | if (TargetRegisterInfo::isPhysicalRegister(LHS.reg) && |
| 1985 | *tri_->getSuperRegisters(LHS.reg)) |
| 1986 | // Imprecise sub-register information. Can't handle it. |
| 1987 | return false; |
Torok Edwin | c23197a | 2009-07-14 16:55:14 +0000 | [diff] [blame] | 1988 | llvm_unreachable("No copies from the RHS?"); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1989 | } else { |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1990 | LHSValNo = EliminatedLHSVals[0]; |
| 1991 | } |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 1992 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1993 | // Okay, now that there is a single LHS value number that we're merging the |
| 1994 | // RHS into, update the value number info for the LHS to indicate that the |
| 1995 | // value number is defined where the RHS value number was. |
Evan Cheng | f3bb2e6 | 2007-09-05 21:46:51 +0000 | [diff] [blame] | 1996 | const VNInfo *VNI = RHS.getValNumInfo(0); |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 1997 | LHSValNo->def = VNI->def; |
Lang Hames | 52c1afc | 2009-08-10 23:43:28 +0000 | [diff] [blame] | 1998 | LHSValNo->setCopy(VNI->getCopy()); |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 1999 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2000 | // Okay, the final step is to loop over the RHS live intervals, adding them to |
| 2001 | // the LHS. |
Lang Hames | 857c4e0 | 2009-06-17 21:01:20 +0000 | [diff] [blame] | 2002 | if (VNI->hasPHIKill()) |
| 2003 | LHSValNo->setHasPHIKill(true); |
Evan Cheng | f3bb2e6 | 2007-09-05 21:46:51 +0000 | [diff] [blame] | 2004 | LHS.addKills(LHSValNo, VNI->kills); |
Evan Cheng | 430a7b0 | 2007-08-14 01:56:58 +0000 | [diff] [blame] | 2005 | LHS.MergeRangesInAsValue(RHS, LHSValNo); |
David Greene | 80607c9 | 2009-07-21 23:36:14 +0000 | [diff] [blame] | 2006 | |
David Greene | 29ff37f | 2009-07-22 20:08:25 +0000 | [diff] [blame] | 2007 | LHS.ComputeJoinedWeight(RHS); |
Evan Cheng | 90f95f8 | 2009-06-14 20:22:55 +0000 | [diff] [blame] | 2008 | |
| 2009 | // Update regalloc hint if both are virtual registers. |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 2010 | if (TargetRegisterInfo::isVirtualRegister(LHS.reg) && |
Evan Cheng | 90f95f8 | 2009-06-14 20:22:55 +0000 | [diff] [blame] | 2011 | TargetRegisterInfo::isVirtualRegister(RHS.reg)) { |
Evan Cheng | 358dec5 | 2009-06-15 08:28:29 +0000 | [diff] [blame] | 2012 | std::pair<unsigned, unsigned> RHSPref = mri_->getRegAllocationHint(RHS.reg); |
| 2013 | std::pair<unsigned, unsigned> LHSPref = mri_->getRegAllocationHint(LHS.reg); |
| 2014 | if (RHSPref != LHSPref) |
Evan Cheng | 90f95f8 | 2009-06-14 20:22:55 +0000 | [diff] [blame] | 2015 | mri_->setRegAllocationHint(LHS.reg, RHSPref.first, RHSPref.second); |
| 2016 | } |
Dan Gohman | 97121ba | 2009-04-08 00:15:30 +0000 | [diff] [blame] | 2017 | |
| 2018 | // Update the liveintervals of sub-registers. |
| 2019 | if (TargetRegisterInfo::isPhysicalRegister(LHS.reg)) |
| 2020 | for (const unsigned *AS = tri_->getSubRegisters(LHS.reg); *AS; ++AS) |
| 2021 | li_->getOrCreateInterval(*AS).MergeInClobberRanges(LHS, |
| 2022 | li_->getVNInfoAllocator()); |
| 2023 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2024 | return true; |
| 2025 | } |
| 2026 | |
| 2027 | /// JoinIntervals - Attempt to join these two intervals. On failure, this |
| 2028 | /// returns false. Otherwise, if one of the intervals being joined is a |
| 2029 | /// physreg, this method always canonicalizes LHS to be it. The output |
| 2030 | /// "RHS" will not have been modified, so we can use this information |
| 2031 | /// below to update aliases. |
Evan Cheng | 8f90b6e | 2009-01-07 02:08:57 +0000 | [diff] [blame] | 2032 | bool |
| 2033 | SimpleRegisterCoalescing::JoinIntervals(LiveInterval &LHS, LiveInterval &RHS, |
| 2034 | bool &Swapped) { |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2035 | // Compute the final value assignment, assuming that the live ranges can be |
Gabor Greif | e510b3a | 2007-07-09 12:00:59 +0000 | [diff] [blame] | 2036 | // coalesced. |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2037 | SmallVector<int, 16> LHSValNoAssignments; |
| 2038 | SmallVector<int, 16> RHSValNoAssignments; |
Evan Cheng | fadfb5b | 2007-08-31 21:23:06 +0000 | [diff] [blame] | 2039 | DenseMap<VNInfo*, VNInfo*> LHSValsDefinedFromRHS; |
| 2040 | DenseMap<VNInfo*, VNInfo*> RHSValsDefinedFromLHS; |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 2041 | SmallVector<VNInfo*, 16> NewVNInfo; |
Evan Cheng | 8f90b6e | 2009-01-07 02:08:57 +0000 | [diff] [blame] | 2042 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2043 | // If a live interval is a physical register, conservatively check if any |
| 2044 | // of its sub-registers is overlapping the live interval of the virtual |
| 2045 | // register. If so, do not coalesce. |
Dan Gohman | 6f0d024 | 2008-02-10 18:45:23 +0000 | [diff] [blame] | 2046 | if (TargetRegisterInfo::isPhysicalRegister(LHS.reg) && |
| 2047 | *tri_->getSubRegisters(LHS.reg)) { |
Evan Cheng | 8f90b6e | 2009-01-07 02:08:57 +0000 | [diff] [blame] | 2048 | // If it's coalescing a virtual register to a physical register, estimate |
| 2049 | // its live interval length. This is the *cost* of scanning an entire live |
| 2050 | // interval. If the cost is low, we'll do an exhaustive check instead. |
Evan Cheng | 1d8a76d | 2009-01-13 03:57:45 +0000 | [diff] [blame] | 2051 | |
| 2052 | // If this is something like this: |
| 2053 | // BB1: |
| 2054 | // v1024 = op |
| 2055 | // ... |
| 2056 | // BB2: |
| 2057 | // ... |
| 2058 | // RAX = v1024 |
| 2059 | // |
| 2060 | // That is, the live interval of v1024 crosses a bb. Then we can't rely on |
| 2061 | // less conservative check. It's possible a sub-register is defined before |
| 2062 | // v1024 (or live in) and live out of BB1. |
Evan Cheng | 8f90b6e | 2009-01-07 02:08:57 +0000 | [diff] [blame] | 2063 | if (RHS.containsOneValue() && |
Evan Cheng | 167650d | 2009-01-13 06:08:37 +0000 | [diff] [blame] | 2064 | li_->intervalIsInOneMBB(RHS) && |
Evan Cheng | 8f90b6e | 2009-01-07 02:08:57 +0000 | [diff] [blame] | 2065 | li_->getApproximateInstructionCount(RHS) <= 10) { |
| 2066 | // Perform a more exhaustive check for some common cases. |
| 2067 | if (li_->conflictsWithPhysRegRef(RHS, LHS.reg, true, JoinedCopies)) |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2068 | return false; |
Evan Cheng | 8f90b6e | 2009-01-07 02:08:57 +0000 | [diff] [blame] | 2069 | } else { |
| 2070 | for (const unsigned* SR = tri_->getSubRegisters(LHS.reg); *SR; ++SR) |
| 2071 | if (li_->hasInterval(*SR) && RHS.overlaps(li_->getInterval(*SR))) { |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 2072 | DEBUG({ |
| 2073 | errs() << "Interfere with sub-register "; |
| 2074 | li_->getInterval(*SR).print(errs(), tri_); |
| 2075 | }); |
Evan Cheng | 8f90b6e | 2009-01-07 02:08:57 +0000 | [diff] [blame] | 2076 | return false; |
| 2077 | } |
| 2078 | } |
Dan Gohman | 6f0d024 | 2008-02-10 18:45:23 +0000 | [diff] [blame] | 2079 | } else if (TargetRegisterInfo::isPhysicalRegister(RHS.reg) && |
| 2080 | *tri_->getSubRegisters(RHS.reg)) { |
Evan Cheng | 8f90b6e | 2009-01-07 02:08:57 +0000 | [diff] [blame] | 2081 | if (LHS.containsOneValue() && |
| 2082 | li_->getApproximateInstructionCount(LHS) <= 10) { |
| 2083 | // Perform a more exhaustive check for some common cases. |
| 2084 | if (li_->conflictsWithPhysRegRef(LHS, RHS.reg, false, JoinedCopies)) |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2085 | return false; |
Evan Cheng | 8f90b6e | 2009-01-07 02:08:57 +0000 | [diff] [blame] | 2086 | } else { |
| 2087 | for (const unsigned* SR = tri_->getSubRegisters(RHS.reg); *SR; ++SR) |
| 2088 | if (li_->hasInterval(*SR) && LHS.overlaps(li_->getInterval(*SR))) { |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 2089 | DEBUG({ |
| 2090 | errs() << "Interfere with sub-register "; |
| 2091 | li_->getInterval(*SR).print(errs(), tri_); |
| 2092 | }); |
Evan Cheng | 8f90b6e | 2009-01-07 02:08:57 +0000 | [diff] [blame] | 2093 | return false; |
| 2094 | } |
| 2095 | } |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2096 | } |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 2097 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2098 | // Compute ultimate value numbers for the LHS and RHS values. |
| 2099 | if (RHS.containsOneValue()) { |
| 2100 | // Copies from a liveinterval with a single value are simple to handle and |
| 2101 | // very common, handle the special case here. This is important, because |
| 2102 | // often RHS is small and LHS is large (e.g. a physreg). |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 2103 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2104 | // Find out if the RHS is defined as a copy from some value in the LHS. |
Evan Cheng | 4f8ff16 | 2007-08-11 00:59:19 +0000 | [diff] [blame] | 2105 | int RHSVal0DefinedFromLHS = -1; |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2106 | int RHSValID = -1; |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 2107 | VNInfo *RHSValNoInfo = NULL; |
Evan Cheng | f3bb2e6 | 2007-09-05 21:46:51 +0000 | [diff] [blame] | 2108 | VNInfo *RHSValNoInfo0 = RHS.getValNumInfo(0); |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 2109 | unsigned RHSSrcReg = li_->getVNInfoSourceReg(RHSValNoInfo0); |
Evan Cheng | 8f90b6e | 2009-01-07 02:08:57 +0000 | [diff] [blame] | 2110 | if (RHSSrcReg == 0 || RHSSrcReg != LHS.reg) { |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2111 | // If RHS is not defined as a copy from the LHS, we can use simpler and |
Gabor Greif | e510b3a | 2007-07-09 12:00:59 +0000 | [diff] [blame] | 2112 | // faster checks to see if the live ranges are coalescable. This joiner |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2113 | // can't swap the LHS/RHS intervals though. |
Dan Gohman | 6f0d024 | 2008-02-10 18:45:23 +0000 | [diff] [blame] | 2114 | if (!TargetRegisterInfo::isPhysicalRegister(RHS.reg)) { |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2115 | return SimpleJoin(LHS, RHS); |
| 2116 | } else { |
Evan Cheng | c14b144 | 2007-08-31 08:04:17 +0000 | [diff] [blame] | 2117 | RHSValNoInfo = RHSValNoInfo0; |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2118 | } |
| 2119 | } else { |
| 2120 | // It was defined as a copy from the LHS, find out what value # it is. |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 2121 | RHSValNoInfo = |
| 2122 | LHS.getLiveRangeContaining(li_->getPrevSlot(RHSValNoInfo0->def))->valno; |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 2123 | RHSValID = RHSValNoInfo->id; |
Evan Cheng | 4f8ff16 | 2007-08-11 00:59:19 +0000 | [diff] [blame] | 2124 | RHSVal0DefinedFromLHS = RHSValID; |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2125 | } |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 2126 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2127 | LHSValNoAssignments.resize(LHS.getNumValNums(), -1); |
| 2128 | RHSValNoAssignments.resize(RHS.getNumValNums(), -1); |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 2129 | NewVNInfo.resize(LHS.getNumValNums(), NULL); |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 2130 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2131 | // Okay, *all* of the values in LHS that are defined as a copy from RHS |
| 2132 | // should now get updated. |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 2133 | for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end(); |
| 2134 | i != e; ++i) { |
| 2135 | VNInfo *VNI = *i; |
| 2136 | unsigned VN = VNI->id; |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 2137 | if (unsigned LHSSrcReg = li_->getVNInfoSourceReg(VNI)) { |
| 2138 | if (LHSSrcReg != RHS.reg) { |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2139 | // If this is not a copy from the RHS, its value number will be |
Gabor Greif | e510b3a | 2007-07-09 12:00:59 +0000 | [diff] [blame] | 2140 | // unmodified by the coalescing. |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 2141 | NewVNInfo[VN] = VNI; |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2142 | LHSValNoAssignments[VN] = VN; |
| 2143 | } else if (RHSValID == -1) { |
| 2144 | // Otherwise, it is a copy from the RHS, and we don't already have a |
| 2145 | // value# for it. Keep the current value number, but remember it. |
| 2146 | LHSValNoAssignments[VN] = RHSValID = VN; |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 2147 | NewVNInfo[VN] = RHSValNoInfo; |
Evan Cheng | c14b144 | 2007-08-31 08:04:17 +0000 | [diff] [blame] | 2148 | LHSValsDefinedFromRHS[VNI] = RHSValNoInfo0; |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2149 | } else { |
| 2150 | // Otherwise, use the specified value #. |
| 2151 | LHSValNoAssignments[VN] = RHSValID; |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 2152 | if (VN == (unsigned)RHSValID) { // Else this val# is dead. |
| 2153 | NewVNInfo[VN] = RHSValNoInfo; |
Evan Cheng | c14b144 | 2007-08-31 08:04:17 +0000 | [diff] [blame] | 2154 | LHSValsDefinedFromRHS[VNI] = RHSValNoInfo0; |
Evan Cheng | 4f8ff16 | 2007-08-11 00:59:19 +0000 | [diff] [blame] | 2155 | } |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2156 | } |
| 2157 | } else { |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 2158 | NewVNInfo[VN] = VNI; |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2159 | LHSValNoAssignments[VN] = VN; |
| 2160 | } |
| 2161 | } |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 2162 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2163 | assert(RHSValID != -1 && "Didn't find value #?"); |
| 2164 | RHSValNoAssignments[0] = RHSValID; |
Evan Cheng | 4f8ff16 | 2007-08-11 00:59:19 +0000 | [diff] [blame] | 2165 | if (RHSVal0DefinedFromLHS != -1) { |
Evan Cheng | 3430135 | 2007-09-01 02:03:17 +0000 | [diff] [blame] | 2166 | // This path doesn't go through ComputeUltimateVN so just set |
| 2167 | // it to anything. |
| 2168 | RHSValsDefinedFromLHS[RHSValNoInfo0] = (VNInfo*)1; |
Evan Cheng | 4f8ff16 | 2007-08-11 00:59:19 +0000 | [diff] [blame] | 2169 | } |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2170 | } else { |
| 2171 | // Loop over the value numbers of the LHS, seeing if any are defined from |
| 2172 | // the RHS. |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 2173 | for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end(); |
| 2174 | i != e; ++i) { |
| 2175 | VNInfo *VNI = *i; |
Lang Hames | 52c1afc | 2009-08-10 23:43:28 +0000 | [diff] [blame] | 2176 | if (VNI->isUnused() || VNI->getCopy() == 0) // Src not defined by a copy? |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2177 | continue; |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 2178 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2179 | // DstReg is known to be a register in the LHS interval. If the src is |
| 2180 | // from the RHS interval, we can use its value #. |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 2181 | if (li_->getVNInfoSourceReg(VNI) != RHS.reg) |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2182 | continue; |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 2183 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2184 | // Figure out the value # from the RHS. |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 2185 | LHSValsDefinedFromRHS[VNI]= |
| 2186 | RHS.getLiveRangeContaining(li_->getPrevSlot(VNI->def))->valno; |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2187 | } |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 2188 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2189 | // Loop over the value numbers of the RHS, seeing if any are defined from |
| 2190 | // the LHS. |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 2191 | for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end(); |
| 2192 | i != e; ++i) { |
| 2193 | VNInfo *VNI = *i; |
Lang Hames | 52c1afc | 2009-08-10 23:43:28 +0000 | [diff] [blame] | 2194 | if (VNI->isUnused() || VNI->getCopy() == 0) // Src not defined by a copy? |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2195 | continue; |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 2196 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2197 | // DstReg is known to be a register in the RHS interval. If the src is |
| 2198 | // from the LHS interval, we can use its value #. |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 2199 | if (li_->getVNInfoSourceReg(VNI) != LHS.reg) |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2200 | continue; |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 2201 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2202 | // Figure out the value # from the LHS. |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 2203 | RHSValsDefinedFromLHS[VNI]= |
| 2204 | LHS.getLiveRangeContaining(li_->getPrevSlot(VNI->def))->valno; |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2205 | } |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 2206 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2207 | LHSValNoAssignments.resize(LHS.getNumValNums(), -1); |
| 2208 | RHSValNoAssignments.resize(RHS.getNumValNums(), -1); |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 2209 | NewVNInfo.reserve(LHS.getNumValNums() + RHS.getNumValNums()); |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 2210 | |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 2211 | for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end(); |
| 2212 | i != e; ++i) { |
| 2213 | VNInfo *VNI = *i; |
| 2214 | unsigned VN = VNI->id; |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 2215 | if (LHSValNoAssignments[VN] >= 0 || VNI->isUnused()) |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2216 | continue; |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 2217 | ComputeUltimateVN(VNI, NewVNInfo, |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2218 | LHSValsDefinedFromRHS, RHSValsDefinedFromLHS, |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 2219 | LHSValNoAssignments, RHSValNoAssignments); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2220 | } |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 2221 | for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end(); |
| 2222 | i != e; ++i) { |
| 2223 | VNInfo *VNI = *i; |
| 2224 | unsigned VN = VNI->id; |
Lang Hames | 857c4e0 | 2009-06-17 21:01:20 +0000 | [diff] [blame] | 2225 | if (RHSValNoAssignments[VN] >= 0 || VNI->isUnused()) |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2226 | continue; |
| 2227 | // If this value number isn't a copy from the LHS, it's a new number. |
Evan Cheng | c14b144 | 2007-08-31 08:04:17 +0000 | [diff] [blame] | 2228 | if (RHSValsDefinedFromLHS.find(VNI) == RHSValsDefinedFromLHS.end()) { |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 2229 | NewVNInfo.push_back(VNI); |
| 2230 | RHSValNoAssignments[VN] = NewVNInfo.size()-1; |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2231 | continue; |
| 2232 | } |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 2233 | |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 2234 | ComputeUltimateVN(VNI, NewVNInfo, |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2235 | RHSValsDefinedFromLHS, LHSValsDefinedFromRHS, |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 2236 | RHSValNoAssignments, LHSValNoAssignments); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2237 | } |
| 2238 | } |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 2239 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2240 | // Armed with the mappings of LHS/RHS values to ultimate values, walk the |
Gabor Greif | e510b3a | 2007-07-09 12:00:59 +0000 | [diff] [blame] | 2241 | // interval lists to see if these intervals are coalescable. |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2242 | LiveInterval::const_iterator I = LHS.begin(); |
| 2243 | LiveInterval::const_iterator IE = LHS.end(); |
| 2244 | LiveInterval::const_iterator J = RHS.begin(); |
| 2245 | LiveInterval::const_iterator JE = RHS.end(); |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 2246 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2247 | // Skip ahead until the first place of potential sharing. |
| 2248 | if (I->start < J->start) { |
| 2249 | I = std::upper_bound(I, IE, J->start); |
| 2250 | if (I != LHS.begin()) --I; |
| 2251 | } else if (J->start < I->start) { |
| 2252 | J = std::upper_bound(J, JE, I->start); |
| 2253 | if (J != RHS.begin()) --J; |
| 2254 | } |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 2255 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2256 | while (1) { |
| 2257 | // Determine if these two live ranges overlap. |
| 2258 | bool Overlaps; |
| 2259 | if (I->start < J->start) { |
| 2260 | Overlaps = I->end > J->start; |
| 2261 | } else { |
| 2262 | Overlaps = J->end > I->start; |
| 2263 | } |
| 2264 | |
| 2265 | // If so, check value # info to determine if they are really different. |
| 2266 | if (Overlaps) { |
| 2267 | // If the live range overlap will map to the same value number in the |
Gabor Greif | e510b3a | 2007-07-09 12:00:59 +0000 | [diff] [blame] | 2268 | // result liverange, we can still coalesce them. If not, we can't. |
Evan Cheng | 7ecb38b | 2007-08-29 20:45:00 +0000 | [diff] [blame] | 2269 | if (LHSValNoAssignments[I->valno->id] != |
| 2270 | RHSValNoAssignments[J->valno->id]) |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2271 | return false; |
| 2272 | } |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 2273 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2274 | if (I->end < J->end) { |
| 2275 | ++I; |
| 2276 | if (I == IE) break; |
| 2277 | } else { |
| 2278 | ++J; |
| 2279 | if (J == JE) break; |
| 2280 | } |
| 2281 | } |
| 2282 | |
Evan Cheng | 3472925 | 2007-10-14 10:08:34 +0000 | [diff] [blame] | 2283 | // Update kill info. Some live ranges are extended due to copy coalescing. |
| 2284 | for (DenseMap<VNInfo*, VNInfo*>::iterator I = LHSValsDefinedFromRHS.begin(), |
| 2285 | E = LHSValsDefinedFromRHS.end(); I != E; ++I) { |
| 2286 | VNInfo *VNI = I->first; |
| 2287 | unsigned LHSValID = LHSValNoAssignments[VNI->id]; |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 2288 | NewVNInfo[LHSValID]->removeKill(VNI->def); |
Lang Hames | 857c4e0 | 2009-06-17 21:01:20 +0000 | [diff] [blame] | 2289 | if (VNI->hasPHIKill()) |
| 2290 | NewVNInfo[LHSValID]->setHasPHIKill(true); |
Evan Cheng | 3472925 | 2007-10-14 10:08:34 +0000 | [diff] [blame] | 2291 | RHS.addKills(NewVNInfo[LHSValID], VNI->kills); |
| 2292 | } |
| 2293 | |
| 2294 | // Update kill info. Some live ranges are extended due to copy coalescing. |
| 2295 | for (DenseMap<VNInfo*, VNInfo*>::iterator I = RHSValsDefinedFromLHS.begin(), |
| 2296 | E = RHSValsDefinedFromLHS.end(); I != E; ++I) { |
| 2297 | VNInfo *VNI = I->first; |
| 2298 | unsigned RHSValID = RHSValNoAssignments[VNI->id]; |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 2299 | NewVNInfo[RHSValID]->removeKill(VNI->def); |
Lang Hames | 857c4e0 | 2009-06-17 21:01:20 +0000 | [diff] [blame] | 2300 | if (VNI->hasPHIKill()) |
| 2301 | NewVNInfo[RHSValID]->setHasPHIKill(true); |
Evan Cheng | 3472925 | 2007-10-14 10:08:34 +0000 | [diff] [blame] | 2302 | LHS.addKills(NewVNInfo[RHSValID], VNI->kills); |
| 2303 | } |
| 2304 | |
Gabor Greif | e510b3a | 2007-07-09 12:00:59 +0000 | [diff] [blame] | 2305 | // If we get here, we know that we can coalesce the live ranges. Ask the |
| 2306 | // intervals to coalesce themselves now. |
Evan Cheng | 1a66f0a | 2007-08-28 08:28:51 +0000 | [diff] [blame] | 2307 | if ((RHS.ranges.size() > LHS.ranges.size() && |
Dan Gohman | 6f0d024 | 2008-02-10 18:45:23 +0000 | [diff] [blame] | 2308 | TargetRegisterInfo::isVirtualRegister(LHS.reg)) || |
| 2309 | TargetRegisterInfo::isPhysicalRegister(RHS.reg)) { |
Evan Cheng | 90f95f8 | 2009-06-14 20:22:55 +0000 | [diff] [blame] | 2310 | RHS.join(LHS, &RHSValNoAssignments[0], &LHSValNoAssignments[0], NewVNInfo, |
| 2311 | mri_); |
Evan Cheng | 1a66f0a | 2007-08-28 08:28:51 +0000 | [diff] [blame] | 2312 | Swapped = true; |
| 2313 | } else { |
Evan Cheng | 90f95f8 | 2009-06-14 20:22:55 +0000 | [diff] [blame] | 2314 | LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], NewVNInfo, |
| 2315 | mri_); |
Evan Cheng | 1a66f0a | 2007-08-28 08:28:51 +0000 | [diff] [blame] | 2316 | Swapped = false; |
| 2317 | } |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2318 | return true; |
| 2319 | } |
| 2320 | |
| 2321 | namespace { |
| 2322 | // DepthMBBCompare - Comparison predicate that sort first based on the loop |
| 2323 | // depth of the basic block (the unsigned), and then on the MBB number. |
| 2324 | struct DepthMBBCompare { |
| 2325 | typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair; |
| 2326 | bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const { |
| 2327 | if (LHS.first > RHS.first) return true; // Deeper loops first |
| 2328 | return LHS.first == RHS.first && |
| 2329 | LHS.second->getNumber() < RHS.second->getNumber(); |
| 2330 | } |
| 2331 | }; |
| 2332 | } |
| 2333 | |
Gabor Greif | e510b3a | 2007-07-09 12:00:59 +0000 | [diff] [blame] | 2334 | void SimpleRegisterCoalescing::CopyCoalesceInMBB(MachineBasicBlock *MBB, |
Evan Cheng | 8b0b874 | 2007-10-16 08:04:24 +0000 | [diff] [blame] | 2335 | std::vector<CopyRec> &TryAgain) { |
Daniel Dunbar | ce63ffb | 2009-07-25 00:23:56 +0000 | [diff] [blame] | 2336 | DEBUG(errs() << ((Value*)MBB->getBasicBlock())->getName() << ":\n"); |
Evan Cheng | 8fc9a10 | 2007-11-06 08:52:21 +0000 | [diff] [blame] | 2337 | |
Evan Cheng | 8b0b874 | 2007-10-16 08:04:24 +0000 | [diff] [blame] | 2338 | std::vector<CopyRec> VirtCopies; |
| 2339 | std::vector<CopyRec> PhysCopies; |
Evan Cheng | 7e073ba | 2008-04-09 20:57:25 +0000 | [diff] [blame] | 2340 | std::vector<CopyRec> ImpDefCopies; |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2341 | for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end(); |
| 2342 | MII != E;) { |
| 2343 | MachineInstr *Inst = MII++; |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 2344 | |
Evan Cheng | 32dfbea | 2007-10-12 08:50:34 +0000 | [diff] [blame] | 2345 | // If this isn't a copy nor a extract_subreg, we can't join intervals. |
Evan Cheng | 04ee5a1 | 2009-01-20 19:12:24 +0000 | [diff] [blame] | 2346 | unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; |
Evan Cheng | 32dfbea | 2007-10-12 08:50:34 +0000 | [diff] [blame] | 2347 | if (Inst->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) { |
| 2348 | DstReg = Inst->getOperand(0).getReg(); |
| 2349 | SrcReg = Inst->getOperand(1).getReg(); |
Dan Gohman | 97121ba | 2009-04-08 00:15:30 +0000 | [diff] [blame] | 2350 | } else if (Inst->getOpcode() == TargetInstrInfo::INSERT_SUBREG || |
| 2351 | Inst->getOpcode() == TargetInstrInfo::SUBREG_TO_REG) { |
Evan Cheng | 7e073ba | 2008-04-09 20:57:25 +0000 | [diff] [blame] | 2352 | DstReg = Inst->getOperand(0).getReg(); |
| 2353 | SrcReg = Inst->getOperand(2).getReg(); |
Evan Cheng | 04ee5a1 | 2009-01-20 19:12:24 +0000 | [diff] [blame] | 2354 | } else if (!tii_->isMoveInstr(*Inst, SrcReg, DstReg, SrcSubIdx, DstSubIdx)) |
Evan Cheng | 32dfbea | 2007-10-12 08:50:34 +0000 | [diff] [blame] | 2355 | continue; |
Evan Cheng | 8b0b874 | 2007-10-16 08:04:24 +0000 | [diff] [blame] | 2356 | |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 2357 | bool SrcIsPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg); |
| 2358 | bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); |
Evan Cheng | b24222c | 2009-09-12 02:14:41 +0000 | [diff] [blame] | 2359 | if (li_->hasInterval(SrcReg) && li_->getInterval(SrcReg).empty()) |
| 2360 | ImpDefCopies.push_back(CopyRec(Inst, 0)); |
| 2361 | else if (SrcIsPhys || DstIsPhys) |
| 2362 | PhysCopies.push_back(CopyRec(Inst, 0)); |
| 2363 | else |
| 2364 | VirtCopies.push_back(CopyRec(Inst, 0)); |
Evan Cheng | 8b0b874 | 2007-10-16 08:04:24 +0000 | [diff] [blame] | 2365 | } |
| 2366 | |
Evan Cheng | 7e073ba | 2008-04-09 20:57:25 +0000 | [diff] [blame] | 2367 | // Try coalescing implicit copies first, followed by copies to / from |
| 2368 | // physical registers, then finally copies from virtual registers to |
| 2369 | // virtual registers. |
| 2370 | for (unsigned i = 0, e = ImpDefCopies.size(); i != e; ++i) { |
| 2371 | CopyRec &TheCopy = ImpDefCopies[i]; |
| 2372 | bool Again = false; |
| 2373 | if (!JoinCopy(TheCopy, Again)) |
| 2374 | if (Again) |
| 2375 | TryAgain.push_back(TheCopy); |
| 2376 | } |
Evan Cheng | 8b0b874 | 2007-10-16 08:04:24 +0000 | [diff] [blame] | 2377 | for (unsigned i = 0, e = PhysCopies.size(); i != e; ++i) { |
| 2378 | CopyRec &TheCopy = PhysCopies[i]; |
Evan Cheng | 0547bab | 2007-11-01 06:22:48 +0000 | [diff] [blame] | 2379 | bool Again = false; |
Evan Cheng | 8fc9a10 | 2007-11-06 08:52:21 +0000 | [diff] [blame] | 2380 | if (!JoinCopy(TheCopy, Again)) |
Evan Cheng | 0547bab | 2007-11-01 06:22:48 +0000 | [diff] [blame] | 2381 | if (Again) |
| 2382 | TryAgain.push_back(TheCopy); |
Evan Cheng | 8b0b874 | 2007-10-16 08:04:24 +0000 | [diff] [blame] | 2383 | } |
| 2384 | for (unsigned i = 0, e = VirtCopies.size(); i != e; ++i) { |
| 2385 | CopyRec &TheCopy = VirtCopies[i]; |
Evan Cheng | 0547bab | 2007-11-01 06:22:48 +0000 | [diff] [blame] | 2386 | bool Again = false; |
Evan Cheng | 8fc9a10 | 2007-11-06 08:52:21 +0000 | [diff] [blame] | 2387 | if (!JoinCopy(TheCopy, Again)) |
Evan Cheng | 0547bab | 2007-11-01 06:22:48 +0000 | [diff] [blame] | 2388 | if (Again) |
| 2389 | TryAgain.push_back(TheCopy); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2390 | } |
| 2391 | } |
| 2392 | |
| 2393 | void SimpleRegisterCoalescing::joinIntervals() { |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 2394 | DEBUG(errs() << "********** JOINING INTERVALS ***********\n"); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2395 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2396 | std::vector<CopyRec> TryAgainList; |
Dan Gohman | a8c763b | 2008-08-14 18:13:49 +0000 | [diff] [blame] | 2397 | if (loopInfo->empty()) { |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2398 | // If there are no loops in the function, join intervals in function order. |
| 2399 | for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); |
| 2400 | I != E; ++I) |
Evan Cheng | 8b0b874 | 2007-10-16 08:04:24 +0000 | [diff] [blame] | 2401 | CopyCoalesceInMBB(I, TryAgainList); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2402 | } else { |
| 2403 | // Otherwise, join intervals in inner loops before other intervals. |
| 2404 | // Unfortunately we can't just iterate over loop hierarchy here because |
| 2405 | // there may be more MBB's than BB's. Collect MBB's for sorting. |
| 2406 | |
| 2407 | // Join intervals in the function prolog first. We want to join physical |
| 2408 | // registers with virtual registers before the intervals got too long. |
| 2409 | std::vector<std::pair<unsigned, MachineBasicBlock*> > MBBs; |
Evan Cheng | 22f07ff | 2007-12-11 02:09:15 +0000 | [diff] [blame] | 2410 | for (MachineFunction::iterator I = mf_->begin(), E = mf_->end();I != E;++I){ |
| 2411 | MachineBasicBlock *MBB = I; |
| 2412 | MBBs.push_back(std::make_pair(loopInfo->getLoopDepth(MBB), I)); |
| 2413 | } |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2414 | |
| 2415 | // Sort by loop depth. |
| 2416 | std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare()); |
| 2417 | |
| 2418 | // Finally, join intervals in loop nest order. |
| 2419 | for (unsigned i = 0, e = MBBs.size(); i != e; ++i) |
Evan Cheng | 8b0b874 | 2007-10-16 08:04:24 +0000 | [diff] [blame] | 2420 | CopyCoalesceInMBB(MBBs[i].second, TryAgainList); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2421 | } |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 2422 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2423 | // Joining intervals can allow other intervals to be joined. Iteratively join |
| 2424 | // until we make no progress. |
Evan Cheng | b24222c | 2009-09-12 02:14:41 +0000 | [diff] [blame] | 2425 | bool ProgressMade = true; |
| 2426 | while (ProgressMade) { |
| 2427 | ProgressMade = false; |
Evan Cheng | 8fc9a10 | 2007-11-06 08:52:21 +0000 | [diff] [blame] | 2428 | |
Evan Cheng | b24222c | 2009-09-12 02:14:41 +0000 | [diff] [blame] | 2429 | for (unsigned i = 0, e = TryAgainList.size(); i != e; ++i) { |
| 2430 | CopyRec &TheCopy = TryAgainList[i]; |
| 2431 | if (!TheCopy.MI) |
| 2432 | continue; |
Evan Cheng | 8fc9a10 | 2007-11-06 08:52:21 +0000 | [diff] [blame] | 2433 | |
Evan Cheng | b24222c | 2009-09-12 02:14:41 +0000 | [diff] [blame] | 2434 | bool Again = false; |
| 2435 | bool Success = JoinCopy(TheCopy, Again); |
| 2436 | if (Success || !Again) { |
| 2437 | TheCopy.MI = 0; // Mark this one as done. |
| 2438 | ProgressMade = true; |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2439 | } |
| 2440 | } |
| 2441 | } |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2442 | } |
| 2443 | |
| 2444 | /// Return true if the two specified registers belong to different register |
Evan Cheng | 8c08d8c | 2009-01-23 02:15:19 +0000 | [diff] [blame] | 2445 | /// classes. The registers may be either phys or virt regs. |
Evan Cheng | e00f5de | 2008-06-19 01:39:21 +0000 | [diff] [blame] | 2446 | bool |
Evan Cheng | 8c08d8c | 2009-01-23 02:15:19 +0000 | [diff] [blame] | 2447 | SimpleRegisterCoalescing::differingRegisterClasses(unsigned RegA, |
| 2448 | unsigned RegB) const { |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2449 | // Get the register classes for the first reg. |
Dan Gohman | 6f0d024 | 2008-02-10 18:45:23 +0000 | [diff] [blame] | 2450 | if (TargetRegisterInfo::isPhysicalRegister(RegA)) { |
| 2451 | assert(TargetRegisterInfo::isVirtualRegister(RegB) && |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2452 | "Shouldn't consider two physregs!"); |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 2453 | return !mri_->getRegClass(RegB)->contains(RegA); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2454 | } |
| 2455 | |
| 2456 | // Compare against the regclass for the second reg. |
Evan Cheng | e00f5de | 2008-06-19 01:39:21 +0000 | [diff] [blame] | 2457 | const TargetRegisterClass *RegClassA = mri_->getRegClass(RegA); |
| 2458 | if (TargetRegisterInfo::isVirtualRegister(RegB)) { |
| 2459 | const TargetRegisterClass *RegClassB = mri_->getRegClass(RegB); |
Evan Cheng | 8c08d8c | 2009-01-23 02:15:19 +0000 | [diff] [blame] | 2460 | return RegClassA != RegClassB; |
Evan Cheng | e00f5de | 2008-06-19 01:39:21 +0000 | [diff] [blame] | 2461 | } |
| 2462 | return !RegClassA->contains(RegB); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2463 | } |
| 2464 | |
| 2465 | /// lastRegisterUse - Returns the last use of the specific register between |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 2466 | /// cycles Start and End or NULL if there are no uses. |
| 2467 | MachineOperand * |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 2468 | SimpleRegisterCoalescing::lastRegisterUse(MachineInstrIndex Start, |
| 2469 | MachineInstrIndex End, |
| 2470 | unsigned Reg, |
| 2471 | MachineInstrIndex &UseIdx) const{ |
| 2472 | UseIdx = MachineInstrIndex(); |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 2473 | if (TargetRegisterInfo::isVirtualRegister(Reg)) { |
| 2474 | MachineOperand *LastUse = NULL; |
| 2475 | for (MachineRegisterInfo::use_iterator I = mri_->use_begin(Reg), |
| 2476 | E = mri_->use_end(); I != E; ++I) { |
| 2477 | MachineOperand &Use = I.getOperand(); |
| 2478 | MachineInstr *UseMI = Use.getParent(); |
Evan Cheng | 04ee5a1 | 2009-01-20 19:12:24 +0000 | [diff] [blame] | 2479 | unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; |
| 2480 | if (tii_->isMoveInstr(*UseMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) && |
| 2481 | SrcReg == DstReg) |
Evan Cheng | a2fb634 | 2008-03-25 02:02:19 +0000 | [diff] [blame] | 2482 | // Ignore identity copies. |
| 2483 | continue; |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 2484 | MachineInstrIndex Idx = li_->getInstructionIndex(UseMI); |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 2485 | if (Idx >= Start && Idx < End && Idx >= UseIdx) { |
| 2486 | LastUse = &Use; |
Evan Cheng | 58207f1 | 2009-02-22 08:35:56 +0000 | [diff] [blame] | 2487 | UseIdx = li_->getUseIndex(Idx); |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 2488 | } |
| 2489 | } |
| 2490 | return LastUse; |
| 2491 | } |
| 2492 | |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 2493 | MachineInstrIndex s = Start; |
| 2494 | MachineInstrIndex e = li_->getBaseIndex(li_->getPrevSlot(End)); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2495 | while (e >= s) { |
| 2496 | // Skip deleted instructions |
| 2497 | MachineInstr *MI = li_->getInstructionFromIndex(e); |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 2498 | while (e != MachineInstrIndex() && li_->getPrevIndex(e) >= s && !MI) { |
| 2499 | e = li_->getPrevIndex(e); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2500 | MI = li_->getInstructionFromIndex(e); |
| 2501 | } |
| 2502 | if (e < s || MI == NULL) |
| 2503 | return NULL; |
| 2504 | |
Evan Cheng | a2fb634 | 2008-03-25 02:02:19 +0000 | [diff] [blame] | 2505 | // Ignore identity copies. |
Evan Cheng | 04ee5a1 | 2009-01-20 19:12:24 +0000 | [diff] [blame] | 2506 | unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; |
| 2507 | if (!(tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx) && |
| 2508 | SrcReg == DstReg)) |
Evan Cheng | a2fb634 | 2008-03-25 02:02:19 +0000 | [diff] [blame] | 2509 | for (unsigned i = 0, NumOps = MI->getNumOperands(); i != NumOps; ++i) { |
| 2510 | MachineOperand &Use = MI->getOperand(i); |
Dan Gohman | d735b80 | 2008-10-03 15:45:36 +0000 | [diff] [blame] | 2511 | if (Use.isReg() && Use.isUse() && Use.getReg() && |
Evan Cheng | a2fb634 | 2008-03-25 02:02:19 +0000 | [diff] [blame] | 2512 | tri_->regsOverlap(Use.getReg(), Reg)) { |
Evan Cheng | 58207f1 | 2009-02-22 08:35:56 +0000 | [diff] [blame] | 2513 | UseIdx = li_->getUseIndex(e); |
Evan Cheng | a2fb634 | 2008-03-25 02:02:19 +0000 | [diff] [blame] | 2514 | return &Use; |
| 2515 | } |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2516 | } |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2517 | |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 2518 | e = li_->getPrevIndex(e); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2519 | } |
| 2520 | |
| 2521 | return NULL; |
| 2522 | } |
| 2523 | |
| 2524 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2525 | void SimpleRegisterCoalescing::printRegName(unsigned reg) const { |
Dan Gohman | 6f0d024 | 2008-02-10 18:45:23 +0000 | [diff] [blame] | 2526 | if (TargetRegisterInfo::isPhysicalRegister(reg)) |
Chris Lattner | d9ea85a | 2009-08-23 08:43:55 +0000 | [diff] [blame] | 2527 | errs() << tri_->getName(reg); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2528 | else |
Chris Lattner | d9ea85a | 2009-08-23 08:43:55 +0000 | [diff] [blame] | 2529 | errs() << "%reg" << reg; |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2530 | } |
| 2531 | |
| 2532 | void SimpleRegisterCoalescing::releaseMemory() { |
Evan Cheng | 8fc9a10 | 2007-11-06 08:52:21 +0000 | [diff] [blame] | 2533 | JoinedCopies.clear(); |
Evan Cheng | cd04708 | 2008-08-30 09:09:33 +0000 | [diff] [blame] | 2534 | ReMatCopies.clear(); |
Evan Cheng | 20580a1 | 2008-09-19 17:38:47 +0000 | [diff] [blame] | 2535 | ReMatDefs.clear(); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2536 | } |
| 2537 | |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 2538 | bool SimpleRegisterCoalescing::isZeroLengthInterval(LiveInterval *li) const { |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2539 | for (LiveInterval::Ranges::const_iterator |
| 2540 | i = li->ranges.begin(), e = li->ranges.end(); i != e; ++i) |
Lang Hames | 8651125 | 2009-09-04 20:41:11 +0000 | [diff] [blame] | 2541 | if (li_->getPrevIndex(i->end) > i->start) |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2542 | return false; |
| 2543 | return true; |
| 2544 | } |
| 2545 | |
Evan Cheng | db9b1c3 | 2008-04-03 16:41:54 +0000 | [diff] [blame] | 2546 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2547 | bool SimpleRegisterCoalescing::runOnMachineFunction(MachineFunction &fn) { |
| 2548 | mf_ = &fn; |
Evan Cheng | 7007143 | 2008-02-13 03:01:43 +0000 | [diff] [blame] | 2549 | mri_ = &fn.getRegInfo(); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2550 | tm_ = &fn.getTarget(); |
Dan Gohman | 6f0d024 | 2008-02-10 18:45:23 +0000 | [diff] [blame] | 2551 | tri_ = tm_->getRegisterInfo(); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2552 | tii_ = tm_->getInstrInfo(); |
| 2553 | li_ = &getAnalysis<LiveIntervals>(); |
Evan Cheng | 22f07ff | 2007-12-11 02:09:15 +0000 | [diff] [blame] | 2554 | loopInfo = &getAnalysis<MachineLoopInfo>(); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2555 | |
Daniel Dunbar | ce63ffb | 2009-07-25 00:23:56 +0000 | [diff] [blame] | 2556 | DEBUG(errs() << "********** SIMPLE REGISTER COALESCING **********\n" |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 2557 | << "********** Function: " |
| 2558 | << ((Value*)mf_->getFunction())->getName() << '\n'); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2559 | |
Dan Gohman | 6f0d024 | 2008-02-10 18:45:23 +0000 | [diff] [blame] | 2560 | allocatableRegs_ = tri_->getAllocatableSet(fn); |
| 2561 | for (TargetRegisterInfo::regclass_iterator I = tri_->regclass_begin(), |
| 2562 | E = tri_->regclass_end(); I != E; ++I) |
Bill Wendling | 2674d71 | 2008-01-04 08:59:18 +0000 | [diff] [blame] | 2563 | allocatableRCRegs_.insert(std::make_pair(*I, |
Dan Gohman | 6f0d024 | 2008-02-10 18:45:23 +0000 | [diff] [blame] | 2564 | tri_->getAllocatableSet(fn, *I))); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2565 | |
Gabor Greif | e510b3a | 2007-07-09 12:00:59 +0000 | [diff] [blame] | 2566 | // Join (coalesce) intervals if requested. |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2567 | if (EnableJoining) { |
| 2568 | joinIntervals(); |
Bill Wendling | bebbded | 2008-12-19 02:09:57 +0000 | [diff] [blame] | 2569 | DEBUG({ |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 2570 | errs() << "********** INTERVALS POST JOINING **********\n"; |
Bill Wendling | bebbded | 2008-12-19 02:09:57 +0000 | [diff] [blame] | 2571 | for (LiveIntervals::iterator I = li_->begin(), E = li_->end(); I != E; ++I){ |
Bill Wendling | 70357db | 2009-08-22 20:52:46 +0000 | [diff] [blame] | 2572 | I->second->print(errs(), tri_); |
| 2573 | errs() << "\n"; |
Bill Wendling | bebbded | 2008-12-19 02:09:57 +0000 | [diff] [blame] | 2574 | } |
| 2575 | }); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2576 | } |
| 2577 | |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 2578 | // Perform a final pass over the instructions and compute spill weights |
| 2579 | // and remove identity moves. |
Evan Cheng | b3990d5 | 2008-10-27 23:21:01 +0000 | [diff] [blame] | 2580 | SmallVector<unsigned, 4> DeadDefs; |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2581 | for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); |
| 2582 | mbbi != mbbe; ++mbbi) { |
| 2583 | MachineBasicBlock* mbb = mbbi; |
Evan Cheng | 22f07ff | 2007-12-11 02:09:15 +0000 | [diff] [blame] | 2584 | unsigned loopDepth = loopInfo->getLoopDepth(mbb); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2585 | |
| 2586 | for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end(); |
| 2587 | mii != mie; ) { |
Evan Cheng | a971dbd | 2008-04-24 09:06:33 +0000 | [diff] [blame] | 2588 | MachineInstr *MI = mii; |
Evan Cheng | 04ee5a1 | 2009-01-20 19:12:24 +0000 | [diff] [blame] | 2589 | unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; |
Evan Cheng | a971dbd | 2008-04-24 09:06:33 +0000 | [diff] [blame] | 2590 | if (JoinedCopies.count(MI)) { |
| 2591 | // Delete all coalesced copies. |
Evan Cheng | 04ee5a1 | 2009-01-20 19:12:24 +0000 | [diff] [blame] | 2592 | if (!tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)) { |
Evan Cheng | a971dbd | 2008-04-24 09:06:33 +0000 | [diff] [blame] | 2593 | assert((MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || |
Dan Gohman | 97121ba | 2009-04-08 00:15:30 +0000 | [diff] [blame] | 2594 | MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG || |
| 2595 | MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG) && |
Evan Cheng | a971dbd | 2008-04-24 09:06:33 +0000 | [diff] [blame] | 2596 | "Unrecognized copy instruction"); |
| 2597 | DstReg = MI->getOperand(0).getReg(); |
| 2598 | } |
| 2599 | if (MI->registerDefIsDead(DstReg)) { |
| 2600 | LiveInterval &li = li_->getInterval(DstReg); |
| 2601 | if (!ShortenDeadCopySrcLiveRange(li, MI)) |
| 2602 | ShortenDeadCopyLiveRange(li, MI); |
| 2603 | } |
| 2604 | li_->RemoveMachineInstrFromMaps(MI); |
| 2605 | mii = mbbi->erase(mii); |
| 2606 | ++numPeep; |
| 2607 | continue; |
| 2608 | } |
| 2609 | |
Evan Cheng | 20580a1 | 2008-09-19 17:38:47 +0000 | [diff] [blame] | 2610 | // Now check if this is a remat'ed def instruction which is now dead. |
| 2611 | if (ReMatDefs.count(MI)) { |
| 2612 | bool isDead = true; |
| 2613 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
| 2614 | const MachineOperand &MO = MI->getOperand(i); |
Evan Cheng | b3990d5 | 2008-10-27 23:21:01 +0000 | [diff] [blame] | 2615 | if (!MO.isReg()) |
Evan Cheng | 20580a1 | 2008-09-19 17:38:47 +0000 | [diff] [blame] | 2616 | continue; |
| 2617 | unsigned Reg = MO.getReg(); |
Evan Cheng | 6792e90 | 2009-02-04 18:18:58 +0000 | [diff] [blame] | 2618 | if (!Reg) |
| 2619 | continue; |
Evan Cheng | b3990d5 | 2008-10-27 23:21:01 +0000 | [diff] [blame] | 2620 | if (TargetRegisterInfo::isVirtualRegister(Reg)) |
| 2621 | DeadDefs.push_back(Reg); |
| 2622 | if (MO.isDead()) |
| 2623 | continue; |
Evan Cheng | 20580a1 | 2008-09-19 17:38:47 +0000 | [diff] [blame] | 2624 | if (TargetRegisterInfo::isPhysicalRegister(Reg) || |
| 2625 | !mri_->use_empty(Reg)) { |
| 2626 | isDead = false; |
| 2627 | break; |
| 2628 | } |
| 2629 | } |
| 2630 | if (isDead) { |
Evan Cheng | b3990d5 | 2008-10-27 23:21:01 +0000 | [diff] [blame] | 2631 | while (!DeadDefs.empty()) { |
| 2632 | unsigned DeadDef = DeadDefs.back(); |
| 2633 | DeadDefs.pop_back(); |
| 2634 | RemoveDeadDef(li_->getInterval(DeadDef), MI); |
| 2635 | } |
Evan Cheng | 20580a1 | 2008-09-19 17:38:47 +0000 | [diff] [blame] | 2636 | li_->RemoveMachineInstrFromMaps(mii); |
| 2637 | mii = mbbi->erase(mii); |
Evan Cheng | fee2d69 | 2008-09-19 22:49:39 +0000 | [diff] [blame] | 2638 | continue; |
Evan Cheng | b3990d5 | 2008-10-27 23:21:01 +0000 | [diff] [blame] | 2639 | } else |
| 2640 | DeadDefs.clear(); |
Evan Cheng | 20580a1 | 2008-09-19 17:38:47 +0000 | [diff] [blame] | 2641 | } |
| 2642 | |
Evan Cheng | a971dbd | 2008-04-24 09:06:33 +0000 | [diff] [blame] | 2643 | // If the move will be an identity move delete it |
Evan Cheng | 04ee5a1 | 2009-01-20 19:12:24 +0000 | [diff] [blame] | 2644 | bool isMove= tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx); |
Evan Cheng | a971dbd | 2008-04-24 09:06:33 +0000 | [diff] [blame] | 2645 | if (isMove && SrcReg == DstReg) { |
| 2646 | if (li_->hasInterval(SrcReg)) { |
| 2647 | LiveInterval &RegInt = li_->getInterval(SrcReg); |
Evan Cheng | 3c88d74 | 2008-03-18 08:26:47 +0000 | [diff] [blame] | 2648 | // If def of this move instruction is dead, remove its live range |
| 2649 | // from the dstination register's live interval. |
Evan Cheng | 20580a1 | 2008-09-19 17:38:47 +0000 | [diff] [blame] | 2650 | if (MI->registerDefIsDead(DstReg)) { |
| 2651 | if (!ShortenDeadCopySrcLiveRange(RegInt, MI)) |
| 2652 | ShortenDeadCopyLiveRange(RegInt, MI); |
Evan Cheng | 3c88d74 | 2008-03-18 08:26:47 +0000 | [diff] [blame] | 2653 | } |
| 2654 | } |
Evan Cheng | 20580a1 | 2008-09-19 17:38:47 +0000 | [diff] [blame] | 2655 | li_->RemoveMachineInstrFromMaps(MI); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2656 | mii = mbbi->erase(mii); |
| 2657 | ++numPeep; |
Evan Cheng | 0768f0e | 2009-07-17 21:06:58 +0000 | [diff] [blame] | 2658 | } else { |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2659 | SmallSet<unsigned, 4> UniqueUses; |
Evan Cheng | 20580a1 | 2008-09-19 17:38:47 +0000 | [diff] [blame] | 2660 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
| 2661 | const MachineOperand &mop = MI->getOperand(i); |
Dan Gohman | d735b80 | 2008-10-03 15:45:36 +0000 | [diff] [blame] | 2662 | if (mop.isReg() && mop.getReg() && |
Dan Gohman | 6f0d024 | 2008-02-10 18:45:23 +0000 | [diff] [blame] | 2663 | TargetRegisterInfo::isVirtualRegister(mop.getReg())) { |
Evan Cheng | c8d044e | 2008-02-15 18:24:29 +0000 | [diff] [blame] | 2664 | unsigned reg = mop.getReg(); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2665 | // Multiple uses of reg by the same instruction. It should not |
| 2666 | // contribute to spill weight again. |
| 2667 | if (UniqueUses.count(reg) != 0) |
| 2668 | continue; |
| 2669 | LiveInterval &RegInt = li_->getInterval(reg); |
Evan Cheng | 81a0382 | 2007-11-17 00:40:40 +0000 | [diff] [blame] | 2670 | RegInt.weight += |
Evan Cheng | c341760 | 2008-06-21 06:45:54 +0000 | [diff] [blame] | 2671 | li_->getSpillWeight(mop.isDef(), mop.isUse(), loopDepth); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2672 | UniqueUses.insert(reg); |
| 2673 | } |
| 2674 | } |
| 2675 | ++mii; |
| 2676 | } |
| 2677 | } |
| 2678 | } |
| 2679 | |
| 2680 | for (LiveIntervals::iterator I = li_->begin(), E = li_->end(); I != E; ++I) { |
Owen Anderson | 03857b2 | 2008-08-13 21:49:13 +0000 | [diff] [blame] | 2681 | LiveInterval &LI = *I->second; |
Dan Gohman | 6f0d024 | 2008-02-10 18:45:23 +0000 | [diff] [blame] | 2682 | if (TargetRegisterInfo::isVirtualRegister(LI.reg)) { |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2683 | // If the live interval length is essentially zero, i.e. in every live |
| 2684 | // range the use follows def immediately, it doesn't make sense to spill |
| 2685 | // it and hope it will be easier to allocate for this li. |
| 2686 | if (isZeroLengthInterval(&LI)) |
| 2687 | LI.weight = HUGE_VALF; |
Evan Cheng | 5ef3a04 | 2007-12-06 00:01:56 +0000 | [diff] [blame] | 2688 | else { |
| 2689 | bool isLoad = false; |
Evan Cheng | dc37786 | 2008-09-30 15:44:16 +0000 | [diff] [blame] | 2690 | SmallVector<LiveInterval*, 4> SpillIs; |
| 2691 | if (li_->isReMaterializable(LI, SpillIs, isLoad)) { |
Evan Cheng | 5ef3a04 | 2007-12-06 00:01:56 +0000 | [diff] [blame] | 2692 | // If all of the definitions of the interval are re-materializable, |
| 2693 | // it is a preferred candidate for spilling. If non of the defs are |
| 2694 | // loads, then it's potentially very cheap to re-materialize. |
| 2695 | // FIXME: this gets much more complicated once we support non-trivial |
| 2696 | // re-materialization. |
| 2697 | if (isLoad) |
| 2698 | LI.weight *= 0.9F; |
| 2699 | else |
| 2700 | LI.weight *= 0.5F; |
| 2701 | } |
| 2702 | } |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2703 | |
| 2704 | // Slightly prefer live interval that has been assigned a preferred reg. |
Evan Cheng | 358dec5 | 2009-06-15 08:28:29 +0000 | [diff] [blame] | 2705 | std::pair<unsigned, unsigned> Hint = mri_->getRegAllocationHint(LI.reg); |
| 2706 | if (Hint.first || Hint.second) |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2707 | LI.weight *= 1.01F; |
| 2708 | |
Daniel Dunbar | a279bc3 | 2009-09-20 02:20:51 +0000 | [diff] [blame^] | 2709 | // Divide the weight of the interval by its size. This encourages |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2710 | // spilling of intervals that are large and have few uses, and |
| 2711 | // discourages spilling of small intervals with many uses. |
Owen Anderson | 496bac5 | 2008-07-23 19:47:27 +0000 | [diff] [blame] | 2712 | LI.weight /= li_->getApproximateInstructionCount(LI) * InstrSlots::NUM; |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2713 | } |
| 2714 | } |
| 2715 | |
| 2716 | DEBUG(dump()); |
| 2717 | return true; |
| 2718 | } |
| 2719 | |
| 2720 | /// print - Implement the dump method. |
Chris Lattner | 45cfe54 | 2009-08-23 06:03:38 +0000 | [diff] [blame] | 2721 | void SimpleRegisterCoalescing::print(raw_ostream &O, const Module* m) const { |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 2722 | li_->print(O, m); |
| 2723 | } |
David Greene | 2c17c4d | 2007-09-06 16:18:45 +0000 | [diff] [blame] | 2724 | |
| 2725 | RegisterCoalescer* llvm::createSimpleRegisterCoalescer() { |
| 2726 | return new SimpleRegisterCoalescing(); |
| 2727 | } |
| 2728 | |
| 2729 | // Make sure that anything that uses RegisterCoalescer pulls in this file... |
| 2730 | DEFINING_FILE_FOR(SimpleRegisterCoalescing) |