1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===-- StackSlotColoring.cpp - Stack slot coloring pass. -----------------===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file implements the stack slot coloring pass. 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#define DEBUG_TYPE "stackcoloring" 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "VirtRegMap.h" 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Function.h" 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Module.h" 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/Passes.h" 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/LiveIntervalAnalysis.h" 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/LiveStackAnalysis.h" 21894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/MachineFrameInfo.h" 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/MachineInstrBuilder.h" 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/MachineLoopInfo.h" 24894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/MachineMemOperand.h" 25894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/MachineRegisterInfo.h" 26894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/PseudoSourceValue.h" 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/CommandLine.h" 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/Debug.h" 29894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Target/TargetInstrInfo.h" 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Target/TargetMachine.h" 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/BitVector.h" 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/SmallSet.h" 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/SmallVector.h" 34894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/Statistic.h" 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <vector> 36894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanusing namespace llvm; 37894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 38894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic cl::opt<bool> 39894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanDisableSharing("no-stack-slot-sharing", 40894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman cl::init(false), cl::Hidden, 41894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman cl::desc("Suppress slot sharing during stack coloring")); 42894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 43894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic cl::opt<bool> 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanColorWithRegsOpt("color-ss-with-regs", 45894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman cl::init(false), cl::Hidden, 46894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman cl::desc("Color stack slots with free registers")); 47894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 48894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic cl::opt<int> DCELimit("ssc-dce-limit", cl::init(-1), cl::Hidden); 50894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 51894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanSTATISTIC(NumEliminated, "Number of stack slots eliminated due to coloring"); 52894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanSTATISTIC(NumRegRepl, "Number of stack slot refs replaced with reg refs"); 53894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanSTATISTIC(NumLoadElim, "Number of loads eliminated"); 54894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanSTATISTIC(NumStoreElim, "Number of stores eliminated"); 55894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanSTATISTIC(NumDead, "Number of trivially dead stack accesses eliminated"); 56894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 57894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumannamespace { 58894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class StackSlotColoring : public MachineFunctionPass { 59894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool ColorWithRegs; 60894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LiveStacks* LS; 61894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman VirtRegMap* VRM; 62894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineFrameInfo *MFI; 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineRegisterInfo *MRI; 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const TargetInstrInfo *TII; 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const TargetRegisterInfo *TRI; 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const MachineLoopInfo *loopInfo; 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // SSIntervals - Spill slot intervals. 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::vector<LiveInterval*> SSIntervals; 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // SSRefs - Keep a list of frame index references for each spill slot. 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<SmallVector<MachineInstr*, 8>, 16> SSRefs; 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 74894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // OrigAlignments - Alignments of stack objects before coloring. 75894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<unsigned, 16> OrigAlignments; 76894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // OrigSizes - Sizess of stack objects before coloring. 78894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<unsigned, 16> OrigSizes; 79894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 80894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // AllColors - If index is set, it's a spill slot, i.e. color. 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // FIXME: This assumes PEI locate spill slot with smaller indices 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // closest to stack pointer / frame pointer. Therefore, smaller 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // index == better color. 84894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BitVector AllColors; 85894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 86894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // NextColor - Next "color" that's not yet used. 87894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int NextColor; 88894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 89894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // UsedColors - "Colors" that have been assigned. 90894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BitVector UsedColors; 91894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 92894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Assignments - Color to intervals mapping. 93894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<SmallVector<LiveInterval*,4>, 16> Assignments; 94894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 95894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman public: 96894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static char ID; // Pass identification 97894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman StackSlotColoring() : 9819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineFunctionPass(ID), ColorWithRegs(false), NextColor(-1) { 9919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman initializeStackSlotColoringPass(*PassRegistry::getPassRegistry()); 10019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman StackSlotColoring(bool RegColor) : 10219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineFunctionPass(ID), ColorWithRegs(RegColor), NextColor(-1) { 10319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman initializeStackSlotColoringPass(*PassRegistry::getPassRegistry()); 10419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 106894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual void getAnalysisUsage(AnalysisUsage &AU) const { 107894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AU.setPreservesCFG(); 108894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AU.addRequired<SlotIndexes>(); 109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AU.addPreserved<SlotIndexes>(); 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AU.addRequired<LiveStacks>(); 111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AU.addRequired<VirtRegMap>(); 112894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AU.addPreserved<VirtRegMap>(); 113894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AU.addRequired<MachineLoopInfo>(); 114894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AU.addPreserved<MachineLoopInfo>(); 115894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AU.addPreservedID(MachineDominatorsID); 116894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineFunctionPass::getAnalysisUsage(AU); 117894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 118894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 119894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual bool runOnMachineFunction(MachineFunction &MF); 120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual const char* getPassName() const { 121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return "Stack Slot Coloring"; 122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 124894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman private: 125894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void InitializeSlots(); 126894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void ScanForSpillSlotRefs(MachineFunction &MF); 127894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool OverlapWithAssignments(LiveInterval *li, int Color) const; 128894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int ColorSlot(LiveInterval *li); 129894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool ColorSlots(MachineFunction &MF); 130894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool ColorSlotsWithFreeRegs(SmallVector<int, 16> &SlotMapping, 131894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<SmallVector<int, 4>, 16> &RevMap, 132894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BitVector &SlotIsReg); 133894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void RewriteInstruction(MachineInstr *MI, int OldFI, int NewFI, 134894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineFunction &MF); 135894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool PropagateBackward(MachineBasicBlock::iterator MII, 136894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock *MBB, 137894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned OldReg, unsigned NewReg); 138894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool PropagateForward(MachineBasicBlock::iterator MII, 139894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock *MBB, 140894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned OldReg, unsigned NewReg); 141894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void UnfoldAndRewriteInstruction(MachineInstr *MI, int OldFI, 142894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Reg, const TargetRegisterClass *RC, 143894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallSet<unsigned, 4> &Defs, 144894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineFunction &MF); 145894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool AllMemRefsCanBeUnfolded(int SS); 146894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool RemoveDeadStores(MachineBasicBlock* MBB); 147894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 148894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} // end anonymous namespace 149894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 150894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanchar StackSlotColoring::ID = 0; 151894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 15219bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_BEGIN(StackSlotColoring, "stack-slot-coloring", 15319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Stack Slot Coloring", false, false) 15419bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_DEPENDENCY(SlotIndexes) 15519bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_DEPENDENCY(LiveStacks) 15619bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_DEPENDENCY(VirtRegMap) 15719bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 15819bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_END(StackSlotColoring, "stack-slot-coloring", 15919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Stack Slot Coloring", false, false) 160894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 161894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanFunctionPass *llvm::createStackSlotColoringPass(bool RegColor) { 162894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return new StackSlotColoring(RegColor); 163894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 164894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 165894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumannamespace { 166894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // IntervalSorter - Comparison predicate that sort live intervals by 167894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // their weight. 168894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman struct IntervalSorter { 169894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool operator()(LiveInterval* LHS, LiveInterval* RHS) const { 170894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return LHS->weight > RHS->weight; 171894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 172894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 173894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 174894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 175894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// ScanForSpillSlotRefs - Scan all the machine instructions for spill slot 176894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// references and update spill slot weights. 177894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid StackSlotColoring::ScanForSpillSlotRefs(MachineFunction &MF) { 178894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SSRefs.resize(MFI->getObjectIndexEnd()); 179894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 180894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // FIXME: Need the equivalent of MachineRegisterInfo for frameindex operands. 181894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end(); 182894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MBBI != E; ++MBBI) { 183894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock *MBB = &*MBBI; 184894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned loopDepth = loopInfo->getLoopDepth(MBB); 185894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (MachineBasicBlock::iterator MII = MBB->begin(), EE = MBB->end(); 186894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MII != EE; ++MII) { 187894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineInstr *MI = &*MII; 188894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 189894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineOperand &MO = MI->getOperand(i); 190894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!MO.isFI()) 191894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 192894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int FI = MO.getIndex(); 193894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (FI < 0) 194894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 195894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!LS->hasInterval(FI)) 196894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 197894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LiveInterval &li = LS->getInterval(FI); 198894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!MI->isDebugValue()) 199894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman li.weight += LiveIntervals::getSpillWeight(false, true, loopDepth); 200894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SSRefs[FI].push_back(MI); 201894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 202894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 203894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 204894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 205894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 206894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// InitializeSlots - Process all spill stack slot liveintervals and add them 207894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// to a sorted (by weight) list. 208894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid StackSlotColoring::InitializeSlots() { 209894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int LastFI = MFI->getObjectIndexEnd(); 210894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OrigAlignments.resize(LastFI); 211894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OrigSizes.resize(LastFI); 212894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AllColors.resize(LastFI); 213894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman UsedColors.resize(LastFI); 214894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Assignments.resize(LastFI); 215894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 216894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Gather all spill slots into a list. 217894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "Spill slot intervals:\n"); 218894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (LiveStacks::iterator i = LS->begin(), e = LS->end(); i != e; ++i) { 219894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LiveInterval &li = i->second; 220894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(li.dump()); 22119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman int FI = TargetRegisterInfo::stackSlot2Index(li.reg); 222894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MFI->isDeadObjectIndex(FI)) 223894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 224894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SSIntervals.push_back(&li); 225894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OrigAlignments[FI] = MFI->getObjectAlignment(FI); 226894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OrigSizes[FI] = MFI->getObjectSize(FI); 227894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AllColors.set(FI); 228894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 229894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << '\n'); 230894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 231894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Sort them by weight. 232894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter()); 233894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 234894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Get first "color". 235894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NextColor = AllColors.find_first(); 236894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 237894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 238894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// OverlapWithAssignments - Return true if LiveInterval overlaps with any 239894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// LiveIntervals that have already been assigned to the specified color. 240894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool 241894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanStackSlotColoring::OverlapWithAssignments(LiveInterval *li, int Color) const { 242894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const SmallVector<LiveInterval*,4> &OtherLIs = Assignments[Color]; 243894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = OtherLIs.size(); i != e; ++i) { 244894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LiveInterval *OtherLI = OtherLIs[i]; 245894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (OtherLI->overlaps(*li)) 246894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 247894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 248894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 249894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 250894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 251894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// ColorSlotsWithFreeRegs - If there are any free registers available, try 252894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// replacing spill slots references with registers instead. 253894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool 254894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanStackSlotColoring::ColorSlotsWithFreeRegs(SmallVector<int, 16> &SlotMapping, 255894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<SmallVector<int, 4>, 16> &RevMap, 256894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BitVector &SlotIsReg) { 257894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!(ColorWithRegs || ColorWithRegsOpt) || !VRM->HasUnusedRegisters()) 258894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 259894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 260894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool Changed = false; 261894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "Assigning unused registers to spill slots:\n"); 262894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) { 263894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LiveInterval *li = SSIntervals[i]; 26419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman int SS = TargetRegisterInfo::stackSlot2Index(li->reg); 265894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!UsedColors[SS] || li->weight < 20) 266894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the weight is < 20, i.e. two references in a loop with depth 1, 267894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // don't bother with it. 268894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 269894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 270894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // These slots allow to share the same registers. 271894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool AllColored = true; 272894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<unsigned, 4> ColoredRegs; 273894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned j = 0, ee = RevMap[SS].size(); j != ee; ++j) { 274894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int RSS = RevMap[SS][j]; 275894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const TargetRegisterClass *RC = LS->getIntervalRegClass(RSS); 276894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If it's not colored to another stack slot, try coloring it 277894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // to a "free" register. 278894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!RC) { 279894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AllColored = false; 280894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 281894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 282894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Reg = VRM->getFirstUnusedRegister(RC); 283894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!Reg) { 284894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AllColored = false; 285894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 286894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 287894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!AllMemRefsCanBeUnfolded(RSS)) { 288894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AllColored = false; 289894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 290894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 291894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "Assigning fi#" << RSS << " to " 292894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman << TRI->getName(Reg) << '\n'); 293894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ColoredRegs.push_back(Reg); 294894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SlotMapping[RSS] = Reg; 295894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SlotIsReg.set(RSS); 296894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed = true; 297894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 298894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 299894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 300894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Register and its sub-registers are no longer free. 301894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (!ColoredRegs.empty()) { 302894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Reg = ColoredRegs.back(); 303894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ColoredRegs.pop_back(); 304894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman VRM->setRegisterUsed(Reg); 305894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If reg is a callee-saved register, it will have to be spilled in 306894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the prologue. 307894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MRI->setPhysRegUsed(Reg); 308894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 309894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman VRM->setRegisterUsed(*AS); 310894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MRI->setPhysRegUsed(*AS); 311894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 312894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 313894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // This spill slot is dead after the rewrites 314894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (AllColored) { 315894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MFI->RemoveStackObject(SS); 316894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumEliminated; 317894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 318894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 319894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << '\n'); 320894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 321894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Changed; 322894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 323894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 324894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// ColorSlot - Assign a "color" (stack slot) to the specified stack slot. 325894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 326894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanint StackSlotColoring::ColorSlot(LiveInterval *li) { 327894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int Color = -1; 328894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool Share = false; 329894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!DisableSharing) { 330894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check if it's possible to reuse any of the used colors. 331894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Color = UsedColors.find_first(); 332894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (Color != -1) { 333894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!OverlapWithAssignments(li, Color)) { 334894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Share = true; 335894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumEliminated; 336894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 337894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 338894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Color = UsedColors.find_next(Color); 339894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 340894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 341894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 342894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Assign it to the first available color (assumed to be the best) if it's 343894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // not possible to share a used color with other objects. 344894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!Share) { 345894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(NextColor != -1 && "No more spill slots?"); 346894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Color = NextColor; 347894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman UsedColors.set(Color); 348894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NextColor = AllColors.find_next(NextColor); 349894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 350894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 351894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Record the assignment. 352894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Assignments[Color].push_back(li); 35319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman int FI = TargetRegisterInfo::stackSlot2Index(li->reg); 354894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "Assigning fi#" << FI << " to fi#" << Color << "\n"); 355894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 356894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Change size and alignment of the allocated slot. If there are multiple 357894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // objects sharing the same slot, then make sure the size and alignment 358894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // are large enough for all. 359894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Align = OrigAlignments[FI]; 360894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!Share || Align > MFI->getObjectAlignment(Color)) 361894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MFI->setObjectAlignment(Color, Align); 362894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int64_t Size = OrigSizes[FI]; 363894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!Share || Size > MFI->getObjectSize(Color)) 364894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MFI->setObjectSize(Color, Size); 365894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Color; 366894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 367894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 368894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Colorslots - Color all spill stack slots and rewrite all frameindex machine 369894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// operands in the function. 370894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool StackSlotColoring::ColorSlots(MachineFunction &MF) { 371894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NumObjs = MFI->getObjectIndexEnd(); 372894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<int, 16> SlotMapping(NumObjs, -1); 373894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<float, 16> SlotWeights(NumObjs, 0.0); 374894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<SmallVector<int, 4>, 16> RevMap(NumObjs); 375894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BitVector SlotIsReg(NumObjs); 376894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BitVector UsedColors(NumObjs); 377894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 378894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "Color spill slot intervals:\n"); 379894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool Changed = false; 380894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) { 381894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LiveInterval *li = SSIntervals[i]; 38219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman int SS = TargetRegisterInfo::stackSlot2Index(li->reg); 383894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int NewSS = ColorSlot(li); 384894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(NewSS >= 0 && "Stack coloring failed?"); 385894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SlotMapping[SS] = NewSS; 386894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RevMap[NewSS].push_back(SS); 387894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SlotWeights[NewSS] += li->weight; 388894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman UsedColors.set(NewSS); 389894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed |= (SS != NewSS); 390894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 391894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 392894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "\nSpill slots after coloring:\n"); 393894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) { 394894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LiveInterval *li = SSIntervals[i]; 39519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman int SS = TargetRegisterInfo::stackSlot2Index(li->reg); 396894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman li->weight = SlotWeights[SS]; 397894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 398894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Sort them by new weight. 399894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::stable_sort(SSIntervals.begin(), SSIntervals.end(), IntervalSorter()); 400894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 401894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#ifndef NDEBUG 402894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = SSIntervals.size(); i != e; ++i) 403894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(SSIntervals[i]->dump()); 404894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << '\n'); 405894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#endif 406894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 407894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Can we "color" a stack slot with a unused register? 408894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed |= ColorSlotsWithFreeRegs(SlotMapping, RevMap, SlotIsReg); 409894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 410894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!Changed) 411894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 412894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 413894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Rewrite all MO_FrameIndex operands. 414894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<SmallSet<unsigned, 4>, 4> NewDefs(MF.getNumBlockIDs()); 415894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned SS = 0, SE = SSRefs.size(); SS != SE; ++SS) { 416894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isReg = SlotIsReg[SS]; 417894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int NewFI = SlotMapping[SS]; 418894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (NewFI == -1 || (NewFI == (int)SS && !isReg)) 419894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 420894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 421894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const TargetRegisterClass *RC = LS->getIntervalRegClass(SS); 422894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<MachineInstr*, 8> &RefMIs = SSRefs[SS]; 423894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = RefMIs.size(); i != e; ++i) 424894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!isReg) 425894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RewriteInstruction(RefMIs[i], SS, NewFI, MF); 426894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else { 427894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Rewrite to use a register instead. 428894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned MBBId = RefMIs[i]->getParent()->getNumber(); 429894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallSet<unsigned, 4> &Defs = NewDefs[MBBId]; 430894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman UnfoldAndRewriteInstruction(RefMIs[i], SS, NewFI, RC, Defs, MF); 431894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 432894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 433894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 434894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Delete unused stack slots. 435894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (NextColor != -1) { 436894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "Removing unused stack object fi#" << NextColor << "\n"); 437894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MFI->RemoveStackObject(NextColor); 438894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NextColor = AllColors.find_next(NextColor); 439894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 440894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 441894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 442894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 443894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 444894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// AllMemRefsCanBeUnfolded - Return true if all references of the specified 445894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// spill slot index can be unfolded. 446894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool StackSlotColoring::AllMemRefsCanBeUnfolded(int SS) { 447894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<MachineInstr*, 8> &RefMIs = SSRefs[SS]; 448894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = RefMIs.size(); i != e; ++i) { 449894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineInstr *MI = RefMIs[i]; 450894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (TII->isLoadFromStackSlot(MI, SS) || 451894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TII->isStoreToStackSlot(MI, SS)) 452894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Restore and spill will become copies. 453894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 454894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!TII->getOpcodeAfterMemoryUnfold(MI->getOpcode(), false, false)) 455894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 456894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 457894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineOperand &MO = MI->getOperand(j); 458894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MO.isFI() && MO.getIndex() != SS) 459894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If it uses another frameindex, we can, currently* unfold it. 460894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 461894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 462894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 463894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 464894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 465894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 466894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// RewriteInstruction - Rewrite specified instruction by replacing references 467894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// to old frame index with new one. 468894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid StackSlotColoring::RewriteInstruction(MachineInstr *MI, int OldFI, 469894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int NewFI, MachineFunction &MF) { 470894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Update the operands. 471894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, ee = MI->getNumOperands(); i != ee; ++i) { 472894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineOperand &MO = MI->getOperand(i); 473894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!MO.isFI()) 474894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 475894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int FI = MO.getIndex(); 476894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (FI != OldFI) 477894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 478894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MO.setIndex(NewFI); 479894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 480894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 481894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Update the memory references. This changes the MachineMemOperands 482894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // directly. They may be in use by multiple instructions, however all 483894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // instructions using OldFI are being rewritten to use NewFI. 484894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const Value *OldSV = PseudoSourceValue::getFixedStack(OldFI); 485894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const Value *NewSV = PseudoSourceValue::getFixedStack(NewFI); 486894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (MachineInstr::mmo_iterator I = MI->memoperands_begin(), 487894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman E = MI->memoperands_end(); I != E; ++I) 488894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if ((*I)->getValue() == OldSV) 489894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (*I)->setValue(NewSV); 490894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 491894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 492894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// PropagateBackward - Traverse backward and look for the definition of 493894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// OldReg. If it can successfully update all of the references with NewReg, 494894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// do so and return true. 495894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool StackSlotColoring::PropagateBackward(MachineBasicBlock::iterator MII, 496894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock *MBB, 497894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned OldReg, unsigned NewReg) { 498894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MII == MBB->begin()) 499894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 500894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 501894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<MachineOperand*, 4> Uses; 502894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<MachineOperand*, 4> Refs; 503894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (--MII != MBB->begin()) { 504894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool FoundDef = false; // Not counting 2address def. 505894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 506894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Uses.clear(); 50719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MCInstrDesc &MCID = MII->getDesc(); 508894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) { 509894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineOperand &MO = MII->getOperand(i); 510894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!MO.isReg()) 511894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 512894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Reg = MO.getReg(); 513894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Reg == 0) 514894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 515894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Reg == OldReg) { 516894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MO.isImplicit()) 517894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 518894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 519894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Abort the use is actually a sub-register def. We don't have enough 520894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // information to figure out if it is really legal. 521894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MO.getSubReg() || MII->isSubregToReg()) 522894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 523894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 52419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetRegisterClass *RC = TII->getRegClass(MCID, i, TRI); 525894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (RC && !RC->contains(NewReg)) 526894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 527894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 528894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MO.isUse()) { 529894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Uses.push_back(&MO); 530894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 531894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Refs.push_back(&MO); 532894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!MII->isRegTiedToUseOperand(i)) 533894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman FoundDef = true; 534894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 535894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else if (TRI->regsOverlap(Reg, NewReg)) { 536894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 537894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else if (TRI->regsOverlap(Reg, OldReg)) { 538894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!MO.isUse() || !MO.isKill()) 539894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 540894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 541894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 542894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 543894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (FoundDef) { 544894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Found non-two-address def. Stop here. 545894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = Refs.size(); i != e; ++i) 546894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Refs[i]->setReg(NewReg); 547894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 548894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 549894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 550894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Two-address uses must be updated as well. 551894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = Uses.size(); i != e; ++i) 552894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Refs.push_back(Uses[i]); 553894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 554894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 555894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 556894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 557894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// PropagateForward - Traverse forward and look for the kill of OldReg. If 558894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// it can successfully update all of the uses with NewReg, do so and 559894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// return true. 560894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool StackSlotColoring::PropagateForward(MachineBasicBlock::iterator MII, 561894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock *MBB, 562894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned OldReg, unsigned NewReg) { 563894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MII == MBB->end()) 564894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 565894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 566894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<MachineOperand*, 4> Uses; 567894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (++MII != MBB->end()) { 568894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool FoundKill = false; 56919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MCInstrDesc &MCID = MII->getDesc(); 570894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) { 571894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineOperand &MO = MII->getOperand(i); 572894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!MO.isReg()) 573894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 574894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Reg = MO.getReg(); 575894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Reg == 0) 576894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 577894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Reg == OldReg) { 578894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MO.isDef() || MO.isImplicit()) 579894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 580894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 581894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Abort the use is actually a sub-register use. We don't have enough 582894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // information to figure out if it is really legal. 583894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MO.getSubReg()) 584894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 585894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 58619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetRegisterClass *RC = TII->getRegClass(MCID, i, TRI); 587894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (RC && !RC->contains(NewReg)) 588894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 589894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MO.isKill()) 590894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman FoundKill = true; 591894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 592894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Uses.push_back(&MO); 593894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else if (TRI->regsOverlap(Reg, NewReg) || 594894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TRI->regsOverlap(Reg, OldReg)) 595894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 596894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 597894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (FoundKill) { 598894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = Uses.size(); i != e; ++i) 599894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Uses[i]->setReg(NewReg); 600894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 601894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 602894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 603894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 604894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 605894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 606894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// UnfoldAndRewriteInstruction - Rewrite specified instruction by unfolding 607894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// folded memory references and replacing those references with register 608894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// references instead. 609894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid 610894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanStackSlotColoring::UnfoldAndRewriteInstruction(MachineInstr *MI, int OldFI, 611894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Reg, 612894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const TargetRegisterClass *RC, 613894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallSet<unsigned, 4> &Defs, 614894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineFunction &MF) { 615894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock *MBB = MI->getParent(); 616894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (unsigned DstReg = TII->isLoadFromStackSlot(MI, OldFI)) { 617894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (PropagateForward(MI, MBB, DstReg, Reg)) { 618894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "Eliminated load: "); 619894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(MI->dump()); 620894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumLoadElim; 621894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 622894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(TargetOpcode::COPY), 623894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DstReg).addReg(Reg); 624894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumRegRepl; 625894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 626894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 627894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!Defs.count(Reg)) { 628894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this is the first use of Reg in this MBB and it wasn't previously 629894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // defined in MBB, add it to livein. 630894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MBB->addLiveIn(Reg); 631894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Defs.insert(Reg); 632894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 633894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else if (unsigned SrcReg = TII->isStoreToStackSlot(MI, OldFI)) { 634894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MI->killsRegister(SrcReg) && PropagateBackward(MI, MBB, SrcReg, Reg)) { 635894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(dbgs() << "Eliminated store: "); 636894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG(MI->dump()); 637894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumStoreElim; 638894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 639894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(TargetOpcode::COPY), Reg) 640894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman .addReg(SrcReg); 641894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumRegRepl; 642894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 643894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 644894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Remember reg has been defined in MBB. 645894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Defs.insert(Reg); 646894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 647894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<MachineInstr*, 4> NewMIs; 648894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool Success = TII->unfoldMemoryOperand(MF, MI, Reg, false, false, NewMIs); 64919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (void)Success; // Silence compiler warning. 650894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Success && "Failed to unfold!"); 651894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineInstr *NewMI = NewMIs[0]; 652894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MBB->insert(MI, NewMI); 653894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumRegRepl; 654894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 655894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (NewMI->readsRegister(Reg)) { 656894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!Defs.count(Reg)) 657894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this is the first use of Reg in this MBB and it wasn't previously 658894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // defined in MBB, add it to livein. 659894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MBB->addLiveIn(Reg); 660894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Defs.insert(Reg); 661894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 662894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 663894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MBB->erase(MI); 664894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 665894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 666894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// RemoveDeadStores - Scan through a basic block and look for loads followed 667894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// by stores. If they're both using the same stack slot, then the store is 668894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// definitely dead. This could obviously be much more aggressive (consider 669894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// pairs with instructions between them), but such extensions might have a 670894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// considerable compile time impact. 671894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool StackSlotColoring::RemoveDeadStores(MachineBasicBlock* MBB) { 672894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // FIXME: This could be much more aggressive, but we need to investigate 673894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the compile time impact of doing so. 674894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool changed = false; 675894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 676894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<MachineInstr*, 4> toErase; 677894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 678894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 679894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I != E; ++I) { 680894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (DCELimit != -1 && (int)NumDead >= DCELimit) 681894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 682894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 683894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock::iterator NextMI = llvm::next(I); 684894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (NextMI == MBB->end()) continue; 685894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 686894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int FirstSS, SecondSS; 687894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned LoadReg = 0; 688894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned StoreReg = 0; 689894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!(LoadReg = TII->isLoadFromStackSlot(I, FirstSS))) continue; 690894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!(StoreReg = TII->isStoreToStackSlot(NextMI, SecondSS))) continue; 691894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (FirstSS != SecondSS || LoadReg != StoreReg || FirstSS == -1) continue; 692894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 693894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumDead; 694894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman changed = true; 695894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 696894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (NextMI->findRegisterUseOperandIdx(LoadReg, true, 0) != -1) { 697894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++NumDead; 698894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman toErase.push_back(I); 699894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 700894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 701894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman toErase.push_back(NextMI); 702894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++I; 703894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 704894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 705894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (SmallVector<MachineInstr*, 4>::iterator I = toErase.begin(), 706894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman E = toErase.end(); I != E; ++I) 707894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (*I)->eraseFromParent(); 708894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 709894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return changed; 710894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 711894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 712894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 713894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool StackSlotColoring::runOnMachineFunction(MachineFunction &MF) { 714894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DEBUG({ 715894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << "********** Stack Slot Coloring **********\n" 716894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman << "********** Function: " 717894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman << MF.getFunction()->getName() << '\n'; 718894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }); 719894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 720894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MFI = MF.getFrameInfo(); 721894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MRI = &MF.getRegInfo(); 722894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TII = MF.getTarget().getInstrInfo(); 723894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TRI = MF.getTarget().getRegisterInfo(); 724894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LS = &getAnalysis<LiveStacks>(); 725894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman VRM = &getAnalysis<VirtRegMap>(); 726894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman loopInfo = &getAnalysis<MachineLoopInfo>(); 727894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 728894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool Changed = false; 729894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 730894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NumSlots = LS->getNumIntervals(); 731894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (NumSlots < 2) { 732894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (NumSlots == 0 || !VRM->HasUnusedRegisters()) 733894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Nothing to do! 734894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 735894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 736894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 737894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If there are calls to setjmp or sigsetjmp, don't perform stack slot 738894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // coloring. The stack could be modified before the longjmp is executed, 739894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // resulting in the wrong value being used afterwards. (See 740894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // <rdar://problem/8007500>.) 741894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MF.callsSetJmp()) 742894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 743894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 744894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Gather spill slot references 745894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ScanForSpillSlotRefs(MF); 746894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman InitializeSlots(); 747894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed = ColorSlots(MF); 748894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 749894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NextColor = -1; 750894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SSIntervals.clear(); 751894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = SSRefs.size(); i != e; ++i) 752894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SSRefs[i].clear(); 753894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SSRefs.clear(); 754894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OrigAlignments.clear(); 755894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OrigSizes.clear(); 756894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AllColors.clear(); 757894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman UsedColors.clear(); 758894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = Assignments.size(); i != e; ++i) 759894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Assignments[i].clear(); 760894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Assignments.clear(); 761894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 762894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Changed) { 763894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 764894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Changed |= RemoveDeadStores(I); 765894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 766894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 767894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Changed; 768894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 769