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