/build/source/bolt/lib/Passes/ShrinkWrapping.cpp

Bug Summary

File:	build/source/bolt/lib/Passes/ShrinkWrapping.cpp
Warning:	line 1639, column 19 Called C++ object pointer is null
Annotated Source Code

Press '?' to see keyboard shortcuts
Show analyzer invocation
clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name ShrinkWrapping.cpp -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/source/build-llvm/tools/clang/stage2-bins -resource-dir /usr/lib/llvm-17/lib/clang/17 -I tools/bolt/lib/Passes -I /build/source/bolt/lib/Passes -I include -I /build/source/llvm/include -I /build/source/bolt/include -I tools/bolt/include -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-17/lib/clang/17/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fmacro-prefix-map=/build/source/= -fcoverage-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fcoverage-prefix-map=/build/source/= -source-date-epoch 1675721604 -O2 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -Wno-misleading-indentation -std=c++17 -fdeprecated-macro -fdebug-compilation-dir=/build/source/build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/source/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2023-02-07-030702-17298-1 -x c++ /build/source/bolt/lib/Passes/ShrinkWrapping.cpp
1//===- bolt/Passes/ShrinkWrapping.cpp -------------------------------------===//
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 file implements the ShrinkWrapping class.
10//
11//===----------------------------------------------------------------------===//

13#include "bolt/Passes/ShrinkWrapping.h"
14#include "bolt/Core/MCPlus.h"
15#include "bolt/Passes/DataflowInfoManager.h"
16#include "bolt/Passes/MCF.h"
17#include "bolt/Utils/CommandLineOpts.h"
18#include <numeric>
19#include <optional>
20#include <stack>

22#define DEBUG_TYPE"shrinkwrapping" "shrinkwrapping"

24using namespace llvm;

26namespace opts {

28extern cl::opt<bool> TimeOpts;
29extern cl::OptionCategory BoltOptCategory;

31static cl::opt<unsigned> ShrinkWrappingThreshold(
  "shrink-wrapping-threshold",
  cl::desc("Percentage of prologue execution count to use as threshold when"
           " evaluating whether a block is cold enough to be profitable to"
           " move eligible spills there"),
  cl::init(30), cl::ZeroOrMore, cl::cat(BoltOptCategory));
37} // namespace opts

39namespace llvm {
40namespace bolt {

42void CalleeSavedAnalysis::analyzeSaves() {
ReachingDefOrUse</*Def=*/true> &RD = Info.getReachingDefs();
StackReachingUses &SRU = Info.getStackReachingUses();
auto &InsnToBB = Info.getInsnToBBMap();
BitVector BlacklistedRegs(BC.MRI->getNumRegs(), false);

LLVM_DEBUG(dbgs() << "Checking spill locations\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "Checking spill locations\n"
; } } while (false);
for (BinaryBasicBlock &BB : BF) {
  LLVM_DEBUG(dbgs() << "\tNow at BB " << BB.getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "\tNow at BB " <<
 BB.getName() << "\n"; } } while (false);
  const MCInst *Prev = nullptr;
  for (MCInst &Inst : BB) {
    if (ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(Inst)) {
      // Blacklist weird stores we don't understand
      if ((!FIE->IsSimple || FIE->StackOffset >= 0) && FIE->IsStore &&
          FIE->IsStoreFromReg) {
        BlacklistedRegs.set(FIE->RegOrImm);
        CalleeSaved.reset(FIE->RegOrImm);
        Prev = &Inst;
        continue;
      }

      if (!FIE->IsStore || !FIE->IsStoreFromReg ||
          BlacklistedRegs[FIE->RegOrImm]) {
        Prev = &Inst;
        continue;
      }

      // If this reg is defined locally, it is not a callee-saved reg
      if (RD.isReachedBy(FIE->RegOrImm,
                         Prev ? RD.expr_begin(*Prev) : RD.expr_begin(BB))) {
        BlacklistedRegs.set(FIE->RegOrImm);
        CalleeSaved.reset(FIE->RegOrImm);
        Prev = &Inst;
        continue;
      }

      // If this stack position is accessed in another function, we are
      // probably dealing with a parameter passed in a stack -- do not mess
      // with it
      if (SRU.isStoreUsed(*FIE,
                          Prev ? SRU.expr_begin(*Prev) : SRU.expr_begin(BB)),
          /*IncludeLocalAccesses=*/false) {
        BlacklistedRegs.set(FIE->RegOrImm);
        CalleeSaved.reset(FIE->RegOrImm);
        Prev = &Inst;
        continue;
      }

      // If this stack position is loaded elsewhere in another reg, we can't
      // update it, so blacklist it.
      if (SRU.isLoadedInDifferentReg(*FIE, Prev ? SRU.expr_begin(*Prev)
                                                : SRU.expr_begin(BB))) {
        BlacklistedRegs.set(FIE->RegOrImm);
        CalleeSaved.reset(FIE->RegOrImm);
        Prev = &Inst;
        continue;
      }

      // Ignore regs with multiple saves
      if (CalleeSaved[FIE->RegOrImm]) {
        BlacklistedRegs.set(FIE->RegOrImm);
        CalleeSaved.reset(FIE->RegOrImm);
        Prev = &Inst;
        continue;
      }

      CalleeSaved.set(FIE->RegOrImm);
      SaveFIEByReg[FIE->RegOrImm] = &*FIE;
      SavingCost[FIE->RegOrImm] += InsnToBB[&Inst]->getKnownExecutionCount();
      BC.MIB->addAnnotation(Inst, getSaveTag(), FIE->RegOrImm, AllocatorId);
      OffsetsByReg[FIE->RegOrImm] = FIE->StackOffset;
      LLVM_DEBUG(dbgs() << "Logging new candidate for Callee-Saved Reg: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "Logging new candidate for Callee-Saved Reg: "
 << FIE->RegOrImm << "\n"; } } while (false)
                        << FIE->RegOrImm << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "Logging new candidate for Callee-Saved Reg: "
 << FIE->RegOrImm << "\n"; } } while (false);
    }
    Prev = &Inst;
  }
}
119}

121void CalleeSavedAnalysis::analyzeRestores() {
ReachingDefOrUse</*Def=*/false> &RU = Info.getReachingUses();

// Now compute all restores of these callee-saved regs
for (BinaryBasicBlock &BB : BF) {
  const MCInst *Prev = nullptr;
  for (MCInst &Inst : llvm::reverse(BB)) {
    if (ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(Inst)) {
      if (!FIE->IsLoad || !CalleeSaved[FIE->RegOrImm]) {
        Prev = &Inst;
        continue;
      }

      // If this reg is used locally after a restore, then we are probably
      // not dealing with a callee-saved reg. Except if this use is by
      // another store, but we don't cover this case yet.
      // Also not callee-saved if this load accesses caller stack or isn't
      // simple.
      if (!FIE->IsSimple || FIE->StackOffset >= 0 ||
          RU.isReachedBy(FIE->RegOrImm,
                         Prev ? RU.expr_begin(*Prev) : RU.expr_begin(BB))) {
        CalleeSaved.reset(FIE->RegOrImm);
        Prev = &Inst;
        continue;
      }
      // If stack offsets between saves/store don't agree with each other,
      // we don't completely understand what's happening here
      if (FIE->StackOffset != OffsetsByReg[FIE->RegOrImm]) {
        CalleeSaved.reset(FIE->RegOrImm);
        LLVM_DEBUG(dbgs() << "Dismissing Callee-Saved Reg because we found a "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "Dismissing Callee-Saved Reg because we found a "
 "mismatching restore: " << FIE->RegOrImm << "\n"
; } } while (false)
                             "mismatching restore: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "Dismissing Callee-Saved Reg because we found a "
 "mismatching restore: " << FIE->RegOrImm << "\n"
; } } while (false)
                          << FIE->RegOrImm << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "Dismissing Callee-Saved Reg because we found a "
 "mismatching restore: " << FIE->RegOrImm << "\n"
; } } while (false);
        Prev = &Inst;
        continue;
      }

      LLVM_DEBUG(dbgs() << "Adding matching restore for: " << FIE->RegOrImmdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "Adding matching restore for: "
 << FIE->RegOrImm << "\n"; } } while (false)
                        << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "Adding matching restore for: "
 << FIE->RegOrImm << "\n"; } } while (false);
      if (LoadFIEByReg[FIE->RegOrImm] == nullptr)
        LoadFIEByReg[FIE->RegOrImm] = &*FIE;
      BC.MIB->addAnnotation(Inst, getRestoreTag(), FIE->RegOrImm,
                            AllocatorId);
      HasRestores.set(FIE->RegOrImm);
    }
    Prev = &Inst;
  }
}
168}

170std::vector<MCInst *> CalleeSavedAnalysis::getSavesByReg(uint16_t Reg) {
std::vector<MCInst *> Results;
for (BinaryBasicBlock &BB : BF)
  for (MCInst &Inst : BB)
    if (getSavedReg(Inst) == Reg)
      Results.push_back(&Inst);
return Results;
177}

179std::vector<MCInst *> CalleeSavedAnalysis::getRestoresByReg(uint16_t Reg) {
std::vector<MCInst *> Results;
for (BinaryBasicBlock &BB : BF)
  for (MCInst &Inst : BB)
    if (getRestoredReg(Inst) == Reg)
      Results.push_back(&Inst);
return Results;
186}

188CalleeSavedAnalysis::~CalleeSavedAnalysis() {
for (BinaryBasicBlock &BB : BF) {
  for (MCInst &Inst : BB) {
    BC.MIB->removeAnnotation(Inst, getSaveTag());
    BC.MIB->removeAnnotation(Inst, getRestoreTag());
  }
}
195}

197void StackLayoutModifier::blacklistRegion(int64_t Offset, int64_t Size) {
if (BlacklistedRegions[Offset] < Size)
  BlacklistedRegions[Offset] = Size;
200}

202bool StackLayoutModifier::isRegionBlacklisted(int64_t Offset, int64_t Size) {
for (std::pair<const int64_t, int64_t> Elem : BlacklistedRegions)
  if (Offset + Size > Elem.first && Offset < Elem.first + Elem.second)
    return true;
return false;
207}

209bool StackLayoutModifier::blacklistAllInConflictWith(int64_t Offset,
                                                   int64_t Size) {
bool HasConflict = false;
for (auto Iter = AvailableRegions.begin(); Iter != AvailableRegions.end();) {
  std::pair<const int64_t, int64_t> &Elem = *Iter;
  if (Offset + Size > Elem.first && Offset < Elem.first + Elem.second &&
      (Offset != Elem.first || Size != Elem.second)) {
    Iter = AvailableRegions.erase(Iter);
    HasConflict = true;
    continue;
  }
  ++Iter;
}
if (HasConflict) {
  blacklistRegion(Offset, Size);
  return true;
}
return false;
227}

229void StackLayoutModifier::checkFramePointerInitialization(MCInst &Point) {
StackPointerTracking &SPT = Info.getStackPointerTracking();
if (!BC.MII->get(Point.getOpcode())
         .hasDefOfPhysReg(Point, BC.MIB->getFramePointer(), *BC.MRI))
  return;

int SPVal, FPVal;
std::tie(SPVal, FPVal) = *SPT.getStateBefore(Point);
std::pair<MCPhysReg, int64_t> FP;

if (FPVal != SPT.EMPTY && FPVal != SPT.SUPERPOSITION)
  FP = std::make_pair(BC.MIB->getFramePointer(), FPVal);
else
  FP = std::make_pair(0, 0);
std::pair<MCPhysReg, int64_t> SP;

if (SPVal != SPT.EMPTY && SPVal != SPT.SUPERPOSITION)
  SP = std::make_pair(BC.MIB->getStackPointer(), SPVal);
else
  SP = std::make_pair(0, 0);

int64_t Output;
if (!BC.MIB->evaluateStackOffsetExpr(Point, Output, SP, FP))
  return;

// Not your regular frame pointer initialization... bail
if (Output != SPVal)
  blacklistRegion(0, 0);
257}

259void StackLayoutModifier::checkStackPointerRestore(MCInst &Point) {
StackPointerTracking &SPT = Info.getStackPointerTracking();
if (!BC.MII->get(Point.getOpcode())
         .hasDefOfPhysReg(Point, BC.MIB->getStackPointer(), *BC.MRI))
  return;
// Check if the definition of SP comes from FP -- in this case, this
// value may need to be updated depending on our stack layout changes
const MCInstrDesc &InstInfo = BC.MII->get(Point.getOpcode());
unsigned NumDefs = InstInfo.getNumDefs();
bool UsesFP = llvm::any_of(
    llvm::drop_begin(MCPlus::primeOperands(Point), NumDefs),
    [&](MCOperand &Op) {
      return Op.isReg() && Op.getReg() == BC.MIB->getFramePointer();
    });
if (!UsesFP)
  return;

// Setting up evaluation
int SPVal, FPVal;
std::tie(SPVal, FPVal) = *SPT.getStateBefore(Point);
std::pair<MCPhysReg, int64_t> FP;

if (FPVal != SPT.EMPTY && FPVal != SPT.SUPERPOSITION)
  FP = std::make_pair(BC.MIB->getFramePointer(), FPVal);
else
  FP = std::make_pair(0, 0);
std::pair<MCPhysReg, int64_t> SP;

if (SPVal != SPT.EMPTY && SPVal != SPT.SUPERPOSITION)
  SP = std::make_pair(BC.MIB->getStackPointer(), SPVal);
else
  SP = std::make_pair(0, 0);

int64_t Output;
if (!BC.MIB->evaluateStackOffsetExpr(Point, Output, SP, FP))
  return;

// If the value is the same of FP, no need to adjust it
if (Output == FPVal)
  return;

// If an allocation happened through FP, bail
if (Output <= SPVal) {
  blacklistRegion(0, 0);
  return;
}

// We are restoring SP to an old value based on FP. Mark it as a stack
// access to be fixed later.
BC.MIB->addAnnotation(Point, getSlotTag(), Output, AllocatorId);
309}

311void StackLayoutModifier::classifyStackAccesses() {
// Understand when stack slots are being used non-locally
StackReachingUses &SRU = Info.getStackReachingUses();

for (BinaryBasicBlock &BB : BF) {
  const MCInst *Prev = nullptr;
  for (MCInst &Inst : llvm::reverse(BB)) {
    checkFramePointerInitialization(Inst);
    checkStackPointerRestore(Inst);
    ErrorOr<const FrameIndexEntry &> FIEX = FA.getFIEFor(Inst);
    if (!FIEX) {
      Prev = &Inst;
      continue;
    }
    if (!FIEX->IsSimple || (FIEX->IsStore && !FIEX->IsStoreFromReg)) {
      blacklistRegion(FIEX->StackOffset, FIEX->Size);
      Prev = &Inst;
      continue;
    }
    // If this stack position is accessed in another function, we are
    // probably dealing with a parameter passed in a stack -- do not mess
    // with it
    if (SRU.isStoreUsed(*FIEX,
                        Prev ? SRU.expr_begin(*Prev) : SRU.expr_begin(BB),
                        /*IncludeLocalAccesses=*/false)) {
      blacklistRegion(FIEX->StackOffset, FIEX->Size);
      Prev = &Inst;
      continue;
    }
    // Now we have a clear stack slot access. Check if its blacklisted or if
    // it conflicts with another chunk.
    if (isRegionBlacklisted(FIEX->StackOffset, FIEX->Size) ||
        blacklistAllInConflictWith(FIEX->StackOffset, FIEX->Size)) {
      Prev = &Inst;
      continue;
    }
    // We are free to go. Add it as available stack slot which we know how
    // to move it.
    AvailableRegions[FIEX->StackOffset] = FIEX->Size;
    BC.MIB->addAnnotation(Inst, getSlotTag(), FIEX->StackOffset, AllocatorId);
    RegionToRegMap[FIEX->StackOffset].insert(FIEX->RegOrImm);
    RegToRegionMap[FIEX->RegOrImm].insert(FIEX->StackOffset);
    LLVM_DEBUG(dbgs() << "Adding region " << FIEX->StackOffset << " size "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "Adding region " <<
 FIEX->StackOffset << " size " << (int)FIEX->
Size << "\n"; } } while (false)
                      << (int)FIEX->Size << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "Adding region " <<
 FIEX->StackOffset << " size " << (int)FIEX->
Size << "\n"; } } while (false);
  }
}
357}

