600 lines · cpp
1//===- StackSlotColoring.cpp - Stack slot coloring pass. ------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the stack slot coloring pass.10//11//===----------------------------------------------------------------------===//12 13#include "llvm/CodeGen/StackSlotColoring.h"14#include "llvm/ADT/BitVector.h"15#include "llvm/ADT/SmallVector.h"16#include "llvm/ADT/Statistic.h"17#include "llvm/CodeGen/LiveDebugVariables.h"18#include "llvm/CodeGen/LiveInterval.h"19#include "llvm/CodeGen/LiveIntervalUnion.h"20#include "llvm/CodeGen/LiveIntervals.h"21#include "llvm/CodeGen/LiveStacks.h"22#include "llvm/CodeGen/MachineBasicBlock.h"23#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"24#include "llvm/CodeGen/MachineDominators.h"25#include "llvm/CodeGen/MachineFrameInfo.h"26#include "llvm/CodeGen/MachineFunction.h"27#include "llvm/CodeGen/MachineFunctionPass.h"28#include "llvm/CodeGen/MachineInstr.h"29#include "llvm/CodeGen/MachineMemOperand.h"30#include "llvm/CodeGen/MachineOperand.h"31#include "llvm/CodeGen/Passes.h"32#include "llvm/CodeGen/PseudoSourceValue.h"33#include "llvm/CodeGen/PseudoSourceValueManager.h"34#include "llvm/CodeGen/SlotIndexes.h"35#include "llvm/CodeGen/TargetInstrInfo.h"36#include "llvm/CodeGen/TargetSubtargetInfo.h"37#include "llvm/InitializePasses.h"38#include "llvm/Pass.h"39#include "llvm/Support/Casting.h"40#include "llvm/Support/CommandLine.h"41#include "llvm/Support/Debug.h"42#include "llvm/Support/raw_ostream.h"43#include <cassert>44#include <cstdint>45#include <iterator>46#include <vector>47 48using namespace llvm;49 50#define DEBUG_TYPE "stack-slot-coloring"51 52static cl::opt<bool>53DisableSharing("no-stack-slot-sharing",54 cl::init(false), cl::Hidden,55 cl::desc("Suppress slot sharing during stack coloring"));56 57static cl::opt<int> DCELimit("ssc-dce-limit", cl::init(-1), cl::Hidden);58 59STATISTIC(NumEliminated, "Number of stack slots eliminated due to coloring");60STATISTIC(NumDead, "Number of trivially dead stack accesses eliminated");61 62namespace {63 64class StackSlotColoring {65 MachineFrameInfo *MFI = nullptr;66 const TargetInstrInfo *TII = nullptr;67 LiveStacks *LS = nullptr;68 const MachineBlockFrequencyInfo *MBFI = nullptr;69 SlotIndexes *Indexes = nullptr;70 71 // SSIntervals - Spill slot intervals.72 std::vector<LiveInterval *> SSIntervals;73 74 // SSRefs - Keep a list of MachineMemOperands for each spill slot.75 // MachineMemOperands can be shared between instructions, so we need76 // to be careful that renames like [FI0, FI1] -> [FI1, FI2] do not77 // become FI0 -> FI1 -> FI2.78 SmallVector<SmallVector<MachineMemOperand *, 8>, 16> SSRefs;79 80 // OrigAlignments - Alignments of stack objects before coloring.81 SmallVector<Align, 16> OrigAlignments;82 83 // OrigSizes - Sizes of stack objects before coloring.84 SmallVector<unsigned, 16> OrigSizes;85 86 // AllColors - If index is set, it's a spill slot, i.e. color.87 // FIXME: This assumes PEI locate spill slot with smaller indices88 // closest to stack pointer / frame pointer. Therefore, smaller89 // index == better color. This is per stack ID.90 SmallVector<BitVector, 2> AllColors;91 92 // NextColor - Next "color" that's not yet used. This is per stack ID.93 SmallVector<int, 2> NextColors = {-1};94 95 // UsedColors - "Colors" that have been assigned. This is per stack ID96 SmallVector<BitVector, 2> UsedColors;97 98 // Join all intervals sharing one color into a single LiveIntervalUnion to99 // speedup range overlap test.100 class ColorAssignmentInfo {101 // Single liverange (used to avoid creation of LiveIntervalUnion).102 LiveInterval *SingleLI = nullptr;103 // LiveIntervalUnion to perform overlap test.104 LiveIntervalUnion *LIU = nullptr;105 // LiveIntervalUnion has a parameter in its constructor so doing this106 // dirty magic.107 uint8_t LIUPad[sizeof(LiveIntervalUnion)];108 109 public:110 ~ColorAssignmentInfo() {111 if (LIU)112 LIU->~LiveIntervalUnion(); // Dirty magic again.113 }114 115 // Return true if LiveInterval overlaps with any116 // intervals that have already been assigned to this color.117 bool overlaps(LiveInterval *LI) const {118 if (LIU)119 return LiveIntervalUnion::Query(*LI, *LIU).checkInterference();120 return SingleLI ? SingleLI->overlaps(*LI) : false;121 }122 123 // Add new LiveInterval to this color.124 void add(LiveInterval *LI, LiveIntervalUnion::Allocator &Alloc) {125 assert(!overlaps(LI));126 if (LIU) {127 LIU->unify(*LI, *LI);128 } else if (SingleLI) {129 LIU = new (LIUPad) LiveIntervalUnion(Alloc);130 LIU->unify(*SingleLI, *SingleLI);131 LIU->unify(*LI, *LI);132 SingleLI = nullptr;133 } else134 SingleLI = LI;135 }136 };137 138 LiveIntervalUnion::Allocator LIUAlloc;139 140 // Assignments - Color to intervals mapping.141 SmallVector<ColorAssignmentInfo, 16> Assignments;142 143public:144 StackSlotColoring(MachineFunction &MF, LiveStacks *LS,145 MachineBlockFrequencyInfo *MBFI, SlotIndexes *Indexes)146 : MFI(&MF.getFrameInfo()), TII(MF.getSubtarget().getInstrInfo()), LS(LS),147 MBFI(MBFI), Indexes(Indexes) {}148 bool run(MachineFunction &MF);149 150private:151 void InitializeSlots();152 void ScanForSpillSlotRefs(MachineFunction &MF);153 int ColorSlot(LiveInterval *li);154 bool ColorSlots(MachineFunction &MF);155 void RewriteInstruction(MachineInstr &MI, SmallVectorImpl<int> &SlotMapping,156 MachineFunction &MF);157 bool RemoveDeadStores(MachineBasicBlock *MBB);158};159 160class StackSlotColoringLegacy : public MachineFunctionPass {161public:162 static char ID; // Pass identification163 164 StackSlotColoringLegacy() : MachineFunctionPass(ID) {165 initializeStackSlotColoringLegacyPass(*PassRegistry::getPassRegistry());166 }167 168 void getAnalysisUsage(AnalysisUsage &AU) const override {169 AU.setPreservesCFG();170 AU.addRequired<SlotIndexesWrapperPass>();171 AU.addPreserved<SlotIndexesWrapperPass>();172 AU.addRequired<LiveStacksWrapperLegacy>();173 AU.addRequired<MachineBlockFrequencyInfoWrapperPass>();174 AU.addPreserved<MachineBlockFrequencyInfoWrapperPass>();175 AU.addPreservedID(MachineDominatorsID);176 177 // In some Target's pipeline, register allocation (RA) might be178 // split into multiple phases based on register class. So, this pass179 // may be invoked multiple times requiring it to save these analyses to be180 // used by RA later.181 AU.addPreserved<LiveIntervalsWrapperPass>();182 AU.addPreserved<LiveDebugVariablesWrapperLegacy>();183 184 MachineFunctionPass::getAnalysisUsage(AU);185 }186 187 bool runOnMachineFunction(MachineFunction &MF) override;188};189 190} // end anonymous namespace191 192char StackSlotColoringLegacy::ID = 0;193 194char &llvm::StackSlotColoringID = StackSlotColoringLegacy::ID;195 196INITIALIZE_PASS_BEGIN(StackSlotColoringLegacy, DEBUG_TYPE,197 "Stack Slot Coloring", false, false)198INITIALIZE_PASS_DEPENDENCY(SlotIndexesWrapperPass)199INITIALIZE_PASS_DEPENDENCY(LiveStacksWrapperLegacy)200INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)201INITIALIZE_PASS_END(StackSlotColoringLegacy, DEBUG_TYPE, "Stack Slot Coloring",202 false, false)203 204namespace {205 206// IntervalSorter - Comparison predicate that sort live intervals by207// their weight.208struct IntervalSorter {209 bool operator()(LiveInterval* LHS, LiveInterval* RHS) const {210 return LHS->weight() > RHS->weight();211 }212};213 214} // end anonymous namespace215 216/// ScanForSpillSlotRefs - Scan all the machine instructions for spill slot217/// references and update spill slot weights.218void StackSlotColoring::ScanForSpillSlotRefs(MachineFunction &MF) {219 SSRefs.resize(MFI->getObjectIndexEnd());220 221 // FIXME: Need the equivalent of MachineRegisterInfo for frameindex operands.222 for (MachineBasicBlock &MBB : MF) {223 for (MachineInstr &MI : MBB) {224 for (const MachineOperand &MO : MI.operands()) {225 if (!MO.isFI())226 continue;227 int FI = MO.getIndex();228 if (FI < 0)229 continue;230 if (!LS->hasInterval(FI))231 continue;232 LiveInterval &li = LS->getInterval(FI);233 if (!MI.isDebugInstr())234 li.incrementWeight(235 LiveIntervals::getSpillWeight(false, true, MBFI, MI));236 }237 for (MachineMemOperand *MMO : MI.memoperands()) {238 if (const FixedStackPseudoSourceValue *FSV =239 dyn_cast_or_null<FixedStackPseudoSourceValue>(240 MMO->getPseudoValue())) {241 int FI = FSV->getFrameIndex();242 if (FI >= 0)243 SSRefs[FI].push_back(MMO);244 }245 }246 }247 }248}249 250/// InitializeSlots - Process all spill stack slot liveintervals and add them251/// to a sorted (by weight) list.252void StackSlotColoring::InitializeSlots() {253 int LastFI = MFI->getObjectIndexEnd();254 255 // There is always at least one stack ID.256 AllColors.resize(1);257 UsedColors.resize(1);258 259 OrigAlignments.resize(LastFI);260 OrigSizes.resize(LastFI);261 AllColors[0].resize(LastFI);262 UsedColors[0].resize(LastFI);263 Assignments.resize(LastFI);264 265 using Pair = std::iterator_traits<LiveStacks::iterator>::value_type;266 267 SmallVector<Pair *, 16> Intervals;268 269 Intervals.reserve(LS->getNumIntervals());270 for (auto &I : *LS)271 Intervals.push_back(&I);272 llvm::sort(Intervals,273 [](Pair *LHS, Pair *RHS) { return LHS->first < RHS->first; });274 275 // Gather all spill slots into a list.276 LLVM_DEBUG(dbgs() << "Spill slot intervals:\n");277 for (auto *I : Intervals) {278 LiveInterval &li = I->second;279 LLVM_DEBUG(li.dump());280 int FI = li.reg().stackSlotIndex();281 if (MFI->isDeadObjectIndex(FI))282 continue;283 284 SSIntervals.push_back(&li);285 OrigAlignments[FI] = MFI->getObjectAlign(FI);286 OrigSizes[FI] = MFI->getObjectSize(FI);287 288 auto StackID = MFI->getStackID(FI);289 if (StackID != 0) {290 if (StackID >= AllColors.size()) {291 AllColors.resize(StackID + 1);292 UsedColors.resize(StackID + 1);293 }294 AllColors[StackID].resize(LastFI);295 UsedColors[StackID].resize(LastFI);296 }297 298 AllColors[StackID].set(FI);299 }300 LLVM_DEBUG(dbgs() << '\n');301 302 // Sort them by weight.303 llvm::stable_sort(SSIntervals, IntervalSorter());304 305 NextColors.resize(AllColors.size());306 307 // Get first "color".308 for (unsigned I = 0, E = AllColors.size(); I != E; ++I)309 NextColors[I] = AllColors[I].find_first();310}311 312/// ColorSlot - Assign a "color" (stack slot) to the specified stack slot.313int StackSlotColoring::ColorSlot(LiveInterval *li) {314 int Color = -1;315 bool Share = false;316 int FI = li->reg().stackSlotIndex();317 uint8_t StackID = MFI->getStackID(FI);318 319 if (!DisableSharing) {320 321 // Check if it's possible to reuse any of the used colors.322 Color = UsedColors[StackID].find_first();323 while (Color != -1) {324 if (!Assignments[Color].overlaps(li)) {325 Share = true;326 ++NumEliminated;327 break;328 }329 Color = UsedColors[StackID].find_next(Color);330 }331 }332 333 if (Color != -1 && MFI->getStackID(Color) != MFI->getStackID(FI)) {334 LLVM_DEBUG(dbgs() << "cannot share FIs with different stack IDs\n");335 Share = false;336 }337 338 // Assign it to the first available color (assumed to be the best) if it's339 // not possible to share a used color with other objects.340 if (!Share) {341 assert(NextColors[StackID] != -1 && "No more spill slots?");342 Color = NextColors[StackID];343 UsedColors[StackID].set(Color);344 NextColors[StackID] = AllColors[StackID].find_next(NextColors[StackID]);345 }346 347 assert(MFI->getStackID(Color) == MFI->getStackID(FI));348 349 // Record the assignment.350 Assignments[Color].add(li, LIUAlloc);351 LLVM_DEBUG(dbgs() << "Assigning fi#" << FI << " to fi#" << Color << "\n");352 353 // Change size and alignment of the allocated slot. If there are multiple354 // objects sharing the same slot, then make sure the size and alignment355 // are large enough for all.356 Align Alignment = OrigAlignments[FI];357 if (!Share || Alignment > MFI->getObjectAlign(Color))358 MFI->setObjectAlignment(Color, Alignment);359 int64_t Size = OrigSizes[FI];360 if (!Share || Size > MFI->getObjectSize(Color))361 MFI->setObjectSize(Color, Size);362 return Color;363}364 365/// Colorslots - Color all spill stack slots and rewrite all frameindex machine366/// operands in the function.367bool StackSlotColoring::ColorSlots(MachineFunction &MF) {368 unsigned NumObjs = MFI->getObjectIndexEnd();369 SmallVector<int, 16> SlotMapping(NumObjs, -1);370 SmallVector<float, 16> SlotWeights(NumObjs, 0.0);371 SmallVector<SmallVector<int, 4>, 16> RevMap(NumObjs);372 BitVector UsedColors(NumObjs);373 374 LLVM_DEBUG(dbgs() << "Color spill slot intervals:\n");375 bool Changed = false;376 for (LiveInterval *li : SSIntervals) {377 int SS = li->reg().stackSlotIndex();378 int NewSS = ColorSlot(li);379 assert(NewSS >= 0 && "Stack coloring failed?");380 SlotMapping[SS] = NewSS;381 RevMap[NewSS].push_back(SS);382 SlotWeights[NewSS] += li->weight();383 UsedColors.set(NewSS);384 Changed |= (SS != NewSS);385 }386 387 LLVM_DEBUG(dbgs() << "\nSpill slots after coloring:\n");388 for (LiveInterval *li : SSIntervals) {389 int SS = li->reg().stackSlotIndex();390 li->setWeight(SlotWeights[SS]);391 }392 // Sort them by new weight.393 llvm::stable_sort(SSIntervals, IntervalSorter());394 395#ifndef NDEBUG396 for (LiveInterval *li : SSIntervals)397 LLVM_DEBUG(li->dump());398 LLVM_DEBUG(dbgs() << '\n');399#endif400 401 if (!Changed)402 return false;403 404 // Rewrite all MachineMemOperands.405 for (unsigned SS = 0, SE = SSRefs.size(); SS != SE; ++SS) {406 int NewFI = SlotMapping[SS];407 if (NewFI == -1 || (NewFI == (int)SS))408 continue;409 410 const PseudoSourceValue *NewSV = MF.getPSVManager().getFixedStack(NewFI);411 SmallVectorImpl<MachineMemOperand *> &RefMMOs = SSRefs[SS];412 for (MachineMemOperand *MMO : RefMMOs)413 MMO->setValue(NewSV);414 }415 416 // Rewrite all MO_FrameIndex operands. Look for dead stores.417 for (MachineBasicBlock &MBB : MF) {418 for (MachineInstr &MI : MBB)419 RewriteInstruction(MI, SlotMapping, MF);420 RemoveDeadStores(&MBB);421 }422 423 // Delete unused stack slots.424 for (int StackID = 0, E = AllColors.size(); StackID != E; ++StackID) {425 int NextColor = NextColors[StackID];426 while (NextColor != -1) {427 LLVM_DEBUG(dbgs() << "Removing unused stack object fi#" << NextColor << "\n");428 MFI->RemoveStackObject(NextColor);429 NextColor = AllColors[StackID].find_next(NextColor);430 }431 }432 433 return true;434}435 436/// RewriteInstruction - Rewrite specified instruction by replacing references437/// to old frame index with new one.438void StackSlotColoring::RewriteInstruction(MachineInstr &MI,439 SmallVectorImpl<int> &SlotMapping,440 MachineFunction &MF) {441 // Update the operands.442 for (MachineOperand &MO : MI.operands()) {443 if (!MO.isFI())444 continue;445 int OldFI = MO.getIndex();446 if (OldFI < 0)447 continue;448 int NewFI = SlotMapping[OldFI];449 if (NewFI == -1 || NewFI == OldFI)450 continue;451 452 assert(MFI->getStackID(OldFI) == MFI->getStackID(NewFI));453 MO.setIndex(NewFI);454 }455 456 // The MachineMemOperands have already been updated.457}458 459/// RemoveDeadStores - Scan through a basic block and look for loads followed460/// by stores. If they're both using the same stack slot, then the store is461/// definitely dead. This could obviously be much more aggressive (consider462/// pairs with instructions between them), but such extensions might have a463/// considerable compile time impact.464bool StackSlotColoring::RemoveDeadStores(MachineBasicBlock* MBB) {465 // FIXME: This could be much more aggressive, but we need to investigate466 // the compile time impact of doing so.467 bool changed = false;468 469 SmallVector<MachineInstr*, 4> toErase;470 471 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();472 I != E; ++I) {473 if (DCELimit != -1 && (int)NumDead >= DCELimit)474 break;475 int FirstSS, SecondSS;476 if (TII->isStackSlotCopy(*I, FirstSS, SecondSS) && FirstSS == SecondSS &&477 FirstSS != -1) {478 ++NumDead;479 changed = true;480 toErase.push_back(&*I);481 continue;482 }483 484 MachineBasicBlock::iterator NextMI = std::next(I);485 MachineBasicBlock::iterator ProbableLoadMI = I;486 487 Register LoadReg;488 Register StoreReg;489 TypeSize LoadSize = TypeSize::getZero();490 TypeSize StoreSize = TypeSize::getZero();491 if (!(LoadReg = TII->isLoadFromStackSlot(*I, FirstSS, LoadSize)))492 continue;493 // Skip the ...pseudo debugging... instructions between a load and store.494 while ((NextMI != E) && NextMI->isDebugInstr()) {495 ++NextMI;496 ++I;497 }498 if (NextMI == E) continue;499 if (!(StoreReg = TII->isStoreToStackSlot(*NextMI, SecondSS, StoreSize)))500 continue;501 if (FirstSS != SecondSS || LoadReg != StoreReg || FirstSS == -1 ||502 LoadSize != StoreSize || !MFI->isSpillSlotObjectIndex(FirstSS))503 continue;504 505 ++NumDead;506 changed = true;507 508 if (NextMI->findRegisterUseOperandIdx(LoadReg, /*TRI=*/nullptr, true) !=509 -1) {510 ++NumDead;511 toErase.push_back(&*ProbableLoadMI);512 }513 514 toErase.push_back(&*NextMI);515 ++I;516 }517 518 for (MachineInstr *MI : toErase) {519 if (Indexes)520 Indexes->removeMachineInstrFromMaps(*MI);521 MI->eraseFromParent();522 }523 524 return changed;525}526 527bool StackSlotColoring::run(MachineFunction &MF) {528 LLVM_DEBUG({529 dbgs() << "********** Stack Slot Coloring **********\n"530 << "********** Function: " << MF.getName() << '\n';531 });532 533 bool Changed = false;534 535 unsigned NumSlots = LS->getNumIntervals();536 if (NumSlots == 0)537 // Nothing to do!538 return false;539 540 // If there are calls to setjmp or sigsetjmp, don't perform stack slot541 // coloring. The stack could be modified before the longjmp is executed,542 // resulting in the wrong value being used afterwards.543 if (MF.exposesReturnsTwice())544 return false;545 546 // Gather spill slot references547 ScanForSpillSlotRefs(MF);548 InitializeSlots();549 Changed = ColorSlots(MF);550 551 for (int &Next : NextColors)552 Next = -1;553 554 SSIntervals.clear();555 for (auto &RefMMOs : SSRefs)556 RefMMOs.clear();557 SSRefs.clear();558 OrigAlignments.clear();559 OrigSizes.clear();560 AllColors.clear();561 UsedColors.clear();562 Assignments.clear();563 564 return Changed;565}566 567bool StackSlotColoringLegacy::runOnMachineFunction(MachineFunction &MF) {568 if (skipFunction(MF.getFunction()))569 return false;570 571 LiveStacks *LS = &getAnalysis<LiveStacksWrapperLegacy>().getLS();572 MachineBlockFrequencyInfo *MBFI =573 &getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI();574 SlotIndexes *Indexes = &getAnalysis<SlotIndexesWrapperPass>().getSI();575 StackSlotColoring Impl(MF, LS, MBFI, Indexes);576 return Impl.run(MF);577}578 579PreservedAnalyses580StackSlotColoringPass::run(MachineFunction &MF,581 MachineFunctionAnalysisManager &MFAM) {582 LiveStacks *LS = &MFAM.getResult<LiveStacksAnalysis>(MF);583 MachineBlockFrequencyInfo *MBFI =584 &MFAM.getResult<MachineBlockFrequencyAnalysis>(MF);585 SlotIndexes *Indexes = &MFAM.getResult<SlotIndexesAnalysis>(MF);586 StackSlotColoring Impl(MF, LS, MBFI, Indexes);587 bool Changed = Impl.run(MF);588 if (!Changed)589 return PreservedAnalyses::all();590 591 auto PA = getMachineFunctionPassPreservedAnalyses();592 PA.preserveSet<CFGAnalyses>();593 PA.preserve<SlotIndexesAnalysis>();594 PA.preserve<MachineBlockFrequencyAnalysis>();595 PA.preserve<MachineDominatorTreeAnalysis>();596 PA.preserve<LiveIntervalsAnalysis>();597 PA.preserve<LiveDebugVariablesAnalysis>();598 return PA;599}600