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 1192a6e5b08ec68e7076d637ebc680da2fcc346a00Jim Stichnoth/// \brief 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 18e82b560e649f8a68bcb252b9b002708e74d962d3John Porto#include "IceBitVector.h" 19d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth#include "IceCfg.h" 2087ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth#include "IceCfgNode.h" 21d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth#include "IceInst.h" 22ec3f56532be1792d04ed470221df663bb8ca9c19John Porto#include "IceInstVarIter.h" 23d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth#include "IceOperand.h" 24d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth#include "IceTargetLowering.h" 25d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 2611756b510456b215628124e7c13750f60b745f86Jim Stichnoth#include "llvm/Support/Format.h" 2711756b510456b215628124e7c13750f60b745f86Jim Stichnoth 28d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnothnamespace Ice { 29d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 30ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnothnamespace { 31ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth 32ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth// Returns true if Var has any definitions within Item's live range. 33d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// TODO(stichnot): Consider trimming the Definitions list similar to how the 34d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// live ranges are trimmed, since all the overlapsDefs() tests are whether some 35d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// variable's definitions overlap Cur, and trimming is with respect Cur.start. 36d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// Initial tests show no measurable performance difference, so we'll keep the 37d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// code simple for now. 385ce0abb87e7134493febe99117c7a2e88d75efc4Jim Stichnothbool overlapsDefs(const Cfg *Func, const Variable *Item, const Variable *Var) { 39a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth constexpr bool UseTrimmed = true; 40037fa1d997307fd68c7e6d9c385e30890d65604dJim Stichnoth VariablesMetadata *VMetadata = Func->getVMetadata(); 41877b04e409637216712d3c36fc155b47f8bd8d38Jim Stichnoth if (const Inst *FirstDef = VMetadata->getFirstDefinition(Var)) 42877b04e409637216712d3c36fc155b47f8bd8d38Jim Stichnoth if (Item->getLiveRange().overlapsInst(FirstDef->getNumber(), UseTrimmed)) 43877b04e409637216712d3c36fc155b47f8bd8d38Jim Stichnoth return true; 4448e3ae5c62d7e626ed1a0dbbe38a7cc11a356260Jim Stichnoth for (const Inst *Def : VMetadata->getLatterDefinitions(Var)) { 4548e3ae5c62d7e626ed1a0dbbe38a7cc11a356260Jim Stichnoth if (Item->getLiveRange().overlapsInst(Def->getNumber(), UseTrimmed)) 46ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth return true; 47ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth } 48ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth return false; 49ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth} 50ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth 51ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnothvoid dumpDisableOverlap(const Cfg *Func, const Variable *Var, 52ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth const char *Reason) { 5320b71f5890ee8651983b126c5978594a01e0af96Jim Stichnoth if (!BuildDefs::dump()) 54b6c96af1e5f019374ab93b2b66fbf79247d24660Karl Schimpf return; 55a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth if (!Func->isVerbose(IceV_LinearScan)) 56a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth return; 57a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth 58a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth VariablesMetadata *VMetadata = Func->getVMetadata(); 59a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth Ostream &Str = Func->getContext()->getStrDump(); 60a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth Str << "Disabling Overlap due to " << Reason << " " << *Var 61a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth << " LIVE=" << Var->getLiveRange() << " Defs="; 62a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth if (const Inst *FirstDef = VMetadata->getFirstDefinition(Var)) 63a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth Str << FirstDef->getNumber(); 64a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth const InstDefList &Defs = VMetadata->getLatterDefinitions(Var); 65a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth for (size_t i = 0; i < Defs.size(); ++i) { 66a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth Str << "," << Defs[i]->getNumber(); 67ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth } 68a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth Str << "\n"; 69ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth} 70ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth 715ce0abb87e7134493febe99117c7a2e88d75efc4Jim Stichnothvoid dumpLiveRange(const Variable *Var, const Cfg *Func) { 7220b71f5890ee8651983b126c5978594a01e0af96Jim Stichnoth if (!BuildDefs::dump()) 73b6c96af1e5f019374ab93b2b66fbf79247d24660Karl Schimpf return; 745ce0abb87e7134493febe99117c7a2e88d75efc4Jim Stichnoth Ostream &Str = Func->getContext()->getStrDump(); 7511756b510456b215628124e7c13750f60b745f86Jim Stichnoth Str << "R="; 7611756b510456b215628124e7c13750f60b745f86Jim Stichnoth if (Var->hasRegTmp()) { 7779810753afd2c8e7b0d04359481fa2ae4dac4bf2Jim Stichnoth Str << llvm::format("%2d", int(Var->getRegNumTmp())); 7811756b510456b215628124e7c13750f60b745f86Jim Stichnoth } else { 7911756b510456b215628124e7c13750f60b745f86Jim Stichnoth Str << "NA"; 8011756b510456b215628124e7c13750f60b745f86Jim Stichnoth } 8111756b510456b215628124e7c13750f60b745f86Jim Stichnoth Str << " V="; 825ce0abb87e7134493febe99117c7a2e88d75efc4Jim Stichnoth Var->dump(Func); 835ce0abb87e7134493febe99117c7a2e88d75efc4Jim Stichnoth Str << " Range=" << Var->getLiveRange(); 84e22f823680ec21304509c1ebcee119cb843f5e76Jim Stichnoth} 85e22f823680ec21304509c1ebcee119cb843f5e76Jim Stichnoth 86b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnothint32_t findMinWeightIndex( 87e82b560e649f8a68bcb252b9b002708e74d962d3John Porto const SmallBitVector &RegMask, 88b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth const llvm::SmallVector<RegWeight, LinearScan::REGS_SIZE> &Weights) { 898aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth int MinWeightIndex = -1; 908aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth for (RegNumT i : RegNumBVIter(RegMask)) { 918aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth if (MinWeightIndex < 0 || Weights[i] < Weights[MinWeightIndex]) 92b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth MinWeightIndex = i; 93b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth } 942655d9627f11b0c97f10eacf1f730bf66e5db05bJim Stichnoth assert(getFlags().getRegAllocReserve() || MinWeightIndex >= 0); 95b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth return MinWeightIndex; 96b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth} 97b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth 98ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth} // end of anonymous namespace 99ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth 100d24cfda1f63f04f22118addb793b197fd3141b15Andrew ScullLinearScan::LinearScan(Cfg *Func) 101bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto : Func(Func), Ctx(Func->getContext()), Target(Func->getTarget()), 102b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth Verbose(BuildDefs::dump() && Func->isVerbose(IceV_LinearScan)), 103d46999474d2b4a388e1d8a7c71f06cd4cec51bfcKarl Schimpf UseReserve(getFlags().getRegAllocReserve()) {} 104d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 10557e126899b20c65ff3ea23a3b7d7a67ab30b99dcAndrew Scull// Prepare for full register allocation of all variables. We depend on liveness 10657e126899b20c65ff3ea23a3b7d7a67ab30b99dcAndrew Scull// analysis to have calculated live ranges. 10770d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnothvoid LinearScan::initForGlobal() { 10887ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth TimerMarker T(TimerStack::TT_initUnhandled, Func); 10970d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth FindPreference = true; 110a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // For full register allocation, normally we want to enable FindOverlap 111a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // (meaning we look for opportunities for two overlapping live ranges to 11257e126899b20c65ff3ea23a3b7d7a67ab30b99dcAndrew Scull // safely share the same register). However, we disable it for phi-lowering 113a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // register allocation since no overlap opportunities should be available and 114a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // it's more expensive to look for opportunities. 115a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth FindOverlap = (Kind != RAK_Phi); 11687ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth Unhandled.reserve(Vars.size()); 1174ead35a7e6d1d04d8cab5db23299fb5c2fe1943dJim Stichnoth UnhandledPrecolored.reserve(Vars.size()); 118d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Gather the live ranges of all variables and add them to the Unhandled set. 11987ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth for (Variable *Var : Vars) { 1204c5c57159b68c909bd4edef27c7ac09795a7f33bJim Stichnoth // Don't consider rematerializable variables. 1214c5c57159b68c909bd4edef27c7ac09795a7f33bJim Stichnoth if (Var->isRematerializable()) 1224c5c57159b68c909bd4edef27c7ac09795a7f33bJim Stichnoth continue; 123d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Explicitly don't consider zero-weight variables, which are meant to be 124d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // spill slots. 12511c9a325399b282cb4ea7d1d24d42fceeec2a09aAndrew Scull if (Var->mustNotHaveReg()) 12687ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth continue; 127d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Don't bother if the variable has a null live range, which means it was 128d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // never referenced. 12987ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth if (Var->getLiveRange().isEmpty()) 13087ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth continue; 13187ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth Var->untrimLiveRange(); 13287ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth Unhandled.push_back(Var); 13387ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth if (Var->hasReg()) { 13487ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth Var->setRegNumTmp(Var->getRegNum()); 13511c9a325399b282cb4ea7d1d24d42fceeec2a09aAndrew Scull Var->setMustHaveReg(); 13687ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth UnhandledPrecolored.push_back(Var); 13787ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth } 13887ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth } 13970d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth 14070d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth // Build the (ordered) list of FakeKill instruction numbers. 14170d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth Kills.clear(); 142a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // Phi lowering should not be creating new call instructions, so there should 143a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // be no infinite-weight not-yet-colored live ranges that span a call 144a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // instruction, hence no need to construct the Kills list. 145a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth if (Kind == RAK_Phi) 146a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth return; 14770d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth for (CfgNode *Node : Func->getNodes()) { 14829841e84014ccbe7344e00f44ce7695a017de69aJim Stichnoth for (Inst &I : Node->getInsts()) { 1495bff61c44841990680781892036adb17b3cff0c4Jim Stichnoth if (auto *Kill = llvm::dyn_cast<InstFakeKill>(&I)) { 15070d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth if (!Kill->isDeleted() && !Kill->getLinked()->isDeleted()) 15129841e84014ccbe7344e00f44ce7695a017de69aJim Stichnoth Kills.push_back(I.getNumber()); 15270d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth } 15370d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth } 15470d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth } 15570d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth} 15670d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth 157230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth// Validate the integrity of the live ranges. If there are any errors, it 158230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth// prints details and returns false. On success, it returns true. 159230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnothbool LinearScan::livenessValidateIntervals( 160230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth const DefUseErrorList &DefsWithoutUses, 161230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth const DefUseErrorList &UsesBeforeDefs, 162230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth const CfgVector<InstNumberT> &LRBegin, 163318f4cdaa21eac5ef1d16731e51cd7adb3083d3bJim Stichnoth const CfgVector<InstNumberT> &LREnd) const { 164230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth if (DefsWithoutUses.empty() && UsesBeforeDefs.empty()) 165230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth return true; 166230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth 167230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth if (!BuildDefs::dump()) 168230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth return false; 169230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth 170230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth OstreamLocker L(Ctx); 171230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth Ostream &Str = Ctx->getStrDump(); 172230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth for (SizeT VarNum : DefsWithoutUses) { 173230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth Variable *Var = Vars[VarNum]; 174230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth Str << "LR def without use, instruction " << LRBegin[VarNum] 175a91c34118294efbf08ebd11eed96fce83bf35f3cJim Stichnoth << ", variable " << Var->getName() << "\n"; 176230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth } 177230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth for (SizeT VarNum : UsesBeforeDefs) { 178230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth Variable *Var = Vars[VarNum]; 179230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth Str << "LR use before def, instruction " << LREnd[VarNum] << ", variable " 180a91c34118294efbf08ebd11eed96fce83bf35f3cJim Stichnoth << Var->getName() << "\n"; 181230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth } 182230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth return false; 183230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth} 184230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth 185a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth// Prepare for very simple register allocation of only infinite-weight Variables 186a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth// while respecting pre-colored Variables. Some properties we take advantage of: 18770d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth// 18870d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth// * Live ranges of interest consist of a single segment. 18970d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth// 19070d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth// * Live ranges of interest never span a call instruction. 19170d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth// 192d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// * Phi instructions are not considered because either phis have already been 193d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// lowered, or they don't contain any pre-colored or infinite-weight 194d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// Variables. 19570d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth// 196a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth// * We don't need to renumber instructions before computing live ranges because 197a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth// all the high-level ICE instructions are deleted prior to lowering, and the 198a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth// low-level instructions are added in monotonically increasing order. 19970d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth// 200d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// * There are no opportunities for register preference or allowing overlap. 20170d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth// 20270d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth// Some properties we aren't (yet) taking advantage of: 20370d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth// 204d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// * Because live ranges are a single segment, the Inactive set will always be 205d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// empty, and the live range trimming operation is unnecessary. 20670d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth// 207a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth// * Calculating overlap of single-segment live ranges could be optimized a bit. 20870d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnothvoid LinearScan::initForInfOnly() { 20970d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth TimerMarker T(TimerStack::TT_initUnhandled, Func); 21070d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth FindPreference = false; 21170d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth FindOverlap = false; 21270d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth SizeT NumVars = 0; 21370d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth 214d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Iterate across all instructions and record the begin and end of the live 215d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // range for each variable that is pre-colored or infinite weight. 21600741a005cf242d2e9108f7cc7c454246e13741cAndrew Scull CfgVector<InstNumberT> LRBegin(Vars.size(), Inst::NumberSentinel); 21700741a005cf242d2e9108f7cc7c454246e13741cAndrew Scull CfgVector<InstNumberT> LREnd(Vars.size(), Inst::NumberSentinel); 218230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth DefUseErrorList DefsWithoutUses, UsesBeforeDefs; 21970d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth for (CfgNode *Node : Func->getNodes()) { 2208cfeb69e17190d3bfe22a8a1cbd7679a114d68cfJim Stichnoth for (Inst &Instr : Node->getInsts()) { 2218cfeb69e17190d3bfe22a8a1cbd7679a114d68cfJim Stichnoth if (Instr.isDeleted()) 22270d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth continue; 2238cfeb69e17190d3bfe22a8a1cbd7679a114d68cfJim Stichnoth FOREACH_VAR_IN_INST(Var, Instr) { 224230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth if (Var->getIgnoreLiveness()) 225230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth continue; 226230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth if (Var->hasReg() || Var->mustHaveReg()) { 227230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth SizeT VarNum = Var->getIndex(); 2288cfeb69e17190d3bfe22a8a1cbd7679a114d68cfJim Stichnoth LREnd[VarNum] = Instr.getNumber(); 229230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth if (!Var->getIsArg() && LRBegin[VarNum] == Inst::NumberSentinel) 230230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth UsesBeforeDefs.push_back(VarNum); 231230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth } 232230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth } 2338cfeb69e17190d3bfe22a8a1cbd7679a114d68cfJim Stichnoth if (const Variable *Var = Instr.getDest()) { 234cc89c959c2f602361488e0fdc0bf62e5d197d15cJim Stichnoth if (!Var->getIgnoreLiveness() && 23511c9a325399b282cb4ea7d1d24d42fceeec2a09aAndrew Scull (Var->hasReg() || Var->mustHaveReg())) { 23670d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth if (LRBegin[Var->getIndex()] == Inst::NumberSentinel) { 2378cfeb69e17190d3bfe22a8a1cbd7679a114d68cfJim Stichnoth LRBegin[Var->getIndex()] = Instr.getNumber(); 23870d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth ++NumVars; 23970d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth } 24070d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth } 24170d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth } 24270d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth } 24370d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth } 24470d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth 24570d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth Unhandled.reserve(NumVars); 2464ead35a7e6d1d04d8cab5db23299fb5c2fe1943dJim Stichnoth UnhandledPrecolored.reserve(NumVars); 24770d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth for (SizeT i = 0; i < Vars.size(); ++i) { 24870d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth Variable *Var = Vars[i]; 2494c5c57159b68c909bd4edef27c7ac09795a7f33bJim Stichnoth if (Var->isRematerializable()) 2504c5c57159b68c909bd4edef27c7ac09795a7f33bJim Stichnoth continue; 25170d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth if (LRBegin[i] != Inst::NumberSentinel) { 252230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth if (LREnd[i] == Inst::NumberSentinel) { 253230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth DefsWithoutUses.push_back(i); 254230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth continue; 255230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth } 25670d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth Unhandled.push_back(Var); 25770d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth Var->resetLiveRange(); 25811c9a325399b282cb4ea7d1d24d42fceeec2a09aAndrew Scull Var->addLiveRange(LRBegin[i], LREnd[i]); 25970d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth Var->untrimLiveRange(); 26070d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth if (Var->hasReg()) { 26170d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth Var->setRegNumTmp(Var->getRegNum()); 26211c9a325399b282cb4ea7d1d24d42fceeec2a09aAndrew Scull Var->setMustHaveReg(); 26370d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth UnhandledPrecolored.push_back(Var); 26470d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth } 26570d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth --NumVars; 26670d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth } 26770d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth } 268230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth 269230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth if (!livenessValidateIntervals(DefsWithoutUses, UsesBeforeDefs, LRBegin, 270230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth LREnd)) { 271230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth llvm::report_fatal_error("initForInfOnly: Liveness error"); 272230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth return; 273230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth } 274230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth 275230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth if (!DefsWithoutUses.empty() || !UsesBeforeDefs.empty()) { 276230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth if (BuildDefs::dump()) { 277230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth OstreamLocker L(Ctx); 278230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth Ostream &Str = Ctx->getStrDump(); 279230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth for (SizeT VarNum : DefsWithoutUses) { 280230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth Variable *Var = Vars[VarNum]; 281230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth Str << "LR def without use, instruction " << LRBegin[VarNum] 282a91c34118294efbf08ebd11eed96fce83bf35f3cJim Stichnoth << ", variable " << Var->getName() << "\n"; 283230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth } 284230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth for (SizeT VarNum : UsesBeforeDefs) { 285230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth Variable *Var = Vars[VarNum]; 286230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth Str << "LR use before def, instruction " << LREnd[VarNum] 287a91c34118294efbf08ebd11eed96fce83bf35f3cJim Stichnoth << ", variable " << Var->getName() << "\n"; 288230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth } 289230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth } 290230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth llvm::report_fatal_error("initForInfOnly: Liveness error"); 291230d4101fb3c591d044406eef27d0ce43ffab53eJim Stichnoth } 292d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // This isn't actually a fatal condition, but it would be nice to know if we 293d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // somehow pre-calculated Unhandled's size wrong. 29470d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth assert(NumVars == 0); 29570d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth 296d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Don't build up the list of Kills because we know that no infinite-weight 297d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Variable has a live range spanning a call. 29870d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth Kills.clear(); 29970d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth} 30070d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth 3014001c9394cade69a60a6b798b7ece891f3b68abbJim Stichnothvoid LinearScan::initForSecondChance() { 3024001c9394cade69a60a6b798b7ece891f3b68abbJim Stichnoth TimerMarker T(TimerStack::TT_initUnhandled, Func); 3034001c9394cade69a60a6b798b7ece891f3b68abbJim Stichnoth FindPreference = true; 3044001c9394cade69a60a6b798b7ece891f3b68abbJim Stichnoth FindOverlap = true; 3054001c9394cade69a60a6b798b7ece891f3b68abbJim Stichnoth const VarList &Vars = Func->getVariables(); 3064001c9394cade69a60a6b798b7ece891f3b68abbJim Stichnoth Unhandled.reserve(Vars.size()); 3074001c9394cade69a60a6b798b7ece891f3b68abbJim Stichnoth UnhandledPrecolored.reserve(Vars.size()); 3084001c9394cade69a60a6b798b7ece891f3b68abbJim Stichnoth for (Variable *Var : Vars) { 3094c5c57159b68c909bd4edef27c7ac09795a7f33bJim Stichnoth if (Var->isRematerializable()) 3104c5c57159b68c909bd4edef27c7ac09795a7f33bJim Stichnoth continue; 3114001c9394cade69a60a6b798b7ece891f3b68abbJim Stichnoth if (Var->hasReg()) { 3124001c9394cade69a60a6b798b7ece891f3b68abbJim Stichnoth Var->untrimLiveRange(); 3134001c9394cade69a60a6b798b7ece891f3b68abbJim Stichnoth Var->setRegNumTmp(Var->getRegNum()); 3144001c9394cade69a60a6b798b7ece891f3b68abbJim Stichnoth Var->setMustHaveReg(); 3154001c9394cade69a60a6b798b7ece891f3b68abbJim Stichnoth UnhandledPrecolored.push_back(Var); 3164001c9394cade69a60a6b798b7ece891f3b68abbJim Stichnoth Unhandled.push_back(Var); 3174001c9394cade69a60a6b798b7ece891f3b68abbJim Stichnoth } 3184001c9394cade69a60a6b798b7ece891f3b68abbJim Stichnoth } 3194001c9394cade69a60a6b798b7ece891f3b68abbJim Stichnoth for (Variable *Var : Evicted) { 3204001c9394cade69a60a6b798b7ece891f3b68abbJim Stichnoth Var->untrimLiveRange(); 3214001c9394cade69a60a6b798b7ece891f3b68abbJim Stichnoth Unhandled.push_back(Var); 3224001c9394cade69a60a6b798b7ece891f3b68abbJim Stichnoth } 3234001c9394cade69a60a6b798b7ece891f3b68abbJim Stichnoth} 3244001c9394cade69a60a6b798b7ece891f3b68abbJim Stichnoth 3257cd926d6d4f401dd3595e0682f48ede3e04ac7f7Manasij Mukherjeevoid LinearScan::init(RegAllocKind Kind, CfgSet<Variable *> ExcludeVars) { 326a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth this->Kind = Kind; 32770d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth Unhandled.clear(); 32870d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth UnhandledPrecolored.clear(); 32970d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth Handled.clear(); 33070d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth Inactive.clear(); 33170d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth Active.clear(); 3327cd926d6d4f401dd3595e0682f48ede3e04ac7f7Manasij Mukherjee Vars.clear(); 3337cd926d6d4f401dd3595e0682f48ede3e04ac7f7Manasij Mukherjee Vars.reserve(Func->getVariables().size() - ExcludeVars.size()); 3347cd926d6d4f401dd3595e0682f48ede3e04ac7f7Manasij Mukherjee for (auto *Var : Func->getVariables()) { 3357cd926d6d4f401dd3595e0682f48ede3e04ac7f7Manasij Mukherjee if (ExcludeVars.find(Var) == ExcludeVars.end()) 3367cd926d6d4f401dd3595e0682f48ede3e04ac7f7Manasij Mukherjee Vars.emplace_back(Var); 3377cd926d6d4f401dd3595e0682f48ede3e04ac7f7Manasij Mukherjee } 33870d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth 339bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto SizeT NumRegs = Target->getNumRegisters(); 340bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto RegAliases.resize(NumRegs); 341bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto for (SizeT Reg = 0; Reg < NumRegs; ++Reg) { 3428aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth RegAliases[Reg] = &Target->getAliasesForRegister(RegNumT::fromInt(Reg)); 343bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto } 344bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto 34570d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth switch (Kind) { 346a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth case RAK_Unknown: 347a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth llvm::report_fatal_error("Invalid RAK_Unknown"); 348a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth break; 34970d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth case RAK_Global: 350a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth case RAK_Phi: 35170d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth initForGlobal(); 35270d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth break; 35370d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth case RAK_InfOnly: 35470d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth initForInfOnly(); 35570d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth break; 3564001c9394cade69a60a6b798b7ece891f3b68abbJim Stichnoth case RAK_SecondChance: 3574001c9394cade69a60a6b798b7ece891f3b68abbJim Stichnoth initForSecondChance(); 3584001c9394cade69a60a6b798b7ece891f3b68abbJim Stichnoth break; 35970d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth } 36070d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth 3614001c9394cade69a60a6b798b7ece891f3b68abbJim Stichnoth Evicted.clear(); 3624001c9394cade69a60a6b798b7ece891f3b68abbJim Stichnoth 363992f91ddfeb7e68bdb51498194c2af7e9017aeb1Jim Stichnoth auto CompareRanges = [](const Variable *L, const Variable *R) { 364aee5fa8dd6aa948160a290c8237d7ae4875811fbQining Lu InstNumberT Lstart = L->getLiveRange().getStart(); 365aee5fa8dd6aa948160a290c8237d7ae4875811fbQining Lu InstNumberT Rstart = R->getLiveRange().getStart(); 366aee5fa8dd6aa948160a290c8237d7ae4875811fbQining Lu if (Lstart == Rstart) 367aee5fa8dd6aa948160a290c8237d7ae4875811fbQining Lu return L->getIndex() < R->getIndex(); 368aee5fa8dd6aa948160a290c8237d7ae4875811fbQining Lu return Lstart < Rstart; 36987ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth }; 37087ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth // Do a reverse sort so that erasing elements (from the end) is fast. 371992f91ddfeb7e68bdb51498194c2af7e9017aeb1Jim Stichnoth std::sort(Unhandled.rbegin(), Unhandled.rend(), CompareRanges); 37287ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth std::sort(UnhandledPrecolored.rbegin(), UnhandledPrecolored.rend(), 373992f91ddfeb7e68bdb51498194c2af7e9017aeb1Jim Stichnoth CompareRanges); 3744ead35a7e6d1d04d8cab5db23299fb5c2fe1943dJim Stichnoth 3754ead35a7e6d1d04d8cab5db23299fb5c2fe1943dJim Stichnoth Handled.reserve(Unhandled.size()); 3764ead35a7e6d1d04d8cab5db23299fb5c2fe1943dJim Stichnoth Inactive.reserve(Unhandled.size()); 3774ead35a7e6d1d04d8cab5db23299fb5c2fe1943dJim Stichnoth Active.reserve(Unhandled.size()); 3784001c9394cade69a60a6b798b7ece891f3b68abbJim Stichnoth Evicted.reserve(Unhandled.size()); 37987ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth} 38087ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth 381a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth// This is called when Cur must be allocated a register but no registers are 382a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth// available across Cur's live range. To handle this, we find a register that is 383a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth// not explicitly used during Cur's live range, spill that register to a stack 384a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth// location right before Cur's live range begins, and fill (reload) the register 385a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth// from the stack location right after Cur's live range ends. 386d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scullvoid LinearScan::addSpillFill(IterationState &Iter) { 387d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Identify the actual instructions that begin and end Iter.Cur's live range. 388d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Iterate through Iter.Cur's node's instruction list until we find the actual 389d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // instructions with instruction numbers corresponding to Iter.Cur's recorded 390d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // live range endpoints. This sounds inefficient but shouldn't be a problem 391d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // in practice because: 392a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // (1) This function is almost never called in practice. 393a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // (2) Since this register over-subscription problem happens only for 394a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // phi-lowered instructions, the number of instructions in the node is 395a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // proportional to the number of phi instructions in the original node, 396a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // which is never very large in practice. 397d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // (3) We still have to iterate through all instructions of Iter.Cur's live 398d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // range to find all explicitly used registers (though the live range is 399d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // usually only 2-3 instructions), so the main cost that could be avoided 400d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // would be finding the instruction that begin's Iter.Cur's live range. 401d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull assert(!Iter.Cur->getLiveRange().isEmpty()); 402d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull InstNumberT Start = Iter.Cur->getLiveRange().getStart(); 403d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull InstNumberT End = Iter.Cur->getLiveRange().getEnd(); 404d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull CfgNode *Node = Func->getVMetadata()->getLocalUseNode(Iter.Cur); 405a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth assert(Node); 406a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth InstList &Insts = Node->getInsts(); 407a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth InstList::iterator SpillPoint = Insts.end(); 408a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth InstList::iterator FillPoint = Insts.end(); 409a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // Stop searching after we have found both the SpillPoint and the FillPoint. 410a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth for (auto I = Insts.begin(), E = Insts.end(); 411a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth I != E && (SpillPoint == E || FillPoint == E); ++I) { 412a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth if (I->getNumber() == Start) 413a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth SpillPoint = I; 414a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth if (I->getNumber() == End) 415a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth FillPoint = I; 416a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth if (SpillPoint != E) { 417a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth // Remove from RegMask any physical registers referenced during Cur's live 418a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth // range. Start looking after SpillPoint gets set, i.e. once Cur's live 419a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth // range begins. 420ec3f56532be1792d04ed470221df663bb8ca9c19John Porto FOREACH_VAR_IN_INST(Var, *I) { 421bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto if (!Var->hasRegTmp()) 422bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto continue; 423e82b560e649f8a68bcb252b9b002708e74d962d3John Porto const auto &Aliases = *RegAliases[Var->getRegNumTmp()]; 4248aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth for (RegNumT RegAlias : RegNumBVIter(Aliases)) { 425bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto Iter.RegMask[RegAlias] = false; 426bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto } 427a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth } 428a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth } 429a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth } 430a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth assert(SpillPoint != Insts.end()); 431a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth assert(FillPoint != Insts.end()); 432a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth ++FillPoint; 4338aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth // TODO(stichnot): Randomize instead of *.begin() which maps to find_first(). 4348aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth const RegNumT RegNum = *RegNumBVIter(Iter.RegMask).begin(); 435d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.Cur->setRegNumTmp(RegNum); 436d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Variable *Preg = Target->getPhysicalRegister(RegNum, Iter.Cur->getType()); 437a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth // TODO(stichnot): Add SpillLoc to VariablesMetadata tracking so that SpillLoc 438a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth // is correctly identified as !isMultiBlock(), reducing stack frame size. 439d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Variable *SpillLoc = Func->makeVariable(Iter.Cur->getType()); 440a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // Add "reg=FakeDef;spill=reg" before SpillPoint 441a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth Target->lowerInst(Node, SpillPoint, InstFakeDef::create(Func, Preg)); 442a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth Target->lowerInst(Node, SpillPoint, InstAssign::create(Func, SpillLoc, Preg)); 443a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth // add "reg=spill;FakeUse(reg)" before FillPoint 444a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth Target->lowerInst(Node, FillPoint, InstAssign::create(Func, Preg, SpillLoc)); 445a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth Target->lowerInst(Node, FillPoint, InstFakeUse::create(Func, Preg)); 446a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth} 447a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth 448d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scullvoid LinearScan::handleActiveRangeExpiredOrInactive(const Variable *Cur) { 449d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull for (SizeT I = Active.size(); I > 0; --I) { 450d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull const SizeT Index = I - 1; 451d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Variable *Item = Active[Index]; 452d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Item->trimLiveRange(Cur->getLiveRange().getStart()); 453d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull bool Moved = false; 454d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Item->rangeEndsBefore(Cur)) { 455d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Move Item from Active to Handled list. 456696605575c4ba11df5ec56149c561839d1bfe532Jim Stichnoth dumpLiveRangeTrace("Expiring ", Item); 457d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull moveItem(Active, Index, Handled); 458d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Moved = true; 459d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } else if (!Item->rangeOverlapsStart(Cur)) { 460d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Move Item from Active to Inactive list. 461696605575c4ba11df5ec56149c561839d1bfe532Jim Stichnoth dumpLiveRangeTrace("Inactivating ", Item); 462d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull moveItem(Active, Index, Inactive); 463d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Moved = true; 464d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 465d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Moved) { 466d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Decrement Item from RegUses[]. 467d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull assert(Item->hasRegTmp()); 468e82b560e649f8a68bcb252b9b002708e74d962d3John Porto const auto &Aliases = *RegAliases[Item->getRegNumTmp()]; 4698aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth for (RegNumT RegAlias : RegNumBVIter(Aliases)) { 470bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto --RegUses[RegAlias]; 471bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto assert(RegUses[RegAlias] >= 0); 472bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto } 473d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 474d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 475d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull} 476d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 477d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scullvoid LinearScan::handleInactiveRangeExpiredOrReactivated(const Variable *Cur) { 478d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull for (SizeT I = Inactive.size(); I > 0; --I) { 479d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull const SizeT Index = I - 1; 480d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Variable *Item = Inactive[Index]; 481d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Item->trimLiveRange(Cur->getLiveRange().getStart()); 482d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Item->rangeEndsBefore(Cur)) { 483d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Move Item from Inactive to Handled list. 484696605575c4ba11df5ec56149c561839d1bfe532Jim Stichnoth dumpLiveRangeTrace("Expiring ", Item); 485d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull moveItem(Inactive, Index, Handled); 486d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } else if (Item->rangeOverlapsStart(Cur)) { 487d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Move Item from Inactive to Active list. 488696605575c4ba11df5ec56149c561839d1bfe532Jim Stichnoth dumpLiveRangeTrace("Reactivating ", Item); 489d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull moveItem(Inactive, Index, Active); 490d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Increment Item in RegUses[]. 491d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull assert(Item->hasRegTmp()); 492e82b560e649f8a68bcb252b9b002708e74d962d3John Porto const auto &Aliases = *RegAliases[Item->getRegNumTmp()]; 4938aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth for (RegNumT RegAlias : RegNumBVIter(Aliases)) { 494bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto assert(RegUses[RegAlias] >= 0); 495bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto ++RegUses[RegAlias]; 496bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto } 497d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 498d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 499d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull} 500d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 501d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// Infer register preference and allowable overlap. Only form a preference when 502a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth// the current Variable has an unambiguous "first" definition. The preference is 503a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth// some source Variable of the defining instruction that either is assigned a 504a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth// register that is currently free, or that is assigned a register that is not 505a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth// free but overlap is allowed. Overlap is allowed when the Variable under 506a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth// consideration is single-definition, and its definition is a simple assignment 507a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth// - i.e., the register gets copied/aliased but is never modified. Furthermore, 508a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth// overlap is only allowed when preferred Variable definition instructions do 509a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth// not appear within the current Variable's live range. 510d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scullvoid LinearScan::findRegisterPreference(IterationState &Iter) { 511d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.Prefer = nullptr; 5125fa0a5f7f730f33e6987527a261de8d833d7585cReed Kotler Iter.PreferReg = RegNumT(); 513d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.AllowOverlap = false; 514d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 515a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth if (!FindPreference) 516a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth return; 517a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth 518a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth VariablesMetadata *VMetadata = Func->getVMetadata(); 519a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth const Inst *DefInst = VMetadata->getFirstDefinitionSingleBlock(Iter.Cur); 520a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth if (DefInst == nullptr) 521a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth return; 522a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth 523a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth assert(DefInst->getDest() == Iter.Cur); 524a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth const bool IsSingleDefAssign = 525a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth DefInst->isVarAssign() && !VMetadata->isMultiDef(Iter.Cur); 526a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth FOREACH_VAR_IN_INST(SrcVar, *DefInst) { 527a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth // Only consider source variables that have (so far) been assigned a 528a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth // register. 529a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth if (!SrcVar->hasRegTmp()) 530a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth continue; 531a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth 532a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth // That register must be one in the RegMask set, e.g. don't try to prefer 533a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth // the stack pointer as a result of the stacksave intrinsic. 534e82b560e649f8a68bcb252b9b002708e74d962d3John Porto const auto &Aliases = *RegAliases[SrcVar->getRegNumTmp()]; 5358aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth const int SrcReg = (Iter.RegMask & Aliases).find_first(); 536a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth if (SrcReg == -1) 537a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth continue; 538a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth 539a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth if (FindOverlap && IsSingleDefAssign && !Iter.Free[SrcReg]) { 540a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth // Don't bother trying to enable AllowOverlap if the register is already 541a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth // free (hence the test on Iter.Free[SrcReg]). 542a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth Iter.AllowOverlap = !overlapsDefs(Func, Iter.Cur, SrcVar); 543a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth } 544a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth if (Iter.AllowOverlap || Iter.Free[SrcReg]) { 545a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth Iter.Prefer = SrcVar; 5468aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth Iter.PreferReg = RegNumT::fromInt(SrcReg); 547a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth // Stop looking for a preference after the first valid preference is 548a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth // found. One might think that we should look at all instruction 549a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth // variables to find the best <Prefer,AllowOverlap> combination, but note 550a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth // that AllowOverlap can only be true for a simple assignment statement 551a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth // which can have only one source operand, so it's not possible for 552a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth // AllowOverlap to be true beyond the first source operand. 553a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth FOREACH_VAR_IN_INST_BREAK; 554d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 555d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 556a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth if (BuildDefs::dump() && Verbose && Iter.Prefer) { 557a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth Ostream &Str = Ctx->getStrDump(); 558a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth Str << "Initial Iter.Prefer="; 559a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth Iter.Prefer->dump(Func); 560a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth Str << " R=" << Iter.PreferReg << " LIVE=" << Iter.Prefer->getLiveRange() 561a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth << " Overlap=" << Iter.AllowOverlap << "\n"; 562a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth } 563d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull} 564d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 565b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth// Remove registers from the Iter.Free[] list where an Inactive range overlaps 566b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth// with the current range. 567d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scullvoid LinearScan::filterFreeWithInactiveRanges(IterationState &Iter) { 568d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull for (const Variable *Item : Inactive) { 569bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto if (!Item->rangeOverlaps(Iter.Cur)) 570bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto continue; 571e82b560e649f8a68bcb252b9b002708e74d962d3John Porto const auto &Aliases = *RegAliases[Item->getRegNumTmp()]; 5728aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth for (RegNumT RegAlias : RegNumBVIter(Aliases)) { 5738aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth // Don't assert(Iter.Free[RegAlias]) because in theory (though probably 574b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth // never in practice) there could be two inactive variables that were 575b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth // marked with AllowOverlap. 576bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto Iter.Free[RegAlias] = false; 577b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth Iter.FreeUnfiltered[RegAlias] = false; 578d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Disable AllowOverlap if an Inactive variable, which is not Prefer, 579a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth // shares Prefer's register, and has a definition within Cur's live range. 580d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Iter.AllowOverlap && Item != Iter.Prefer && 581bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto RegAlias == Iter.PreferReg && overlapsDefs(Func, Iter.Cur, Item)) { 582d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.AllowOverlap = false; 583d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull dumpDisableOverlap(Func, Item, "Inactive"); 584d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 585d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 586d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 587d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull} 588d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 589b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth// Remove registers from the Iter.Free[] list where an Unhandled pre-colored 590b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth// range overlaps with the current range, and set those registers to infinite 591b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth// weight so that they aren't candidates for eviction. 592b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth// Cur->rangeEndsBefore(Item) is an early exit check that turns a guaranteed 593b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth// O(N^2) algorithm into expected linear complexity. 594d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scullvoid LinearScan::filterFreeWithPrecoloredRanges(IterationState &Iter) { 5954c5c57159b68c909bd4edef27c7ac09795a7f33bJim Stichnoth // TODO(stichnot): Partition UnhandledPrecolored according to register class, 5964c5c57159b68c909bd4edef27c7ac09795a7f33bJim Stichnoth // to restrict the number of overlap comparisons needed. 597d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull for (Variable *Item : reverse_range(UnhandledPrecolored)) { 598d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull assert(Item->hasReg()); 599d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Iter.Cur->rangeEndsBefore(Item)) 600d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull break; 601a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth if (!Item->rangeOverlaps(Iter.Cur)) 602a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth continue; 603e82b560e649f8a68bcb252b9b002708e74d962d3John Porto const auto &Aliases = 604a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth *RegAliases[Item->getRegNum()]; // Note: not getRegNumTmp() 6058aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth for (RegNumT RegAlias : RegNumBVIter(Aliases)) { 606a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth Iter.Weights[RegAlias].setWeight(RegWeight::Inf); 607a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth Iter.Free[RegAlias] = false; 608b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth Iter.FreeUnfiltered[RegAlias] = false; 609a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth Iter.PrecoloredUnhandledMask[RegAlias] = true; 610a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth // Disable Iter.AllowOverlap if the preferred register is one of these 611a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth // pre-colored unhandled overlapping ranges. 612a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth if (Iter.AllowOverlap && RegAlias == Iter.PreferReg) { 613a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth Iter.AllowOverlap = false; 614a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth dumpDisableOverlap(Func, Item, "PrecoloredUnhandled"); 615d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 616d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 617d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 618d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull} 619d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 620d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scullvoid LinearScan::allocatePrecoloredRegister(Variable *Cur) { 6218aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth const auto RegNum = Cur->getRegNum(); 622d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // RegNumTmp should have already been set above. 623d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull assert(Cur->getRegNumTmp() == RegNum); 624d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull dumpLiveRangeTrace("Precoloring ", Cur); 625d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Active.push_back(Cur); 626e82b560e649f8a68bcb252b9b002708e74d962d3John Porto const auto &Aliases = *RegAliases[RegNum]; 6278aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth for (RegNumT RegAlias : RegNumBVIter(Aliases)) { 628bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto assert(RegUses[RegAlias] >= 0); 629bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto ++RegUses[RegAlias]; 630bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto } 631d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull assert(!UnhandledPrecolored.empty()); 632d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull assert(UnhandledPrecolored.back() == Cur); 633d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull UnhandledPrecolored.pop_back(); 634d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull} 635d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 636d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scullvoid LinearScan::allocatePreferredRegister(IterationState &Iter) { 637d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.Cur->setRegNumTmp(Iter.PreferReg); 638d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull dumpLiveRangeTrace("Preferring ", Iter.Cur); 639e82b560e649f8a68bcb252b9b002708e74d962d3John Porto const auto &Aliases = *RegAliases[Iter.PreferReg]; 6408aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth for (RegNumT RegAlias : RegNumBVIter(Aliases)) { 641bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto assert(RegUses[RegAlias] >= 0); 642bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto ++RegUses[RegAlias]; 643bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto } 644d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Active.push_back(Iter.Cur); 645d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull} 646d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 647b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnothvoid LinearScan::allocateFreeRegister(IterationState &Iter, bool Filtered) { 6488aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth const RegNumT RegNum = 6498aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth *RegNumBVIter(Filtered ? Iter.Free : Iter.FreeUnfiltered).begin(); 650d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.Cur->setRegNumTmp(RegNum); 651b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth if (Filtered) 6524b6e4b44a8abe5f4c5f209d45828cc1ef1bb6a1eJohn Porto dumpLiveRangeTrace("Allocating Y ", Iter.Cur); 653b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth else 654b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth dumpLiveRangeTrace("Allocating X ", Iter.Cur); 655e82b560e649f8a68bcb252b9b002708e74d962d3John Porto const auto &Aliases = *RegAliases[RegNum]; 6568aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth for (RegNumT RegAlias : RegNumBVIter(Aliases)) { 657bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto assert(RegUses[RegAlias] >= 0); 658bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto ++RegUses[RegAlias]; 659bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto } 660d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Active.push_back(Iter.Cur); 661d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull} 662d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 663d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scullvoid LinearScan::handleNoFreeRegisters(IterationState &Iter) { 664d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Check Active ranges. 665d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull for (const Variable *Item : Active) { 666d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull assert(Item->rangeOverlaps(Iter.Cur)); 667d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull assert(Item->hasRegTmp()); 668e82b560e649f8a68bcb252b9b002708e74d962d3John Porto const auto &Aliases = *RegAliases[Item->getRegNumTmp()]; 669bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto // We add the Item's weight to each alias/subregister to represent that, 670bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto // should we decide to pick any of them, then we would incur that many 671bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto // memory accesses. 672bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto RegWeight W = Item->getWeight(Func); 6738aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth for (RegNumT RegAlias : RegNumBVIter(Aliases)) { 674bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto Iter.Weights[RegAlias].addWeight(W); 675bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto } 676d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 677d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Same as above, but check Inactive ranges instead of Active. 678d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull for (const Variable *Item : Inactive) { 679bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto if (!Item->rangeOverlaps(Iter.Cur)) 680bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto continue; 681d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull assert(Item->hasRegTmp()); 682e82b560e649f8a68bcb252b9b002708e74d962d3John Porto const auto &Aliases = *RegAliases[Item->getRegNumTmp()]; 683bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto RegWeight W = Item->getWeight(Func); 6848aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth for (RegNumT RegAlias : RegNumBVIter(Aliases)) { 685bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto Iter.Weights[RegAlias].addWeight(W); 686bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto } 687d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 688d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 689a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth // All the weights are now calculated. Find the register with smallest weight. 690b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth int32_t MinWeightIndex = findMinWeightIndex(Iter.RegMask, Iter.Weights); 691d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 6922655d9627f11b0c97f10eacf1f730bf66e5db05bJim Stichnoth if (MinWeightIndex < 0 || 6932655d9627f11b0c97f10eacf1f730bf66e5db05bJim Stichnoth Iter.Cur->getWeight(Func) <= Iter.Weights[MinWeightIndex]) { 694b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth if (!Iter.Cur->mustHaveReg()) { 695b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth // Iter.Cur doesn't have priority over any other live ranges, so don't 696b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth // allocate any register to it, and move it to the Handled state. 697b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth Handled.push_back(Iter.Cur); 698b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth return; 699d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 700b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth if (Kind == RAK_Phi) { 701b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth // Iter.Cur is infinite-weight but all physical registers are already 702b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth // taken, so we need to force one to be temporarily available. 703b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth addSpillFill(Iter); 704b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth Handled.push_back(Iter.Cur); 705b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth return; 706b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth } 707b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth // The remaining portion of the enclosing "if" block should only be 708b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth // reachable if we are manually limiting physical registers for testing. 709b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth if (UseReserve) { 710b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth if (Iter.FreeUnfiltered.any()) { 711b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth // There is some available physical register held in reserve, so use it. 712b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth constexpr bool NotFiltered = false; 713b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth allocateFreeRegister(Iter, NotFiltered); 714b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth // Iter.Cur is now on the Active list. 715b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth return; 716d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 717b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth // At this point, we need to find some reserve register that is already 718b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth // assigned to a non-infinite-weight variable. This could happen if some 719b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth // variable was previously assigned an alias of such a register. 720b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth MinWeightIndex = findMinWeightIndex(Iter.RegMaskUnfiltered, Iter.Weights); 721b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth } 722b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth if (Iter.Cur->getWeight(Func) <= Iter.Weights[MinWeightIndex]) { 723b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth dumpLiveRangeTrace("Failing ", Iter.Cur); 724b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth Func->setError("Unable to find a physical register for an " 725b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth "infinite-weight live range " 726b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth "(consider using -reg-reserve): " + 727a91c34118294efbf08ebd11eed96fce83bf35f3cJim Stichnoth Iter.Cur->getName()); 728b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth Handled.push_back(Iter.Cur); 729b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth return; 730d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 731b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth // At this point, MinWeightIndex points to a valid reserve register to 732b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth // reallocate to Iter.Cur, so drop into the eviction code. 733b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth } 734b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth 735b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth // Evict all live ranges in Active that register number MinWeightIndex is 736b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth // assigned to. 737e82b560e649f8a68bcb252b9b002708e74d962d3John Porto const auto &Aliases = *RegAliases[MinWeightIndex]; 738b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth for (SizeT I = Active.size(); I > 0; --I) { 739b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth const SizeT Index = I - 1; 740b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth Variable *Item = Active[Index]; 7418aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth const auto RegNum = Item->getRegNumTmp(); 742b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth if (Aliases[RegNum]) { 743b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth dumpLiveRangeTrace("Evicting A ", Item); 744e82b560e649f8a68bcb252b9b002708e74d962d3John Porto const auto &Aliases = *RegAliases[RegNum]; 7458aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth for (RegNumT RegAlias : RegNumBVIter(Aliases)) { 746b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth --RegUses[RegAlias]; 747b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth assert(RegUses[RegAlias] >= 0); 748d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 7495fa0a5f7f730f33e6987527a261de8d833d7585cReed Kotler Item->setRegNumTmp(RegNumT()); 750b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth moveItem(Active, Index, Handled); 751b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth Evicted.push_back(Item); 752d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 753b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth } 754b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth // Do the same for Inactive. 755b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth for (SizeT I = Inactive.size(); I > 0; --I) { 756b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth const SizeT Index = I - 1; 757b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth Variable *Item = Inactive[Index]; 758b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth // Note: The Item->rangeOverlaps(Cur) clause is not part of the description 759b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth // of AssignMemLoc() in the original paper. But there doesn't seem to be any 760b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth // need to evict an inactive live range that doesn't overlap with the live 761b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth // range currently being considered. It's especially bad if we would end up 762b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth // evicting an infinite-weight but currently-inactive live range. The most 763b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth // common situation for this would be a scratch register kill set for call 764b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth // instructions. 765b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth if (Aliases[Item->getRegNumTmp()] && Item->rangeOverlaps(Iter.Cur)) { 766b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth dumpLiveRangeTrace("Evicting I ", Item); 7675fa0a5f7f730f33e6987527a261de8d833d7585cReed Kotler Item->setRegNumTmp(RegNumT()); 768b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth moveItem(Inactive, Index, Handled); 769b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth Evicted.push_back(Item); 770bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto } 771d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 772b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth // Assign the register to Cur. 7738aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth Iter.Cur->setRegNumTmp(RegNumT::fromInt(MinWeightIndex)); 7748aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth for (RegNumT RegAlias : RegNumBVIter(Aliases)) { 775b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth assert(RegUses[RegAlias] >= 0); 776b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth ++RegUses[RegAlias]; 777b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth } 778b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth Active.push_back(Iter.Cur); 7794b6e4b44a8abe5f4c5f209d45828cc1ef1bb6a1eJohn Porto dumpLiveRangeTrace("Allocating Z ", Iter.Cur); 780d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull} 781d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 782e82b560e649f8a68bcb252b9b002708e74d962d3John Portovoid LinearScan::assignFinalRegisters(const SmallBitVector &RegMaskFull, 783e82b560e649f8a68bcb252b9b002708e74d962d3John Porto const SmallBitVector &PreDefinedRegisters, 784e82b560e649f8a68bcb252b9b002708e74d962d3John Porto bool Randomized) { 785d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull const size_t NumRegisters = RegMaskFull.size(); 7868aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth llvm::SmallVector<RegNumT, REGS_SIZE> Permutation(NumRegisters); 787d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Randomized) { 788d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Create a random number generator for regalloc randomization. Merge 789d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // function's sequence and Kind value as the Salt. Because regAlloc() is 79057e126899b20c65ff3ea23a3b7d7a67ab30b99dcAndrew Scull // called twice under O2, the second time with RAK_Phi, we check Kind == 79157e126899b20c65ff3ea23a3b7d7a67ab30b99dcAndrew Scull // RAK_Phi to determine the lowest-order bit to make sure the Salt is 79257e126899b20c65ff3ea23a3b7d7a67ab30b99dcAndrew Scull // different. 793d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull uint64_t Salt = 794d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull (Func->getSequenceNumber() << 1) ^ (Kind == RAK_Phi ? 0u : 1u); 795bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto Target->makeRandomRegisterPermutation( 796d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Permutation, PreDefinedRegisters | ~RegMaskFull, Salt); 797d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 798d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 799d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Finish up by setting RegNum = RegNumTmp (or a random permutation thereof) 800d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // for each Variable. 801d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull for (Variable *Item : Handled) { 8028aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth const auto RegNum = Item->getRegNumTmp(); 8038aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth auto AssignedRegNum = RegNum; 804d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 805d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Randomized && Item->hasRegTmp() && !Item->hasReg()) { 806d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull AssignedRegNum = Permutation[RegNum]; 807d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 808a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth if (BuildDefs::dump() && Verbose) { 809d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Ostream &Str = Ctx->getStrDump(); 810d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (!Item->hasRegTmp()) { 811d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Str << "Not assigning "; 812d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Item->dump(Func); 813d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Str << "\n"; 814d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } else { 815d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Str << (AssignedRegNum == Item->getRegNum() ? "Reassigning " 816d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull : "Assigning ") 8174a659477004e85c491e98311dc5cf0a543ebe547Jim Stichnoth << Target->getRegName(AssignedRegNum, Item->getType()) << "(r" 818bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto << AssignedRegNum << ") to "; 819d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Item->dump(Func); 820d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Str << "\n"; 821d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 822d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 823d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Item->setRegNum(AssignedRegNum); 824d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 825d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull} 826d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 827d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// Implements the linear-scan algorithm. Based on "Linear Scan Register 828d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// Allocation in the Context of SSA Form and Register Constraints" by Hanspeter 829d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// Mössenböck and Michael Pfeiffer, 830d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// ftp://ftp.ssw.uni-linz.ac.at/pub/Papers/Moe02.PDF. This implementation is 831a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth// modified to take affinity into account and allow two interfering variables to 832a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth// share the same register in certain cases. 833d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth// 834d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// Requires running Cfg::liveness(Liveness_Intervals) in preparation. Results 835d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull// are assigned to Variable::RegNum for each Variable. 836e82b560e649f8a68bcb252b9b002708e74d962d3John Portovoid LinearScan::scan(const SmallBitVector &RegMaskFull, bool Randomized) { 8378363a0668ce21ea0c2a61f78083b0536dbd89860Jim Stichnoth TimerMarker T(TimerStack::TT_linearScan, Func); 838d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth assert(RegMaskFull.any()); // Sanity check 839e4a8f400267b3c3b9f0cb7c4b00f8512f9fbe0a1Jim Stichnoth if (Verbose) 840e4a8f400267b3c3b9f0cb7c4b00f8512f9fbe0a1Jim Stichnoth Ctx->lockStr(); 841800dab29d19d6cc9e842fc16bfb9433018322062Jim Stichnoth Func->resetCurrentNode(); 842e6d24789bc5cc2ccadb5582ff51e5b4a5d4e2ac8Jim Stichnoth const size_t NumRegisters = RegMaskFull.size(); 843e82b560e649f8a68bcb252b9b002708e74d962d3John Porto SmallBitVector PreDefinedRegisters(NumRegisters); 844e6d24789bc5cc2ccadb5582ff51e5b4a5d4e2ac8Jim Stichnoth if (Randomized) { 845e6d24789bc5cc2ccadb5582ff51e5b4a5d4e2ac8Jim Stichnoth for (Variable *Var : UnhandledPrecolored) { 846e6d24789bc5cc2ccadb5582ff51e5b4a5d4e2ac8Jim Stichnoth PreDefinedRegisters[Var->getRegNum()] = true; 847e6d24789bc5cc2ccadb5582ff51e5b4a5d4e2ac8Jim Stichnoth } 848e6d24789bc5cc2ccadb5582ff51e5b4a5d4e2ac8Jim Stichnoth } 849d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 85087ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth // Build a LiveRange representing the Kills list. 8512a7fcbb4aa216dc4db4216a5275a3471da25f7c5Jim Stichnoth LiveRange KillsRange(Kills); 85287ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth KillsRange.untrim(); 853d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 854a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth // Reset the register use count. 855d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull RegUses.resize(NumRegisters); 856d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull std::fill(RegUses.begin(), RegUses.end(), 0); 857d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 858a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth // Unhandled is already set to all ranges in increasing order of start points. 859d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth assert(Active.empty()); 860d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth assert(Inactive.empty()); 861d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth assert(Handled.empty()); 86287ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth const TargetLowering::RegSetMask RegsInclude = 86387ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth TargetLowering::RegSet_CallerSave; 86487ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth const TargetLowering::RegSetMask RegsExclude = TargetLowering::RegSet_None; 865e82b560e649f8a68bcb252b9b002708e74d962d3John Porto const SmallBitVector KillsMask = 866bb0a5fe31a71fdc5b3292d62169f428d531437a4John Porto Target->getRegisterSet(RegsInclude, RegsExclude); 867d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 868a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth // Allocate memory once outside the loop. 869d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull IterationState Iter; 870d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.Weights.reserve(NumRegisters); 871d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.PrecoloredUnhandledMask.reserve(NumRegisters); 872d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 873d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth while (!Unhandled.empty()) { 874d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.Cur = Unhandled.back(); 875e22f823680ec21304509c1ebcee119cb843f5e76Jim Stichnoth Unhandled.pop_back(); 876d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull dumpLiveRangeTrace("\nConsidering ", Iter.Cur); 8772655d9627f11b0c97f10eacf1f730bf66e5db05bJim Stichnoth if (UseReserve) 8782655d9627f11b0c97f10eacf1f730bf66e5db05bJim Stichnoth assert(Target->getAllRegistersForVariable(Iter.Cur).any()); 8792655d9627f11b0c97f10eacf1f730bf66e5db05bJim Stichnoth else 8802655d9627f11b0c97f10eacf1f730bf66e5db05bJim Stichnoth assert(Target->getRegistersForVariable(Iter.Cur).any()); 881c59288b334b91f4c0b2edf0de7415c68c760aa12Jim Stichnoth Iter.RegMask = RegMaskFull & Target->getRegistersForVariable(Iter.Cur); 882b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth Iter.RegMaskUnfiltered = 883b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth RegMaskFull & Target->getAllRegistersForVariable(Iter.Cur); 884d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull KillsRange.trim(Iter.Cur->getLiveRange().getStart()); 885d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 886d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Check for pre-colored ranges. If Cur is pre-colored, it definitely gets 887d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // that register. Previously processed live ranges would have avoided that 888d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // register due to it being pre-colored. Future processed live ranges won't 889d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // evict that register because the live range has infinite weight. 890d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Iter.Cur->hasReg()) { 891d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull allocatePrecoloredRegister(Iter.Cur); 892d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth continue; 893d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth } 894d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 895d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull handleActiveRangeExpiredOrInactive(Iter.Cur); 896d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull handleInactiveRangeExpiredOrReactivated(Iter.Cur); 897d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 898b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth // Calculate available registers into Iter.Free[] and Iter.FreeUnfiltered[]. 899d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.Free = Iter.RegMask; 900b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth Iter.FreeUnfiltered = Iter.RegMaskUnfiltered; 901d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull for (SizeT i = 0; i < Iter.RegMask.size(); ++i) { 902b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth if (RegUses[i] > 0) { 903d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.Free[i] = false; 904b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth Iter.FreeUnfiltered[i] = false; 905b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth } 906ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth } 907ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth 908d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull findRegisterPreference(Iter); 909d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull filterFreeWithInactiveRanges(Iter); 910ad4035397bdf3484dbc12ade5f9ebd87fb5f037dJim Stichnoth 911d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Disable AllowOverlap if an Active variable, which is not Prefer, shares 912d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Prefer's register, and has a definition within Cur's live range. 913d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Iter.AllowOverlap) { 914e82b560e649f8a68bcb252b9b002708e74d962d3John Porto const auto &Aliases = *RegAliases[Iter.PreferReg]; 91570d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth for (const Variable *Item : Active) { 9168aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth const RegNumT RegNum = Item->getRegNumTmp(); 917c59288b334b91f4c0b2edf0de7415c68c760aa12Jim Stichnoth if (Item != Iter.Prefer && Aliases[RegNum] && 918d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull overlapsDefs(Func, Iter.Cur, Item)) { 919d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.AllowOverlap = false; 92070d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth dumpDisableOverlap(Func, Item, "Active"); 92170d0a054b3a2ed6ee49b2bf5d94cf52d79bbb1b9Jim Stichnoth } 922d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth } 923d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth } 924d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 925d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.Weights.resize(Iter.RegMask.size()); 926d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull std::fill(Iter.Weights.begin(), Iter.Weights.end(), RegWeight()); 927d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 928d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.PrecoloredUnhandledMask.resize(Iter.RegMask.size()); 929d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.PrecoloredUnhandledMask.reset(); 930d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 931d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull filterFreeWithPrecoloredRanges(Iter); 932d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 933b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth // Remove scratch registers from the Iter.Free[] list, and mark their 934b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth // Iter.Weights[] as infinite, if KillsRange overlaps Cur's live range. 935a3f57b9a6c7dbd3be7bf86dba697e9219c3413b2Jim Stichnoth constexpr bool UseTrimmed = true; 936d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Iter.Cur->getLiveRange().overlaps(KillsRange, UseTrimmed)) { 937d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.Free.reset(KillsMask); 938b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth Iter.FreeUnfiltered.reset(KillsMask); 9398aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth for (RegNumT i : RegNumBVIter(KillsMask)) { 940d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.Weights[i].setWeight(RegWeight::Inf); 941d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Iter.PreferReg == i) 942d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Iter.AllowOverlap = false; 94387ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth } 94487ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth } 94587ff3a186eb0e5a9ff791964e377910acceed84eJim Stichnoth 946d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth // Print info about physical register availability. 947a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth if (BuildDefs::dump() && Verbose) { 948e4a8f400267b3c3b9f0cb7c4b00f8512f9fbe0a1Jim Stichnoth Ostream &Str = Ctx->getStrDump(); 9498aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth for (RegNumT i : RegNumBVIter(Iter.RegMaskUnfiltered)) { 9508aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth Str << Target->getRegName(i, Iter.Cur->getType()) << "(U=" << RegUses[i] 9518aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth << ",F=" << Iter.Free[i] << ",P=" << Iter.PrecoloredUnhandledMask[i] 9528aa396610b7baf728631a43ea16ad3d13e38397aJim Stichnoth << ") "; 953d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth } 954d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth Str << "\n"; 955d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth } 956d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 957d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Iter.Prefer && (Iter.AllowOverlap || Iter.Free[Iter.PreferReg])) { 958a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth // First choice: a preferred register that is either free or is allowed to 959a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth // overlap with its linked variable. 960d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull allocatePreferredRegister(Iter); 961d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } else if (Iter.Free.any()) { 962d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull // Second choice: any free register. 963b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth constexpr bool Filtered = true; 964b40595a17b83cca5d11f8d056a4ac5a4d8102a84Jim Stichnoth allocateFreeRegister(Iter, Filtered); 965d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth } else { 966a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth // Fallback: there are no free registers, so we look for the lowest-weight 967a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth // register and see if Cur has higher weight. 968d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull handleNoFreeRegisters(Iter); 969d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth } 970d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth dump(Func); 971d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth } 972d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 973d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth // Move anything Active or Inactive to Handled for easier handling. 974d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Handled.insert(Handled.end(), Active.begin(), Active.end()); 975f44f371b7f3fab5683e6781873d71987e44fea2fJim Stichnoth Active.clear(); 976d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Handled.insert(Handled.end(), Inactive.begin(), Inactive.end()); 977f44f371b7f3fab5683e6781873d71987e44fea2fJim Stichnoth Inactive.clear(); 978d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth dump(Func); 979d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 980d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull assignFinalRegisters(RegMaskFull, PreDefinedRegisters, Randomized); 981d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 982e4a8f400267b3c3b9f0cb7c4b00f8512f9fbe0a1Jim Stichnoth if (Verbose) 983e4a8f400267b3c3b9f0cb7c4b00f8512f9fbe0a1Jim Stichnoth Ctx->unlockStr(); 984d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth} 985d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 986d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth// ======================== Dump routines ======================== // 987d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 988d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scullvoid LinearScan::dumpLiveRangeTrace(const char *Label, const Variable *Item) { 989d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (!BuildDefs::dump()) 990d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull return; 991d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 992d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull if (Verbose) { 993d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Ostream &Str = Ctx->getStrDump(); 994d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Str << Label; 995d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull dumpLiveRange(Item, Func); 996d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull Str << "\n"; 997d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull } 998d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull} 999d24cfda1f63f04f22118addb793b197fd3141b15Andrew Scull 1000d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnothvoid LinearScan::dump(Cfg *Func) const { 100120b71f5890ee8651983b126c5978594a01e0af96Jim Stichnoth if (!BuildDefs::dump()) 1002b6c96af1e5f019374ab93b2b66fbf79247d24660Karl Schimpf return; 1003a1da6ff9af30f2cf95b9232f9d80f35e97514221Jim Stichnoth if (!Verbose) 1004d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth return; 1005e4a8f400267b3c3b9f0cb7c4b00f8512f9fbe0a1Jim Stichnoth Ostream &Str = Func->getContext()->getStrDump(); 1006800dab29d19d6cc9e842fc16bfb9433018322062Jim Stichnoth Func->resetCurrentNode(); 1007d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth Str << "**** Current regalloc state:\n"; 1008d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth Str << "++++++ Handled:\n"; 10095ce0abb87e7134493febe99117c7a2e88d75efc4Jim Stichnoth for (const Variable *Item : Handled) { 10105ce0abb87e7134493febe99117c7a2e88d75efc4Jim Stichnoth dumpLiveRange(Item, Func); 1011d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth Str << "\n"; 1012d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth } 1013d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth Str << "++++++ Unhandled:\n"; 10147e571364bcc48d361b71c1402611873fb8544117Jim Stichnoth for (const Variable *Item : reverse_range(Unhandled)) { 10157e571364bcc48d361b71c1402611873fb8544117Jim Stichnoth dumpLiveRange(Item, Func); 1016d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth Str << "\n"; 1017d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth } 1018d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth Str << "++++++ Active:\n"; 10195ce0abb87e7134493febe99117c7a2e88d75efc4Jim Stichnoth for (const Variable *Item : Active) { 10205ce0abb87e7134493febe99117c7a2e88d75efc4Jim Stichnoth dumpLiveRange(Item, Func); 1021d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth Str << "\n"; 1022d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth } 1023d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth Str << "++++++ Inactive:\n"; 10245ce0abb87e7134493febe99117c7a2e88d75efc4Jim Stichnoth for (const Variable *Item : Inactive) { 10255ce0abb87e7134493febe99117c7a2e88d75efc4Jim Stichnoth dumpLiveRange(Item, Func); 1026d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth Str << "\n"; 1027d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth } 1028d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth} 1029d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth 1030d97c7df5a3c94fc0d1ad42acbf79756f15682919Jim Stichnoth} // end of namespace Ice 1031