359void StackLayoutModifier::classifyCFIs() {
std::stack<std::pair<int64_t, uint16_t>> CFIStack;
int64_t CfaOffset = -8;
uint16_t CfaReg = 7;

auto recordAccess = [&](MCInst *Inst, int64_t Offset) {
  const uint16_t Reg = *BC.MRI->getLLVMRegNum(CfaReg, /*isEH=*/false);
  if (Reg == BC.MIB->getStackPointer() || Reg == BC.MIB->getFramePointer()) {
    BC.MIB->addAnnotation(*Inst, getSlotTag(), Offset, AllocatorId);
    LLVM_DEBUG(dbgs() << "Recording CFI " << Offset << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "Recording CFI " <<
 Offset << "\n"; } } while (false);
  } else {
    IsSimple = false;
    return;
  }
};

for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
  for (MCInst &Inst : *BB) {
    if (!BC.MIB->isCFI(Inst))
      continue;
    const MCCFIInstruction *CFI = BF.getCFIFor(Inst);
    switch (CFI->getOperation()) {
    case MCCFIInstruction::OpDefCfa:
      CfaOffset = -CFI->getOffset();
      recordAccess(&Inst, CfaOffset);
      [[fallthrough]];
    case MCCFIInstruction::OpDefCfaRegister:
      CfaReg = CFI->getRegister();
      break;
    case MCCFIInstruction::OpDefCfaOffset:
      CfaOffset = -CFI->getOffset();
      recordAccess(&Inst, CfaOffset);
      break;
    case MCCFIInstruction::OpOffset:
      recordAccess(&Inst, CFI->getOffset());
      BC.MIB->addAnnotation(Inst, getOffsetCFIRegTag(),
                            BC.MRI->getLLVMRegNum(CFI->getRegister(),
                                                  /*isEH=*/false),
                            AllocatorId);
      break;
    case MCCFIInstruction::OpSameValue:
      BC.MIB->addAnnotation(Inst, getOffsetCFIRegTag(),
                            BC.MRI->getLLVMRegNum(CFI->getRegister(),
                                                  /*isEH=*/false),
                            AllocatorId);
      break;
    case MCCFIInstruction::OpRememberState:
      CFIStack.push(std::make_pair(CfaOffset, CfaReg));
      break;
    case MCCFIInstruction::OpRestoreState: {
      assert(!CFIStack.empty() && "Corrupt CFI stack")(static_cast <bool> (!CFIStack.empty() && "Corrupt CFI stack"
) ? void (0) : __assert_fail ("!CFIStack.empty() && \"Corrupt CFI stack\""
, "bolt/lib/Passes/ShrinkWrapping.cpp", 409, __extension__ __PRETTY_FUNCTION__
));
      std::pair<int64_t, uint16_t> &Elem = CFIStack.top();
      CFIStack.pop();
      CfaOffset = Elem.first;
      CfaReg = Elem.second;
      break;
    }
    case MCCFIInstruction::OpRelOffset:
    case MCCFIInstruction::OpAdjustCfaOffset:
      llvm_unreachable("Unhandled AdjustCfaOffset")::llvm::llvm_unreachable_internal("Unhandled AdjustCfaOffset"
, "bolt/lib/Passes/ShrinkWrapping.cpp", 418);
      break;
    default:
      break;
    }
  }
}
425}

427void StackLayoutModifier::scheduleChange(
  MCInst &Inst, StackLayoutModifier::WorklistItem Item) {
auto &WList = BC.MIB->getOrCreateAnnotationAs<std::vector<WorklistItem>>(
    Inst, getTodoTag(), AllocatorId);
WList.push_back(Item);
432}

434bool StackLayoutModifier::canCollapseRegion(MCInst *DeletedPush) {
if (!IsSimple || !BC.MIB->isPush(*DeletedPush))
  return false;

ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(*DeletedPush);
if (!FIE)
  return false;

return canCollapseRegion(FIE->StackOffset);
443}

445bool StackLayoutModifier::canCollapseRegion(int64_t RegionAddr) {
if (!IsInitialized)
  initialize();
if (!IsSimple)
  return false;

if (CollapsedRegions.count(RegionAddr))
  return true;

// Check if it is possible to readjust all accesses below RegionAddr
if (!BlacklistedRegions.empty())
  return false;

return true;
459}

461bool StackLayoutModifier::collapseRegion(MCInst *DeletedPush) {
ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(*DeletedPush);
if (!FIE)
  return false;
int64_t RegionAddr = FIE->StackOffset;
int64_t RegionSz = FIE->Size;
return collapseRegion(DeletedPush, RegionAddr, RegionSz);
468}

470bool StackLayoutModifier::collapseRegion(MCInst *Alloc, int64_t RegionAddr,
                                       int64_t RegionSz) {
if (!canCollapseRegion(RegionAddr))
  return false;

assert(IsInitialized)(static_cast <bool> (IsInitialized) ? void (0) : __assert_fail
 ("IsInitialized", "bolt/lib/Passes/ShrinkWrapping.cpp", 475,
 __extension__ __PRETTY_FUNCTION__));
StackAllocationAnalysis &SAA = Info.getStackAllocationAnalysis();

for (BinaryBasicBlock &BB : BF) {
  for (MCInst &Inst : BB) {
    if (!BC.MIB->hasAnnotation(Inst, getSlotTag()))
      continue;
    auto Slot =
        BC.MIB->getAnnotationAs<decltype(FrameIndexEntry::StackOffset)>(
            Inst, getSlotTag());
    if (!AvailableRegions.count(Slot))
      continue;
    // We need to ensure this access is affected by the deleted push
    if (!(*SAA.getStateBefore(Inst))[SAA.ExprToIdx[Alloc]])
      continue;

    if (BC.MIB->isCFI(Inst)) {
      if (Slot > RegionAddr)
        continue;
      scheduleChange(Inst, WorklistItem(WorklistItem::AdjustCFI, RegionSz));
      continue;
    }
    ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(Inst);
    if (!FIE) {
      if (Slot > RegionAddr)
        continue;
      // SP update based on frame pointer
      scheduleChange(
          Inst, WorklistItem(WorklistItem::AdjustLoadStoreOffset, RegionSz));
      continue;
    }

    if (Slot == RegionAddr) {
      BC.MIB->addAnnotation(Inst, "AccessesDeletedPos", 0U, AllocatorId);
      continue;
    }
    if (BC.MIB->isPush(Inst) || BC.MIB->isPop(Inst))
      continue;

    if (FIE->StackPtrReg == BC.MIB->getStackPointer() && Slot < RegionAddr)
      continue;

    if (FIE->StackPtrReg == BC.MIB->getFramePointer() && Slot > RegionAddr)
      continue;

    scheduleChange(
        Inst, WorklistItem(WorklistItem::AdjustLoadStoreOffset, RegionSz));
  }
}

CollapsedRegions.insert(RegionAddr);
return true;
527}

529void StackLayoutModifier::setOffsetForCollapsedAccesses(int64_t NewOffset) {
for (BinaryBasicBlock &BB : BF) {
  for (MCInst &Inst : BB) {
    if (!BC.MIB->hasAnnotation(Inst, "AccessesDeletedPos"))
      continue;
    BC.MIB->removeAnnotation(Inst, "AccessesDeletedPos");
    scheduleChange(
        Inst, WorklistItem(WorklistItem::AdjustLoadStoreOffset, NewOffset));
  }
}
539}

541bool StackLayoutModifier::canInsertRegion(ProgramPoint P) {
if (!IsInitialized)
  initialize();
if (!IsSimple)
  return false;

StackPointerTracking &SPT = Info.getStackPointerTracking();
int64_t RegionAddr = SPT.getStateBefore(P)->first;
if (RegionAddr == SPT.SUPERPOSITION || RegionAddr == SPT.EMPTY)
  return false;

if (InsertedRegions.count(RegionAddr))
  return true;

// Check if we are going to screw up stack accesses at call sites that
// pass parameters via stack
if (!BlacklistedRegions.empty())
  return false;

return true;
561}

563bool StackLayoutModifier::insertRegion(ProgramPoint P, int64_t RegionSz) {
if (!canInsertRegion(P))
  return false;

assert(IsInitialized)(static_cast <bool> (IsInitialized) ? void (0) : __assert_fail
 ("IsInitialized", "bolt/lib/Passes/ShrinkWrapping.cpp", 567,
 __extension__ __PRETTY_FUNCTION__));
StackPointerTracking &SPT = Info.getStackPointerTracking();
// This RegionAddr is slightly different from the one seen in collapseRegion
// This is the value of SP before the allocation the user wants to make.
int64_t RegionAddr = SPT.getStateBefore(P)->first;
if (RegionAddr == SPT.SUPERPOSITION || RegionAddr == SPT.EMPTY)
  return false;

DominatorAnalysis<false> &DA = Info.getDominatorAnalysis();

for (BinaryBasicBlock &BB : BF) {
  for (MCInst &Inst : BB) {
    if (!BC.MIB->hasAnnotation(Inst, getSlotTag()))
      continue;
    auto Slot =
        BC.MIB->getAnnotationAs<decltype(FrameIndexEntry::StackOffset)>(
            Inst, getSlotTag());
    if (!AvailableRegions.count(Slot))
      continue;

    if (!(DA.doesADominateB(P, Inst)))
      continue;

    if (BC.MIB->isCFI(Inst)) {
      if (Slot >= RegionAddr)
        continue;
      scheduleChange(Inst, WorklistItem(WorklistItem::AdjustCFI, -RegionSz));
      continue;
    }
    ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(Inst);
    if (!FIE) {
      if (Slot >= RegionAddr)
        continue;
      scheduleChange(
          Inst, WorklistItem(WorklistItem::AdjustLoadStoreOffset, -RegionSz));
      continue;
    }

    if (FIE->StackPtrReg == BC.MIB->getStackPointer() && Slot < RegionAddr)
      continue;
    if (FIE->StackPtrReg == BC.MIB->getFramePointer() && Slot >= RegionAddr)
      continue;
    if (BC.MIB->isPush(Inst) || BC.MIB->isPop(Inst))
      continue;
    scheduleChange(
        Inst, WorklistItem(WorklistItem::AdjustLoadStoreOffset, -RegionSz));
  }
}

InsertedRegions.insert(RegionAddr);
return true;
618}

620void StackLayoutModifier::performChanges() {
std::set<uint32_t> ModifiedCFIIndices;
for (BinaryBasicBlock &BB : BF) {
  for (MCInst &Inst : llvm::reverse(BB)) {
    if (BC.MIB->hasAnnotation(Inst, "AccessesDeletedPos")) {
      assert(BC.MIB->isPop(Inst) || BC.MIB->isPush(Inst))(static_cast <bool> (BC.MIB->isPop(Inst) || BC.MIB->
isPush(Inst)) ? void (0) : __assert_fail ("BC.MIB->isPop(Inst) || BC.MIB->isPush(Inst)"
, "bolt/lib/Passes/ShrinkWrapping.cpp", 625, __extension__ __PRETTY_FUNCTION__
));
      BC.MIB->removeAnnotation(Inst, "AccessesDeletedPos");
    }
    if (!BC.MIB->hasAnnotation(Inst, getTodoTag()))
      continue;
    auto &WList = BC.MIB->getAnnotationAs<std::vector<WorklistItem>>(
        Inst, getTodoTag());
    int64_t Adjustment = 0;
    WorklistItem::ActionType AdjustmentType = WorklistItem::None;
    for (WorklistItem &WI : WList) {
      if (WI.Action == WorklistItem::None)
        continue;
      assert(WI.Action == WorklistItem::AdjustLoadStoreOffset ||(static_cast <bool> (WI.Action == WorklistItem::AdjustLoadStoreOffset
 || WI.Action == WorklistItem::AdjustCFI) ? void (0) : __assert_fail
 ("WI.Action == WorklistItem::AdjustLoadStoreOffset || WI.Action == WorklistItem::AdjustCFI"
, "bolt/lib/Passes/ShrinkWrapping.cpp", 638, __extension__ __PRETTY_FUNCTION__
))
             WI.Action == WorklistItem::AdjustCFI)(static_cast <bool> (WI.Action == WorklistItem::AdjustLoadStoreOffset
 || WI.Action == WorklistItem::AdjustCFI) ? void (0) : __assert_fail
 ("WI.Action == WorklistItem::AdjustLoadStoreOffset || WI.Action == WorklistItem::AdjustCFI"
, "bolt/lib/Passes/ShrinkWrapping.cpp", 638, __extension__ __PRETTY_FUNCTION__
));
      assert((AdjustmentType == WorklistItem::None ||(static_cast <bool> ((AdjustmentType == WorklistItem::None
 || AdjustmentType == WI.Action) && "Conflicting actions requested at the same program point"
) ? void (0) : __assert_fail ("(AdjustmentType == WorklistItem::None || AdjustmentType == WI.Action) && \"Conflicting actions requested at the same program point\""
, "bolt/lib/Passes/ShrinkWrapping.cpp", 641, __extension__ __PRETTY_FUNCTION__
))
              AdjustmentType == WI.Action) &&(static_cast <bool> ((AdjustmentType == WorklistItem::None
 || AdjustmentType == WI.Action) && "Conflicting actions requested at the same program point"
) ? void (0) : __assert_fail ("(AdjustmentType == WorklistItem::None || AdjustmentType == WI.Action) && \"Conflicting actions requested at the same program point\""
, "bolt/lib/Passes/ShrinkWrapping.cpp", 641, __extension__ __PRETTY_FUNCTION__
))
             "Conflicting actions requested at the same program point")(static_cast <bool> ((AdjustmentType == WorklistItem::None
 || AdjustmentType == WI.Action) && "Conflicting actions requested at the same program point"
) ? void (0) : __assert_fail ("(AdjustmentType == WorklistItem::None || AdjustmentType == WI.Action) && \"Conflicting actions requested at the same program point\""
, "bolt/lib/Passes/ShrinkWrapping.cpp", 641, __extension__ __PRETTY_FUNCTION__
));
      AdjustmentType = WI.Action;
      Adjustment += WI.OffsetUpdate;
    }
    if (!Adjustment)
      continue;
    if (AdjustmentType != WorklistItem::AdjustLoadStoreOffset) {
      assert(BC.MIB->isCFI(Inst))(static_cast <bool> (BC.MIB->isCFI(Inst)) ? void (0)
 : __assert_fail ("BC.MIB->isCFI(Inst)", "bolt/lib/Passes/ShrinkWrapping.cpp"
, 648, __extension__ __PRETTY_FUNCTION__));
      uint32_t CFINum = Inst.getOperand(0).getImm();
      if (ModifiedCFIIndices.count(CFINum))
        continue;
      ModifiedCFIIndices.insert(CFINum);
      const MCCFIInstruction *CFI = BF.getCFIFor(Inst);
      const MCCFIInstruction::OpType Operation = CFI->getOperation();
      if (Operation == MCCFIInstruction::OpDefCfa ||
          Operation == MCCFIInstruction::OpDefCfaOffset)
        Adjustment = 0 - Adjustment;
      LLVM_DEBUG(dbgs() << "Changing CFI offset from " << CFI->getOffset()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "Changing CFI offset from "
 << CFI->getOffset() << " to " << (CFI->
getOffset() + Adjustment) << "\n"; } } while (false)
                        << " to " << (CFI->getOffset() + Adjustment) << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "Changing CFI offset from "
 << CFI->getOffset() << " to " << (CFI->
getOffset() + Adjustment) << "\n"; } } while (false);
      BF.mutateCFIOffsetFor(Inst, CFI->getOffset() + Adjustment);
      continue;
    }
    int32_t SrcImm = 0;
    MCPhysReg Reg = 0;
    MCPhysReg StackPtrReg = 0;
    int64_t StackOffset = 0;
    bool IsIndexed = false;
    bool IsLoad = false;
    bool IsStore = false;
    bool IsSimple = false;
    bool IsStoreFromReg = false;
    uint8_t Size = 0;
    bool Success = false;
    Success = BC.MIB->isStackAccess(Inst, IsLoad, IsStore, IsStoreFromReg,
                                    Reg, SrcImm, StackPtrReg, StackOffset,
                                    Size, IsSimple, IsIndexed);
    if (!Success) {
      // SP update based on FP value
      Success = BC.MIB->addToImm(Inst, Adjustment, &*BC.Ctx);
      assert(Success)(static_cast <bool> (Success) ? void (0) : __assert_fail
 ("Success", "bolt/lib/Passes/ShrinkWrapping.cpp", 680, __extension__
 __PRETTY_FUNCTION__));
      continue;
    }
    assert(Success && IsSimple && !IsIndexed && (!IsStore || IsStoreFromReg))(static_cast <bool> (Success && IsSimple &&
 !IsIndexed && (!IsStore || IsStoreFromReg)) ? void (
0) : __assert_fail ("Success && IsSimple && !IsIndexed && (!IsStore || IsStoreFromReg)"
, "bolt/lib/Passes/ShrinkWrapping.cpp", 683, __extension__ __PRETTY_FUNCTION__
));
    if (StackPtrReg != BC.MIB->getFramePointer())
      Adjustment = -Adjustment;
    if (IsLoad)
      Success = BC.MIB->createRestoreFromStack(
          Inst, StackPtrReg, StackOffset + Adjustment, Reg, Size);
    else if (IsStore)
      Success = BC.MIB->createSaveToStack(
          Inst, StackPtrReg, StackOffset + Adjustment, Reg, Size);
    LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Adjusted instruction: "
