1//===- ShrinkWrap.cpp - Compute safe point for prolog/epilog insertion ----===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This pass looks for safe point where the prologue and epilogue can be
10// inserted.
11// The safe point for the prologue (resp. epilogue) is called Save
12// (resp. Restore).
13// A point is safe for prologue (resp. epilogue) if and only if
14// it 1) dominates (resp. post-dominates) all the frame related operations and
15// between 2) two executions of the Save (resp. Restore) point there is an
16// execution of the Restore (resp. Save) point.
17//
18// For instance, the following points are safe:
19// for (int i = 0; i < 10; ++i) {
20// Save
21// ...
22// Restore
23// }
24// Indeed, the execution looks like Save -> Restore -> Save -> Restore ...
25// And the following points are not:
26// for (int i = 0; i < 10; ++i) {
27// Save
28// ...
29// }
30// for (int i = 0; i < 10; ++i) {
31// ...
32// Restore
33// }
34// Indeed, the execution looks like Save -> Save -> ... -> Restore -> Restore.
35//
36// This pass also ensures that the safe points are 3) cheaper than the regular
37// entry and exits blocks.
38//
39// Property #1 is ensured via the use of MachineDominatorTree and
40// MachinePostDominatorTree.
41// Property #2 is ensured via property #1 and MachineLoopInfo, i.e., both
42// points must be in the same loop.
43// Property #3 is ensured via the MachineBlockFrequencyInfo.
44//
45// If this pass found points matching all these properties, then
46// MachineFrameInfo is updated with this information.
47//
48//===----------------------------------------------------------------------===//
49
50#include "llvm/CodeGen/ShrinkWrap.h"
51#include "llvm/ADT/BitVector.h"
52#include "llvm/ADT/PostOrderIterator.h"
53#include "llvm/ADT/SetVector.h"
54#include "llvm/ADT/SmallVector.h"
55#include "llvm/ADT/Statistic.h"
56#include "llvm/Analysis/CFG.h"
57#include "llvm/Analysis/ValueTracking.h"
58#include "llvm/CodeGen/MachineBasicBlock.h"
59#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
60#include "llvm/CodeGen/MachineDominators.h"
61#include "llvm/CodeGen/MachineFrameInfo.h"
62#include "llvm/CodeGen/MachineFunction.h"
63#include "llvm/CodeGen/MachineFunctionPass.h"
64#include "llvm/CodeGen/MachineInstr.h"
65#include "llvm/CodeGen/MachineLoopInfo.h"
66#include "llvm/CodeGen/MachineOperand.h"
67#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
68#include "llvm/CodeGen/MachinePostDominators.h"
69#include "llvm/CodeGen/RegisterClassInfo.h"
70#include "llvm/CodeGen/RegisterScavenging.h"
71#include "llvm/CodeGen/TargetFrameLowering.h"
72#include "llvm/CodeGen/TargetInstrInfo.h"
73#include "llvm/CodeGen/TargetLowering.h"
74#include "llvm/CodeGen/TargetRegisterInfo.h"
75#include "llvm/CodeGen/TargetSubtargetInfo.h"
76#include "llvm/IR/Attributes.h"
77#include "llvm/IR/Function.h"
78#include "llvm/InitializePasses.h"
79#include "llvm/MC/MCAsmInfo.h"
80#include "llvm/Pass.h"
81#include "llvm/Support/CommandLine.h"
82#include "llvm/Support/Debug.h"
83#include "llvm/Support/ErrorHandling.h"
84#include "llvm/Support/raw_ostream.h"
85#include "llvm/Target/TargetMachine.h"
86#include <cassert>
87#include <memory>
88
89using namespace llvm;
90
91#define DEBUG_TYPE "shrink-wrap"
92
93STATISTIC(NumFunc, "Number of functions");
94STATISTIC(NumCandidates, "Number of shrink-wrapping candidates");
95STATISTIC(NumCandidatesDropped,
96 "Number of shrink-wrapping candidates dropped because of frequency");
97
98static cl::opt<cl::boolOrDefault>
99EnableShrinkWrapOpt("enable-shrink-wrap", cl::Hidden,
100 cl::desc("enable the shrink-wrapping pass"));
101static cl::opt<bool> EnablePostShrinkWrapOpt(
102 "enable-shrink-wrap-region-split", cl::init(Val: true), cl::Hidden,
103 cl::desc("enable splitting of the restore block if possible"));
104
105namespace {
106
107/// Class to determine where the safe point to insert the
108/// prologue and epilogue are.
109/// Unlike the paper from Fred C. Chow, PLDI'88, that introduces the
110/// shrink-wrapping term for prologue/epilogue placement, this pass
111/// does not rely on expensive data-flow analysis. Instead we use the
112/// dominance properties and loop information to decide which point
113/// are safe for such insertion.
114class ShrinkWrapImpl {
115 /// Hold callee-saved information.
116 const RegisterClassInfo *RCI = nullptr;
117 MachineDominatorTree *MDT = nullptr;
118 MachinePostDominatorTree *MPDT = nullptr;
119
120 /// Current safe point found for the prologue.
121 /// The prologue will be inserted before the first instruction
122 /// in this basic block.
123 MachineBasicBlock *Save = nullptr;
124
125 /// Current safe point found for the epilogue.
126 /// The epilogue will be inserted before the first terminator instruction
127 /// in this basic block.
128 MachineBasicBlock *Restore = nullptr;
129
130 /// Hold the information of the basic block frequency.
131 /// Use to check the profitability of the new points.
132 MachineBlockFrequencyInfo *MBFI = nullptr;
133
134 /// Hold the loop information. Used to determine if Save and Restore
135 /// are in the same loop.
136 MachineLoopInfo *MLI = nullptr;
137
138 // Emit remarks.
139 MachineOptimizationRemarkEmitter *ORE = nullptr;
140
141 /// Frequency of the Entry block.
142 BlockFrequency EntryFreq;
143
144 /// Current opcode for frame setup.
145 unsigned FrameSetupOpcode = ~0u;
146
147 /// Current opcode for frame destroy.
148 unsigned FrameDestroyOpcode = ~0u;
149
150 /// Stack pointer register, used by llvm.{savestack,restorestack}
151 Register SP;
152
153 /// Entry block.
154 const MachineBasicBlock *Entry = nullptr;
155
156 using SetOfRegs = SmallSetVector<unsigned, 16>;
157
158 /// Registers that need to be saved for the current function.
159 mutable SetOfRegs CurrentCSRs;
160
161 /// Current MachineFunction.
162 MachineFunction *MachineFunc = nullptr;
163
164 /// Is `true` for the block numbers where we assume possible stack accesses
165 /// or computation of stack-relative addresses on any CFG path including the
166 /// block itself. Is `false` for basic blocks where we can guarantee the
167 /// opposite. False positives won't lead to incorrect analysis results,
168 /// therefore this approach is fair.
169 BitVector StackAddressUsedBlockInfo;
170
171 /// Check if \p MI uses or defines a callee-saved register or
172 /// a frame index. If this is the case, this means \p MI must happen
173 /// after Save and before Restore.
174 bool useOrDefCSROrFI(const MachineInstr &MI, RegScavenger *RS,
175 bool StackAddressUsed) const;
176
177 const SetOfRegs &getCurrentCSRs(RegScavenger *RS) const {
178 if (CurrentCSRs.empty()) {
179 BitVector SavedRegs;
180 const TargetFrameLowering *TFI =
181 MachineFunc->getSubtarget().getFrameLowering();
182
183 TFI->determineCalleeSaves(MF&: *MachineFunc, SavedRegs, RS);
184
185 for (int Reg = SavedRegs.find_first(); Reg != -1;
186 Reg = SavedRegs.find_next(Prev: Reg))
187 CurrentCSRs.insert(X: (unsigned)Reg);
188 }
189 return CurrentCSRs;
190 }
191
192 /// Update the Save and Restore points such that \p MBB is in
193 /// the region that is dominated by Save and post-dominated by Restore
194 /// and Save and Restore still match the safe point definition.
195 /// Such point may not exist and Save and/or Restore may be null after
196 /// this call.
197 void updateSaveRestorePoints(MachineBasicBlock &MBB, RegScavenger *RS);
198
199 // Try to find safe point based on dominance and block frequency without
200 // any change in IR.
201 bool performShrinkWrapping(
202 const ReversePostOrderTraversal<MachineBasicBlock *> &RPOT,
203 RegScavenger *RS);
204
205 /// This function tries to split the restore point if doing so can shrink the
206 /// save point further. \return True if restore point is split.
207 bool postShrinkWrapping(bool HasCandidate, MachineFunction &MF,
208 RegScavenger *RS);
209
210 /// This function analyzes if the restore point can split to create a new
211 /// restore point. This function collects
212 /// 1. Any preds of current restore that are reachable by callee save/FI
213 /// blocks
214 /// - indicated by DirtyPreds
215 /// 2. Any preds of current restore that are not DirtyPreds - indicated by
216 /// CleanPreds
217 /// Both sets should be non-empty for considering restore point split.
218 bool checkIfRestoreSplittable(
219 const MachineBasicBlock *CurRestore,
220 const DenseSet<const MachineBasicBlock *> &ReachableByDirty,
221 SmallVectorImpl<MachineBasicBlock *> &DirtyPreds,
222 SmallVectorImpl<MachineBasicBlock *> &CleanPreds,
223 const TargetInstrInfo *TII, RegScavenger *RS);
224
225 /// Initialize the pass for \p MF.
226 void init(MachineFunction &MF) {
227 Save = nullptr;
228 Restore = nullptr;
229 EntryFreq = MBFI->getEntryFreq();
230 const TargetSubtargetInfo &Subtarget = MF.getSubtarget();
231 const TargetInstrInfo &TII = *Subtarget.getInstrInfo();
232 FrameSetupOpcode = TII.getCallFrameSetupOpcode();
233 FrameDestroyOpcode = TII.getCallFrameDestroyOpcode();
234 SP = Subtarget.getTargetLowering()->getStackPointerRegisterToSaveRestore();
235 Entry = &MF.front();
236 CurrentCSRs.clear();
237 MachineFunc = &MF;
238
239 ++NumFunc;
240 }
241
242 /// Check whether or not Save and Restore points are still interesting for
243 /// shrink-wrapping.
244 bool ArePointsInteresting() const { return Save != Entry && Save && Restore; }
245
246public:
247 ShrinkWrapImpl(const RegisterClassInfo *RCI, MachineDominatorTree *MDT,
248 MachinePostDominatorTree *MPDT,
249 MachineBlockFrequencyInfo *MBFI, MachineLoopInfo *MLI,
250 MachineOptimizationRemarkEmitter *ORE)
251 : RCI(RCI), MDT(MDT), MPDT(MPDT), MBFI(MBFI), MLI(MLI), ORE(ORE) {}
252
253 /// Check if shrink wrapping is enabled for this target and function.
254 static bool isShrinkWrapEnabled(const MachineFunction &MF);
255
256 bool run(MachineFunction &MF);
257};
258
259class ShrinkWrapLegacy : public MachineFunctionPass {
260public:
261 static char ID;
262
263 ShrinkWrapLegacy() : MachineFunctionPass(ID) {}
264
265 void getAnalysisUsage(AnalysisUsage &AU) const override {
266 AU.setPreservesAll();
267 AU.addRequired<MachineBlockFrequencyInfoWrapperPass>();
268 AU.addRequired<MachineDominatorTreeWrapperPass>();
269 AU.addRequired<MachinePostDominatorTreeWrapperPass>();
270 AU.addRequired<MachineLoopInfoWrapperPass>();
271 AU.addRequired<MachineOptimizationRemarkEmitterPass>();
272 AU.addRequired<MachineRegisterClassInfoWrapperPass>();
273 MachineFunctionPass::getAnalysisUsage(AU);
274 }
275
276 MachineFunctionProperties getRequiredProperties() const override {
277 return MachineFunctionProperties().setNoVRegs();
278 }
279
280 StringRef getPassName() const override { return "Shrink Wrapping analysis"; }
281
282 /// Perform the shrink-wrapping analysis and update
283 /// the MachineFrameInfo attached to \p MF with the results.
284 bool runOnMachineFunction(MachineFunction &MF) override;
285};
286
287} // end anonymous namespace
288
289char ShrinkWrapLegacy::ID = 0;
290
291char &llvm::ShrinkWrapID = ShrinkWrapLegacy::ID;
292
293INITIALIZE_PASS_BEGIN(ShrinkWrapLegacy, DEBUG_TYPE, "Shrink Wrap Pass", false,
294 false)
295INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfoWrapperPass)
296INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
297INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTreeWrapperPass)
298INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
299INITIALIZE_PASS_DEPENDENCY(MachineOptimizationRemarkEmitterPass)
300INITIALIZE_PASS_DEPENDENCY(MachineRegisterClassInfoWrapperPass)
301INITIALIZE_PASS_END(ShrinkWrapLegacy, DEBUG_TYPE, "Shrink Wrap Pass", false,
302 false)
303
304bool ShrinkWrapImpl::useOrDefCSROrFI(const MachineInstr &MI, RegScavenger *RS,
305 bool StackAddressUsed) const {
306 /// Check if \p Op is known to access an address not on the function's stack .
307 /// At the moment, accesses where the underlying object is a global, function
308 /// argument, or jump table are considered non-stack accesses. Note that the
309 /// caller's stack may get accessed when passing an argument via the stack,
310 /// but not the stack of the current function.
311 ///
312 auto IsKnownNonStackPtr = [](MachineMemOperand *Op) {
313 if (Op->getValue()) {
314 SmallVector<const Value *, 2> Objs;
315 getUnderlyingObjects(V: Op->getValue(), Objects&: Objs);
316 return !Objs.empty() && all_of(Range&: Objs, P: [](const Value *UO) {
317 if (auto *Arg = dyn_cast<Argument>(Val: UO))
318 return !Arg->hasPassPointeeByValueCopyAttr();
319 return isa<GlobalValue>(Val: UO);
320 });
321 }
322 if (const PseudoSourceValue *PSV = Op->getPseudoValue())
323 return PSV->isJumpTable() || PSV->isConstantPool();
324 return false;
325 };
326 // Load/store operations may access the stack indirectly when we previously
327 // computed an address to a stack location.
328 if (StackAddressUsed && MI.mayLoadOrStore() &&
329 (MI.isCall() || MI.hasUnmodeledSideEffects() || MI.memoperands_empty() ||
330 !all_of(Range: MI.memoperands(), P: IsKnownNonStackPtr)))
331 return true;
332
333 if (MI.getOpcode() == FrameSetupOpcode ||
334 MI.getOpcode() == FrameDestroyOpcode) {
335 LLVM_DEBUG(dbgs() << "Frame instruction: " << MI << '\n');
336 return true;
337 }
338 const MachineFunction *MF = MI.getParent()->getParent();
339 const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
340 for (const MachineOperand &MO : MI.operands()) {
341 bool UseOrDefCSR = false;
342 if (MO.isReg()) {
343 // Ignore instructions like DBG_VALUE which don't read/def the register.
344 if (!MO.isDef() && !MO.readsReg())
345 continue;
346 Register PhysReg = MO.getReg();
347 if (!PhysReg)
348 continue;
349 assert(PhysReg.isPhysical() && "Unallocated register?!");
350 // The stack pointer is not normally described as a callee-saved register
351 // in calling convention definitions, so we need to watch for it
352 // separately. An SP mentioned by a call instruction, we can ignore,
353 // though, as it's harmless and we do not want to effectively disable tail
354 // calls by forcing the restore point to post-dominate them.
355 // PPC's LR is also not normally described as a callee-saved register in
356 // calling convention definitions, so we need to watch for it, too. An LR
357 // mentioned implicitly by a return (or "branch to link register")
358 // instruction we can ignore, otherwise we may pessimize shrinkwrapping.
359 // PPC's Frame pointer (FP) is also not described as a callee-saved
360 // register. Until the FP is assigned a Physical Register PPC's FP needs
361 // to be checked separately.
362 UseOrDefCSR = (!MI.isCall() && PhysReg == SP) ||
363 RCI->getLastCalleeSavedAlias(PhysReg) ||
364 (!MI.isReturn() &&
365 TRI->isNonallocatableRegisterCalleeSave(Reg: PhysReg)) ||
366 TRI->isVirtualFrameRegister(Reg: PhysReg);
367 } else if (MO.isRegMask()) {
368 // Check if this regmask clobbers any of the CSRs.
369 for (unsigned Reg : getCurrentCSRs(RS)) {
370 if (MO.clobbersPhysReg(PhysReg: Reg)) {
371 UseOrDefCSR = true;
372 break;
373 }
374 }
375 }
376 // Skip FrameIndex operands in DBG_VALUE instructions.
377 if (UseOrDefCSR || (MO.isFI() && !MI.isDebugValue())) {
378 LLVM_DEBUG(dbgs() << "Use or define CSR(" << UseOrDefCSR << ") or FI("
379 << MO.isFI() << "): " << MI << '\n');
380 return true;
381 }
382 }
383 return false;
384}
385
386/// Helper function to find the immediate (post) dominator.
387template <typename ListOfBBs, typename DominanceAnalysis>
388static MachineBasicBlock *FindIDom(MachineBasicBlock &Block, ListOfBBs BBs,
389 DominanceAnalysis &Dom, bool Strict = true) {
390 if (BBs.begin() == BBs.end())
391 return Strict ? nullptr : &Block;
392 MachineBasicBlock *IDom = Dom.findNearestCommonDominator(iterator_range(BBs));
393 if (Strict && IDom == &Block)
394 return nullptr;
395 return IDom;
396}
397
398static bool isAnalyzableBB(const TargetInstrInfo &TII,
399 MachineBasicBlock &Entry) {
400 // Check if the block is analyzable.
401 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
402 SmallVector<MachineOperand, 4> Cond;
403 return !TII.analyzeBranch(MBB&: Entry, TBB, FBB, Cond);
404}
405
406/// Determines if any predecessor of MBB is on the path from block that has use
407/// or def of CSRs/FI to MBB.
408/// ReachableByDirty: All blocks reachable from block that has use or def of
409/// CSR/FI.
410static bool
411hasDirtyPred(const DenseSet<const MachineBasicBlock *> &ReachableByDirty,
412 const MachineBasicBlock &MBB) {
413 for (const MachineBasicBlock *PredBB : MBB.predecessors())
414 if (ReachableByDirty.count(V: PredBB))
415 return true;
416 return false;
417}
418
419/// Derives the list of all the basic blocks reachable from MBB.
420static void markAllReachable(DenseSet<const MachineBasicBlock *> &Visited,
421 const MachineBasicBlock &MBB) {
422 SmallVector<MachineBasicBlock *, 4> Worklist(MBB.successors());
423 Visited.insert(V: &MBB);
424 while (!Worklist.empty()) {
425 MachineBasicBlock *SuccMBB = Worklist.pop_back_val();
426 if (!Visited.insert(V: SuccMBB).second)
427 continue;
428 Worklist.append(in_start: SuccMBB->succ_begin(), in_end: SuccMBB->succ_end());
429 }
430}
431
432/// Collect blocks reachable by use or def of CSRs/FI.
433static void collectBlocksReachableByDirty(
434 const DenseSet<const MachineBasicBlock *> &DirtyBBs,
435 DenseSet<const MachineBasicBlock *> &ReachableByDirty) {
436 for (const MachineBasicBlock *MBB : DirtyBBs) {
437 if (ReachableByDirty.count(V: MBB))
438 continue;
439 // Mark all offsprings as reachable.
440 markAllReachable(Visited&: ReachableByDirty, MBB: *MBB);
441 }
442}
443
444/// \return true if there is a clean path from SavePoint to the original
445/// Restore.
446static bool
447isSaveReachableThroughClean(const MachineBasicBlock *SavePoint,
448 ArrayRef<MachineBasicBlock *> CleanPreds) {
449 DenseSet<const MachineBasicBlock *> Visited;
450 SmallVector<MachineBasicBlock *, 4> Worklist(CleanPreds);
451 while (!Worklist.empty()) {
452 MachineBasicBlock *CleanBB = Worklist.pop_back_val();
453 if (CleanBB == SavePoint)
454 return true;
455 if (!Visited.insert(V: CleanBB).second || !CleanBB->pred_size())
456 continue;
457 Worklist.append(in_start: CleanBB->pred_begin(), in_end: CleanBB->pred_end());
458 }
459 return false;
460}
461
462/// This function updates the branches post restore point split.
463///
464/// Restore point has been split.
465/// Old restore point: MBB
466/// New restore point: NMBB
467/// Any basic block(say BBToUpdate) which had a fallthrough to MBB
468/// previously should
469/// 1. Fallthrough to NMBB iff NMBB is inserted immediately above MBB in the
470/// block layout OR
471/// 2. Branch unconditionally to NMBB iff NMBB is inserted at any other place.
472static void updateTerminator(MachineBasicBlock *BBToUpdate,
473 MachineBasicBlock *NMBB,
474 const TargetInstrInfo *TII) {
475 DebugLoc DL = BBToUpdate->findBranchDebugLoc();
476 // if NMBB isn't the new layout successor for BBToUpdate, insert unconditional
477 // branch to it
478 if (!BBToUpdate->isLayoutSuccessor(MBB: NMBB))
479 TII->insertUnconditionalBranch(MBB&: *BBToUpdate, DestBB: NMBB, DL);
480}
481
482/// This function splits the restore point and returns new restore point/BB.
483///
484/// DirtyPreds: Predessors of \p MBB that are ReachableByDirty
485///
486/// Decision has been made to split the restore point.
487/// old restore point: \p MBB
488/// new restore point: \p NMBB
489/// This function makes the necessary block layout changes so that
490/// 1. \p NMBB points to \p MBB unconditionally
491/// 2. All dirtyPreds that previously pointed to \p MBB point to \p NMBB
492static MachineBasicBlock *
493tryToSplitRestore(MachineBasicBlock *MBB,
494 ArrayRef<MachineBasicBlock *> DirtyPreds,
495 const TargetInstrInfo *TII) {
496 MachineFunction *MF = MBB->getParent();
497
498 // get the list of DirtyPreds who have a fallthrough to MBB
499 // before the block layout change. This is just to ensure that if the NMBB is
500 // inserted after MBB, then we create unconditional branch from
501 // DirtyPred/CleanPred to NMBB
502 SmallPtrSet<MachineBasicBlock *, 8> MBBFallthrough;
503 for (MachineBasicBlock *BB : DirtyPreds)
504 if (BB->getFallThrough(JumpToFallThrough: false) == MBB)
505 MBBFallthrough.insert(Ptr: BB);
506
507 MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock();
508 // Insert this block at the end of the function. Inserting in between may
509 // interfere with control flow optimizer decisions.
510 MF->insert(MBBI: MF->end(), MBB: NMBB);
511
512 for (const MachineBasicBlock::RegisterMaskPair &LI : MBB->liveins())
513 NMBB->addLiveIn(PhysReg: LI.PhysReg);
514
515 TII->insertUnconditionalBranch(MBB&: *NMBB, DestBB: MBB, DL: DebugLoc());
516
517 // After splitting, all predecessors of the restore point should be dirty
518 // blocks.
519 for (MachineBasicBlock *SuccBB : DirtyPreds)
520 SuccBB->ReplaceUsesOfBlockWith(Old: MBB, New: NMBB);
521
522 NMBB->addSuccessor(Succ: MBB);
523
524 for (MachineBasicBlock *BBToUpdate : MBBFallthrough)
525 updateTerminator(BBToUpdate, NMBB, TII);
526
527 return NMBB;
528}
529
530/// This function undoes the restore point split done earlier.
531///
532/// DirtyPreds: All predecessors of \p NMBB that are ReachableByDirty.
533///
534/// Restore point was split and the change needs to be unrolled. Make necessary
535/// changes to reset restore point from \p NMBB to \p MBB.
536static void rollbackRestoreSplit(MachineFunction &MF, MachineBasicBlock *NMBB,
537 MachineBasicBlock *MBB,
538 ArrayRef<MachineBasicBlock *> DirtyPreds,
539 const TargetInstrInfo *TII) {
540 // For a BB, if NMBB is fallthrough in the current layout, then in the new
541 // layout a. BB should fallthrough to MBB OR b. BB should undconditionally
542 // branch to MBB
543 SmallPtrSet<MachineBasicBlock *, 8> NMBBFallthrough;
544 for (MachineBasicBlock *BB : DirtyPreds)
545 if (BB->getFallThrough(JumpToFallThrough: false) == NMBB)
546 NMBBFallthrough.insert(Ptr: BB);
547
548 NMBB->removeSuccessor(Succ: MBB);
549 for (MachineBasicBlock *SuccBB : DirtyPreds)
550 SuccBB->ReplaceUsesOfBlockWith(Old: NMBB, New: MBB);
551
552 NMBB->erase(I: NMBB->begin(), E: NMBB->end());
553 NMBB->eraseFromParent();
554
555 for (MachineBasicBlock *BBToUpdate : NMBBFallthrough)
556 updateTerminator(BBToUpdate, NMBB: MBB, TII);
557}
558
559// A block is deemed fit for restore point split iff there exist
560// 1. DirtyPreds - preds of CurRestore reachable from use or def of CSR/FI
561// 2. CleanPreds - preds of CurRestore that arent DirtyPreds
562bool ShrinkWrapImpl::checkIfRestoreSplittable(
563 const MachineBasicBlock *CurRestore,
564 const DenseSet<const MachineBasicBlock *> &ReachableByDirty,
565 SmallVectorImpl<MachineBasicBlock *> &DirtyPreds,
566 SmallVectorImpl<MachineBasicBlock *> &CleanPreds,
567 const TargetInstrInfo *TII, RegScavenger *RS) {
568 for (const MachineInstr &MI : *CurRestore)
569 if (useOrDefCSROrFI(MI, RS, /*StackAddressUsed=*/true))
570 return false;
571
572 for (MachineBasicBlock *PredBB : CurRestore->predecessors()) {
573 if (!isAnalyzableBB(TII: *TII, Entry&: *PredBB))
574 return false;
575
576 if (ReachableByDirty.count(V: PredBB))
577 DirtyPreds.push_back(Elt: PredBB);
578 else
579 CleanPreds.push_back(Elt: PredBB);
580 }
581
582 return !(CleanPreds.empty() || DirtyPreds.empty());
583}
584
585bool ShrinkWrapImpl::postShrinkWrapping(bool HasCandidate, MachineFunction &MF,
586 RegScavenger *RS) {
587 if (!EnablePostShrinkWrapOpt)
588 return false;
589
590 MachineBasicBlock *InitSave = nullptr;
591 MachineBasicBlock *InitRestore = nullptr;
592
593 if (HasCandidate) {
594 InitSave = Save;
595 InitRestore = Restore;
596 } else {
597 InitRestore = nullptr;
598 InitSave = &MF.front();
599 for (MachineBasicBlock &MBB : MF) {
600 if (MBB.isEHFuncletEntry())
601 return false;
602 if (MBB.isReturnBlock()) {
603 // Do not support multiple restore points.
604 if (InitRestore)
605 return false;
606 InitRestore = &MBB;
607 }
608 }
609 }
610
611 if (!InitSave || !InitRestore || InitRestore == InitSave ||
612 !MDT->dominates(A: InitSave, B: InitRestore) ||
613 !MPDT->dominates(A: InitRestore, B: InitSave))
614 return false;
615
616 // Bail out of the optimization if any of the basic block is target of
617 // INLINEASM_BR instruction
618 for (MachineBasicBlock &MBB : MF)
619 if (MBB.isInlineAsmBrIndirectTarget())
620 return false;
621
622 DenseSet<const MachineBasicBlock *> DirtyBBs;
623 for (MachineBasicBlock &MBB : MF) {
624 if (!MDT->isReachableFromEntry(A: &MBB))
625 continue;
626 if (MBB.isEHPad()) {
627 DirtyBBs.insert(V: &MBB);
628 continue;
629 }
630 for (const MachineInstr &MI : MBB)
631 if (useOrDefCSROrFI(MI, RS, /*StackAddressUsed=*/true)) {
632 DirtyBBs.insert(V: &MBB);
633 break;
634 }
635 }
636
637 // Find blocks reachable from the use or def of CSRs/FI.
638 DenseSet<const MachineBasicBlock *> ReachableByDirty;
639 collectBlocksReachableByDirty(DirtyBBs, ReachableByDirty);
640
641 const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
642 SmallVector<MachineBasicBlock *, 2> DirtyPreds;
643 SmallVector<MachineBasicBlock *, 2> CleanPreds;
644 if (!checkIfRestoreSplittable(CurRestore: InitRestore, ReachableByDirty, DirtyPreds,
645 CleanPreds, TII, RS))
646 return false;
647
648 // Trying to reach out to the new save point which dominates all dirty blocks.
649 MachineBasicBlock *NewSave =
650 FindIDom<>(Block&: **DirtyPreds.begin(), BBs: DirtyPreds, Dom&: *MDT, Strict: false);
651
652 while (NewSave && (hasDirtyPred(ReachableByDirty, MBB: *NewSave) ||
653 EntryFreq < MBFI->getBlockFreq(MBB: NewSave) ||
654 /*Entry freq has been observed more than a loop block in
655 some cases*/
656 MLI->getLoopFor(BB: NewSave))) {
657 SmallVector<MachineBasicBlock*> ReachablePreds;
658 for (auto BB: NewSave->predecessors())
659 if (MDT->isReachableFromEntry(A: BB))
660 ReachablePreds.push_back(Elt: BB);
661 if (ReachablePreds.empty())
662 break;
663
664 NewSave = FindIDom<>(Block&: **ReachablePreds.begin(), BBs: ReachablePreds, Dom&: *MDT,
665 Strict: false);
666 }
667
668 const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
669 if (!NewSave || NewSave == InitSave ||
670 isSaveReachableThroughClean(SavePoint: NewSave, CleanPreds) ||
671 !TFI->canUseAsPrologue(MBB: *NewSave))
672 return false;
673
674 // Now we know that splitting a restore point can isolate the restore point
675 // from clean blocks and doing so can shrink the save point.
676 MachineBasicBlock *NewRestore =
677 tryToSplitRestore(MBB: InitRestore, DirtyPreds, TII);
678
679 // Make sure if the new restore point is valid as an epilogue, depending on
680 // targets.
681 if (!TFI->canUseAsEpilogue(MBB: *NewRestore)) {
682 rollbackRestoreSplit(MF, NMBB: NewRestore, MBB: InitRestore, DirtyPreds, TII);
683 return false;
684 }
685
686 Save = NewSave;
687 Restore = NewRestore;
688
689 MDT->recalculate(Func&: MF);
690 MPDT->recalculate(Func&: MF);
691
692 assert((MDT->dominates(Save, Restore) && MPDT->dominates(Restore, Save)) &&
693 "Incorrect save or restore point due to dominance relations");
694 assert((!MLI->getLoopFor(Save) && !MLI->getLoopFor(Restore)) &&
695 "Unexpected save or restore point in a loop");
696 assert((EntryFreq >= MBFI->getBlockFreq(Save) &&
697 EntryFreq >= MBFI->getBlockFreq(Restore)) &&
698 "Incorrect save or restore point based on block frequency");
699 return true;
700}
701
702void ShrinkWrapImpl::updateSaveRestorePoints(MachineBasicBlock &MBB,
703 RegScavenger *RS) {
704 // Get rid of the easy cases first.
705 if (!Save)
706 Save = &MBB;
707 else
708 Save = MDT->findNearestCommonDominator(A: Save, B: &MBB);
709 assert(Save);
710
711 if (!Restore)
712 Restore = &MBB;
713 else if (MPDT->getNode(BB: &MBB)) // If the block is not in the post dom tree, it
714 // means the block never returns. If that's the
715 // case, we don't want to call
716 // `findNearestCommonDominator`, which will
717 // return `Restore`.
718 Restore = MPDT->findNearestCommonDominator(A: Restore, B: &MBB);
719 else
720 Restore = nullptr; // Abort, we can't find a restore point in this case.
721
722 // Make sure we would be able to insert the restore code before the
723 // terminator.
724 if (Restore == &MBB) {
725 for (const MachineInstr &Terminator : MBB.terminators()) {
726 if (!useOrDefCSROrFI(MI: Terminator, RS, /*StackAddressUsed=*/true))
727 continue;
728 // One of the terminator needs to happen before the restore point.
729 if (MBB.succ_empty()) {
730 Restore = nullptr; // Abort, we can't find a restore point in this case.
731 break;
732 }
733 // Look for a restore point that post-dominates all the successors.
734 // The immediate post-dominator is what we are looking for.
735 Restore = FindIDom<>(Block&: *Restore, BBs: Restore->successors(), Dom&: *MPDT);
736 break;
737 }
738 }
739
740 if (!Restore) {
741 LLVM_DEBUG(
742 dbgs() << "Restore point needs to be spanned on several blocks\n");
743 return;
744 }
745
746 // Make sure Save and Restore are suitable for shrink-wrapping:
747 // 1. all path from Save needs to lead to Restore before exiting.
748 // 2. all path to Restore needs to go through Save from Entry.
749 // We achieve that by making sure that:
750 // A. Save dominates Restore.
751 // B. Restore post-dominates Save.
752 // C. Save and Restore are in the same loop.
753 bool SaveDominatesRestore = false;
754 bool RestorePostDominatesSave = false;
755 while (Restore &&
756 (!(SaveDominatesRestore = MDT->dominates(A: Save, B: Restore)) ||
757 !(RestorePostDominatesSave = MPDT->dominates(A: Restore, B: Save)) ||
758 // Post-dominance is not enough in loops to ensure that all uses/defs
759 // are after the prologue and before the epilogue at runtime.
760 // E.g.,
761 // while(1) {
762 // Save
763 // Restore
764 // if (...)
765 // break;
766 // use/def CSRs
767 // }
768 // All the uses/defs of CSRs are dominated by Save and post-dominated
769 // by Restore. However, the CSRs uses are still reachable after
770 // Restore and before Save are executed.
771 //
772 // For now, just push the restore/save points outside of loops.
773 // FIXME: Refine the criteria to still find interesting cases
774 // for loops.
775 MLI->getLoopFor(BB: Save) || MLI->getLoopFor(BB: Restore))) {
776 // Fix (A).
777 if (!SaveDominatesRestore) {
778 Save = MDT->findNearestCommonDominator(A: Save, B: Restore);
779 continue;
780 }
781 // Fix (B).
782 if (!RestorePostDominatesSave)
783 Restore = MPDT->findNearestCommonDominator(A: Restore, B: Save);
784
785 // Fix (C).
786 if (Restore && (MLI->getLoopFor(BB: Save) || MLI->getLoopFor(BB: Restore))) {
787 if (MLI->getLoopDepth(BB: Save) > MLI->getLoopDepth(BB: Restore)) {
788 // Push Save outside of this loop if immediate dominator is different
789 // from save block. If immediate dominator is not different, bail out.
790 SmallVector<MachineBasicBlock *> Preds;
791 for (auto *PBB : Save->predecessors())
792 if (MDT->isReachableFromEntry(A: PBB))
793 Preds.push_back(Elt: PBB);
794 Save = FindIDom<>(Block&: *Save, BBs: Preds, Dom&: *MDT);
795 if (!Save)
796 break;
797 } else {
798 // If the loop does not exit, there is no point in looking
799 // for a post-dominator outside the loop.
800 SmallVector<MachineBasicBlock*, 4> ExitBlocks;
801 MLI->getLoopFor(BB: Restore)->getExitingBlocks(ExitingBlocks&: ExitBlocks);
802 // Push Restore outside of this loop.
803 // Look for the immediate post-dominator of the loop exits.
804 MachineBasicBlock *IPdom = Restore;
805 for (MachineBasicBlock *LoopExitBB: ExitBlocks) {
806 IPdom = FindIDom<>(Block&: *IPdom, BBs: LoopExitBB->successors(), Dom&: *MPDT);
807 if (!IPdom)
808 break;
809 }
810 // If the immediate post-dominator is not in a less nested loop,
811 // then we are stuck in a program with an infinite loop.
812 // In that case, we will not find a safe point, hence, bail out.
813 if (IPdom && MLI->getLoopDepth(BB: IPdom) < MLI->getLoopDepth(BB: Restore))
814 Restore = IPdom;
815 else {
816 Restore = nullptr;
817 break;
818 }
819 }
820 }
821 }
822}
823
824static bool giveUpWithRemarks(MachineOptimizationRemarkEmitter *ORE,
825 StringRef RemarkName, StringRef RemarkMessage,
826 const DiagnosticLocation &Loc,
827 const MachineBasicBlock *MBB) {
828 ORE->emit(RemarkBuilder: [&]() {
829 return MachineOptimizationRemarkMissed(DEBUG_TYPE, RemarkName, Loc, MBB)
830 << RemarkMessage;
831 });
832
833 LLVM_DEBUG(dbgs() << RemarkMessage << '\n');
834 return false;
835}
836
837bool ShrinkWrapImpl::performShrinkWrapping(
838 const ReversePostOrderTraversal<MachineBasicBlock *> &RPOT,
839 RegScavenger *RS) {
840 for (MachineBasicBlock *MBB : RPOT) {
841 LLVM_DEBUG(dbgs() << "Look into: " << printMBBReference(*MBB) << '\n');
842
843 if (MBB->isEHFuncletEntry())
844 return giveUpWithRemarks(ORE, RemarkName: "UnsupportedEHFunclets",
845 RemarkMessage: "EH Funclets are not supported yet.",
846 Loc: MBB->front().getDebugLoc(), MBB);
847
848 if (MBB->isEHPad() || MBB->isInlineAsmBrIndirectTarget()) {
849 // Push the prologue and epilogue outside of the region that may throw (or
850 // jump out via inlineasm_br), by making sure that all the landing pads
851 // are at least at the boundary of the save and restore points. The
852 // problem is that a basic block can jump out from the middle in these
853 // cases, which we do not handle.
854 updateSaveRestorePoints(MBB&: *MBB, RS);
855 if (!ArePointsInteresting()) {
856 LLVM_DEBUG(dbgs() << "EHPad/inlineasm_br prevents shrink-wrapping\n");
857 return false;
858 }
859 continue;
860 }
861
862 bool StackAddressUsed = false;
863 // Check if we found any stack accesses in the predecessors. We are not
864 // doing a full dataflow analysis here to keep things simple but just
865 // rely on a reverse portorder traversal (RPOT) to guarantee predecessors
866 // are already processed except for loops (and accept the conservative
867 // result for loops).
868 for (const MachineBasicBlock *Pred : MBB->predecessors()) {
869 if (StackAddressUsedBlockInfo.test(Idx: Pred->getNumber())) {
870 StackAddressUsed = true;
871 break;
872 }
873 }
874
875 for (const MachineInstr &MI : *MBB) {
876 if (useOrDefCSROrFI(MI, RS, StackAddressUsed)) {
877 // Save (resp. restore) point must dominate (resp. post dominate)
878 // MI. Look for the proper basic block for those.
879 updateSaveRestorePoints(MBB&: *MBB, RS);
880 // If we are at a point where we cannot improve the placement of
881 // save/restore instructions, just give up.
882 if (!ArePointsInteresting()) {
883 LLVM_DEBUG(dbgs() << "No Shrink wrap candidate found\n");
884 return false;
885 }
886 // No need to look for other instructions, this basic block
887 // will already be part of the handled region.
888 StackAddressUsed = true;
889 break;
890 }
891 }
892 StackAddressUsedBlockInfo[MBB->getNumber()] = StackAddressUsed;
893 }
894 if (!ArePointsInteresting()) {
895 // If the points are not interesting at this point, then they must be null
896 // because it means we did not encounter any frame/CSR related code.
897 // Otherwise, we would have returned from the previous loop.
898 assert(!Save && !Restore && "We miss a shrink-wrap opportunity?!");
899 LLVM_DEBUG(dbgs() << "Nothing to shrink-wrap\n");
900 return false;
901 }
902
903 LLVM_DEBUG(dbgs() << "\n ** Results **\nFrequency of the Entry: "
904 << EntryFreq.getFrequency() << '\n');
905
906 const TargetFrameLowering *TFI =
907 MachineFunc->getSubtarget().getFrameLowering();
908 do {
909 LLVM_DEBUG(dbgs() << "Shrink wrap candidates (#, Name, Freq):\nSave: "
910 << printMBBReference(*Save) << ' '
911 << printBlockFreq(*MBFI, *Save)
912 << "\nRestore: " << printMBBReference(*Restore) << ' '
913 << printBlockFreq(*MBFI, *Restore) << '\n');
914
915 bool IsSaveCheap, TargetCanUseSaveAsPrologue = false;
916 if (((IsSaveCheap = EntryFreq >= MBFI->getBlockFreq(MBB: Save)) &&
917 EntryFreq >= MBFI->getBlockFreq(MBB: Restore)) &&
918 ((TargetCanUseSaveAsPrologue = TFI->canUseAsPrologue(MBB: *Save)) &&
919 TFI->canUseAsEpilogue(MBB: *Restore)))
920 break;
921 LLVM_DEBUG(
922 dbgs() << "New points are too expensive or invalid for the target\n");
923 MachineBasicBlock *NewBB;
924 if (!IsSaveCheap || !TargetCanUseSaveAsPrologue) {
925 Save = FindIDom<>(Block&: *Save, BBs: Save->predecessors(), Dom&: *MDT);
926 if (!Save)
927 break;
928 NewBB = Save;
929 } else {
930 // Restore is expensive.
931 Restore = FindIDom<>(Block&: *Restore, BBs: Restore->successors(), Dom&: *MPDT);
932 if (!Restore)
933 break;
934 NewBB = Restore;
935 }
936 updateSaveRestorePoints(MBB&: *NewBB, RS);
937 } while (Save && Restore);
938
939 if (!ArePointsInteresting()) {
940 ++NumCandidatesDropped;
941 return false;
942 }
943 return true;
944}
945
946bool ShrinkWrapImpl::run(MachineFunction &MF) {
947 LLVM_DEBUG(dbgs() << "**** Analysing " << MF.getName() << '\n');
948
949 init(MF);
950
951 ReversePostOrderTraversal<MachineBasicBlock *> RPOT(&*MF.begin());
952 if (containsIrreducibleCFG<MachineBasicBlock *>(RPOTraversal&: RPOT, LI: *MLI)) {
953 // If MF is irreducible, a block may be in a loop without
954 // MachineLoopInfo reporting it. I.e., we may use the
955 // post-dominance property in loops, which lead to incorrect
956 // results. Moreover, we may miss that the prologue and
957 // epilogue are not in the same loop, leading to unbalanced
958 // construction/deconstruction of the stack frame.
959 return giveUpWithRemarks(ORE, RemarkName: "UnsupportedIrreducibleCFG",
960 RemarkMessage: "Irreducible CFGs are not supported yet.",
961 Loc: MF.getFunction().getSubprogram(), MBB: &MF.front());
962 }
963
964 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
965 std::unique_ptr<RegScavenger> RS(
966 TRI->requiresRegisterScavenging(MF) ? new RegScavenger() : nullptr);
967
968 bool Changed = false;
969
970 // Initially, conservatively assume that stack addresses can be used in each
971 // basic block and change the state only for those basic blocks for which we
972 // were able to prove the opposite.
973 StackAddressUsedBlockInfo.resize(N: MF.getNumBlockIDs(), t: true);
974 bool HasCandidate = performShrinkWrapping(RPOT, RS: RS.get());
975 StackAddressUsedBlockInfo.clear();
976 Changed = postShrinkWrapping(HasCandidate, MF, RS: RS.get());
977 if (!HasCandidate && !Changed)
978 return false;
979 if (!ArePointsInteresting())
980 return Changed;
981
982 LLVM_DEBUG(dbgs() << "Final shrink wrap candidates:\nSave: "
983 << printMBBReference(*Save) << ' '
984 << "\nRestore: " << printMBBReference(*Restore) << '\n');
985
986 MachineFrameInfo &MFI = MF.getFrameInfo();
987
988 // List of CalleeSavedInfo for registers will be added during prologepilog
989 // pass
990 SaveRestorePoints SavePoints({{Save, {}}});
991 SaveRestorePoints RestorePoints({{Restore, {}}});
992
993 MFI.setSavePoints(SavePoints);
994 MFI.setRestorePoints(RestorePoints);
995 ++NumCandidates;
996 return Changed;
997}
998
999bool ShrinkWrapLegacy::runOnMachineFunction(MachineFunction &MF) {
1000 if (skipFunction(F: MF.getFunction()) || MF.empty() ||
1001 !ShrinkWrapImpl::isShrinkWrapEnabled(MF))
1002 return false;
1003
1004 const RegisterClassInfo *RCI =
1005 &getAnalysis<MachineRegisterClassInfoWrapperPass>().getRCI();
1006 MachineDominatorTree *MDT =
1007 &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
1008 MachinePostDominatorTree *MPDT =
1009 &getAnalysis<MachinePostDominatorTreeWrapperPass>().getPostDomTree();
1010 MachineBlockFrequencyInfo *MBFI =
1011 &getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI();
1012 MachineLoopInfo *MLI = &getAnalysis<MachineLoopInfoWrapperPass>().getLI();
1013 MachineOptimizationRemarkEmitter *ORE =
1014 &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
1015
1016 return ShrinkWrapImpl(RCI, MDT, MPDT, MBFI, MLI, ORE).run(MF);
1017}
1018
1019PreservedAnalyses ShrinkWrapPass::run(MachineFunction &MF,
1020 MachineFunctionAnalysisManager &MFAM) {
1021 MFPropsModifier _(*this, MF);
1022 if (MF.empty() || !ShrinkWrapImpl::isShrinkWrapEnabled(MF))
1023 return PreservedAnalyses::all();
1024
1025 const RegisterClassInfo &RCI =
1026 MFAM.getResult<MachineRegisterClassAnalysis>(IR&: MF);
1027 MachineDominatorTree &MDT = MFAM.getResult<MachineDominatorTreeAnalysis>(IR&: MF);
1028 MachinePostDominatorTree &MPDT =
1029 MFAM.getResult<MachinePostDominatorTreeAnalysis>(IR&: MF);
1030 MachineBlockFrequencyInfo &MBFI =
1031 MFAM.getResult<MachineBlockFrequencyAnalysis>(IR&: MF);
1032 MachineLoopInfo &MLI = MFAM.getResult<MachineLoopAnalysis>(IR&: MF);
1033 MachineOptimizationRemarkEmitter &ORE =
1034 MFAM.getResult<MachineOptimizationRemarkEmitterAnalysis>(IR&: MF);
1035
1036 ShrinkWrapImpl(&RCI, &MDT, &MPDT, &MBFI, &MLI, &ORE).run(MF);
1037 return PreservedAnalyses::all();
1038}
1039
1040bool ShrinkWrapImpl::isShrinkWrapEnabled(const MachineFunction &MF) {
1041 const TargetFrameLowering *TFI = MF.getSubtarget().getFrameLowering();
1042
1043 switch (EnableShrinkWrapOpt) {
1044 case cl::boolOrDefault::BOU_UNSET:
1045 return TFI->enableShrinkWrapping(MF) &&
1046 // Windows with CFI has some limitations that make it impossible
1047 // to use shrink-wrapping.
1048 !MF.usesWindowsUnwindInfo() &&
1049 // Sanitizers look at the value of the stack at the location
1050 // of the crash. Since a crash can happen anywhere, the
1051 // frame must be lowered before anything else happen for the
1052 // sanitizers to be able to get a correct stack frame.
1053 !(MF.getFunction().hasFnAttribute(Kind: Attribute::SanitizeAddress) ||
1054 MF.getFunction().hasFnAttribute(Kind: Attribute::SanitizeThread) ||
1055 MF.getFunction().hasFnAttribute(Kind: Attribute::SanitizeMemory) ||
1056 MF.getFunction().hasFnAttribute(Kind: Attribute::SanitizeType) ||
1057 MF.getFunction().hasFnAttribute(Kind: Attribute::SanitizeHWAddress));
1058 // If EnableShrinkWrap is set, it takes precedence on whatever the
1059 // target sets. The rational is that we assume we want to test
1060 // something related to shrink-wrapping.
1061 case cl::boolOrDefault::BOU_TRUE:
1062 return true;
1063 case cl::boolOrDefault::BOU_FALSE:
1064 return false;
1065 }
1066 llvm_unreachable("Invalid shrink-wrapping state");
1067}
1068