OLD | NEW |
1 //===- subzero/src/IceRegAlloc.cpp - Linear-scan implementation -----------===// | 1 //===- subzero/src/IceRegAlloc.cpp - Linear-scan implementation -----------===// |
2 // | 2 // |
3 // The Subzero Code Generator | 3 // The Subzero Code Generator |
4 // | 4 // |
5 // This file is distributed under the University of Illinois Open Source | 5 // This file is distributed under the University of Illinois Open Source |
6 // License. See LICENSE.TXT for details. | 6 // License. See LICENSE.TXT for details. |
7 // | 7 // |
8 //===----------------------------------------------------------------------===// | 8 //===----------------------------------------------------------------------===// |
9 /// | 9 /// |
10 /// \file | 10 /// \file |
(...skipping 95 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
106 // analysis to have calculated live ranges. | 106 // analysis to have calculated live ranges. |
107 void LinearScan::initForGlobal() { | 107 void LinearScan::initForGlobal() { |
108 TimerMarker T(TimerStack::TT_initUnhandled, Func); | 108 TimerMarker T(TimerStack::TT_initUnhandled, Func); |
109 FindPreference = true; | 109 FindPreference = true; |
110 // For full register allocation, normally we want to enable FindOverlap | 110 // For full register allocation, normally we want to enable FindOverlap |
111 // (meaning we look for opportunities for two overlapping live ranges to | 111 // (meaning we look for opportunities for two overlapping live ranges to |
112 // safely share the same register). However, we disable it for phi-lowering | 112 // safely share the same register). However, we disable it for phi-lowering |
113 // register allocation since no overlap opportunities should be available and | 113 // register allocation since no overlap opportunities should be available and |
114 // it's more expensive to look for opportunities. | 114 // it's more expensive to look for opportunities. |
115 FindOverlap = (Kind != RAK_Phi); | 115 FindOverlap = (Kind != RAK_Phi); |
116 const VarList &Vars = Func->getVariables(); | |
117 Unhandled.reserve(Vars.size()); | 116 Unhandled.reserve(Vars.size()); |
118 UnhandledPrecolored.reserve(Vars.size()); | 117 UnhandledPrecolored.reserve(Vars.size()); |
119 // Gather the live ranges of all variables and add them to the Unhandled set. | 118 // Gather the live ranges of all variables and add them to the Unhandled set. |
120 for (Variable *Var : Vars) { | 119 for (Variable *Var : Vars) { |
121 // Don't consider rematerializable variables. | 120 // Don't consider rematerializable variables. |
122 if (Var->isRematerializable()) | 121 if (Var->isRematerializable()) |
123 continue; | 122 continue; |
124 // Explicitly don't consider zero-weight variables, which are meant to be | 123 // Explicitly don't consider zero-weight variables, which are meant to be |
125 // spill slots. | 124 // spill slots. |
126 if (Var->mustNotHaveReg()) | 125 if (Var->mustNotHaveReg()) |
(...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
161 const DefUseErrorList &DefsWithoutUses, | 160 const DefUseErrorList &DefsWithoutUses, |
162 const DefUseErrorList &UsesBeforeDefs, | 161 const DefUseErrorList &UsesBeforeDefs, |
163 const CfgVector<InstNumberT> &LRBegin, | 162 const CfgVector<InstNumberT> &LRBegin, |
164 const CfgVector<InstNumberT> &LREnd) const { | 163 const CfgVector<InstNumberT> &LREnd) const { |
165 if (DefsWithoutUses.empty() && UsesBeforeDefs.empty()) | 164 if (DefsWithoutUses.empty() && UsesBeforeDefs.empty()) |
166 return true; | 165 return true; |
167 | 166 |
168 if (!BuildDefs::dump()) | 167 if (!BuildDefs::dump()) |
169 return false; | 168 return false; |
170 | 169 |
171 const VarList &Vars = Func->getVariables(); | |
172 OstreamLocker L(Ctx); | 170 OstreamLocker L(Ctx); |
173 Ostream &Str = Ctx->getStrDump(); | 171 Ostream &Str = Ctx->getStrDump(); |
174 for (SizeT VarNum : DefsWithoutUses) { | 172 for (SizeT VarNum : DefsWithoutUses) { |
175 Variable *Var = Vars[VarNum]; | 173 Variable *Var = Vars[VarNum]; |
176 Str << "LR def without use, instruction " << LRBegin[VarNum] | 174 Str << "LR def without use, instruction " << LRBegin[VarNum] |
177 << ", variable " << Var->getName() << "\n"; | 175 << ", variable " << Var->getName() << "\n"; |
178 } | 176 } |
179 for (SizeT VarNum : UsesBeforeDefs) { | 177 for (SizeT VarNum : UsesBeforeDefs) { |
180 Variable *Var = Vars[VarNum]; | 178 Variable *Var = Vars[VarNum]; |
181 Str << "LR use before def, instruction " << LREnd[VarNum] << ", variable " | 179 Str << "LR use before def, instruction " << LREnd[VarNum] << ", variable " |
(...skipping 23 matching lines...) Expand all Loading... |
205 // | 203 // |
206 // * Because live ranges are a single segment, the Inactive set will always be | 204 // * Because live ranges are a single segment, the Inactive set will always be |
207 // empty, and the live range trimming operation is unnecessary. | 205 // empty, and the live range trimming operation is unnecessary. |
208 // | 206 // |
209 // * Calculating overlap of single-segment live ranges could be optimized a bit. | 207 // * Calculating overlap of single-segment live ranges could be optimized a bit. |
210 void LinearScan::initForInfOnly() { | 208 void LinearScan::initForInfOnly() { |
211 TimerMarker T(TimerStack::TT_initUnhandled, Func); | 209 TimerMarker T(TimerStack::TT_initUnhandled, Func); |
212 FindPreference = false; | 210 FindPreference = false; |
213 FindOverlap = false; | 211 FindOverlap = false; |
214 SizeT NumVars = 0; | 212 SizeT NumVars = 0; |
215 const VarList &Vars = Func->getVariables(); | |
216 | 213 |
217 // Iterate across all instructions and record the begin and end of the live | 214 // Iterate across all instructions and record the begin and end of the live |
218 // range for each variable that is pre-colored or infinite weight. | 215 // range for each variable that is pre-colored or infinite weight. |
219 CfgVector<InstNumberT> LRBegin(Vars.size(), Inst::NumberSentinel); | 216 CfgVector<InstNumberT> LRBegin(Vars.size(), Inst::NumberSentinel); |
220 CfgVector<InstNumberT> LREnd(Vars.size(), Inst::NumberSentinel); | 217 CfgVector<InstNumberT> LREnd(Vars.size(), Inst::NumberSentinel); |
221 DefUseErrorList DefsWithoutUses, UsesBeforeDefs; | 218 DefUseErrorList DefsWithoutUses, UsesBeforeDefs; |
222 for (CfgNode *Node : Func->getNodes()) { | 219 for (CfgNode *Node : Func->getNodes()) { |
223 for (Inst &Instr : Node->getInsts()) { | 220 for (Inst &Instr : Node->getInsts()) { |
224 if (Instr.isDeleted()) | 221 if (Instr.isDeleted()) |
225 continue; | 222 continue; |
(...skipping 92 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
318 UnhandledPrecolored.push_back(Var); | 315 UnhandledPrecolored.push_back(Var); |
319 Unhandled.push_back(Var); | 316 Unhandled.push_back(Var); |
320 } | 317 } |
321 } | 318 } |
322 for (Variable *Var : Evicted) { | 319 for (Variable *Var : Evicted) { |
323 Var->untrimLiveRange(); | 320 Var->untrimLiveRange(); |
324 Unhandled.push_back(Var); | 321 Unhandled.push_back(Var); |
325 } | 322 } |
326 } | 323 } |
327 | 324 |
328 void LinearScan::init(RegAllocKind Kind) { | 325 void LinearScan::init(RegAllocKind Kind, CfgSet<Variable *> ExcludeVars) { |
329 this->Kind = Kind; | 326 this->Kind = Kind; |
330 Unhandled.clear(); | 327 Unhandled.clear(); |
331 UnhandledPrecolored.clear(); | 328 UnhandledPrecolored.clear(); |
332 Handled.clear(); | 329 Handled.clear(); |
333 Inactive.clear(); | 330 Inactive.clear(); |
334 Active.clear(); | 331 Active.clear(); |
| 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 } |
335 | 338 |
336 SizeT NumRegs = Target->getNumRegisters(); | 339 SizeT NumRegs = Target->getNumRegisters(); |
337 RegAliases.resize(NumRegs); | 340 RegAliases.resize(NumRegs); |
338 for (SizeT Reg = 0; Reg < NumRegs; ++Reg) { | 341 for (SizeT Reg = 0; Reg < NumRegs; ++Reg) { |
339 RegAliases[Reg] = &Target->getAliasesForRegister(RegNumT::fromInt(Reg)); | 342 RegAliases[Reg] = &Target->getAliasesForRegister(RegNumT::fromInt(Reg)); |
340 } | 343 } |
341 | 344 |
342 switch (Kind) { | 345 switch (Kind) { |
343 case RAK_Unknown: | 346 case RAK_Unknown: |
344 llvm::report_fatal_error("Invalid RAK_Unknown"); | 347 llvm::report_fatal_error("Invalid RAK_Unknown"); |
(...skipping 673 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1018 Str << "\n"; | 1021 Str << "\n"; |
1019 } | 1022 } |
1020 Str << "++++++ Inactive:\n"; | 1023 Str << "++++++ Inactive:\n"; |
1021 for (const Variable *Item : Inactive) { | 1024 for (const Variable *Item : Inactive) { |
1022 dumpLiveRange(Item, Func); | 1025 dumpLiveRange(Item, Func); |
1023 Str << "\n"; | 1026 Str << "\n"; |
1024 } | 1027 } |
1025 } | 1028 } |
1026 | 1029 |
1027 } // end of namespace Ice | 1030 } // end of namespace Ice |
OLD | NEW |