; Inst.dump(); }; } } while (false)
      dbgs() << "Adjusted instruction: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Adjusted instruction: "
; Inst.dump(); }; } } while (false)
      Inst.dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Adjusted instruction: "
; Inst.dump(); }; } } while (false)
    })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Adjusted instruction: "
; Inst.dump(); }; } } while (false);
    assert(Success)(static_cast <bool> (Success) ? void (0) : __assert_fail
 ("Success", "bolt/lib/Passes/ShrinkWrapping.cpp", 696, __extension__
 __PRETTY_FUNCTION__));
  }
}
699}

701void StackLayoutModifier::initialize() {
classifyStackAccesses();
classifyCFIs();
IsInitialized = true;
705}

707std::atomic<std::uint64_t> ShrinkWrapping::SpillsMovedRegularMode{0};
708std::atomic<std::uint64_t> ShrinkWrapping::SpillsMovedPushPopMode{0};
709std::atomic<std::uint64_t> ShrinkWrapping::SpillsMovedDynamicCount{0};
710std::atomic<std::uint64_t> ShrinkWrapping::SpillsFailedDynamicCount{0};
711std::atomic<std::uint64_t> ShrinkWrapping::InstrDynamicCount{0};
712std::atomic<std::uint64_t> ShrinkWrapping::StoreDynamicCount{0};

714using BBIterTy = BinaryBasicBlock::iterator;

716void ShrinkWrapping::classifyCSRUses() {
DominatorAnalysis<false> &DA = Info.getDominatorAnalysis();
StackPointerTracking &SPT = Info.getStackPointerTracking();
UsesByReg = std::vector<BitVector>(BC.MRI->getNumRegs(),
                                   BitVector(DA.NumInstrs, false));

const BitVector &FPAliases = BC.MIB->getAliases(BC.MIB->getFramePointer());
for (BinaryBasicBlock &BB : BF) {
  for (MCInst &Inst : BB) {
    if (BC.MIB->isCFI(Inst))
      continue;
    BitVector BV = BitVector(BC.MRI->getNumRegs(), false);
    BC.MIB->getTouchedRegs(Inst, BV);
    BV &= CSA.CalleeSaved;
    for (int I : BV.set_bits()) {
      if (I == 0)
        continue;
      if (CSA.getSavedReg(Inst) != I && CSA.getRestoredReg(Inst) != I)
        UsesByReg[I].set(DA.ExprToIdx[&Inst]);
    }
    if (!SPT.HasFramePointer || !BC.MIB->isCall(Inst))
      continue;
    BV = CSA.CalleeSaved;
    BV &= FPAliases;
    for (int I : BV.set_bits())
      UsesByReg[I].set(DA.ExprToIdx[&Inst]);
  }
}
744}

746void ShrinkWrapping::pruneUnwantedCSRs() {
BitVector ParamRegs = BC.MIB->getRegsUsedAsParams();
for (unsigned I = 0, E = BC.MRI->getNumRegs(); I != E; ++I) {
  if (!CSA.CalleeSaved[I])
    continue;
  if (ParamRegs[I]) {
    CSA.CalleeSaved.reset(I);
    continue;
  }
  if (UsesByReg[I].empty()) {
    LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "Dismissing Callee-Saved Reg because we found no uses of it:"
 << I << "\n"; } } while (false)
        dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "Dismissing Callee-Saved Reg because we found no uses of it:"
 << I << "\n"; } } while (false)
        << "Dismissing Callee-Saved Reg because we found no uses of it:" << Ido { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "Dismissing Callee-Saved Reg because we found no uses of it:"
 << I << "\n"; } } while (false)
        << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "Dismissing Callee-Saved Reg because we found no uses of it:"
 << I << "\n"; } } while (false);
    CSA.CalleeSaved.reset(I);
    continue;
  }
  if (!CSA.HasRestores[I]) {
    LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "Dismissing Callee-Saved Reg because it does not have "
 "restores:" << I << "\n"; } } while (false)
        dbgs() << "Dismissing Callee-Saved Reg because it does not have "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "Dismissing Callee-Saved Reg because it does not have "
 "restores:" << I << "\n"; } } while (false)
                  "restores:"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "Dismissing Callee-Saved Reg because it does not have "
 "restores:" << I << "\n"; } } while (false)
               << I << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "Dismissing Callee-Saved Reg because it does not have "
 "restores:" << I << "\n"; } } while (false);
    CSA.CalleeSaved.reset(I);
  }
}
771}

773void ShrinkWrapping::computeSaveLocations() {
BestSavePos = std::vector<std::vector<MCInst *>>(BC.MRI->getNumRegs());
ReachingInsns<true> &RI = Info.getReachingInsnsBackwards();
DominatorAnalysis<false> &DA = Info.getDominatorAnalysis();
StackPointerTracking &SPT = Info.getStackPointerTracking();

LLVM_DEBUG(dbgs() << "Checking save/restore possibilities\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "Checking save/restore possibilities\n"
; } } while (false);
for (BinaryBasicBlock &BB : BF) {
  LLVM_DEBUG(dbgs() << "\tNow at BB " << BB.getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "\tNow at BB " <<
 BB.getName() << "\n"; } } while (false);

  MCInst *First = BB.begin() != BB.end() ? &*BB.begin() : nullptr;
  if (!First)
    continue;

  // Use reaching instructions to detect if we are inside a loop - if we
  // are, do not consider this BB as valid placement for saves.
  if (RI.isInLoop(BB))
    continue;

  const std::pair<int, int> SPFP = *SPT.getStateBefore(*First);
  // If we don't know stack state at this point, bail
  if ((SPFP.first == SPT.SUPERPOSITION || SPFP.first == SPT.EMPTY) &&
      (SPFP.second == SPT.SUPERPOSITION || SPFP.second == SPT.EMPTY))
    continue;

  for (unsigned I = 0, E = BC.MRI->getNumRegs(); I != E; ++I) {
    if (!CSA.CalleeSaved[I])
      continue;

    BitVector BBDominatedUses = BitVector(DA.NumInstrs, false);
    for (int J : UsesByReg[I].set_bits())
      if (DA.doesADominateB(*First, J))
        BBDominatedUses.set(J);
    LLVM_DEBUG(dbgs() << "\t\tBB " << BB.getName() << " dominates "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "\t\tBB " << BB.getName
() << " dominates " << BBDominatedUses.count() <<
 " uses for reg " << I << ". Total uses for reg is "
 << UsesByReg[I].count() << "\n"; } } while (false
)
                      << BBDominatedUses.count() << " uses for reg " << Ido { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "\t\tBB " << BB.getName
() << " dominates " << BBDominatedUses.count() <<
 " uses for reg " << I << ". Total uses for reg is "
 << UsesByReg[I].count() << "\n"; } } while (false
)
                      << ". Total uses for reg is " << UsesByReg[I].count()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "\t\tBB " << BB.getName
() << " dominates " << BBDominatedUses.count() <<
 " uses for reg " << I << ". Total uses for reg is "
 << UsesByReg[I].count() << "\n"; } } while (false
)
                      << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "\t\tBB " << BB.getName
() << " dominates " << BBDominatedUses.count() <<
 " uses for reg " << I << ". Total uses for reg is "
 << UsesByReg[I].count() << "\n"; } } while (false
);
    BBDominatedUses &= UsesByReg[I];
    if (BBDominatedUses == UsesByReg[I]) {
      LLVM_DEBUG(dbgs() << "\t\t\tAdded " << BB.getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "\t\t\tAdded " <<
 BB.getName() << " as a save pos for " << I <<
 "\n"; } } while (false)
                        << " as a save pos for " << I << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "\t\t\tAdded " <<
 BB.getName() << " as a save pos for " << I <<
 "\n"; } } while (false);
      BestSavePos[I].push_back(First);
      LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Dominated uses are:\n"
; for (int J : UsesByReg[I].set_bits()) { dbgs() << "Idx "
 << J << ": "; BC.printInstruction(dbgs(), *DA.Expressions
[J]); DA.Expressions[J]->dump(); } }; } } while (false)
        dbgs() << "Dominated uses are:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Dominated uses are:\n"
; for (int J : UsesByReg[I].set_bits()) { dbgs() << "Idx "
 << J << ": "; BC.printInstruction(dbgs(), *DA.Expressions
[J]); DA.Expressions[J]->dump(); } }; } } while (false)
        for (int J : UsesByReg[I].set_bits()) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Dominated uses are:\n"
; for (int J : UsesByReg[I].set_bits()) { dbgs() << "Idx "
 << J << ": "; BC.printInstruction(dbgs(), *DA.Expressions
[J]); DA.Expressions[J]->dump(); } }; } } while (false)
          dbgs() << "Idx " << J << ": ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Dominated uses are:\n"
; for (int J : UsesByReg[I].set_bits()) { dbgs() << "Idx "
 << J << ": "; BC.printInstruction(dbgs(), *DA.Expressions
[J]); DA.Expressions[J]->dump(); } }; } } while (false)
          BC.printInstruction(dbgs(), *DA.Expressions[J]);do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Dominated uses are:\n"
; for (int J : UsesByReg[I].set_bits()) { dbgs() << "Idx "
 << J << ": "; BC.printInstruction(dbgs(), *DA.Expressions
[J]); DA.Expressions[J]->dump(); } }; } } while (false)
          DA.Expressions[J]->dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Dominated uses are:\n"
; for (int J : UsesByReg[I].set_bits()) { dbgs() << "Idx "
 << J << ": "; BC.printInstruction(dbgs(), *DA.Expressions
[J]); DA.Expressions[J]->dump(); } }; } } while (false)
        }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Dominated uses are:\n"
; for (int J : UsesByReg[I].set_bits()) { dbgs() << "Idx "
 << J << ": "; BC.printInstruction(dbgs(), *DA.Expressions
[J]); DA.Expressions[J]->dump(); } }; } } while (false)
      })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Dominated uses are:\n"
; for (int J : UsesByReg[I].set_bits()) { dbgs() << "Idx "
 << J << ": "; BC.printInstruction(dbgs(), *DA.Expressions
[J]); DA.Expressions[J]->dump(); } }; } } while (false);
    }
  }
}

BestSaveCount = std::vector<std::vector<uint64_t>>(BC.MRI->getNumRegs());

auto &InsnToBB = Info.getInsnToBBMap();
for (unsigned I = 0, E = BC.MRI->getNumRegs(); I != E; ++I) {
  if (!CSA.CalleeSaved[I])
    continue;

  std::stable_sort(BestSavePos[I].begin(), BestSavePos[I].end(),
                   [&](const MCInst *A, const MCInst *B) {
                     const BinaryBasicBlock *BBA = InsnToBB[A];
                     const BinaryBasicBlock *BBB = InsnToBB[B];
                     const uint64_t CountA = BBA->getKnownExecutionCount();
                     const uint64_t CountB = BBB->getKnownExecutionCount();
                     return CountB < CountA;
                   });

  for (MCInst *Pos : BestSavePos[I]) {
    const BinaryBasicBlock *BB = InsnToBB[Pos];
    const uint64_t Count = BB->getKnownExecutionCount();
    BestSaveCount[I].push_back(Count);
  }
}
849}

851void ShrinkWrapping::computeDomOrder() {
DomOrder = std::vector<MCPhysReg>(BC.MRI->getNumRegs(), 0);
std::vector<MCPhysReg> Order;
for (MCPhysReg I = 0, E = BC.MRI->getNumRegs(); I != E; ++I) {
  Order.push_back(I);
}

DominatorAnalysis<false> &DA = Info.getDominatorAnalysis();
auto &InsnToBB = Info.getInsnToBBMap();
llvm::sort(Order, [&](const MCPhysReg &A, const MCPhysReg &B) {
  BinaryBasicBlock *BBA =
      BestSavePos[A].size() ? InsnToBB[BestSavePos[A].back()] : nullptr;
  BinaryBasicBlock *BBB =
      BestSavePos[B].size() ? InsnToBB[BestSavePos[B].back()] : nullptr;
  if (BBA == BBB)
    return A < B;
  if (!BBA && BBB)
    return false;
  if (BBA && !BBB)
    return true;
  if (DA.doesADominateB(*BestSavePos[A].back(), *BestSavePos[B].back()))
    return true;
  if (DA.doesADominateB(*BestSavePos[B].back(), *BestSavePos[A].back()))
    return false;
  return A < B;
});

for (MCPhysReg I = 0, E = BC.MRI->getNumRegs(); I != E; ++I)
  DomOrder[Order[I]] = I;
880}

