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