blob: ed3e159ac5667fa8b7dbdc0dc6b44a8a95271a23 [file] [log] [blame]
Eugene Zelenko900b6332017-08-29 22:32:07 +00001//===- InlineSpiller.cpp - Insert spills and restores inline --------------===//
Jakob Stoklund Olesenf8889112010-06-29 23:58:39 +00002//
Chandler Carruth2946cd72019-01-19 08:50:56 +00003// 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-exception
Jakob Stoklund Olesenf8889112010-06-29 23:58:39 +00006//
7//===----------------------------------------------------------------------===//
8//
9// The inline spiller modifies the machine function directly instead of
10// inserting spills and restores in VirtRegMap.
11//
12//===----------------------------------------------------------------------===//
13
Jakob Stoklund Olesenf8889112010-06-29 23:58:39 +000014#include "Spiller.h"
Wei Mi8c4136b2016-05-11 22:37:43 +000015#include "SplitKit.h"
Eugene Zelenko900b6332017-08-29 22:32:07 +000016#include "llvm/ADT/ArrayRef.h"
17#include "llvm/ADT/DenseMap.h"
Wei Mi9a16d652016-04-13 03:08:27 +000018#include "llvm/ADT/MapVector.h"
Eugene Zelenko900b6332017-08-29 22:32:07 +000019#include "llvm/ADT/None.h"
20#include "llvm/ADT/STLExtras.h"
Benjamin Kramerbc6666b2013-05-23 15:42:57 +000021#include "llvm/ADT/SetVector.h"
Eugene Zelenko900b6332017-08-29 22:32:07 +000022#include "llvm/ADT/SmallPtrSet.h"
23#include "llvm/ADT/SmallVector.h"
Jakob Stoklund Olesenc5a8c082011-05-05 17:22:53 +000024#include "llvm/ADT/Statistic.h"
Jakob Stoklund Olesen868dd4e2010-11-10 23:55:56 +000025#include "llvm/Analysis/AliasAnalysis.h"
Eugene Zelenko900b6332017-08-29 22:32:07 +000026#include "llvm/CodeGen/LiveInterval.h"
Matthias Braunf8422972017-12-13 02:51:04 +000027#include "llvm/CodeGen/LiveIntervals.h"
Marcello Maggioni6fc9563d2019-10-17 03:12:51 +000028#include "llvm/CodeGen/LiveRangeCalc.h"
Pete Cooper3ca96f92012-04-02 22:44:18 +000029#include "llvm/CodeGen/LiveRangeEdit.h"
Matthias Braunef959692017-12-18 23:19:44 +000030#include "llvm/CodeGen/LiveStacks.h"
Eugene Zelenko900b6332017-08-29 22:32:07 +000031#include "llvm/CodeGen/MachineBasicBlock.h"
Benjamin Kramere2a1d892013-06-17 19:00:36 +000032#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
Chandler Carruth8a8cd2b2014-01-07 11:48:04 +000033#include "llvm/CodeGen/MachineDominators.h"
Jakob Stoklund Olesenf8889112010-06-29 23:58:39 +000034#include "llvm/CodeGen/MachineFunction.h"
Eugene Zelenko900b6332017-08-29 22:32:07 +000035#include "llvm/CodeGen/MachineFunctionPass.h"
36#include "llvm/CodeGen/MachineInstr.h"
David Blaikie0252265b2013-06-16 20:34:15 +000037#include "llvm/CodeGen/MachineInstrBuilder.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000038#include "llvm/CodeGen/MachineInstrBundle.h"
Jakob Stoklund Olesena0d5ec12011-03-15 21:13:25 +000039#include "llvm/CodeGen/MachineLoopInfo.h"
Eugene Zelenko900b6332017-08-29 22:32:07 +000040#include "llvm/CodeGen/MachineOperand.h"
Jakob Stoklund Olesenf8889112010-06-29 23:58:39 +000041#include "llvm/CodeGen/MachineRegisterInfo.h"
Eugene Zelenko900b6332017-08-29 22:32:07 +000042#include "llvm/CodeGen/SlotIndexes.h"
David Blaikie3f833ed2017-11-08 01:01:31 +000043#include "llvm/CodeGen/TargetInstrInfo.h"
David Blaikieb3bde2e2017-11-17 01:07:10 +000044#include "llvm/CodeGen/TargetOpcodes.h"
45#include "llvm/CodeGen/TargetRegisterInfo.h"
46#include "llvm/CodeGen/TargetSubtargetInfo.h"
Jakob Stoklund Olesen26c9d702012-11-28 19:13:06 +000047#include "llvm/CodeGen/VirtRegMap.h"
Nico Weber432a3882018-04-30 14:59:11 +000048#include "llvm/Config/llvm-config.h"
Eugene Zelenko900b6332017-08-29 22:32:07 +000049#include "llvm/Support/BlockFrequency.h"
50#include "llvm/Support/BranchProbability.h"
Jakob Stoklund Olesenbceb9e52011-09-15 21:06:00 +000051#include "llvm/Support/CommandLine.h"
Eugene Zelenko900b6332017-08-29 22:32:07 +000052#include "llvm/Support/Compiler.h"
Jakob Stoklund Olesenf8889112010-06-29 23:58:39 +000053#include "llvm/Support/Debug.h"
Eugene Zelenko900b6332017-08-29 22:32:07 +000054#include "llvm/Support/ErrorHandling.h"
Jakob Stoklund Olesenf8889112010-06-29 23:58:39 +000055#include "llvm/Support/raw_ostream.h"
Eugene Zelenko900b6332017-08-29 22:32:07 +000056#include <cassert>
57#include <iterator>
58#include <tuple>
59#include <utility>
60#include <vector>
Jakob Stoklund Olesenf8889112010-06-29 23:58:39 +000061
62using namespace llvm;
63
Chandler Carruth1b9dde02014-04-22 02:02:50 +000064#define DEBUG_TYPE "regalloc"
65
Jakob Stoklund Olesenc5a8c082011-05-05 17:22:53 +000066STATISTIC(NumSpilledRanges, "Number of spilled live ranges");
Jakob Stoklund Olesen37eb6962011-09-15 17:54:28 +000067STATISTIC(NumSnippets, "Number of spilled snippets");
Jakob Stoklund Olesenc5a8c082011-05-05 17:22:53 +000068STATISTIC(NumSpills, "Number of spills inserted");
Jakob Stoklund Olesen37eb6962011-09-15 17:54:28 +000069STATISTIC(NumSpillsRemoved, "Number of spills removed");
Jakob Stoklund Olesenc5a8c082011-05-05 17:22:53 +000070STATISTIC(NumReloads, "Number of reloads inserted");
Jakob Stoklund Olesen37eb6962011-09-15 17:54:28 +000071STATISTIC(NumReloadsRemoved, "Number of reloads removed");
Jakob Stoklund Olesenc5a8c082011-05-05 17:22:53 +000072STATISTIC(NumFolded, "Number of folded stack accesses");
73STATISTIC(NumFoldedLoads, "Number of folded loads");
74STATISTIC(NumRemats, "Number of rematerialized defs for spilling");
Jakob Stoklund Olesenc5a8c082011-05-05 17:22:53 +000075
Jakob Stoklund Olesenbceb9e52011-09-15 21:06:00 +000076static cl::opt<bool> DisableHoisting("disable-spill-hoist", cl::Hidden,
77 cl::desc("Disable inline spill hoisting"));
Philip Reames7403fac2019-02-12 18:33:01 +000078static cl::opt<bool>
79RestrictStatepointRemat("restrict-statepoint-remat",
80 cl::init(false), cl::Hidden,
81 cl::desc("Restrict remat for statepoint operands"));
Jakob Stoklund Olesenbceb9e52011-09-15 21:06:00 +000082
Jakob Stoklund Olesenf8889112010-06-29 23:58:39 +000083namespace {
Eugene Zelenko900b6332017-08-29 22:32:07 +000084
Wei Mi963f2df2016-04-15 23:16:44 +000085class HoistSpillHelper : private LiveRangeEdit::Delegate {
86 MachineFunction &MF;
Wei Mi9a16d652016-04-13 03:08:27 +000087 LiveIntervals &LIS;
88 LiveStacks &LSS;
89 AliasAnalysis *AA;
90 MachineDominatorTree &MDT;
91 MachineLoopInfo &Loops;
92 VirtRegMap &VRM;
Wei Mi9a16d652016-04-13 03:08:27 +000093 MachineRegisterInfo &MRI;
94 const TargetInstrInfo &TII;
95 const TargetRegisterInfo &TRI;
96 const MachineBlockFrequencyInfo &MBFI;
97
Wei Mi8c4136b2016-05-11 22:37:43 +000098 InsertPointAnalysis IPA;
99
Wei Mic0d06642017-09-13 21:41:30 +0000100 // Map from StackSlot to the LiveInterval of the original register.
101 // Note the LiveInterval of the original register may have been deleted
102 // after it is spilled. We keep a copy here to track the range where
103 // spills can be moved.
104 DenseMap<int, std::unique_ptr<LiveInterval>> StackSlotToOrigLI;
Eugene Zelenko900b6332017-08-29 22:32:07 +0000105
Wei Mi9a16d652016-04-13 03:08:27 +0000106 // Map from pair of (StackSlot and Original VNI) to a set of spills which
107 // have the same stackslot and have equal values defined by Original VNI.
108 // These spills are mergeable and are hoist candiates.
Eugene Zelenko900b6332017-08-29 22:32:07 +0000109 using MergeableSpillsMap =
110 MapVector<std::pair<int, VNInfo *>, SmallPtrSet<MachineInstr *, 16>>;
Wei Mi9a16d652016-04-13 03:08:27 +0000111 MergeableSpillsMap MergeableSpills;
112
113 /// This is the map from original register to a set containing all its
114 /// siblings. To hoist a spill to another BB, we need to find out a live
115 /// sibling there and use it as the source of the new spill.
116 DenseMap<unsigned, SmallSetVector<unsigned, 16>> Virt2SiblingsMap;
117
Wei Mic0d06642017-09-13 21:41:30 +0000118 bool isSpillCandBB(LiveInterval &OrigLI, VNInfo &OrigVNI,
119 MachineBasicBlock &BB, unsigned &LiveReg);
Wei Mi9a16d652016-04-13 03:08:27 +0000120
121 void rmRedundantSpills(
122 SmallPtrSet<MachineInstr *, 16> &Spills,
123 SmallVectorImpl<MachineInstr *> &SpillsToRm,
124 DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill);
125
126 void getVisitOrders(
127 MachineBasicBlock *Root, SmallPtrSet<MachineInstr *, 16> &Spills,
128 SmallVectorImpl<MachineDomTreeNode *> &Orders,
129 SmallVectorImpl<MachineInstr *> &SpillsToRm,
130 DenseMap<MachineDomTreeNode *, unsigned> &SpillsToKeep,
131 DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill);
132
Wei Mic0d06642017-09-13 21:41:30 +0000133 void runHoistSpills(LiveInterval &OrigLI, VNInfo &OrigVNI,
Wei Mi9a16d652016-04-13 03:08:27 +0000134 SmallPtrSet<MachineInstr *, 16> &Spills,
135 SmallVectorImpl<MachineInstr *> &SpillsToRm,
136 DenseMap<MachineBasicBlock *, unsigned> &SpillsToIns);
137
138public:
139 HoistSpillHelper(MachineFunctionPass &pass, MachineFunction &mf,
140 VirtRegMap &vrm)
Wei Mi963f2df2016-04-15 23:16:44 +0000141 : MF(mf), LIS(pass.getAnalysis<LiveIntervals>()),
Wei Mi9a16d652016-04-13 03:08:27 +0000142 LSS(pass.getAnalysis<LiveStacks>()),
143 AA(&pass.getAnalysis<AAResultsWrapperPass>().getAAResults()),
144 MDT(pass.getAnalysis<MachineDominatorTree>()),
145 Loops(pass.getAnalysis<MachineLoopInfo>()), VRM(vrm),
Eugene Zelenko900b6332017-08-29 22:32:07 +0000146 MRI(mf.getRegInfo()), TII(*mf.getSubtarget().getInstrInfo()),
Wei Mi9a16d652016-04-13 03:08:27 +0000147 TRI(*mf.getSubtarget().getRegisterInfo()),
Wei Mi8c4136b2016-05-11 22:37:43 +0000148 MBFI(pass.getAnalysis<MachineBlockFrequencyInfo>()),
149 IPA(LIS, mf.getNumBlockIDs()) {}
Wei Mi9a16d652016-04-13 03:08:27 +0000150
Duncan P. N. Exon Smith91298732016-06-30 23:28:15 +0000151 void addToMergeableSpills(MachineInstr &Spill, int StackSlot,
Wei Mi9a16d652016-04-13 03:08:27 +0000152 unsigned Original);
Duncan P. N. Exon Smith91298732016-06-30 23:28:15 +0000153 bool rmFromMergeableSpills(MachineInstr &Spill, int StackSlot);
Wei Mi963f2df2016-04-15 23:16:44 +0000154 void hoistAllSpills();
155 void LRE_DidCloneVirtReg(unsigned, unsigned) override;
Wei Mi9a16d652016-04-13 03:08:27 +0000156};
157
Jakob Stoklund Olesenf8889112010-06-29 23:58:39 +0000158class InlineSpiller : public Spiller {
Jakob Stoklund Olesena00bab22011-03-14 19:56:43 +0000159 MachineFunction &MF;
160 LiveIntervals &LIS;
161 LiveStacks &LSS;
162 AliasAnalysis *AA;
Jakob Stoklund Olesena0d5ec12011-03-15 21:13:25 +0000163 MachineDominatorTree &MDT;
164 MachineLoopInfo &Loops;
Jakob Stoklund Olesena00bab22011-03-14 19:56:43 +0000165 VirtRegMap &VRM;
Jakob Stoklund Olesena00bab22011-03-14 19:56:43 +0000166 MachineRegisterInfo &MRI;
167 const TargetInstrInfo &TII;
168 const TargetRegisterInfo &TRI;
Benjamin Kramere2a1d892013-06-17 19:00:36 +0000169 const MachineBlockFrequencyInfo &MBFI;
Jakob Stoklund Olesenbde96ad2010-06-30 23:03:52 +0000170
171 // Variables that are valid during spill(), but used by multiple methods.
Jakob Stoklund Olesena00bab22011-03-14 19:56:43 +0000172 LiveRangeEdit *Edit;
Jakob Stoklund Olesene4663452011-03-26 22:16:41 +0000173 LiveInterval *StackInt;
Jakob Stoklund Olesena00bab22011-03-14 19:56:43 +0000174 int StackSlot;
Jakob Stoklund Olesena0d5ec12011-03-15 21:13:25 +0000175 unsigned Original;
Jakob Stoklund Olesenf8889112010-06-29 23:58:39 +0000176
Jakob Stoklund Olesena00bab22011-03-14 19:56:43 +0000177 // All registers to spill to StackSlot, including the main register.
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +0000178 SmallVector<unsigned, 8> RegsToSpill;
179
180 // All COPY instructions to/from snippets.
181 // They are ignored since both operands refer to the same stack slot.
182 SmallPtrSet<MachineInstr*, 8> SnippetCopies;
183
Jakob Stoklund Olesen2edaa2f2010-10-20 22:00:51 +0000184 // Values that failed to remat at some point.
Jakob Stoklund Olesena00bab22011-03-14 19:56:43 +0000185 SmallPtrSet<VNInfo*, 8> UsedValues;
Jakob Stoklund Olesen96037182010-07-02 17:44:57 +0000186
Jakob Stoklund Olesen27320cb2011-03-18 04:23:06 +0000187 // Dead defs generated during spilling.
188 SmallVector<MachineInstr*, 8> DeadDefs;
Jakob Stoklund Olesena0d5ec12011-03-15 21:13:25 +0000189
Wei Mi9a16d652016-04-13 03:08:27 +0000190 // Object records spills information and does the hoisting.
191 HoistSpillHelper HSpiller;
192
Eugene Zelenko900b6332017-08-29 22:32:07 +0000193 ~InlineSpiller() override = default;
Jakob Stoklund Olesenf8889112010-06-29 23:58:39 +0000194
195public:
Eric Christopherd9134482014-08-04 21:25:23 +0000196 InlineSpiller(MachineFunctionPass &pass, MachineFunction &mf, VirtRegMap &vrm)
197 : MF(mf), LIS(pass.getAnalysis<LiveIntervals>()),
198 LSS(pass.getAnalysis<LiveStacks>()),
Chandler Carruth7b560d42015-09-09 17:55:00 +0000199 AA(&pass.getAnalysis<AAResultsWrapperPass>().getAAResults()),
Eric Christopherd9134482014-08-04 21:25:23 +0000200 MDT(pass.getAnalysis<MachineDominatorTree>()),
201 Loops(pass.getAnalysis<MachineLoopInfo>()), VRM(vrm),
Eugene Zelenko900b6332017-08-29 22:32:07 +0000202 MRI(mf.getRegInfo()), TII(*mf.getSubtarget().getInstrInfo()),
Eric Christopherfc6de422014-08-05 02:39:49 +0000203 TRI(*mf.getSubtarget().getRegisterInfo()),
Wei Mi9a16d652016-04-13 03:08:27 +0000204 MBFI(pass.getAnalysis<MachineBlockFrequencyInfo>()),
205 HSpiller(pass, mf, vrm) {}
Jakob Stoklund Olesenf8889112010-06-29 23:58:39 +0000206
Craig Topper4584cd52014-03-07 09:26:03 +0000207 void spill(LiveRangeEdit &) override;
Wei Mi9a16d652016-04-13 03:08:27 +0000208 void postOptimization() override;
Jakob Stoklund Olesen72911e42010-10-14 23:49:52 +0000209
Jakob Stoklund Olesen96037182010-07-02 17:44:57 +0000210private:
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +0000211 bool isSnippet(const LiveInterval &SnipLI);
212 void collectRegsToSpill();
213
David Majnemer42531262016-08-12 03:55:06 +0000214 bool isRegToSpill(unsigned Reg) { return is_contained(RegsToSpill, Reg); }
Jakob Stoklund Olesen27320cb2011-03-18 04:23:06 +0000215
216 bool isSibling(unsigned Reg);
Wei Mi9a16d652016-04-13 03:08:27 +0000217 bool hoistSpillInsideBB(LiveInterval &SpillLI, MachineInstr &CopyMI);
Jakob Stoklund Olesen39488642011-03-20 05:44:55 +0000218 void eliminateRedundantSpills(LiveInterval &LI, VNInfo *VNI);
Jakob Stoklund Olesen27320cb2011-03-18 04:23:06 +0000219
Jakob Stoklund Olesend8af5292011-03-29 03:12:02 +0000220 void markValueUsed(LiveInterval*, VNInfo*);
Philip Reames7403fac2019-02-12 18:33:01 +0000221 bool canGuaranteeAssignmentAfterRemat(unsigned VReg, MachineInstr &MI);
Duncan P. N. Exon Smithd6ebd072016-02-27 20:23:14 +0000222 bool reMaterializeFor(LiveInterval &, MachineInstr &MI);
Jakob Stoklund Olesen96037182010-07-02 17:44:57 +0000223 void reMaterializeAll();
224
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +0000225 bool coalesceStackAccess(MachineInstr *MI, unsigned Reg);
Eugene Zelenko900b6332017-08-29 22:32:07 +0000226 bool foldMemoryOperand(ArrayRef<std::pair<MachineInstr *, unsigned>>,
Craig Topperc0196b12014-04-14 00:51:57 +0000227 MachineInstr *LoadMI = nullptr);
Mark Lacey9d8103d2013-08-14 23:50:16 +0000228 void insertReload(unsigned VReg, SlotIndex, MachineBasicBlock::iterator MI);
229 void insertSpill(unsigned VReg, bool isKill, MachineBasicBlock::iterator MI);
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +0000230
231 void spillAroundUses(unsigned Reg);
Jakob Stoklund Olesene991f722011-03-29 21:20:19 +0000232 void spillAll();
Jakob Stoklund Olesenf8889112010-06-29 23:58:39 +0000233};
Jakob Stoklund Olesenf8889112010-06-29 23:58:39 +0000234
Eugene Zelenko900b6332017-08-29 22:32:07 +0000235} // end anonymous namespace
Lang Hamescdd90772014-11-06 19:12:38 +0000236
Eugene Zelenko900b6332017-08-29 22:32:07 +0000237Spiller::~Spiller() = default;
Lang Hamescdd90772014-11-06 19:12:38 +0000238
Eugene Zelenko900b6332017-08-29 22:32:07 +0000239void Spiller::anchor() {}
240
241Spiller *llvm::createInlineSpiller(MachineFunctionPass &pass,
242 MachineFunction &mf,
243 VirtRegMap &vrm) {
Jakob Stoklund Olesen0fef9dd2010-07-20 23:50:15 +0000244 return new InlineSpiller(pass, mf, vrm);
Jakob Stoklund Olesenf8889112010-06-29 23:58:39 +0000245}
Lang Hamescdd90772014-11-06 19:12:38 +0000246
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +0000247//===----------------------------------------------------------------------===//
248// Snippets
249//===----------------------------------------------------------------------===//
250
251// When spilling a virtual register, we also spill any snippets it is connected
252// to. The snippets are small live ranges that only have a single real use,
253// leftovers from live range splitting. Spilling them enables memory operand
254// folding or tightens the live range around the single use.
255//
256// This minimizes register pressure and maximizes the store-to-load distance for
257// spill slots which can be important in tight loops.
258
259/// isFullCopyOf - If MI is a COPY to or from Reg, return the other register,
260/// otherwise return 0.
Duncan P. N. Exon Smith9cfc75c2016-06-30 00:01:54 +0000261static unsigned isFullCopyOf(const MachineInstr &MI, unsigned Reg) {
262 if (!MI.isFullCopy())
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +0000263 return 0;
Duncan P. N. Exon Smith9cfc75c2016-06-30 00:01:54 +0000264 if (MI.getOperand(0).getReg() == Reg)
265 return MI.getOperand(1).getReg();
266 if (MI.getOperand(1).getReg() == Reg)
267 return MI.getOperand(0).getReg();
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +0000268 return 0;
269}
270
271/// isSnippet - Identify if a live interval is a snippet that should be spilled.
272/// It is assumed that SnipLI is a virtual register with the same original as
Jakob Stoklund Olesena00bab22011-03-14 19:56:43 +0000273/// Edit->getReg().
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +0000274bool InlineSpiller::isSnippet(const LiveInterval &SnipLI) {
Jakob Stoklund Olesena00bab22011-03-14 19:56:43 +0000275 unsigned Reg = Edit->getReg();
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +0000276
277 // A snippet is a tiny live range with only a single instruction using it
278 // besides copies to/from Reg or spills/fills. We accept:
279 //
280 // %snip = COPY %Reg / FILL fi#
281 // %snip = USE %snip
282 // %Reg = COPY %snip / SPILL %snip, fi#
283 //
Jakob Stoklund Olesena00bab22011-03-14 19:56:43 +0000284 if (SnipLI.getNumValNums() > 2 || !LIS.intervalIsInOneMBB(SnipLI))
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +0000285 return false;
286
Craig Topperc0196b12014-04-14 00:51:57 +0000287 MachineInstr *UseMI = nullptr;
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +0000288
289 // Check that all uses satisfy our criteria.
Owen Andersonabb90c92014-03-13 06:02:25 +0000290 for (MachineRegisterInfo::reg_instr_nodbg_iterator
291 RI = MRI.reg_instr_nodbg_begin(SnipLI.reg),
292 E = MRI.reg_instr_nodbg_end(); RI != E; ) {
Duncan P. N. Exon Smith9cfc75c2016-06-30 00:01:54 +0000293 MachineInstr &MI = *RI++;
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +0000294
295 // Allow copies to/from Reg.
296 if (isFullCopyOf(MI, Reg))
297 continue;
298
299 // Allow stack slot loads.
300 int FI;
Jakob Stoklund Olesena00bab22011-03-14 19:56:43 +0000301 if (SnipLI.reg == TII.isLoadFromStackSlot(MI, FI) && FI == StackSlot)
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +0000302 continue;
303
304 // Allow stack slot stores.
Jakob Stoklund Olesena00bab22011-03-14 19:56:43 +0000305 if (SnipLI.reg == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot)
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +0000306 continue;
307
308 // Allow a single additional instruction.
Duncan P. N. Exon Smith9cfc75c2016-06-30 00:01:54 +0000309 if (UseMI && &MI != UseMI)
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +0000310 return false;
Duncan P. N. Exon Smith9cfc75c2016-06-30 00:01:54 +0000311 UseMI = &MI;
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +0000312 }
313 return true;
314}
315
316/// collectRegsToSpill - Collect live range snippets that only have a single
317/// real use.
318void InlineSpiller::collectRegsToSpill() {
Jakob Stoklund Olesena00bab22011-03-14 19:56:43 +0000319 unsigned Reg = Edit->getReg();
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +0000320
321 // Main register always spills.
322 RegsToSpill.assign(1, Reg);
323 SnippetCopies.clear();
324
325 // Snippets all have the same original, so there can't be any for an original
326 // register.
Jakob Stoklund Olesena0d5ec12011-03-15 21:13:25 +0000327 if (Original == Reg)
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +0000328 return;
329
Owen Andersonabb90c92014-03-13 06:02:25 +0000330 for (MachineRegisterInfo::reg_instr_iterator
331 RI = MRI.reg_instr_begin(Reg), E = MRI.reg_instr_end(); RI != E; ) {
Duncan P. N. Exon Smith9cfc75c2016-06-30 00:01:54 +0000332 MachineInstr &MI = *RI++;
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +0000333 unsigned SnipReg = isFullCopyOf(MI, Reg);
Jakob Stoklund Olesen27320cb2011-03-18 04:23:06 +0000334 if (!isSibling(SnipReg))
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +0000335 continue;
Jakob Stoklund Olesena00bab22011-03-14 19:56:43 +0000336 LiveInterval &SnipLI = LIS.getInterval(SnipReg);
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +0000337 if (!isSnippet(SnipLI))
338 continue;
Duncan P. N. Exon Smith9cfc75c2016-06-30 00:01:54 +0000339 SnippetCopies.insert(&MI);
Jakob Stoklund Olesenc5a8c082011-05-05 17:22:53 +0000340 if (isRegToSpill(SnipReg))
341 continue;
342 RegsToSpill.push_back(SnipReg);
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000343 LLVM_DEBUG(dbgs() << "\talso spill snippet " << SnipLI << '\n');
Jakob Stoklund Olesenc5a8c082011-05-05 17:22:53 +0000344 ++NumSnippets;
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +0000345 }
346}
347
Jakob Stoklund Olesen27320cb2011-03-18 04:23:06 +0000348bool InlineSpiller::isSibling(unsigned Reg) {
Daniel Sanders2bea69b2019-08-01 23:27:28 +0000349 return Register::isVirtualRegister(Reg) && VRM.getOriginal(Reg) == Original;
Jakob Stoklund Olesen27320cb2011-03-18 04:23:06 +0000350}
351
Wei Mi9a16d652016-04-13 03:08:27 +0000352/// It is beneficial to spill to earlier place in the same BB in case
353/// as follows:
354/// There is an alternative def earlier in the same MBB.
355/// Hoist the spill as far as possible in SpillMBB. This can ease
356/// register pressure:
Hans Wennborg5a7723c2016-04-08 15:17:43 +0000357///
Wei Mi9a16d652016-04-13 03:08:27 +0000358/// x = def
359/// y = use x
360/// s = copy x
Hans Wennborg5a7723c2016-04-08 15:17:43 +0000361///
Wei Mi9a16d652016-04-13 03:08:27 +0000362/// Hoisting the spill of s to immediately after the def removes the
363/// interference between x and y:
Hans Wennborg5a7723c2016-04-08 15:17:43 +0000364///
Wei Mi9a16d652016-04-13 03:08:27 +0000365/// x = def
366/// spill x
Francis Visoiu Mistriha8a83d12017-12-07 10:40:31 +0000367/// y = use killed x
Hans Wennborg5a7723c2016-04-08 15:17:43 +0000368///
Wei Mi9a16d652016-04-13 03:08:27 +0000369/// This hoist only helps when the copy kills its source.
Hans Wennborg5a7723c2016-04-08 15:17:43 +0000370///
Wei Mi9a16d652016-04-13 03:08:27 +0000371bool InlineSpiller::hoistSpillInsideBB(LiveInterval &SpillLI,
372 MachineInstr &CopyMI) {
Hans Wennborg5a7723c2016-04-08 15:17:43 +0000373 SlotIndex Idx = LIS.getInstructionIndex(CopyMI);
Wei Mi9a16d652016-04-13 03:08:27 +0000374#ifndef NDEBUG
Hans Wennborg5a7723c2016-04-08 15:17:43 +0000375 VNInfo *VNI = SpillLI.getVNInfoAt(Idx.getRegSlot());
376 assert(VNI && VNI->def == Idx.getRegSlot() && "Not defined by copy");
Wei Mi9a16d652016-04-13 03:08:27 +0000377#endif
Wei Mifb5252c2016-04-04 17:45:03 +0000378
Daniel Sanders0c476112019-08-15 19:22:08 +0000379 Register SrcReg = CopyMI.getOperand(1).getReg();
Wei Mi9a16d652016-04-13 03:08:27 +0000380 LiveInterval &SrcLI = LIS.getInterval(SrcReg);
381 VNInfo *SrcVNI = SrcLI.getVNInfoAt(Idx);
382 LiveQueryResult SrcQ = SrcLI.Query(Idx);
383 MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(SrcVNI->def);
384 if (DefMBB != CopyMI.getParent() || !SrcQ.isKill())
Hans Wennborg5a7723c2016-04-08 15:17:43 +0000385 return false;
386
Jakob Stoklund Olesen27320cb2011-03-18 04:23:06 +0000387 // Conservatively extend the stack slot range to the range of the original
388 // value. We may be able to do better with stack slot coloring by being more
389 // careful here.
Jakob Stoklund Olesene4663452011-03-26 22:16:41 +0000390 assert(StackInt && "No stack slot assigned yet.");
Jakob Stoklund Olesen27320cb2011-03-18 04:23:06 +0000391 LiveInterval &OrigLI = LIS.getInterval(Original);
392 VNInfo *OrigVNI = OrigLI.getVNInfoAt(Idx);
Jakob Stoklund Olesene4663452011-03-26 22:16:41 +0000393 StackInt->MergeValueInAsValue(OrigLI, OrigVNI, StackInt->getValNumInfo(0));
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000394 LLVM_DEBUG(dbgs() << "\tmerged orig valno " << OrigVNI->id << ": "
395 << *StackInt << '\n');
Jakob Stoklund Olesen27320cb2011-03-18 04:23:06 +0000396
Wei Mi9a16d652016-04-13 03:08:27 +0000397 // We are going to spill SrcVNI immediately after its def, so clear out
Jakob Stoklund Olesen27320cb2011-03-18 04:23:06 +0000398 // any later spills of the same value.
Wei Mi9a16d652016-04-13 03:08:27 +0000399 eliminateRedundantSpills(SrcLI, SrcVNI);
Jakob Stoklund Olesen27320cb2011-03-18 04:23:06 +0000400
Wei Mi9a16d652016-04-13 03:08:27 +0000401 MachineBasicBlock *MBB = LIS.getMBBFromIndex(SrcVNI->def);
Jakob Stoklund Olesen27320cb2011-03-18 04:23:06 +0000402 MachineBasicBlock::iterator MII;
Wei Mi9a16d652016-04-13 03:08:27 +0000403 if (SrcVNI->isPHIDef())
Keith Walker830a8c12016-09-16 14:07:29 +0000404 MII = MBB->SkipPHIsLabelsAndDebug(MBB->begin());
Jakob Stoklund Olesen27320cb2011-03-18 04:23:06 +0000405 else {
Wei Mi9a16d652016-04-13 03:08:27 +0000406 MachineInstr *DefMI = LIS.getInstructionFromIndex(SrcVNI->def);
Jakob Stoklund Olesenec9b4a62011-04-30 06:42:21 +0000407 assert(DefMI && "Defining instruction disappeared");
408 MII = DefMI;
Jakob Stoklund Olesen27320cb2011-03-18 04:23:06 +0000409 ++MII;
410 }
411 // Insert spill without kill flag immediately after def.
Wei Mi9a16d652016-04-13 03:08:27 +0000412 TII.storeRegToStackSlot(*MBB, MII, SrcReg, false, StackSlot,
413 MRI.getRegClass(SrcReg), &TRI);
Jakob Stoklund Olesen27320cb2011-03-18 04:23:06 +0000414 --MII; // Point to store instruction.
Duncan P. N. Exon Smith3ac9cc62016-02-27 06:40:41 +0000415 LIS.InsertMachineInstrInMaps(*MII);
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000416 LLVM_DEBUG(dbgs() << "\thoisted: " << SrcVNI->def << '\t' << *MII);
Jakob Stoklund Olesenc5a8c082011-05-05 17:22:53 +0000417
Duncan P. N. Exon Smith91298732016-06-30 23:28:15 +0000418 HSpiller.addToMergeableSpills(*MII, StackSlot, Original);
Jakob Stoklund Olesen37eb6962011-09-15 17:54:28 +0000419 ++NumSpills;
Jakob Stoklund Olesen27320cb2011-03-18 04:23:06 +0000420 return true;
421}
422
Jakob Stoklund Olesen39488642011-03-20 05:44:55 +0000423/// eliminateRedundantSpills - SLI:VNI is known to be on the stack. Remove any
424/// redundant spills of this value in SLI.reg and sibling copies.
425void InlineSpiller::eliminateRedundantSpills(LiveInterval &SLI, VNInfo *VNI) {
Jakob Stoklund Olesene55003f2011-03-20 05:44:58 +0000426 assert(VNI && "Missing value");
Jakob Stoklund Olesen39488642011-03-20 05:44:55 +0000427 SmallVector<std::pair<LiveInterval*, VNInfo*>, 8> WorkList;
428 WorkList.push_back(std::make_pair(&SLI, VNI));
Jakob Stoklund Olesene4663452011-03-26 22:16:41 +0000429 assert(StackInt && "No stack slot assigned yet.");
Jakob Stoklund Olesen27320cb2011-03-18 04:23:06 +0000430
431 do {
Jakob Stoklund Olesen39488642011-03-20 05:44:55 +0000432 LiveInterval *LI;
Benjamin Kramerd6f1f842014-03-02 13:30:33 +0000433 std::tie(LI, VNI) = WorkList.pop_back_val();
Jakob Stoklund Olesen39488642011-03-20 05:44:55 +0000434 unsigned Reg = LI->reg;
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000435 LLVM_DEBUG(dbgs() << "Checking redundant spills for " << VNI->id << '@'
436 << VNI->def << " in " << *LI << '\n');
Jakob Stoklund Olesen27320cb2011-03-18 04:23:06 +0000437
438 // Regs to spill are taken care of.
439 if (isRegToSpill(Reg))
440 continue;
441
442 // Add all of VNI's live range to StackInt.
Jakob Stoklund Olesene4663452011-03-26 22:16:41 +0000443 StackInt->MergeValueInAsValue(*LI, VNI, StackInt->getValNumInfo(0));
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000444 LLVM_DEBUG(dbgs() << "Merged to stack int: " << *StackInt << '\n');
Jakob Stoklund Olesen27320cb2011-03-18 04:23:06 +0000445
446 // Find all spills and copies of VNI.
Owen Andersonabb90c92014-03-13 06:02:25 +0000447 for (MachineRegisterInfo::use_instr_nodbg_iterator
448 UI = MRI.use_instr_nodbg_begin(Reg), E = MRI.use_instr_nodbg_end();
449 UI != E; ) {
Duncan P. N. Exon Smith9cfc75c2016-06-30 00:01:54 +0000450 MachineInstr &MI = *UI++;
451 if (!MI.isCopy() && !MI.mayStore())
Jakob Stoklund Olesen27320cb2011-03-18 04:23:06 +0000452 continue;
Duncan P. N. Exon Smith9cfc75c2016-06-30 00:01:54 +0000453 SlotIndex Idx = LIS.getInstructionIndex(MI);
Jakob Stoklund Olesen39488642011-03-20 05:44:55 +0000454 if (LI->getVNInfoAt(Idx) != VNI)
Jakob Stoklund Olesen27320cb2011-03-18 04:23:06 +0000455 continue;
456
457 // Follow sibling copies down the dominator tree.
458 if (unsigned DstReg = isFullCopyOf(MI, Reg)) {
459 if (isSibling(DstReg)) {
460 LiveInterval &DstLI = LIS.getInterval(DstReg);
Jakob Stoklund Olesen90b5e562011-11-13 20:45:27 +0000461 VNInfo *DstVNI = DstLI.getVNInfoAt(Idx.getRegSlot());
Jakob Stoklund Olesen27320cb2011-03-18 04:23:06 +0000462 assert(DstVNI && "Missing defined value");
Jakob Stoklund Olesen90b5e562011-11-13 20:45:27 +0000463 assert(DstVNI->def == Idx.getRegSlot() && "Wrong copy def slot");
Jakob Stoklund Olesen39488642011-03-20 05:44:55 +0000464 WorkList.push_back(std::make_pair(&DstLI, DstVNI));
Jakob Stoklund Olesen27320cb2011-03-18 04:23:06 +0000465 }
466 continue;
467 }
468
469 // Erase spills.
470 int FI;
471 if (Reg == TII.isStoreToStackSlot(MI, FI) && FI == StackSlot) {
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000472 LLVM_DEBUG(dbgs() << "Redundant spill " << Idx << '\t' << MI);
Jakob Stoklund Olesen27320cb2011-03-18 04:23:06 +0000473 // eliminateDeadDefs won't normally remove stores, so switch opcode.
Duncan P. N. Exon Smith9cfc75c2016-06-30 00:01:54 +0000474 MI.setDesc(TII.get(TargetOpcode::KILL));
475 DeadDefs.push_back(&MI);
Jakob Stoklund Olesen37eb6962011-09-15 17:54:28 +0000476 ++NumSpillsRemoved;
Duncan P. N. Exon Smith91298732016-06-30 23:28:15 +0000477 if (HSpiller.rmFromMergeableSpills(MI, StackSlot))
Wei Mi9a16d652016-04-13 03:08:27 +0000478 --NumSpills;
Jakob Stoklund Olesen27320cb2011-03-18 04:23:06 +0000479 }
480 }
481 } while (!WorkList.empty());
482}
483
Jakob Stoklund Olesend8af5292011-03-29 03:12:02 +0000484//===----------------------------------------------------------------------===//
485// Rematerialization
486//===----------------------------------------------------------------------===//
487
488/// markValueUsed - Remember that VNI failed to rematerialize, so its defining
489/// instruction cannot be eliminated. See through snippet copies
490void InlineSpiller::markValueUsed(LiveInterval *LI, VNInfo *VNI) {
491 SmallVector<std::pair<LiveInterval*, VNInfo*>, 8> WorkList;
492 WorkList.push_back(std::make_pair(LI, VNI));
493 do {
Benjamin Kramerd6f1f842014-03-02 13:30:33 +0000494 std::tie(LI, VNI) = WorkList.pop_back_val();
David Blaikie70573dc2014-11-19 07:49:26 +0000495 if (!UsedValues.insert(VNI).second)
Jakob Stoklund Olesend8af5292011-03-29 03:12:02 +0000496 continue;
497
498 if (VNI->isPHIDef()) {
499 MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def);
Craig Topper73275a22015-12-24 05:20:40 +0000500 for (MachineBasicBlock *P : MBB->predecessors()) {
501 VNInfo *PVNI = LI->getVNInfoBefore(LIS.getMBBEndIdx(P));
Jakob Stoklund Olesend8af5292011-03-29 03:12:02 +0000502 if (PVNI)
503 WorkList.push_back(std::make_pair(LI, PVNI));
504 }
505 continue;
506 }
507
508 // Follow snippet copies.
509 MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);
510 if (!SnippetCopies.count(MI))
511 continue;
512 LiveInterval &SnipLI = LIS.getInterval(MI->getOperand(1).getReg());
513 assert(isRegToSpill(SnipLI.reg) && "Unexpected register in copy");
Jakob Stoklund Olesen90b5e562011-11-13 20:45:27 +0000514 VNInfo *SnipVNI = SnipLI.getVNInfoAt(VNI->def.getRegSlot(true));
Jakob Stoklund Olesend8af5292011-03-29 03:12:02 +0000515 assert(SnipVNI && "Snippet undefined before copy");
516 WorkList.push_back(std::make_pair(&SnipLI, SnipVNI));
517 } while (!WorkList.empty());
518}
519
Philip Reames7403fac2019-02-12 18:33:01 +0000520bool InlineSpiller::canGuaranteeAssignmentAfterRemat(unsigned VReg,
521 MachineInstr &MI) {
522 if (!RestrictStatepointRemat)
523 return true;
524 // Here's a quick explanation of the problem we're trying to handle here:
525 // * There are some pseudo instructions with more vreg uses than there are
526 // physical registers on the machine.
527 // * This is normally handled by spilling the vreg, and folding the reload
528 // into the user instruction. (Thus decreasing the number of used vregs
529 // until the remainder can be assigned to physregs.)
530 // * However, since we may try to spill vregs in any order, we can end up
531 // trying to spill each operand to the instruction, and then rematting it
532 // instead. When that happens, the new live intervals (for the remats) are
533 // expected to be trivially assignable (i.e. RS_Done). However, since we
534 // may have more remats than physregs, we're guaranteed to fail to assign
535 // one.
536 // At the moment, we only handle this for STATEPOINTs since they're the only
Jay Foad8382f872020-01-03 14:05:58 +0000537 // pseudo op where we've seen this. If we start seeing other instructions
Philip Reames7403fac2019-02-12 18:33:01 +0000538 // with the same problem, we need to revisit this.
539 return (MI.getOpcode() != TargetOpcode::STATEPOINT);
540}
541
Jakob Stoklund Olesend8af5292011-03-29 03:12:02 +0000542/// reMaterializeFor - Attempt to rematerialize before MI instead of reloading.
Duncan P. N. Exon Smithd6ebd072016-02-27 20:23:14 +0000543bool InlineSpiller::reMaterializeFor(LiveInterval &VirtReg, MachineInstr &MI) {
Patrik Hagglund296acbf2014-09-01 11:04:07 +0000544 // Analyze instruction
545 SmallVector<std::pair<MachineInstr *, unsigned>, 8> Ops;
Florian Hahn5d062562019-12-02 19:41:09 +0000546 VirtRegInfo RI = AnalyzeVirtRegInBundle(MI, VirtReg.reg, &Ops);
Patrik Hagglund296acbf2014-09-01 11:04:07 +0000547
548 if (!RI.Reads)
549 return false;
550
Duncan P. N. Exon Smithd6ebd072016-02-27 20:23:14 +0000551 SlotIndex UseIdx = LIS.getInstructionIndex(MI).getRegSlot(true);
Jakob Stoklund Olesenc0dd3da2011-07-18 05:31:59 +0000552 VNInfo *ParentVNI = VirtReg.getVNInfoAt(UseIdx.getBaseIndex());
Jakob Stoklund Olesend8af5292011-03-29 03:12:02 +0000553
554 if (!ParentVNI) {
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000555 LLVM_DEBUG(dbgs() << "\tadding <undef> flags: ");
Duncan P. N. Exon Smithd6ebd072016-02-27 20:23:14 +0000556 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
557 MachineOperand &MO = MI.getOperand(i);
Jakob Stoklund Olesen0ed9ebc2011-03-29 17:47:02 +0000558 if (MO.isReg() && MO.isUse() && MO.getReg() == VirtReg.reg)
Jakob Stoklund Olesen96037182010-07-02 17:44:57 +0000559 MO.setIsUndef();
560 }
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000561 LLVM_DEBUG(dbgs() << UseIdx << '\t' << MI);
Jakob Stoklund Olesen96037182010-07-02 17:44:57 +0000562 return true;
563 }
Jakob Stoklund Olesen2edaa2f2010-10-20 22:00:51 +0000564
Duncan P. N. Exon Smithd6ebd072016-02-27 20:23:14 +0000565 if (SnippetCopies.count(&MI))
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +0000566 return false;
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +0000567
Wei Mi9a16d652016-04-13 03:08:27 +0000568 LiveInterval &OrigLI = LIS.getInterval(Original);
569 VNInfo *OrigVNI = OrigLI.getVNInfoAt(UseIdx);
Jakob Stoklund Olesend8af5292011-03-29 03:12:02 +0000570 LiveRangeEdit::Remat RM(ParentVNI);
Wei Mi9a16d652016-04-13 03:08:27 +0000571 RM.OrigMI = LIS.getInstructionFromIndex(OrigVNI->def);
572
573 if (!Edit->canRematerializeAt(RM, OrigVNI, UseIdx, false)) {
Jakob Stoklund Olesend8af5292011-03-29 03:12:02 +0000574 markValueUsed(&VirtReg, ParentVNI);
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000575 LLVM_DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << MI);
Jakob Stoklund Olesen96037182010-07-02 17:44:57 +0000576 return false;
577 }
578
Jakob Stoklund Olesen0ed9ebc2011-03-29 17:47:02 +0000579 // If the instruction also writes VirtReg.reg, it had better not require the
580 // same register for uses and defs.
Jakob Stoklund Olesenabe8c092012-03-01 01:43:25 +0000581 if (RI.Tied) {
582 markValueUsed(&VirtReg, ParentVNI);
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000583 LLVM_DEBUG(dbgs() << "\tcannot remat tied reg: " << UseIdx << '\t' << MI);
Jakob Stoklund Olesenabe8c092012-03-01 01:43:25 +0000584 return false;
Jakob Stoklund Olesen96037182010-07-02 17:44:57 +0000585 }
586
Jakob Stoklund Olesen3b2966d2010-12-18 03:04:14 +0000587 // Before rematerializing into a register for a single instruction, try to
588 // fold a load into the instruction. That avoids allocating a new register.
Evan Cheng7f8e5632011-12-07 07:15:52 +0000589 if (RM.OrigMI->canFoldAsLoad() &&
Jakob Stoklund Olesenabe8c092012-03-01 01:43:25 +0000590 foldMemoryOperand(Ops, RM.OrigMI)) {
Jakob Stoklund Olesena00bab22011-03-14 19:56:43 +0000591 Edit->markRematerialized(RM.ParentVNI);
Jakob Stoklund Olesenc5a8c082011-05-05 17:22:53 +0000592 ++NumFoldedLoads;
Jakob Stoklund Olesen3b2966d2010-12-18 03:04:14 +0000593 return true;
594 }
595
Philip Reames7403fac2019-02-12 18:33:01 +0000596 // If we can't guarantee that we'll be able to actually assign the new vreg,
597 // we can't remat.
598 if (!canGuaranteeAssignmentAfterRemat(VirtReg.reg, MI)) {
599 markValueUsed(&VirtReg, ParentVNI);
600 LLVM_DEBUG(dbgs() << "\tcannot remat for " << UseIdx << '\t' << MI);
601 return false;
602 }
603
Wolfgang Pieb8df58f42016-08-16 17:12:50 +0000604 // Allocate a new register for the remat.
Mark Lacey9d8103d2013-08-14 23:50:16 +0000605 unsigned NewVReg = Edit->createFrom(Original);
Jakob Stoklund Olesen96037182010-07-02 17:44:57 +0000606
607 // Finally we can rematerialize OrigMI before MI.
Duncan P. N. Exon Smithd6ebd072016-02-27 20:23:14 +0000608 SlotIndex DefIdx =
609 Edit->rematerializeAt(*MI.getParent(), MI, NewVReg, RM, TRI);
Wolfgang Pieb8df58f42016-08-16 17:12:50 +0000610
611 // We take the DebugLoc from MI, since OrigMI may be attributed to a
Junmo Park061bec82017-02-25 01:50:45 +0000612 // different source location.
Wolfgang Pieb8df58f42016-08-16 17:12:50 +0000613 auto *NewMI = LIS.getInstructionFromIndex(DefIdx);
614 NewMI->setDebugLoc(MI.getDebugLoc());
615
Mark Lacey9d8103d2013-08-14 23:50:16 +0000616 (void)DefIdx;
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000617 LLVM_DEBUG(dbgs() << "\tremat: " << DefIdx << '\t'
618 << *LIS.getInstructionFromIndex(DefIdx));
Jakob Stoklund Olesen96037182010-07-02 17:44:57 +0000619
620 // Replace operands
Craig Topper73275a22015-12-24 05:20:40 +0000621 for (const auto &OpPair : Ops) {
622 MachineOperand &MO = OpPair.first->getOperand(OpPair.second);
Jakob Stoklund Olesen0ed9ebc2011-03-29 17:47:02 +0000623 if (MO.isReg() && MO.isUse() && MO.getReg() == VirtReg.reg) {
Mark Lacey9d8103d2013-08-14 23:50:16 +0000624 MO.setReg(NewVReg);
Jakob Stoklund Olesen96037182010-07-02 17:44:57 +0000625 MO.setIsKill();
626 }
627 }
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000628 LLVM_DEBUG(dbgs() << "\t " << UseIdx << '\t' << MI << '\n');
Jakob Stoklund Olesen96037182010-07-02 17:44:57 +0000629
Jakob Stoklund Olesenc5a8c082011-05-05 17:22:53 +0000630 ++NumRemats;
Jakob Stoklund Olesenbde96ad2010-06-30 23:03:52 +0000631 return true;
632}
633
Jakob Stoklund Olesen72911e42010-10-14 23:49:52 +0000634/// reMaterializeAll - Try to rematerialize as many uses as possible,
Jakob Stoklund Olesen96037182010-07-02 17:44:57 +0000635/// and trim the live ranges after.
636void InlineSpiller::reMaterializeAll() {
Pete Cooper2bde2f42012-04-02 22:22:53 +0000637 if (!Edit->anyRematerializable(AA))
Jakob Stoklund Olesen96037182010-07-02 17:44:57 +0000638 return;
639
Jakob Stoklund Olesena00bab22011-03-14 19:56:43 +0000640 UsedValues.clear();
Jakob Stoklund Olesen2edaa2f2010-10-20 22:00:51 +0000641
Jakob Stoklund Olesend8af5292011-03-29 03:12:02 +0000642 // Try to remat before all uses of snippets.
Jakob Stoklund Olesen96037182010-07-02 17:44:57 +0000643 bool anyRemat = false;
Craig Topper73275a22015-12-24 05:20:40 +0000644 for (unsigned Reg : RegsToSpill) {
Jakob Stoklund Olesend8af5292011-03-29 03:12:02 +0000645 LiveInterval &LI = LIS.getInterval(Reg);
Patrik Hagglund296acbf2014-09-01 11:04:07 +0000646 for (MachineRegisterInfo::reg_bundle_iterator
647 RegI = MRI.reg_bundle_begin(Reg), E = MRI.reg_bundle_end();
648 RegI != E; ) {
Duncan P. N. Exon Smithd6ebd072016-02-27 20:23:14 +0000649 MachineInstr &MI = *RegI++;
Patrik Hagglund296acbf2014-09-01 11:04:07 +0000650
651 // Debug values are not allowed to affect codegen.
Shiva Chen21eab932018-05-16 02:57:26 +0000652 if (MI.isDebugValue())
Patrik Hagglund296acbf2014-09-01 11:04:07 +0000653 continue;
654
Shiva Chen21eab932018-05-16 02:57:26 +0000655 assert(!MI.isDebugInstr() && "Did not expect to find a use in debug "
656 "instruction that isn't a DBG_VALUE");
657
Jakob Stoklund Olesend8af5292011-03-29 03:12:02 +0000658 anyRemat |= reMaterializeFor(LI, MI);
Owen Andersonabb90c92014-03-13 06:02:25 +0000659 }
Jakob Stoklund Olesend8af5292011-03-29 03:12:02 +0000660 }
Jakob Stoklund Olesen96037182010-07-02 17:44:57 +0000661 if (!anyRemat)
662 return;
663
664 // Remove any values that were completely rematted.
Craig Topper73275a22015-12-24 05:20:40 +0000665 for (unsigned Reg : RegsToSpill) {
Jakob Stoklund Olesend8af5292011-03-29 03:12:02 +0000666 LiveInterval &LI = LIS.getInterval(Reg);
667 for (LiveInterval::vni_iterator I = LI.vni_begin(), E = LI.vni_end();
668 I != E; ++I) {
669 VNInfo *VNI = *I;
Jakob Stoklund Olesenadd79c62011-03-29 17:47:00 +0000670 if (VNI->isUnused() || VNI->isPHIDef() || UsedValues.count(VNI))
Jakob Stoklund Olesencf6c5c92010-07-02 19:54:40 +0000671 continue;
Jakob Stoklund Olesend8af5292011-03-29 03:12:02 +0000672 MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);
673 MI->addRegisterDead(Reg, &TRI);
674 if (!MI->allDefsAreDead())
675 continue;
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000676 LLVM_DEBUG(dbgs() << "All defs dead: " << *MI);
Jakob Stoklund Olesend8af5292011-03-29 03:12:02 +0000677 DeadDefs.push_back(MI);
Jakob Stoklund Olesencf6c5c92010-07-02 19:54:40 +0000678 }
Jakob Stoklund Olesen96037182010-07-02 17:44:57 +0000679 }
Jakob Stoklund Olesenadd79c62011-03-29 17:47:00 +0000680
681 // Eliminate dead code after remat. Note that some snippet copies may be
682 // deleted here.
683 if (DeadDefs.empty())
684 return;
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000685 LLVM_DEBUG(dbgs() << "Remat created " << DeadDefs.size() << " dead defs.\n");
Wei Mic0223702016-07-08 21:08:09 +0000686 Edit->eliminateDeadDefs(DeadDefs, RegsToSpill, AA);
Jakob Stoklund Olesenadd79c62011-03-29 17:47:00 +0000687
Wei Mia62f0582016-02-05 18:14:24 +0000688 // LiveRangeEdit::eliminateDeadDef is used to remove dead define instructions
689 // after rematerialization. To remove a VNI for a vreg from its LiveInterval,
690 // LiveIntervals::removeVRegDefAt is used. However, after non-PHI VNIs are all
691 // removed, PHI VNI are still left in the LiveInterval.
692 // So to get rid of unused reg, we need to check whether it has non-dbg
693 // reference instead of whether it has non-empty interval.
Benjamin Kramer391f5a62013-05-05 11:29:14 +0000694 unsigned ResultPos = 0;
Craig Topper73275a22015-12-24 05:20:40 +0000695 for (unsigned Reg : RegsToSpill) {
Wei Mia62f0582016-02-05 18:14:24 +0000696 if (MRI.reg_nodbg_empty(Reg)) {
Benjamin Kramer391f5a62013-05-05 11:29:14 +0000697 Edit->eraseVirtReg(Reg);
Jakob Stoklund Olesenadd79c62011-03-29 17:47:00 +0000698 continue;
699 }
Matt Arsenaultc5d1e502017-07-22 00:24:01 +0000700
Matt Arsenault5fbc8702017-07-24 18:07:55 +0000701 assert(LIS.hasInterval(Reg) &&
702 (!LIS.getInterval(Reg).empty() || !MRI.reg_nodbg_empty(Reg)) &&
703 "Empty and not used live-range?!");
704
Benjamin Kramer391f5a62013-05-05 11:29:14 +0000705 RegsToSpill[ResultPos++] = Reg;
Jakob Stoklund Olesenadd79c62011-03-29 17:47:00 +0000706 }
Benjamin Kramer391f5a62013-05-05 11:29:14 +0000707 RegsToSpill.erase(RegsToSpill.begin() + ResultPos, RegsToSpill.end());
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000708 LLVM_DEBUG(dbgs() << RegsToSpill.size()
709 << " registers to spill after remat.\n");
Jakob Stoklund Olesen96037182010-07-02 17:44:57 +0000710}
711
Jakob Stoklund Olesene991f722011-03-29 21:20:19 +0000712//===----------------------------------------------------------------------===//
713// Spilling
714//===----------------------------------------------------------------------===//
715
Jakob Stoklund Olesena00bab22011-03-14 19:56:43 +0000716/// If MI is a load or store of StackSlot, it can be removed.
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +0000717bool InlineSpiller::coalesceStackAccess(MachineInstr *MI, unsigned Reg) {
Jakob Stoklund Olesen7fd49052010-08-04 22:35:11 +0000718 int FI = 0;
Duncan P. N. Exon Smith9cfc75c2016-06-30 00:01:54 +0000719 unsigned InstrReg = TII.isLoadFromStackSlot(*MI, FI);
Jakob Stoklund Olesen37eb6962011-09-15 17:54:28 +0000720 bool IsLoad = InstrReg;
721 if (!IsLoad)
Duncan P. N. Exon Smith9cfc75c2016-06-30 00:01:54 +0000722 InstrReg = TII.isStoreToStackSlot(*MI, FI);
Jakob Stoklund Olesen7fd49052010-08-04 22:35:11 +0000723
724 // We have a stack access. Is it the right register and slot?
Jakob Stoklund Olesena00bab22011-03-14 19:56:43 +0000725 if (InstrReg != Reg || FI != StackSlot)
Jakob Stoklund Olesen7fd49052010-08-04 22:35:11 +0000726 return false;
727
Wei Mi9a16d652016-04-13 03:08:27 +0000728 if (!IsLoad)
Duncan P. N. Exon Smith91298732016-06-30 23:28:15 +0000729 HSpiller.rmFromMergeableSpills(*MI, StackSlot);
Wei Mi9a16d652016-04-13 03:08:27 +0000730
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000731 LLVM_DEBUG(dbgs() << "Coalescing stack access: " << *MI);
Duncan P. N. Exon Smith3ac9cc62016-02-27 06:40:41 +0000732 LIS.RemoveMachineInstrFromMaps(*MI);
Jakob Stoklund Olesen7fd49052010-08-04 22:35:11 +0000733 MI->eraseFromParent();
Jakob Stoklund Olesen37eb6962011-09-15 17:54:28 +0000734
735 if (IsLoad) {
736 ++NumReloadsRemoved;
737 --NumReloads;
738 } else {
739 ++NumSpillsRemoved;
740 --NumSpills;
741 }
742
Jakob Stoklund Olesen7fd49052010-08-04 22:35:11 +0000743 return true;
744}
745
Aaron Ballman615eb472017-10-15 14:32:27 +0000746#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
Junmo Parkc7479ba2017-03-28 04:14:25 +0000747LLVM_DUMP_METHOD
Mark Lacey9d8103d2013-08-14 23:50:16 +0000748// Dump the range of instructions from B to E with their slot indexes.
749static void dumpMachineInstrRangeWithSlotIndex(MachineBasicBlock::iterator B,
750 MachineBasicBlock::iterator E,
751 LiveIntervals const &LIS,
752 const char *const header,
753 unsigned VReg =0) {
754 char NextLine = '\n';
755 char SlotIndent = '\t';
756
Benjamin Kramerb6d0bd42014-03-02 12:27:27 +0000757 if (std::next(B) == E) {
Mark Lacey9d8103d2013-08-14 23:50:16 +0000758 NextLine = ' ';
759 SlotIndent = ' ';
760 }
761
762 dbgs() << '\t' << header << ": " << NextLine;
763
764 for (MachineBasicBlock::iterator I = B; I != E; ++I) {
Duncan P. N. Exon Smith3ac9cc62016-02-27 06:40:41 +0000765 SlotIndex Idx = LIS.getInstructionIndex(*I).getRegSlot();
Mark Lacey9d8103d2013-08-14 23:50:16 +0000766
767 // If a register was passed in and this instruction has it as a
768 // destination that is marked as an early clobber, print the
769 // early-clobber slot index.
770 if (VReg) {
771 MachineOperand *MO = I->findRegisterDefOperand(VReg);
772 if (MO && MO->isEarlyClobber())
773 Idx = Idx.getRegSlot(true);
774 }
775
776 dbgs() << SlotIndent << Idx << '\t' << *I;
777 }
778}
779#endif
780
Jakob Stoklund Olesenabe8c092012-03-01 01:43:25 +0000781/// foldMemoryOperand - Try folding stack slot references in Ops into their
782/// instructions.
783///
Florian Hahn5d062562019-12-02 19:41:09 +0000784/// @param Ops Operand indices from AnalyzeVirtRegInBundle().
Jakob Stoklund Olesen3b2966d2010-12-18 03:04:14 +0000785/// @param LoadMI Load instruction to use instead of stack slot when non-null.
Jakob Stoklund Olesenabe8c092012-03-01 01:43:25 +0000786/// @return True on success.
787bool InlineSpiller::
Eugene Zelenko900b6332017-08-29 22:32:07 +0000788foldMemoryOperand(ArrayRef<std::pair<MachineInstr *, unsigned>> Ops,
Jakob Stoklund Olesenabe8c092012-03-01 01:43:25 +0000789 MachineInstr *LoadMI) {
790 if (Ops.empty())
791 return false;
792 // Don't attempt folding in bundles.
793 MachineInstr *MI = Ops.front().first;
794 if (Ops.back().first != MI || MI->isBundled())
795 return false;
796
Jakob Stoklund Olesenc94c9672011-09-15 18:22:52 +0000797 bool WasCopy = MI->isCopy();
Jakob Stoklund Oleseneef48b62011-11-10 00:17:03 +0000798 unsigned ImpReg = 0;
799
Michael Kuperstein47eb85a2016-11-23 18:33:49 +0000800 // Spill subregs if the target allows it.
801 // We always want to spill subregs for stackmap/patchpoint pseudos.
802 bool SpillSubRegs = TII.isSubregFoldable() ||
803 MI->getOpcode() == TargetOpcode::STATEPOINT ||
804 MI->getOpcode() == TargetOpcode::PATCHPOINT ||
805 MI->getOpcode() == TargetOpcode::STACKMAP;
Andrew Trick10d5be42013-11-17 01:36:23 +0000806
Jakob Stoklund Olesen8656a452010-07-01 00:13:04 +0000807 // TargetInstrInfo::foldMemoryOperand only expects explicit, non-tied
808 // operands.
809 SmallVector<unsigned, 8> FoldOps;
Craig Topper73275a22015-12-24 05:20:40 +0000810 for (const auto &OpPair : Ops) {
811 unsigned Idx = OpPair.second;
812 assert(MI == OpPair.first && "Instruction conflict during operand folding");
Jakob Stoklund Olesen8656a452010-07-01 00:13:04 +0000813 MachineOperand &MO = MI->getOperand(Idx);
Jakob Stoklund Oleseneef48b62011-11-10 00:17:03 +0000814 if (MO.isImplicit()) {
815 ImpReg = MO.getReg();
Jakob Stoklund Olesen8656a452010-07-01 00:13:04 +0000816 continue;
Jakob Stoklund Oleseneef48b62011-11-10 00:17:03 +0000817 }
Michael Kuperstein47eb85a2016-11-23 18:33:49 +0000818
Andrew Trick10d5be42013-11-17 01:36:23 +0000819 if (!SpillSubRegs && MO.getSubReg())
Jakob Stoklund Olesen8656a452010-07-01 00:13:04 +0000820 return false;
Jakob Stoklund Olesenc6a20412011-02-08 19:33:55 +0000821 // We cannot fold a load instruction into a def.
822 if (LoadMI && MO.isDef())
823 return false;
Jakob Stoklund Olesen8656a452010-07-01 00:13:04 +0000824 // Tied use operands should not be passed to foldMemoryOperand.
825 if (!MI->isRegTiedToDefOperand(Idx))
826 FoldOps.push_back(Idx);
827 }
828
Quentin Colombetae3168d2016-12-08 00:06:51 +0000829 // If we only have implicit uses, we won't be able to fold that.
830 // Moreover, TargetInstrInfo::foldMemoryOperand will assert if we try!
831 if (FoldOps.empty())
832 return false;
833
Michael Liao8d6ea2d2019-07-05 20:23:59 +0000834 MachineInstrSpan MIS(MI, MI->getParent());
Mark Lacey9d8103d2013-08-14 23:50:16 +0000835
Jakob Stoklund Olesen3b2966d2010-12-18 03:04:14 +0000836 MachineInstr *FoldMI =
Duncan P. N. Exon Smith9cfc75c2016-06-30 00:01:54 +0000837 LoadMI ? TII.foldMemoryOperand(*MI, FoldOps, *LoadMI, &LIS)
Jonas Paulssonfdc4ea32019-06-08 06:19:15 +0000838 : TII.foldMemoryOperand(*MI, FoldOps, StackSlot, &LIS, &VRM);
Jakob Stoklund Olesen8656a452010-07-01 00:13:04 +0000839 if (!FoldMI)
840 return false;
Andrew Trick5749b8b2013-06-21 18:33:26 +0000841
842 // Remove LIS for any dead defs in the original MI not in FoldMI.
Duncan P. N. Exon Smithf9ab4162016-02-27 17:05:33 +0000843 for (MIBundleOperands MO(*MI); MO.isValid(); ++MO) {
Andrew Trick5749b8b2013-06-21 18:33:26 +0000844 if (!MO->isReg())
845 continue;
Daniel Sanders0c476112019-08-15 19:22:08 +0000846 Register Reg = MO->getReg();
Daniel Sanders2bea69b2019-08-01 23:27:28 +0000847 if (!Reg || Register::isVirtualRegister(Reg) || MRI.isReserved(Reg)) {
Andrew Trick5749b8b2013-06-21 18:33:26 +0000848 continue;
849 }
Andrew Trickdfacda32014-01-07 07:31:10 +0000850 // Skip non-Defs, including undef uses and internal reads.
851 if (MO->isUse())
852 continue;
Florian Hahn5154b022019-12-02 20:00:56 +0000853 PhysRegInfo RI = AnalyzePhysRegInBundle(*FoldMI, Reg, &TRI);
Matthias Braun60d69e22015-12-11 19:42:09 +0000854 if (RI.FullyDefined)
Andrew Trick5749b8b2013-06-21 18:33:26 +0000855 continue;
856 // FoldMI does not define this physreg. Remove the LI segment.
857 assert(MO->isDead() && "Cannot fold physreg def");
Duncan P. N. Exon Smith3ac9cc62016-02-27 06:40:41 +0000858 SlotIndex Idx = LIS.getInstructionIndex(*MI).getRegSlot();
Matthias Brauncfb8ad22015-01-21 18:50:21 +0000859 LIS.removePhysRegDefAt(Reg, Idx);
Andrew Trick5749b8b2013-06-21 18:33:26 +0000860 }
Mark Lacey9d8103d2013-08-14 23:50:16 +0000861
Wei Mi9a16d652016-04-13 03:08:27 +0000862 int FI;
Duncan P. N. Exon Smith91298732016-06-30 23:28:15 +0000863 if (TII.isStoreToStackSlot(*MI, FI) &&
864 HSpiller.rmFromMergeableSpills(*MI, FI))
Wei Mi9a16d652016-04-13 03:08:27 +0000865 --NumSpills;
Duncan P. N. Exon Smith3ac9cc62016-02-27 06:40:41 +0000866 LIS.ReplaceMachineInstrInMaps(*MI, *FoldMI);
Djordje Todorovic71d38692019-06-27 13:10:29 +0000867 if (MI->isCall())
Nikola Prica98603a82019-10-08 15:43:12 +0000868 MI->getMF()->moveCallSiteInfo(MI, FoldMI);
Jakob Stoklund Olesenbd953d12010-07-09 17:29:08 +0000869 MI->eraseFromParent();
Jakob Stoklund Oleseneef48b62011-11-10 00:17:03 +0000870
Mark Lacey9d8103d2013-08-14 23:50:16 +0000871 // Insert any new instructions other than FoldMI into the LIS maps.
872 assert(!MIS.empty() && "Unexpected empty span of instructions!");
Craig Topper73275a22015-12-24 05:20:40 +0000873 for (MachineInstr &MI : MIS)
874 if (&MI != FoldMI)
Duncan P. N. Exon Smith3ac9cc62016-02-27 06:40:41 +0000875 LIS.InsertMachineInstrInMaps(MI);
Mark Lacey9d8103d2013-08-14 23:50:16 +0000876
Jakob Stoklund Oleseneef48b62011-11-10 00:17:03 +0000877 // TII.foldMemoryOperand may have left some implicit operands on the
878 // instruction. Strip them.
879 if (ImpReg)
880 for (unsigned i = FoldMI->getNumOperands(); i; --i) {
881 MachineOperand &MO = FoldMI->getOperand(i - 1);
882 if (!MO.isReg() || !MO.isImplicit())
883 break;
884 if (MO.getReg() == ImpReg)
885 FoldMI->RemoveOperand(i - 1);
886 }
887
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000888 LLVM_DEBUG(dumpMachineInstrRangeWithSlotIndex(MIS.begin(), MIS.end(), LIS,
889 "folded"));
Mark Lacey9d8103d2013-08-14 23:50:16 +0000890
Jakob Stoklund Olesenc94c9672011-09-15 18:22:52 +0000891 if (!WasCopy)
892 ++NumFolded;
Wei Mi9a16d652016-04-13 03:08:27 +0000893 else if (Ops.front().second == 0) {
Jakob Stoklund Olesenc94c9672011-09-15 18:22:52 +0000894 ++NumSpills;
Duncan P. N. Exon Smith91298732016-06-30 23:28:15 +0000895 HSpiller.addToMergeableSpills(*FoldMI, StackSlot, Original);
Wei Mi9a16d652016-04-13 03:08:27 +0000896 } else
Jakob Stoklund Olesenc94c9672011-09-15 18:22:52 +0000897 ++NumReloads;
Jakob Stoklund Olesen8656a452010-07-01 00:13:04 +0000898 return true;
899}
900
Mark Lacey9d8103d2013-08-14 23:50:16 +0000901void InlineSpiller::insertReload(unsigned NewVReg,
Jakob Stoklund Olesen9f294a92011-04-18 20:23:27 +0000902 SlotIndex Idx,
Jakob Stoklund Olesenbde96ad2010-06-30 23:03:52 +0000903 MachineBasicBlock::iterator MI) {
904 MachineBasicBlock &MBB = *MI->getParent();
Mark Lacey9d8103d2013-08-14 23:50:16 +0000905
Michael Liao8d6ea2d2019-07-05 20:23:59 +0000906 MachineInstrSpan MIS(MI, &MBB);
Mark Lacey9d8103d2013-08-14 23:50:16 +0000907 TII.loadRegFromStackSlot(MBB, MI, NewVReg, StackSlot,
908 MRI.getRegClass(NewVReg), &TRI);
909
910 LIS.InsertMachineInstrRangeInMaps(MIS.begin(), MI);
911
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000912 LLVM_DEBUG(dumpMachineInstrRangeWithSlotIndex(MIS.begin(), MI, LIS, "reload",
913 NewVReg));
Jakob Stoklund Olesenc5a8c082011-05-05 17:22:53 +0000914 ++NumReloads;
Jakob Stoklund Olesenbde96ad2010-06-30 23:03:52 +0000915}
916
Quentin Colombetc6689352017-06-05 23:51:27 +0000917/// Check if \p Def fully defines a VReg with an undefined value.
918/// If that's the case, that means the value of VReg is actually
919/// not relevant.
920static bool isFullUndefDef(const MachineInstr &Def) {
921 if (!Def.isImplicitDef())
922 return false;
923 assert(Def.getNumOperands() == 1 &&
924 "Implicit def with more than one definition");
925 // We can say that the VReg defined by Def is undef, only if it is
926 // fully defined by Def. Otherwise, some of the lanes may not be
927 // undef and the value of the VReg matters.
928 return !Def.getOperand(0).getSubReg();
929}
930
Mark Lacey9d8103d2013-08-14 23:50:16 +0000931/// insertSpill - Insert a spill of NewVReg after MI.
932void InlineSpiller::insertSpill(unsigned NewVReg, bool isKill,
933 MachineBasicBlock::iterator MI) {
Jakob Stoklund Olesenbde96ad2010-06-30 23:03:52 +0000934 MachineBasicBlock &MBB = *MI->getParent();
Mark Lacey9d8103d2013-08-14 23:50:16 +0000935
Michael Liao8d6ea2d2019-07-05 20:23:59 +0000936 MachineInstrSpan MIS(MI, &MBB);
Quentin Colombet9e9d6382017-06-07 00:22:07 +0000937 bool IsRealSpill = true;
938 if (isFullUndefDef(*MI)) {
Quentin Colombetc6689352017-06-05 23:51:27 +0000939 // Don't spill undef value.
940 // Anything works for undef, in particular keeping the memory
941 // uninitialized is a viable option and it saves code size and
942 // run time.
943 BuildMI(MBB, std::next(MI), MI->getDebugLoc(), TII.get(TargetOpcode::KILL))
944 .addReg(NewVReg, getKillRegState(isKill));
Quentin Colombet9e9d6382017-06-07 00:22:07 +0000945 IsRealSpill = false;
946 } else
Quentin Colombetc6689352017-06-05 23:51:27 +0000947 TII.storeRegToStackSlot(MBB, std::next(MI), NewVReg, isKill, StackSlot,
948 MRI.getRegClass(NewVReg), &TRI);
Mark Lacey9d8103d2013-08-14 23:50:16 +0000949
Benjamin Kramerb6d0bd42014-03-02 12:27:27 +0000950 LIS.InsertMachineInstrRangeInMaps(std::next(MI), MIS.end());
Mark Lacey9d8103d2013-08-14 23:50:16 +0000951
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000952 LLVM_DEBUG(dumpMachineInstrRangeWithSlotIndex(std::next(MI), MIS.end(), LIS,
953 "spill"));
Jakob Stoklund Olesenc5a8c082011-05-05 17:22:53 +0000954 ++NumSpills;
Quentin Colombet9e9d6382017-06-07 00:22:07 +0000955 if (IsRealSpill)
956 HSpiller.addToMergeableSpills(*std::next(MI), StackSlot, Original);
Jakob Stoklund Olesenbde96ad2010-06-30 23:03:52 +0000957}
958
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +0000959/// spillAroundUses - insert spill code around each use of Reg.
960void InlineSpiller::spillAroundUses(unsigned Reg) {
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000961 LLVM_DEBUG(dbgs() << "spillAroundUses " << printReg(Reg) << '\n');
Jakob Stoklund Olesena00bab22011-03-14 19:56:43 +0000962 LiveInterval &OldLI = LIS.getInterval(Reg);
Jakob Stoklund Olesenf8889112010-06-29 23:58:39 +0000963
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +0000964 // Iterate over instructions using Reg.
Owen Andersonabb90c92014-03-13 06:02:25 +0000965 for (MachineRegisterInfo::reg_bundle_iterator
966 RegI = MRI.reg_bundle_begin(Reg), E = MRI.reg_bundle_end();
967 RegI != E; ) {
Owen Andersonec5d4802014-03-14 05:02:18 +0000968 MachineInstr *MI = &*(RegI++);
Jakob Stoklund Olesenf8889112010-06-29 23:58:39 +0000969
Jakob Stoklund Olesencf6c5c92010-07-02 19:54:40 +0000970 // Debug values are not allowed to affect codegen.
Shiva Chen21eab932018-05-16 02:57:26 +0000971 if (MI->isDebugValue()) {
Jakob Stoklund Olesencf6c5c92010-07-02 19:54:40 +0000972 // Modify DBG_VALUE now that the value is in a spill slot.
David Blaikie0252265b2013-06-16 20:34:15 +0000973 MachineBasicBlock *MBB = MI->getParent();
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000974 LLVM_DEBUG(dbgs() << "Modifying debug info due to spill:\t" << *MI);
Adrian Prantl6825fb62017-04-18 01:21:53 +0000975 buildDbgValueForSpill(*MBB, MI, *MI, StackSlot);
976 MBB->erase(MI);
Jakob Stoklund Olesencf6c5c92010-07-02 19:54:40 +0000977 continue;
978 }
979
Shiva Chen21eab932018-05-16 02:57:26 +0000980 assert(!MI->isDebugInstr() && "Did not expect to find a use in debug "
981 "instruction that isn't a DBG_VALUE");
982
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +0000983 // Ignore copies to/from snippets. We'll delete them.
984 if (SnippetCopies.count(MI))
985 continue;
986
Jakob Stoklund Olesen7fd49052010-08-04 22:35:11 +0000987 // Stack slot accesses may coalesce away.
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +0000988 if (coalesceStackAccess(MI, Reg))
Jakob Stoklund Olesen7fd49052010-08-04 22:35:11 +0000989 continue;
990
Jakob Stoklund Olesenf8889112010-06-29 23:58:39 +0000991 // Analyze instruction.
Jakob Stoklund Olesenabe8c092012-03-01 01:43:25 +0000992 SmallVector<std::pair<MachineInstr*, unsigned>, 8> Ops;
Florian Hahn5d062562019-12-02 19:41:09 +0000993 VirtRegInfo RI = AnalyzeVirtRegInBundle(*MI, Reg, &Ops);
Jakob Stoklund Olesenf8889112010-06-29 23:58:39 +0000994
Jakob Stoklund Olesen9f294a92011-04-18 20:23:27 +0000995 // Find the slot index where this instruction reads and writes OldLI.
996 // This is usually the def slot, except for tied early clobbers.
Duncan P. N. Exon Smith3ac9cc62016-02-27 06:40:41 +0000997 SlotIndex Idx = LIS.getInstructionIndex(*MI).getRegSlot();
Jakob Stoklund Olesen90b5e562011-11-13 20:45:27 +0000998 if (VNInfo *VNI = OldLI.getVNInfoAt(Idx.getRegSlot(true)))
Jakob Stoklund Olesen9f294a92011-04-18 20:23:27 +0000999 if (SlotIndex::isSameInstr(Idx, VNI->def))
1000 Idx = VNI->def;
1001
Jakob Stoklund Olesen27320cb2011-03-18 04:23:06 +00001002 // Check for a sibling copy.
Duncan P. N. Exon Smith9cfc75c2016-06-30 00:01:54 +00001003 unsigned SibReg = isFullCopyOf(*MI, Reg);
Jakob Stoklund Olesene55003f2011-03-20 05:44:58 +00001004 if (SibReg && isSibling(SibReg)) {
Jakob Stoklund Olesen31a0b5e2011-05-11 18:25:10 +00001005 // This may actually be a copy between snippets.
1006 if (isRegToSpill(SibReg)) {
Nicola Zaghend34e60c2018-05-14 12:53:11 +00001007 LLVM_DEBUG(dbgs() << "Found new snippet copy: " << *MI);
Jakob Stoklund Olesen31a0b5e2011-05-11 18:25:10 +00001008 SnippetCopies.insert(MI);
1009 continue;
1010 }
Jakob Stoklund Olesenabe8c092012-03-01 01:43:25 +00001011 if (RI.Writes) {
Wei Mi9a16d652016-04-13 03:08:27 +00001012 if (hoistSpillInsideBB(OldLI, *MI)) {
Jakob Stoklund Olesene55003f2011-03-20 05:44:58 +00001013 // This COPY is now dead, the value is already in the stack slot.
1014 MI->getOperand(0).setIsDead();
1015 DeadDefs.push_back(MI);
1016 continue;
1017 }
1018 } else {
1019 // This is a reload for a sib-reg copy. Drop spills downstream.
Jakob Stoklund Olesene55003f2011-03-20 05:44:58 +00001020 LiveInterval &SibLI = LIS.getInterval(SibReg);
1021 eliminateRedundantSpills(SibLI, SibLI.getVNInfoAt(Idx));
1022 // The COPY will fold to a reload below.
1023 }
Jakob Stoklund Olesen27320cb2011-03-18 04:23:06 +00001024 }
1025
Jakob Stoklund Olesen96037182010-07-02 17:44:57 +00001026 // Attempt to fold memory ops.
Jakob Stoklund Olesenabe8c092012-03-01 01:43:25 +00001027 if (foldMemoryOperand(Ops))
Jakob Stoklund Olesen96037182010-07-02 17:44:57 +00001028 continue;
1029
Mark Lacey9d8103d2013-08-14 23:50:16 +00001030 // Create a new virtual register for spill/fill.
Jakob Stoklund Olesenf8889112010-06-29 23:58:39 +00001031 // FIXME: Infer regclass from instruction alone.
Mark Lacey9d8103d2013-08-14 23:50:16 +00001032 unsigned NewVReg = Edit->createFrom(Reg);
Jakob Stoklund Olesenf8889112010-06-29 23:58:39 +00001033
Jakob Stoklund Olesenabe8c092012-03-01 01:43:25 +00001034 if (RI.Reads)
Mark Lacey9d8103d2013-08-14 23:50:16 +00001035 insertReload(NewVReg, Idx, MI);
Jakob Stoklund Olesenf8889112010-06-29 23:58:39 +00001036
1037 // Rewrite instruction operands.
1038 bool hasLiveDef = false;
Craig Topper73275a22015-12-24 05:20:40 +00001039 for (const auto &OpPair : Ops) {
1040 MachineOperand &MO = OpPair.first->getOperand(OpPair.second);
Mark Lacey9d8103d2013-08-14 23:50:16 +00001041 MO.setReg(NewVReg);
Jakob Stoklund Olesenf8889112010-06-29 23:58:39 +00001042 if (MO.isUse()) {
Craig Topper73275a22015-12-24 05:20:40 +00001043 if (!OpPair.first->isRegTiedToDefOperand(OpPair.second))
Jakob Stoklund Olesenf8889112010-06-29 23:58:39 +00001044 MO.setIsKill();
1045 } else {
1046 if (!MO.isDead())
1047 hasLiveDef = true;
1048 }
1049 }
Nicola Zaghend34e60c2018-05-14 12:53:11 +00001050 LLVM_DEBUG(dbgs() << "\trewrite: " << Idx << '\t' << *MI << '\n');
Jakob Stoklund Olesenf8889112010-06-29 23:58:39 +00001051
Jakob Stoklund Olesenf8889112010-06-29 23:58:39 +00001052 // FIXME: Use a second vreg if instruction has no tied ops.
Mark Lacey9d8103d2013-08-14 23:50:16 +00001053 if (RI.Writes)
Jakob Stoklund Olesenabe8c092012-03-01 01:43:25 +00001054 if (hasLiveDef)
Mark Lacey9d8103d2013-08-14 23:50:16 +00001055 insertSpill(NewVReg, true, MI);
Jakob Stoklund Olesenf8889112010-06-29 23:58:39 +00001056 }
1057}
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +00001058
Jakob Stoklund Olesene991f722011-03-29 21:20:19 +00001059/// spillAll - Spill all registers remaining after rematerialization.
1060void InlineSpiller::spillAll() {
1061 // Update LiveStacks now that we are committed to spilling.
1062 if (StackSlot == VirtRegMap::NO_STACK_SLOT) {
1063 StackSlot = VRM.assignVirt2StackSlot(Original);
1064 StackInt = &LSS.getOrCreateInterval(StackSlot, MRI.getRegClass(Original));
Jakob Stoklund Olesenad6b22e2012-02-04 05:20:49 +00001065 StackInt->getNextValue(SlotIndex(), LSS.getVNInfoAllocator());
Jakob Stoklund Olesene991f722011-03-29 21:20:19 +00001066 } else
1067 StackInt = &LSS.getInterval(StackSlot);
1068
1069 if (Original != Edit->getReg())
1070 VRM.assignVirt2StackSlot(Edit->getReg(), StackSlot);
1071
1072 assert(StackInt->getNumValNums() == 1 && "Bad stack interval values");
Craig Topper73275a22015-12-24 05:20:40 +00001073 for (unsigned Reg : RegsToSpill)
1074 StackInt->MergeSegmentsInAsValue(LIS.getInterval(Reg),
Matthias Braun13ddb7c2013-10-10 21:28:43 +00001075 StackInt->getValNumInfo(0));
Nicola Zaghend34e60c2018-05-14 12:53:11 +00001076 LLVM_DEBUG(dbgs() << "Merged spilled regs: " << *StackInt << '\n');
Jakob Stoklund Olesene991f722011-03-29 21:20:19 +00001077
1078 // Spill around uses of all RegsToSpill.
Craig Topper73275a22015-12-24 05:20:40 +00001079 for (unsigned Reg : RegsToSpill)
1080 spillAroundUses(Reg);
Jakob Stoklund Olesene991f722011-03-29 21:20:19 +00001081
1082 // Hoisted spills may cause dead code.
1083 if (!DeadDefs.empty()) {
Nicola Zaghend34e60c2018-05-14 12:53:11 +00001084 LLVM_DEBUG(dbgs() << "Eliminating " << DeadDefs.size() << " dead defs\n");
Wei Mic0223702016-07-08 21:08:09 +00001085 Edit->eliminateDeadDefs(DeadDefs, RegsToSpill, AA);
Jakob Stoklund Olesene991f722011-03-29 21:20:19 +00001086 }
1087
1088 // Finally delete the SnippetCopies.
Craig Topper73275a22015-12-24 05:20:40 +00001089 for (unsigned Reg : RegsToSpill) {
Owen Andersonabb90c92014-03-13 06:02:25 +00001090 for (MachineRegisterInfo::reg_instr_iterator
Craig Topper73275a22015-12-24 05:20:40 +00001091 RI = MRI.reg_instr_begin(Reg), E = MRI.reg_instr_end();
Owen Andersonabb90c92014-03-13 06:02:25 +00001092 RI != E; ) {
Duncan P. N. Exon Smith3ac9cc62016-02-27 06:40:41 +00001093 MachineInstr &MI = *(RI++);
1094 assert(SnippetCopies.count(&MI) && "Remaining use wasn't a snippet copy");
Jakob Stoklund Olesen31a0b5e2011-05-11 18:25:10 +00001095 // FIXME: Do this with a LiveRangeEdit callback.
Jakob Stoklund Olesen31a0b5e2011-05-11 18:25:10 +00001096 LIS.RemoveMachineInstrFromMaps(MI);
Duncan P. N. Exon Smith3ac9cc62016-02-27 06:40:41 +00001097 MI.eraseFromParent();
Jakob Stoklund Olesen31a0b5e2011-05-11 18:25:10 +00001098 }
Jakob Stoklund Olesene991f722011-03-29 21:20:19 +00001099 }
1100
1101 // Delete all spilled registers.
Craig Topper73275a22015-12-24 05:20:40 +00001102 for (unsigned Reg : RegsToSpill)
1103 Edit->eraseVirtReg(Reg);
Jakob Stoklund Olesene991f722011-03-29 21:20:19 +00001104}
1105
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +00001106void InlineSpiller::spill(LiveRangeEdit &edit) {
Jakob Stoklund Olesenc5a8c082011-05-05 17:22:53 +00001107 ++NumSpilledRanges;
Jakob Stoklund Olesena00bab22011-03-14 19:56:43 +00001108 Edit = &edit;
Daniel Sanders2bea69b2019-08-01 23:27:28 +00001109 assert(!Register::isStackSlot(edit.getReg()) &&
1110 "Trying to spill a stack slot.");
Jakob Stoklund Olesena0d5ec12011-03-15 21:13:25 +00001111 // Share a stack slot among all descendants of Original.
1112 Original = VRM.getOriginal(edit.getReg());
1113 StackSlot = VRM.getStackSlot(Original);
Craig Topperc0196b12014-04-14 00:51:57 +00001114 StackInt = nullptr;
Jakob Stoklund Olesena0d5ec12011-03-15 21:13:25 +00001115
Nicola Zaghend34e60c2018-05-14 12:53:11 +00001116 LLVM_DEBUG(dbgs() << "Inline spilling "
1117 << TRI.getRegClassName(MRI.getRegClass(edit.getReg()))
1118 << ':' << edit.getParent() << "\nFrom original "
1119 << printReg(Original) << '\n');
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +00001120 assert(edit.getParent().isSpillable() &&
1121 "Attempting to spill already spilled value.");
Jakob Stoklund Olesen27320cb2011-03-18 04:23:06 +00001122 assert(DeadDefs.empty() && "Previous spill didn't remove dead defs");
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +00001123
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +00001124 collectRegsToSpill();
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +00001125 reMaterializeAll();
1126
1127 // Remat may handle everything.
Jakob Stoklund Olesene991f722011-03-29 21:20:19 +00001128 if (!RegsToSpill.empty())
1129 spillAll();
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +00001130
Benjamin Kramere2a1d892013-06-17 19:00:36 +00001131 Edit->calculateRegClassAndHint(MF, Loops, MBFI);
Jakob Stoklund Olesena86595e2011-03-12 04:17:20 +00001132}
Wei Mi9a16d652016-04-13 03:08:27 +00001133
1134/// Optimizations after all the reg selections and spills are done.
Wei Mi963f2df2016-04-15 23:16:44 +00001135void InlineSpiller::postOptimization() { HSpiller.hoistAllSpills(); }
Wei Mi9a16d652016-04-13 03:08:27 +00001136
1137/// When a spill is inserted, add the spill to MergeableSpills map.
Duncan P. N. Exon Smith91298732016-06-30 23:28:15 +00001138void HoistSpillHelper::addToMergeableSpills(MachineInstr &Spill, int StackSlot,
Wei Mi9a16d652016-04-13 03:08:27 +00001139 unsigned Original) {
Wei Mic0d06642017-09-13 21:41:30 +00001140 BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator();
1141 LiveInterval &OrigLI = LIS.getInterval(Original);
1142 // save a copy of LiveInterval in StackSlotToOrigLI because the original
1143 // LiveInterval may be cleared after all its references are spilled.
1144 if (StackSlotToOrigLI.find(StackSlot) == StackSlotToOrigLI.end()) {
Jonas Devlieghere0eaee542019-08-15 15:54:37 +00001145 auto LI = std::make_unique<LiveInterval>(OrigLI.reg, OrigLI.weight);
Wei Mic0d06642017-09-13 21:41:30 +00001146 LI->assign(OrigLI, Allocator);
1147 StackSlotToOrigLI[StackSlot] = std::move(LI);
1148 }
Duncan P. N. Exon Smith91298732016-06-30 23:28:15 +00001149 SlotIndex Idx = LIS.getInstructionIndex(Spill);
Wei Mic0d06642017-09-13 21:41:30 +00001150 VNInfo *OrigVNI = StackSlotToOrigLI[StackSlot]->getVNInfoAt(Idx.getRegSlot());
Wei Mi9a16d652016-04-13 03:08:27 +00001151 std::pair<int, VNInfo *> MIdx = std::make_pair(StackSlot, OrigVNI);
Duncan P. N. Exon Smith91298732016-06-30 23:28:15 +00001152 MergeableSpills[MIdx].insert(&Spill);
Wei Mi9a16d652016-04-13 03:08:27 +00001153}
1154
1155/// When a spill is removed, remove the spill from MergeableSpills map.
1156/// Return true if the spill is removed successfully.
Duncan P. N. Exon Smith91298732016-06-30 23:28:15 +00001157bool HoistSpillHelper::rmFromMergeableSpills(MachineInstr &Spill,
Wei Mi9a16d652016-04-13 03:08:27 +00001158 int StackSlot) {
Wei Mic0d06642017-09-13 21:41:30 +00001159 auto It = StackSlotToOrigLI.find(StackSlot);
1160 if (It == StackSlotToOrigLI.end())
Wei Mi9a16d652016-04-13 03:08:27 +00001161 return false;
Duncan P. N. Exon Smith91298732016-06-30 23:28:15 +00001162 SlotIndex Idx = LIS.getInstructionIndex(Spill);
Wei Mic0d06642017-09-13 21:41:30 +00001163 VNInfo *OrigVNI = It->second->getVNInfoAt(Idx.getRegSlot());
Wei Mi9a16d652016-04-13 03:08:27 +00001164 std::pair<int, VNInfo *> MIdx = std::make_pair(StackSlot, OrigVNI);
Duncan P. N. Exon Smith91298732016-06-30 23:28:15 +00001165 return MergeableSpills[MIdx].erase(&Spill);
Wei Mi9a16d652016-04-13 03:08:27 +00001166}
1167
1168/// Check BB to see if it is a possible target BB to place a hoisted spill,
1169/// i.e., there should be a living sibling of OrigReg at the insert point.
Wei Mic0d06642017-09-13 21:41:30 +00001170bool HoistSpillHelper::isSpillCandBB(LiveInterval &OrigLI, VNInfo &OrigVNI,
Wei Mi9a16d652016-04-13 03:08:27 +00001171 MachineBasicBlock &BB, unsigned &LiveReg) {
1172 SlotIndex Idx;
Wei Mic0d06642017-09-13 21:41:30 +00001173 unsigned OrigReg = OrigLI.reg;
Wei Mif3c8f532016-05-23 19:39:19 +00001174 MachineBasicBlock::iterator MI = IPA.getLastInsertPointIter(OrigLI, BB);
Wei Mi9a16d652016-04-13 03:08:27 +00001175 if (MI != BB.end())
1176 Idx = LIS.getInstructionIndex(*MI);
1177 else
1178 Idx = LIS.getMBBEndIdx(&BB).getPrevSlot();
1179 SmallSetVector<unsigned, 16> &Siblings = Virt2SiblingsMap[OrigReg];
Wei Mic0d06642017-09-13 21:41:30 +00001180 assert(OrigLI.getVNInfoAt(Idx) == &OrigVNI && "Unexpected VNI");
Wei Mi9a16d652016-04-13 03:08:27 +00001181
1182 for (auto const SibReg : Siblings) {
1183 LiveInterval &LI = LIS.getInterval(SibReg);
1184 VNInfo *VNI = LI.getVNInfoAt(Idx);
1185 if (VNI) {
1186 LiveReg = SibReg;
1187 return true;
1188 }
1189 }
1190 return false;
1191}
1192
Eric Christopher75d661a2016-05-04 21:45:36 +00001193/// Remove redundant spills in the same BB. Save those redundant spills in
Wei Mi9a16d652016-04-13 03:08:27 +00001194/// SpillsToRm, and save the spill to keep and its BB in SpillBBToSpill map.
Wei Mi9a16d652016-04-13 03:08:27 +00001195void HoistSpillHelper::rmRedundantSpills(
1196 SmallPtrSet<MachineInstr *, 16> &Spills,
1197 SmallVectorImpl<MachineInstr *> &SpillsToRm,
1198 DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill) {
1199 // For each spill saw, check SpillBBToSpill[] and see if its BB already has
1200 // another spill inside. If a BB contains more than one spill, only keep the
1201 // earlier spill with smaller SlotIndex.
1202 for (const auto CurrentSpill : Spills) {
1203 MachineBasicBlock *Block = CurrentSpill->getParent();
Bjorn Pettersson3c6ce732017-01-04 09:41:56 +00001204 MachineDomTreeNode *Node = MDT.getBase().getNode(Block);
Wei Mi9a16d652016-04-13 03:08:27 +00001205 MachineInstr *PrevSpill = SpillBBToSpill[Node];
1206 if (PrevSpill) {
1207 SlotIndex PIdx = LIS.getInstructionIndex(*PrevSpill);
1208 SlotIndex CIdx = LIS.getInstructionIndex(*CurrentSpill);
1209 MachineInstr *SpillToRm = (CIdx > PIdx) ? CurrentSpill : PrevSpill;
1210 MachineInstr *SpillToKeep = (CIdx > PIdx) ? PrevSpill : CurrentSpill;
1211 SpillsToRm.push_back(SpillToRm);
Bjorn Pettersson3c6ce732017-01-04 09:41:56 +00001212 SpillBBToSpill[MDT.getBase().getNode(Block)] = SpillToKeep;
Wei Mi9a16d652016-04-13 03:08:27 +00001213 } else {
Bjorn Pettersson3c6ce732017-01-04 09:41:56 +00001214 SpillBBToSpill[MDT.getBase().getNode(Block)] = CurrentSpill;
Wei Mi9a16d652016-04-13 03:08:27 +00001215 }
1216 }
1217 for (const auto SpillToRm : SpillsToRm)
1218 Spills.erase(SpillToRm);
1219}
1220
1221/// Starting from \p Root find a top-down traversal order of the dominator
1222/// tree to visit all basic blocks containing the elements of \p Spills.
1223/// Redundant spills will be found and put into \p SpillsToRm at the same
1224/// time. \p SpillBBToSpill will be populated as part of the process and
1225/// maps a basic block to the first store occurring in the basic block.
1226/// \post SpillsToRm.union(Spills\@post) == Spills\@pre
Wei Mi9a16d652016-04-13 03:08:27 +00001227void HoistSpillHelper::getVisitOrders(
1228 MachineBasicBlock *Root, SmallPtrSet<MachineInstr *, 16> &Spills,
1229 SmallVectorImpl<MachineDomTreeNode *> &Orders,
1230 SmallVectorImpl<MachineInstr *> &SpillsToRm,
1231 DenseMap<MachineDomTreeNode *, unsigned> &SpillsToKeep,
1232 DenseMap<MachineDomTreeNode *, MachineInstr *> &SpillBBToSpill) {
1233 // The set contains all the possible BB nodes to which we may hoist
1234 // original spills.
1235 SmallPtrSet<MachineDomTreeNode *, 8> WorkSet;
1236 // Save the BB nodes on the path from the first BB node containing
Eric Christopher75d661a2016-05-04 21:45:36 +00001237 // non-redundant spill to the Root node.
Wei Mi9a16d652016-04-13 03:08:27 +00001238 SmallPtrSet<MachineDomTreeNode *, 8> NodesOnPath;
1239 // All the spills to be hoisted must originate from a single def instruction
1240 // to the OrigReg. It means the def instruction should dominate all the spills
1241 // to be hoisted. We choose the BB where the def instruction is located as
1242 // the Root.
1243 MachineDomTreeNode *RootIDomNode = MDT[Root]->getIDom();
1244 // For every node on the dominator tree with spill, walk up on the dominator
1245 // tree towards the Root node until it is reached. If there is other node
1246 // containing spill in the middle of the path, the previous spill saw will
Eric Christopher75d661a2016-05-04 21:45:36 +00001247 // be redundant and the node containing it will be removed. All the nodes on
1248 // the path starting from the first node with non-redundant spill to the Root
Wei Mi9a16d652016-04-13 03:08:27 +00001249 // node will be added to the WorkSet, which will contain all the possible
1250 // locations where spills may be hoisted to after the loop below is done.
1251 for (const auto Spill : Spills) {
1252 MachineBasicBlock *Block = Spill->getParent();
1253 MachineDomTreeNode *Node = MDT[Block];
1254 MachineInstr *SpillToRm = nullptr;
1255 while (Node != RootIDomNode) {
1256 // If Node dominates Block, and it already contains a spill, the spill in
Eric Christopher75d661a2016-05-04 21:45:36 +00001257 // Block will be redundant.
Wei Mi9a16d652016-04-13 03:08:27 +00001258 if (Node != MDT[Block] && SpillBBToSpill[Node]) {
1259 SpillToRm = SpillBBToSpill[MDT[Block]];
1260 break;
1261 /// If we see the Node already in WorkSet, the path from the Node to
1262 /// the Root node must already be traversed by another spill.
1263 /// Then no need to repeat.
1264 } else if (WorkSet.count(Node)) {
1265 break;
1266 } else {
1267 NodesOnPath.insert(Node);
1268 }
1269 Node = Node->getIDom();
1270 }
1271 if (SpillToRm) {
1272 SpillsToRm.push_back(SpillToRm);
1273 } else {
1274 // Add a BB containing the original spills to SpillsToKeep -- i.e.,
1275 // set the initial status before hoisting start. The value of BBs
1276 // containing original spills is set to 0, in order to descriminate
1277 // with BBs containing hoisted spills which will be inserted to
1278 // SpillsToKeep later during hoisting.
1279 SpillsToKeep[MDT[Block]] = 0;
1280 WorkSet.insert(NodesOnPath.begin(), NodesOnPath.end());
1281 }
1282 NodesOnPath.clear();
1283 }
1284
1285 // Sort the nodes in WorkSet in top-down order and save the nodes
1286 // in Orders. Orders will be used for hoisting in runHoistSpills.
1287 unsigned idx = 0;
Bjorn Pettersson3c6ce732017-01-04 09:41:56 +00001288 Orders.push_back(MDT.getBase().getNode(Root));
Wei Mi9a16d652016-04-13 03:08:27 +00001289 do {
1290 MachineDomTreeNode *Node = Orders[idx++];
1291 const std::vector<MachineDomTreeNode *> &Children = Node->getChildren();
1292 unsigned NumChildren = Children.size();
1293 for (unsigned i = 0; i != NumChildren; ++i) {
1294 MachineDomTreeNode *Child = Children[i];
1295 if (WorkSet.count(Child))
1296 Orders.push_back(Child);
1297 }
1298 } while (idx != Orders.size());
1299 assert(Orders.size() == WorkSet.size() &&
1300 "Orders have different size with WorkSet");
1301
1302#ifndef NDEBUG
Nicola Zaghend34e60c2018-05-14 12:53:11 +00001303 LLVM_DEBUG(dbgs() << "Orders size is " << Orders.size() << "\n");
Wei Mi9a16d652016-04-13 03:08:27 +00001304 SmallVector<MachineDomTreeNode *, 32>::reverse_iterator RIt = Orders.rbegin();
1305 for (; RIt != Orders.rend(); RIt++)
Nicola Zaghend34e60c2018-05-14 12:53:11 +00001306 LLVM_DEBUG(dbgs() << "BB" << (*RIt)->getBlock()->getNumber() << ",");
1307 LLVM_DEBUG(dbgs() << "\n");
Wei Mi9a16d652016-04-13 03:08:27 +00001308#endif
1309}
1310
1311/// Try to hoist spills according to BB hotness. The spills to removed will
1312/// be saved in \p SpillsToRm. The spills to be inserted will be saved in
1313/// \p SpillsToIns.
Wei Mi9a16d652016-04-13 03:08:27 +00001314void HoistSpillHelper::runHoistSpills(
Wei Mic0d06642017-09-13 21:41:30 +00001315 LiveInterval &OrigLI, VNInfo &OrigVNI,
1316 SmallPtrSet<MachineInstr *, 16> &Spills,
Wei Mi9a16d652016-04-13 03:08:27 +00001317 SmallVectorImpl<MachineInstr *> &SpillsToRm,
1318 DenseMap<MachineBasicBlock *, unsigned> &SpillsToIns) {
1319 // Visit order of dominator tree nodes.
1320 SmallVector<MachineDomTreeNode *, 32> Orders;
1321 // SpillsToKeep contains all the nodes where spills are to be inserted
1322 // during hoisting. If the spill to be inserted is an original spill
1323 // (not a hoisted one), the value of the map entry is 0. If the spill
1324 // is a hoisted spill, the value of the map entry is the VReg to be used
1325 // as the source of the spill.
1326 DenseMap<MachineDomTreeNode *, unsigned> SpillsToKeep;
1327 // Map from BB to the first spill inside of it.
1328 DenseMap<MachineDomTreeNode *, MachineInstr *> SpillBBToSpill;
1329
1330 rmRedundantSpills(Spills, SpillsToRm, SpillBBToSpill);
1331
1332 MachineBasicBlock *Root = LIS.getMBBFromIndex(OrigVNI.def);
1333 getVisitOrders(Root, Spills, Orders, SpillsToRm, SpillsToKeep,
1334 SpillBBToSpill);
1335
1336 // SpillsInSubTreeMap keeps the map from a dom tree node to a pair of
1337 // nodes set and the cost of all the spills inside those nodes.
1338 // The nodes set are the locations where spills are to be inserted
1339 // in the subtree of current node.
Eugene Zelenko900b6332017-08-29 22:32:07 +00001340 using NodesCostPair =
1341 std::pair<SmallPtrSet<MachineDomTreeNode *, 16>, BlockFrequency>;
Wei Mi9a16d652016-04-13 03:08:27 +00001342 DenseMap<MachineDomTreeNode *, NodesCostPair> SpillsInSubTreeMap;
Eugene Zelenko900b6332017-08-29 22:32:07 +00001343
Wei Mi9a16d652016-04-13 03:08:27 +00001344 // Iterate Orders set in reverse order, which will be a bottom-up order
1345 // in the dominator tree. Once we visit a dom tree node, we know its
1346 // children have already been visited and the spill locations in the
1347 // subtrees of all the children have been determined.
1348 SmallVector<MachineDomTreeNode *, 32>::reverse_iterator RIt = Orders.rbegin();
1349 for (; RIt != Orders.rend(); RIt++) {
1350 MachineBasicBlock *Block = (*RIt)->getBlock();
1351
1352 // If Block contains an original spill, simply continue.
1353 if (SpillsToKeep.find(*RIt) != SpillsToKeep.end() && !SpillsToKeep[*RIt]) {
1354 SpillsInSubTreeMap[*RIt].first.insert(*RIt);
1355 // SpillsInSubTreeMap[*RIt].second contains the cost of spill.
1356 SpillsInSubTreeMap[*RIt].second = MBFI.getBlockFreq(Block);
1357 continue;
1358 }
1359
1360 // Collect spills in subtree of current node (*RIt) to
1361 // SpillsInSubTreeMap[*RIt].first.
1362 const std::vector<MachineDomTreeNode *> &Children = (*RIt)->getChildren();
1363 unsigned NumChildren = Children.size();
1364 for (unsigned i = 0; i != NumChildren; ++i) {
1365 MachineDomTreeNode *Child = Children[i];
1366 if (SpillsInSubTreeMap.find(Child) == SpillsInSubTreeMap.end())
1367 continue;
1368 // The stmt "SpillsInSubTree = SpillsInSubTreeMap[*RIt].first" below
1369 // should be placed before getting the begin and end iterators of
1370 // SpillsInSubTreeMap[Child].first, or else the iterators may be
1371 // invalidated when SpillsInSubTreeMap[*RIt] is seen the first time
1372 // and the map grows and then the original buckets in the map are moved.
1373 SmallPtrSet<MachineDomTreeNode *, 16> &SpillsInSubTree =
1374 SpillsInSubTreeMap[*RIt].first;
1375 BlockFrequency &SubTreeCost = SpillsInSubTreeMap[*RIt].second;
1376 SubTreeCost += SpillsInSubTreeMap[Child].second;
1377 auto BI = SpillsInSubTreeMap[Child].first.begin();
1378 auto EI = SpillsInSubTreeMap[Child].first.end();
1379 SpillsInSubTree.insert(BI, EI);
1380 SpillsInSubTreeMap.erase(Child);
1381 }
1382
1383 SmallPtrSet<MachineDomTreeNode *, 16> &SpillsInSubTree =
1384 SpillsInSubTreeMap[*RIt].first;
1385 BlockFrequency &SubTreeCost = SpillsInSubTreeMap[*RIt].second;
1386 // No spills in subtree, simply continue.
1387 if (SpillsInSubTree.empty())
1388 continue;
1389
1390 // Check whether Block is a possible candidate to insert spill.
1391 unsigned LiveReg = 0;
Wei Mic0d06642017-09-13 21:41:30 +00001392 if (!isSpillCandBB(OrigLI, OrigVNI, *Block, LiveReg))
Wei Mi9a16d652016-04-13 03:08:27 +00001393 continue;
1394
1395 // If there are multiple spills that could be merged, bias a little
1396 // to hoist the spill.
1397 BranchProbability MarginProb = (SpillsInSubTree.size() > 1)
1398 ? BranchProbability(9, 10)
1399 : BranchProbability(1, 1);
1400 if (SubTreeCost > MBFI.getBlockFreq(Block) * MarginProb) {
1401 // Hoist: Move spills to current Block.
1402 for (const auto SpillBB : SpillsInSubTree) {
1403 // When SpillBB is a BB contains original spill, insert the spill
1404 // to SpillsToRm.
1405 if (SpillsToKeep.find(SpillBB) != SpillsToKeep.end() &&
1406 !SpillsToKeep[SpillBB]) {
1407 MachineInstr *SpillToRm = SpillBBToSpill[SpillBB];
1408 SpillsToRm.push_back(SpillToRm);
1409 }
1410 // SpillBB will not contain spill anymore, remove it from SpillsToKeep.
1411 SpillsToKeep.erase(SpillBB);
1412 }
1413 // Current Block is the BB containing the new hoisted spill. Add it to
1414 // SpillsToKeep. LiveReg is the source of the new spill.
1415 SpillsToKeep[*RIt] = LiveReg;
Nicola Zaghend34e60c2018-05-14 12:53:11 +00001416 LLVM_DEBUG({
Wei Mi9a16d652016-04-13 03:08:27 +00001417 dbgs() << "spills in BB: ";
1418 for (const auto Rspill : SpillsInSubTree)
1419 dbgs() << Rspill->getBlock()->getNumber() << " ";
1420 dbgs() << "were promoted to BB" << (*RIt)->getBlock()->getNumber()
1421 << "\n";
1422 });
1423 SpillsInSubTree.clear();
1424 SpillsInSubTree.insert(*RIt);
1425 SubTreeCost = MBFI.getBlockFreq(Block);
1426 }
1427 }
1428 // For spills in SpillsToKeep with LiveReg set (i.e., not original spill),
1429 // save them to SpillsToIns.
Mark de Wever8dc7b982020-01-01 17:23:21 +01001430 for (const auto &Ent : SpillsToKeep) {
Wei Mi9a16d652016-04-13 03:08:27 +00001431 if (Ent.second)
1432 SpillsToIns[Ent.first->getBlock()] = Ent.second;
1433 }
1434}
1435
Eric Christopher75d661a2016-05-04 21:45:36 +00001436/// For spills with equal values, remove redundant spills and hoist those left
Wei Mi9a16d652016-04-13 03:08:27 +00001437/// to less hot spots.
1438///
1439/// Spills with equal values will be collected into the same set in
1440/// MergeableSpills when spill is inserted. These equal spills are originated
Eric Christopher75d661a2016-05-04 21:45:36 +00001441/// from the same defining instruction and are dominated by the instruction.
1442/// Before hoisting all the equal spills, redundant spills inside in the same
1443/// BB are first marked to be deleted. Then starting from the spills left, walk
1444/// up on the dominator tree towards the Root node where the define instruction
Wei Mi9a16d652016-04-13 03:08:27 +00001445/// is located, mark the dominated spills to be deleted along the way and
1446/// collect the BB nodes on the path from non-dominated spills to the define
1447/// instruction into a WorkSet. The nodes in WorkSet are the candidate places
Eric Christopher75d661a2016-05-04 21:45:36 +00001448/// where we are considering to hoist the spills. We iterate the WorkSet in
1449/// bottom-up order, and for each node, we will decide whether to hoist spills
1450/// inside its subtree to that node. In this way, we can get benefit locally
1451/// even if hoisting all the equal spills to one cold place is impossible.
Wei Mi963f2df2016-04-15 23:16:44 +00001452void HoistSpillHelper::hoistAllSpills() {
1453 SmallVector<unsigned, 4> NewVRegs;
1454 LiveRangeEdit Edit(nullptr, NewVRegs, MF, LIS, &VRM, this);
1455
Wei Mi9a16d652016-04-13 03:08:27 +00001456 for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) {
Daniel Sanders2bea69b2019-08-01 23:27:28 +00001457 unsigned Reg = Register::index2VirtReg(i);
Wei Mi9a16d652016-04-13 03:08:27 +00001458 unsigned Original = VRM.getPreSplitReg(Reg);
1459 if (!MRI.def_empty(Reg))
1460 Virt2SiblingsMap[Original].insert(Reg);
1461 }
1462
1463 // Each entry in MergeableSpills contains a spill set with equal values.
1464 for (auto &Ent : MergeableSpills) {
1465 int Slot = Ent.first.first;
Wei Mic0d06642017-09-13 21:41:30 +00001466 LiveInterval &OrigLI = *StackSlotToOrigLI[Slot];
Wei Mi9a16d652016-04-13 03:08:27 +00001467 VNInfo *OrigVNI = Ent.first.second;
1468 SmallPtrSet<MachineInstr *, 16> &EqValSpills = Ent.second;
1469 if (Ent.second.empty())
1470 continue;
1471
Nicola Zaghend34e60c2018-05-14 12:53:11 +00001472 LLVM_DEBUG({
Wei Mi9a16d652016-04-13 03:08:27 +00001473 dbgs() << "\nFor Slot" << Slot << " and VN" << OrigVNI->id << ":\n"
1474 << "Equal spills in BB: ";
1475 for (const auto spill : EqValSpills)
1476 dbgs() << spill->getParent()->getNumber() << " ";
1477 dbgs() << "\n";
1478 });
1479
1480 // SpillsToRm is the spill set to be removed from EqValSpills.
1481 SmallVector<MachineInstr *, 16> SpillsToRm;
1482 // SpillsToIns is the spill set to be newly inserted after hoisting.
1483 DenseMap<MachineBasicBlock *, unsigned> SpillsToIns;
1484
Wei Mic0d06642017-09-13 21:41:30 +00001485 runHoistSpills(OrigLI, *OrigVNI, EqValSpills, SpillsToRm, SpillsToIns);
Wei Mi9a16d652016-04-13 03:08:27 +00001486
Nicola Zaghend34e60c2018-05-14 12:53:11 +00001487 LLVM_DEBUG({
Wei Mi9a16d652016-04-13 03:08:27 +00001488 dbgs() << "Finally inserted spills in BB: ";
Mark de Wever8dc7b982020-01-01 17:23:21 +01001489 for (const auto &Ispill : SpillsToIns)
Wei Mi9a16d652016-04-13 03:08:27 +00001490 dbgs() << Ispill.first->getNumber() << " ";
1491 dbgs() << "\nFinally removed spills in BB: ";
1492 for (const auto Rspill : SpillsToRm)
1493 dbgs() << Rspill->getParent()->getNumber() << " ";
1494 dbgs() << "\n";
1495 });
1496
1497 // Stack live range update.
1498 LiveInterval &StackIntvl = LSS.getInterval(Slot);
Wei Mi8c4136b2016-05-11 22:37:43 +00001499 if (!SpillsToIns.empty() || !SpillsToRm.empty())
Wei Mi9a16d652016-04-13 03:08:27 +00001500 StackIntvl.MergeValueInAsValue(OrigLI, OrigVNI,
1501 StackIntvl.getValNumInfo(0));
Wei Mi9a16d652016-04-13 03:08:27 +00001502
1503 // Insert hoisted spills.
Mark de Wever8dc7b982020-01-01 17:23:21 +01001504 for (auto const &Insert : SpillsToIns) {
Wei Mi9a16d652016-04-13 03:08:27 +00001505 MachineBasicBlock *BB = Insert.first;
1506 unsigned LiveReg = Insert.second;
Wei Mif3c8f532016-05-23 19:39:19 +00001507 MachineBasicBlock::iterator MI = IPA.getLastInsertPointIter(OrigLI, *BB);
Wei Mi9a16d652016-04-13 03:08:27 +00001508 TII.storeRegToStackSlot(*BB, MI, LiveReg, false, Slot,
1509 MRI.getRegClass(LiveReg), &TRI);
1510 LIS.InsertMachineInstrRangeInMaps(std::prev(MI), MI);
1511 ++NumSpills;
1512 }
1513
Eric Christopher75d661a2016-05-04 21:45:36 +00001514 // Remove redundant spills or change them to dead instructions.
Wei Mi9a16d652016-04-13 03:08:27 +00001515 NumSpills -= SpillsToRm.size();
1516 for (auto const RMEnt : SpillsToRm) {
1517 RMEnt->setDesc(TII.get(TargetOpcode::KILL));
1518 for (unsigned i = RMEnt->getNumOperands(); i; --i) {
1519 MachineOperand &MO = RMEnt->getOperand(i - 1);
1520 if (MO.isReg() && MO.isImplicit() && MO.isDef() && !MO.isDead())
1521 RMEnt->RemoveOperand(i - 1);
1522 }
1523 }
Wei Mic0223702016-07-08 21:08:09 +00001524 Edit.eliminateDeadDefs(SpillsToRm, None, AA);
Wei Mi9a16d652016-04-13 03:08:27 +00001525 }
1526}
Wei Mi963f2df2016-04-15 23:16:44 +00001527
1528/// For VirtReg clone, the \p New register should have the same physreg or
1529/// stackslot as the \p old register.
1530void HoistSpillHelper::LRE_DidCloneVirtReg(unsigned New, unsigned Old) {
1531 if (VRM.hasPhys(Old))
1532 VRM.assignVirt2Phys(New, VRM.getPhys(Old));
1533 else if (VRM.getStackSlot(Old) != VirtRegMap::NO_STACK_SLOT)
1534 VRM.assignVirt2StackSlot(New, VRM.getStackSlot(Old));
1535 else
1536 llvm_unreachable("VReg should be assigned either physreg or stackslot");
1537}