882bool ShrinkWrapping::isBestSavePosCold(unsigned CSR, MCInst *&BestPosSave,
                                     uint64_t &TotalEstimatedWin) {
const uint64_t CurSavingCost = CSA.SavingCost[CSR];
if (!CSA.CalleeSaved[CSR])
  return false;

assert(BestSaveCount[CSR].size() == BestSavePos[CSR].size() &&(static_cast <bool> (BestSaveCount[CSR].size() == BestSavePos
[CSR].size() && "save position vectors out of sync") ?
 void (0) : __assert_fail ("BestSaveCount[CSR].size() == BestSavePos[CSR].size() && \"save position vectors out of sync\""
, "bolt/lib/Passes/ShrinkWrapping.cpp", 889, __extension__ __PRETTY_FUNCTION__
))
       "save position vectors out of sync")(static_cast <bool> (BestSaveCount[CSR].size() == BestSavePos
[CSR].size() && "save position vectors out of sync") ?
 void (0) : __assert_fail ("BestSaveCount[CSR].size() == BestSavePos[CSR].size() && \"save position vectors out of sync\""
, "bolt/lib/Passes/ShrinkWrapping.cpp", 889, __extension__ __PRETTY_FUNCTION__
));
if (BestSaveCount[CSR].empty())
  return false;

const uint64_t BestCount = BestSaveCount[CSR].back();
BestPosSave = BestSavePos[CSR].back();
if (BestCount >= (opts::ShrinkWrappingThreshold / 100.0) * CurSavingCost)
  return false;

LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { auto &InsnToBB = Info.getInsnToBBMap
(); dbgs() << "Better position for saves found in func "
 << BF.getPrintName() << " count << " <<
 BF.getKnownExecutionCount() << "\n"; dbgs() << "Reg: "
 << CSR << "; New BB: " << InsnToBB[BestPosSave
]->getName() << " Freq reduction: " << (CurSavingCost
 - BestCount) << "\n"; }; } } while (false)
  auto &InsnToBB = Info.getInsnToBBMap();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { auto &InsnToBB = Info.getInsnToBBMap
(); dbgs() << "Better position for saves found in func "
 << BF.getPrintName() << " count << " <<
 BF.getKnownExecutionCount() << "\n"; dbgs() << "Reg: "
 << CSR << "; New BB: " << InsnToBB[BestPosSave
]->getName() << " Freq reduction: " << (CurSavingCost
 - BestCount) << "\n"; }; } } while (false)
  dbgs() << "Better position for saves found in func " << BF.getPrintName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { auto &InsnToBB = Info.getInsnToBBMap
(); dbgs() << "Better position for saves found in func "
 << BF.getPrintName() << " count << " <<
 BF.getKnownExecutionCount() << "\n"; dbgs() << "Reg: "
 << CSR << "; New BB: " << InsnToBB[BestPosSave
]->getName() << " Freq reduction: " << (CurSavingCost
 - BestCount) << "\n"; }; } } while (false)
         << " count << " << BF.getKnownExecutionCount() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { auto &InsnToBB = Info.getInsnToBBMap
(); dbgs() << "Better position for saves found in func "
 << BF.getPrintName() << " count << " <<
 BF.getKnownExecutionCount() << "\n"; dbgs() << "Reg: "
 << CSR << "; New BB: " << InsnToBB[BestPosSave
]->getName() << " Freq reduction: " << (CurSavingCost
 - BestCount) << "\n"; }; } } while (false)
  dbgs() << "Reg: " << CSR << "; New BB: " << InsnToBB[BestPosSave]->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { auto &InsnToBB = Info.getInsnToBBMap
(); dbgs() << "Better position for saves found in func "
 << BF.getPrintName() << " count << " <<
 BF.getKnownExecutionCount() << "\n"; dbgs() << "Reg: "
 << CSR << "; New BB: " << InsnToBB[BestPosSave
]->getName() << " Freq reduction: " << (CurSavingCost
 - BestCount) << "\n"; }; } } while (false)
         << " Freq reduction: " << (CurSavingCost - BestCount) << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { auto &InsnToBB = Info.getInsnToBBMap
(); dbgs() << "Better position for saves found in func "
 << BF.getPrintName() << " count << " <<
 BF.getKnownExecutionCount() << "\n"; dbgs() << "Reg: "
 << CSR << "; New BB: " << InsnToBB[BestPosSave
]->getName() << " Freq reduction: " << (CurSavingCost
 - BestCount) << "\n"; }; } } while (false)
})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { auto &InsnToBB = Info.getInsnToBBMap
(); dbgs() << "Better position for saves found in func "
 << BF.getPrintName() << " count << " <<
 BF.getKnownExecutionCount() << "\n"; dbgs() << "Reg: "
 << CSR << "; New BB: " << InsnToBB[BestPosSave
]->getName() << " Freq reduction: " << (CurSavingCost
 - BestCount) << "\n"; }; } } while (false);

TotalEstimatedWin = CurSavingCost - BestCount;
return true;
908}

910/// Auxiliar function used to create basic blocks for critical edges and update
911/// the dominance frontier with these new locations
912void ShrinkWrapping::splitFrontierCritEdges(
  BinaryFunction *Func, SmallVector<ProgramPoint, 4> &Frontier,
  const SmallVector<bool, 4> &IsCritEdge,
  const SmallVector<BinaryBasicBlock *, 4> &From,
  const SmallVector<SmallVector<BinaryBasicBlock *, 4>, 4> &To) {
LLVM_DEBUG(dbgs() << "splitFrontierCritEdges: Now handling func "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "splitFrontierCritEdges: Now handling func "
 << BF.getPrintName() << "\n"; } } while (false)
                  << BF.getPrintName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "splitFrontierCritEdges: Now handling func "
 << BF.getPrintName() << "\n"; } } while (false);
// For every FromBB, there might be one or more critical edges, with
// To[I] containing destination BBs. It's important to memorize
// the original size of the Frontier as we may append to it while splitting
// critical edges originating with blocks with multiple destinations.
for (size_t I = 0, IE = Frontier.size(); I < IE; ++I) {
  if (!IsCritEdge[I])
    continue;
  if (To[I].empty())
    continue;
  BinaryBasicBlock *FromBB = From[I];
  LLVM_DEBUG(dbgs() << " - Now handling FrontierBB " << FromBB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << " - Now handling FrontierBB "
 << FromBB->getName() << "\n"; } } while (false
)
                    << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << " - Now handling FrontierBB "
 << FromBB->getName() << "\n"; } } while (false
);
  // Split edge for every DestinationBBs
  for (size_t DI = 0, DIE = To[I].size(); DI < DIE; ++DI) {
    BinaryBasicBlock *DestinationBB = To[I][DI];
    LLVM_DEBUG(dbgs() << "   - Dest : " << DestinationBB->getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "   - Dest : " <<
 DestinationBB->getName() << "\n"; } } while (false);
    BinaryBasicBlock *NewBB = Func->splitEdge(FromBB, DestinationBB);
    // Insert dummy instruction so this BB is never empty (we need this for
    // PredictiveStackPointerTracking to work, since it annotates instructions
    // and not BBs).
    if (NewBB->empty()) {
      MCInst NewInst;
      BC.MIB->createNoop(NewInst);
      NewBB->addInstruction(std::move(NewInst));
      scheduleChange(&*NewBB->begin(), WorklistItem(WorklistItem::Erase, 0));
    }

    // Update frontier
    ProgramPoint NewFrontierPP = ProgramPoint::getLastPointAt(*NewBB);
    if (DI == 0) {
      // Update frontier inplace
      Frontier[I] = NewFrontierPP;
      LLVM_DEBUG(dbgs() << "   - Update frontier with " << NewBB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "   - Update frontier with "
 << NewBB->getName() << '\n'; } } while (false
)
                        << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "   - Update frontier with "
 << NewBB->getName() << '\n'; } } while (false
);
    } else {
      // Append new frontier to the end of the list
      Frontier.push_back(NewFrontierPP);
      LLVM_DEBUG(dbgs() << "   - Append frontier " << NewBB->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "   - Append frontier "
 << NewBB->getName() << '\n'; } } while (false
)
                        << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "   - Append frontier "
 << NewBB->getName() << '\n'; } } while (false
);
    }
  }
}
961}

963SmallVector<ProgramPoint, 4>
964ShrinkWrapping::doRestorePlacement(MCInst *BestPosSave, unsigned CSR,
                                 uint64_t TotalEstimatedWin) {
SmallVector<ProgramPoint, 4> Frontier;
SmallVector<bool, 4> IsCritEdge;
DominatorAnalysis<false> &DA = Info.getDominatorAnalysis();

SmallVector<BinaryBasicBlock *, 4> CritEdgesFrom;
SmallVector<SmallVector<BinaryBasicBlock *, 4>, 4> CritEdgesTo;
// In case of a critical edge, we need to create extra BBs to host restores
// into edges transitioning to the dominance frontier, otherwise we pull these
// restores to inside the dominated area.
Frontier = DA.getDominanceFrontierFor(*BestPosSave).takeVector();
LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Dumping dominance frontier for "
; BC.printInstruction(dbgs(), *BestPosSave); for (ProgramPoint
 &PP : Frontier) if (PP.isInst()) BC.printInstruction(dbgs
(), *PP.getInst()); else dbgs() << PP.getBB()->getName
() << "\n"; }; } } while (false)
  dbgs() << "Dumping dominance frontier for ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Dumping dominance frontier for "
; BC.printInstruction(dbgs(), *BestPosSave); for (ProgramPoint
 &PP : Frontier) if (PP.isInst()) BC.printInstruction(dbgs
(), *PP.getInst()); else dbgs() << PP.getBB()->getName
() << "\n"; }; } } while (false)
  BC.printInstruction(dbgs(), *BestPosSave);do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Dumping dominance frontier for "
; BC.printInstruction(dbgs(), *BestPosSave); for (ProgramPoint
 &PP : Frontier) if (PP.isInst()) BC.printInstruction(dbgs
(), *PP.getInst()); else dbgs() << PP.getBB()->getName
() << "\n"; }; } } while (false)
  for (ProgramPoint &PP : Frontier)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Dumping dominance frontier for "
; BC.printInstruction(dbgs(), *BestPosSave); for (ProgramPoint
 &PP : Frontier) if (PP.isInst()) BC.printInstruction(dbgs
(), *PP.getInst()); else dbgs() << PP.getBB()->getName
() << "\n"; }; } } while (false)
    if (PP.isInst())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Dumping dominance frontier for "
; BC.printInstruction(dbgs(), *BestPosSave); for (ProgramPoint
 &PP : Frontier) if (PP.isInst()) BC.printInstruction(dbgs
(), *PP.getInst()); else dbgs() << PP.getBB()->getName
() << "\n"; }; } } while (false)
      BC.printInstruction(dbgs(), *PP.getInst());do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Dumping dominance frontier for "
; BC.printInstruction(dbgs(), *BestPosSave); for (ProgramPoint
 &PP : Frontier) if (PP.isInst()) BC.printInstruction(dbgs
(), *PP.getInst()); else dbgs() << PP.getBB()->getName
() << "\n"; }; } } while (false)
    elsedo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Dumping dominance frontier for "
; BC.printInstruction(dbgs(), *BestPosSave); for (ProgramPoint
 &PP : Frontier) if (PP.isInst()) BC.printInstruction(dbgs
(), *PP.getInst()); else dbgs() << PP.getBB()->getName
() << "\n"; }; } } while (false)
      dbgs() << PP.getBB()->getName() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Dumping dominance frontier for "
; BC.printInstruction(dbgs(), *BestPosSave); for (ProgramPoint
 &PP : Frontier) if (PP.isInst()) BC.printInstruction(dbgs
(), *PP.getInst()); else dbgs() << PP.getBB()->getName
() << "\n"; }; } } while (false)
})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Dumping dominance frontier for "
; BC.printInstruction(dbgs(), *BestPosSave); for (ProgramPoint
 &PP : Frontier) if (PP.isInst()) BC.printInstruction(dbgs
(), *PP.getInst()); else dbgs() << PP.getBB()->getName
() << "\n"; }; } } while (false);
for (ProgramPoint &PP : Frontier) {
  bool HasCritEdges = false;
  if (PP.isInst() && BC.MIB->isTerminator(*PP.getInst()) &&
      doesInstUsesCSR(*PP.getInst(), CSR)) {
    Frontier.clear();
    return Frontier;
  }
  BinaryBasicBlock *FrontierBB = Info.getParentBB(PP);
  CritEdgesFrom.emplace_back(FrontierBB);
  CritEdgesTo.emplace_back(0);
  SmallVector<BinaryBasicBlock *, 4> &Dests = CritEdgesTo.back();
  // Check for invoke instructions at the dominance frontier, which indicates
  // the landing pad is not dominated.
  if (PP.isInst() && BC.MIB->isInvoke(*PP.getInst())) {
    Frontier.clear();
    return Frontier;
  }
  doForAllSuccs(*FrontierBB, [&](ProgramPoint P) {
    if (!DA.doesADominateB(*BestPosSave, P)) {
      Dests.emplace_back(Info.getParentBB(P));
      return;
    }
    HasCritEdges = true;
  });
  IsCritEdge.push_back(HasCritEdges);
}
// Restores cannot be placed in empty BBs because we have a dataflow
// analysis that depends on insertions happening before real instructions
// (PredictiveStackPointerTracking). Detect now for empty BBs and add a
// dummy nop that is scheduled to be removed later.
bool InvalidateRequired = false;
for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
  if (BB->size() != 0)
    continue;
  MCInst NewInst;
  BC.MIB->createNoop(NewInst);
  auto II = BB->addInstruction(std::move(NewInst));
  scheduleChange(&*II, WorklistItem(WorklistItem::Erase, 0));
  InvalidateRequired = true;
}
if (std::accumulate(IsCritEdge.begin(), IsCritEdge.end(), 0)) {
  LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Now detected critical edges in the following frontier:\n"
; for (ProgramPoint &PP : Frontier) { if (PP.isBB()) { dbgs
() << "  BB: " << PP.getBB()->getName() <<
 "\n"; } else { dbgs() << "  Inst: "; PP.getInst()->
dump(); } } }; } } while (false)
    dbgs() << "Now detected critical edges in the following frontier:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Now detected critical edges in the following frontier:\n"
; for (ProgramPoint &PP : Frontier) { if (PP.isBB()) { dbgs
() << "  BB: " << PP.getBB()->getName() <<
 "\n"; } else { dbgs() << "  Inst: "; PP.getInst()->
dump(); } } }; } } while (false)
    for (ProgramPoint &PP : Frontier) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Now detected critical edges in the following frontier:\n"
; for (ProgramPoint &PP : Frontier) { if (PP.isBB()) { dbgs
() << "  BB: " << PP.getBB()->getName() <<
 "\n"; } else { dbgs() << "  Inst: "; PP.getInst()->
dump(); } } }; } } while (false)
      if (PP.isBB()) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Now detected critical edges in the following frontier:\n"
; for (ProgramPoint &PP : Frontier) { if (PP.isBB()) { dbgs
() << "  BB: " << PP.getBB()->getName() <<
 "\n"; } else { dbgs() << "  Inst: "; PP.getInst()->
dump(); } } }; } } while (false)
        dbgs() << "  BB: " << PP.getBB()->getName() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Now detected critical edges in the following frontier:\n"
; for (ProgramPoint &PP : Frontier) { if (PP.isBB()) { dbgs
() << "  BB: " << PP.getBB()->getName() <<
 "\n"; } else { dbgs() << "  Inst: "; PP.getInst()->
dump(); } } }; } } while (false)
      } else {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Now detected critical edges in the following frontier:\n"
; for (ProgramPoint &PP : Frontier) { if (PP.isBB()) { dbgs
() << "  BB: " << PP.getBB()->getName() <<
 "\n"; } else { dbgs() << "  Inst: "; PP.getInst()->
dump(); } } }; } } while (false)
        dbgs() << "  Inst: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Now detected critical edges in the following frontier:\n"
