IceRegAlloc.cpp revision 696605575c4ba11df5ec56149c561839d1bfe532
1d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth//===- subzero/src/IceRegAlloc.cpp - Linear-scan implementation -----------===// 2d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth// 3d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth// The Subzero Code Generator 4d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth// 5d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth// This file is distributed under the University of Illinois Open Source 6d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth// License. See LICENSE.TXT for details. 7d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth// 8d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth//===----------------------------------------------------------------------===// 99612d32c7e5eb2cb403686ef31172d42e075e460Andrew Scull/// 109612d32c7e5eb2cb403686ef31172d42e075e460Andrew Scull/// \file 11d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull/// This file implements the LinearScan class, which performs the linear-scan 12d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull/// register allocation after liveness analysis has been performed. 139612d32c7e5eb2cb403686ef31172d42e075e460Andrew Scull/// 14d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth//===----------------------------------------------------------------------===// 15d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 1667f8de9adf6439881a00d8e0f081918436c71f62John Porto#include "IceRegAlloc.h" 1767f8de9adf6439881a00d8e0f081918436c71f62John Porto 18d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth#include "IceCfg.h" 1987ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth#include "IceCfgNode.h" 20d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth#include "IceInst.h" 21ec3f56532be1792d04ed470221df663bb8ca9c19John Porto#include "IceInstVarIter.h" 22d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth#include "IceOperand.h" 23d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth#include "IceTargetLowering.h" 24d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 25d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnothnamespace Ice { 26d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 27ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnothnamespace { 28ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth 29ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth// Returns true if Var has any definitions within Item's live range. 30d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// TODO(stichnot): Consider trimming the Definitions list similar to how the 31d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// live ranges are trimmed, since all the overlapsDefs() tests are whether some 32d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// variable's definitions overlap Cur, and trimming is with respect Cur.start. 33d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// Initial tests show no measurable performance difference, so we'll keep the 34d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// code simple for now. 355ce0abb87e7134493febe99117c7a2e88d75efc4Jim Stichnothbool overlapsDefs(const Cfg *Func, const Variable *Item, const Variable *Var) { 36a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth constexpr bool UseTrimmed = true; 37037fa1d997307fd68c7e6d9c385e30890d65604dJim Stichnoth VariablesMetadata *VMetadata = Func->getVMetadata(); 38877b04e409637216712d3c36fc155b47f8bd8d38Jim Stichnoth if (const Inst *FirstDef = VMetadata->getFirstDefinition(Var)) 39877b04e409637216712d3c36fc155b47f8bd8d38Jim Stichnoth if (Item->getLiveRange().overlapsInst(FirstDef->getNumber(), UseTrimmed)) 40877b04e409637216712d3c36fc155b47f8bd8d38Jim Stichnoth return true; 41877b04e409637216712d3c36fc155b47f8bd8d38Jim Stichnoth const InstDefList &Defs = VMetadata->getLatterDefinitions(Var); 42ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth for (size_t i = 0; i < Defs.size(); ++i) { 435ce0abb87e7134493febe99117c7a2e88d75efc4Jim Stichnoth if (Item->getLiveRange().overlapsInst(Defs[i]->getNumber(), UseTrimmed)) 44ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth return true; 45ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth } 46ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth return false; 47ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth} 48ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth 49ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnothvoid dumpDisableOverlap(const Cfg *Func, const Variable *Var, 50ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth const char *Reason) { 5120b71f5890ee8651983b126c5978594a01e0af96Jim Stichnoth if (!BuildDefs::dump()) 52b6c96af1e5f019374ab93b2b66fbf79247d24660Karl Schimpf return; 53fa4efea5413aa993e8e6ba10579e0934d1a3e784Jim Stichnoth if (Func->isVerbose(IceV_LinearScan)) { 54037fa1d997307fd68c7e6d9c385e30890d65604dJim Stichnoth VariablesMetadata *VMetadata = Func->getVMetadata(); 55ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth Ostream &Str = Func->getContext()->getStrDump(); 56ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth Str << "Disabling Overlap due to " << Reason << " " << *Var 57ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth << " LIVE=" << Var->getLiveRange() << " Defs="; 58877b04e409637216712d3c36fc155b47f8bd8d38Jim Stichnoth if (const Inst *FirstDef = VMetadata->getFirstDefinition(Var)) 59877b04e409637216712d3c36fc155b47f8bd8d38Jim Stichnoth Str << FirstDef->getNumber(); 60877b04e409637216712d3c36fc155b47f8bd8d38Jim Stichnoth const InstDefList &Defs = VMetadata->getLatterDefinitions(Var); 61ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth for (size_t i = 0; i < Defs.size(); ++i) { 62877b04e409637216712d3c36fc155b47f8bd8d38Jim Stichnoth Str << "," << Defs[i]->getNumber(); 63ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth } 64ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth Str << "\n"; 65ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth } 66ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth} 67ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth 685ce0abb87e7134493febe99117c7a2e88d75efc4Jim Stichnothvoid dumpLiveRange(const Variable *Var, const Cfg *Func) { 6920b71f5890ee8651983b126c5978594a01e0af96Jim Stichnoth if (!BuildDefs::dump()) 70b6c96af1e5f019374ab93b2b66fbf79247d24660Karl Schimpf return; 715ce0abb87e7134493febe99117c7a2e88d75efc4Jim Stichnoth Ostream &Str = Func->getContext()->getStrDump(); 72a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth char buf[30]; 73a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth snprintf(buf, llvm::array_lengthof(buf), "%2d", Var->getRegNumTmp()); 745ce0abb87e7134493febe99117c7a2e88d75efc4Jim Stichnoth Str << "R=" << buf << " V="; 755ce0abb87e7134493febe99117c7a2e88d75efc4Jim Stichnoth Var->dump(Func); 765ce0abb87e7134493febe99117c7a2e88d75efc4Jim Stichnoth Str << " Range=" << Var->getLiveRange(); 77e22f823680ec21304509c1ebcee119cb843f5e76Jim Stichnoth} 78e22f823680ec21304509c1ebcee119cb843f5e76Jim Stichnoth 79ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth} // end of anonymous namespace 80ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth 81d24cfda1f63f04f22118addb793b197fd3141b15Andrew ScullLinearScan::LinearScan(Cfg *Func) 82bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto : Func(Func), Ctx(Func->getContext()), Target(Func->getTarget()), 83d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Verbose(BuildDefs::dump() && Func->isVerbose(IceV_LinearScan)) {} 84d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 8557e126899b20c65ff3ea23a3b7d7a67ab30b99dcAndrew Scull// Prepare for full register allocation of all variables. We depend on liveness 8657e126899b20c65ff3ea23a3b7d7a67ab30b99dcAndrew Scull// analysis to have calculated live ranges. 8770d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnothvoid LinearScan::initForGlobal() { 8887ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth TimerMarker T(TimerStack::TT_initUnhandled, Func); 8970d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth FindPreference = true; 90a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // For full register allocation, normally we want to enable FindOverlap 91a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // (meaning we look for opportunities for two overlapping live ranges to 9257e126899b20c65ff3ea23a3b7d7a67ab30b99dcAndrew Scull // safely share the same register). However, we disable it for phi-lowering 93a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // register allocation since no overlap opportunities should be available and 94a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // it's more expensive to look for opportunities. 95a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth FindOverlap = (Kind != RAK_Phi); 9687ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth const VarList &Vars = Func->getVariables(); 9787ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth Unhandled.reserve(Vars.size()); 984ead35a7e6d1d04d8cab5db23299fb5c2fe1943dJim Stichnoth UnhandledPrecolored.reserve(Vars.size()); 99d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Gather the live ranges of all variables and add them to the Unhandled set. 10087ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth for (Variable *Var : Vars) { 101d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Explicitly don't consider zero-weight variables, which are meant to be 102d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // spill slots. 10311c9a325399b282cb4ea7d1d24d42fceeec2a09aAndrew Scull if (Var->mustNotHaveReg()) 10487ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth continue; 105d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Don't bother if the variable has a null live range, which means it was 106d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // never referenced. 10787ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth if (Var->getLiveRange().isEmpty()) 10887ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth continue; 10987ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth Var->untrimLiveRange(); 11087ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth Unhandled.push_back(Var); 11187ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth if (Var->hasReg()) { 11287ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth Var->setRegNumTmp(Var->getRegNum()); 11311c9a325399b282cb4ea7d1d24d42fceeec2a09aAndrew Scull Var->setMustHaveReg(); 11487ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth UnhandledPrecolored.push_back(Var); 11587ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth } 11687ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth } 11770d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth 11870d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth // Build the (ordered) list of FakeKill instruction numbers. 11970d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth Kills.clear(); 120a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // Phi lowering should not be creating new call instructions, so there should 121a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // be no infinite-weight not-yet-colored live ranges that span a call 122a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // instruction, hence no need to construct the Kills list. 123a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth if (Kind == RAK_Phi) 124a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth return; 12570d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth for (CfgNode *Node : Func->getNodes()) { 12629841e84014ccbe7344e00f44ce7695a017de69aJim Stichnoth for (Inst &I : Node->getInsts()) { 12729841e84014ccbe7344e00f44ce7695a017de69aJim Stichnoth if (auto Kill = llvm::dyn_cast<InstFakeKill>(&I)) { 12870d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth if (!Kill->isDeleted() && !Kill->getLinked()->isDeleted()) 12929841e84014ccbe7344e00f44ce7695a017de69aJim Stichnoth Kills.push_back(I.getNumber()); 13070d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth } 13170d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth } 13270d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth } 13370d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth} 13470d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth 13570d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth// Prepare for very simple register allocation of only infinite-weight 136d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// Variables while respecting pre-colored Variables. Some properties we take 137d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// advantage of: 13870d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth// 13970d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth// * Live ranges of interest consist of a single segment. 14070d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth// 14170d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth// * Live ranges of interest never span a call instruction. 14270d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth// 143d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// * Phi instructions are not considered because either phis have already been 144d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// lowered, or they don't contain any pre-colored or infinite-weight 145d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// Variables. 14670d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth// 147d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// * We don't need to renumber instructions before computing live ranges 148d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// because all the high-level ICE instructions are deleted prior to lowering, 149d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// and the low-level instructions are added in monotonically increasing order. 15070d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth// 151d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// * There are no opportunities for register preference or allowing overlap. 15270d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth// 15370d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth// Some properties we aren't (yet) taking advantage of: 15470d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth// 155d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// * Because live ranges are a single segment, the Inactive set will always be 156d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// empty, and the live range trimming operation is unnecessary. 15770d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth// 158d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// * Calculating overlap of single-segment live ranges could be optimized a 159d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// bit. 16070d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnothvoid LinearScan::initForInfOnly() { 16170d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth TimerMarker T(TimerStack::TT_initUnhandled, Func); 16270d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth FindPreference = false; 16370d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth FindOverlap = false; 16470d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth SizeT NumVars = 0; 16570d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth const VarList &Vars = Func->getVariables(); 16670d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth 167d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Iterate across all instructions and record the begin and end of the live 168d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // range for each variable that is pre-colored or infinite weight. 16900741a005cf242d2e9108f7cc7c454246e13741cAndrew Scull CfgVector<InstNumberT> LRBegin(Vars.size(), Inst::NumberSentinel); 17000741a005cf242d2e9108f7cc7c454246e13741cAndrew Scull CfgVector<InstNumberT> LREnd(Vars.size(), Inst::NumberSentinel); 17170d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth for (CfgNode *Node : Func->getNodes()) { 17229841e84014ccbe7344e00f44ce7695a017de69aJim Stichnoth for (Inst &Inst : Node->getInsts()) { 17329841e84014ccbe7344e00f44ce7695a017de69aJim Stichnoth if (Inst.isDeleted()) 17470d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth continue; 17529841e84014ccbe7344e00f44ce7695a017de69aJim Stichnoth if (const Variable *Var = Inst.getDest()) { 176f9df45232d77d5a53cee87a138db42f27798d9eeJim Stichnoth if (!Var->getIgnoreLiveness() && 17711c9a325399b282cb4ea7d1d24d42fceeec2a09aAndrew Scull (Var->hasReg() || Var->mustHaveReg())) { 17870d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth if (LRBegin[Var->getIndex()] == Inst::NumberSentinel) { 17929841e84014ccbe7344e00f44ce7695a017de69aJim Stichnoth LRBegin[Var->getIndex()] = Inst.getNumber(); 18070d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth ++NumVars; 18170d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth } 18270d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth } 18370d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth } 184ec3f56532be1792d04ed470221df663bb8ca9c19John Porto FOREACH_VAR_IN_INST(Var, Inst) { 185ec3f56532be1792d04ed470221df663bb8ca9c19John Porto if (Var->getIgnoreLiveness()) 186ec3f56532be1792d04ed470221df663bb8ca9c19John Porto continue; 187ec3f56532be1792d04ed470221df663bb8ca9c19John Porto if (Var->hasReg() || Var->mustHaveReg()) 188ec3f56532be1792d04ed470221df663bb8ca9c19John Porto LREnd[Var->getIndex()] = Inst.getNumber(); 18970d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth } 19070d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth } 19170d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth } 19270d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth 19370d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth Unhandled.reserve(NumVars); 1944ead35a7e6d1d04d8cab5db23299fb5c2fe1943dJim Stichnoth UnhandledPrecolored.reserve(NumVars); 19570d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth for (SizeT i = 0; i < Vars.size(); ++i) { 19670d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth Variable *Var = Vars[i]; 19770d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth if (LRBegin[i] != Inst::NumberSentinel) { 19870d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth assert(LREnd[i] != Inst::NumberSentinel); 19970d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth Unhandled.push_back(Var); 20070d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth Var->resetLiveRange(); 20111c9a325399b282cb4ea7d1d24d42fceeec2a09aAndrew Scull Var->addLiveRange(LRBegin[i], LREnd[i]); 20270d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth Var->untrimLiveRange(); 20370d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth if (Var->hasReg()) { 20470d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth Var->setRegNumTmp(Var->getRegNum()); 20511c9a325399b282cb4ea7d1d24d42fceeec2a09aAndrew Scull Var->setMustHaveReg(); 20670d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth UnhandledPrecolored.push_back(Var); 20770d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth } 20870d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth --NumVars; 20970d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth } 21070d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth } 211d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // This isn't actually a fatal condition, but it would be nice to know if we 212d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // somehow pre-calculated Unhandled's size wrong. 21370d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth assert(NumVars == 0); 21470d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth 215d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Don't build up the list of Kills because we know that no infinite-weight 216d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Variable has a live range spanning a call. 21770d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth Kills.clear(); 21870d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth} 21970d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth 22070d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnothvoid LinearScan::init(RegAllocKind Kind) { 221a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth this->Kind = Kind; 22270d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth Unhandled.clear(); 22370d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth UnhandledPrecolored.clear(); 22470d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth Handled.clear(); 22570d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth Inactive.clear(); 22670d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth Active.clear(); 22770d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth 228bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto SizeT NumRegs = Target->getNumRegisters(); 229bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto RegAliases.resize(NumRegs); 230bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto for (SizeT Reg = 0; Reg < NumRegs; ++Reg) { 231bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto RegAliases[Reg] = &Target->getAliasesForRegister(Reg); 232bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto } 233bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto 23470d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth switch (Kind) { 235a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth case RAK_Unknown: 236a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth llvm::report_fatal_error("Invalid RAK_Unknown"); 237a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth break; 23870d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth case RAK_Global: 239a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth case RAK_Phi: 24070d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth initForGlobal(); 24170d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth break; 24270d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth case RAK_InfOnly: 24370d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth initForInfOnly(); 24470d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth break; 24570d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth } 24670d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth 247992f91ddfeb7e68bdb51498194c2af7e9017aeb1Jim Stichnoth auto CompareRanges = [](const Variable *L, const Variable *R) { 248aee5fa8dd6aa948160a290c8237d7ae4875811fbQining Lu InstNumberT Lstart = L->getLiveRange().getStart(); 249aee5fa8dd6aa948160a290c8237d7ae4875811fbQining Lu InstNumberT Rstart = R->getLiveRange().getStart(); 250aee5fa8dd6aa948160a290c8237d7ae4875811fbQining Lu if (Lstart == Rstart) 251aee5fa8dd6aa948160a290c8237d7ae4875811fbQining Lu return L->getIndex() < R->getIndex(); 252aee5fa8dd6aa948160a290c8237d7ae4875811fbQining Lu return Lstart < Rstart; 25387ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth }; 25487ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth // Do a reverse sort so that erasing elements (from the end) is fast. 255992f91ddfeb7e68bdb51498194c2af7e9017aeb1Jim Stichnoth std::sort(Unhandled.rbegin(), Unhandled.rend(), CompareRanges); 25687ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth std::sort(UnhandledPrecolored.rbegin(), UnhandledPrecolored.rend(), 257992f91ddfeb7e68bdb51498194c2af7e9017aeb1Jim Stichnoth CompareRanges); 2584ead35a7e6d1d04d8cab5db23299fb5c2fe1943dJim Stichnoth 2594ead35a7e6d1d04d8cab5db23299fb5c2fe1943dJim Stichnoth Handled.reserve(Unhandled.size()); 2604ead35a7e6d1d04d8cab5db23299fb5c2fe1943dJim Stichnoth Inactive.reserve(Unhandled.size()); 2614ead35a7e6d1d04d8cab5db23299fb5c2fe1943dJim Stichnoth Active.reserve(Unhandled.size()); 26287ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth} 26387ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth 264a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth// This is called when Cur must be allocated a register but no registers are 26557e126899b20c65ff3ea23a3b7d7a67ab30b99dcAndrew Scull// available across Cur's live range. To handle this, we find a register that 266a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth// is not explicitly used during Cur's live range, spill that register to a 267a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth// stack location right before Cur's live range begins, and fill (reload) the 268a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth// register from the stack location right after Cur's live range ends. 269d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scullvoid LinearScan::addSpillFill(IterationState &Iter) { 270d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Identify the actual instructions that begin and end Iter.Cur's live range. 271d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Iterate through Iter.Cur's node's instruction list until we find the actual 272d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // instructions with instruction numbers corresponding to Iter.Cur's recorded 273d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // live range endpoints. This sounds inefficient but shouldn't be a problem 274d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // in practice because: 275a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // (1) This function is almost never called in practice. 276a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // (2) Since this register over-subscription problem happens only for 277a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // phi-lowered instructions, the number of instructions in the node is 278a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // proportional to the number of phi instructions in the original node, 279a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // which is never very large in practice. 280d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // (3) We still have to iterate through all instructions of Iter.Cur's live 281d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // range to find all explicitly used registers (though the live range is 282d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // usually only 2-3 instructions), so the main cost that could be avoided 283d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // would be finding the instruction that begin's Iter.Cur's live range. 284d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull assert(!Iter.Cur->getLiveRange().isEmpty()); 285d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull InstNumberT Start = Iter.Cur->getLiveRange().getStart(); 286d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull InstNumberT End = Iter.Cur->getLiveRange().getEnd(); 287d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull CfgNode *Node = Func->getVMetadata()->getLocalUseNode(Iter.Cur); 288a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth assert(Node); 289a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth InstList &Insts = Node->getInsts(); 290a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth InstList::iterator SpillPoint = Insts.end(); 291a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth InstList::iterator FillPoint = Insts.end(); 292a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // Stop searching after we have found both the SpillPoint and the FillPoint. 293a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth for (auto I = Insts.begin(), E = Insts.end(); 294a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth I != E && (SpillPoint == E || FillPoint == E); ++I) { 295a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth if (I->getNumber() == Start) 296a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth SpillPoint = I; 297a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth if (I->getNumber() == End) 298a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth FillPoint = I; 299a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth if (SpillPoint != E) { 30057e126899b20c65ff3ea23a3b7d7a67ab30b99dcAndrew Scull // Remove from RegMask any physical registers referenced during Cur's 30157e126899b20c65ff3ea23a3b7d7a67ab30b99dcAndrew Scull // live range. Start looking after SpillPoint gets set, i.e. once Cur's 30257e126899b20c65ff3ea23a3b7d7a67ab30b99dcAndrew Scull // live range begins. 303ec3f56532be1792d04ed470221df663bb8ca9c19John Porto FOREACH_VAR_IN_INST(Var, *I) { 304bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto if (!Var->hasRegTmp()) 305bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto continue; 306bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto const llvm::SmallBitVector &Aliases = *RegAliases[Var->getRegNumTmp()]; 307bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0; 308bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto RegAlias = Aliases.find_next(RegAlias)) { 309bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto Iter.RegMask[RegAlias] = false; 310bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto } 311a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth } 312a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth } 313a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth } 314a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth assert(SpillPoint != Insts.end()); 315a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth assert(FillPoint != Insts.end()); 316a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth ++FillPoint; 317a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // TODO(stichnot): Randomize instead of find_first(). 318d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull int32_t RegNum = Iter.RegMask.find_first(); 319a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth assert(RegNum != -1); 320d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.Cur->setRegNumTmp(RegNum); 321d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Variable *Preg = Target->getPhysicalRegister(RegNum, Iter.Cur->getType()); 32257e126899b20c65ff3ea23a3b7d7a67ab30b99dcAndrew Scull // TODO(stichnot): Add SpillLoc to VariablesMetadata tracking so that 32357e126899b20c65ff3ea23a3b7d7a67ab30b99dcAndrew Scull // SpillLoc is correctly identified as !isMultiBlock(), reducing stack frame 32457e126899b20c65ff3ea23a3b7d7a67ab30b99dcAndrew Scull // size. 325d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Variable *SpillLoc = Func->makeVariable(Iter.Cur->getType()); 326a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // Add "reg=FakeDef;spill=reg" before SpillPoint 327a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth Target->lowerInst(Node, SpillPoint, InstFakeDef::create(Func, Preg)); 328a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth Target->lowerInst(Node, SpillPoint, InstAssign::create(Func, SpillLoc, Preg)); 329a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // add "reg=spill;FakeUse(reg)" before FillPoint 330a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth Target->lowerInst(Node, FillPoint, InstAssign::create(Func, Preg, SpillLoc)); 331a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth Target->lowerInst(Node, FillPoint, InstFakeUse::create(Func, Preg)); 332a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth} 333a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth 334d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scullvoid LinearScan::handleActiveRangeExpiredOrInactive(const Variable *Cur) { 335d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull for (SizeT I = Active.size(); I > 0; --I) { 336d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull const SizeT Index = I - 1; 337d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Variable *Item = Active[Index]; 338d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Item->trimLiveRange(Cur->getLiveRange().getStart()); 339d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull bool Moved = false; 340d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Item->rangeEndsBefore(Cur)) { 341d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Move Item from Active to Handled list. 342696605575c4ba11df5ec56149c561839d1bfe532Jim Stichnoth dumpLiveRangeTrace("Expiring ", Item); 343d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull moveItem(Active, Index, Handled); 344d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Moved = true; 345d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } else if (!Item->rangeOverlapsStart(Cur)) { 346d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Move Item from Active to Inactive list. 347696605575c4ba11df5ec56149c561839d1bfe532Jim Stichnoth dumpLiveRangeTrace("Inactivating ", Item); 348d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull moveItem(Active, Index, Inactive); 349d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Moved = true; 350d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 351d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Moved) { 352d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Decrement Item from RegUses[]. 353d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull assert(Item->hasRegTmp()); 354bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()]; 355bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0; 356bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto RegAlias = Aliases.find_next(RegAlias)) { 357bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto --RegUses[RegAlias]; 358bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto assert(RegUses[RegAlias] >= 0); 359bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto } 360d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 361d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 362d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull} 363d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 364d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scullvoid LinearScan::handleInactiveRangeExpiredOrReactivated(const Variable *Cur) { 365d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull for (SizeT I = Inactive.size(); I > 0; --I) { 366d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull const SizeT Index = I - 1; 367d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Variable *Item = Inactive[Index]; 368d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Item->trimLiveRange(Cur->getLiveRange().getStart()); 369d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Item->rangeEndsBefore(Cur)) { 370d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Move Item from Inactive to Handled list. 371696605575c4ba11df5ec56149c561839d1bfe532Jim Stichnoth dumpLiveRangeTrace("Expiring ", Item); 372d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull moveItem(Inactive, Index, Handled); 373d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } else if (Item->rangeOverlapsStart(Cur)) { 374d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Move Item from Inactive to Active list. 375696605575c4ba11df5ec56149c561839d1bfe532Jim Stichnoth dumpLiveRangeTrace("Reactivating ", Item); 376d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull moveItem(Inactive, Index, Active); 377d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Increment Item in RegUses[]. 378d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull assert(Item->hasRegTmp()); 379bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()]; 380bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0; 381bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto RegAlias = Aliases.find_next(RegAlias)) { 382bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto assert(RegUses[RegAlias] >= 0); 383bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto ++RegUses[RegAlias]; 384bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto } 385d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 386d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 387d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull} 388d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 389d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// Infer register preference and allowable overlap. Only form a preference when 390d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// the current Variable has an unambiguous "first" definition. The preference 391d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// is some source Variable of the defining instruction that either is assigned 392d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// a register that is currently free, or that is assigned a register that is 393d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// not free but overlap is allowed. Overlap is allowed when the Variable under 394d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// consideration is single-definition, and its definition is a simple 395d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// assignment - i.e., the register gets copied/aliased but is never modified. 396d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// Furthermore, overlap is only allowed when preferred Variable definition 397d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// instructions do not appear within the current Variable's live range. 398d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scullvoid LinearScan::findRegisterPreference(IterationState &Iter) { 399d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.Prefer = nullptr; 400d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.PreferReg = Variable::NoRegister; 401d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.AllowOverlap = false; 402d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 403d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (FindPreference) { 404d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull VariablesMetadata *VMetadata = Func->getVMetadata(); 405d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (const Inst *DefInst = VMetadata->getFirstDefinition(Iter.Cur)) { 406d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull assert(DefInst->getDest() == Iter.Cur); 407d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull bool IsAssign = DefInst->isSimpleAssign(); 408d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull bool IsSingleDef = !VMetadata->isMultiDef(Iter.Cur); 409d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull for (SizeT i = 0; i < DefInst->getSrcSize(); ++i) { 410d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // TODO(stichnot): Iterate through the actual Variables of the 411d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // instruction, not just the source operands. This could capture Load 412d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // instructions, including address mode optimization, for Prefer (but 413d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // not for AllowOverlap). 414d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Variable *SrcVar = llvm::dyn_cast<Variable>(DefInst->getSrc(i))) { 415d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull int32_t SrcReg = SrcVar->getRegNumTmp(); 416d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Only consider source variables that have (so far) been assigned a 41757e126899b20c65ff3ea23a3b7d7a67ab30b99dcAndrew Scull // register. That register must be one in the RegMask set, e.g. don't 41857e126899b20c65ff3ea23a3b7d7a67ab30b99dcAndrew Scull // try to prefer the stack pointer as a result of the stacksave 419d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // intrinsic. 420d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (SrcVar->hasRegTmp() && Iter.RegMask[SrcReg]) { 421d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (FindOverlap && !Iter.Free[SrcReg]) { 422d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Don't bother trying to enable AllowOverlap if the register is 423d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // already free. 424d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.AllowOverlap = IsSingleDef && IsAssign && 425d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull !overlapsDefs(Func, Iter.Cur, SrcVar); 426d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 427d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Iter.AllowOverlap || Iter.Free[SrcReg]) { 428d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.Prefer = SrcVar; 429d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.PreferReg = SrcReg; 430d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 431d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 432d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 433d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 434d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Verbose && Iter.Prefer) { 435d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Ostream &Str = Ctx->getStrDump(); 436d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Str << "Initial Iter.Prefer="; 437d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.Prefer->dump(Func); 438d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Str << " R=" << Iter.PreferReg 439d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull << " LIVE=" << Iter.Prefer->getLiveRange() 440d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull << " Overlap=" << Iter.AllowOverlap << "\n"; 441d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 442d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 443d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 444d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull} 445d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 446d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// Remove registers from the Free[] list where an Inactive range overlaps with 447d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// the current range. 448d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scullvoid LinearScan::filterFreeWithInactiveRanges(IterationState &Iter) { 449d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull for (const Variable *Item : Inactive) { 450bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto if (!Item->rangeOverlaps(Iter.Cur)) 451bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto continue; 452bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()]; 453bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0; 454bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto RegAlias = Aliases.find_next(RegAlias)) { 455d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Don't assert(Free[RegNum]) because in theory (though probably never in 456d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // practice) there could be two inactive variables that were marked with 457d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // AllowOverlap. 458bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto Iter.Free[RegAlias] = false; 459d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Disable AllowOverlap if an Inactive variable, which is not Prefer, 460d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // shares Prefer's register, and has a definition within Cur's live 461d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // range. 462d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Iter.AllowOverlap && Item != Iter.Prefer && 463bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto RegAlias == Iter.PreferReg && overlapsDefs(Func, Iter.Cur, Item)) { 464d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.AllowOverlap = false; 465d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull dumpDisableOverlap(Func, Item, "Inactive"); 466d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 467d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 468d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 469d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull} 470d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 471d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// Remove registers from the Free[] list where an Unhandled pre-colored range 472d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// overlaps with the current range, and set those registers to infinite weight 47357e126899b20c65ff3ea23a3b7d7a67ab30b99dcAndrew Scull// so that they aren't candidates for eviction. Cur->rangeEndsBefore(Item) is 474d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// an early exit check that turns a guaranteed O(N^2) algorithm into expected 475d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// linear complexity. 476d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scullvoid LinearScan::filterFreeWithPrecoloredRanges(IterationState &Iter) { 477d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull for (Variable *Item : reverse_range(UnhandledPrecolored)) { 478d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull assert(Item->hasReg()); 479d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Iter.Cur->rangeEndsBefore(Item)) 480d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull break; 481d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Item->rangeOverlaps(Iter.Cur)) { 482bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto const llvm::SmallBitVector &Aliases = 483bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto *RegAliases[Item->getRegNum()]; // Note: not getRegNumTmp() 484bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0; 485bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto RegAlias = Aliases.find_next(RegAlias)) { 486bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto Iter.Weights[RegAlias].setWeight(RegWeight::Inf); 487bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto Iter.Free[RegAlias] = false; 488bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto Iter.PrecoloredUnhandledMask[RegAlias] = true; 489bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto // Disable Iter.AllowOverlap if the preferred register is one of these 490bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto // pre-colored unhandled overlapping ranges. 491bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto if (Iter.AllowOverlap && RegAlias == Iter.PreferReg) { 492bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto Iter.AllowOverlap = false; 493bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto dumpDisableOverlap(Func, Item, "PrecoloredUnhandled"); 494bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto } 495d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 496d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 497d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 498d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull} 499d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 500d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scullvoid LinearScan::allocatePrecoloredRegister(Variable *Cur) { 501d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull int32_t RegNum = Cur->getRegNum(); 502d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // RegNumTmp should have already been set above. 503d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull assert(Cur->getRegNumTmp() == RegNum); 504d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull dumpLiveRangeTrace("Precoloring ", Cur); 505d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Active.push_back(Cur); 506bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto const llvm::SmallBitVector &Aliases = *RegAliases[RegNum]; 507bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0; 508bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto RegAlias = Aliases.find_next(RegAlias)) { 509bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto assert(RegUses[RegAlias] >= 0); 510bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto ++RegUses[RegAlias]; 511bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto } 512d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull assert(!UnhandledPrecolored.empty()); 513d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull assert(UnhandledPrecolored.back() == Cur); 514d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull UnhandledPrecolored.pop_back(); 515d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull} 516d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 517d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scullvoid LinearScan::allocatePreferredRegister(IterationState &Iter) { 518d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.Cur->setRegNumTmp(Iter.PreferReg); 519d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull dumpLiveRangeTrace("Preferring ", Iter.Cur); 520bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto const llvm::SmallBitVector &Aliases = *RegAliases[Iter.PreferReg]; 521bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0; 522bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto RegAlias = Aliases.find_next(RegAlias)) { 523bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto assert(RegUses[RegAlias] >= 0); 524bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto ++RegUses[RegAlias]; 525bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto } 526d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Active.push_back(Iter.Cur); 527d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull} 528d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 529d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scullvoid LinearScan::allocateFreeRegister(IterationState &Iter) { 530d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull int32_t RegNum = Iter.Free.find_first(); 531d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.Cur->setRegNumTmp(RegNum); 532d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull dumpLiveRangeTrace("Allocating ", Iter.Cur); 533bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto const llvm::SmallBitVector &Aliases = *RegAliases[RegNum]; 534bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0; 535bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto RegAlias = Aliases.find_next(RegAlias)) { 536bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto assert(RegUses[RegAlias] >= 0); 537bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto ++RegUses[RegAlias]; 538bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto } 539d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Active.push_back(Iter.Cur); 540d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull} 541d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 542d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scullvoid LinearScan::handleNoFreeRegisters(IterationState &Iter) { 543d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Check Active ranges. 544d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull for (const Variable *Item : Active) { 545d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull assert(Item->rangeOverlaps(Iter.Cur)); 546d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull assert(Item->hasRegTmp()); 547bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()]; 548bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto // We add the Item's weight to each alias/subregister to represent that, 549bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto // should we decide to pick any of them, then we would incur that many 550bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto // memory accesses. 551bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto RegWeight W = Item->getWeight(Func); 552bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0; 553bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto RegAlias = Aliases.find_next(RegAlias)) { 554bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto Iter.Weights[RegAlias].addWeight(W); 555bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto } 556d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 557d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Same as above, but check Inactive ranges instead of Active. 558d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull for (const Variable *Item : Inactive) { 559bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto if (!Item->rangeOverlaps(Iter.Cur)) 560bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto continue; 561d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull assert(Item->hasRegTmp()); 562bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto const llvm::SmallBitVector &Aliases = *RegAliases[Item->getRegNumTmp()]; 563bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto RegWeight W = Item->getWeight(Func); 564bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0; 565bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto RegAlias = Aliases.find_next(RegAlias)) { 566bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto Iter.Weights[RegAlias].addWeight(W); 567bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto } 568d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 569d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 570d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // All the weights are now calculated. Find the register with smallest 571d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // weight. 572d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull int32_t MinWeightIndex = Iter.RegMask.find_first(); 573d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // MinWeightIndex must be valid because of the initial RegMask.any() test. 574d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull assert(MinWeightIndex >= 0); 575d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull for (SizeT i = MinWeightIndex + 1; i < Iter.Weights.size(); ++i) { 576d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Iter.RegMask[i] && Iter.Weights[i] < Iter.Weights[MinWeightIndex]) 577d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull MinWeightIndex = i; 578d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 579d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 58011c9a325399b282cb4ea7d1d24d42fceeec2a09aAndrew Scull if (Iter.Cur->getWeight(Func) <= Iter.Weights[MinWeightIndex]) { 581d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Cur doesn't have priority over any other live ranges, so don't allocate 582d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // any register to it, and move it to the Handled state. 583d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Handled.push_back(Iter.Cur); 58411c9a325399b282cb4ea7d1d24d42fceeec2a09aAndrew Scull if (Iter.Cur->mustHaveReg()) { 585d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Kind == RAK_Phi) 586d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull addSpillFill(Iter); 587d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull else 588d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Func->setError("Unable to find a physical register for an " 589d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull "infinite-weight live range"); 590d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 591d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } else { 592d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Evict all live ranges in Active that register number MinWeightIndex is 593d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // assigned to. 594d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull for (SizeT I = Active.size(); I > 0; --I) { 595d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull const SizeT Index = I - 1; 596d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Variable *Item = Active[Index]; 597d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Item->getRegNumTmp() == MinWeightIndex) { 598d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull dumpLiveRangeTrace("Evicting ", Item); 599bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto const llvm::SmallBitVector &Aliases = *RegAliases[MinWeightIndex]; 600bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0; 601bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto RegAlias = Aliases.find_next(RegAlias)) { 602bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto --RegUses[RegAlias]; 603bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto assert(RegUses[RegAlias] >= 0); 604bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto } 605d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Item->setRegNumTmp(Variable::NoRegister); 606d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull moveItem(Active, Index, Handled); 607d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 608d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 609d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Do the same for Inactive. 610d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull for (SizeT I = Inactive.size(); I > 0; --I) { 611d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull const SizeT Index = I - 1; 612d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Variable *Item = Inactive[Index]; 613d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Note: The Item->rangeOverlaps(Cur) clause is not part of the 61457e126899b20c65ff3ea23a3b7d7a67ab30b99dcAndrew Scull // description of AssignMemLoc() in the original paper. But there doesn't 61557e126899b20c65ff3ea23a3b7d7a67ab30b99dcAndrew Scull // seem to be any need to evict an inactive live range that doesn't 61657e126899b20c65ff3ea23a3b7d7a67ab30b99dcAndrew Scull // overlap with the live range currently being considered. It's 617d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // especially bad if we would end up evicting an infinite-weight but 618d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // currently-inactive live range. The most common situation for this 619d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // would be a scratch register kill set for call instructions. 620d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Item->getRegNumTmp() == MinWeightIndex && 621d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Item->rangeOverlaps(Iter.Cur)) { 622d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull dumpLiveRangeTrace("Evicting ", Item); 623d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Item->setRegNumTmp(Variable::NoRegister); 624d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull moveItem(Inactive, Index, Handled); 625d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 626d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 627d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Assign the register to Cur. 628d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.Cur->setRegNumTmp(MinWeightIndex); 629bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto const llvm::SmallBitVector &Aliases = *RegAliases[MinWeightIndex]; 630bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto for (int32_t RegAlias = Aliases.find_first(); RegAlias >= 0; 631bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto RegAlias = Aliases.find_next(RegAlias)) { 632bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto assert(RegUses[RegAlias] >= 0); 633bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto ++RegUses[RegAlias]; 634bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto } 635d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Active.push_back(Iter.Cur); 636d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull dumpLiveRangeTrace("Allocating ", Iter.Cur); 637d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 638d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull} 639d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 640d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scullvoid LinearScan::assignFinalRegisters( 641d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull const llvm::SmallBitVector &RegMaskFull, 642d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull const llvm::SmallBitVector &PreDefinedRegisters, bool Randomized) { 643d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull const size_t NumRegisters = RegMaskFull.size(); 644d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull llvm::SmallVector<int32_t, REGS_SIZE> Permutation(NumRegisters); 645d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Randomized) { 646d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Create a random number generator for regalloc randomization. Merge 647d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // function's sequence and Kind value as the Salt. Because regAlloc() is 64857e126899b20c65ff3ea23a3b7d7a67ab30b99dcAndrew Scull // called twice under O2, the second time with RAK_Phi, we check Kind == 64957e126899b20c65ff3ea23a3b7d7a67ab30b99dcAndrew Scull // RAK_Phi to determine the lowest-order bit to make sure the Salt is 65057e126899b20c65ff3ea23a3b7d7a67ab30b99dcAndrew Scull // different. 651d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull uint64_t Salt = 652d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull (Func->getSequenceNumber() << 1) ^ (Kind == RAK_Phi ? 0u : 1u); 653bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto Target->makeRandomRegisterPermutation( 654d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Permutation, PreDefinedRegisters | ~RegMaskFull, Salt); 655d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 656d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 657d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Finish up by setting RegNum = RegNumTmp (or a random permutation thereof) 658d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // for each Variable. 659d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull for (Variable *Item : Handled) { 660d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull int32_t RegNum = Item->getRegNumTmp(); 661d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull int32_t AssignedRegNum = RegNum; 662d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 663d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Randomized && Item->hasRegTmp() && !Item->hasReg()) { 664d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull AssignedRegNum = Permutation[RegNum]; 665d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 666d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Verbose) { 667d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Ostream &Str = Ctx->getStrDump(); 668d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (!Item->hasRegTmp()) { 669d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Str << "Not assigning "; 670d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Item->dump(Func); 671d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Str << "\n"; 672d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } else { 673d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Str << (AssignedRegNum == Item->getRegNum() ? "Reassigning " 674d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull : "Assigning ") 675bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto << Target->getRegName(AssignedRegNum, IceType_i32) << "(r" 676bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto << AssignedRegNum << ") to "; 677d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Item->dump(Func); 678d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Str << "\n"; 679d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 680d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 681d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Item->setRegNum(AssignedRegNum); 682d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 683d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull} 684d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 685d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// Implements the linear-scan algorithm. Based on "Linear Scan Register 686d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// Allocation in the Context of SSA Form and Register Constraints" by Hanspeter 687d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// Mössenböck and Michael Pfeiffer, 688d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// ftp://ftp.ssw.uni-linz.ac.at/pub/Papers/Moe02.PDF. This implementation is 689d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// modified to take affinity into account and allow two interfering variables 690d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// to share the same register in certain cases. 691d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth// 692d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// Requires running Cfg::liveness(Liveness_Intervals) in preparation. Results 693d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// are assigned to Variable::RegNum for each Variable. 694e6d24789bc5cc2ccadb5582ff51e5b4a5d4e2ac8Jim Stichnothvoid LinearScan::scan(const llvm::SmallBitVector &RegMaskFull, 695e6d24789bc5cc2ccadb5582ff51e5b4a5d4e2ac8Jim Stichnoth bool Randomized) { 6968363a0668ce21ea0c2a61f78083b0536dbd89860Jim Stichnoth TimerMarker T(TimerStack::TT_linearScan, Func); 697d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth assert(RegMaskFull.any()); // Sanity check 698e4a8f400267b3c3b9f0cb7c4b00f8512f9fbe0a1Jim Stichnoth if (Verbose) 699e4a8f400267b3c3b9f0cb7c4b00f8512f9fbe0a1Jim Stichnoth Ctx->lockStr(); 700800dab29d19d6cc9e842fc16bfb9433018322062Jim Stichnoth Func->resetCurrentNode(); 701e6d24789bc5cc2ccadb5582ff51e5b4a5d4e2ac8Jim Stichnoth const size_t NumRegisters = RegMaskFull.size(); 702e6d24789bc5cc2ccadb5582ff51e5b4a5d4e2ac8Jim Stichnoth llvm::SmallBitVector PreDefinedRegisters(NumRegisters); 703e6d24789bc5cc2ccadb5582ff51e5b4a5d4e2ac8Jim Stichnoth if (Randomized) { 704e6d24789bc5cc2ccadb5582ff51e5b4a5d4e2ac8Jim Stichnoth for (Variable *Var : UnhandledPrecolored) { 705e6d24789bc5cc2ccadb5582ff51e5b4a5d4e2ac8Jim Stichnoth PreDefinedRegisters[Var->getRegNum()] = true; 706e6d24789bc5cc2ccadb5582ff51e5b4a5d4e2ac8Jim Stichnoth } 707e6d24789bc5cc2ccadb5582ff51e5b4a5d4e2ac8Jim Stichnoth } 708d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 70987ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth // Build a LiveRange representing the Kills list. 7102a7fcbb4aa216dc4db4216a5275a3471da25f7c5Jim Stichnoth LiveRange KillsRange(Kills); 71187ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth KillsRange.untrim(); 712d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 713d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Reset the register use count 714d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull RegUses.resize(NumRegisters); 715d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull std::fill(RegUses.begin(), RegUses.end(), 0); 716d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 717d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Unhandled is already set to all ranges in increasing order of start 718d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // points. 719d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth assert(Active.empty()); 720d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth assert(Inactive.empty()); 721d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth assert(Handled.empty()); 72287ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth const TargetLowering::RegSetMask RegsInclude = 72387ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth TargetLowering::RegSet_CallerSave; 72487ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth const TargetLowering::RegSetMask RegsExclude = TargetLowering::RegSet_None; 72587ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth const llvm::SmallBitVector KillsMask = 726bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto Target->getRegisterSet(RegsInclude, RegsExclude); 727d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 728d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Allocate memory once outside the loop 729d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull IterationState Iter; 730d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.Weights.reserve(NumRegisters); 731d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.PrecoloredUnhandledMask.reserve(NumRegisters); 732d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 733d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth while (!Unhandled.empty()) { 734d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.Cur = Unhandled.back(); 735e22f823680ec21304509c1ebcee119cb843f5e76Jim Stichnoth Unhandled.pop_back(); 736d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull dumpLiveRangeTrace("\nConsidering ", Iter.Cur); 737d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.RegMask = 738bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto RegMaskFull & Target->getRegisterSetForType(Iter.Cur->getType()); 739d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull KillsRange.trim(Iter.Cur->getLiveRange().getStart()); 740d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 741d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Check for pre-colored ranges. If Cur is pre-colored, it definitely gets 742d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // that register. Previously processed live ranges would have avoided that 743d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // register due to it being pre-colored. Future processed live ranges won't 744d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // evict that register because the live range has infinite weight. 745d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Iter.Cur->hasReg()) { 746d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull allocatePrecoloredRegister(Iter.Cur); 747d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth continue; 748d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth } 749d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 750d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull handleActiveRangeExpiredOrInactive(Iter.Cur); 751d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull handleInactiveRangeExpiredOrReactivated(Iter.Cur); 752d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 753d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth // Calculate available registers into Free[]. 754d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.Free = Iter.RegMask; 755d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull for (SizeT i = 0; i < Iter.RegMask.size(); ++i) { 756d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth if (RegUses[i] > 0) 757d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.Free[i] = false; 758ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth } 759ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth 760d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull findRegisterPreference(Iter); 761d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull filterFreeWithInactiveRanges(Iter); 762ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth 763d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Disable AllowOverlap if an Active variable, which is not Prefer, shares 764d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Prefer's register, and has a definition within Cur's live range. 765d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Iter.AllowOverlap) { 76670d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth for (const Variable *Item : Active) { 76770d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth int32_t RegNum = Item->getRegNumTmp(); 768d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Item != Iter.Prefer && RegNum == Iter.PreferReg && 769d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull overlapsDefs(Func, Iter.Cur, Item)) { 770d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.AllowOverlap = false; 77170d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth dumpDisableOverlap(Func, Item, "Active"); 77270d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth } 773d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth } 774d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth } 775d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 776d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.Weights.resize(Iter.RegMask.size()); 777d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull std::fill(Iter.Weights.begin(), Iter.Weights.end(), RegWeight()); 778d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 779d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.PrecoloredUnhandledMask.resize(Iter.RegMask.size()); 780d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.PrecoloredUnhandledMask.reset(); 781d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 782d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull filterFreeWithPrecoloredRanges(Iter); 783d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 784d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Remove scratch registers from the Free[] list, and mark their Weights[] 785d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // as infinite, if KillsRange overlaps Cur's live range. 786a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth constexpr bool UseTrimmed = true; 787d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Iter.Cur->getLiveRange().overlaps(KillsRange, UseTrimmed)) { 788d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.Free.reset(KillsMask); 78987ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth for (int i = KillsMask.find_first(); i != -1; 79087ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth i = KillsMask.find_next(i)) { 791d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.Weights[i].setWeight(RegWeight::Inf); 792d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Iter.PreferReg == i) 793d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.AllowOverlap = false; 79487ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth } 79587ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth } 79687ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth 797d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth // Print info about physical register availability. 798c4554d784583d26a02eca8610b43511ade516082Jim Stichnoth if (Verbose) { 799e4a8f400267b3c3b9f0cb7c4b00f8512f9fbe0a1Jim Stichnoth Ostream &Str = Ctx->getStrDump(); 800d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull for (SizeT i = 0; i < Iter.RegMask.size(); ++i) { 801d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Iter.RegMask[i]) { 802bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto Str << Target->getRegName(i, IceType_i32) << "(U=" << RegUses[i] 803bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto << ",F=" << Iter.Free[i] 804d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull << ",P=" << Iter.PrecoloredUnhandledMask[i] << ") "; 805d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth } 806d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth } 807d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth Str << "\n"; 808d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth } 809d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 810d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Iter.Prefer && (Iter.AllowOverlap || Iter.Free[Iter.PreferReg])) { 811d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // First choice: a preferred register that is either free or is allowed 812d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // to overlap with its linked variable. 813d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull allocatePreferredRegister(Iter); 814d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } else if (Iter.Free.any()) { 815d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Second choice: any free register. 816d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull allocateFreeRegister(Iter); 817d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth } else { 818d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth // Fallback: there are no free registers, so we look for the 819d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth // lowest-weight register and see if Cur has higher weight. 820d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull handleNoFreeRegisters(Iter); 821d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth } 822d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth dump(Func); 823d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth } 824d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 825d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth // Move anything Active or Inactive to Handled for easier handling. 826d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Handled.insert(Handled.end(), Active.begin(), Active.end()); 827f44f371b7f3fab5683e6781873d71987e44fea2fJim Stichnoth Active.clear(); 828d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Handled.insert(Handled.end(), Inactive.begin(), Inactive.end()); 829f44f371b7f3fab5683e6781873d71987e44fea2fJim Stichnoth Inactive.clear(); 830d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth dump(Func); 831d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 832d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull assignFinalRegisters(RegMaskFull, PreDefinedRegisters, Randomized); 833d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 834d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // TODO: Consider running register allocation one more time, with infinite 835d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // registers, for two reasons. First, evicted live ranges get a second chance 836d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // for a register. Second, it allows coalescing of stack slots. If there is 837d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // no time budget for the second register allocation run, each unallocated 838d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // variable just gets its own slot. 839d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth // 840d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Another idea for coalescing stack slots is to initialize the Unhandled 841d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // list with just the unallocated variables, saving time but not offering 842d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // second-chance opportunities. 843e4a8f400267b3c3b9f0cb7c4b00f8512f9fbe0a1Jim Stichnoth 844e4a8f400267b3c3b9f0cb7c4b00f8512f9fbe0a1Jim Stichnoth if (Verbose) 845e4a8f400267b3c3b9f0cb7c4b00f8512f9fbe0a1Jim Stichnoth Ctx->unlockStr(); 846d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth} 847d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 848d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth// ======================== Dump routines ======================== // 849d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 850d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scullvoid LinearScan::dumpLiveRangeTrace(const char *Label, const Variable *Item) { 851d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (!BuildDefs::dump()) 852d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull return; 853d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 854d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Verbose) { 855d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Ostream &Str = Ctx->getStrDump(); 856d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Str << Label; 857d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull dumpLiveRange(Item, Func); 858d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Str << "\n"; 859d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 860d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull} 861d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 862d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnothvoid LinearScan::dump(Cfg *Func) const { 86320b71f5890ee8651983b126c5978594a01e0af96Jim Stichnoth if (!BuildDefs::dump()) 864b6c96af1e5f019374ab93b2b66fbf79247d24660Karl Schimpf return; 865fa4efea5413aa993e8e6ba10579e0934d1a3e784Jim Stichnoth if (!Func->isVerbose(IceV_LinearScan)) 866d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth return; 867e4a8f400267b3c3b9f0cb7c4b00f8512f9fbe0a1Jim Stichnoth Ostream &Str = Func->getContext()->getStrDump(); 868800dab29d19d6cc9e842fc16bfb9433018322062Jim Stichnoth Func->resetCurrentNode(); 869d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth Str << "**** Current regalloc state:\n"; 870d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth Str << "++++++ Handled:\n"; 8715ce0abb87e7134493febe99117c7a2e88d75efc4Jim Stichnoth for (const Variable *Item : Handled) { 8725ce0abb87e7134493febe99117c7a2e88d75efc4Jim Stichnoth dumpLiveRange(Item, Func); 873d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth Str << "\n"; 874d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth } 875d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth Str << "++++++ Unhandled:\n"; 8767e571364bcc48d361b71c1402611873fb8544117Jim Stichnoth for (const Variable *Item : reverse_range(Unhandled)) { 8777e571364bcc48d361b71c1402611873fb8544117Jim Stichnoth dumpLiveRange(Item, Func); 878d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth Str << "\n"; 879d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth } 880d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth Str << "++++++ Active:\n"; 8815ce0abb87e7134493febe99117c7a2e88d75efc4Jim Stichnoth for (const Variable *Item : Active) { 8825ce0abb87e7134493febe99117c7a2e88d75efc4Jim Stichnoth dumpLiveRange(Item, Func); 883d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth Str << "\n"; 884d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth } 885d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth Str << "++++++ Inactive:\n"; 8865ce0abb87e7134493febe99117c7a2e88d75efc4Jim Stichnoth for (const Variable *Item : Inactive) { 8875ce0abb87e7134493febe99117c7a2e88d75efc4Jim Stichnoth dumpLiveRange(Item, Func); 888d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth Str << "\n"; 889d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth } 890d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth} 891d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 892d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth} // end of namespace Ice 893