Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 1 | //===- subzero/src/IceRegAlloc.cpp - Linear-scan implementation -----------===// |
| 2 | // |
| 3 | // The Subzero Code Generator |
| 4 | // |
| 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 9 | /// |
| 10 | /// \file |
Jim Stichnoth | 92a6e5b | 2015-12-02 16:52:44 -0800 | [diff] [blame] | 11 | /// \brief Implements the LinearScan class, which performs the linear-scan |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 12 | /// register allocation after liveness analysis has been performed. |
Andrew Scull | 9612d32 | 2015-07-06 14:53:25 -0700 | [diff] [blame] | 13 | /// |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 14 | //===----------------------------------------------------------------------===// |
| 15 | |
John Porto | 67f8de9 | 2015-06-25 10:14:17 -0700 | [diff] [blame] | 16 | #include "IceRegAlloc.h" |
| 17 | |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 18 | #include "IceBitVector.h" |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 19 | #include "IceCfg.h" |
Jim Stichnoth | 87ff3a1 | 2014-11-14 10:27:29 -0800 | [diff] [blame] | 20 | #include "IceCfgNode.h" |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 21 | #include "IceInst.h" |
John Porto | ec3f565 | 2015-08-31 15:07:09 -0700 | [diff] [blame] | 22 | #include "IceInstVarIter.h" |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 23 | #include "IceOperand.h" |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 24 | #include "IceTargetLowering.h" |
| 25 | |
Jim Stichnoth | 11756b5 | 2016-04-06 12:20:18 -0700 | [diff] [blame] | 26 | #include "llvm/Support/Format.h" |
| 27 | |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 28 | namespace Ice { |
| 29 | |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 30 | namespace { |
| 31 | |
| 32 | // Returns true if Var has any definitions within Item's live range. |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 33 | // TODO(stichnot): Consider trimming the Definitions list similar to how the |
| 34 | // live ranges are trimmed, since all the overlapsDefs() tests are whether some |
| 35 | // variable's definitions overlap Cur, and trimming is with respect Cur.start. |
| 36 | // Initial tests show no measurable performance difference, so we'll keep the |
| 37 | // code simple for now. |
Jim Stichnoth | 5ce0abb | 2014-10-15 10:16:54 -0700 | [diff] [blame] | 38 | bool overlapsDefs(const Cfg *Func, const Variable *Item, const Variable *Var) { |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 39 | constexpr bool UseTrimmed = true; |
Jim Stichnoth | 037fa1d | 2014-10-07 11:09:33 -0700 | [diff] [blame] | 40 | VariablesMetadata *VMetadata = Func->getVMetadata(); |
Jim Stichnoth | 877b04e | 2014-10-15 15:13:06 -0700 | [diff] [blame] | 41 | if (const Inst *FirstDef = VMetadata->getFirstDefinition(Var)) |
| 42 | if (Item->getLiveRange().overlapsInst(FirstDef->getNumber(), UseTrimmed)) |
| 43 | return true; |
Jim Stichnoth | 48e3ae5 | 2015-10-01 13:33:35 -0700 | [diff] [blame] | 44 | for (const Inst *Def : VMetadata->getLatterDefinitions(Var)) { |
| 45 | if (Item->getLiveRange().overlapsInst(Def->getNumber(), UseTrimmed)) |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 46 | return true; |
| 47 | } |
| 48 | return false; |
| 49 | } |
| 50 | |
| 51 | void dumpDisableOverlap(const Cfg *Func, const Variable *Var, |
| 52 | const char *Reason) { |
Jim Stichnoth | 20b71f5 | 2015-06-24 15:52:24 -0700 | [diff] [blame] | 53 | if (!BuildDefs::dump()) |
Karl Schimpf | b6c96af | 2014-11-17 10:58:39 -0800 | [diff] [blame] | 54 | return; |
Jim Stichnoth | a1da6ff | 2015-11-16 15:59:39 -0800 | [diff] [blame] | 55 | if (!Func->isVerbose(IceV_LinearScan)) |
| 56 | return; |
| 57 | |
| 58 | VariablesMetadata *VMetadata = Func->getVMetadata(); |
| 59 | Ostream &Str = Func->getContext()->getStrDump(); |
| 60 | Str << "Disabling Overlap due to " << Reason << " " << *Var |
| 61 | << " LIVE=" << Var->getLiveRange() << " Defs="; |
| 62 | if (const Inst *FirstDef = VMetadata->getFirstDefinition(Var)) |
| 63 | Str << FirstDef->getNumber(); |
| 64 | const InstDefList &Defs = VMetadata->getLatterDefinitions(Var); |
| 65 | for (size_t i = 0; i < Defs.size(); ++i) { |
| 66 | Str << "," << Defs[i]->getNumber(); |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 67 | } |
Jim Stichnoth | a1da6ff | 2015-11-16 15:59:39 -0800 | [diff] [blame] | 68 | Str << "\n"; |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 69 | } |
| 70 | |
Jim Stichnoth | 5ce0abb | 2014-10-15 10:16:54 -0700 | [diff] [blame] | 71 | void dumpLiveRange(const Variable *Var, const Cfg *Func) { |
Jim Stichnoth | 20b71f5 | 2015-06-24 15:52:24 -0700 | [diff] [blame] | 72 | if (!BuildDefs::dump()) |
Karl Schimpf | b6c96af | 2014-11-17 10:58:39 -0800 | [diff] [blame] | 73 | return; |
Jim Stichnoth | 5ce0abb | 2014-10-15 10:16:54 -0700 | [diff] [blame] | 74 | Ostream &Str = Func->getContext()->getStrDump(); |
Jim Stichnoth | 11756b5 | 2016-04-06 12:20:18 -0700 | [diff] [blame] | 75 | Str << "R="; |
| 76 | if (Var->hasRegTmp()) { |
| 77 | Str << llvm::format("%2d", Var->getRegNumTmp()); |
| 78 | } else { |
| 79 | Str << "NA"; |
| 80 | } |
| 81 | Str << " V="; |
Jim Stichnoth | 5ce0abb | 2014-10-15 10:16:54 -0700 | [diff] [blame] | 82 | Var->dump(Func); |
| 83 | Str << " Range=" << Var->getLiveRange(); |
Jim Stichnoth | e22f823 | 2014-10-13 16:20:59 -0700 | [diff] [blame] | 84 | } |
| 85 | |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 86 | int32_t findMinWeightIndex( |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 87 | const SmallBitVector &RegMask, |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 88 | const llvm::SmallVector<RegWeight, LinearScan::REGS_SIZE> &Weights) { |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 89 | int MinWeightIndex = -1; |
| 90 | for (RegNumT i : RegNumBVIter(RegMask)) { |
| 91 | if (MinWeightIndex < 0 || Weights[i] < Weights[MinWeightIndex]) |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 92 | MinWeightIndex = i; |
| 93 | } |
Jim Stichnoth | 2655d96 | 2016-04-21 05:38:15 -0700 | [diff] [blame] | 94 | assert(getFlags().getRegAllocReserve() || MinWeightIndex >= 0); |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 95 | return MinWeightIndex; |
| 96 | } |
| 97 | |
Jim Stichnoth | ad40353 | 2014-09-25 12:44:17 -0700 | [diff] [blame] | 98 | } // end of anonymous namespace |
| 99 | |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 100 | LinearScan::LinearScan(Cfg *Func) |
John Porto | bb0a5fe | 2015-09-04 11:23:41 -0700 | [diff] [blame] | 101 | : Func(Func), Ctx(Func->getContext()), Target(Func->getTarget()), |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 102 | Verbose(BuildDefs::dump() && Func->isVerbose(IceV_LinearScan)), |
Karl Schimpf | d469994 | 2016-04-02 09:55:31 -0700 | [diff] [blame] | 103 | UseReserve(getFlags().getRegAllocReserve()) {} |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 104 | |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 105 | // Prepare for full register allocation of all variables. We depend on liveness |
| 106 | // analysis to have calculated live ranges. |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 107 | void LinearScan::initForGlobal() { |
Jim Stichnoth | 87ff3a1 | 2014-11-14 10:27:29 -0800 | [diff] [blame] | 108 | TimerMarker T(TimerStack::TT_initUnhandled, Func); |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 109 | FindPreference = true; |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 110 | // For full register allocation, normally we want to enable FindOverlap |
| 111 | // (meaning we look for opportunities for two overlapping live ranges to |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 112 | // safely share the same register). However, we disable it for phi-lowering |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 113 | // register allocation since no overlap opportunities should be available and |
| 114 | // it's more expensive to look for opportunities. |
| 115 | FindOverlap = (Kind != RAK_Phi); |
Jim Stichnoth | 87ff3a1 | 2014-11-14 10:27:29 -0800 | [diff] [blame] | 116 | Unhandled.reserve(Vars.size()); |
Jim Stichnoth | 4ead35a | 2014-12-03 20:30:34 -0800 | [diff] [blame] | 117 | UnhandledPrecolored.reserve(Vars.size()); |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 118 | // Gather the live ranges of all variables and add them to the Unhandled set. |
Jim Stichnoth | 87ff3a1 | 2014-11-14 10:27:29 -0800 | [diff] [blame] | 119 | for (Variable *Var : Vars) { |
Jim Stichnoth | 4c5c571 | 2015-11-16 17:17:48 -0800 | [diff] [blame] | 120 | // Don't consider rematerializable variables. |
| 121 | if (Var->isRematerializable()) |
| 122 | continue; |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 123 | // Explicitly don't consider zero-weight variables, which are meant to be |
| 124 | // spill slots. |
Andrew Scull | 11c9a32 | 2015-08-28 14:24:14 -0700 | [diff] [blame] | 125 | if (Var->mustNotHaveReg()) |
Jim Stichnoth | 87ff3a1 | 2014-11-14 10:27:29 -0800 | [diff] [blame] | 126 | continue; |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 127 | // Don't bother if the variable has a null live range, which means it was |
| 128 | // never referenced. |
Jim Stichnoth | 87ff3a1 | 2014-11-14 10:27:29 -0800 | [diff] [blame] | 129 | if (Var->getLiveRange().isEmpty()) |
| 130 | continue; |
| 131 | Var->untrimLiveRange(); |
| 132 | Unhandled.push_back(Var); |
| 133 | if (Var->hasReg()) { |
| 134 | Var->setRegNumTmp(Var->getRegNum()); |
Andrew Scull | 11c9a32 | 2015-08-28 14:24:14 -0700 | [diff] [blame] | 135 | Var->setMustHaveReg(); |
Jim Stichnoth | 87ff3a1 | 2014-11-14 10:27:29 -0800 | [diff] [blame] | 136 | UnhandledPrecolored.push_back(Var); |
| 137 | } |
| 138 | } |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 139 | |
| 140 | // Build the (ordered) list of FakeKill instruction numbers. |
| 141 | Kills.clear(); |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 142 | // Phi lowering should not be creating new call instructions, so there should |
| 143 | // be no infinite-weight not-yet-colored live ranges that span a call |
| 144 | // instruction, hence no need to construct the Kills list. |
| 145 | if (Kind == RAK_Phi) |
| 146 | return; |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 147 | for (CfgNode *Node : Func->getNodes()) { |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 148 | for (Inst &I : Node->getInsts()) { |
Jim Stichnoth | 5bff61c | 2015-10-28 09:26:00 -0700 | [diff] [blame] | 149 | if (auto *Kill = llvm::dyn_cast<InstFakeKill>(&I)) { |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 150 | if (!Kill->isDeleted() && !Kill->getLinked()->isDeleted()) |
Jim Stichnoth | 29841e8 | 2014-12-23 12:26:24 -0800 | [diff] [blame] | 151 | Kills.push_back(I.getNumber()); |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 152 | } |
| 153 | } |
| 154 | } |
| 155 | } |
| 156 | |
Jim Stichnoth | 230d410 | 2015-09-25 17:40:32 -0700 | [diff] [blame] | 157 | // Validate the integrity of the live ranges. If there are any errors, it |
| 158 | // prints details and returns false. On success, it returns true. |
| 159 | bool LinearScan::livenessValidateIntervals( |
| 160 | const DefUseErrorList &DefsWithoutUses, |
| 161 | const DefUseErrorList &UsesBeforeDefs, |
| 162 | const CfgVector<InstNumberT> &LRBegin, |
Jim Stichnoth | 318f4cd | 2015-10-01 21:02:37 -0700 | [diff] [blame] | 163 | const CfgVector<InstNumberT> &LREnd) const { |
Jim Stichnoth | 230d410 | 2015-09-25 17:40:32 -0700 | [diff] [blame] | 164 | if (DefsWithoutUses.empty() && UsesBeforeDefs.empty()) |
| 165 | return true; |
| 166 | |
| 167 | if (!BuildDefs::dump()) |
| 168 | return false; |
| 169 | |
Jim Stichnoth | 230d410 | 2015-09-25 17:40:32 -0700 | [diff] [blame] | 170 | OstreamLocker L(Ctx); |
| 171 | Ostream &Str = Ctx->getStrDump(); |
| 172 | for (SizeT VarNum : DefsWithoutUses) { |
| 173 | Variable *Var = Vars[VarNum]; |
| 174 | Str << "LR def without use, instruction " << LRBegin[VarNum] |
Jim Stichnoth | a91c341 | 2016-04-05 15:31:43 -0700 | [diff] [blame] | 175 | << ", variable " << Var->getName() << "\n"; |
Jim Stichnoth | 230d410 | 2015-09-25 17:40:32 -0700 | [diff] [blame] | 176 | } |
| 177 | for (SizeT VarNum : UsesBeforeDefs) { |
| 178 | Variable *Var = Vars[VarNum]; |
| 179 | Str << "LR use before def, instruction " << LREnd[VarNum] << ", variable " |
Jim Stichnoth | a91c341 | 2016-04-05 15:31:43 -0700 | [diff] [blame] | 180 | << Var->getName() << "\n"; |
Jim Stichnoth | 230d410 | 2015-09-25 17:40:32 -0700 | [diff] [blame] | 181 | } |
| 182 | return false; |
| 183 | } |
| 184 | |
Jim Stichnoth | a1da6ff | 2015-11-16 15:59:39 -0800 | [diff] [blame] | 185 | // Prepare for very simple register allocation of only infinite-weight Variables |
| 186 | // while respecting pre-colored Variables. Some properties we take advantage of: |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 187 | // |
| 188 | // * Live ranges of interest consist of a single segment. |
| 189 | // |
| 190 | // * Live ranges of interest never span a call instruction. |
| 191 | // |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 192 | // * Phi instructions are not considered because either phis have already been |
| 193 | // lowered, or they don't contain any pre-colored or infinite-weight |
| 194 | // Variables. |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 195 | // |
Jim Stichnoth | a1da6ff | 2015-11-16 15:59:39 -0800 | [diff] [blame] | 196 | // * We don't need to renumber instructions before computing live ranges because |
| 197 | // all the high-level ICE instructions are deleted prior to lowering, and the |
| 198 | // low-level instructions are added in monotonically increasing order. |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 199 | // |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 200 | // * There are no opportunities for register preference or allowing overlap. |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 201 | // |
| 202 | // Some properties we aren't (yet) taking advantage of: |
| 203 | // |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 204 | // * Because live ranges are a single segment, the Inactive set will always be |
| 205 | // empty, and the live range trimming operation is unnecessary. |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 206 | // |
Jim Stichnoth | a1da6ff | 2015-11-16 15:59:39 -0800 | [diff] [blame] | 207 | // * Calculating overlap of single-segment live ranges could be optimized a bit. |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 208 | void LinearScan::initForInfOnly() { |
| 209 | TimerMarker T(TimerStack::TT_initUnhandled, Func); |
| 210 | FindPreference = false; |
| 211 | FindOverlap = false; |
| 212 | SizeT NumVars = 0; |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 213 | |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 214 | // Iterate across all instructions and record the begin and end of the live |
| 215 | // range for each variable that is pre-colored or infinite weight. |
Andrew Scull | 00741a0 | 2015-09-16 19:04:09 -0700 | [diff] [blame] | 216 | CfgVector<InstNumberT> LRBegin(Vars.size(), Inst::NumberSentinel); |
| 217 | CfgVector<InstNumberT> LREnd(Vars.size(), Inst::NumberSentinel); |
Jim Stichnoth | 230d410 | 2015-09-25 17:40:32 -0700 | [diff] [blame] | 218 | DefUseErrorList DefsWithoutUses, UsesBeforeDefs; |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 219 | for (CfgNode *Node : Func->getNodes()) { |
Jim Stichnoth | 8cfeb69 | 2016-02-05 09:50:02 -0800 | [diff] [blame] | 220 | for (Inst &Instr : Node->getInsts()) { |
| 221 | if (Instr.isDeleted()) |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 222 | continue; |
Jim Stichnoth | 8cfeb69 | 2016-02-05 09:50:02 -0800 | [diff] [blame] | 223 | FOREACH_VAR_IN_INST(Var, Instr) { |
Jim Stichnoth | 230d410 | 2015-09-25 17:40:32 -0700 | [diff] [blame] | 224 | if (Var->getIgnoreLiveness()) |
| 225 | continue; |
| 226 | if (Var->hasReg() || Var->mustHaveReg()) { |
| 227 | SizeT VarNum = Var->getIndex(); |
Jim Stichnoth | 8cfeb69 | 2016-02-05 09:50:02 -0800 | [diff] [blame] | 228 | LREnd[VarNum] = Instr.getNumber(); |
Jim Stichnoth | 230d410 | 2015-09-25 17:40:32 -0700 | [diff] [blame] | 229 | if (!Var->getIsArg() && LRBegin[VarNum] == Inst::NumberSentinel) |
| 230 | UsesBeforeDefs.push_back(VarNum); |
| 231 | } |
| 232 | } |
Jim Stichnoth | 8cfeb69 | 2016-02-05 09:50:02 -0800 | [diff] [blame] | 233 | if (const Variable *Var = Instr.getDest()) { |
Jim Stichnoth | cc89c95 | 2016-03-31 11:55:23 -0700 | [diff] [blame] | 234 | if (!Var->getIgnoreLiveness() && |
Andrew Scull | 11c9a32 | 2015-08-28 14:24:14 -0700 | [diff] [blame] | 235 | (Var->hasReg() || Var->mustHaveReg())) { |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 236 | if (LRBegin[Var->getIndex()] == Inst::NumberSentinel) { |
Jim Stichnoth | 8cfeb69 | 2016-02-05 09:50:02 -0800 | [diff] [blame] | 237 | LRBegin[Var->getIndex()] = Instr.getNumber(); |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 238 | ++NumVars; |
| 239 | } |
| 240 | } |
| 241 | } |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 242 | } |
| 243 | } |
| 244 | |
| 245 | Unhandled.reserve(NumVars); |
Jim Stichnoth | 4ead35a | 2014-12-03 20:30:34 -0800 | [diff] [blame] | 246 | UnhandledPrecolored.reserve(NumVars); |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 247 | for (SizeT i = 0; i < Vars.size(); ++i) { |
| 248 | Variable *Var = Vars[i]; |
Jim Stichnoth | 4c5c571 | 2015-11-16 17:17:48 -0800 | [diff] [blame] | 249 | if (Var->isRematerializable()) |
| 250 | continue; |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 251 | if (LRBegin[i] != Inst::NumberSentinel) { |
Jim Stichnoth | 230d410 | 2015-09-25 17:40:32 -0700 | [diff] [blame] | 252 | if (LREnd[i] == Inst::NumberSentinel) { |
| 253 | DefsWithoutUses.push_back(i); |
| 254 | continue; |
| 255 | } |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 256 | Unhandled.push_back(Var); |
| 257 | Var->resetLiveRange(); |
Andrew Scull | 11c9a32 | 2015-08-28 14:24:14 -0700 | [diff] [blame] | 258 | Var->addLiveRange(LRBegin[i], LREnd[i]); |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 259 | Var->untrimLiveRange(); |
| 260 | if (Var->hasReg()) { |
| 261 | Var->setRegNumTmp(Var->getRegNum()); |
Andrew Scull | 11c9a32 | 2015-08-28 14:24:14 -0700 | [diff] [blame] | 262 | Var->setMustHaveReg(); |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 263 | UnhandledPrecolored.push_back(Var); |
| 264 | } |
| 265 | --NumVars; |
| 266 | } |
| 267 | } |
Jim Stichnoth | 230d410 | 2015-09-25 17:40:32 -0700 | [diff] [blame] | 268 | |
| 269 | if (!livenessValidateIntervals(DefsWithoutUses, UsesBeforeDefs, LRBegin, |
| 270 | LREnd)) { |
| 271 | llvm::report_fatal_error("initForInfOnly: Liveness error"); |
| 272 | return; |
| 273 | } |
| 274 | |
| 275 | if (!DefsWithoutUses.empty() || !UsesBeforeDefs.empty()) { |
| 276 | if (BuildDefs::dump()) { |
| 277 | OstreamLocker L(Ctx); |
| 278 | Ostream &Str = Ctx->getStrDump(); |
| 279 | for (SizeT VarNum : DefsWithoutUses) { |
| 280 | Variable *Var = Vars[VarNum]; |
| 281 | Str << "LR def without use, instruction " << LRBegin[VarNum] |
Jim Stichnoth | a91c341 | 2016-04-05 15:31:43 -0700 | [diff] [blame] | 282 | << ", variable " << Var->getName() << "\n"; |
Jim Stichnoth | 230d410 | 2015-09-25 17:40:32 -0700 | [diff] [blame] | 283 | } |
| 284 | for (SizeT VarNum : UsesBeforeDefs) { |
| 285 | Variable *Var = Vars[VarNum]; |
| 286 | Str << "LR use before def, instruction " << LREnd[VarNum] |
Jim Stichnoth | a91c341 | 2016-04-05 15:31:43 -0700 | [diff] [blame] | 287 | << ", variable " << Var->getName() << "\n"; |
Jim Stichnoth | 230d410 | 2015-09-25 17:40:32 -0700 | [diff] [blame] | 288 | } |
| 289 | } |
| 290 | llvm::report_fatal_error("initForInfOnly: Liveness error"); |
| 291 | } |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 292 | // This isn't actually a fatal condition, but it would be nice to know if we |
| 293 | // somehow pre-calculated Unhandled's size wrong. |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 294 | assert(NumVars == 0); |
| 295 | |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 296 | // Don't build up the list of Kills because we know that no infinite-weight |
| 297 | // Variable has a live range spanning a call. |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 298 | Kills.clear(); |
| 299 | } |
| 300 | |
Jim Stichnoth | 4001c93 | 2015-10-09 14:33:26 -0700 | [diff] [blame] | 301 | void LinearScan::initForSecondChance() { |
| 302 | TimerMarker T(TimerStack::TT_initUnhandled, Func); |
| 303 | FindPreference = true; |
| 304 | FindOverlap = true; |
| 305 | const VarList &Vars = Func->getVariables(); |
| 306 | Unhandled.reserve(Vars.size()); |
| 307 | UnhandledPrecolored.reserve(Vars.size()); |
| 308 | for (Variable *Var : Vars) { |
Jim Stichnoth | 4c5c571 | 2015-11-16 17:17:48 -0800 | [diff] [blame] | 309 | if (Var->isRematerializable()) |
| 310 | continue; |
Jim Stichnoth | 4001c93 | 2015-10-09 14:33:26 -0700 | [diff] [blame] | 311 | if (Var->hasReg()) { |
| 312 | Var->untrimLiveRange(); |
| 313 | Var->setRegNumTmp(Var->getRegNum()); |
| 314 | Var->setMustHaveReg(); |
| 315 | UnhandledPrecolored.push_back(Var); |
| 316 | Unhandled.push_back(Var); |
| 317 | } |
| 318 | } |
| 319 | for (Variable *Var : Evicted) { |
| 320 | Var->untrimLiveRange(); |
| 321 | Unhandled.push_back(Var); |
| 322 | } |
| 323 | } |
| 324 | |
Manasij Mukherjee | 7cd926d | 2016-08-04 12:33:23 -0700 | [diff] [blame^] | 325 | void LinearScan::init(RegAllocKind Kind, CfgSet<Variable *> ExcludeVars) { |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 326 | this->Kind = Kind; |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 327 | Unhandled.clear(); |
| 328 | UnhandledPrecolored.clear(); |
| 329 | Handled.clear(); |
| 330 | Inactive.clear(); |
| 331 | Active.clear(); |
Manasij Mukherjee | 7cd926d | 2016-08-04 12:33:23 -0700 | [diff] [blame^] | 332 | Vars.clear(); |
| 333 | Vars.reserve(Func->getVariables().size() - ExcludeVars.size()); |
| 334 | for (auto *Var : Func->getVariables()) { |
| 335 | if (ExcludeVars.find(Var) == ExcludeVars.end()) |
| 336 | Vars.emplace_back(Var); |
| 337 | } |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 338 | |
John Porto | bb0a5fe | 2015-09-04 11:23:41 -0700 | [diff] [blame] | 339 | SizeT NumRegs = Target->getNumRegisters(); |
| 340 | RegAliases.resize(NumRegs); |
| 341 | for (SizeT Reg = 0; Reg < NumRegs; ++Reg) { |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 342 | RegAliases[Reg] = &Target->getAliasesForRegister(RegNumT::fromInt(Reg)); |
John Porto | bb0a5fe | 2015-09-04 11:23:41 -0700 | [diff] [blame] | 343 | } |
| 344 | |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 345 | switch (Kind) { |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 346 | case RAK_Unknown: |
| 347 | llvm::report_fatal_error("Invalid RAK_Unknown"); |
| 348 | break; |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 349 | case RAK_Global: |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 350 | case RAK_Phi: |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 351 | initForGlobal(); |
| 352 | break; |
| 353 | case RAK_InfOnly: |
| 354 | initForInfOnly(); |
| 355 | break; |
Jim Stichnoth | 4001c93 | 2015-10-09 14:33:26 -0700 | [diff] [blame] | 356 | case RAK_SecondChance: |
| 357 | initForSecondChance(); |
| 358 | break; |
Jim Stichnoth | 70d0a05 | 2014-11-14 15:53:46 -0800 | [diff] [blame] | 359 | } |
| 360 | |
Jim Stichnoth | 4001c93 | 2015-10-09 14:33:26 -0700 | [diff] [blame] | 361 | Evicted.clear(); |
| 362 | |
Jim Stichnoth | 992f91d | 2015-08-10 11:18:38 -0700 | [diff] [blame] | 363 | auto CompareRanges = [](const Variable *L, const Variable *R) { |
Qining Lu | aee5fa8 | 2015-08-20 14:59:03 -0700 | [diff] [blame] | 364 | InstNumberT Lstart = L->getLiveRange().getStart(); |
| 365 | InstNumberT Rstart = R->getLiveRange().getStart(); |
| 366 | if (Lstart == Rstart) |
| 367 | return L->getIndex() < R->getIndex(); |
| 368 | return Lstart < Rstart; |
Jim Stichnoth | 87ff3a1 | 2014-11-14 10:27:29 -0800 | [diff] [blame] | 369 | }; |
| 370 | // Do a reverse sort so that erasing elements (from the end) is fast. |
Jim Stichnoth | 992f91d | 2015-08-10 11:18:38 -0700 | [diff] [blame] | 371 | std::sort(Unhandled.rbegin(), Unhandled.rend(), CompareRanges); |
Jim Stichnoth | 87ff3a1 | 2014-11-14 10:27:29 -0800 | [diff] [blame] | 372 | std::sort(UnhandledPrecolored.rbegin(), UnhandledPrecolored.rend(), |
Jim Stichnoth | 992f91d | 2015-08-10 11:18:38 -0700 | [diff] [blame] | 373 | CompareRanges); |
Jim Stichnoth | 4ead35a | 2014-12-03 20:30:34 -0800 | [diff] [blame] | 374 | |
| 375 | Handled.reserve(Unhandled.size()); |
| 376 | Inactive.reserve(Unhandled.size()); |
| 377 | Active.reserve(Unhandled.size()); |
Jim Stichnoth | 4001c93 | 2015-10-09 14:33:26 -0700 | [diff] [blame] | 378 | Evicted.reserve(Unhandled.size()); |
Jim Stichnoth | 87ff3a1 | 2014-11-14 10:27:29 -0800 | [diff] [blame] | 379 | } |
| 380 | |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 381 | // This is called when Cur must be allocated a register but no registers are |
Jim Stichnoth | a1da6ff | 2015-11-16 15:59:39 -0800 | [diff] [blame] | 382 | // available across Cur's live range. To handle this, we find a register that is |
| 383 | // not explicitly used during Cur's live range, spill that register to a stack |
| 384 | // location right before Cur's live range begins, and fill (reload) the register |
| 385 | // from the stack location right after Cur's live range ends. |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 386 | void LinearScan::addSpillFill(IterationState &Iter) { |
| 387 | // Identify the actual instructions that begin and end Iter.Cur's live range. |
| 388 | // Iterate through Iter.Cur's node's instruction list until we find the actual |
| 389 | // instructions with instruction numbers corresponding to Iter.Cur's recorded |
| 390 | // live range endpoints. This sounds inefficient but shouldn't be a problem |
| 391 | // in practice because: |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 392 | // (1) This function is almost never called in practice. |
| 393 | // (2) Since this register over-subscription problem happens only for |
| 394 | // phi-lowered instructions, the number of instructions in the node is |
| 395 | // proportional to the number of phi instructions in the original node, |
| 396 | // which is never very large in practice. |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 397 | // (3) We still have to iterate through all instructions of Iter.Cur's live |
| 398 | // range to find all explicitly used registers (though the live range is |
| 399 | // usually only 2-3 instructions), so the main cost that could be avoided |
| 400 | // would be finding the instruction that begin's Iter.Cur's live range. |
| 401 | assert(!Iter.Cur->getLiveRange().isEmpty()); |
| 402 | InstNumberT Start = Iter.Cur->getLiveRange().getStart(); |
| 403 | InstNumberT End = Iter.Cur->getLiveRange().getEnd(); |
| 404 | CfgNode *Node = Func->getVMetadata()->getLocalUseNode(Iter.Cur); |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 405 | assert(Node); |
| 406 | InstList &Insts = Node->getInsts(); |
| 407 | InstList::iterator SpillPoint = Insts.end(); |
| 408 | InstList::iterator FillPoint = Insts.end(); |
| 409 | // Stop searching after we have found both the SpillPoint and the FillPoint. |
| 410 | for (auto I = Insts.begin(), E = Insts.end(); |
| 411 | I != E && (SpillPoint == E || FillPoint == E); ++I) { |
| 412 | if (I->getNumber() == Start) |
| 413 | SpillPoint = I; |
| 414 | if (I->getNumber() == End) |
| 415 | FillPoint = I; |
| 416 | if (SpillPoint != E) { |
Jim Stichnoth | a1da6ff | 2015-11-16 15:59:39 -0800 | [diff] [blame] | 417 | // Remove from RegMask any physical registers referenced during Cur's live |
| 418 | // range. Start looking after SpillPoint gets set, i.e. once Cur's live |
| 419 | // range begins. |
John Porto | ec3f565 | 2015-08-31 15:07:09 -0700 | [diff] [blame] | 420 | FOREACH_VAR_IN_INST(Var, *I) { |
John Porto | bb0a5fe | 2015-09-04 11:23:41 -0700 | [diff] [blame] | 421 | if (!Var->hasRegTmp()) |
| 422 | continue; |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 423 | const auto &Aliases = *RegAliases[Var->getRegNumTmp()]; |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 424 | for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
John Porto | bb0a5fe | 2015-09-04 11:23:41 -0700 | [diff] [blame] | 425 | Iter.RegMask[RegAlias] = false; |
| 426 | } |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 427 | } |
| 428 | } |
| 429 | } |
| 430 | assert(SpillPoint != Insts.end()); |
| 431 | assert(FillPoint != Insts.end()); |
| 432 | ++FillPoint; |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 433 | // TODO(stichnot): Randomize instead of *.begin() which maps to find_first(). |
| 434 | const RegNumT RegNum = *RegNumBVIter(Iter.RegMask).begin(); |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 435 | Iter.Cur->setRegNumTmp(RegNum); |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 436 | Variable *Preg = Target->getPhysicalRegister(RegNum, Iter.Cur->getType()); |
Jim Stichnoth | a1da6ff | 2015-11-16 15:59:39 -0800 | [diff] [blame] | 437 | // TODO(stichnot): Add SpillLoc to VariablesMetadata tracking so that SpillLoc |
| 438 | // is correctly identified as !isMultiBlock(), reducing stack frame size. |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 439 | Variable *SpillLoc = Func->makeVariable(Iter.Cur->getType()); |
Jim Stichnoth | a3f57b9 | 2015-07-30 12:46:04 -0700 | [diff] [blame] | 440 | // Add "reg=FakeDef;spill=reg" before SpillPoint |
| 441 | Target->lowerInst(Node, SpillPoint, InstFakeDef::create(Func, Preg)); |
| 442 | Target->lowerInst(Node, SpillPoint, InstAssign::create(Func, SpillLoc, Preg)); |
| 443 | // add "reg=spill;FakeUse(reg)" before FillPoint |
| 444 | Target->lowerInst(Node, FillPoint, InstAssign::create(Func, Preg, SpillLoc)); |
| 445 | Target->lowerInst(Node, FillPoint, InstFakeUse::create(Func, Preg)); |
| 446 | } |
| 447 | |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 448 | void LinearScan::handleActiveRangeExpiredOrInactive(const Variable *Cur) { |
| 449 | for (SizeT I = Active.size(); I > 0; --I) { |
| 450 | const SizeT Index = I - 1; |
| 451 | Variable *Item = Active[Index]; |
| 452 | Item->trimLiveRange(Cur->getLiveRange().getStart()); |
| 453 | bool Moved = false; |
| 454 | if (Item->rangeEndsBefore(Cur)) { |
| 455 | // Move Item from Active to Handled list. |
Jim Stichnoth | 6966055 | 2015-09-18 06:41:02 -0700 | [diff] [blame] | 456 | dumpLiveRangeTrace("Expiring ", Item); |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 457 | moveItem(Active, Index, Handled); |
| 458 | Moved = true; |
| 459 | } else if (!Item->rangeOverlapsStart(Cur)) { |
| 460 | // Move Item from Active to Inactive list. |
Jim Stichnoth | 6966055 | 2015-09-18 06:41:02 -0700 | [diff] [blame] | 461 | dumpLiveRangeTrace("Inactivating ", Item); |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 462 | moveItem(Active, Index, Inactive); |
| 463 | Moved = true; |
| 464 | } |
| 465 | if (Moved) { |
| 466 | // Decrement Item from RegUses[]. |
| 467 | assert(Item->hasRegTmp()); |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 468 | const auto &Aliases = *RegAliases[Item->getRegNumTmp()]; |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 469 | for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
John Porto | bb0a5fe | 2015-09-04 11:23:41 -0700 | [diff] [blame] | 470 | --RegUses[RegAlias]; |
| 471 | assert(RegUses[RegAlias] >= 0); |
| 472 | } |
Jim Stichnoth | e6d2478 | 2014-12-19 05:42:24 -0800 | [diff] [blame] | 473 | } |
| 474 | } |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 475 | } |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 476 | |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 477 | void LinearScan::handleInactiveRangeExpiredOrReactivated(const Variable *Cur) { |
| 478 | for (SizeT I = Inactive.size(); I > 0; --I) { |
| 479 | const SizeT Index = I - 1; |
| 480 | Variable *Item = Inactive[Index]; |
| 481 | Item->trimLiveRange(Cur->getLiveRange().getStart()); |
| 482 | if (Item->rangeEndsBefore(Cur)) { |
| 483 | // Move Item from Inactive to Handled list. |
Jim Stichnoth | 6966055 | 2015-09-18 06:41:02 -0700 | [diff] [blame] | 484 | dumpLiveRangeTrace("Expiring ", Item); |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 485 | moveItem(Inactive, Index, Handled); |
| 486 | } else if (Item->rangeOverlapsStart(Cur)) { |
| 487 | // Move Item from Inactive to Active list. |
Jim Stichnoth | 6966055 | 2015-09-18 06:41:02 -0700 | [diff] [blame] | 488 | dumpLiveRangeTrace("Reactivating ", Item); |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 489 | moveItem(Inactive, Index, Active); |
| 490 | // Increment Item in RegUses[]. |
| 491 | assert(Item->hasRegTmp()); |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 492 | const auto &Aliases = *RegAliases[Item->getRegNumTmp()]; |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 493 | for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
John Porto | bb0a5fe | 2015-09-04 11:23:41 -0700 | [diff] [blame] | 494 | assert(RegUses[RegAlias] >= 0); |
| 495 | ++RegUses[RegAlias]; |
| 496 | } |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 497 | } |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 498 | } |
| 499 | } |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 500 | |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 501 | // Infer register preference and allowable overlap. Only form a preference when |
Jim Stichnoth | a1da6ff | 2015-11-16 15:59:39 -0800 | [diff] [blame] | 502 | // the current Variable has an unambiguous "first" definition. The preference is |
| 503 | // some source Variable of the defining instruction that either is assigned a |
| 504 | // register that is currently free, or that is assigned a register that is not |
| 505 | // free but overlap is allowed. Overlap is allowed when the Variable under |
| 506 | // consideration is single-definition, and its definition is a simple assignment |
| 507 | // - i.e., the register gets copied/aliased but is never modified. Furthermore, |
| 508 | // overlap is only allowed when preferred Variable definition instructions do |
| 509 | // not appear within the current Variable's live range. |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 510 | void LinearScan::findRegisterPreference(IterationState &Iter) { |
| 511 | Iter.Prefer = nullptr; |
Reed Kotler | 5fa0a5f | 2016-02-15 20:01:24 -0800 | [diff] [blame] | 512 | Iter.PreferReg = RegNumT(); |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 513 | Iter.AllowOverlap = false; |
| 514 | |
Jim Stichnoth | a1da6ff | 2015-11-16 15:59:39 -0800 | [diff] [blame] | 515 | if (!FindPreference) |
| 516 | return; |
| 517 | |
| 518 | VariablesMetadata *VMetadata = Func->getVMetadata(); |
| 519 | const Inst *DefInst = VMetadata->getFirstDefinitionSingleBlock(Iter.Cur); |
| 520 | if (DefInst == nullptr) |
| 521 | return; |
| 522 | |
| 523 | assert(DefInst->getDest() == Iter.Cur); |
| 524 | const bool IsSingleDefAssign = |
| 525 | DefInst->isVarAssign() && !VMetadata->isMultiDef(Iter.Cur); |
| 526 | FOREACH_VAR_IN_INST(SrcVar, *DefInst) { |
| 527 | // Only consider source variables that have (so far) been assigned a |
| 528 | // register. |
| 529 | if (!SrcVar->hasRegTmp()) |
| 530 | continue; |
| 531 | |
| 532 | // That register must be one in the RegMask set, e.g. don't try to prefer |
| 533 | // the stack pointer as a result of the stacksave intrinsic. |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 534 | const auto &Aliases = *RegAliases[SrcVar->getRegNumTmp()]; |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 535 | const int SrcReg = (Iter.RegMask & Aliases).find_first(); |
Jim Stichnoth | a1da6ff | 2015-11-16 15:59:39 -0800 | [diff] [blame] | 536 | if (SrcReg == -1) |
| 537 | continue; |
| 538 | |
| 539 | if (FindOverlap && IsSingleDefAssign && !Iter.Free[SrcReg]) { |
| 540 | // Don't bother trying to enable AllowOverlap if the register is already |
| 541 | // free (hence the test on Iter.Free[SrcReg]). |
| 542 | Iter.AllowOverlap = !overlapsDefs(Func, Iter.Cur, SrcVar); |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 543 | } |
Jim Stichnoth | a1da6ff | 2015-11-16 15:59:39 -0800 | [diff] [blame] | 544 | if (Iter.AllowOverlap || Iter.Free[SrcReg]) { |
| 545 | Iter.Prefer = SrcVar; |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 546 | Iter.PreferReg = RegNumT::fromInt(SrcReg); |
Jim Stichnoth | a1da6ff | 2015-11-16 15:59:39 -0800 | [diff] [blame] | 547 | // Stop looking for a preference after the first valid preference is |
| 548 | // found. One might think that we should look at all instruction |
| 549 | // variables to find the best <Prefer,AllowOverlap> combination, but note |
| 550 | // that AllowOverlap can only be true for a simple assignment statement |
| 551 | // which can have only one source operand, so it's not possible for |
| 552 | // AllowOverlap to be true beyond the first source operand. |
| 553 | FOREACH_VAR_IN_INST_BREAK; |
| 554 | } |
| 555 | } |
| 556 | if (BuildDefs::dump() && Verbose && Iter.Prefer) { |
| 557 | Ostream &Str = Ctx->getStrDump(); |
| 558 | Str << "Initial Iter.Prefer="; |
| 559 | Iter.Prefer->dump(Func); |
| 560 | Str << " R=" << Iter.PreferReg << " LIVE=" << Iter.Prefer->getLiveRange() |
| 561 | << " Overlap=" << Iter.AllowOverlap << "\n"; |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 562 | } |
| 563 | } |
| 564 | |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 565 | // Remove registers from the Iter.Free[] list where an Inactive range overlaps |
| 566 | // with the current range. |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 567 | void LinearScan::filterFreeWithInactiveRanges(IterationState &Iter) { |
| 568 | for (const Variable *Item : Inactive) { |
John Porto | bb0a5fe | 2015-09-04 11:23:41 -0700 | [diff] [blame] | 569 | if (!Item->rangeOverlaps(Iter.Cur)) |
| 570 | continue; |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 571 | const auto &Aliases = *RegAliases[Item->getRegNumTmp()]; |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 572 | for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
| 573 | // Don't assert(Iter.Free[RegAlias]) because in theory (though probably |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 574 | // never in practice) there could be two inactive variables that were |
| 575 | // marked with AllowOverlap. |
John Porto | bb0a5fe | 2015-09-04 11:23:41 -0700 | [diff] [blame] | 576 | Iter.Free[RegAlias] = false; |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 577 | Iter.FreeUnfiltered[RegAlias] = false; |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 578 | // Disable AllowOverlap if an Inactive variable, which is not Prefer, |
Jim Stichnoth | a1da6ff | 2015-11-16 15:59:39 -0800 | [diff] [blame] | 579 | // shares Prefer's register, and has a definition within Cur's live range. |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 580 | if (Iter.AllowOverlap && Item != Iter.Prefer && |
John Porto | bb0a5fe | 2015-09-04 11:23:41 -0700 | [diff] [blame] | 581 | RegAlias == Iter.PreferReg && overlapsDefs(Func, Iter.Cur, Item)) { |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 582 | Iter.AllowOverlap = false; |
| 583 | dumpDisableOverlap(Func, Item, "Inactive"); |
| 584 | } |
| 585 | } |
| 586 | } |
| 587 | } |
| 588 | |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 589 | // Remove registers from the Iter.Free[] list where an Unhandled pre-colored |
| 590 | // range overlaps with the current range, and set those registers to infinite |
| 591 | // weight so that they aren't candidates for eviction. |
| 592 | // Cur->rangeEndsBefore(Item) is an early exit check that turns a guaranteed |
| 593 | // O(N^2) algorithm into expected linear complexity. |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 594 | void LinearScan::filterFreeWithPrecoloredRanges(IterationState &Iter) { |
Jim Stichnoth | 4c5c571 | 2015-11-16 17:17:48 -0800 | [diff] [blame] | 595 | // TODO(stichnot): Partition UnhandledPrecolored according to register class, |
| 596 | // to restrict the number of overlap comparisons needed. |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 597 | for (Variable *Item : reverse_range(UnhandledPrecolored)) { |
| 598 | assert(Item->hasReg()); |
| 599 | if (Iter.Cur->rangeEndsBefore(Item)) |
| 600 | break; |
Jim Stichnoth | a1da6ff | 2015-11-16 15:59:39 -0800 | [diff] [blame] | 601 | if (!Item->rangeOverlaps(Iter.Cur)) |
| 602 | continue; |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 603 | const auto &Aliases = |
Jim Stichnoth | a1da6ff | 2015-11-16 15:59:39 -0800 | [diff] [blame] | 604 | *RegAliases[Item->getRegNum()]; // Note: not getRegNumTmp() |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 605 | for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
Jim Stichnoth | a1da6ff | 2015-11-16 15:59:39 -0800 | [diff] [blame] | 606 | Iter.Weights[RegAlias].setWeight(RegWeight::Inf); |
| 607 | Iter.Free[RegAlias] = false; |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 608 | Iter.FreeUnfiltered[RegAlias] = false; |
Jim Stichnoth | a1da6ff | 2015-11-16 15:59:39 -0800 | [diff] [blame] | 609 | Iter.PrecoloredUnhandledMask[RegAlias] = true; |
| 610 | // Disable Iter.AllowOverlap if the preferred register is one of these |
| 611 | // pre-colored unhandled overlapping ranges. |
| 612 | if (Iter.AllowOverlap && RegAlias == Iter.PreferReg) { |
| 613 | Iter.AllowOverlap = false; |
| 614 | dumpDisableOverlap(Func, Item, "PrecoloredUnhandled"); |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 615 | } |
| 616 | } |
| 617 | } |
| 618 | } |
| 619 | |
| 620 | void LinearScan::allocatePrecoloredRegister(Variable *Cur) { |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 621 | const auto RegNum = Cur->getRegNum(); |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 622 | // RegNumTmp should have already been set above. |
| 623 | assert(Cur->getRegNumTmp() == RegNum); |
| 624 | dumpLiveRangeTrace("Precoloring ", Cur); |
| 625 | Active.push_back(Cur); |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 626 | const auto &Aliases = *RegAliases[RegNum]; |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 627 | for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
John Porto | bb0a5fe | 2015-09-04 11:23:41 -0700 | [diff] [blame] | 628 | assert(RegUses[RegAlias] >= 0); |
| 629 | ++RegUses[RegAlias]; |
| 630 | } |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 631 | assert(!UnhandledPrecolored.empty()); |
| 632 | assert(UnhandledPrecolored.back() == Cur); |
| 633 | UnhandledPrecolored.pop_back(); |
| 634 | } |
| 635 | |
| 636 | void LinearScan::allocatePreferredRegister(IterationState &Iter) { |
| 637 | Iter.Cur->setRegNumTmp(Iter.PreferReg); |
| 638 | dumpLiveRangeTrace("Preferring ", Iter.Cur); |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 639 | const auto &Aliases = *RegAliases[Iter.PreferReg]; |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 640 | for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
John Porto | bb0a5fe | 2015-09-04 11:23:41 -0700 | [diff] [blame] | 641 | assert(RegUses[RegAlias] >= 0); |
| 642 | ++RegUses[RegAlias]; |
| 643 | } |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 644 | Active.push_back(Iter.Cur); |
| 645 | } |
| 646 | |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 647 | void LinearScan::allocateFreeRegister(IterationState &Iter, bool Filtered) { |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 648 | const RegNumT RegNum = |
| 649 | *RegNumBVIter(Filtered ? Iter.Free : Iter.FreeUnfiltered).begin(); |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 650 | Iter.Cur->setRegNumTmp(RegNum); |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 651 | if (Filtered) |
John Porto | 4b6e4b4 | 2016-02-17 05:00:59 -0800 | [diff] [blame] | 652 | dumpLiveRangeTrace("Allocating Y ", Iter.Cur); |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 653 | else |
| 654 | dumpLiveRangeTrace("Allocating X ", Iter.Cur); |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 655 | const auto &Aliases = *RegAliases[RegNum]; |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 656 | for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
John Porto | bb0a5fe | 2015-09-04 11:23:41 -0700 | [diff] [blame] | 657 | assert(RegUses[RegAlias] >= 0); |
| 658 | ++RegUses[RegAlias]; |
| 659 | } |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 660 | Active.push_back(Iter.Cur); |
| 661 | } |
| 662 | |
| 663 | void LinearScan::handleNoFreeRegisters(IterationState &Iter) { |
| 664 | // Check Active ranges. |
| 665 | for (const Variable *Item : Active) { |
| 666 | assert(Item->rangeOverlaps(Iter.Cur)); |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 667 | assert(Item->hasRegTmp()); |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 668 | const auto &Aliases = *RegAliases[Item->getRegNumTmp()]; |
John Porto | bb0a5fe | 2015-09-04 11:23:41 -0700 | [diff] [blame] | 669 | // We add the Item's weight to each alias/subregister to represent that, |
| 670 | // should we decide to pick any of them, then we would incur that many |
| 671 | // memory accesses. |
| 672 | RegWeight W = Item->getWeight(Func); |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 673 | for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
John Porto | bb0a5fe | 2015-09-04 11:23:41 -0700 | [diff] [blame] | 674 | Iter.Weights[RegAlias].addWeight(W); |
| 675 | } |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 676 | } |
| 677 | // Same as above, but check Inactive ranges instead of Active. |
| 678 | for (const Variable *Item : Inactive) { |
John Porto | bb0a5fe | 2015-09-04 11:23:41 -0700 | [diff] [blame] | 679 | if (!Item->rangeOverlaps(Iter.Cur)) |
| 680 | continue; |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 681 | assert(Item->hasRegTmp()); |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 682 | const auto &Aliases = *RegAliases[Item->getRegNumTmp()]; |
John Porto | bb0a5fe | 2015-09-04 11:23:41 -0700 | [diff] [blame] | 683 | RegWeight W = Item->getWeight(Func); |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 684 | for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
John Porto | bb0a5fe | 2015-09-04 11:23:41 -0700 | [diff] [blame] | 685 | Iter.Weights[RegAlias].addWeight(W); |
| 686 | } |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 687 | } |
| 688 | |
Jim Stichnoth | a1da6ff | 2015-11-16 15:59:39 -0800 | [diff] [blame] | 689 | // All the weights are now calculated. Find the register with smallest weight. |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 690 | int32_t MinWeightIndex = findMinWeightIndex(Iter.RegMask, Iter.Weights); |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 691 | |
Jim Stichnoth | 2655d96 | 2016-04-21 05:38:15 -0700 | [diff] [blame] | 692 | if (MinWeightIndex < 0 || |
| 693 | Iter.Cur->getWeight(Func) <= Iter.Weights[MinWeightIndex]) { |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 694 | if (!Iter.Cur->mustHaveReg()) { |
| 695 | // Iter.Cur doesn't have priority over any other live ranges, so don't |
| 696 | // allocate any register to it, and move it to the Handled state. |
| 697 | Handled.push_back(Iter.Cur); |
| 698 | return; |
| 699 | } |
| 700 | if (Kind == RAK_Phi) { |
| 701 | // Iter.Cur is infinite-weight but all physical registers are already |
| 702 | // taken, so we need to force one to be temporarily available. |
| 703 | addSpillFill(Iter); |
| 704 | Handled.push_back(Iter.Cur); |
| 705 | return; |
| 706 | } |
| 707 | // The remaining portion of the enclosing "if" block should only be |
| 708 | // reachable if we are manually limiting physical registers for testing. |
| 709 | if (UseReserve) { |
| 710 | if (Iter.FreeUnfiltered.any()) { |
| 711 | // There is some available physical register held in reserve, so use it. |
| 712 | constexpr bool NotFiltered = false; |
| 713 | allocateFreeRegister(Iter, NotFiltered); |
| 714 | // Iter.Cur is now on the Active list. |
| 715 | return; |
Jim Stichnoth | 2544d4d | 2016-01-22 13:07:46 -0800 | [diff] [blame] | 716 | } |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 717 | // At this point, we need to find some reserve register that is already |
| 718 | // assigned to a non-infinite-weight variable. This could happen if some |
| 719 | // variable was previously assigned an alias of such a register. |
| 720 | MinWeightIndex = findMinWeightIndex(Iter.RegMaskUnfiltered, Iter.Weights); |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 721 | } |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 722 | if (Iter.Cur->getWeight(Func) <= Iter.Weights[MinWeightIndex]) { |
| 723 | dumpLiveRangeTrace("Failing ", Iter.Cur); |
| 724 | Func->setError("Unable to find a physical register for an " |
| 725 | "infinite-weight live range " |
| 726 | "(consider using -reg-reserve): " + |
Jim Stichnoth | a91c341 | 2016-04-05 15:31:43 -0700 | [diff] [blame] | 727 | Iter.Cur->getName()); |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 728 | Handled.push_back(Iter.Cur); |
| 729 | return; |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 730 | } |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 731 | // At this point, MinWeightIndex points to a valid reserve register to |
| 732 | // reallocate to Iter.Cur, so drop into the eviction code. |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 733 | } |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 734 | |
| 735 | // Evict all live ranges in Active that register number MinWeightIndex is |
| 736 | // assigned to. |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 737 | const auto &Aliases = *RegAliases[MinWeightIndex]; |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 738 | for (SizeT I = Active.size(); I > 0; --I) { |
| 739 | const SizeT Index = I - 1; |
| 740 | Variable *Item = Active[Index]; |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 741 | const auto RegNum = Item->getRegNumTmp(); |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 742 | if (Aliases[RegNum]) { |
| 743 | dumpLiveRangeTrace("Evicting A ", Item); |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 744 | const auto &Aliases = *RegAliases[RegNum]; |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 745 | for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 746 | --RegUses[RegAlias]; |
| 747 | assert(RegUses[RegAlias] >= 0); |
| 748 | } |
Reed Kotler | 5fa0a5f | 2016-02-15 20:01:24 -0800 | [diff] [blame] | 749 | Item->setRegNumTmp(RegNumT()); |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 750 | moveItem(Active, Index, Handled); |
| 751 | Evicted.push_back(Item); |
| 752 | } |
| 753 | } |
| 754 | // Do the same for Inactive. |
| 755 | for (SizeT I = Inactive.size(); I > 0; --I) { |
| 756 | const SizeT Index = I - 1; |
| 757 | Variable *Item = Inactive[Index]; |
| 758 | // Note: The Item->rangeOverlaps(Cur) clause is not part of the description |
| 759 | // of AssignMemLoc() in the original paper. But there doesn't seem to be any |
| 760 | // need to evict an inactive live range that doesn't overlap with the live |
| 761 | // range currently being considered. It's especially bad if we would end up |
| 762 | // evicting an infinite-weight but currently-inactive live range. The most |
| 763 | // common situation for this would be a scratch register kill set for call |
| 764 | // instructions. |
| 765 | if (Aliases[Item->getRegNumTmp()] && Item->rangeOverlaps(Iter.Cur)) { |
| 766 | dumpLiveRangeTrace("Evicting I ", Item); |
Reed Kotler | 5fa0a5f | 2016-02-15 20:01:24 -0800 | [diff] [blame] | 767 | Item->setRegNumTmp(RegNumT()); |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 768 | moveItem(Inactive, Index, Handled); |
| 769 | Evicted.push_back(Item); |
| 770 | } |
| 771 | } |
| 772 | // Assign the register to Cur. |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 773 | Iter.Cur->setRegNumTmp(RegNumT::fromInt(MinWeightIndex)); |
| 774 | for (RegNumT RegAlias : RegNumBVIter(Aliases)) { |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 775 | assert(RegUses[RegAlias] >= 0); |
| 776 | ++RegUses[RegAlias]; |
| 777 | } |
| 778 | Active.push_back(Iter.Cur); |
John Porto | 4b6e4b4 | 2016-02-17 05:00:59 -0800 | [diff] [blame] | 779 | dumpLiveRangeTrace("Allocating Z ", Iter.Cur); |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 780 | } |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 781 | |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 782 | void LinearScan::assignFinalRegisters(const SmallBitVector &RegMaskFull, |
| 783 | const SmallBitVector &PreDefinedRegisters, |
| 784 | bool Randomized) { |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 785 | const size_t NumRegisters = RegMaskFull.size(); |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 786 | llvm::SmallVector<RegNumT, REGS_SIZE> Permutation(NumRegisters); |
Jim Stichnoth | e6d2478 | 2014-12-19 05:42:24 -0800 | [diff] [blame] | 787 | if (Randomized) { |
Qining Lu | aee5fa8 | 2015-08-20 14:59:03 -0700 | [diff] [blame] | 788 | // Create a random number generator for regalloc randomization. Merge |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 789 | // function's sequence and Kind value as the Salt. Because regAlloc() is |
Andrew Scull | 57e1268 | 2015-09-16 11:30:19 -0700 | [diff] [blame] | 790 | // called twice under O2, the second time with RAK_Phi, we check Kind == |
| 791 | // RAK_Phi to determine the lowest-order bit to make sure the Salt is |
| 792 | // different. |
Qining Lu | aee5fa8 | 2015-08-20 14:59:03 -0700 | [diff] [blame] | 793 | uint64_t Salt = |
| 794 | (Func->getSequenceNumber() << 1) ^ (Kind == RAK_Phi ? 0u : 1u); |
John Porto | bb0a5fe | 2015-09-04 11:23:41 -0700 | [diff] [blame] | 795 | Target->makeRandomRegisterPermutation( |
Qining Lu | aee5fa8 | 2015-08-20 14:59:03 -0700 | [diff] [blame] | 796 | Permutation, PreDefinedRegisters | ~RegMaskFull, Salt); |
Jim Stichnoth | e6d2478 | 2014-12-19 05:42:24 -0800 | [diff] [blame] | 797 | } |
| 798 | |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 799 | // Finish up by setting RegNum = RegNumTmp (or a random permutation thereof) |
| 800 | // for each Variable. |
Jim Stichnoth | 5ce0abb | 2014-10-15 10:16:54 -0700 | [diff] [blame] | 801 | for (Variable *Item : Handled) { |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 802 | const auto RegNum = Item->getRegNumTmp(); |
| 803 | auto AssignedRegNum = RegNum; |
Jim Stichnoth | e6d2478 | 2014-12-19 05:42:24 -0800 | [diff] [blame] | 804 | |
| 805 | if (Randomized && Item->hasRegTmp() && !Item->hasReg()) { |
| 806 | AssignedRegNum = Permutation[RegNum]; |
| 807 | } |
Jim Stichnoth | a1da6ff | 2015-11-16 15:59:39 -0800 | [diff] [blame] | 808 | if (BuildDefs::dump() && Verbose) { |
Jim Stichnoth | e4a8f40 | 2015-01-20 12:52:51 -0800 | [diff] [blame] | 809 | Ostream &Str = Ctx->getStrDump(); |
Jim Stichnoth | 5ce0abb | 2014-10-15 10:16:54 -0700 | [diff] [blame] | 810 | if (!Item->hasRegTmp()) { |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 811 | Str << "Not assigning "; |
Jim Stichnoth | 5ce0abb | 2014-10-15 10:16:54 -0700 | [diff] [blame] | 812 | Item->dump(Func); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 813 | Str << "\n"; |
| 814 | } else { |
Jim Stichnoth | e6d2478 | 2014-12-19 05:42:24 -0800 | [diff] [blame] | 815 | Str << (AssignedRegNum == Item->getRegNum() ? "Reassigning " |
| 816 | : "Assigning ") |
Jim Stichnoth | 4a65947 | 2016-02-01 10:41:18 -0800 | [diff] [blame] | 817 | << Target->getRegName(AssignedRegNum, Item->getType()) << "(r" |
John Porto | bb0a5fe | 2015-09-04 11:23:41 -0700 | [diff] [blame] | 818 | << AssignedRegNum << ") to "; |
Jim Stichnoth | 5ce0abb | 2014-10-15 10:16:54 -0700 | [diff] [blame] | 819 | Item->dump(Func); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 820 | Str << "\n"; |
| 821 | } |
| 822 | } |
Jim Stichnoth | e6d2478 | 2014-12-19 05:42:24 -0800 | [diff] [blame] | 823 | Item->setRegNum(AssignedRegNum); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 824 | } |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 825 | } |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 826 | |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 827 | // Implements the linear-scan algorithm. Based on "Linear Scan Register |
| 828 | // Allocation in the Context of SSA Form and Register Constraints" by Hanspeter |
| 829 | // Mössenböck and Michael Pfeiffer, |
| 830 | // ftp://ftp.ssw.uni-linz.ac.at/pub/Papers/Moe02.PDF. This implementation is |
Jim Stichnoth | a1da6ff | 2015-11-16 15:59:39 -0800 | [diff] [blame] | 831 | // modified to take affinity into account and allow two interfering variables to |
| 832 | // share the same register in certain cases. |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 833 | // |
| 834 | // Requires running Cfg::liveness(Liveness_Intervals) in preparation. Results |
| 835 | // are assigned to Variable::RegNum for each Variable. |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 836 | void LinearScan::scan(const SmallBitVector &RegMaskFull, bool Randomized) { |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 837 | TimerMarker T(TimerStack::TT_linearScan, Func); |
| 838 | assert(RegMaskFull.any()); // Sanity check |
| 839 | if (Verbose) |
| 840 | Ctx->lockStr(); |
| 841 | Func->resetCurrentNode(); |
| 842 | const size_t NumRegisters = RegMaskFull.size(); |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 843 | SmallBitVector PreDefinedRegisters(NumRegisters); |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 844 | if (Randomized) { |
| 845 | for (Variable *Var : UnhandledPrecolored) { |
| 846 | PreDefinedRegisters[Var->getRegNum()] = true; |
| 847 | } |
| 848 | } |
| 849 | |
| 850 | // Build a LiveRange representing the Kills list. |
| 851 | LiveRange KillsRange(Kills); |
| 852 | KillsRange.untrim(); |
| 853 | |
Jim Stichnoth | a1da6ff | 2015-11-16 15:59:39 -0800 | [diff] [blame] | 854 | // Reset the register use count. |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 855 | RegUses.resize(NumRegisters); |
| 856 | std::fill(RegUses.begin(), RegUses.end(), 0); |
| 857 | |
Jim Stichnoth | a1da6ff | 2015-11-16 15:59:39 -0800 | [diff] [blame] | 858 | // Unhandled is already set to all ranges in increasing order of start points. |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 859 | assert(Active.empty()); |
| 860 | assert(Inactive.empty()); |
| 861 | assert(Handled.empty()); |
| 862 | const TargetLowering::RegSetMask RegsInclude = |
| 863 | TargetLowering::RegSet_CallerSave; |
| 864 | const TargetLowering::RegSetMask RegsExclude = TargetLowering::RegSet_None; |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 865 | const SmallBitVector KillsMask = |
John Porto | bb0a5fe | 2015-09-04 11:23:41 -0700 | [diff] [blame] | 866 | Target->getRegisterSet(RegsInclude, RegsExclude); |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 867 | |
Jim Stichnoth | a1da6ff | 2015-11-16 15:59:39 -0800 | [diff] [blame] | 868 | // Allocate memory once outside the loop. |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 869 | IterationState Iter; |
| 870 | Iter.Weights.reserve(NumRegisters); |
| 871 | Iter.PrecoloredUnhandledMask.reserve(NumRegisters); |
| 872 | |
| 873 | while (!Unhandled.empty()) { |
| 874 | Iter.Cur = Unhandled.back(); |
| 875 | Unhandled.pop_back(); |
| 876 | dumpLiveRangeTrace("\nConsidering ", Iter.Cur); |
Jim Stichnoth | 2655d96 | 2016-04-21 05:38:15 -0700 | [diff] [blame] | 877 | if (UseReserve) |
| 878 | assert(Target->getAllRegistersForVariable(Iter.Cur).any()); |
| 879 | else |
| 880 | assert(Target->getRegistersForVariable(Iter.Cur).any()); |
Jim Stichnoth | c59288b | 2015-11-09 11:38:40 -0800 | [diff] [blame] | 881 | Iter.RegMask = RegMaskFull & Target->getRegistersForVariable(Iter.Cur); |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 882 | Iter.RegMaskUnfiltered = |
| 883 | RegMaskFull & Target->getAllRegistersForVariable(Iter.Cur); |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 884 | KillsRange.trim(Iter.Cur->getLiveRange().getStart()); |
| 885 | |
| 886 | // Check for pre-colored ranges. If Cur is pre-colored, it definitely gets |
| 887 | // that register. Previously processed live ranges would have avoided that |
| 888 | // register due to it being pre-colored. Future processed live ranges won't |
| 889 | // evict that register because the live range has infinite weight. |
| 890 | if (Iter.Cur->hasReg()) { |
| 891 | allocatePrecoloredRegister(Iter.Cur); |
| 892 | continue; |
| 893 | } |
| 894 | |
| 895 | handleActiveRangeExpiredOrInactive(Iter.Cur); |
| 896 | handleInactiveRangeExpiredOrReactivated(Iter.Cur); |
| 897 | |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 898 | // Calculate available registers into Iter.Free[] and Iter.FreeUnfiltered[]. |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 899 | Iter.Free = Iter.RegMask; |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 900 | Iter.FreeUnfiltered = Iter.RegMaskUnfiltered; |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 901 | for (SizeT i = 0; i < Iter.RegMask.size(); ++i) { |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 902 | if (RegUses[i] > 0) { |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 903 | Iter.Free[i] = false; |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 904 | Iter.FreeUnfiltered[i] = false; |
| 905 | } |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 906 | } |
| 907 | |
| 908 | findRegisterPreference(Iter); |
| 909 | filterFreeWithInactiveRanges(Iter); |
| 910 | |
| 911 | // Disable AllowOverlap if an Active variable, which is not Prefer, shares |
| 912 | // Prefer's register, and has a definition within Cur's live range. |
| 913 | if (Iter.AllowOverlap) { |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 914 | const auto &Aliases = *RegAliases[Iter.PreferReg]; |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 915 | for (const Variable *Item : Active) { |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 916 | const RegNumT RegNum = Item->getRegNumTmp(); |
Jim Stichnoth | c59288b | 2015-11-09 11:38:40 -0800 | [diff] [blame] | 917 | if (Item != Iter.Prefer && Aliases[RegNum] && |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 918 | overlapsDefs(Func, Iter.Cur, Item)) { |
| 919 | Iter.AllowOverlap = false; |
| 920 | dumpDisableOverlap(Func, Item, "Active"); |
| 921 | } |
| 922 | } |
| 923 | } |
| 924 | |
| 925 | Iter.Weights.resize(Iter.RegMask.size()); |
| 926 | std::fill(Iter.Weights.begin(), Iter.Weights.end(), RegWeight()); |
| 927 | |
| 928 | Iter.PrecoloredUnhandledMask.resize(Iter.RegMask.size()); |
| 929 | Iter.PrecoloredUnhandledMask.reset(); |
| 930 | |
| 931 | filterFreeWithPrecoloredRanges(Iter); |
| 932 | |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 933 | // Remove scratch registers from the Iter.Free[] list, and mark their |
| 934 | // Iter.Weights[] as infinite, if KillsRange overlaps Cur's live range. |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 935 | constexpr bool UseTrimmed = true; |
| 936 | if (Iter.Cur->getLiveRange().overlaps(KillsRange, UseTrimmed)) { |
| 937 | Iter.Free.reset(KillsMask); |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 938 | Iter.FreeUnfiltered.reset(KillsMask); |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 939 | for (RegNumT i : RegNumBVIter(KillsMask)) { |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 940 | Iter.Weights[i].setWeight(RegWeight::Inf); |
| 941 | if (Iter.PreferReg == i) |
| 942 | Iter.AllowOverlap = false; |
| 943 | } |
| 944 | } |
| 945 | |
| 946 | // Print info about physical register availability. |
Jim Stichnoth | a1da6ff | 2015-11-16 15:59:39 -0800 | [diff] [blame] | 947 | if (BuildDefs::dump() && Verbose) { |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 948 | Ostream &Str = Ctx->getStrDump(); |
Jim Stichnoth | 8aa3966 | 2016-02-10 11:20:30 -0800 | [diff] [blame] | 949 | for (RegNumT i : RegNumBVIter(Iter.RegMaskUnfiltered)) { |
| 950 | Str << Target->getRegName(i, Iter.Cur->getType()) << "(U=" << RegUses[i] |
| 951 | << ",F=" << Iter.Free[i] << ",P=" << Iter.PrecoloredUnhandledMask[i] |
| 952 | << ") "; |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 953 | } |
| 954 | Str << "\n"; |
| 955 | } |
| 956 | |
| 957 | if (Iter.Prefer && (Iter.AllowOverlap || Iter.Free[Iter.PreferReg])) { |
Jim Stichnoth | a1da6ff | 2015-11-16 15:59:39 -0800 | [diff] [blame] | 958 | // First choice: a preferred register that is either free or is allowed to |
| 959 | // overlap with its linked variable. |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 960 | allocatePreferredRegister(Iter); |
| 961 | } else if (Iter.Free.any()) { |
| 962 | // Second choice: any free register. |
Jim Stichnoth | b40595a | 2016-01-29 06:14:31 -0800 | [diff] [blame] | 963 | constexpr bool Filtered = true; |
| 964 | allocateFreeRegister(Iter, Filtered); |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 965 | } else { |
Jim Stichnoth | a1da6ff | 2015-11-16 15:59:39 -0800 | [diff] [blame] | 966 | // Fallback: there are no free registers, so we look for the lowest-weight |
| 967 | // register and see if Cur has higher weight. |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 968 | handleNoFreeRegisters(Iter); |
| 969 | } |
| 970 | dump(Func); |
| 971 | } |
| 972 | |
| 973 | // Move anything Active or Inactive to Handled for easier handling. |
| 974 | Handled.insert(Handled.end(), Active.begin(), Active.end()); |
| 975 | Active.clear(); |
| 976 | Handled.insert(Handled.end(), Inactive.begin(), Inactive.end()); |
| 977 | Inactive.clear(); |
| 978 | dump(Func); |
| 979 | |
| 980 | assignFinalRegisters(RegMaskFull, PreDefinedRegisters, Randomized); |
| 981 | |
Jim Stichnoth | e4a8f40 | 2015-01-20 12:52:51 -0800 | [diff] [blame] | 982 | if (Verbose) |
| 983 | Ctx->unlockStr(); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 984 | } |
| 985 | |
| 986 | // ======================== Dump routines ======================== // |
| 987 | |
Andrew Scull | d24cfda | 2015-08-25 10:31:15 -0700 | [diff] [blame] | 988 | void LinearScan::dumpLiveRangeTrace(const char *Label, const Variable *Item) { |
| 989 | if (!BuildDefs::dump()) |
| 990 | return; |
| 991 | |
| 992 | if (Verbose) { |
| 993 | Ostream &Str = Ctx->getStrDump(); |
| 994 | Str << Label; |
| 995 | dumpLiveRange(Item, Func); |
| 996 | Str << "\n"; |
| 997 | } |
| 998 | } |
| 999 | |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 1000 | void LinearScan::dump(Cfg *Func) const { |
Jim Stichnoth | 20b71f5 | 2015-06-24 15:52:24 -0700 | [diff] [blame] | 1001 | if (!BuildDefs::dump()) |
Karl Schimpf | b6c96af | 2014-11-17 10:58:39 -0800 | [diff] [blame] | 1002 | return; |
Jim Stichnoth | a1da6ff | 2015-11-16 15:59:39 -0800 | [diff] [blame] | 1003 | if (!Verbose) |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 1004 | return; |
Jim Stichnoth | e4a8f40 | 2015-01-20 12:52:51 -0800 | [diff] [blame] | 1005 | Ostream &Str = Func->getContext()->getStrDump(); |
Jim Stichnoth | 800dab2 | 2014-09-20 12:25:02 -0700 | [diff] [blame] | 1006 | Func->resetCurrentNode(); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 1007 | Str << "**** Current regalloc state:\n"; |
| 1008 | Str << "++++++ Handled:\n"; |
Jim Stichnoth | 5ce0abb | 2014-10-15 10:16:54 -0700 | [diff] [blame] | 1009 | for (const Variable *Item : Handled) { |
| 1010 | dumpLiveRange(Item, Func); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 1011 | Str << "\n"; |
| 1012 | } |
| 1013 | Str << "++++++ Unhandled:\n"; |
Jim Stichnoth | 7e57136 | 2015-01-09 11:43:26 -0800 | [diff] [blame] | 1014 | for (const Variable *Item : reverse_range(Unhandled)) { |
| 1015 | dumpLiveRange(Item, Func); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 1016 | Str << "\n"; |
| 1017 | } |
| 1018 | Str << "++++++ Active:\n"; |
Jim Stichnoth | 5ce0abb | 2014-10-15 10:16:54 -0700 | [diff] [blame] | 1019 | for (const Variable *Item : Active) { |
| 1020 | dumpLiveRange(Item, Func); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 1021 | Str << "\n"; |
| 1022 | } |
| 1023 | Str << "++++++ Inactive:\n"; |
Jim Stichnoth | 5ce0abb | 2014-10-15 10:16:54 -0700 | [diff] [blame] | 1024 | for (const Variable *Item : Inactive) { |
| 1025 | dumpLiveRange(Item, Func); |
Jim Stichnoth | d97c7df | 2014-06-04 11:57:08 -0700 | [diff] [blame] | 1026 | Str << "\n"; |
| 1027 | } |
| 1028 | } |
| 1029 | |
| 1030 | } // end of namespace Ice |