; for (ProgramPoint &PP : Frontier) { if (PP.isBB()) { dbgs
() << "  BB: " << PP.getBB()->getName() <<
 "\n"; } else { dbgs() << "  Inst: "; PP.getInst()->
dump(); } } }; } } while (false)
        PP.getInst()->dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Now detected critical edges in the following frontier:\n"
; for (ProgramPoint &PP : Frontier) { if (PP.isBB()) { dbgs
() << "  BB: " << PP.getBB()->getName() <<
 "\n"; } else { dbgs() << "  Inst: "; PP.getInst()->
dump(); } } }; } } while (false)
      }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Now detected critical edges in the following frontier:\n"
; for (ProgramPoint &PP : Frontier) { if (PP.isBB()) { dbgs
() << "  BB: " << PP.getBB()->getName() <<
 "\n"; } else { dbgs() << "  Inst: "; PP.getInst()->
dump(); } } }; } } while (false)
    }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Now detected critical edges in the following frontier:\n"
; for (ProgramPoint &PP : Frontier) { if (PP.isBB()) { dbgs
() << "  BB: " << PP.getBB()->getName() <<
 "\n"; } else { dbgs() << "  Inst: "; PP.getInst()->
dump(); } } }; } } while (false)
  })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Now detected critical edges in the following frontier:\n"
; for (ProgramPoint &PP : Frontier) { if (PP.isBB()) { dbgs
() << "  BB: " << PP.getBB()->getName() <<
 "\n"; } else { dbgs() << "  Inst: "; PP.getInst()->
dump(); } } }; } } while (false);
  splitFrontierCritEdges(&BF, Frontier, IsCritEdge, CritEdgesFrom,
                         CritEdgesTo);
  InvalidateRequired = true;
}
if (InvalidateRequired) {
  // BitVectors that represent all insns of the function are invalid now
  // since we changed BBs/Insts. Re-run steps that depend on pointers being
  // valid
  Info.invalidateAll();
  classifyCSRUses();
}
return Frontier;
1049}

1051bool ShrinkWrapping::validatePushPopsMode(unsigned CSR, MCInst *BestPosSave,
                                        int64_t SaveOffset) {
if (FA.requiresAlignment(BF)) {
  LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Reg " << CSR <<
 " is not using push/pops due to function " "alignment requirements.\n"
; }; } } while (false)
    dbgs() << "Reg " << CSRdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Reg " << CSR <<
 " is not using push/pops due to function " "alignment requirements.\n"
; }; } } while (false)
           << " is not using push/pops due to function "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Reg " << CSR <<
 " is not using push/pops due to function " "alignment requirements.\n"
; }; } } while (false)
              "alignment requirements.\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Reg " << CSR <<
 " is not using push/pops due to function " "alignment requirements.\n"
; }; } } while (false)
  })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Reg " << CSR <<
 " is not using push/pops due to function " "alignment requirements.\n"
; }; } } while (false);
  return false;
}
if (FA.hasStackArithmetic(BF)) {
  LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Reg " << CSR <<
 " is not using push/pops due to function " "taking the address of a stack position.\n"
; }; } } while (false)
    dbgs() << "Reg " << CSRdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Reg " << CSR <<
 " is not using push/pops due to function " "taking the address of a stack position.\n"
; }; } } while (false)
           << " is not using push/pops due to function "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Reg " << CSR <<
 " is not using push/pops due to function " "taking the address of a stack position.\n"
; }; } } while (false)
              "taking the address of a stack position.\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Reg " << CSR <<
 " is not using push/pops due to function " "taking the address of a stack position.\n"
; }; } } while (false)
  })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Reg " << CSR <<
 " is not using push/pops due to function " "taking the address of a stack position.\n"
; }; } } while (false);
  return false;
}
for (MCInst *Save : CSA.getSavesByReg(CSR)) {
  if (!SLM.canCollapseRegion(Save)) {
    LLVM_DEBUG(dbgs() << "Reg " << CSR << " cannot collapse region.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "Reg " << CSR <<
 " cannot collapse region.\n"; } } while (false);
    return false;
  }
}
// Abort if one of the restores for this CSR is not a POP.
for (MCInst *Load : CSA.getRestoresByReg(CSR)) {
  if (!BC.MIB->isPop(*Load)) {
    LLVM_DEBUG(dbgs() << "Reg " << CSR << " has a mismatching restore.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "Reg " << CSR <<
 " has a mismatching restore.\n"; } } while (false);
    return false;
  }
}

StackPointerTracking &SPT = Info.getStackPointerTracking();
// Abort if we are inserting a push into an entry BB (offset -8) and this
// func sets up a frame pointer.
if (!SLM.canInsertRegion(BestPosSave) || SaveOffset == SPT.SUPERPOSITION ||
    SaveOffset == SPT.EMPTY || (SaveOffset == -8 && SPT.HasFramePointer)) {
  LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Reg " << CSR <<
 " cannot insert region or we are " "trying to insert a push into entry bb.\n"
; }; } } while (false)
    dbgs() << "Reg " << CSRdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Reg " << CSR <<
 " cannot insert region or we are " "trying to insert a push into entry bb.\n"
; }; } } while (false)
           << " cannot insert region or we are "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Reg " << CSR <<
 " cannot insert region or we are " "trying to insert a push into entry bb.\n"
; }; } } while (false)
              "trying to insert a push into entry bb.\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Reg " << CSR <<
 " cannot insert region or we are " "trying to insert a push into entry bb.\n"
; }; } } while (false)
  })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Reg " << CSR <<
 " cannot insert region or we are " "trying to insert a push into entry bb.\n"
; }; } } while (false);
  return false;
}
return true;
1096}

1098SmallVector<ProgramPoint, 4> ShrinkWrapping::fixPopsPlacements(
  const SmallVector<ProgramPoint, 4> &RestorePoints, int64_t SaveOffset,
  unsigned CSR) {
SmallVector<ProgramPoint, 4> FixedRestorePoints = RestorePoints;
// Moving pop locations to the correct sp offset
ReachingInsns<true> &RI = Info.getReachingInsnsBackwards();
StackPointerTracking &SPT = Info.getStackPointerTracking();
for (ProgramPoint &PP : FixedRestorePoints) {
  BinaryBasicBlock *BB = Info.getParentBB(PP);
  bool Found = false;
  if (SPT.getStateAt(ProgramPoint::getLastPointAt(*BB))->first ==
      SaveOffset) {
    BitVector BV = *RI.getStateAt(ProgramPoint::getLastPointAt(*BB));
    BV &= UsesByReg[CSR];
    if (!BV.any()) {
      Found = true;
      PP = BB;
      continue;
    }
  }
  for (MCInst &Inst : llvm::reverse(*BB)) {
    if (SPT.getStateBefore(Inst)->first == SaveOffset) {
      BitVector BV = *RI.getStateAt(Inst);
      BV &= UsesByReg[CSR];
      if (!BV.any()) {
        Found = true;
        PP = &Inst;
        break;
      }
    }
  }
  if (!Found) {
    LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Could not find restore insertion point for "
 << CSR << ", falling back to load/store mode\n";
 }; } } while (false)
      dbgs() << "Could not find restore insertion point for " << CSRdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Could not find restore insertion point for "
 << CSR << ", falling back to load/store mode\n";
 }; } } while (false)
             << ", falling back to load/store mode\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Could not find restore insertion point for "
 << CSR << ", falling back to load/store mode\n";
 }; } } while (false)
    })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Could not find restore insertion point for "
 << CSR << ", falling back to load/store mode\n";
 }; } } while (false);
    FixedRestorePoints.clear();
    return FixedRestorePoints;
  }
}
return FixedRestorePoints;
1139}

1141void ShrinkWrapping::scheduleOldSaveRestoresRemoval(unsigned CSR,
                                                  bool UsePushPops) {

for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
  std::vector<MCInst *> CFIs;
  for (MCInst &Inst : llvm::reverse(*BB)) {
    if (BC.MIB->isCFI(Inst)) {
      // Delete all offset CFIs related to this CSR
      if (SLM.getOffsetCFIReg(Inst) == CSR) {
        HasDeletedOffsetCFIs[CSR] = true;
        scheduleChange(&Inst, WorklistItem(WorklistItem::Erase, CSR));
        continue;
      }
      CFIs.push_back(&Inst);
      continue;
    }

    uint16_t SavedReg = CSA.getSavedReg(Inst);
    uint16_t RestoredReg = CSA.getRestoredReg(Inst);
    if (SavedReg != CSR && RestoredReg != CSR) {
      CFIs.clear();
      continue;
    }

    scheduleChange(&Inst, WorklistItem(UsePushPops
                                           ? WorklistItem::Erase
                                           : WorklistItem::ChangeToAdjustment,
                                       CSR));

    // Delete associated CFIs
    const bool RecordDeletedPushCFIs =
        SavedReg == CSR && DeletedPushCFIs[CSR].empty();
    const bool RecordDeletedPopCFIs =
        RestoredReg == CSR && DeletedPopCFIs[CSR].empty();
    for (MCInst *CFI : CFIs) {
      const MCCFIInstruction *MCCFI = BF.getCFIFor(*CFI);
      // Do not touch these...
      if (MCCFI->getOperation() == MCCFIInstruction::OpRestoreState ||
          MCCFI->getOperation() == MCCFIInstruction::OpRememberState)
        continue;
      scheduleChange(CFI, WorklistItem(WorklistItem::Erase, CSR));
      if (RecordDeletedPushCFIs) {
        // Do not record this to be replayed later because we are going to
        // rebuild it.
        if (MCCFI->getOperation() == MCCFIInstruction::OpDefCfaOffset)
          continue;
        DeletedPushCFIs[CSR].push_back(CFI->getOperand(0).getImm());
      }
      if (RecordDeletedPopCFIs) {
        if (MCCFI->getOperation() == MCCFIInstruction::OpDefCfaOffset)
          continue;
        DeletedPopCFIs[CSR].push_back(CFI->getOperand(0).getImm());
      }
    }
    CFIs.clear();
  }
}
1198}

1200bool ShrinkWrapping::doesInstUsesCSR(const MCInst &Inst, uint16_t CSR) {
if (BC.MIB->isCFI(Inst) || CSA.getSavedReg(Inst) == CSR ||
    CSA.getRestoredReg(Inst) == CSR)
  return false;
BitVector BV = BitVector(BC.MRI->getNumRegs(), false);
BC.MIB->getTouchedRegs(Inst, BV);
return BV[CSR];
1207}

1209void ShrinkWrapping::scheduleSaveRestoreInsertions(
  unsigned CSR, MCInst *BestPosSave,
  SmallVector<ProgramPoint, 4> &RestorePoints, bool UsePushPops) {
auto &InsnToBB = Info.getInsnToBBMap();
const FrameIndexEntry *FIESave = CSA.SaveFIEByReg[CSR];
const FrameIndexEntry *FIELoad = CSA.LoadFIEByReg[CSR];
assert(FIESave && FIELoad && "Invalid CSR")(static_cast <bool> (FIESave && FIELoad &&
 "Invalid CSR") ? void (0) : __assert_fail ("FIESave && FIELoad && \"Invalid CSR\""
, "bolt/lib/Passes/ShrinkWrapping.cpp", 1215, __extension__ __PRETTY_FUNCTION__
));

LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Scheduling save insertion at: "
; BestPosSave->dump(); }; } } while (false)
  dbgs() << "Scheduling save insertion at: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Scheduling save insertion at: "
; BestPosSave->dump(); }; } } while (false)
  BestPosSave->dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Scheduling save insertion at: "
; BestPosSave->dump(); }; } } while (false)
})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Scheduling save insertion at: "
; BestPosSave->dump(); }; } } while (false);

scheduleChange(BestPosSave,
               UsePushPops ? WorklistItem::InsertPushOrPop
                           : WorklistItem::InsertLoadOrStore,
               *FIESave, CSR);

for (ProgramPoint &PP : RestorePoints) {
  BinaryBasicBlock *FrontierBB = Info.getParentBB(PP);
  LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Scheduling restore insertion at: "
; if (PP.isInst()) PP.getInst()->dump(); else dbgs() <<
 PP.getBB()->getName() << "\n"; }; } } while (false)
    dbgs() << "Scheduling restore insertion at: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Scheduling restore insertion at: "
; if (PP.isInst()) PP.getInst()->dump(); else dbgs() <<
 PP.getBB()->getName() << "\n"; }; } } while (false)
    if (PP.isInst())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Scheduling restore insertion at: "
; if (PP.isInst()) PP.getInst()->dump(); else dbgs() <<
 PP.getBB()->getName() << "\n"; }; } } while (false)
      PP.getInst()->dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Scheduling restore insertion at: "
; if (PP.isInst()) PP.getInst()->dump(); else dbgs() <<
 PP.getBB()->getName() << "\n"; }; } } while (false)
    elsedo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Scheduling restore insertion at: "
; if (PP.isInst()) PP.getInst()->dump(); else dbgs() <<
 PP.getBB()->getName() << "\n"; }; } } while (false)
      dbgs() << PP.getBB()->getName() << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Scheduling restore insertion at: "
; if (PP.isInst()) PP.getInst()->dump(); else dbgs() <<
 PP.getBB()->getName() << "\n"; }; } } while (false)
  })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Scheduling restore insertion at: "
; if (PP.isInst()) PP.getInst()->dump(); else dbgs() <<
 PP.getBB()->getName() << "\n"; }; } } while (false);
  MCInst *Term =
      FrontierBB->getTerminatorBefore(PP.isInst() ? PP.getInst() : nullptr);
  if (Term)
    PP = Term;
  bool PrecededByPrefix = false;
  if (PP.isInst()) {
    auto Iter = FrontierBB->findInstruction(PP.getInst());
    if (Iter != FrontierBB->end() && Iter != FrontierBB->begin()) {
      --Iter;
      PrecededByPrefix = BC.MIB->isPrefix(*Iter);
    }
  }
  if (PP.isInst() &&
      (doesInstUsesCSR(*PP.getInst(), CSR) || PrecededByPrefix)) {
    assert(!InsnToBB[PP.getInst()]->hasTerminatorAfter(PP.getInst()) &&(static_cast <bool> (!InsnToBB[PP.getInst()]->hasTerminatorAfter
(PP.getInst()) && "cannot move to end of bb") ? void (
0) : __assert_fail ("!InsnToBB[PP.getInst()]->hasTerminatorAfter(PP.getInst()) && \"cannot move to end of bb\""
, "bolt/lib/Passes/ShrinkWrapping.cpp", 1251, __extension__ __PRETTY_FUNCTION__
))
           "cannot move to end of bb")(static_cast <bool> (!InsnToBB[PP.getInst()]->hasTerminatorAfter
(PP.getInst()) && "cannot move to end of bb") ? void (
0) : __assert_fail ("!InsnToBB[PP.getInst()]->hasTerminatorAfter(PP.getInst()) && \"cannot move to end of bb\""
, "bolt/lib/Passes/ShrinkWrapping.cpp", 1251, __extension__ __PRETTY_FUNCTION__
));
    scheduleChange(InsnToBB[PP.getInst()],
                   UsePushPops ? WorklistItem::InsertPushOrPop
                               : WorklistItem::InsertLoadOrStore,
                   *FIELoad, CSR);
    continue;
  }
  scheduleChange(PP,
                 UsePushPops ? WorklistItem::InsertPushOrPop
                             : WorklistItem::InsertLoadOrStore,
                 *FIELoad, CSR);
}
1263}

