IceRegAlloc.cpp revision cc89c959c2f602361488e0fdc0bf62e5d197d15c
13839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o//===- subzero/src/IceRegAlloc.cpp - Linear-scan implementation -----------===// 23839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// 33839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// The Subzero Code Generator 421c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o// 521c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o// This file is distributed under the University of Illinois Open Source 621c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o// License. See LICENSE.TXT for details. 721c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o// 821c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o//===----------------------------------------------------------------------===// 921c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o/// 103839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o/// \file 113839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o/// \brief Implements the LinearScan class, which performs the linear-scan 123839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o/// register allocation after liveness analysis has been performed. 133839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o/// 143839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o//===----------------------------------------------------------------------===// 153839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 163839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o#include "IceRegAlloc.h" 173839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 183839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o#include "IceBitVector.h" 193839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o#include "IceCfg.h" 203839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o#include "IceCfgNode.h" 213839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o#include "IceInst.h" 22aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o#include "IceInstVarIter.h" 233839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o#include "IceOperand.h" 2421c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o#include "IceTargetLowering.h" 25aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o 263839e65723771b85975f4263102dd3ceec4523cTheodore Ts'onamespace Ice { 273839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 283839e65723771b85975f4263102dd3ceec4523cTheodore Ts'onamespace { 293839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 303839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// Returns true if Var has any definitions within Item's live range. 313839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// TODO(stichnot): Consider trimming the Definitions list similar to how the 323839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// live ranges are trimmed, since all the overlapsDefs() tests are whether some 333839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// variable's definitions overlap Cur, and trimming is with respect Cur.start. 343839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// Initial tests show no measurable performance difference, so we'll keep the 353839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// code simple for now. 363839e65723771b85975f4263102dd3ceec4523cTheodore Ts'obool overlapsDefs(const Cfg *Func, const Variable *Item, const Variable *Var) { 373839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o constexpr bool UseTrimmed = true; 383839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o VariablesMetadata *VMetadata = Func->getVMetadata(); 393839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o if (const Inst *FirstDef = VMetadata->getFirstDefinition(Var)) 403839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o if (Item->getLiveRange().overlapsInst(FirstDef->getNumber(), UseTrimmed)) 4150e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o return true; 4250e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o for (const Inst *Def : VMetadata->getLatterDefinitions(Var)) { 4350e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o if (Item->getLiveRange().overlapsInst(Def->getNumber(), UseTrimmed)) 443839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o return true; 453839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o } 4621c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o return false; 473839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o} 4850e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o 4950e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'ovoid dumpDisableOverlap(const Cfg *Func, const Variable *Var, 5050e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o const char *Reason) { 5150e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o if (!BuildDefs::dump()) 5250e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o return; 5350e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o if (!Func->isVerbose(IceV_LinearScan)) 543839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o return; 559d1bd3de8dd44603a8141dbe4f0b2057dbdc5ea7Theodore Ts'o 5654dc7ca2869897ae8cb81a9ab9880ebff11680bcTheodore Ts'o VariablesMetadata *VMetadata = Func->getVMetadata(); 573839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Ostream &Str = Func->getContext()->getStrDump(); 589d1bd3de8dd44603a8141dbe4f0b2057dbdc5ea7Theodore Ts'o Str << "Disabling Overlap due to " << Reason << " " << *Var 5954dc7ca2869897ae8cb81a9ab9880ebff11680bcTheodore Ts'o << " LIVE=" << Var->getLiveRange() << " Defs="; 601b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o if (const Inst *FirstDef = VMetadata->getFirstDefinition(Var)) 613839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Str << FirstDef->getNumber(); 621b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o const InstDefList &Defs = VMetadata->getLatterDefinitions(Var); 631b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o for (size_t i = 0; i < Defs.size(); ++i) { 641b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Str << "," << Defs[i]->getNumber(); 65aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o } 661b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Str << "\n"; 671b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o} 684c77fe50d97a773e32a4756c79dade3adbb6a601Theodore Ts'o 69f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'ovoid dumpLiveRange(const Variable *Var, const Cfg *Func) { 7054dc7ca2869897ae8cb81a9ab9880ebff11680bcTheodore Ts'o if (!BuildDefs::dump()) 7121c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o return; 723839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Ostream &Str = Func->getContext()->getStrDump(); 733839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o char buf[30]; 7486c627ec1136446409a0170d439e60c148e6eb48Theodore Ts'o snprintf(buf, llvm::array_lengthof(buf), "%2u", 751917875fcd16428d14eb5a86acf414472bc216f1Theodore Ts'o unsigned(Var->getRegNumTmp())); 761917875fcd16428d14eb5a86acf414472bc216f1Theodore Ts'o Str << "R=" << buf << " V="; 77246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o Var->dump(Func); 789d1bd3de8dd44603a8141dbe4f0b2057dbdc5ea7Theodore Ts'o Str << " Range=" << Var->getLiveRange(); 79246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o} 80246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o 81f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'oint32_t findMinWeightIndex( 8221c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o const SmallBitVector &RegMask, 831b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o const llvm::SmallVector<RegWeight, LinearScan::REGS_SIZE> &Weights) { 843839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o int MinWeightIndex = -1; 853839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o for (RegNumT i : RegNumBVIter(RegMask)) { 863839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o if (MinWeightIndex < 0 || Weights[i] < Weights[MinWeightIndex]) 8786c627ec1136446409a0170d439e60c148e6eb48Theodore Ts'o MinWeightIndex = i; 883839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o } 893839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o assert(MinWeightIndex >= 0); 903839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o return MinWeightIndex; 91f8188fff23dc2d9c9f858fb21264e46b17672825Theodore Ts'o} 92f8188fff23dc2d9c9f858fb21264e46b17672825Theodore Ts'o 93f8188fff23dc2d9c9f858fb21264e46b17672825Theodore Ts'o} // end of anonymous namespace 94f8188fff23dc2d9c9f858fb21264e46b17672825Theodore Ts'o 95f8188fff23dc2d9c9f858fb21264e46b17672825Theodore Ts'oLinearScan::LinearScan(Cfg *Func) 963839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o : Func(Func), Ctx(Func->getContext()), Target(Func->getTarget()), 973839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Verbose(BuildDefs::dump() && Func->isVerbose(IceV_LinearScan)), 983839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o UseReserve(Ctx->getFlags().getRegAllocReserve()) {} 993839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 1003839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// Prepare for full register allocation of all variables. We depend on liveness 1013839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// analysis to have calculated live ranges. 1029d1bd3de8dd44603a8141dbe4f0b2057dbdc5ea7Theodore Ts'ovoid LinearScan::initForGlobal() { 103246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o TimerMarker T(TimerStack::TT_initUnhandled, Func); 1043839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o FindPreference = true; 105f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o // For full register allocation, normally we want to enable FindOverlap 106f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o // (meaning we look for opportunities for two overlapping live ranges to 107f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o // safely share the same register). However, we disable it for phi-lowering 108f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o // register allocation since no overlap opportunities should be available and 109f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o // it's more expensive to look for opportunities. 11008b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o FindOverlap = (Kind != RAK_Phi); 11108b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o const VarList &Vars = Func->getVariables(); 112f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o Unhandled.reserve(Vars.size()); 113f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o UnhandledPrecolored.reserve(Vars.size()); 1147cf73dcd3d173d88ceab26d381f4abac362d8518Theodore Ts'o // Gather the live ranges of all variables and add them to the Unhandled set. 1157cf73dcd3d173d88ceab26d381f4abac362d8518Theodore Ts'o for (Variable *Var : Vars) { 1167cf73dcd3d173d88ceab26d381f4abac362d8518Theodore Ts'o // Don't consider rematerializable variables. 1171dde43f0c1176f61dd0bf91aff265ce8cd1c5fd6Theodore Ts'o if (Var->isRematerializable()) 1181dde43f0c1176f61dd0bf91aff265ce8cd1c5fd6Theodore Ts'o continue; 1191dde43f0c1176f61dd0bf91aff265ce8cd1c5fd6Theodore Ts'o // Explicitly don't consider zero-weight variables, which are meant to be 1201dde43f0c1176f61dd0bf91aff265ce8cd1c5fd6Theodore Ts'o // spill slots. 1217cf73dcd3d173d88ceab26d381f4abac362d8518Theodore Ts'o if (Var->mustNotHaveReg()) 1227cf73dcd3d173d88ceab26d381f4abac362d8518Theodore Ts'o continue; 1237cf73dcd3d173d88ceab26d381f4abac362d8518Theodore Ts'o // Don't bother if the variable has a null live range, which means it was 1247cf73dcd3d173d88ceab26d381f4abac362d8518Theodore Ts'o // never referenced. 1257cf73dcd3d173d88ceab26d381f4abac362d8518Theodore Ts'o if (Var->getLiveRange().isEmpty()) 1267fdfabd3217ebe23b36063d561fc79960275db42Theodore Ts'o continue; 1277fdfabd3217ebe23b36063d561fc79960275db42Theodore Ts'o Var->untrimLiveRange(); 1287fdfabd3217ebe23b36063d561fc79960275db42Theodore Ts'o Unhandled.push_back(Var); 1297fdfabd3217ebe23b36063d561fc79960275db42Theodore Ts'o if (Var->hasReg()) { 1307fdfabd3217ebe23b36063d561fc79960275db42Theodore Ts'o Var->setRegNumTmp(Var->getRegNum()); 1317fdfabd3217ebe23b36063d561fc79960275db42Theodore Ts'o Var->setMustHaveReg(); 1327fdfabd3217ebe23b36063d561fc79960275db42Theodore Ts'o UnhandledPrecolored.push_back(Var); 1337fdfabd3217ebe23b36063d561fc79960275db42Theodore Ts'o } 1347fdfabd3217ebe23b36063d561fc79960275db42Theodore Ts'o } 1357fdfabd3217ebe23b36063d561fc79960275db42Theodore Ts'o 1367fdfabd3217ebe23b36063d561fc79960275db42Theodore Ts'o // Build the (ordered) list of FakeKill instruction numbers. 13701fbc701413a4975e6ed551ae6ccb8bb791ea515Theodore Ts'o Kills.clear(); 1387fdfabd3217ebe23b36063d561fc79960275db42Theodore Ts'o // Phi lowering should not be creating new call instructions, so there should 1397fdfabd3217ebe23b36063d561fc79960275db42Theodore Ts'o // be no infinite-weight not-yet-colored live ranges that span a call 1407fdfabd3217ebe23b36063d561fc79960275db42Theodore Ts'o // instruction, hence no need to construct the Kills list. 1417fdfabd3217ebe23b36063d561fc79960275db42Theodore Ts'o if (Kind == RAK_Phi) 1427cf73dcd3d173d88ceab26d381f4abac362d8518Theodore Ts'o return; 1437cf73dcd3d173d88ceab26d381f4abac362d8518Theodore Ts'o for (CfgNode *Node : Func->getNodes()) { 1447cf73dcd3d173d88ceab26d381f4abac362d8518Theodore Ts'o for (Inst &I : Node->getInsts()) { 1456fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o if (auto *Kill = llvm::dyn_cast<InstFakeKill>(&I)) { 14601fbc701413a4975e6ed551ae6ccb8bb791ea515Theodore Ts'o if (!Kill->isDeleted() && !Kill->getLinked()->isDeleted()) 14701fbc701413a4975e6ed551ae6ccb8bb791ea515Theodore Ts'o Kills.push_back(I.getNumber()); 1486fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o } 1496fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o } 1506fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o } 15101fbc701413a4975e6ed551ae6ccb8bb791ea515Theodore Ts'o} 1526fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o 1536fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o// Validate the integrity of the live ranges. If there are any errors, it 1546fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o// prints details and returns false. On success, it returns true. 1556fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'obool LinearScan::livenessValidateIntervals( 1566fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o const DefUseErrorList &DefsWithoutUses, 15701fbc701413a4975e6ed551ae6ccb8bb791ea515Theodore Ts'o const DefUseErrorList &UsesBeforeDefs, 1586fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o const CfgVector<InstNumberT> &LRBegin, 1596fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o const CfgVector<InstNumberT> &LREnd) const { 1606fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o if (DefsWithoutUses.empty() && UsesBeforeDefs.empty()) 161d647a1ea4db5fa4e4ed48573c63a1bde56e071dbTheodore Ts'o return true; 162d647a1ea4db5fa4e4ed48573c63a1bde56e071dbTheodore Ts'o 163d647a1ea4db5fa4e4ed48573c63a1bde56e071dbTheodore Ts'o if (!BuildDefs::dump()) 164d647a1ea4db5fa4e4ed48573c63a1bde56e071dbTheodore Ts'o return false; 165d647a1ea4db5fa4e4ed48573c63a1bde56e071dbTheodore Ts'o 166d647a1ea4db5fa4e4ed48573c63a1bde56e071dbTheodore Ts'o const VarList &Vars = Func->getVariables(); 167d647a1ea4db5fa4e4ed48573c63a1bde56e071dbTheodore Ts'o OstreamLocker L(Ctx); 168d647a1ea4db5fa4e4ed48573c63a1bde56e071dbTheodore Ts'o Ostream &Str = Ctx->getStrDump(); 169d647a1ea4db5fa4e4ed48573c63a1bde56e071dbTheodore Ts'o for (SizeT VarNum : DefsWithoutUses) { 170d647a1ea4db5fa4e4ed48573c63a1bde56e071dbTheodore Ts'o Variable *Var = Vars[VarNum]; 171d647a1ea4db5fa4e4ed48573c63a1bde56e071dbTheodore Ts'o Str << "LR def without use, instruction " << LRBegin[VarNum] 172d647a1ea4db5fa4e4ed48573c63a1bde56e071dbTheodore Ts'o << ", variable " << Var->getName(Func) << "\n"; 173d647a1ea4db5fa4e4ed48573c63a1bde56e071dbTheodore Ts'o } 174d647a1ea4db5fa4e4ed48573c63a1bde56e071dbTheodore Ts'o for (SizeT VarNum : UsesBeforeDefs) { 175d647a1ea4db5fa4e4ed48573c63a1bde56e071dbTheodore Ts'o Variable *Var = Vars[VarNum]; 176d647a1ea4db5fa4e4ed48573c63a1bde56e071dbTheodore Ts'o Str << "LR use before def, instruction " << LREnd[VarNum] << ", variable " 177d647a1ea4db5fa4e4ed48573c63a1bde56e071dbTheodore Ts'o << Var->getName(Func) << "\n"; 178d647a1ea4db5fa4e4ed48573c63a1bde56e071dbTheodore Ts'o } 179d647a1ea4db5fa4e4ed48573c63a1bde56e071dbTheodore Ts'o return false; 180d647a1ea4db5fa4e4ed48573c63a1bde56e071dbTheodore Ts'o} 181d647a1ea4db5fa4e4ed48573c63a1bde56e071dbTheodore Ts'o 182d647a1ea4db5fa4e4ed48573c63a1bde56e071dbTheodore Ts'o// Prepare for very simple register allocation of only infinite-weight Variables 1836fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o// while respecting pre-colored Variables. Some properties we take advantage of: 18408b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o// 1853839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// * Live ranges of interest consist of a single segment. 1869d1bd3de8dd44603a8141dbe4f0b2057dbdc5ea7Theodore Ts'o// 1879d1bd3de8dd44603a8141dbe4f0b2057dbdc5ea7Theodore Ts'o// * Live ranges of interest never span a call instruction. 1881b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o// 18986c627ec1136446409a0170d439e60c148e6eb48Theodore Ts'o// * Phi instructions are not considered because either phis have already been 1903839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// lowered, or they don't contain any pre-colored or infinite-weight 1913839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// Variables. 1923839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// 1938bf191e8660939687ef35c013066d2082cb16722Theodore Ts'o// * We don't need to renumber instructions before computing live ranges because 1943839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// all the high-level ICE instructions are deleted prior to lowering, and the 1958bf191e8660939687ef35c013066d2082cb16722Theodore Ts'o// low-level instructions are added in monotonically increasing order. 1961e3472c5f37ca3686dd69b079d4d02a302f5798dTheodore Ts'o// 19721c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o// * There are no opportunities for register preference or allowing overlap. 198f8188fff23dc2d9c9f858fb21264e46b17672825Theodore Ts'o// 1995dd8f963d04fa4099a003cb3b13ffae05ab29210Theodore Ts'o// Some properties we aren't (yet) taking advantage of: 2006fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o// 2013839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// * Because live ranges are a single segment, the Inactive set will always be 2028bf191e8660939687ef35c013066d2082cb16722Theodore Ts'o// empty, and the live range trimming operation is unnecessary. 2033839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// 2048bf191e8660939687ef35c013066d2082cb16722Theodore Ts'o// * Calculating overlap of single-segment live ranges could be optimized a bit. 2051b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'ovoid LinearScan::initForInfOnly() { 2061b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o TimerMarker T(TimerStack::TT_initUnhandled, Func); 2071b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o FindPreference = false; 2081b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o FindOverlap = false; 2093839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o SizeT NumVars = 0; 2103839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o const VarList &Vars = Func->getVariables(); 2113839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 2123839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // Iterate across all instructions and record the begin and end of the live 2133839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // range for each variable that is pre-colored or infinite weight. 2149d1bd3de8dd44603a8141dbe4f0b2057dbdc5ea7Theodore Ts'o CfgVector<InstNumberT> LRBegin(Vars.size(), Inst::NumberSentinel); 2159d1bd3de8dd44603a8141dbe4f0b2057dbdc5ea7Theodore Ts'o CfgVector<InstNumberT> LREnd(Vars.size(), Inst::NumberSentinel); 2169d1bd3de8dd44603a8141dbe4f0b2057dbdc5ea7Theodore Ts'o DefUseErrorList DefsWithoutUses, UsesBeforeDefs; 2179d1bd3de8dd44603a8141dbe4f0b2057dbdc5ea7Theodore Ts'o for (CfgNode *Node : Func->getNodes()) { 2189d1bd3de8dd44603a8141dbe4f0b2057dbdc5ea7Theodore Ts'o for (Inst &Instr : Node->getInsts()) { 2199d1bd3de8dd44603a8141dbe4f0b2057dbdc5ea7Theodore Ts'o if (Instr.isDeleted()) 2209d1bd3de8dd44603a8141dbe4f0b2057dbdc5ea7Theodore Ts'o continue; 2219d1bd3de8dd44603a8141dbe4f0b2057dbdc5ea7Theodore Ts'o FOREACH_VAR_IN_INST(Var, Instr) { 2229d1bd3de8dd44603a8141dbe4f0b2057dbdc5ea7Theodore Ts'o if (Var->getIgnoreLiveness()) 2239d1bd3de8dd44603a8141dbe4f0b2057dbdc5ea7Theodore Ts'o continue; 2249d1bd3de8dd44603a8141dbe4f0b2057dbdc5ea7Theodore Ts'o if (Var->hasReg() || Var->mustHaveReg()) { 2259d1bd3de8dd44603a8141dbe4f0b2057dbdc5ea7Theodore Ts'o SizeT VarNum = Var->getIndex(); 2266fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o LREnd[VarNum] = Instr.getNumber(); 2276fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o if (!Var->getIsArg() && LRBegin[VarNum] == Inst::NumberSentinel) 2286fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o UsesBeforeDefs.push_back(VarNum); 2293839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o } 2303839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o } 2313839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o if (const Variable *Var = Instr.getDest()) { 2320c4a07264e55b42c6e30230e66b1dea7d4b94ea9Theodore Ts'o if (!Var->getIgnoreLiveness() && 2331b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o (Var->hasReg() || Var->mustHaveReg())) { 2341b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o if (LRBegin[Var->getIndex()] == Inst::NumberSentinel) { 2351b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o LRBegin[Var->getIndex()] = Instr.getNumber(); 2361b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o ++NumVars; 23708b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o } 23808b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o } 2393839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o } 2400c4a07264e55b42c6e30230e66b1dea7d4b94ea9Theodore Ts'o } 2410c4a07264e55b42c6e30230e66b1dea7d4b94ea9Theodore Ts'o } 2421b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o 2431b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Unhandled.reserve(NumVars); 2441b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o UnhandledPrecolored.reserve(NumVars); 24508b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o for (SizeT i = 0; i < Vars.size(); ++i) { 24608b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o Variable *Var = Vars[i]; 2473839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o if (Var->isRematerializable()) 248aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o continue; 2490c4a07264e55b42c6e30230e66b1dea7d4b94ea9Theodore Ts'o if (LRBegin[i] != Inst::NumberSentinel) { 250aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o if (LREnd[i] == Inst::NumberSentinel) { 251aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o DefsWithoutUses.push_back(i); 252aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o continue; 253aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o } 254aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o Unhandled.push_back(Var); 255aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o Var->resetLiveRange(); 2560c4a07264e55b42c6e30230e66b1dea7d4b94ea9Theodore Ts'o Var->addLiveRange(LRBegin[i], LREnd[i]); 2571b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Var->untrimLiveRange(); 2581b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o if (Var->hasReg()) { 2591b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Var->setRegNumTmp(Var->getRegNum()); 2601b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Var->setMustHaveReg(); 26108b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o UnhandledPrecolored.push_back(Var); 26208b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o } 2633839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o --NumVars; 2641b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o } 2651b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o } 2661b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o 2671b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o if (!livenessValidateIntervals(DefsWithoutUses, UsesBeforeDefs, LRBegin, 26808b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o LREnd)) { 26908b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o llvm::report_fatal_error("initForInfOnly: Liveness error"); 27021c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o return; 27154dc7ca2869897ae8cb81a9ab9880ebff11680bcTheodore Ts'o } 27254dc7ca2869897ae8cb81a9ab9880ebff11680bcTheodore Ts'o 27354dc7ca2869897ae8cb81a9ab9880ebff11680bcTheodore Ts'o if (!DefsWithoutUses.empty() || !UsesBeforeDefs.empty()) { 27454dc7ca2869897ae8cb81a9ab9880ebff11680bcTheodore Ts'o if (BuildDefs::dump()) { 27554dc7ca2869897ae8cb81a9ab9880ebff11680bcTheodore Ts'o OstreamLocker L(Ctx); 2763839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Ostream &Str = Ctx->getStrDump(); 2773839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o for (SizeT VarNum : DefsWithoutUses) { 2781b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Variable *Var = Vars[VarNum]; 2791b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Str << "LR def without use, instruction " << LRBegin[VarNum] 2801b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o << ", variable " << Var->getName(Func) << "\n"; 28108b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o } 28208b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o for (SizeT VarNum : UsesBeforeDefs) { 28321c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o Variable *Var = Vars[VarNum]; 2843839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Str << "LR use before def, instruction " << LREnd[VarNum] 2859cbfb8d0d97f6c5400f94d86bcbedb094f970072Theodore Ts'o << ", variable " << Var->getName(Func) << "\n"; 2869cbfb8d0d97f6c5400f94d86bcbedb094f970072Theodore Ts'o } 2879cbfb8d0d97f6c5400f94d86bcbedb094f970072Theodore Ts'o } 2889cbfb8d0d97f6c5400f94d86bcbedb094f970072Theodore Ts'o llvm::report_fatal_error("initForInfOnly: Liveness error"); 2899cbfb8d0d97f6c5400f94d86bcbedb094f970072Theodore Ts'o } 2909cbfb8d0d97f6c5400f94d86bcbedb094f970072Theodore Ts'o // This isn't actually a fatal condition, but it would be nice to know if we 2919cbfb8d0d97f6c5400f94d86bcbedb094f970072Theodore Ts'o // somehow pre-calculated Unhandled's size wrong. 2929cbfb8d0d97f6c5400f94d86bcbedb094f970072Theodore Ts'o assert(NumVars == 0); 2939cbfb8d0d97f6c5400f94d86bcbedb094f970072Theodore Ts'o 2949cbfb8d0d97f6c5400f94d86bcbedb094f970072Theodore Ts'o // Don't build up the list of Kills because we know that no infinite-weight 2959cbfb8d0d97f6c5400f94d86bcbedb094f970072Theodore Ts'o // Variable has a live range spanning a call. 2969cbfb8d0d97f6c5400f94d86bcbedb094f970072Theodore Ts'o Kills.clear(); 2979cbfb8d0d97f6c5400f94d86bcbedb094f970072Theodore Ts'o} 2989cbfb8d0d97f6c5400f94d86bcbedb094f970072Theodore Ts'o 2991b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'ovoid LinearScan::initForSecondChance() { 30054dc7ca2869897ae8cb81a9ab9880ebff11680bcTheodore Ts'o TimerMarker T(TimerStack::TT_initUnhandled, Func); 30154dc7ca2869897ae8cb81a9ab9880ebff11680bcTheodore Ts'o FindPreference = true; 302e72a9ba39471364ad2f9397f645ca547090e3485Theodore Ts'o FindOverlap = true; 3030c4a07264e55b42c6e30230e66b1dea7d4b94ea9Theodore Ts'o const VarList &Vars = Func->getVariables(); 3041b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Unhandled.reserve(Vars.size()); 3051b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o UnhandledPrecolored.reserve(Vars.size()); 3061b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o for (Variable *Var : Vars) { 3071b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o if (Var->isRematerializable()) 30808b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o continue; 30908b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o if (Var->hasReg()) { 3103839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Var->untrimLiveRange(); 31121c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o Var->setRegNumTmp(Var->getRegNum()); 3121b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Var->setMustHaveReg(); 3131b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o UnhandledPrecolored.push_back(Var); 3141b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Unhandled.push_back(Var); 31508b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o } 31608b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o } 3173839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o for (Variable *Var : Evicted) { 3181b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Var->untrimLiveRange(); 319f8188fff23dc2d9c9f858fb21264e46b17672825Theodore Ts'o Unhandled.push_back(Var); 320f8188fff23dc2d9c9f858fb21264e46b17672825Theodore Ts'o } 321f8188fff23dc2d9c9f858fb21264e46b17672825Theodore Ts'o} 322f8188fff23dc2d9c9f858fb21264e46b17672825Theodore Ts'o 323a02ce9df5ff5db2982462aec7162f7142dc18131Theodore Ts'ovoid LinearScan::init(RegAllocKind Kind) { 324a02ce9df5ff5db2982462aec7162f7142dc18131Theodore Ts'o this->Kind = Kind; 3253839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Unhandled.clear(); 32621c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o UnhandledPrecolored.clear(); 32721c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o Handled.clear(); 3281b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Inactive.clear(); 3291b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Active.clear(); 3301b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o 3311b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o SizeT NumRegs = Target->getNumRegisters(); 3321b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o RegAliases.resize(NumRegs); 3331b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o for (SizeT Reg = 0; Reg < NumRegs; ++Reg) { 3341b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o RegAliases[Reg] = &Target->getAliasesForRegister(RegNumT::fromInt(Reg)); 33508b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o } 33608b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o 3371b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o switch (Kind) { 3381b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o case RAK_Unknown: 3393839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o llvm::report_fatal_error("Invalid RAK_Unknown"); 3403839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o break; 3413839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o case RAK_Global: 3423839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o case RAK_Phi: 3433839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o initForGlobal(); 344f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o break; 34521c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o case RAK_InfOnly: 34674becf3c0a065f8d64e07ce4d31f9fe53be91d62Theodore Ts'o initForInfOnly(); 347f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o break; 34821c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o case RAK_SecondChance: 3491b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o initForSecondChance(); 3501b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o break; 3511b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o } 3521b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o 3531b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Evicted.clear(); 35408b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o 35508b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o auto CompareRanges = [](const Variable *L, const Variable *R) { 3561b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o InstNumberT Lstart = L->getLiveRange().getStart(); 3571b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o InstNumberT Rstart = R->getLiveRange().getStart(); 35821c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o if (Lstart == Rstart) 3593839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o return L->getIndex() < R->getIndex(); 3603839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o return Lstart < Rstart; 3613839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o }; 3623839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // Do a reverse sort so that erasing elements (from the end) is fast. 3633839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o std::sort(Unhandled.rbegin(), Unhandled.rend(), CompareRanges); 3643839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o std::sort(UnhandledPrecolored.rbegin(), UnhandledPrecolored.rend(), 3653839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o CompareRanges); 3663839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 36750e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o Handled.reserve(Unhandled.size()); 3681b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Inactive.reserve(Unhandled.size()); 3693839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Active.reserve(Unhandled.size()); 3703839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Evicted.reserve(Unhandled.size()); 3711b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o} 37221c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o 37308b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o// This is called when Cur must be allocated a register but no registers are 374f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o// available across Cur's live range. To handle this, we find a register that is 37521c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o// not explicitly used during Cur's live range, spill that register to a stack 376b09a4b0c906db2e520296b31855b7947e889f514Theodore Ts'o// location right before Cur's live range begins, and fill (reload) the register 3773839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// from the stack location right after Cur's live range ends. 3783839e65723771b85975f4263102dd3ceec4523cTheodore Ts'ovoid LinearScan::addSpillFill(IterationState &Iter) { 3793839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // Identify the actual instructions that begin and end Iter.Cur's live range. 3803839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // Iterate through Iter.Cur's node's instruction list until we find the actual 3813839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // instructions with instruction numbers corresponding to Iter.Cur's recorded 3823839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // live range endpoints. This sounds inefficient but shouldn't be a problem 3833839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // in practice because: 3843839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // (1) This function is almost never called in practice. 3853839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // (2) Since this register over-subscription problem happens only for 3863839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // phi-lowered instructions, the number of instructions in the node is 3873839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // proportional to the number of phi instructions in the original node, 3881b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o // which is never very large in practice. 3893839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // (3) We still have to iterate through all instructions of Iter.Cur's live 39008b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o // range to find all explicitly used registers (though the live range is 391f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o // usually only 2-3 instructions), so the main cost that could be avoided 39221c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o // would be finding the instruction that begin's Iter.Cur's live range. 3933839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o assert(!Iter.Cur->getLiveRange().isEmpty()); 3943839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o InstNumberT Start = Iter.Cur->getLiveRange().getStart(); 395f18996c8eb7f530a7a408b8ede4a99fd52c02533Theodore Ts'o InstNumberT End = Iter.Cur->getLiveRange().getEnd(); 396f18996c8eb7f530a7a408b8ede4a99fd52c02533Theodore Ts'o CfgNode *Node = Func->getVMetadata()->getLocalUseNode(Iter.Cur); 397f18996c8eb7f530a7a408b8ede4a99fd52c02533Theodore Ts'o assert(Node); 398f18996c8eb7f530a7a408b8ede4a99fd52c02533Theodore Ts'o InstList &Insts = Node->getInsts(); 399f18996c8eb7f530a7a408b8ede4a99fd52c02533Theodore Ts'o InstList::iterator SpillPoint = Insts.end(); 400f18996c8eb7f530a7a408b8ede4a99fd52c02533Theodore Ts'o InstList::iterator FillPoint = Insts.end(); 401f18996c8eb7f530a7a408b8ede4a99fd52c02533Theodore Ts'o // Stop searching after we have found both the SpillPoint and the FillPoint. 402f18996c8eb7f530a7a408b8ede4a99fd52c02533Theodore Ts'o for (auto I = Insts.begin(), E = Insts.end(); 403f18996c8eb7f530a7a408b8ede4a99fd52c02533Theodore Ts'o I != E && (SpillPoint == E || FillPoint == E); ++I) { 404f18996c8eb7f530a7a408b8ede4a99fd52c02533Theodore Ts'o if (I->getNumber() == Start) 405f18996c8eb7f530a7a408b8ede4a99fd52c02533Theodore Ts'o SpillPoint = I; 406f18996c8eb7f530a7a408b8ede4a99fd52c02533Theodore Ts'o if (I->getNumber() == End) 407f18996c8eb7f530a7a408b8ede4a99fd52c02533Theodore Ts'o FillPoint = I; 4087f88b04341d88c5df0360d930832c38040303b61Theodore Ts'o if (SpillPoint != E) { 4097f88b04341d88c5df0360d930832c38040303b61Theodore Ts'o // Remove from RegMask any physical registers referenced during Cur's live 410b09a4b0c906db2e520296b31855b7947e889f514Theodore Ts'o // range. Start looking after SpillPoint gets set, i.e. once Cur's live 411b09a4b0c906db2e520296b31855b7947e889f514Theodore Ts'o // range begins. 4121b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o FOREACH_VAR_IN_INST(Var, *I) { 41353ef44c40a3e425d2c700d8fd77a6b655aa121feTheodore Ts'o if (!Var->hasRegTmp()) 414b09a4b0c906db2e520296b31855b7947e889f514Theodore Ts'o continue; 415b09a4b0c906db2e520296b31855b7947e889f514Theodore Ts'o const auto &Aliases = *RegAliases[Var->getRegNumTmp()]; 41653ef44c40a3e425d2c700d8fd77a6b655aa121feTheodore Ts'o for (RegNumT RegAlias : RegNumBVIter(Aliases)) { 417b09a4b0c906db2e520296b31855b7947e889f514Theodore Ts'o Iter.RegMask[RegAlias] = false; 418b09a4b0c906db2e520296b31855b7947e889f514Theodore Ts'o } 419b09a4b0c906db2e520296b31855b7947e889f514Theodore Ts'o } 420b09a4b0c906db2e520296b31855b7947e889f514Theodore Ts'o } 421b09a4b0c906db2e520296b31855b7947e889f514Theodore Ts'o } 42250e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o assert(SpillPoint != Insts.end()); 42308b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o assert(FillPoint != Insts.end()); 42450e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o ++FillPoint; 42521c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o // TODO(stichnot): Randomize instead of *.begin() which maps to find_first(). 42650e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o const RegNumT RegNum = *RegNumBVIter(Iter.RegMask).begin(); 4271b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Iter.Cur->setRegNumTmp(RegNum); 4283839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Variable *Preg = Target->getPhysicalRegister(RegNum, Iter.Cur->getType()); 4293839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // TODO(stichnot): Add SpillLoc to VariablesMetadata tracking so that SpillLoc 4303839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // is correctly identified as !isMultiBlock(), reducing stack frame size. 4313839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Variable *SpillLoc = Func->makeVariable(Iter.Cur->getType()); 4323839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // Add "reg=FakeDef;spill=reg" before SpillPoint 4333839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Target->lowerInst(Node, SpillPoint, InstFakeDef::create(Func, Preg)); 4343839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Target->lowerInst(Node, SpillPoint, InstAssign::create(Func, SpillLoc, Preg)); 4353839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // add "reg=spill;FakeUse(reg)" before FillPoint 4361b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Target->lowerInst(Node, FillPoint, InstAssign::create(Func, Preg, SpillLoc)); 43721c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o Target->lowerInst(Node, FillPoint, InstFakeUse::create(Func, Preg)); 4383839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o} 43908b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o 440f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'ovoid LinearScan::handleActiveRangeExpiredOrInactive(const Variable *Cur) { 44121c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o for (SizeT I = Active.size(); I > 0; --I) { 4423839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o const SizeT Index = I - 1; 4433839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Variable *Item = Active[Index]; 4443839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Item->trimLiveRange(Cur->getLiveRange().getStart()); 4453839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o bool Moved = false; 4461e3472c5f37ca3686dd69b079d4d02a302f5798dTheodore Ts'o if (Item->rangeEndsBefore(Cur)) { 4473839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // Move Item from Active to Handled list. 4481e3472c5f37ca3686dd69b079d4d02a302f5798dTheodore Ts'o dumpLiveRangeTrace("Expiring ", Item); 4491e3472c5f37ca3686dd69b079d4d02a302f5798dTheodore Ts'o moveItem(Active, Index, Handled); 4501e3472c5f37ca3686dd69b079d4d02a302f5798dTheodore Ts'o Moved = true; 4511e3472c5f37ca3686dd69b079d4d02a302f5798dTheodore Ts'o } else if (!Item->rangeOverlapsStart(Cur)) { 4521e3472c5f37ca3686dd69b079d4d02a302f5798dTheodore Ts'o // Move Item from Active to Inactive list. 4533839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o dumpLiveRangeTrace("Inactivating ", Item); 4543839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o moveItem(Active, Index, Inactive); 4553839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Moved = true; 4561b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o } 4571e3472c5f37ca3686dd69b079d4d02a302f5798dTheodore Ts'o if (Moved) { 45808b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o // Decrement Item from RegUses[]. 45921c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o assert(Item->hasRegTmp()); 4603839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o const auto &Aliases = *RegAliases[Item->getRegNumTmp()]; 4613839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o for (RegNumT RegAlias : RegNumBVIter(Aliases)) { 4621b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o --RegUses[RegAlias]; 4631e3472c5f37ca3686dd69b079d4d02a302f5798dTheodore Ts'o assert(RegUses[RegAlias] >= 0); 4641e3472c5f37ca3686dd69b079d4d02a302f5798dTheodore Ts'o } 4651e3472c5f37ca3686dd69b079d4d02a302f5798dTheodore Ts'o } 4661e3472c5f37ca3686dd69b079d4d02a302f5798dTheodore Ts'o } 4671e3472c5f37ca3686dd69b079d4d02a302f5798dTheodore Ts'o} 4681e3472c5f37ca3686dd69b079d4d02a302f5798dTheodore Ts'o 4691e3472c5f37ca3686dd69b079d4d02a302f5798dTheodore Ts'ovoid LinearScan::handleInactiveRangeExpiredOrReactivated(const Variable *Cur) { 4701e3472c5f37ca3686dd69b079d4d02a302f5798dTheodore Ts'o for (SizeT I = Inactive.size(); I > 0; --I) { 4711e3472c5f37ca3686dd69b079d4d02a302f5798dTheodore Ts'o const SizeT Index = I - 1; 4721e3472c5f37ca3686dd69b079d4d02a302f5798dTheodore Ts'o Variable *Item = Inactive[Index]; 4731e3472c5f37ca3686dd69b079d4d02a302f5798dTheodore Ts'o Item->trimLiveRange(Cur->getLiveRange().getStart()); 4741e3472c5f37ca3686dd69b079d4d02a302f5798dTheodore Ts'o if (Item->rangeEndsBefore(Cur)) { 4751e3472c5f37ca3686dd69b079d4d02a302f5798dTheodore Ts'o // Move Item from Inactive to Handled list. 4761e3472c5f37ca3686dd69b079d4d02a302f5798dTheodore Ts'o dumpLiveRangeTrace("Expiring ", Item); 4771e3472c5f37ca3686dd69b079d4d02a302f5798dTheodore Ts'o moveItem(Inactive, Index, Handled); 4781e3472c5f37ca3686dd69b079d4d02a302f5798dTheodore Ts'o } else if (Item->rangeOverlapsStart(Cur)) { 4791e3472c5f37ca3686dd69b079d4d02a302f5798dTheodore Ts'o // Move Item from Inactive to Active list. 4801e3472c5f37ca3686dd69b079d4d02a302f5798dTheodore Ts'o dumpLiveRangeTrace("Reactivating ", Item); 481246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o moveItem(Inactive, Index, Active); 482246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o // Increment Item in RegUses[]. 4831b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o assert(Item->hasRegTmp()); 4841b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o const auto &Aliases = *RegAliases[Item->getRegNumTmp()]; 4851b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o for (RegNumT RegAlias : RegNumBVIter(Aliases)) { 4863839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o assert(RegUses[RegAlias] >= 0); 487aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o ++RegUses[RegAlias]; 4886fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o } 4896fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o } 4906fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o } 4916fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o} 4926fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o 4936fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o// Infer register preference and allowable overlap. Only form a preference when 4946fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o// the current Variable has an unambiguous "first" definition. The preference is 4956fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o// some source Variable of the defining instruction that either is assigned a 4966fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o// register that is currently free, or that is assigned a register that is not 4976fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o// free but overlap is allowed. Overlap is allowed when the Variable under 4986fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o// consideration is single-definition, and its definition is a simple assignment 4996fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o// - i.e., the register gets copied/aliased but is never modified. Furthermore, 500aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o// overlap is only allowed when preferred Variable definition instructions do 5013839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// not appear within the current Variable's live range. 50250e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'ovoid LinearScan::findRegisterPreference(IterationState &Iter) { 5031b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Iter.Prefer = nullptr; 50408b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o Iter.PreferReg = RegNumT(); 5051b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Iter.AllowOverlap = false; 506aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o 507aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o if (!FindPreference) 5081b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o return; 509aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o 5106fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o VariablesMetadata *VMetadata = Func->getVMetadata(); 5116fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o const Inst *DefInst = VMetadata->getFirstDefinitionSingleBlock(Iter.Cur); 512d647a1ea4db5fa4e4ed48573c63a1bde56e071dbTheodore Ts'o if (DefInst == nullptr) 5131b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o return; 5146fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o 5156fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o assert(DefInst->getDest() == Iter.Cur); 5166fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o const bool IsSingleDefAssign = 517d647a1ea4db5fa4e4ed48573c63a1bde56e071dbTheodore Ts'o DefInst->isVarAssign() && !VMetadata->isMultiDef(Iter.Cur); 5181b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o FOREACH_VAR_IN_INST(SrcVar, *DefInst) { 5196fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o // Only consider source variables that have (so far) been assigned a 5201b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o // register. 52121c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o if (!SrcVar->hasRegTmp()) 5221b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o continue; 52321c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o 52421c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o // That register must be one in the RegMask set, e.g. don't try to prefer 5253839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // the stack pointer as a result of the stacksave intrinsic. 5261dde43f0c1176f61dd0bf91aff265ce8cd1c5fd6Theodore Ts'o const auto &Aliases = *RegAliases[SrcVar->getRegNumTmp()]; 5276fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o const int SrcReg = (Iter.RegMask & Aliases).find_first(); 5286fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o if (SrcReg == -1) 529d647a1ea4db5fa4e4ed48573c63a1bde56e071dbTheodore Ts'o continue; 5301b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o 5316fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o if (FindOverlap && IsSingleDefAssign && !Iter.Free[SrcReg]) { 5326fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o // Don't bother trying to enable AllowOverlap if the register is already 5336fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o // free (hence the test on Iter.Free[SrcReg]). 534d647a1ea4db5fa4e4ed48573c63a1bde56e071dbTheodore Ts'o Iter.AllowOverlap = !overlapsDefs(Func, Iter.Cur, SrcVar); 535d647a1ea4db5fa4e4ed48573c63a1bde56e071dbTheodore Ts'o } 5366fdc7a325c8bff67fc3a0489d0858bc7c48dc1a3Theodore Ts'o if (Iter.AllowOverlap || Iter.Free[SrcReg]) { 5371b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Iter.Prefer = SrcVar; 5381b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Iter.PreferReg = RegNumT::fromInt(SrcReg); 5391b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o // Stop looking for a preference after the first valid preference is 5403839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // found. One might think that we should look at all instruction 54150e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o // variables to find the best <Prefer,AllowOverlap> combination, but note 5421b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o // that AllowOverlap can only be true for a simple assignment statement 54350e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o // which can have only one source operand, so it's not possible for 5441b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o // AllowOverlap to be true beyond the first source operand. 54550e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o FOREACH_VAR_IN_INST_BREAK; 5461b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o } 5473839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o } 5483839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o if (BuildDefs::dump() && Verbose && Iter.Prefer) { 5493839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Ostream &Str = Ctx->getStrDump(); 5503839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Str << "Initial Iter.Prefer="; 5513839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Iter.Prefer->dump(Func); 5523839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Str << " R=" << Iter.PreferReg << " LIVE=" << Iter.Prefer->getLiveRange() 553f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o << " Overlap=" << Iter.AllowOverlap << "\n"; 5541b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o } 5553839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o} 556a02ce9df5ff5db2982462aec7162f7142dc18131Theodore Ts'o 55708b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o// Remove registers from the Iter.Free[] list where an Inactive range overlaps 55808b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o// with the current range. 55908b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'ovoid LinearScan::filterFreeWithInactiveRanges(IterationState &Iter) { 5601b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o for (const Variable *Item : Inactive) { 56108b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o if (!Item->rangeOverlaps(Iter.Cur)) 562a02ce9df5ff5db2982462aec7162f7142dc18131Theodore Ts'o continue; 56308b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o const auto &Aliases = *RegAliases[Item->getRegNumTmp()]; 56408b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o for (RegNumT RegAlias : RegNumBVIter(Aliases)) { 5653839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // Don't assert(Iter.Free[RegAlias]) because in theory (though probably 5661b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o // never in practice) there could be two inactive variables that were 5672df1f6aa071e09527d1767e0d5178f29b4e9a73cTheodore Ts'o // marked with AllowOverlap. 5682df1f6aa071e09527d1767e0d5178f29b4e9a73cTheodore Ts'o Iter.Free[RegAlias] = false; 5691b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Iter.FreeUnfiltered[RegAlias] = false; 5701b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o // Disable AllowOverlap if an Inactive variable, which is not Prefer, 5711b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o // shares Prefer's register, and has a definition within Cur's live range. 5721b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o if (Iter.AllowOverlap && Item != Iter.Prefer && 5731b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o RegAlias == Iter.PreferReg && overlapsDefs(Func, Iter.Cur, Item)) { 57421c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o Iter.AllowOverlap = false; 57521c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o dumpDisableOverlap(Func, Item, "Inactive"); 5761b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o } 5771b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o } 57808b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o } 57908b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o} 5803839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 5813839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// Remove registers from the Iter.Free[] list where an Unhandled pre-colored 5821b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o// range overlaps with the current range, and set those registers to infinite 5833839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// weight so that they aren't candidates for eviction. 5843839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// Cur->rangeEndsBefore(Item) is an early exit check that turns a guaranteed 5853839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// O(N^2) algorithm into expected linear complexity. 5861b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'ovoid LinearScan::filterFreeWithPrecoloredRanges(IterationState &Iter) { 5871b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o // TODO(stichnot): Partition UnhandledPrecolored according to register class, 588f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o // to restrict the number of overlap comparisons needed. 58908b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o for (Variable *Item : reverse_range(UnhandledPrecolored)) { 590aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o assert(Item->hasReg()); 591aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o if (Iter.Cur->rangeEndsBefore(Item)) 592aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o break; 593aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o if (!Item->rangeOverlaps(Iter.Cur)) 594aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o continue; 595aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o const auto &Aliases = 596aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o *RegAliases[Item->getRegNum()]; // Note: not getRegNumTmp() 597f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o for (RegNumT RegAlias : RegNumBVIter(Aliases)) { 598f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o Iter.Weights[RegAlias].setWeight(RegWeight::Inf); 599f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o Iter.Free[RegAlias] = false; 600f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o Iter.FreeUnfiltered[RegAlias] = false; 6011b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Iter.PrecoloredUnhandledMask[RegAlias] = true; 6021b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o // Disable Iter.AllowOverlap if the preferred register is one of these 6031b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o // pre-colored unhandled overlapping ranges. 6041b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o if (Iter.AllowOverlap && RegAlias == Iter.PreferReg) { 6053839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Iter.AllowOverlap = false; 60608b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o dumpDisableOverlap(Func, Item, "PrecoloredUnhandled"); 6073839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o } 60808b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o } 609f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o } 610e72a9ba39471364ad2f9397f645ca547090e3485Theodore Ts'o} 6111e3472c5f37ca3686dd69b079d4d02a302f5798dTheodore Ts'o 61208b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'ovoid LinearScan::allocatePrecoloredRegister(Variable *Cur) { 61321c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o const auto RegNum = Cur->getRegNum(); 6148188c9e6b3dc73c528ebaa6c65e7a96ccef807d1Theodore Ts'o // RegNumTmp should have already been set above. 615f5ae75e5f0e1b509311fac5944167bc0d8674c38Theodore Ts'o assert(Cur->getRegNumTmp() == RegNum); 616f5ae75e5f0e1b509311fac5944167bc0d8674c38Theodore Ts'o dumpLiveRangeTrace("Precoloring ", Cur); 6178188c9e6b3dc73c528ebaa6c65e7a96ccef807d1Theodore Ts'o Active.push_back(Cur); 6188188c9e6b3dc73c528ebaa6c65e7a96ccef807d1Theodore Ts'o const auto &Aliases = *RegAliases[RegNum]; 619246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o for (RegNumT RegAlias : RegNumBVIter(Aliases)) { 620246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o assert(RegUses[RegAlias] >= 0); 621246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o ++RegUses[RegAlias]; 6228188c9e6b3dc73c528ebaa6c65e7a96ccef807d1Theodore Ts'o } 6238188c9e6b3dc73c528ebaa6c65e7a96ccef807d1Theodore Ts'o assert(!UnhandledPrecolored.empty()); 6248188c9e6b3dc73c528ebaa6c65e7a96ccef807d1Theodore Ts'o assert(UnhandledPrecolored.back() == Cur); 6258188c9e6b3dc73c528ebaa6c65e7a96ccef807d1Theodore Ts'o UnhandledPrecolored.pop_back(); 6268188c9e6b3dc73c528ebaa6c65e7a96ccef807d1Theodore Ts'o} 627246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o 628874b4d262e9664c08622611087c341f6aa242bc8Theodore Ts'ovoid LinearScan::allocatePreferredRegister(IterationState &Iter) { 629246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o Iter.Cur->setRegNumTmp(Iter.PreferReg); 630246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o dumpLiveRangeTrace("Preferring ", Iter.Cur); 631874b4d262e9664c08622611087c341f6aa242bc8Theodore Ts'o const auto &Aliases = *RegAliases[Iter.PreferReg]; 632246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o for (RegNumT RegAlias : RegNumBVIter(Aliases)) { 633246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o assert(RegUses[RegAlias] >= 0); 634246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o ++RegUses[RegAlias]; 635246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o } 636246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o Active.push_back(Iter.Cur); 6378bf191e8660939687ef35c013066d2082cb16722Theodore Ts'o} 6385596defa1e212242c1bf1b028139143fbb7777a0Theodore Ts'o 6395596defa1e212242c1bf1b028139143fbb7777a0Theodore Ts'ovoid LinearScan::allocateFreeRegister(IterationState &Iter, bool Filtered) { 6400c4a07264e55b42c6e30230e66b1dea7d4b94ea9Theodore Ts'o const RegNumT RegNum = 6415596defa1e212242c1bf1b028139143fbb7777a0Theodore Ts'o *RegNumBVIter(Filtered ? Iter.Free : Iter.FreeUnfiltered).begin(); 6428bf191e8660939687ef35c013066d2082cb16722Theodore Ts'o Iter.Cur->setRegNumTmp(RegNum); 6433839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o if (Filtered) 6443839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o dumpLiveRangeTrace("Allocating Y ", Iter.Cur); 6453839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o else 646f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o dumpLiveRangeTrace("Allocating X ", Iter.Cur); 647f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o const auto &Aliases = *RegAliases[RegNum]; 648f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o for (RegNumT RegAlias : RegNumBVIter(Aliases)) { 649f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o assert(RegUses[RegAlias] >= 0); 65054dc7ca2869897ae8cb81a9ab9880ebff11680bcTheodore Ts'o ++RegUses[RegAlias]; 651f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o } 65254dc7ca2869897ae8cb81a9ab9880ebff11680bcTheodore Ts'o Active.push_back(Iter.Cur); 653f8188fff23dc2d9c9f858fb21264e46b17672825Theodore Ts'o} 654f8188fff23dc2d9c9f858fb21264e46b17672825Theodore Ts'o 65554dc7ca2869897ae8cb81a9ab9880ebff11680bcTheodore Ts'ovoid LinearScan::handleNoFreeRegisters(IterationState &Iter) { 656f8188fff23dc2d9c9f858fb21264e46b17672825Theodore Ts'o // Check Active ranges. 657f8188fff23dc2d9c9f858fb21264e46b17672825Theodore Ts'o for (const Variable *Item : Active) { 65854dc7ca2869897ae8cb81a9ab9880ebff11680bcTheodore Ts'o assert(Item->rangeOverlaps(Iter.Cur)); 659f8188fff23dc2d9c9f858fb21264e46b17672825Theodore Ts'o assert(Item->hasRegTmp()); 660f8188fff23dc2d9c9f858fb21264e46b17672825Theodore Ts'o const auto &Aliases = *RegAliases[Item->getRegNumTmp()]; 661a02ce9df5ff5db2982462aec7162f7142dc18131Theodore Ts'o // We add the Item's weight to each alias/subregister to represent that, 662a02ce9df5ff5db2982462aec7162f7142dc18131Theodore Ts'o // should we decide to pick any of them, then we would incur that many 663a02ce9df5ff5db2982462aec7162f7142dc18131Theodore Ts'o // memory accesses. 664f8188fff23dc2d9c9f858fb21264e46b17672825Theodore Ts'o RegWeight W = Item->getWeight(Func); 665f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o for (RegNumT RegAlias : RegNumBVIter(Aliases)) { 666f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o Iter.Weights[RegAlias].addWeight(W); 667f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o } 668f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o } 6693839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // Same as above, but check Inactive ranges instead of Active. 6703839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o for (const Variable *Item : Inactive) { 6711b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o if (!Item->rangeOverlaps(Iter.Cur)) 6723839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o continue; 6733839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o assert(Item->hasRegTmp()); 6743839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o const auto &Aliases = *RegAliases[Item->getRegNumTmp()]; 67586c627ec1136446409a0170d439e60c148e6eb48Theodore Ts'o RegWeight W = Item->getWeight(Func); 6763839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o for (RegNumT RegAlias : RegNumBVIter(Aliases)) { 6773839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Iter.Weights[RegAlias].addWeight(W); 67821c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o } 67921c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o } 6803839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 681f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o // All the weights are now calculated. Find the register with smallest weight. 6823839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o int32_t MinWeightIndex = findMinWeightIndex(Iter.RegMask, Iter.Weights); 68386a63e92eb4a957d8e24795cefd2f7058e4aec30Theodore Ts'o 68486a63e92eb4a957d8e24795cefd2f7058e4aec30Theodore Ts'o if (Iter.Cur->getWeight(Func) <= Iter.Weights[MinWeightIndex]) { 6853839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o if (!Iter.Cur->mustHaveReg()) { 6861b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o // Iter.Cur doesn't have priority over any other live ranges, so don't 6871b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o // allocate any register to it, and move it to the Handled state. 6883839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Handled.push_back(Iter.Cur); 6893839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o return; 69021c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o } 6913839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o if (Kind == RAK_Phi) { 6921b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o // Iter.Cur is infinite-weight but all physical registers are already 6931b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o // taken, so we need to force one to be temporarily available. 69421c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o addSpillFill(Iter); 6953839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Handled.push_back(Iter.Cur); 69621c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o return; 6973839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o } 69886c627ec1136446409a0170d439e60c148e6eb48Theodore Ts'o // The remaining portion of the enclosing "if" block should only be 6990c4a07264e55b42c6e30230e66b1dea7d4b94ea9Theodore Ts'o // reachable if we are manually limiting physical registers for testing. 7003839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o if (UseReserve) { 7011b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o if (Iter.FreeUnfiltered.any()) { 702a02ce9df5ff5db2982462aec7162f7142dc18131Theodore Ts'o // There is some available physical register held in reserve, so use it. 7032df1f6aa071e09527d1767e0d5178f29b4e9a73cTheodore Ts'o constexpr bool NotFiltered = false; 7043839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o allocateFreeRegister(Iter, NotFiltered); 7051b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o // Iter.Cur is now on the Active list. 7061b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o return; 7073839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o } 7083839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // At this point, we need to find some reserve register that is already 709f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o // assigned to a non-infinite-weight variable. This could happen if some 7103839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // variable was previously assigned an alias of such a register. 7113839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o MinWeightIndex = findMinWeightIndex(Iter.RegMaskUnfiltered, Iter.Weights); 7123839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o } 7133839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o if (Iter.Cur->getWeight(Func) <= Iter.Weights[MinWeightIndex]) { 7144c77fe50d97a773e32a4756c79dade3adbb6a601Theodore Ts'o dumpLiveRangeTrace("Failing ", Iter.Cur); 7153839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Func->setError("Unable to find a physical register for an " 7163839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o "infinite-weight live range " 7173839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o "(consider using -reg-reserve): " + 7183839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Iter.Cur->getName(Func)); 7193839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Handled.push_back(Iter.Cur); 7203839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o return; 7213839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o } 7223839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // At this point, MinWeightIndex points to a valid reserve register to 7233839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // reallocate to Iter.Cur, so drop into the eviction code. 7243839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o } 7253839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 7263839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // Evict all live ranges in Active that register number MinWeightIndex is 7273839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // assigned to. 7281b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o const auto &Aliases = *RegAliases[MinWeightIndex]; 7293839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o for (SizeT I = Active.size(); I > 0; --I) { 7301b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o const SizeT Index = I - 1; 7311b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Variable *Item = Active[Index]; 7321b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o const auto RegNum = Item->getRegNumTmp(); 7333839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o if (Aliases[RegNum]) { 7340c4a07264e55b42c6e30230e66b1dea7d4b94ea9Theodore Ts'o dumpLiveRangeTrace("Evicting A ", Item); 7351b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o const auto &Aliases = *RegAliases[RegNum]; 7361b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o for (RegNumT RegAlias : RegNumBVIter(Aliases)) { 7371b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o --RegUses[RegAlias]; 7381b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o assert(RegUses[RegAlias] >= 0); 73908b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o } 74008b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o Item->setRegNumTmp(RegNumT()); 74108b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o moveItem(Active, Index, Handled); 7423839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Evicted.push_back(Item); 7433839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o } 7443839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o } 7453839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // Do the same for Inactive. 74621c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o for (SizeT I = Inactive.size(); I > 0; --I) { 74721c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o const SizeT Index = I - 1; 7481b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Variable *Item = Inactive[Index]; 74921c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o // Note: The Item->rangeOverlaps(Cur) clause is not part of the description 7501b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o // of AssignMemLoc() in the original paper. But there doesn't seem to be any 75121c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o // need to evict an inactive live range that doesn't overlap with the live 7521b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o // range currently being considered. It's especially bad if we would end up 7531b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o // evicting an infinite-weight but currently-inactive live range. The most 7540c4a07264e55b42c6e30230e66b1dea7d4b94ea9Theodore Ts'o // common situation for this would be a scratch register kill set for call 7551b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o // instructions. 7561b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o if (Aliases[Item->getRegNumTmp()] && Item->rangeOverlaps(Iter.Cur)) { 7571b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o dumpLiveRangeTrace("Evicting I ", Item); 7581b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Item->setRegNumTmp(RegNumT()); 75908b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o moveItem(Inactive, Index, Handled); 76008b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o Evicted.push_back(Item); 76108b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o } 76221c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o } 76321c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o // Assign the register to Cur. 76421c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o Iter.Cur->setRegNumTmp(RegNumT::fromInt(MinWeightIndex)); 76521c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o for (RegNumT RegAlias : RegNumBVIter(Aliases)) { 766aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o assert(RegUses[RegAlias] >= 0); 767aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o ++RegUses[RegAlias]; 768aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o } 769aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o Active.push_back(Iter.Cur); 770aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o dumpLiveRangeTrace("Allocating Z ", Iter.Cur); 771aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o} 772aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o 773aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'ovoid LinearScan::assignFinalRegisters(const SmallBitVector &RegMaskFull, 7740c4a07264e55b42c6e30230e66b1dea7d4b94ea9Theodore Ts'o const SmallBitVector &PreDefinedRegisters, 775aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o bool Randomized) { 776aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o const size_t NumRegisters = RegMaskFull.size(); 777aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o llvm::SmallVector<RegNumT, REGS_SIZE> Permutation(NumRegisters); 778aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o if (Randomized) { 779aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o // Create a random number generator for regalloc randomization. Merge 780aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o // function's sequence and Kind value as the Salt. Because regAlloc() is 781aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o // called twice under O2, the second time with RAK_Phi, we check Kind == 782aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o // RAK_Phi to determine the lowest-order bit to make sure the Salt is 783aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o // different. 784aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o uint64_t Salt = 785aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o (Func->getSequenceNumber() << 1) ^ (Kind == RAK_Phi ? 0u : 1u); 7863839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Target->makeRandomRegisterPermutation( 7873839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Permutation, PreDefinedRegisters | ~RegMaskFull, Salt); 78850e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o } 78950e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o 79050e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o // Finish up by setting RegNum = RegNumTmp (or a random permutation thereof) 7913839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // for each Variable. 7921b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o for (Variable *Item : Handled) { 7933839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o const auto RegNum = Item->getRegNumTmp(); 7941b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o auto AssignedRegNum = RegNum; 7951b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o 7961b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o if (Randomized && Item->hasRegTmp() && !Item->hasReg()) { 7973839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o AssignedRegNum = Permutation[RegNum]; 7981b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o } 7991b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o if (BuildDefs::dump() && Verbose) { 8001b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Ostream &Str = Ctx->getStrDump(); 8010c4a07264e55b42c6e30230e66b1dea7d4b94ea9Theodore Ts'o if (!Item->hasRegTmp()) { 8021b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Str << "Not assigning "; 8031b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Item->dump(Func); 8041b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Str << "\n"; 8051b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o } else { 8061b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Str << (AssignedRegNum == Item->getRegNum() ? "Reassigning " 80708b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o : "Assigning ") 80808b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o << Target->getRegName(AssignedRegNum, Item->getType()) << "(r" 80908b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o << AssignedRegNum << ") to "; 8103839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Item->dump(Func); 8113839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Str << "\n"; 8121b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o } 8133839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o } 8141b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Item->setRegNum(AssignedRegNum); 8153839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o } 8163839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o} 8173839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 8183839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// Implements the linear-scan algorithm. Based on "Linear Scan Register 8193839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// Allocation in the Context of SSA Form and Register Constraints" by Hanspeter 8203839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// Mössenböck and Michael Pfeiffer, 8213839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// ftp://ftp.ssw.uni-linz.ac.at/pub/Papers/Moe02.PDF. This implementation is 8221b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o// modified to take affinity into account and allow two interfering variables to 8233839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// share the same register in certain cases. 8243839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// 8251b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o// Requires running Cfg::liveness(Liveness_Intervals) in preparation. Results 8263839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o// are assigned to Variable::RegNum for each Variable. 82786c627ec1136446409a0170d439e60c148e6eb48Theodore Ts'ovoid LinearScan::scan(const SmallBitVector &RegMaskFull, bool Randomized) { 82821c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o TimerMarker T(TimerStack::TT_linearScan, Func); 829246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o assert(RegMaskFull.any()); // Sanity check 830246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o if (Verbose) 8313839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Ctx->lockStr(); 83221c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o Func->resetCurrentNode(); 8333839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o const size_t NumRegisters = RegMaskFull.size(); 8343839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o SmallBitVector PreDefinedRegisters(NumRegisters); 8353839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o if (Randomized) { 8363839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o for (Variable *Var : UnhandledPrecolored) { 837f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o PreDefinedRegisters[Var->getRegNum()] = true; 83821c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o } 83974becf3c0a065f8d64e07ce4d31f9fe53be91d62Theodore Ts'o } 8401917875fcd16428d14eb5a86acf414472bc216f1Theodore Ts'o 84174becf3c0a065f8d64e07ce4d31f9fe53be91d62Theodore Ts'o // Build a LiveRange representing the Kills list. 84221c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o LiveRange KillsRange(Kills); 843f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o KillsRange.untrim(); 84421c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o 8451b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o // Reset the register use count. 8461b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o RegUses.resize(NumRegisters); 8471917875fcd16428d14eb5a86acf414472bc216f1Theodore Ts'o std::fill(RegUses.begin(), RegUses.end(), 0); 8481917875fcd16428d14eb5a86acf414472bc216f1Theodore Ts'o 849f5ae75e5f0e1b509311fac5944167bc0d8674c38Theodore Ts'o // Unhandled is already set to all ranges in increasing order of start points. 850f5ae75e5f0e1b509311fac5944167bc0d8674c38Theodore Ts'o assert(Active.empty()); 8511917875fcd16428d14eb5a86acf414472bc216f1Theodore Ts'o assert(Inactive.empty()); 8521917875fcd16428d14eb5a86acf414472bc216f1Theodore Ts'o assert(Handled.empty()); 8531917875fcd16428d14eb5a86acf414472bc216f1Theodore Ts'o const TargetLowering::RegSetMask RegsInclude = 8541917875fcd16428d14eb5a86acf414472bc216f1Theodore Ts'o TargetLowering::RegSet_CallerSave; 8551917875fcd16428d14eb5a86acf414472bc216f1Theodore Ts'o const TargetLowering::RegSetMask RegsExclude = TargetLowering::RegSet_None; 8561917875fcd16428d14eb5a86acf414472bc216f1Theodore Ts'o const SmallBitVector KillsMask = 8571917875fcd16428d14eb5a86acf414472bc216f1Theodore Ts'o Target->getRegisterSet(RegsInclude, RegsExclude); 8581917875fcd16428d14eb5a86acf414472bc216f1Theodore Ts'o 8591917875fcd16428d14eb5a86acf414472bc216f1Theodore Ts'o // Allocate memory once outside the loop. 8601917875fcd16428d14eb5a86acf414472bc216f1Theodore Ts'o IterationState Iter; 8611b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Iter.Weights.reserve(NumRegisters); 86221c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o Iter.PrecoloredUnhandledMask.reserve(NumRegisters); 86321c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o 864a02ce9df5ff5db2982462aec7162f7142dc18131Theodore Ts'o while (!Unhandled.empty()) { 86508b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o Iter.Cur = Unhandled.back(); 8661b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o Unhandled.pop_back(); 8671b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o dumpLiveRangeTrace("\nConsidering ", Iter.Cur); 8681b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o assert(Target->getRegistersForVariable(Iter.Cur).any()); 8693839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Iter.RegMask = RegMaskFull & Target->getRegistersForVariable(Iter.Cur); 87074becf3c0a065f8d64e07ce4d31f9fe53be91d62Theodore Ts'o Iter.RegMaskUnfiltered = 8711b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o RegMaskFull & Target->getAllRegistersForVariable(Iter.Cur); 87274becf3c0a065f8d64e07ce4d31f9fe53be91d62Theodore Ts'o KillsRange.trim(Iter.Cur->getLiveRange().getStart()); 873f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o 87408b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o // Check for pre-colored ranges. If Cur is pre-colored, it definitely gets 875f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o // that register. Previously processed live ranges would have avoided that 8761b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o // register due to it being pre-colored. Future processed live ranges won't 877f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o // evict that register because the live range has infinite weight. 87808b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o if (Iter.Cur->hasReg()) { 8791b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o allocatePrecoloredRegister(Iter.Cur); 880aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o continue; 8811b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o } 882f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o 883f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o handleActiveRangeExpiredOrInactive(Iter.Cur); 884f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o handleInactiveRangeExpiredOrReactivated(Iter.Cur); 885f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o 886f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o // Calculate available registers into Iter.Free[] and Iter.FreeUnfiltered[]. 88708b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o Iter.Free = Iter.RegMask; 888f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o Iter.FreeUnfiltered = Iter.RegMaskUnfiltered; 889f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o for (SizeT i = 0; i < Iter.RegMask.size(); ++i) { 890f3db3566b5e1342e49dffc5ec3f418a838584194Theodore Ts'o if (RegUses[i] > 0) { 8913839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Iter.Free[i] = false; 8923839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Iter.FreeUnfiltered[i] = false; 893246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o } 8943839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o } 8953839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 8963839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o findRegisterPreference(Iter); 8973839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o filterFreeWithInactiveRanges(Iter); 8981b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o 8993839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // Disable AllowOverlap if an Active variable, which is not Prefer, shares 9001b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o // Prefer's register, and has a definition within Cur's live range. 9013839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o if (Iter.AllowOverlap) { 90208b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o const auto &Aliases = *RegAliases[Iter.PreferReg]; 9031b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o for (const Variable *Item : Active) { 904aa4115a47c554a936fdf5e6679e72a9329fecf45Theodore Ts'o const RegNumT RegNum = Item->getRegNumTmp(); 9051b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o if (Item != Iter.Prefer && Aliases[RegNum] && 9061b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o overlapsDefs(Func, Iter.Cur, Item)) { 90750e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o Iter.AllowOverlap = false; 90821c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o dumpDisableOverlap(Func, Item, "Active"); 9093839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o } 910246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o } 911246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o } 912246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o 913246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o Iter.Weights.resize(Iter.RegMask.size()); 914246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o std::fill(Iter.Weights.begin(), Iter.Weights.end(), RegWeight()); 915246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o 916246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o Iter.PrecoloredUnhandledMask.resize(Iter.RegMask.size()); 9175dd8f963d04fa4099a003cb3b13ffae05ab29210Theodore Ts'o Iter.PrecoloredUnhandledMask.reset(); 9189d1bd3de8dd44603a8141dbe4f0b2057dbdc5ea7Theodore Ts'o 919246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o filterFreeWithPrecoloredRanges(Iter); 920246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o 921246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o // Remove scratch registers from the Iter.Free[] list, and mark their 922246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o // Iter.Weights[] as infinite, if KillsRange overlaps Cur's live range. 9239d1bd3de8dd44603a8141dbe4f0b2057dbdc5ea7Theodore Ts'o constexpr bool UseTrimmed = true; 924246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o if (Iter.Cur->getLiveRange().overlaps(KillsRange, UseTrimmed)) { 9259d1bd3de8dd44603a8141dbe4f0b2057dbdc5ea7Theodore Ts'o Iter.Free.reset(KillsMask); 926246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o Iter.FreeUnfiltered.reset(KillsMask); 927246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o for (RegNumT i : RegNumBVIter(KillsMask)) { 92821c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o Iter.Weights[i].setWeight(RegWeight::Inf); 9291b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o if (Iter.PreferReg == i) 93021c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o Iter.AllowOverlap = false; 931246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o } 932246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o } 93308b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o 93421c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o // Print info about physical register availability. 93521c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o if (BuildDefs::dump() && Verbose) { 9363839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Ostream &Str = Ctx->getStrDump(); 937246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o for (RegNumT i : RegNumBVIter(Iter.RegMaskUnfiltered)) { 938246501c612cb8309dc81b354b785405bbeef05ceTheodore Ts'o Str << Target->getRegName(i, Iter.Cur->getType()) << "(U=" << RegUses[i] 9393839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o << ",F=" << Iter.Free[i] << ",P=" << Iter.PrecoloredUnhandledMask[i] 94021c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o << ") "; 9411b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o } 9423839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Str << "\n"; 94308b213017f8371ce4b56ad4d368eb0f92211d04eTheodore Ts'o } 94421c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o 94521c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o if (Iter.Prefer && (Iter.AllowOverlap || Iter.Free[Iter.PreferReg])) { 9463839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o // First choice: a preferred register that is either free or is allowed to 94750e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o // overlap with its linked variable. 94850e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o allocatePreferredRegister(Iter); 94921c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o } else if (Iter.Free.any()) { 95050e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o // Second choice: any free register. 95150e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o constexpr bool Filtered = true; 95250e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o allocateFreeRegister(Iter, Filtered); 95350e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o } else { 95450e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o // Fallback: there are no free registers, so we look for the lowest-weight 95550e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o // register and see if Cur has higher weight. 95650e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o handleNoFreeRegisters(Iter); 95750e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o } 95850e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o dump(Func); 95950e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o } 96050e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o 96150e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o // Move anything Active or Inactive to Handled for easier handling. 96250e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o Handled.insert(Handled.end(), Active.begin(), Active.end()); 96350e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o Active.clear(); 96450e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o Handled.insert(Handled.end(), Inactive.begin(), Inactive.end()); 96550e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o Inactive.clear(); 96650e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o dump(Func); 96750e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o 96850e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o assignFinalRegisters(RegMaskFull, PreDefinedRegisters, Randomized); 96950e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o 97050e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o if (Verbose) 97150e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o Ctx->unlockStr(); 97250e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o} 97350e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o 97450e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o// ======================== Dump routines ======================== // 97550e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o 97650e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'ovoid LinearScan::dumpLiveRangeTrace(const char *Label, const Variable *Item) { 97750e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o if (!BuildDefs::dump()) 97850e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o return; 97950e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o 98050e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o if (Verbose) { 98150e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o Ostream &Str = Ctx->getStrDump(); 98250e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o Str << Label; 98350e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o dumpLiveRange(Item, Func); 98450e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o Str << "\n"; 98550e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o } 98650e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o} 98750e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o 98850e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'ovoid LinearScan::dump(Cfg *Func) const { 98950e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o if (!BuildDefs::dump()) 99050e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o return; 99150e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o if (!Verbose) 99250e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o return; 99350e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o Ostream &Str = Func->getContext()->getStrDump(); 99450e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o Func->resetCurrentNode(); 99550e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o Str << "**** Current regalloc state:\n"; 99650e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o Str << "++++++ Handled:\n"; 99750e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o for (const Variable *Item : Handled) { 99850e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o dumpLiveRange(Item, Func); 99921c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o Str << "\n"; 10003839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o } 10013839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Str << "++++++ Unhandled:\n"; 10023839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o for (const Variable *Item : reverse_range(Unhandled)) { 10033839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o dumpLiveRange(Item, Func); 100453ef44c40a3e425d2c700d8fd77a6b655aa121feTheodore Ts'o Str << "\n"; 10053839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o } 10069d1bd3de8dd44603a8141dbe4f0b2057dbdc5ea7Theodore Ts'o Str << "++++++ Active:\n"; 100721c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o for (const Variable *Item : Active) { 100821c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o dumpLiveRange(Item, Func); 100954dc7ca2869897ae8cb81a9ab9880ebff11680bcTheodore Ts'o Str << "\n"; 10103839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o } 10113839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o Str << "++++++ Inactive:\n"; 101221c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o for (const Variable *Item : Inactive) { 10133839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o dumpLiveRange(Item, Func); 101450e1e10fa0ac12a3e2a9d20a75ee9041873cda96Theodore Ts'o Str << "\n"; 101521c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o } 10161b6bf1759af884957234b7dce768b785f792abd0Theodore Ts'o} 10173839e65723771b85975f4263102dd3ceec4523cTheodore Ts'o 101854dc7ca2869897ae8cb81a9ab9880ebff11680bcTheodore Ts'o} // end of namespace Ice 101921c84b71e205b5ab13f14343da5645dcc985856dTheodore Ts'o