1265void ShrinkWrapping::moveSaveRestores() {
bool DisablePushPopMode = false;
bool UsedPushPopMode = false;
// Keeps info about successfully moved regs: reg index, save position and
// save size
std::vector<std::tuple<unsigned, MCInst *, size_t>> MovedRegs;
uint64_t TotalEstimatedWin = 0;

computeDomOrder();
for (unsigned I = 0, E = BC.MRI->getNumRegs(); I != E; ++I) {
  MCInst *BestPosSave = nullptr;
  uint64_t EstimatedWin = 0;
  SmallVector<ProgramPoint, 4> RestorePoints;
  while (RestorePoints.empty() &&
         isBestSavePosCold(I, BestPosSave, EstimatedWin)) {
    RestorePoints = doRestorePlacement(BestPosSave, I, EstimatedWin);
    if (RestorePoints.empty()) {
      LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Dropping opportunity because restore placement failed"
 " -- total est. freq reduc: " << EstimatedWin <<
 ". Will try " << (BestSaveCount[I].size() - 1) <<
 " more times.\n"; }; } } while (false)
        dbgs() << "Dropping opportunity because restore placement failed"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Dropping opportunity because restore placement failed"
 " -- total est. freq reduc: " << EstimatedWin <<
 ". Will try " << (BestSaveCount[I].size() - 1) <<
 " more times.\n"; }; } } while (false)
                  " -- total est. freq reduc: "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Dropping opportunity because restore placement failed"
 " -- total est. freq reduc: " << EstimatedWin <<
 ". Will try " << (BestSaveCount[I].size() - 1) <<
 " more times.\n"; }; } } while (false)
               << EstimatedWin << ". Will try "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Dropping opportunity because restore placement failed"
 " -- total est. freq reduc: " << EstimatedWin <<
 ". Will try " << (BestSaveCount[I].size() - 1) <<
 " more times.\n"; }; } } while (false)
               << (BestSaveCount[I].size() - 1) << " more times.\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Dropping opportunity because restore placement failed"
 " -- total est. freq reduc: " << EstimatedWin <<
 ". Will try " << (BestSaveCount[I].size() - 1) <<
 " more times.\n"; }; } } while (false)
      })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Dropping opportunity because restore placement failed"
 " -- total est. freq reduc: " << EstimatedWin <<
 ". Will try " << (BestSaveCount[I].size() - 1) <<
 " more times.\n"; }; } } while (false);
      BestSaveCount[I].pop_back();
      BestSavePos[I].pop_back();
      computeDomOrder();
    }
  }
  if (RestorePoints.empty()) {
    SpillsFailedDynamicCount += EstimatedWin;
    continue;
  }

  const FrameIndexEntry *FIESave = CSA.SaveFIEByReg[I];
  const FrameIndexEntry *FIELoad = CSA.LoadFIEByReg[I];
  (void)FIELoad;
  assert(FIESave && FIELoad)(static_cast <bool> (FIESave && FIELoad) ? void
 (0) : __assert_fail ("FIESave && FIELoad", "bolt/lib/Passes/ShrinkWrapping.cpp"
, 1301, __extension__ __PRETTY_FUNCTION__));
  StackPointerTracking &SPT = Info.getStackPointerTracking();
  const std::pair<int, int> SPFP = *SPT.getStateBefore(*BestPosSave);
  int SaveOffset = SPFP.first;
  uint8_t SaveSize = FIESave->Size;

  // If we don't know stack state at this point, bail
  if ((SPFP.first == SPT.SUPERPOSITION || SPFP.first == SPT.EMPTY) &&
      (SPFP.second == SPT.SUPERPOSITION || SPFP.second == SPT.EMPTY)) {
    SpillsFailedDynamicCount += EstimatedWin;
    continue;
  }

  // Operation mode: if true, will insert push/pops instead of loads/restores
  bool UsePushPops = validatePushPopsMode(I, BestPosSave, SaveOffset);

  if (UsePushPops) {
    SmallVector<ProgramPoint, 4> FixedRestorePoints =
        fixPopsPlacements(RestorePoints, SaveOffset, I);
    if (FixedRestorePoints.empty())
      UsePushPops = false;
    else
      RestorePoints = FixedRestorePoints;
  }

  // Disable push-pop mode for all CSRs in this function
  if (!UsePushPops)
    DisablePushPopMode = true;
  else
    UsedPushPopMode = true;

  scheduleOldSaveRestoresRemoval(I, UsePushPops);
  scheduleSaveRestoreInsertions(I, BestPosSave, RestorePoints, UsePushPops);
  MovedRegs.emplace_back(std::make_tuple(I, BestPosSave, SaveSize));
  TotalEstimatedWin += EstimatedWin;
}

// Revert push-pop mode if it failed for a single CSR
if (DisablePushPopMode && UsedPushPopMode) {
  UsedPushPopMode = false;
  for (BinaryBasicBlock &BB : BF) {
    auto WRI = Todo.find(&BB);
    if (WRI != Todo.end()) {
      std::vector<WorklistItem> &TodoList = WRI->second;
      for (WorklistItem &Item : TodoList)
        if (Item.Action == WorklistItem::InsertPushOrPop)
          Item.Action = WorklistItem::InsertLoadOrStore;
    }
    for (MCInst &Inst : llvm::reverse(BB)) {
      auto TodoList = BC.MIB->tryGetAnnotationAs<std::vector<WorklistItem>>(
          Inst, getAnnotationIndex());
      if (!TodoList)
        continue;
      bool isCFI = BC.MIB->isCFI(Inst);
      for (WorklistItem &Item : *TodoList) {
        if (Item.Action == WorklistItem::InsertPushOrPop)
          Item.Action = WorklistItem::InsertLoadOrStore;
        if (!isCFI && Item.Action == WorklistItem::Erase)
          Item.Action = WorklistItem::ChangeToAdjustment;
      }
    }
  }
}
SpillsMovedDynamicCount += TotalEstimatedWin;

// Update statistics
if (!UsedPushPopMode) {
  SpillsMovedRegularMode += MovedRegs.size();
  return;
}

// Schedule modifications to stack-accessing instructions via
// StackLayoutModifier.
SpillsMovedPushPopMode += MovedRegs.size();
for (std::tuple<unsigned, MCInst *, size_t> &I : MovedRegs) {
  unsigned RegNdx;
  MCInst *SavePos;
  size_t SaveSize;
  std::tie(RegNdx, SavePos, SaveSize) = I;
  for (MCInst *Save : CSA.getSavesByReg(RegNdx))
    SLM.collapseRegion(Save);
  SLM.insertRegion(SavePos, SaveSize);
}
1384}

1386namespace {
1387/// Helper function to identify whether two basic blocks created by splitting
1388/// a critical edge have the same contents.
1389bool isIdenticalSplitEdgeBB(const BinaryContext &BC, const BinaryBasicBlock &A,
                          const BinaryBasicBlock &B) {
if (A.succ_size() != B.succ_size())
  return false;
if (A.succ_size() != 1)
  return false;

if (*A.succ_begin() != *B.succ_begin())
  return false;

if (A.size() != B.size())
  return false;

// Compare instructions
auto I = A.begin(), E = A.end();
auto OtherI = B.begin(), OtherE = B.end();
while (I != E && OtherI != OtherE) {
  if (I->getOpcode() != OtherI->getOpcode())
    return false;
  if (!BC.MIB->equals(*I, *OtherI, [](const MCSymbol *A, const MCSymbol *B) {
        return true;
      }))
    return false;
  ++I;
  ++OtherI;
}
return true;
1416}
1417} // namespace

1419bool ShrinkWrapping::foldIdenticalSplitEdges() {
bool Changed = false;
for (auto Iter = BF.begin(); Iter != BF.end(); ++Iter) {
  BinaryBasicBlock &BB = *Iter;
  if (!BB.getName().startswith(".LSplitEdge"))
    continue;
  for (BinaryBasicBlock &RBB : llvm::reverse(BF)) {
    if (&RBB == &BB)
      break;
    if (!RBB.getName().startswith(".LSplitEdge") || !RBB.isValid() ||
        !isIdenticalSplitEdgeBB(BC, *Iter, RBB))
      continue;
    assert(RBB.pred_size() == 1 && "Invalid split edge BB")(static_cast <bool> (RBB.pred_size() == 1 && "Invalid split edge BB"
) ? void (0) : __assert_fail ("RBB.pred_size() == 1 && \"Invalid split edge BB\""
, "bolt/lib/Passes/ShrinkWrapping.cpp", 1431, __extension__ __PRETTY_FUNCTION__
));
    BinaryBasicBlock *Pred = *RBB.pred_begin();
    uint64_t OrigCount = Pred->branch_info_begin()->Count;
    uint64_t OrigMispreds = Pred->branch_info_begin()->MispredictedCount;
    BF.replaceJumpTableEntryIn(Pred, &RBB, &BB);
    Pred->replaceSuccessor(&RBB, &BB, OrigCount, OrigMispreds);
    Changed = true;
    // Remove the block from CFG
    RBB.markValid(false);
  }
}

return Changed;
1444}

1446namespace {

1448// A special StackPointerTracking that compensates for our future plans
1449// in removing/adding insn.
1450class PredictiveStackPointerTracking
  : public StackPointerTrackingBase<PredictiveStackPointerTracking> {
friend class DataflowAnalysis<PredictiveStackPointerTracking,
                              std::pair<int, int>>;
decltype(ShrinkWrapping::Todo) &TodoMap;
DataflowInfoManager &Info;

std::optional<unsigned> AnnotationIndex;

1459protected:
void compNextAux(const MCInst &Point,
                 const std::vector<ShrinkWrapping::WorklistItem> &TodoItems,
                 std::pair<int, int> &Res) {
  for (const ShrinkWrapping::WorklistItem &Item : TodoItems) {
    if (Item.Action == ShrinkWrapping::WorklistItem::Erase &&
        BC.MIB->isPush(Point)) {
      Res.first += BC.MIB->getPushSize(Point);
      continue;
    }
    if (Item.Action == ShrinkWrapping::WorklistItem::Erase &&
        BC.MIB->isPop(Point)) {
      Res.first -= BC.MIB->getPopSize(Point);
      continue;
    }
    if (Item.Action == ShrinkWrapping::WorklistItem::InsertPushOrPop &&
        Item.FIEToInsert.IsStore) {
      Res.first -= Item.FIEToInsert.Size;
      continue;
    }
    if (Item.Action == ShrinkWrapping::WorklistItem::InsertPushOrPop &&
        Item.FIEToInsert.IsLoad) {
      Res.first += Item.FIEToInsert.Size;
      continue;
    }
  }
}

std::pair<int, int> computeNext(const MCInst &Point,
                                const std::pair<int, int> &Cur) {
  std::pair<int, int> Res =
      StackPointerTrackingBase<PredictiveStackPointerTracking>::computeNext(
          Point, Cur);
  if (Res.first == StackPointerTracking::SUPERPOSITION ||
      Res.first == StackPointerTracking::EMPTY)
    return Res;
  auto TodoItems =
      BC.MIB->tryGetAnnotationAs<std::vector<ShrinkWrapping::WorklistItem>>(
          Point, ShrinkWrapping::getAnnotationName());
  if (TodoItems)
    compNextAux(Point, *TodoItems, Res);
  auto &InsnToBBMap = Info.getInsnToBBMap();
  if (&*InsnToBBMap[&Point]->rbegin() != &Point)
    return Res;
  auto WRI = TodoMap.find(InsnToBBMap[&Point]);
  if (WRI == TodoMap.end())
    return Res;
  compNextAux(Point, WRI->second, Res);
  return Res;
}

StringRef getAnnotationName() const {
  return StringRef("PredictiveStackPointerTracking");
}

1514public:
PredictiveStackPointerTracking(BinaryFunction &BF,
                               decltype(ShrinkWrapping::Todo) &TodoMap,
                               DataflowInfoManager &Info,
                               MCPlusBuilder::AllocatorIdTy AllocatorId = 0)
    : StackPointerTrackingBase<PredictiveStackPointerTracking>(BF,
                                                               AllocatorId),
      TodoMap(TodoMap), Info(Info) {}

void run() {
  StackPointerTrackingBase<PredictiveStackPointerTracking>::run();
}
1526};

1528} // end anonymous namespace

1530void ShrinkWrapping::insertUpdatedCFI(unsigned CSR, int SPValPush,
                                    int SPValPop) {
MCInst *SavePoint = nullptr;
for (BinaryBasicBlock &BB : BF) {
  for (MCInst &Inst : llvm::reverse(BB)) {
    int32_t SrcImm = 0;
    MCPhysReg Reg = 0;
    MCPhysReg StackPtrReg = 0;
    int64_t StackOffset = 0;
    bool IsIndexed = false;
    bool IsLoad = false;
    bool IsStore = false;
    bool IsSimple = false;
    bool IsStoreFromReg = false;
    uint8_t Size = 0;
    if (!BC.MIB->isStackAccess(Inst, IsLoad, IsStore, IsStoreFromReg, Reg,
                               SrcImm, StackPtrReg, StackOffset, Size,
                               IsSimple, IsIndexed))
      continue;
    if (Reg != CSR || !IsStore || !IsSimple)
      continue;
    SavePoint = &Inst;
    break;
  }
  if (SavePoint)
    break;
}
assert(SavePoint)(static_cast <bool> (SavePoint) ? void (0) : __assert_fail
 ("SavePoint", "bolt/lib/Passes/ShrinkWrapping.cpp", 1557, __extension__
 __PRETTY_FUNCTION__));
LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Now using as save point for reg "
 << CSR << " :"; SavePoint->dump(); }; } } while
 (false)
  dbgs() << "Now using as save point for reg " << CSR << " :";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Now using as save point for reg "
 << CSR << " :"; SavePoint->dump(); }; } } while
 (false)
  SavePoint->dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Now using as save point for reg "
 << CSR << " :"; SavePoint->dump(); }; } } while
 (false)
})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Now using as save point for reg "
 << CSR << " :"; SavePoint->dump(); }; } } while
 (false);
bool PrevAffectedZone = false;
BinaryBasicBlock *PrevBB = nullptr;
DominatorAnalysis<false> &DA = Info.getDominatorAnalysis();
for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
  if (BB->size() == 0)
    continue;
  const bool InAffectedZoneAtEnd = DA.count(*BB->rbegin(), *SavePoint);
  const bool InAffectedZoneAtBegin =
      (*DA.getStateBefore(*BB->begin()))[DA.ExprToIdx[SavePoint]];
  bool InAffectedZone = InAffectedZoneAtBegin;
  for (auto InstIter = BB->begin(); InstIter != BB->end(); ++InstIter) {
    const bool CurZone = DA.count(*InstIter, *SavePoint);
    if (InAffectedZone != CurZone) {
      auto InsertionIter = InstIter;
      ++InsertionIter;
      InAffectedZone = CurZone;
      if (InAffectedZone)
        InstIter = insertCFIsForPushOrPop(*BB, InsertionIter, CSR, true, 0,
                                          SPValPop);
      else
        InstIter = insertCFIsForPushOrPop(*BB, InsertionIter, CSR, false, 0,
                                          SPValPush);
      --InstIter;
    }
  }
  // Are we at the first basic block or hot-cold split point?
  if (!PrevBB || (BF.isSplit() && BB->isCold() != PrevBB->isCold())) {
    if (InAffectedZoneAtBegin)
      insertCFIsForPushOrPop(*BB, BB->begin(), CSR, true, 0, SPValPush);
  } else if (InAffectedZoneAtBegin != PrevAffectedZone) {
    if (InAffectedZoneAtBegin)
      insertCFIsForPushOrPop(*PrevBB, PrevBB->end(), CSR, true, 0, SPValPush);
    else
      insertCFIsForPushOrPop(*PrevBB, PrevBB->end(), CSR, false, 0, SPValPop);
  }
  PrevAffectedZone = InAffectedZoneAtEnd;
  PrevBB = BB;
}
1600}

1602void ShrinkWrapping::rebuildCFIForSP() {
for (BinaryBasicBlock &BB : BF) {
  for (MCInst &Inst : BB) {
    if (!BC.MIB->isCFI(Inst))
      continue;
    const MCCFIInstruction *CFI = BF.getCFIFor(Inst);
    if (CFI->getOperation() == MCCFIInstruction::OpDefCfaOffset)
      BC.MIB->addAnnotation(Inst, "DeleteMe", 0U, AllocatorId);
  }
}

int PrevSPVal = -8;
BinaryBasicBlock *PrevBB = nullptr;
4
←
'PrevBB' initialized to a null pointer value→
StackPointerTracking &SPT = Info.getStackPointerTracking();
for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
5
←
Assuming '__begin2' is not equal to '__end2'→
  if (BB->size() == 0)
6
←
Assuming the condition is false→
7
←
Taking false branch→
    continue;
  const int SPValAtEnd = SPT.getStateAt(*BB->rbegin())->first;
  const int SPValAtBegin = SPT.getStateBefore(*BB->begin())->first;
  int SPVal = SPValAtBegin;
  for (auto Iter = BB->begin(); Iter != BB->end(); ++Iter) {
    const int CurVal = SPT.getStateAt(*Iter)->first;
    if (SPVal != CurVal) {
      auto InsertionIter = Iter;
      ++InsertionIter;
      Iter = BF.addCFIInstruction(
          BB, InsertionIter,
          MCCFIInstruction::cfiDefCfaOffset(nullptr, -CurVal));
      SPVal = CurVal;
    }
  }
  if (BF.isSplit() && PrevBB && BB->isCold() != PrevBB->isCold())
8
←
Assuming the condition is false→
    BF.addCFIInstruction(
        BB, BB->begin(),
        MCCFIInstruction::cfiDefCfaOffset(nullptr, -SPValAtBegin));
  else if (SPValAtBegin != PrevSPVal)
9
←
Assuming 'SPValAtBegin' is not equal to 'PrevSPVal'→
10
←
Taking true branch→
    BF.addCFIInstruction(
        PrevBB, PrevBB->end(),
11
←
Called C++ object pointer is null
        MCCFIInstruction::cfiDefCfaOffset(nullptr, -SPValAtBegin));
  PrevSPVal = SPValAtEnd;
  PrevBB = BB;
}

for (BinaryBasicBlock &BB : BF)
  for (auto I = BB.begin(); I != BB.end();)
    if (BC.MIB->hasAnnotation(*I, "DeleteMe"))
      I = BB.eraseInstruction(I);
    else
      ++I;
1651}

1653MCInst ShrinkWrapping::createStackAccess(int SPVal, int FPVal,
                                       const FrameIndexEntry &FIE,
                                       bool CreatePushOrPop) {
MCInst NewInst;
if (SPVal != StackPointerTracking::SUPERPOSITION &&
    SPVal != StackPointerTracking::EMPTY) {
  if (FIE.IsLoad) {
    if (!BC.MIB->createRestoreFromStack(NewInst, BC.MIB->getStackPointer(),
                                        FIE.StackOffset - SPVal, FIE.RegOrImm,
                                        FIE.Size)) {
      errs() << "createRestoreFromStack: not supported on this platform\n";
      abort();
    }
  } else {
    if (!BC.MIB->createSaveToStack(NewInst, BC.MIB->getStackPointer(),
                                   FIE.StackOffset - SPVal, FIE.RegOrImm,
                                   FIE.Size)) {
      errs() << "createSaveToStack: not supported on this platform\n";
      abort();
    }
  }
  if (CreatePushOrPop)
    BC.MIB->changeToPushOrPop(NewInst);
  return NewInst;
}
assert(FPVal != StackPointerTracking::SUPERPOSITION &&(static_cast <bool> (FPVal != StackPointerTracking::SUPERPOSITION
 && FPVal != StackPointerTracking::EMPTY) ? void (0) :
 __assert_fail ("FPVal != StackPointerTracking::SUPERPOSITION && FPVal != StackPointerTracking::EMPTY"
, "bolt/lib/Passes/ShrinkWrapping.cpp", 1679, __extension__ __PRETTY_FUNCTION__
))
       FPVal != StackPointerTracking::EMPTY)(static_cast <bool> (FPVal != StackPointerTracking::SUPERPOSITION
 && FPVal != StackPointerTracking::EMPTY) ? void (0) :
 __assert_fail ("FPVal != StackPointerTracking::SUPERPOSITION && FPVal != StackPointerTracking::EMPTY"
, "bolt/lib/Passes/ShrinkWrapping.cpp", 1679, __extension__ __PRETTY_FUNCTION__
));

if (FIE.IsLoad) {
  if (!BC.MIB->createRestoreFromStack(NewInst, BC.MIB->getFramePointer(),
                                      FIE.StackOffset - FPVal, FIE.RegOrImm,
                                      FIE.Size)) {
    errs() << "createRestoreFromStack: not supported on this platform\n";
    abort();
  }
} else {
  if (!BC.MIB->createSaveToStack(NewInst, BC.MIB->getFramePointer(),
                                 FIE.StackOffset - FPVal, FIE.RegOrImm,
                                 FIE.Size)) {
    errs() << "createSaveToStack: not supported on this platform\n";
    abort();
  }
}
return NewInst;
1697}

1699void ShrinkWrapping::updateCFIInstOffset(MCInst &Inst, int64_t NewOffset) {
const MCCFIInstruction *CFI = BF.getCFIFor(Inst);
if (UpdatedCFIs.count(CFI))
  return;

switch (CFI->getOperation()) {
case MCCFIInstruction::OpDefCfa:
case MCCFIInstruction::OpDefCfaRegister:
case MCCFIInstruction::OpDefCfaOffset:
  CFI = BF.mutateCFIOffsetFor(Inst, -NewOffset);
  break;
case MCCFIInstruction::OpOffset:
default:
  break;
}

UpdatedCFIs.insert(CFI);
1716}

1718BBIterTy ShrinkWrapping::insertCFIsForPushOrPop(BinaryBasicBlock &BB,
                                              BBIterTy Pos, unsigned Reg,
                                              bool isPush, int Sz,
                                              int64_t NewOffset) {
if (isPush) {
  for (uint32_t Idx : DeletedPushCFIs[Reg]) {
    Pos = BF.addCFIPseudo(&BB, Pos, Idx);
    updateCFIInstOffset(*Pos++, NewOffset);
  }
  if (HasDeletedOffsetCFIs[Reg]) {
    Pos = BF.addCFIInstruction(
        &BB, Pos,
        MCCFIInstruction::createOffset(
            nullptr, BC.MRI->getDwarfRegNum(Reg, false), NewOffset));
    ++Pos;
  }
} else {
  for (uint32_t Idx : DeletedPopCFIs[Reg]) {
    Pos = BF.addCFIPseudo(&BB, Pos, Idx);
    updateCFIInstOffset(*Pos++, NewOffset);
  }
  if (HasDeletedOffsetCFIs[Reg]) {
    Pos = BF.addCFIInstruction(
        &BB, Pos,
        MCCFIInstruction::createSameValue(
            nullptr, BC.MRI->getDwarfRegNum(Reg, false)));
    ++Pos;
  }
}
return Pos;
1748}

1750BBIterTy ShrinkWrapping::processInsertion(BBIterTy InsertionPoint,
                                        BinaryBasicBlock *CurBB,
                                        const WorklistItem &Item,
                                        int64_t SPVal, int64_t FPVal) {
// Trigger CFI reconstruction for this CSR if necessary - writing to
// PushOffsetByReg/PopOffsetByReg *will* trigger CFI update
if ((Item.FIEToInsert.IsStore &&
     !DeletedPushCFIs[Item.AffectedReg].empty()) ||
    (Item.FIEToInsert.IsLoad && !DeletedPopCFIs[Item.AffectedReg].empty()) ||
    HasDeletedOffsetCFIs[Item.AffectedReg]) {
  if (Item.Action == WorklistItem::InsertPushOrPop) {
    if (Item.FIEToInsert.IsStore)
      PushOffsetByReg[Item.AffectedReg] = SPVal - Item.FIEToInsert.Size;
    else
      PopOffsetByReg[Item.AffectedReg] = SPVal;
  } else {
    if (Item.FIEToInsert.IsStore)
      PushOffsetByReg[Item.AffectedReg] = Item.FIEToInsert.StackOffset;
    else
      PopOffsetByReg[Item.AffectedReg] = Item.FIEToInsert.StackOffset;
  }
}

LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Creating stack access with SPVal = "
 << SPVal << "; stack offset = " << Item.FIEToInsert
.StackOffset << " Is push = " << (Item.Action == WorklistItem
::InsertPushOrPop) << "\n"; }; } } while (false)
  dbgs() << "Creating stack access with SPVal = " << SPValdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Creating stack access with SPVal = "
 << SPVal << "; stack offset = " << Item.FIEToInsert
.StackOffset << " Is push = " << (Item.Action == WorklistItem
::InsertPushOrPop) << "\n"; }; } } while (false)
         << "; stack offset = " << Item.FIEToInsert.StackOffsetdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Creating stack access with SPVal = "
 << SPVal << "; stack offset = " << Item.FIEToInsert
.StackOffset << " Is push = " << (Item.Action == WorklistItem
::InsertPushOrPop) << "\n"; }; } } while (false)
         << " Is push = " << (Item.Action == WorklistItem::InsertPushOrPop)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Creating stack access with SPVal = "
 << SPVal << "; stack offset = " << Item.FIEToInsert
.StackOffset << " Is push = " << (Item.Action == WorklistItem
::InsertPushOrPop) << "\n"; }; } } while (false)
         << "\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Creating stack access with SPVal = "
 << SPVal << "; stack offset = " << Item.FIEToInsert
.StackOffset << " Is push = " << (Item.Action == WorklistItem
::InsertPushOrPop) << "\n"; }; } } while (false)
})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Creating stack access with SPVal = "
 << SPVal << "; stack offset = " << Item.FIEToInsert
.StackOffset << " Is push = " << (Item.Action == WorklistItem
::InsertPushOrPop) << "\n"; }; } } while (false);
MCInst NewInst =
    createStackAccess(SPVal, FPVal, Item.FIEToInsert,
                      Item.Action == WorklistItem::InsertPushOrPop);
if (InsertionPoint != CurBB->end()) {
  LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Adding before Inst: "
; InsertionPoint->dump(); dbgs() << "the following inst: "
; NewInst.dump(); }; } } while (false)
    dbgs() << "Adding before Inst: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Adding before Inst: "
; InsertionPoint->dump(); dbgs() << "the following inst: "
; NewInst.dump(); }; } } while (false)
    InsertionPoint->dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Adding before Inst: "
; InsertionPoint->dump(); dbgs() << "the following inst: "
; NewInst.dump(); }; } } while (false)
    dbgs() << "the following inst: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Adding before Inst: "
; InsertionPoint->dump(); dbgs() << "the following inst: "
; NewInst.dump(); }; } } while (false)
    NewInst.dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Adding before Inst: "
; InsertionPoint->dump(); dbgs() << "the following inst: "
; NewInst.dump(); }; } } while (false)
  })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Adding before Inst: "
; InsertionPoint->dump(); dbgs() << "the following inst: "
; NewInst.dump(); }; } } while (false);
  BBIterTy Iter =
      CurBB->insertInstruction(InsertionPoint, std::move(NewInst));
  return ++Iter;
}
CurBB->addInstruction(std::move(NewInst));
LLVM_DEBUG(dbgs() << "Adding to BB!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "Adding to BB!\n"; } } while
 (false);
return CurBB->end();
1796}

1798BBIterTy ShrinkWrapping::processInsertionsList(
  BBIterTy InsertionPoint, BinaryBasicBlock *CurBB,
  std::vector<WorklistItem> &TodoList, int64_t SPVal, int64_t FPVal) {
bool HasInsertions = llvm::any_of(TodoList, [&](WorklistItem &Item) {
  return Item.Action == WorklistItem::InsertLoadOrStore ||
         Item.Action == WorklistItem::InsertPushOrPop;
});

if (!HasInsertions)
  return InsertionPoint;

assert(((SPVal != StackPointerTracking::SUPERPOSITION &&(static_cast <bool> (((SPVal != StackPointerTracking::SUPERPOSITION
 && SPVal != StackPointerTracking::EMPTY) || (FPVal !=
 StackPointerTracking::SUPERPOSITION && FPVal != StackPointerTracking
::EMPTY)) && "Cannot insert if we have no idea of the stack state here"
) ? void (0) : __assert_fail ("((SPVal != StackPointerTracking::SUPERPOSITION && SPVal != StackPointerTracking::EMPTY) || (FPVal != StackPointerTracking::SUPERPOSITION && FPVal != StackPointerTracking::EMPTY)) && \"Cannot insert if we have no idea of the stack state here\""
, "bolt/lib/Passes/ShrinkWrapping.cpp", 1813, __extension__ __PRETTY_FUNCTION__
))
         SPVal != StackPointerTracking::EMPTY) ||(static_cast <bool> (((SPVal != StackPointerTracking::SUPERPOSITION
 && SPVal != StackPointerTracking::EMPTY) || (FPVal !=
 StackPointerTracking::SUPERPOSITION && FPVal != StackPointerTracking
::EMPTY)) && "Cannot insert if we have no idea of the stack state here"
) ? void (0) : __assert_fail ("((SPVal != StackPointerTracking::SUPERPOSITION && SPVal != StackPointerTracking::EMPTY) || (FPVal != StackPointerTracking::SUPERPOSITION && FPVal != StackPointerTracking::EMPTY)) && \"Cannot insert if we have no idea of the stack state here\""
, "bolt/lib/Passes/ShrinkWrapping.cpp", 1813, __extension__ __PRETTY_FUNCTION__
))
        (FPVal != StackPointerTracking::SUPERPOSITION &&(static_cast <bool> (((SPVal != StackPointerTracking::SUPERPOSITION
 && SPVal != StackPointerTracking::EMPTY) || (FPVal !=
 StackPointerTracking::SUPERPOSITION && FPVal != StackPointerTracking
::EMPTY)) && "Cannot insert if we have no idea of the stack state here"
) ? void (0) : __assert_fail ("((SPVal != StackPointerTracking::SUPERPOSITION && SPVal != StackPointerTracking::EMPTY) || (FPVal != StackPointerTracking::SUPERPOSITION && FPVal != StackPointerTracking::EMPTY)) && \"Cannot insert if we have no idea of the stack state here\""
, "bolt/lib/Passes/ShrinkWrapping.cpp", 1813, __extension__ __PRETTY_FUNCTION__
))
         FPVal != StackPointerTracking::EMPTY)) &&(static_cast <bool> (((SPVal != StackPointerTracking::SUPERPOSITION
 && SPVal != StackPointerTracking::EMPTY) || (FPVal !=
 StackPointerTracking::SUPERPOSITION && FPVal != StackPointerTracking
::EMPTY)) && "Cannot insert if we have no idea of the stack state here"
) ? void (0) : __assert_fail ("((SPVal != StackPointerTracking::SUPERPOSITION && SPVal != StackPointerTracking::EMPTY) || (FPVal != StackPointerTracking::SUPERPOSITION && FPVal != StackPointerTracking::EMPTY)) && \"Cannot insert if we have no idea of the stack state here\""
, "bolt/lib/Passes/ShrinkWrapping.cpp", 1813, __extension__ __PRETTY_FUNCTION__
))
       "Cannot insert if we have no idea of the stack state here")(static_cast <bool> (((SPVal != StackPointerTracking::SUPERPOSITION
 && SPVal != StackPointerTracking::EMPTY) || (FPVal !=
 StackPointerTracking::SUPERPOSITION && FPVal != StackPointerTracking
::EMPTY)) && "Cannot insert if we have no idea of the stack state here"
) ? void (0) : __assert_fail ("((SPVal != StackPointerTracking::SUPERPOSITION && SPVal != StackPointerTracking::EMPTY) || (FPVal != StackPointerTracking::SUPERPOSITION && FPVal != StackPointerTracking::EMPTY)) && \"Cannot insert if we have no idea of the stack state here\""
, "bolt/lib/Passes/ShrinkWrapping.cpp", 1813, __extension__ __PRETTY_FUNCTION__
));

// Revert the effect of PSPT for this location, we want SP Value before
// insertions
if (InsertionPoint == CurBB->end()) {
  for (WorklistItem &Item : TodoList) {
    if (Item.Action != WorklistItem::InsertPushOrPop)
      continue;
    if (Item.FIEToInsert.IsStore)
      SPVal += Item.FIEToInsert.Size;
    if (Item.FIEToInsert.IsLoad)
      SPVal -= Item.FIEToInsert.Size;
  }
}

// Reorder POPs to obey the correct dominance relation between them
llvm::stable_sort(TodoList, [&](const WorklistItem &A,
                                const WorklistItem &B) {
  if ((A.Action != WorklistItem::InsertPushOrPop || !A.FIEToInsert.IsLoad) &&
      (B.Action != WorklistItem::InsertPushOrPop || !B.FIEToInsert.IsLoad))
    return false;
  if ((A.Action != WorklistItem::InsertPushOrPop || !A.FIEToInsert.IsLoad))
    return true;
  if ((B.Action != WorklistItem::InsertPushOrPop || !B.FIEToInsert.IsLoad))
    return false;
  return DomOrder[B.AffectedReg] < DomOrder[A.AffectedReg];
});

// Process insertions
for (WorklistItem &Item : TodoList) {
  if (Item.Action == WorklistItem::Erase ||
      Item.Action == WorklistItem::ChangeToAdjustment)
    continue;

  InsertionPoint =
      processInsertion(InsertionPoint, CurBB, Item, SPVal, FPVal);
  if (Item.Action == WorklistItem::InsertPushOrPop &&
      Item.FIEToInsert.IsStore)
    SPVal -= Item.FIEToInsert.Size;
  if (Item.Action == WorklistItem::InsertPushOrPop &&
      Item.FIEToInsert.IsLoad)
    SPVal += Item.FIEToInsert.Size;
}
return InsertionPoint;
1857}

1859bool ShrinkWrapping::processInsertions() {
PredictiveStackPointerTracking PSPT(BF, Todo, Info, AllocatorId);
PSPT.run();

bool Changes = false;
for (BinaryBasicBlock &BB : BF) {
  // Process insertions before some inst.
  for (auto I = BB.begin(); I != BB.end(); ++I) {
    MCInst &Inst = *I;
    auto TodoList = BC.MIB->tryGetAnnotationAs<std::vector<WorklistItem>>(
        Inst, getAnnotationIndex());
    if (!TodoList)
      continue;
    Changes = true;
    std::vector<WorklistItem> List = *TodoList;
    LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Now processing insertions in "
 << BB.getName() << " before inst: "; Inst.dump()
; }; } } while (false)
      dbgs() << "Now processing insertions in " << BB.getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Now processing insertions in "
 << BB.getName() << " before inst: "; Inst.dump()
; }; } } while (false)
             << " before inst: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Now processing insertions in "
 << BB.getName() << " before inst: "; Inst.dump()
; }; } } while (false)
      Inst.dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Now processing insertions in "
 << BB.getName() << " before inst: "; Inst.dump()
; }; } } while (false)
    })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Now processing insertions in "
 << BB.getName() << " before inst: "; Inst.dump()
; }; } } while (false);
    auto Iter = I;
    std::pair<int, int> SPTState =
        *PSPT.getStateAt(Iter == BB.begin() ? (ProgramPoint)&BB : &*(--Iter));
    I = processInsertionsList(I, &BB, List, SPTState.first, SPTState.second);
  }
  // Process insertions at the end of bb
  auto WRI = Todo.find(&BB);
  if (WRI != Todo.end()) {
    std::pair<int, int> SPTState = *PSPT.getStateAt(*BB.rbegin());
    processInsertionsList(BB.end(), &BB, WRI->second, SPTState.first,
                          SPTState.second);
    Changes = true;
  }
}
return Changes;
1894}

1896void ShrinkWrapping::processDeletions() {
LivenessAnalysis &LA = Info.getLivenessAnalysis();
for (BinaryBasicBlock &BB : BF) {
  for (auto II = BB.begin(); II != BB.end(); ++II) {
    MCInst &Inst = *II;
    auto TodoList = BC.MIB->tryGetAnnotationAs<std::vector<WorklistItem>>(
        Inst, getAnnotationIndex());
    if (!TodoList)
      continue;
    // Process all deletions
    for (WorklistItem &Item : *TodoList) {
      if (Item.Action != WorklistItem::Erase &&
          Item.Action != WorklistItem::ChangeToAdjustment)
        continue;

      if (Item.Action == WorklistItem::ChangeToAdjustment) {
        // Is flag reg alive across this func?
        bool DontClobberFlags = LA.isAlive(&Inst, BC.MIB->getFlagsReg());
        if (int Sz = BC.MIB->getPushSize(Inst)) {
          BC.MIB->createStackPointerIncrement(Inst, Sz, DontClobberFlags);
          continue;
        }
        if (int Sz = BC.MIB->getPopSize(Inst)) {
          BC.MIB->createStackPointerDecrement(Inst, Sz, DontClobberFlags);
          continue;
        }
      }

      LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Erasing: "; BC.printInstruction
(dbgs(), Inst); }; } } while (false)
        dbgs() << "Erasing: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Erasing: "; BC.printInstruction
(dbgs(), Inst); }; } } while (false)
        BC.printInstruction(dbgs(), Inst);do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Erasing: "; BC.printInstruction
(dbgs(), Inst); }; } } while (false)
      })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Erasing: "; BC.printInstruction
(dbgs(), Inst); }; } } while (false);
      II = std::prev(BB.eraseInstruction(II));
      break;
    }
  }
}
1933}

1935void ShrinkWrapping::rebuildCFI() {
const bool FP = Info.getStackPointerTracking().HasFramePointer;
Info.invalidateAll();
if (!FP) {
1
Assuming 'FP' is false→
2
←
Taking true branch→
  rebuildCFIForSP();
3
←
Calling 'ShrinkWrapping::rebuildCFIForSP'→
  Info.invalidateAll();
}
for (unsigned I = 0, E = BC.MRI->getNumRegs(); I != E; ++I) {
  if (PushOffsetByReg[I] == 0 || PopOffsetByReg[I] == 0)
    continue;
  const int64_t SPValPush = PushOffsetByReg[I];
  const int64_t SPValPop = PopOffsetByReg[I];
  insertUpdatedCFI(I, SPValPush, SPValPop);
  Info.invalidateAll();
}
1950}

1952bool ShrinkWrapping::perform(bool HotOnly) {
HasDeletedOffsetCFIs = BitVector(BC.MRI->getNumRegs(), false);
PushOffsetByReg = std::vector<int64_t>(BC.MRI->getNumRegs(), 0LL);
PopOffsetByReg = std::vector<int64_t>(BC.MRI->getNumRegs(), 0LL);

// Update pass statistics
uint64_t TotalInstrs = 0ULL;
uint64_t TotalStoreInstrs = 0ULL;
for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {
  uint64_t BBExecCount = BB->getExecutionCount();
  if (!BBExecCount || BBExecCount == BinaryBasicBlock::COUNT_NO_PROFILE)
    continue;
  for (const auto &Instr : *BB) {
    if (BC.MIB->isPseudo(Instr))
      continue;
    if (BC.MIB->isStore(Instr))
      TotalStoreInstrs += BBExecCount;
    TotalInstrs += BBExecCount;
  }
}
InstrDynamicCount += TotalInstrs;
StoreDynamicCount += TotalStoreInstrs;

if (!FA.hasFrameInfo(BF))
  return false;

if (HotOnly && (BF.getKnownExecutionCount() < BC.getHotThreshold()))
  return false;

if (opts::EqualizeBBCounts)
  equalizeBBCounts(Info, BF);

if (BF.checkForAmbiguousJumpTables()) {
  LLVM_DEBUG(dbgs() << "BOLT-DEBUG: ambiguous JTs in " << BF.getPrintName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "BOLT-DEBUG: ambiguous JTs in "
 << BF.getPrintName() << ".\n"; } } while (false)
                    << ".\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "BOLT-DEBUG: ambiguous JTs in "
 << BF.getPrintName() << ".\n"; } } while (false);
  // We could call disambiguateJumpTables here, but it is probably not worth
  // the cost (of duplicating potentially large jump tables that could regress
  // dcache misses). Moreover, ambiguous JTs are rare and coming from code
  // written in assembly language. Just bail.
  return false;
}
SLM.initialize();
CSA.compute();
classifyCSRUses();
pruneUnwantedCSRs();
computeSaveLocations();
moveSaveRestores();
LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Func before shrink-wrapping: \n"
; BF.dump(); }; } } while (false)
  dbgs() << "Func before shrink-wrapping: \n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Func before shrink-wrapping: \n"
; BF.dump(); }; } } while (false)
  BF.dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Func before shrink-wrapping: \n"
; BF.dump(); }; } } while (false)
})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Func before shrink-wrapping: \n"
; BF.dump(); }; } } while (false);
SLM.performChanges();
// Early exit if processInsertions doesn't detect any todo items
if (!processInsertions())
  return false;
processDeletions();
if (foldIdenticalSplitEdges()) {
  const std::pair<unsigned, uint64_t> Stats = BF.eraseInvalidBBs();
  (void)Stats;
  LLVM_DEBUG(dbgs() << "Deleted " << Stats.firstdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "Deleted " << Stats
.first << " redundant split edge BBs (" << Stats.
second << " bytes) for " << BF.getPrintName() <<
 "\n"; } } while (false)
                    << " redundant split edge BBs (" << Stats.seconddo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "Deleted " << Stats
.first << " redundant split edge BBs (" << Stats.
second << " bytes) for " << BF.getPrintName() <<
 "\n"; } } while (false)
                    << " bytes) for " << BF.getPrintName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { dbgs() << "Deleted " << Stats
.first << " redundant split edge BBs (" << Stats.
second << " bytes) for " << BF.getPrintName() <<
 "\n"; } } while (false);
}
rebuildCFI();
// We may have split edges, creating BBs that need correct branching
BF.fixBranches();
LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Func after shrink-wrapping: \n"
; BF.dump(); }; } } while (false)
  dbgs() << "Func after shrink-wrapping: \n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Func after shrink-wrapping: \n"
; BF.dump(); }; } } while (false)
  BF.dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Func after shrink-wrapping: \n"
; BF.dump(); }; } } while (false)
})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("shrinkwrapping")) { { dbgs() << "Func after shrink-wrapping: \n"
; BF.dump(); }; } } while (false);
return true;
2023}

2025void ShrinkWrapping::printStats() {
outs() << "BOLT-INFO: Shrink wrapping moved " << SpillsMovedRegularMode
       << " spills inserting load/stores and " << SpillsMovedPushPopMode
       << " spills inserting push/pops\n";
if (!InstrDynamicCount || !StoreDynamicCount)
  return;
outs() << "BOLT-INFO: Shrink wrapping reduced " << SpillsMovedDynamicCount
       << " store executions ("
       << format("%.1lf%%",
                 (100.0 * SpillsMovedDynamicCount / InstrDynamicCount))
       << " total instructions executed, "
       << format("%.1lf%%",
                 (100.0 * SpillsMovedDynamicCount / StoreDynamicCount))
       << " store instructions)\n";
outs() << "BOLT-INFO: Shrink wrapping failed at reducing "
       << SpillsFailedDynamicCount << " store executions ("
       << format("%.1lf%%",
                 (100.0 * SpillsFailedDynamicCount / InstrDynamicCount))
       << " total instructions executed, "
       << format("%.1lf%%",
                 (100.0 * SpillsFailedDynamicCount / StoreDynamicCount))
       << " store instructions)\n";
2047}

2049// Operators necessary as a result of using MCAnnotation
2050raw_ostream &operator<<(raw_ostream &OS,
                      const std::vector<ShrinkWrapping::WorklistItem> &Vec) {
OS << "SWTodo[";
const char *Sep = "";
for (const ShrinkWrapping::WorklistItem &Item : Vec) {
  OS << Sep;
  switch (Item.Action) {
  case ShrinkWrapping::WorklistItem::Erase:
    OS << "Erase";
    break;
  case ShrinkWrapping::WorklistItem::ChangeToAdjustment:
    OS << "ChangeToAdjustment";
    break;
  case ShrinkWrapping::WorklistItem::InsertLoadOrStore:
    OS << "InsertLoadOrStore";
    break;
  case ShrinkWrapping::WorklistItem::InsertPushOrPop:
    OS << "InsertPushOrPop";
    break;
  }
  Sep = ", ";
}
OS << "]";
return OS;
2074}

2076raw_ostream &
2077operator<<(raw_ostream &OS,
         const std::vector<StackLayoutModifier::WorklistItem> &Vec) {
OS << "SLMTodo[";
const char *Sep = "";
for (const StackLayoutModifier::WorklistItem &Item : Vec) {
  OS << Sep;
  switch (Item.Action) {
  case StackLayoutModifier::WorklistItem::None:
    OS << "None";
    break;
  case StackLayoutModifier::WorklistItem::AdjustLoadStoreOffset:
    OS << "AdjustLoadStoreOffset";
    break;
  case StackLayoutModifier::WorklistItem::AdjustCFI:
    OS << "AdjustCFI";
    break;
  }
  Sep = ", ";
}
OS << "]";
return OS;
2098}

2100bool operator==(const ShrinkWrapping::WorklistItem &A,
              const ShrinkWrapping::WorklistItem &B) {
return (A.Action == B.Action && A.AffectedReg == B.AffectedReg &&
        A.Adjustment == B.Adjustment &&
        A.FIEToInsert.IsLoad == B.FIEToInsert.IsLoad &&
        A.FIEToInsert.IsStore == B.FIEToInsert.IsStore &&
        A.FIEToInsert.RegOrImm == B.FIEToInsert.RegOrImm &&
        A.FIEToInsert.Size == B.FIEToInsert.Size &&
        A.FIEToInsert.IsSimple == B.FIEToInsert.IsSimple &&
        A.FIEToInsert.StackOffset == B.FIEToInsert.StackOffset);
2110}

2112bool operator==(const StackLayoutModifier::WorklistItem &A,
              const StackLayoutModifier::WorklistItem &B) {
return (A.Action == B.Action && A.OffsetUpdate == B.OffsetUpdate);
2115}

2117} // end namespace bolt
2118} // end namespace llvm