2116 lines · 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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the ShrinkWrapping class.10//11//===----------------------------------------------------------------------===//12 13#include "bolt/Passes/ShrinkWrapping.h"14#include "bolt/Passes/DataflowInfoManager.h"15#include "bolt/Passes/MCF.h"16#include "bolt/Utils/CommandLineOpts.h"17#include <numeric>18#include <optional>19#include <stack>20 21#define DEBUG_TYPE "shrinkwrapping"22 23using namespace llvm;24 25namespace opts {26 27extern cl::opt<bool> TimeOpts;28extern cl::OptionCategory BoltOptCategory;29 30static cl::opt<unsigned> ShrinkWrappingThreshold(31 "shrink-wrapping-threshold",32 cl::desc("Percentage of prologue execution count to use as threshold when"33 " evaluating whether a block is cold enough to be profitable to"34 " move eligible spills there"),35 cl::init(30), cl::ZeroOrMore, cl::cat(BoltOptCategory));36} // namespace opts37 38namespace llvm {39namespace bolt {40 41void CalleeSavedAnalysis::analyzeSaves() {42 ReachingDefOrUse</*Def=*/true> &RD = Info.getReachingDefs();43 StackReachingUses &SRU = Info.getStackReachingUses();44 auto &InsnToBB = Info.getInsnToBBMap();45 BitVector BlacklistedRegs(BC.MRI->getNumRegs(), false);46 47 LLVM_DEBUG(dbgs() << "Checking spill locations\n");48 for (BinaryBasicBlock &BB : BF) {49 LLVM_DEBUG(dbgs() << "\tNow at BB " << BB.getName() << "\n");50 const MCInst *Prev = nullptr;51 for (MCInst &Inst : BB) {52 if (ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(Inst)) {53 // Blacklist weird stores we don't understand54 if ((!FIE->IsSimple || FIE->StackOffset >= 0) && FIE->IsStore &&55 FIE->IsStoreFromReg) {56 BlacklistedRegs.set(FIE->RegOrImm);57 CalleeSaved.reset(FIE->RegOrImm);58 Prev = &Inst;59 continue;60 }61 62 if (!FIE->IsStore || !FIE->IsStoreFromReg ||63 BlacklistedRegs[FIE->RegOrImm]) {64 Prev = &Inst;65 continue;66 }67 68 // If this reg is defined locally, it is not a callee-saved reg69 if (RD.isReachedBy(FIE->RegOrImm,70 Prev ? RD.expr_begin(*Prev) : RD.expr_begin(BB))) {71 BlacklistedRegs.set(FIE->RegOrImm);72 CalleeSaved.reset(FIE->RegOrImm);73 Prev = &Inst;74 continue;75 }76 77 // If this stack position is accessed in another function, we are78 // probably dealing with a parameter passed in a stack -- do not mess79 // with it80 if (SRU.isStoreUsed(*FIE,81 Prev ? SRU.expr_begin(*Prev) : SRU.expr_begin(BB)),82 /*IncludeLocalAccesses=*/false) {83 BlacklistedRegs.set(FIE->RegOrImm);84 CalleeSaved.reset(FIE->RegOrImm);85 Prev = &Inst;86 continue;87 }88 89 // If this stack position is loaded elsewhere in another reg, we can't90 // update it, so blacklist it.91 if (SRU.isLoadedInDifferentReg(*FIE, Prev ? SRU.expr_begin(*Prev)92 : SRU.expr_begin(BB))) {93 BlacklistedRegs.set(FIE->RegOrImm);94 CalleeSaved.reset(FIE->RegOrImm);95 Prev = &Inst;96 continue;97 }98 99 // Ignore regs with multiple saves100 if (CalleeSaved[FIE->RegOrImm]) {101 BlacklistedRegs.set(FIE->RegOrImm);102 CalleeSaved.reset(FIE->RegOrImm);103 Prev = &Inst;104 continue;105 }106 107 CalleeSaved.set(FIE->RegOrImm);108 SaveFIEByReg[FIE->RegOrImm] = &*FIE;109 SavingCost[FIE->RegOrImm] += InsnToBB[&Inst]->getKnownExecutionCount();110 BC.MIB->addAnnotation(Inst, getSaveTag(), FIE->RegOrImm, AllocatorId);111 OffsetsByReg[FIE->RegOrImm] = FIE->StackOffset;112 LLVM_DEBUG(dbgs() << "Logging new candidate for Callee-Saved Reg: "113 << FIE->RegOrImm << "\n");114 }115 Prev = &Inst;116 }117 }118}119 120void CalleeSavedAnalysis::analyzeRestores() {121 ReachingDefOrUse</*Def=*/false> &RU = Info.getReachingUses();122 123 // Now compute all restores of these callee-saved regs124 for (BinaryBasicBlock &BB : BF) {125 const MCInst *Prev = nullptr;126 for (MCInst &Inst : llvm::reverse(BB)) {127 if (ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(Inst)) {128 if (!FIE->IsLoad || !CalleeSaved[FIE->RegOrImm]) {129 Prev = &Inst;130 continue;131 }132 133 // If this reg is used locally after a restore, then we are probably134 // not dealing with a callee-saved reg. Except if this use is by135 // another store, but we don't cover this case yet.136 // Also not callee-saved if this load accesses caller stack or isn't137 // simple.138 if (!FIE->IsSimple || FIE->StackOffset >= 0 ||139 RU.isReachedBy(FIE->RegOrImm,140 Prev ? RU.expr_begin(*Prev) : RU.expr_begin(BB))) {141 CalleeSaved.reset(FIE->RegOrImm);142 Prev = &Inst;143 continue;144 }145 // If stack offsets between saves/store don't agree with each other,146 // we don't completely understand what's happening here147 if (FIE->StackOffset != OffsetsByReg[FIE->RegOrImm]) {148 CalleeSaved.reset(FIE->RegOrImm);149 LLVM_DEBUG(dbgs() << "Dismissing Callee-Saved Reg because we found a "150 "mismatching restore: "151 << FIE->RegOrImm << "\n");152 Prev = &Inst;153 continue;154 }155 156 LLVM_DEBUG(dbgs() << "Adding matching restore for: " << FIE->RegOrImm157 << "\n");158 if (LoadFIEByReg[FIE->RegOrImm] == nullptr)159 LoadFIEByReg[FIE->RegOrImm] = &*FIE;160 BC.MIB->addAnnotation(Inst, getRestoreTag(), FIE->RegOrImm,161 AllocatorId);162 HasRestores.set(FIE->RegOrImm);163 }164 Prev = &Inst;165 }166 }167}168 169std::vector<MCInst *> CalleeSavedAnalysis::getSavesByReg(uint16_t Reg) {170 std::vector<MCInst *> Results;171 for (BinaryBasicBlock &BB : BF)172 for (MCInst &Inst : BB)173 if (getSavedReg(Inst) == Reg)174 Results.push_back(&Inst);175 return Results;176}177 178std::vector<MCInst *> CalleeSavedAnalysis::getRestoresByReg(uint16_t Reg) {179 std::vector<MCInst *> Results;180 for (BinaryBasicBlock &BB : BF)181 for (MCInst &Inst : BB)182 if (getRestoredReg(Inst) == Reg)183 Results.push_back(&Inst);184 return Results;185}186 187CalleeSavedAnalysis::~CalleeSavedAnalysis() {188 for (BinaryBasicBlock &BB : BF) {189 for (MCInst &Inst : BB) {190 BC.MIB->removeAnnotation(Inst, getSaveTag());191 BC.MIB->removeAnnotation(Inst, getRestoreTag());192 }193 }194}195 196void StackLayoutModifier::blacklistRegion(int64_t Offset, int64_t Size) {197 if (BlacklistedRegions[Offset] < Size)198 BlacklistedRegions[Offset] = Size;199}200 201bool StackLayoutModifier::isRegionBlacklisted(int64_t Offset, int64_t Size) {202 for (std::pair<const int64_t, int64_t> Elem : BlacklistedRegions)203 if (Offset + Size > Elem.first && Offset < Elem.first + Elem.second)204 return true;205 return false;206}207 208bool StackLayoutModifier::blacklistAllInConflictWith(int64_t Offset,209 int64_t Size) {210 bool HasConflict = false;211 for (auto Iter = AvailableRegions.begin(); Iter != AvailableRegions.end();) {212 std::pair<const int64_t, int64_t> &Elem = *Iter;213 if (Offset + Size > Elem.first && Offset < Elem.first + Elem.second &&214 (Offset != Elem.first || Size != Elem.second)) {215 Iter = AvailableRegions.erase(Iter);216 HasConflict = true;217 continue;218 }219 ++Iter;220 }221 if (HasConflict) {222 blacklistRegion(Offset, Size);223 return true;224 }225 return false;226}227 228void StackLayoutModifier::checkFramePointerInitialization(MCInst &Point) {229 StackPointerTracking &SPT = Info.getStackPointerTracking();230 if (!BC.MII->get(Point.getOpcode())231 .hasDefOfPhysReg(Point, BC.MIB->getFramePointer(), *BC.MRI))232 return;233 234 int SPVal, FPVal;235 std::tie(SPVal, FPVal) = *SPT.getStateBefore(Point);236 std::pair<MCPhysReg, int64_t> FP;237 238 if (FPVal != SPT.EMPTY && FPVal != SPT.SUPERPOSITION)239 FP = std::make_pair(BC.MIB->getFramePointer(), FPVal);240 else241 FP = std::make_pair(0, 0);242 std::pair<MCPhysReg, int64_t> SP;243 244 if (SPVal != SPT.EMPTY && SPVal != SPT.SUPERPOSITION)245 SP = std::make_pair(BC.MIB->getStackPointer(), SPVal);246 else247 SP = std::make_pair(0, 0);248 249 int64_t Output;250 if (!BC.MIB->evaluateStackOffsetExpr(Point, Output, SP, FP))251 return;252 253 // Not your regular frame pointer initialization... bail254 if (Output != SPVal)255 blacklistRegion(0, 0);256}257 258void StackLayoutModifier::checkStackPointerRestore(MCInst &Point) {259 StackPointerTracking &SPT = Info.getStackPointerTracking();260 if (!BC.MII->get(Point.getOpcode())261 .hasDefOfPhysReg(Point, BC.MIB->getStackPointer(), *BC.MRI))262 return;263 // Check if the definition of SP comes from FP -- in this case, this264 // value may need to be updated depending on our stack layout changes265 bool UsesFP = llvm::any_of(BC.MIB->useOperands(Point), [&](MCOperand &Op) {266 return Op.isReg() && Op.getReg() == BC.MIB->getFramePointer();267 });268 if (!UsesFP)269 return;270 271 // Setting up evaluation272 int SPVal, FPVal;273 std::tie(SPVal, FPVal) = *SPT.getStateBefore(Point);274 std::pair<MCPhysReg, int64_t> FP;275 276 if (FPVal != SPT.EMPTY && FPVal != SPT.SUPERPOSITION)277 FP = std::make_pair(BC.MIB->getFramePointer(), FPVal);278 else279 FP = std::make_pair(0, 0);280 std::pair<MCPhysReg, int64_t> SP;281 282 if (SPVal != SPT.EMPTY && SPVal != SPT.SUPERPOSITION)283 SP = std::make_pair(BC.MIB->getStackPointer(), SPVal);284 else285 SP = std::make_pair(0, 0);286 287 int64_t Output;288 if (!BC.MIB->evaluateStackOffsetExpr(Point, Output, SP, FP))289 return;290 291 // If the value is the same of FP, no need to adjust it292 if (Output == FPVal)293 return;294 295 // If an allocation happened through FP, bail296 if (Output <= SPVal) {297 blacklistRegion(0, 0);298 return;299 }300 301 // We are restoring SP to an old value based on FP. Mark it as a stack302 // access to be fixed later.303 BC.MIB->addAnnotation(Point, getSlotTag(), Output, AllocatorId);304}305 306void StackLayoutModifier::classifyStackAccesses() {307 // Understand when stack slots are being used non-locally308 StackReachingUses &SRU = Info.getStackReachingUses();309 310 for (BinaryBasicBlock &BB : BF) {311 const MCInst *Prev = nullptr;312 for (MCInst &Inst : llvm::reverse(BB)) {313 checkFramePointerInitialization(Inst);314 checkStackPointerRestore(Inst);315 ErrorOr<const FrameIndexEntry &> FIEX = FA.getFIEFor(Inst);316 if (!FIEX) {317 Prev = &Inst;318 continue;319 }320 if (!FIEX->IsSimple || (FIEX->IsStore && !FIEX->IsStoreFromReg)) {321 blacklistRegion(FIEX->StackOffset, FIEX->Size);322 Prev = &Inst;323 continue;324 }325 // If this stack position is accessed in another function, we are326 // probably dealing with a parameter passed in a stack -- do not mess327 // with it328 if (SRU.isStoreUsed(*FIEX,329 Prev ? SRU.expr_begin(*Prev) : SRU.expr_begin(BB),330 /*IncludeLocalAccesses=*/false)) {331 blacklistRegion(FIEX->StackOffset, FIEX->Size);332 Prev = &Inst;333 continue;334 }335 // Now we have a clear stack slot access. Check if its blacklisted or if336 // it conflicts with another chunk.337 if (isRegionBlacklisted(FIEX->StackOffset, FIEX->Size) ||338 blacklistAllInConflictWith(FIEX->StackOffset, FIEX->Size)) {339 Prev = &Inst;340 continue;341 }342 // We are free to go. Add it as available stack slot which we know how343 // to move it.344 AvailableRegions[FIEX->StackOffset] = FIEX->Size;345 BC.MIB->addAnnotation(Inst, getSlotTag(), FIEX->StackOffset, AllocatorId);346 RegionToRegMap[FIEX->StackOffset].insert(FIEX->RegOrImm);347 RegToRegionMap[FIEX->RegOrImm].insert(FIEX->StackOffset);348 LLVM_DEBUG(dbgs() << "Adding region " << FIEX->StackOffset << " size "349 << (int)FIEX->Size << "\n");350 }351 }352}353 354void StackLayoutModifier::classifyCFIs() {355 std::stack<std::pair<int64_t, uint16_t>> CFIStack;356 int64_t CfaOffset = -8;357 uint16_t CfaReg = 7;358 359 auto recordAccess = [&](MCInst *Inst, int64_t Offset) {360 const uint16_t Reg = *BC.MRI->getLLVMRegNum(CfaReg, /*isEH=*/false);361 if (Reg == BC.MIB->getStackPointer() || Reg == BC.MIB->getFramePointer()) {362 BC.MIB->addAnnotation(*Inst, getSlotTag(), Offset, AllocatorId);363 LLVM_DEBUG(dbgs() << "Recording CFI " << Offset << "\n");364 } else {365 IsSimple = false;366 return;367 }368 };369 370 for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {371 for (MCInst &Inst : *BB) {372 if (!BC.MIB->isCFI(Inst))373 continue;374 const MCCFIInstruction *CFI = BF.getCFIFor(Inst);375 switch (CFI->getOperation()) {376 case MCCFIInstruction::OpDefCfa:377 CfaOffset = -CFI->getOffset();378 recordAccess(&Inst, CfaOffset);379 [[fallthrough]];380 case MCCFIInstruction::OpDefCfaRegister:381 CfaReg = CFI->getRegister();382 break;383 case MCCFIInstruction::OpDefCfaOffset:384 CfaOffset = -CFI->getOffset();385 recordAccess(&Inst, CfaOffset);386 break;387 case MCCFIInstruction::OpOffset:388 recordAccess(&Inst, CFI->getOffset());389 BC.MIB->addAnnotation(Inst, getOffsetCFIRegTag(),390 BC.MRI->getLLVMRegNum(CFI->getRegister(),391 /*isEH=*/false),392 AllocatorId);393 break;394 case MCCFIInstruction::OpSameValue:395 BC.MIB->addAnnotation(Inst, getOffsetCFIRegTag(),396 BC.MRI->getLLVMRegNum(CFI->getRegister(),397 /*isEH=*/false),398 AllocatorId);399 break;400 case MCCFIInstruction::OpRememberState:401 CFIStack.push(std::make_pair(CfaOffset, CfaReg));402 break;403 case MCCFIInstruction::OpRestoreState: {404 assert(!CFIStack.empty() && "Corrupt CFI stack");405 std::pair<int64_t, uint16_t> Elem = CFIStack.top();406 CFIStack.pop();407 CfaOffset = Elem.first;408 CfaReg = Elem.second;409 break;410 }411 case MCCFIInstruction::OpRelOffset:412 case MCCFIInstruction::OpAdjustCfaOffset:413 llvm_unreachable("Unhandled AdjustCfaOffset");414 break;415 default:416 break;417 }418 }419 }420}421 422void StackLayoutModifier::scheduleChange(423 MCInst &Inst, StackLayoutModifier::WorklistItem Item) {424 auto &WList = BC.MIB->getOrCreateAnnotationAs<std::vector<WorklistItem>>(425 Inst, getTodoTag(), AllocatorId);426 WList.push_back(Item);427}428 429bool StackLayoutModifier::canCollapseRegion(MCInst *DeletedPush) {430 if (!IsSimple || !BC.MIB->isPush(*DeletedPush))431 return false;432 433 ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(*DeletedPush);434 if (!FIE)435 return false;436 437 return canCollapseRegion(FIE->StackOffset);438}439 440bool StackLayoutModifier::canCollapseRegion(int64_t RegionAddr) {441 if (!IsInitialized)442 initialize();443 if (!IsSimple)444 return false;445 446 if (CollapsedRegions.count(RegionAddr))447 return true;448 449 // Check if it is possible to readjust all accesses below RegionAddr450 if (!BlacklistedRegions.empty())451 return false;452 453 return true;454}455 456bool StackLayoutModifier::collapseRegion(MCInst *DeletedPush) {457 ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(*DeletedPush);458 if (!FIE)459 return false;460 int64_t RegionAddr = FIE->StackOffset;461 int64_t RegionSz = FIE->Size;462 return collapseRegion(DeletedPush, RegionAddr, RegionSz);463}464 465bool StackLayoutModifier::collapseRegion(MCInst *Alloc, int64_t RegionAddr,466 int64_t RegionSz) {467 if (!canCollapseRegion(RegionAddr))468 return false;469 470 assert(IsInitialized);471 StackAllocationAnalysis &SAA = Info.getStackAllocationAnalysis();472 473 for (BinaryBasicBlock &BB : BF) {474 for (MCInst &Inst : BB) {475 if (!BC.MIB->hasAnnotation(Inst, getSlotTag()))476 continue;477 auto Slot =478 BC.MIB->getAnnotationAs<decltype(FrameIndexEntry::StackOffset)>(479 Inst, getSlotTag());480 if (!AvailableRegions.count(Slot))481 continue;482 // We need to ensure this access is affected by the deleted push483 if (!(*SAA.getStateBefore(Inst))[SAA.ExprToIdx[Alloc]])484 continue;485 486 if (BC.MIB->isCFI(Inst)) {487 if (Slot > RegionAddr)488 continue;489 scheduleChange(Inst, WorklistItem(WorklistItem::AdjustCFI, RegionSz));490 continue;491 }492 ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(Inst);493 if (!FIE) {494 if (Slot > RegionAddr)495 continue;496 // SP update based on frame pointer497 scheduleChange(498 Inst, WorklistItem(WorklistItem::AdjustLoadStoreOffset, RegionSz));499 continue;500 }501 502 if (Slot == RegionAddr) {503 BC.MIB->addAnnotation(Inst, "AccessesDeletedPos", 0U, AllocatorId);504 continue;505 }506 if (BC.MIB->isPush(Inst) || BC.MIB->isPop(Inst))507 continue;508 509 if (FIE->StackPtrReg == BC.MIB->getStackPointer() && Slot < RegionAddr)510 continue;511 512 if (FIE->StackPtrReg == BC.MIB->getFramePointer() && Slot > RegionAddr)513 continue;514 515 scheduleChange(516 Inst, WorklistItem(WorklistItem::AdjustLoadStoreOffset, RegionSz));517 }518 }519 520 CollapsedRegions.insert(RegionAddr);521 return true;522}523 524void StackLayoutModifier::setOffsetForCollapsedAccesses(int64_t NewOffset) {525 for (BinaryBasicBlock &BB : BF) {526 for (MCInst &Inst : BB) {527 if (!BC.MIB->hasAnnotation(Inst, "AccessesDeletedPos"))528 continue;529 BC.MIB->removeAnnotation(Inst, "AccessesDeletedPos");530 scheduleChange(531 Inst, WorklistItem(WorklistItem::AdjustLoadStoreOffset, NewOffset));532 }533 }534}535 536bool StackLayoutModifier::canInsertRegion(ProgramPoint P) {537 if (!IsInitialized)538 initialize();539 if (!IsSimple)540 return false;541 542 StackPointerTracking &SPT = Info.getStackPointerTracking();543 int64_t RegionAddr = SPT.getStateBefore(P)->first;544 if (RegionAddr == SPT.SUPERPOSITION || RegionAddr == SPT.EMPTY)545 return false;546 547 if (InsertedRegions.count(RegionAddr))548 return true;549 550 // Check if we are going to screw up stack accesses at call sites that551 // pass parameters via stack552 if (!BlacklistedRegions.empty())553 return false;554 555 return true;556}557 558bool StackLayoutModifier::insertRegion(ProgramPoint P, int64_t RegionSz) {559 if (!canInsertRegion(P))560 return false;561 562 assert(IsInitialized);563 StackPointerTracking &SPT = Info.getStackPointerTracking();564 // This RegionAddr is slightly different from the one seen in collapseRegion565 // This is the value of SP before the allocation the user wants to make.566 int64_t RegionAddr = SPT.getStateBefore(P)->first;567 if (RegionAddr == SPT.SUPERPOSITION || RegionAddr == SPT.EMPTY)568 return false;569 570 DominatorAnalysis<false> &DA = Info.getDominatorAnalysis();571 572 for (BinaryBasicBlock &BB : BF) {573 for (MCInst &Inst : BB) {574 if (!BC.MIB->hasAnnotation(Inst, getSlotTag()))575 continue;576 auto Slot =577 BC.MIB->getAnnotationAs<decltype(FrameIndexEntry::StackOffset)>(578 Inst, getSlotTag());579 if (!AvailableRegions.count(Slot))580 continue;581 582 if (!(DA.doesADominateB(P, Inst)))583 continue;584 585 if (BC.MIB->isCFI(Inst)) {586 if (Slot >= RegionAddr)587 continue;588 scheduleChange(Inst, WorklistItem(WorklistItem::AdjustCFI, -RegionSz));589 continue;590 }591 ErrorOr<const FrameIndexEntry &> FIE = FA.getFIEFor(Inst);592 if (!FIE) {593 if (Slot >= RegionAddr)594 continue;595 scheduleChange(596 Inst, WorklistItem(WorklistItem::AdjustLoadStoreOffset, -RegionSz));597 continue;598 }599 600 if (FIE->StackPtrReg == BC.MIB->getStackPointer() && Slot < RegionAddr)601 continue;602 if (FIE->StackPtrReg == BC.MIB->getFramePointer() && Slot >= RegionAddr)603 continue;604 if (BC.MIB->isPush(Inst) || BC.MIB->isPop(Inst))605 continue;606 scheduleChange(607 Inst, WorklistItem(WorklistItem::AdjustLoadStoreOffset, -RegionSz));608 }609 }610 611 InsertedRegions.insert(RegionAddr);612 return true;613}614 615void StackLayoutModifier::performChanges() {616 std::set<uint32_t> ModifiedCFIIndices;617 for (BinaryBasicBlock &BB : BF) {618 for (MCInst &Inst : llvm::reverse(BB)) {619 if (BC.MIB->hasAnnotation(Inst, "AccessesDeletedPos")) {620 assert(BC.MIB->isPop(Inst) || BC.MIB->isPush(Inst));621 BC.MIB->removeAnnotation(Inst, "AccessesDeletedPos");622 }623 if (!BC.MIB->hasAnnotation(Inst, getTodoTag()))624 continue;625 auto &WList = BC.MIB->getAnnotationAs<std::vector<WorklistItem>>(626 Inst, getTodoTag());627 int64_t Adjustment = 0;628 WorklistItem::ActionType AdjustmentType = WorklistItem::None;629 for (WorklistItem &WI : WList) {630 if (WI.Action == WorklistItem::None)631 continue;632 assert(WI.Action == WorklistItem::AdjustLoadStoreOffset ||633 WI.Action == WorklistItem::AdjustCFI);634 assert((AdjustmentType == WorklistItem::None ||635 AdjustmentType == WI.Action) &&636 "Conflicting actions requested at the same program point");637 AdjustmentType = WI.Action;638 Adjustment += WI.OffsetUpdate;639 }640 if (!Adjustment)641 continue;642 if (AdjustmentType != WorklistItem::AdjustLoadStoreOffset) {643 assert(BC.MIB->isCFI(Inst));644 uint32_t CFINum = Inst.getOperand(0).getImm();645 if (ModifiedCFIIndices.count(CFINum))646 continue;647 ModifiedCFIIndices.insert(CFINum);648 const MCCFIInstruction *CFI = BF.getCFIFor(Inst);649 const MCCFIInstruction::OpType Operation = CFI->getOperation();650 if (Operation == MCCFIInstruction::OpDefCfa ||651 Operation == MCCFIInstruction::OpDefCfaOffset)652 Adjustment = 0 - Adjustment;653 LLVM_DEBUG(dbgs() << "Changing CFI offset from " << CFI->getOffset()654 << " to " << (CFI->getOffset() + Adjustment) << "\n");655 BF.mutateCFIOffsetFor(Inst, CFI->getOffset() + Adjustment);656 continue;657 }658 int32_t SrcImm = 0;659 MCPhysReg Reg = 0;660 MCPhysReg StackPtrReg = 0;661 int64_t StackOffset = 0;662 bool IsIndexed = false;663 bool IsLoad = false;664 bool IsStore = false;665 bool IsSimple = false;666 bool IsStoreFromReg = false;667 uint8_t Size = 0;668 bool Success = false;669 Success = BC.MIB->isStackAccess(Inst, IsLoad, IsStore, IsStoreFromReg,670 Reg, SrcImm, StackPtrReg, StackOffset,671 Size, IsSimple, IsIndexed);672 if (!Success) {673 // SP update based on FP value674 Success = BC.MIB->addToImm(Inst, Adjustment, &*BC.Ctx);675 assert(Success);676 continue;677 }678 assert(Success && IsSimple && !IsIndexed && (!IsStore || IsStoreFromReg));679 if (StackPtrReg != BC.MIB->getFramePointer())680 Adjustment = -Adjustment;681 if (IsLoad)682 BC.MIB->createRestoreFromStack(Inst, StackPtrReg,683 StackOffset + Adjustment, Reg, Size);684 else if (IsStore)685 BC.MIB->createSaveToStack(Inst, StackPtrReg, StackOffset + Adjustment,686 Reg, Size);687 LLVM_DEBUG({688 dbgs() << "Adjusted instruction: ";689 Inst.dump();690 });691 }692 }693}694 695void StackLayoutModifier::initialize() {696 classifyStackAccesses();697 classifyCFIs();698 IsInitialized = true;699}700 701std::atomic<std::uint64_t> ShrinkWrapping::SpillsMovedRegularMode{0};702std::atomic<std::uint64_t> ShrinkWrapping::SpillsMovedPushPopMode{0};703std::atomic<std::uint64_t> ShrinkWrapping::SpillsMovedDynamicCount{0};704std::atomic<std::uint64_t> ShrinkWrapping::SpillsFailedDynamicCount{0};705std::atomic<std::uint64_t> ShrinkWrapping::InstrDynamicCount{0};706std::atomic<std::uint64_t> ShrinkWrapping::StoreDynamicCount{0};707 708using BBIterTy = BinaryBasicBlock::iterator;709 710void ShrinkWrapping::classifyCSRUses() {711 DominatorAnalysis<false> &DA = Info.getDominatorAnalysis();712 StackPointerTracking &SPT = Info.getStackPointerTracking();713 UsesByReg = std::vector<BitVector>(BC.MRI->getNumRegs(),714 BitVector(DA.NumInstrs, false));715 716 const BitVector &FPAliases = BC.MIB->getAliases(BC.MIB->getFramePointer());717 for (BinaryBasicBlock &BB : BF) {718 for (MCInst &Inst : BB) {719 if (BC.MIB->isCFI(Inst))720 continue;721 BitVector BV = BitVector(BC.MRI->getNumRegs(), false);722 BC.MIB->getTouchedRegs(Inst, BV);723 BV &= CSA.CalleeSaved;724 for (int I : BV.set_bits()) {725 if (I == 0)726 continue;727 if (CSA.getSavedReg(Inst) != I && CSA.getRestoredReg(Inst) != I)728 UsesByReg[I].set(DA.ExprToIdx[&Inst]);729 }730 if (!SPT.HasFramePointer || !BC.MIB->isCall(Inst))731 continue;732 BV = CSA.CalleeSaved;733 BV &= FPAliases;734 for (int I : BV.set_bits())735 UsesByReg[I].set(DA.ExprToIdx[&Inst]);736 }737 }738}739 740void ShrinkWrapping::pruneUnwantedCSRs() {741 BitVector ParamRegs = BC.MIB->getRegsUsedAsParams();742 for (unsigned I = 0, E = BC.MRI->getNumRegs(); I != E; ++I) {743 if (!CSA.CalleeSaved[I])744 continue;745 if (ParamRegs[I]) {746 CSA.CalleeSaved.reset(I);747 continue;748 }749 if (UsesByReg[I].empty()) {750 LLVM_DEBUG(751 dbgs()752 << "Dismissing Callee-Saved Reg because we found no uses of it:" << I753 << "\n");754 CSA.CalleeSaved.reset(I);755 continue;756 }757 if (!CSA.HasRestores[I]) {758 LLVM_DEBUG(759 dbgs() << "Dismissing Callee-Saved Reg because it does not have "760 "restores:"761 << I << "\n");762 CSA.CalleeSaved.reset(I);763 }764 }765}766 767void ShrinkWrapping::computeSaveLocations() {768 BestSavePos = std::vector<std::vector<MCInst *>>(BC.MRI->getNumRegs());769 ReachingInsns<true> &RI = Info.getReachingInsnsBackwards();770 DominatorAnalysis<false> &DA = Info.getDominatorAnalysis();771 StackPointerTracking &SPT = Info.getStackPointerTracking();772 773 LLVM_DEBUG(dbgs() << "Checking save/restore possibilities\n");774 for (BinaryBasicBlock &BB : BF) {775 LLVM_DEBUG(dbgs() << "\tNow at BB " << BB.getName() << "\n");776 777 MCInst *First = BB.begin() != BB.end() ? &*BB.begin() : nullptr;778 if (!First)779 continue;780 781 // Use reaching instructions to detect if we are inside a loop - if we782 // are, do not consider this BB as valid placement for saves.783 if (RI.isInLoop(BB))784 continue;785 786 const std::pair<int, int> SPFP = *SPT.getStateBefore(*First);787 // If we don't know stack state at this point, bail788 if ((SPFP.first == SPT.SUPERPOSITION || SPFP.first == SPT.EMPTY) &&789 (SPFP.second == SPT.SUPERPOSITION || SPFP.second == SPT.EMPTY))790 continue;791 792 for (unsigned I = 0, E = BC.MRI->getNumRegs(); I != E; ++I) {793 if (!CSA.CalleeSaved[I])794 continue;795 796 BitVector BBDominatedUses = BitVector(DA.NumInstrs, false);797 for (int J : UsesByReg[I].set_bits())798 if (DA.doesADominateB(*First, J))799 BBDominatedUses.set(J);800 LLVM_DEBUG(dbgs() << "\t\tBB " << BB.getName() << " dominates "801 << BBDominatedUses.count() << " uses for reg " << I802 << ". Total uses for reg is " << UsesByReg[I].count()803 << "\n");804 BBDominatedUses &= UsesByReg[I];805 if (BBDominatedUses == UsesByReg[I]) {806 LLVM_DEBUG(dbgs() << "\t\t\tAdded " << BB.getName()807 << " as a save pos for " << I << "\n");808 BestSavePos[I].push_back(First);809 LLVM_DEBUG({810 dbgs() << "Dominated uses are:\n";811 for (int J : UsesByReg[I].set_bits()) {812 dbgs() << "Idx " << J << ": ";813 BC.printInstruction(dbgs(), *DA.Expressions[J]);814 DA.Expressions[J]->dump();815 }816 });817 }818 }819 }820 821 BestSaveCount = std::vector<std::vector<uint64_t>>(BC.MRI->getNumRegs());822 823 auto &InsnToBB = Info.getInsnToBBMap();824 for (unsigned I = 0, E = BC.MRI->getNumRegs(); I != E; ++I) {825 if (!CSA.CalleeSaved[I])826 continue;827 828 llvm::stable_sort(BestSavePos[I], [&](const MCInst *A, const MCInst *B) {829 const BinaryBasicBlock *BBA = InsnToBB[A];830 const BinaryBasicBlock *BBB = InsnToBB[B];831 const uint64_t CountA = BBA->getKnownExecutionCount();832 const uint64_t CountB = BBB->getKnownExecutionCount();833 return CountB < CountA;834 });835 836 for (MCInst *Pos : BestSavePos[I]) {837 const BinaryBasicBlock *BB = InsnToBB[Pos];838 const uint64_t Count = BB->getKnownExecutionCount();839 BestSaveCount[I].push_back(Count);840 }841 }842}843 844void ShrinkWrapping::computeDomOrder() {845 DomOrder = std::vector<MCPhysReg>(BC.MRI->getNumRegs(), 0);846 std::vector<MCPhysReg> Order;847 for (MCPhysReg I = 0, E = BC.MRI->getNumRegs(); I != E; ++I) {848 Order.push_back(I);849 }850 851 DominatorAnalysis<false> &DA = Info.getDominatorAnalysis();852 auto &InsnToBB = Info.getInsnToBBMap();853 llvm::sort(Order, [&](const MCPhysReg &A, const MCPhysReg &B) {854 BinaryBasicBlock *BBA =855 BestSavePos[A].size() ? InsnToBB[BestSavePos[A].back()] : nullptr;856 BinaryBasicBlock *BBB =857 BestSavePos[B].size() ? InsnToBB[BestSavePos[B].back()] : nullptr;858 if (BBA == BBB)859 return A < B;860 if (!BBA && BBB)861 return false;862 if (BBA && !BBB)863 return true;864 if (DA.doesADominateB(*BestSavePos[A].back(), *BestSavePos[B].back()))865 return true;866 if (DA.doesADominateB(*BestSavePos[B].back(), *BestSavePos[A].back()))867 return false;868 return A < B;869 });870 871 for (MCPhysReg I = 0, E = BC.MRI->getNumRegs(); I != E; ++I)872 DomOrder[Order[I]] = I;873}874 875bool ShrinkWrapping::isBestSavePosCold(unsigned CSR, MCInst *&BestPosSave,876 uint64_t &TotalEstimatedWin) {877 const uint64_t CurSavingCost = CSA.SavingCost[CSR];878 if (!CSA.CalleeSaved[CSR])879 return false;880 881 assert(BestSaveCount[CSR].size() == BestSavePos[CSR].size() &&882 "save position vectors out of sync");883 if (BestSaveCount[CSR].empty())884 return false;885 886 const uint64_t BestCount = BestSaveCount[CSR].back();887 BestPosSave = BestSavePos[CSR].back();888 if (BestCount >= (opts::ShrinkWrappingThreshold / 100.0) * CurSavingCost)889 return false;890 891 LLVM_DEBUG({892 auto &InsnToBB = Info.getInsnToBBMap();893 dbgs() << "Better position for saves found in func " << BF.getPrintName()894 << " count << " << BF.getKnownExecutionCount() << "\n";895 dbgs() << "Reg: " << CSR << "; New BB: " << InsnToBB[BestPosSave]->getName()896 << " Freq reduction: " << (CurSavingCost - BestCount) << "\n";897 });898 899 TotalEstimatedWin = CurSavingCost - BestCount;900 return true;901}902 903/// Auxiliary function used to create basic blocks for critical edges and update904/// the dominance frontier with these new locations905void ShrinkWrapping::splitFrontierCritEdges(906 BinaryFunction *Func, SmallVector<ProgramPoint, 4> &Frontier,907 const SmallVector<bool, 4> &IsCritEdge,908 const SmallVector<BinaryBasicBlock *, 4> &From,909 const SmallVector<SmallVector<BinaryBasicBlock *, 4>, 4> &To) {910 LLVM_DEBUG(dbgs() << "splitFrontierCritEdges: Now handling func "911 << BF.getPrintName() << "\n");912 // For every FromBB, there might be one or more critical edges, with913 // To[I] containing destination BBs. It's important to memorize914 // the original size of the Frontier as we may append to it while splitting915 // critical edges originating with blocks with multiple destinations.916 for (size_t I = 0, IE = Frontier.size(); I < IE; ++I) {917 if (!IsCritEdge[I])918 continue;919 if (To[I].empty())920 continue;921 BinaryBasicBlock *FromBB = From[I];922 LLVM_DEBUG(dbgs() << " - Now handling FrontierBB " << FromBB->getName()923 << "\n");924 // Split edge for every DestinationBBs925 for (size_t DI = 0, DIE = To[I].size(); DI < DIE; ++DI) {926 BinaryBasicBlock *DestinationBB = To[I][DI];927 LLVM_DEBUG(dbgs() << " - Dest : " << DestinationBB->getName() << "\n");928 BinaryBasicBlock *NewBB = Func->splitEdge(FromBB, DestinationBB);929 // Insert dummy instruction so this BB is never empty (we need this for930 // PredictiveStackPointerTracking to work, since it annotates instructions931 // and not BBs).932 if (NewBB->empty()) {933 MCInst NewInst;934 BC.MIB->createNoop(NewInst);935 NewBB->addInstruction(std::move(NewInst));936 scheduleChange(&*NewBB->begin(), WorklistItem(WorklistItem::Erase, 0));937 }938 939 // Update frontier940 ProgramPoint NewFrontierPP = ProgramPoint::getLastPointAt(*NewBB);941 if (DI == 0) {942 // Update frontier inplace943 Frontier[I] = NewFrontierPP;944 LLVM_DEBUG(dbgs() << " - Update frontier with " << NewBB->getName()945 << '\n');946 } else {947 // Append new frontier to the end of the list948 Frontier.push_back(NewFrontierPP);949 LLVM_DEBUG(dbgs() << " - Append frontier " << NewBB->getName()950 << '\n');951 }952 }953 }954}955 956SmallVector<ProgramPoint, 4>957ShrinkWrapping::doRestorePlacement(MCInst *BestPosSave, unsigned CSR,958 uint64_t TotalEstimatedWin) {959 SmallVector<ProgramPoint, 4> Frontier;960 SmallVector<bool, 4> IsCritEdge;961 DominatorAnalysis<false> &DA = Info.getDominatorAnalysis();962 963 SmallVector<BinaryBasicBlock *, 4> CritEdgesFrom;964 SmallVector<SmallVector<BinaryBasicBlock *, 4>, 4> CritEdgesTo;965 // In case of a critical edge, we need to create extra BBs to host restores966 // into edges transitioning to the dominance frontier, otherwise we pull these967 // restores to inside the dominated area.968 Frontier = DA.getDominanceFrontierFor(*BestPosSave).takeVector();969 LLVM_DEBUG({970 dbgs() << "Dumping dominance frontier for ";971 BC.printInstruction(dbgs(), *BestPosSave);972 for (ProgramPoint &PP : Frontier)973 if (PP.isInst())974 BC.printInstruction(dbgs(), *PP.getInst());975 else976 dbgs() << PP.getBB()->getName() << "\n";977 });978 for (ProgramPoint &PP : Frontier) {979 bool HasCritEdges = false;980 if (PP.isInst() && BC.MIB->isTerminator(*PP.getInst()) &&981 doesInstUsesCSR(*PP.getInst(), CSR)) {982 Frontier.clear();983 return Frontier;984 }985 BinaryBasicBlock *FrontierBB = Info.getParentBB(PP);986 CritEdgesFrom.emplace_back(FrontierBB);987 CritEdgesTo.emplace_back(0);988 SmallVector<BinaryBasicBlock *, 4> &Dests = CritEdgesTo.back();989 // Check for invoke instructions at the dominance frontier, which indicates990 // the landing pad is not dominated.991 if (PP.isInst() && BC.MIB->isInvoke(*PP.getInst())) {992 Frontier.clear();993 return Frontier;994 }995 doForAllSuccs(*FrontierBB, [&](ProgramPoint P) {996 if (!DA.doesADominateB(*BestPosSave, P)) {997 Dests.emplace_back(Info.getParentBB(P));998 return;999 }1000 HasCritEdges = true;1001 });1002 IsCritEdge.push_back(HasCritEdges);1003 }1004 // Restores cannot be placed in empty BBs because we have a dataflow1005 // analysis that depends on insertions happening before real instructions1006 // (PredictiveStackPointerTracking). Detect now for empty BBs and add a1007 // dummy nop that is scheduled to be removed later.1008 bool InvalidateRequired = false;1009 for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {1010 if (BB->size() != 0)1011 continue;1012 MCInst NewInst;1013 BC.MIB->createNoop(NewInst);1014 auto II = BB->addInstruction(std::move(NewInst));1015 scheduleChange(&*II, WorklistItem(WorklistItem::Erase, 0));1016 InvalidateRequired = true;1017 }1018 if (std::accumulate(IsCritEdge.begin(), IsCritEdge.end(), 0)) {1019 LLVM_DEBUG({1020 dbgs() << "Now detected critical edges in the following frontier:\n";1021 for (ProgramPoint &PP : Frontier) {1022 if (PP.isBB()) {1023 dbgs() << " BB: " << PP.getBB()->getName() << "\n";1024 } else {1025 dbgs() << " Inst: ";1026 PP.getInst()->dump();1027 }1028 }1029 });1030 splitFrontierCritEdges(&BF, Frontier, IsCritEdge, CritEdgesFrom,1031 CritEdgesTo);1032 InvalidateRequired = true;1033 }1034 if (InvalidateRequired) {1035 // BitVectors that represent all insns of the function are invalid now1036 // since we changed BBs/Insts. Re-run steps that depend on pointers being1037 // valid1038 Info.invalidateAll();1039 classifyCSRUses();1040 }1041 return Frontier;1042}1043 1044bool ShrinkWrapping::validatePushPopsMode(unsigned CSR, MCInst *BestPosSave,1045 int64_t SaveOffset) {1046 if (FA.requiresAlignment(BF)) {1047 LLVM_DEBUG({1048 dbgs() << "Reg " << CSR1049 << " is not using push/pops due to function "1050 "alignment requirements.\n";1051 });1052 return false;1053 }1054 if (FA.hasStackArithmetic(BF)) {1055 LLVM_DEBUG({1056 dbgs() << "Reg " << CSR1057 << " is not using push/pops due to function "1058 "taking the address of a stack position.\n";1059 });1060 return false;1061 }1062 for (MCInst *Save : CSA.getSavesByReg(CSR)) {1063 if (!SLM.canCollapseRegion(Save)) {1064 LLVM_DEBUG(dbgs() << "Reg " << CSR << " cannot collapse region.\n");1065 return false;1066 }1067 }1068 // Abort if one of the restores for this CSR is not a POP.1069 for (MCInst *Load : CSA.getRestoresByReg(CSR)) {1070 if (!BC.MIB->isPop(*Load)) {1071 LLVM_DEBUG(dbgs() << "Reg " << CSR << " has a mismatching restore.\n");1072 return false;1073 }1074 }1075 1076 StackPointerTracking &SPT = Info.getStackPointerTracking();1077 // Abort if we are inserting a push into an entry BB (offset -8) and this1078 // func sets up a frame pointer.1079 if (!SLM.canInsertRegion(BestPosSave) || SaveOffset == SPT.SUPERPOSITION ||1080 SaveOffset == SPT.EMPTY || (SaveOffset == -8 && SPT.HasFramePointer)) {1081 LLVM_DEBUG({1082 dbgs() << "Reg " << CSR1083 << " cannot insert region or we are "1084 "trying to insert a push into entry bb.\n";1085 });1086 return false;1087 }1088 return true;1089}1090 1091SmallVector<ProgramPoint, 4> ShrinkWrapping::fixPopsPlacements(1092 const SmallVector<ProgramPoint, 4> &RestorePoints, int64_t SaveOffset,1093 unsigned CSR) {1094 SmallVector<ProgramPoint, 4> FixedRestorePoints = RestorePoints;1095 // Moving pop locations to the correct sp offset1096 ReachingInsns<true> &RI = Info.getReachingInsnsBackwards();1097 StackPointerTracking &SPT = Info.getStackPointerTracking();1098 for (ProgramPoint &PP : FixedRestorePoints) {1099 BinaryBasicBlock *BB = Info.getParentBB(PP);1100 bool Found = false;1101 if (SPT.getStateAt(ProgramPoint::getLastPointAt(*BB))->first ==1102 SaveOffset) {1103 BitVector BV = *RI.getStateAt(ProgramPoint::getLastPointAt(*BB));1104 BV &= UsesByReg[CSR];1105 if (!BV.any()) {1106 Found = true;1107 PP = BB;1108 continue;1109 }1110 }1111 for (MCInst &Inst : llvm::reverse(*BB)) {1112 if (SPT.getStateBefore(Inst)->first == SaveOffset) {1113 BitVector BV = *RI.getStateAt(Inst);1114 BV &= UsesByReg[CSR];1115 if (!BV.any()) {1116 Found = true;1117 PP = &Inst;1118 break;1119 }1120 }1121 }1122 if (!Found) {1123 LLVM_DEBUG({1124 dbgs() << "Could not find restore insertion point for " << CSR1125 << ", falling back to load/store mode\n";1126 });1127 FixedRestorePoints.clear();1128 return FixedRestorePoints;1129 }1130 }1131 return FixedRestorePoints;1132}1133 1134void ShrinkWrapping::scheduleOldSaveRestoresRemoval(unsigned CSR,1135 bool UsePushPops) {1136 1137 for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {1138 std::vector<MCInst *> CFIs;1139 for (MCInst &Inst : llvm::reverse(*BB)) {1140 if (BC.MIB->isCFI(Inst)) {1141 // Delete all offset CFIs related to this CSR1142 if (SLM.getOffsetCFIReg(Inst) == CSR) {1143 HasDeletedOffsetCFIs[CSR] = true;1144 scheduleChange(&Inst, WorklistItem(WorklistItem::Erase, CSR));1145 continue;1146 }1147 CFIs.push_back(&Inst);1148 continue;1149 }1150 1151 uint16_t SavedReg = CSA.getSavedReg(Inst);1152 uint16_t RestoredReg = CSA.getRestoredReg(Inst);1153 if (SavedReg != CSR && RestoredReg != CSR) {1154 CFIs.clear();1155 continue;1156 }1157 1158 scheduleChange(&Inst, WorklistItem(UsePushPops1159 ? WorklistItem::Erase1160 : WorklistItem::ChangeToAdjustment,1161 CSR));1162 1163 // Delete associated CFIs1164 const bool RecordDeletedPushCFIs =1165 SavedReg == CSR && DeletedPushCFIs[CSR].empty();1166 const bool RecordDeletedPopCFIs =1167 RestoredReg == CSR && DeletedPopCFIs[CSR].empty();1168 for (MCInst *CFI : CFIs) {1169 const MCCFIInstruction *MCCFI = BF.getCFIFor(*CFI);1170 // Do not touch these...1171 if (MCCFI->getOperation() == MCCFIInstruction::OpRestoreState ||1172 MCCFI->getOperation() == MCCFIInstruction::OpRememberState)1173 continue;1174 scheduleChange(CFI, WorklistItem(WorklistItem::Erase, CSR));1175 if (RecordDeletedPushCFIs) {1176 // Do not record this to be replayed later because we are going to1177 // rebuild it.1178 if (MCCFI->getOperation() == MCCFIInstruction::OpDefCfaOffset)1179 continue;1180 DeletedPushCFIs[CSR].push_back(CFI->getOperand(0).getImm());1181 }1182 if (RecordDeletedPopCFIs) {1183 if (MCCFI->getOperation() == MCCFIInstruction::OpDefCfaOffset)1184 continue;1185 DeletedPopCFIs[CSR].push_back(CFI->getOperand(0).getImm());1186 }1187 }1188 CFIs.clear();1189 }1190 }1191}1192 1193bool ShrinkWrapping::doesInstUsesCSR(const MCInst &Inst, uint16_t CSR) {1194 if (BC.MIB->isCFI(Inst) || CSA.getSavedReg(Inst) == CSR ||1195 CSA.getRestoredReg(Inst) == CSR)1196 return false;1197 BitVector BV = BitVector(BC.MRI->getNumRegs(), false);1198 BC.MIB->getTouchedRegs(Inst, BV);1199 return BV[CSR];1200}1201 1202void ShrinkWrapping::scheduleSaveRestoreInsertions(1203 unsigned CSR, MCInst *BestPosSave,1204 SmallVector<ProgramPoint, 4> &RestorePoints, bool UsePushPops) {1205 auto &InsnToBB = Info.getInsnToBBMap();1206 const FrameIndexEntry *FIESave = CSA.SaveFIEByReg[CSR];1207 const FrameIndexEntry *FIELoad = CSA.LoadFIEByReg[CSR];1208 assert(FIESave && FIELoad && "Invalid CSR");1209 1210 LLVM_DEBUG({1211 dbgs() << "Scheduling save insertion at: ";1212 BestPosSave->dump();1213 });1214 1215 scheduleChange(BestPosSave,1216 UsePushPops ? WorklistItem::InsertPushOrPop1217 : WorklistItem::InsertLoadOrStore,1218 *FIESave, CSR);1219 1220 for (ProgramPoint &PP : RestorePoints) {1221 BinaryBasicBlock *FrontierBB = Info.getParentBB(PP);1222 LLVM_DEBUG({1223 dbgs() << "Scheduling restore insertion at: ";1224 if (PP.isInst())1225 PP.getInst()->dump();1226 else1227 dbgs() << PP.getBB()->getName() << "\n";1228 });1229 MCInst *Term =1230 FrontierBB->getTerminatorBefore(PP.isInst() ? PP.getInst() : nullptr);1231 if (Term)1232 PP = Term;1233 bool PrecededByPrefix = false;1234 if (PP.isInst()) {1235 auto Iter = FrontierBB->findInstruction(PP.getInst());1236 if (Iter != FrontierBB->end() && Iter != FrontierBB->begin()) {1237 --Iter;1238 PrecededByPrefix = BC.MIB->isPrefix(*Iter);1239 }1240 }1241 if (PP.isInst() &&1242 (doesInstUsesCSR(*PP.getInst(), CSR) || PrecededByPrefix)) {1243 assert(!InsnToBB[PP.getInst()]->hasTerminatorAfter(PP.getInst()) &&1244 "cannot move to end of bb");1245 scheduleChange(InsnToBB[PP.getInst()],1246 UsePushPops ? WorklistItem::InsertPushOrPop1247 : WorklistItem::InsertLoadOrStore,1248 *FIELoad, CSR);1249 continue;1250 }1251 scheduleChange(PP,1252 UsePushPops ? WorklistItem::InsertPushOrPop1253 : WorklistItem::InsertLoadOrStore,1254 *FIELoad, CSR);1255 }1256}1257 1258void ShrinkWrapping::moveSaveRestores() {1259 bool DisablePushPopMode = false;1260 bool UsedPushPopMode = false;1261 // Keeps info about successfully moved regs: reg index, save position and1262 // save size1263 std::vector<std::tuple<unsigned, MCInst *, size_t>> MovedRegs;1264 uint64_t TotalEstimatedWin = 0;1265 1266 computeDomOrder();1267 for (unsigned I = 0, E = BC.MRI->getNumRegs(); I != E; ++I) {1268 MCInst *BestPosSave = nullptr;1269 uint64_t EstimatedWin = 0;1270 SmallVector<ProgramPoint, 4> RestorePoints;1271 while (RestorePoints.empty() &&1272 isBestSavePosCold(I, BestPosSave, EstimatedWin)) {1273 RestorePoints = doRestorePlacement(BestPosSave, I, EstimatedWin);1274 if (RestorePoints.empty()) {1275 LLVM_DEBUG({1276 dbgs() << "Dropping opportunity because restore placement failed"1277 " -- total est. freq reduc: "1278 << EstimatedWin << ". Will try "1279 << (BestSaveCount[I].size() - 1) << " more times.\n";1280 });1281 BestSaveCount[I].pop_back();1282 BestSavePos[I].pop_back();1283 computeDomOrder();1284 }1285 }1286 if (RestorePoints.empty()) {1287 SpillsFailedDynamicCount += EstimatedWin;1288 continue;1289 }1290 1291 const FrameIndexEntry *FIESave = CSA.SaveFIEByReg[I];1292 const FrameIndexEntry *FIELoad = CSA.LoadFIEByReg[I];1293 (void)FIELoad;1294 assert(FIESave && FIELoad);1295 StackPointerTracking &SPT = Info.getStackPointerTracking();1296 const std::pair<int, int> SPFP = *SPT.getStateBefore(*BestPosSave);1297 int SaveOffset = SPFP.first;1298 uint8_t SaveSize = FIESave->Size;1299 1300 // If we don't know stack state at this point, bail1301 if ((SPFP.first == SPT.SUPERPOSITION || SPFP.first == SPT.EMPTY) &&1302 (SPFP.second == SPT.SUPERPOSITION || SPFP.second == SPT.EMPTY)) {1303 SpillsFailedDynamicCount += EstimatedWin;1304 continue;1305 }1306 1307 // Operation mode: if true, will insert push/pops instead of loads/restores1308 bool UsePushPops = validatePushPopsMode(I, BestPosSave, SaveOffset);1309 1310 if (UsePushPops) {1311 SmallVector<ProgramPoint, 4> FixedRestorePoints =1312 fixPopsPlacements(RestorePoints, SaveOffset, I);1313 if (FixedRestorePoints.empty())1314 UsePushPops = false;1315 else1316 RestorePoints = FixedRestorePoints;1317 }1318 1319 // Disable push-pop mode for all CSRs in this function1320 if (!UsePushPops)1321 DisablePushPopMode = true;1322 else1323 UsedPushPopMode = true;1324 1325 scheduleOldSaveRestoresRemoval(I, UsePushPops);1326 scheduleSaveRestoreInsertions(I, BestPosSave, RestorePoints, UsePushPops);1327 MovedRegs.emplace_back(std::make_tuple(I, BestPosSave, SaveSize));1328 TotalEstimatedWin += EstimatedWin;1329 }1330 1331 // Revert push-pop mode if it failed for a single CSR1332 if (DisablePushPopMode && UsedPushPopMode) {1333 UsedPushPopMode = false;1334 for (BinaryBasicBlock &BB : BF) {1335 auto WRI = Todo.find(&BB);1336 if (WRI != Todo.end()) {1337 std::vector<WorklistItem> &TodoList = WRI->second;1338 for (WorklistItem &Item : TodoList)1339 if (Item.Action == WorklistItem::InsertPushOrPop)1340 Item.Action = WorklistItem::InsertLoadOrStore;1341 }1342 for (MCInst &Inst : llvm::reverse(BB)) {1343 auto TodoList = BC.MIB->tryGetAnnotationAs<std::vector<WorklistItem>>(1344 Inst, getAnnotationIndex());1345 if (!TodoList)1346 continue;1347 bool isCFI = BC.MIB->isCFI(Inst);1348 for (WorklistItem &Item : *TodoList) {1349 if (Item.Action == WorklistItem::InsertPushOrPop)1350 Item.Action = WorklistItem::InsertLoadOrStore;1351 if (!isCFI && Item.Action == WorklistItem::Erase)1352 Item.Action = WorklistItem::ChangeToAdjustment;1353 }1354 }1355 }1356 }1357 SpillsMovedDynamicCount += TotalEstimatedWin;1358 1359 // Update statistics1360 if (!UsedPushPopMode) {1361 SpillsMovedRegularMode += MovedRegs.size();1362 return;1363 }1364 1365 // Schedule modifications to stack-accessing instructions via1366 // StackLayoutModifier.1367 SpillsMovedPushPopMode += MovedRegs.size();1368 for (std::tuple<unsigned, MCInst *, size_t> &I : MovedRegs) {1369 unsigned RegNdx;1370 MCInst *SavePos;1371 size_t SaveSize;1372 std::tie(RegNdx, SavePos, SaveSize) = I;1373 for (MCInst *Save : CSA.getSavesByReg(RegNdx))1374 SLM.collapseRegion(Save);1375 SLM.insertRegion(SavePos, SaveSize);1376 }1377}1378 1379namespace {1380/// Helper function to identify whether two basic blocks created by splitting1381/// a critical edge have the same contents.1382bool isIdenticalSplitEdgeBB(const BinaryContext &BC, const BinaryBasicBlock &A,1383 const BinaryBasicBlock &B) {1384 if (A.succ_size() != B.succ_size())1385 return false;1386 if (A.succ_size() != 1)1387 return false;1388 1389 if (*A.succ_begin() != *B.succ_begin())1390 return false;1391 1392 if (A.size() != B.size())1393 return false;1394 1395 // Compare instructions1396 auto I = A.begin(), E = A.end();1397 auto OtherI = B.begin(), OtherE = B.end();1398 while (I != E && OtherI != OtherE) {1399 if (I->getOpcode() != OtherI->getOpcode())1400 return false;1401 if (!BC.MIB->equals(*I, *OtherI, [](const MCSymbol *A, const MCSymbol *B) {1402 return true;1403 }))1404 return false;1405 ++I;1406 ++OtherI;1407 }1408 return true;1409}1410} // namespace1411 1412bool ShrinkWrapping::foldIdenticalSplitEdges() {1413 bool Changed = false;1414 for (auto Iter = BF.begin(); Iter != BF.end(); ++Iter) {1415 BinaryBasicBlock &BB = *Iter;1416 if (!BB.getName().starts_with(".LSplitEdge"))1417 continue;1418 for (BinaryBasicBlock &RBB : llvm::reverse(BF)) {1419 if (&RBB == &BB)1420 break;1421 if (!RBB.getName().starts_with(".LSplitEdge") || !RBB.isValid() ||1422 !isIdenticalSplitEdgeBB(BC, *Iter, RBB))1423 continue;1424 assert(RBB.pred_size() == 1 && "Invalid split edge BB");1425 BinaryBasicBlock *Pred = *RBB.pred_begin();1426 uint64_t OrigCount = Pred->branch_info_begin()->Count;1427 uint64_t OrigMispreds = Pred->branch_info_begin()->MispredictedCount;1428 BF.replaceJumpTableEntryIn(Pred, &RBB, &BB);1429 Pred->replaceSuccessor(&RBB, &BB, OrigCount, OrigMispreds);1430 Changed = true;1431 // Remove the block from CFG1432 RBB.markValid(false);1433 }1434 }1435 1436 return Changed;1437}1438 1439namespace {1440 1441// A special StackPointerTracking that compensates for our future plans1442// in removing/adding insn.1443class PredictiveStackPointerTracking1444 : public StackPointerTrackingBase<PredictiveStackPointerTracking> {1445 friend class DataflowAnalysis<PredictiveStackPointerTracking,1446 std::pair<int, int>>;1447 decltype(ShrinkWrapping::Todo) &TodoMap;1448 DataflowInfoManager &Info;1449 1450 std::optional<unsigned> AnnotationIndex;1451 1452protected:1453 void compNextAux(const MCInst &Point,1454 const std::vector<ShrinkWrapping::WorklistItem> &TodoItems,1455 std::pair<int, int> &Res) {1456 for (const ShrinkWrapping::WorklistItem &Item : TodoItems) {1457 if (Item.Action == ShrinkWrapping::WorklistItem::Erase &&1458 BC.MIB->isPush(Point)) {1459 Res.first += BC.MIB->getPushSize(Point);1460 continue;1461 }1462 if (Item.Action == ShrinkWrapping::WorklistItem::Erase &&1463 BC.MIB->isPop(Point)) {1464 Res.first -= BC.MIB->getPopSize(Point);1465 continue;1466 }1467 if (Item.Action == ShrinkWrapping::WorklistItem::InsertPushOrPop &&1468 Item.FIEToInsert.IsStore) {1469 Res.first -= Item.FIEToInsert.Size;1470 continue;1471 }1472 if (Item.Action == ShrinkWrapping::WorklistItem::InsertPushOrPop &&1473 Item.FIEToInsert.IsLoad) {1474 Res.first += Item.FIEToInsert.Size;1475 continue;1476 }1477 }1478 }1479 1480 std::pair<int, int> computeNext(const MCInst &Point,1481 const std::pair<int, int> &Cur) {1482 std::pair<int, int> Res =1483 StackPointerTrackingBase<PredictiveStackPointerTracking>::computeNext(1484 Point, Cur);1485 if (Res.first == StackPointerTracking::SUPERPOSITION ||1486 Res.first == StackPointerTracking::EMPTY)1487 return Res;1488 auto TodoItems =1489 BC.MIB->tryGetAnnotationAs<std::vector<ShrinkWrapping::WorklistItem>>(1490 Point, ShrinkWrapping::getAnnotationName());1491 if (TodoItems)1492 compNextAux(Point, *TodoItems, Res);1493 auto &InsnToBBMap = Info.getInsnToBBMap();1494 if (&*InsnToBBMap[&Point]->rbegin() != &Point)1495 return Res;1496 auto WRI = TodoMap.find(InsnToBBMap[&Point]);1497 if (WRI == TodoMap.end())1498 return Res;1499 compNextAux(Point, WRI->second, Res);1500 return Res;1501 }1502 1503 StringRef getAnnotationName() const {1504 return StringRef("PredictiveStackPointerTracking");1505 }1506 1507public:1508 PredictiveStackPointerTracking(BinaryFunction &BF,1509 decltype(ShrinkWrapping::Todo) &TodoMap,1510 DataflowInfoManager &Info,1511 MCPlusBuilder::AllocatorIdTy AllocatorId = 0)1512 : StackPointerTrackingBase<PredictiveStackPointerTracking>(BF,1513 AllocatorId),1514 TodoMap(TodoMap), Info(Info) {}1515 1516 void run() {1517 StackPointerTrackingBase<PredictiveStackPointerTracking>::run();1518 }1519};1520 1521} // end anonymous namespace1522 1523void ShrinkWrapping::insertUpdatedCFI(unsigned CSR, int SPValPush,1524 int SPValPop) {1525 MCInst *SavePoint = nullptr;1526 for (BinaryBasicBlock &BB : BF) {1527 for (MCInst &Inst : llvm::reverse(BB)) {1528 int32_t SrcImm = 0;1529 MCPhysReg Reg = 0;1530 MCPhysReg StackPtrReg = 0;1531 int64_t StackOffset = 0;1532 bool IsIndexed = false;1533 bool IsLoad = false;1534 bool IsStore = false;1535 bool IsSimple = false;1536 bool IsStoreFromReg = false;1537 uint8_t Size = 0;1538 if (!BC.MIB->isStackAccess(Inst, IsLoad, IsStore, IsStoreFromReg, Reg,1539 SrcImm, StackPtrReg, StackOffset, Size,1540 IsSimple, IsIndexed))1541 continue;1542 if (Reg != CSR || !IsStore || !IsSimple)1543 continue;1544 SavePoint = &Inst;1545 break;1546 }1547 if (SavePoint)1548 break;1549 }1550 assert(SavePoint);1551 LLVM_DEBUG({1552 dbgs() << "Now using as save point for reg " << CSR << " :";1553 SavePoint->dump();1554 });1555 bool PrevAffectedZone = false;1556 BinaryBasicBlock *PrevBB = nullptr;1557 DominatorAnalysis<false> &DA = Info.getDominatorAnalysis();1558 for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {1559 if (BB->size() == 0)1560 continue;1561 const bool InAffectedZoneAtEnd = DA.count(*BB->rbegin(), *SavePoint);1562 const bool InAffectedZoneAtBegin =1563 (*DA.getStateBefore(*BB->begin()))[DA.ExprToIdx[SavePoint]];1564 bool InAffectedZone = InAffectedZoneAtBegin;1565 for (auto InstIter = BB->begin(); InstIter != BB->end(); ++InstIter) {1566 const bool CurZone = DA.count(*InstIter, *SavePoint);1567 if (InAffectedZone != CurZone) {1568 auto InsertionIter = InstIter;1569 ++InsertionIter;1570 InAffectedZone = CurZone;1571 if (InAffectedZone)1572 InstIter = insertCFIsForPushOrPop(*BB, InsertionIter, CSR, true, 0,1573 SPValPop);1574 else1575 InstIter = insertCFIsForPushOrPop(*BB, InsertionIter, CSR, false, 0,1576 SPValPush);1577 --InstIter;1578 }1579 }1580 // Are we at the first basic block or hot-cold split point?1581 if (!PrevBB || (BF.isSplit() && BB->isCold() != PrevBB->isCold())) {1582 if (InAffectedZoneAtBegin)1583 insertCFIsForPushOrPop(*BB, BB->begin(), CSR, true, 0, SPValPush);1584 } else if (InAffectedZoneAtBegin != PrevAffectedZone) {1585 if (InAffectedZoneAtBegin)1586 insertCFIsForPushOrPop(*PrevBB, PrevBB->end(), CSR, true, 0, SPValPush);1587 else1588 insertCFIsForPushOrPop(*PrevBB, PrevBB->end(), CSR, false, 0, SPValPop);1589 }1590 PrevAffectedZone = InAffectedZoneAtEnd;1591 PrevBB = BB;1592 }1593}1594 1595void ShrinkWrapping::rebuildCFIForSP() {1596 for (BinaryBasicBlock &BB : BF) {1597 for (MCInst &Inst : BB) {1598 if (!BC.MIB->isCFI(Inst))1599 continue;1600 const MCCFIInstruction *CFI = BF.getCFIFor(Inst);1601 if (CFI->getOperation() == MCCFIInstruction::OpDefCfaOffset)1602 BC.MIB->addAnnotation(Inst, "DeleteMe", 0U, AllocatorId);1603 }1604 }1605 1606 int PrevSPVal = -8;1607 BinaryBasicBlock *PrevBB = nullptr;1608 StackPointerTracking &SPT = Info.getStackPointerTracking();1609 for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {1610 if (BB->size() == 0)1611 continue;1612 const int SPValAtEnd = SPT.getStateAt(*BB->rbegin())->first;1613 const int SPValAtBegin = SPT.getStateBefore(*BB->begin())->first;1614 int SPVal = SPValAtBegin;1615 for (auto Iter = BB->begin(); Iter != BB->end(); ++Iter) {1616 const int CurVal = SPT.getStateAt(*Iter)->first;1617 if (SPVal != CurVal) {1618 auto InsertionIter = Iter;1619 ++InsertionIter;1620 Iter = BF.addCFIInstruction(1621 BB, InsertionIter,1622 MCCFIInstruction::cfiDefCfaOffset(nullptr, -CurVal));1623 SPVal = CurVal;1624 }1625 }1626 if (BF.isSplit() && PrevBB && BB->isCold() != PrevBB->isCold())1627 BF.addCFIInstruction(1628 BB, BB->begin(),1629 MCCFIInstruction::cfiDefCfaOffset(nullptr, -SPValAtBegin));1630 else if (SPValAtBegin != PrevSPVal)1631 BF.addCFIInstruction(1632 PrevBB, PrevBB->end(),1633 MCCFIInstruction::cfiDefCfaOffset(nullptr, -SPValAtBegin));1634 PrevSPVal = SPValAtEnd;1635 PrevBB = BB;1636 }1637 1638 for (BinaryBasicBlock &BB : BF)1639 for (auto I = BB.begin(); I != BB.end();)1640 if (BC.MIB->hasAnnotation(*I, "DeleteMe"))1641 I = BB.eraseInstruction(I);1642 else1643 ++I;1644}1645 1646Expected<MCInst> ShrinkWrapping::createStackAccess(int SPVal, int FPVal,1647 const FrameIndexEntry &FIE,1648 bool CreatePushOrPop) {1649 MCInst NewInst;1650 if (SPVal != StackPointerTracking::SUPERPOSITION &&1651 SPVal != StackPointerTracking::EMPTY) {1652 if (FIE.IsLoad) {1653 BC.MIB->createRestoreFromStack(NewInst, BC.MIB->getStackPointer(),1654 FIE.StackOffset - SPVal, FIE.RegOrImm,1655 FIE.Size);1656 } else {1657 BC.MIB->createSaveToStack(NewInst, BC.MIB->getStackPointer(),1658 FIE.StackOffset - SPVal, FIE.RegOrImm,1659 FIE.Size);1660 }1661 if (CreatePushOrPop)1662 BC.MIB->changeToPushOrPop(NewInst);1663 return NewInst;1664 }1665 assert(FPVal != StackPointerTracking::SUPERPOSITION &&1666 FPVal != StackPointerTracking::EMPTY);1667 1668 if (FIE.IsLoad) {1669 BC.MIB->createRestoreFromStack(NewInst, BC.MIB->getFramePointer(),1670 FIE.StackOffset - FPVal, FIE.RegOrImm,1671 FIE.Size);1672 } else {1673 BC.MIB->createSaveToStack(NewInst, BC.MIB->getFramePointer(),1674 FIE.StackOffset - FPVal, FIE.RegOrImm, FIE.Size);1675 }1676 return NewInst;1677}1678 1679void ShrinkWrapping::updateCFIInstOffset(MCInst &Inst, int64_t NewOffset) {1680 const MCCFIInstruction *CFI = BF.getCFIFor(Inst);1681 if (UpdatedCFIs.count(CFI))1682 return;1683 1684 switch (CFI->getOperation()) {1685 case MCCFIInstruction::OpDefCfa:1686 case MCCFIInstruction::OpDefCfaRegister:1687 case MCCFIInstruction::OpDefCfaOffset:1688 CFI = BF.mutateCFIOffsetFor(Inst, -NewOffset);1689 break;1690 case MCCFIInstruction::OpOffset:1691 default:1692 break;1693 }1694 1695 UpdatedCFIs.insert(CFI);1696}1697 1698BBIterTy ShrinkWrapping::insertCFIsForPushOrPop(BinaryBasicBlock &BB,1699 BBIterTy Pos, unsigned Reg,1700 bool isPush, int Sz,1701 int64_t NewOffset) {1702 if (isPush) {1703 for (uint32_t Idx : DeletedPushCFIs[Reg]) {1704 Pos = BF.addCFIPseudo(&BB, Pos, Idx);1705 updateCFIInstOffset(*Pos++, NewOffset);1706 }1707 if (HasDeletedOffsetCFIs[Reg]) {1708 Pos = BF.addCFIInstruction(1709 &BB, Pos,1710 MCCFIInstruction::createOffset(1711 nullptr, BC.MRI->getDwarfRegNum(Reg, false), NewOffset));1712 ++Pos;1713 }1714 } else {1715 for (uint32_t Idx : DeletedPopCFIs[Reg]) {1716 Pos = BF.addCFIPseudo(&BB, Pos, Idx);1717 updateCFIInstOffset(*Pos++, NewOffset);1718 }1719 if (HasDeletedOffsetCFIs[Reg]) {1720 Pos = BF.addCFIInstruction(1721 &BB, Pos,1722 MCCFIInstruction::createSameValue(1723 nullptr, BC.MRI->getDwarfRegNum(Reg, false)));1724 ++Pos;1725 }1726 }1727 return Pos;1728}1729 1730Expected<BBIterTy> ShrinkWrapping::processInsertion(BBIterTy InsertionPoint,1731 BinaryBasicBlock *CurBB,1732 const WorklistItem &Item,1733 int64_t SPVal,1734 int64_t FPVal) {1735 // Trigger CFI reconstruction for this CSR if necessary - writing to1736 // PushOffsetByReg/PopOffsetByReg *will* trigger CFI update1737 if ((Item.FIEToInsert.IsStore &&1738 !DeletedPushCFIs[Item.AffectedReg].empty()) ||1739 (Item.FIEToInsert.IsLoad && !DeletedPopCFIs[Item.AffectedReg].empty()) ||1740 HasDeletedOffsetCFIs[Item.AffectedReg]) {1741 if (Item.Action == WorklistItem::InsertPushOrPop) {1742 if (Item.FIEToInsert.IsStore)1743 PushOffsetByReg[Item.AffectedReg] = SPVal - Item.FIEToInsert.Size;1744 else1745 PopOffsetByReg[Item.AffectedReg] = SPVal;1746 } else {1747 if (Item.FIEToInsert.IsStore)1748 PushOffsetByReg[Item.AffectedReg] = Item.FIEToInsert.StackOffset;1749 else1750 PopOffsetByReg[Item.AffectedReg] = Item.FIEToInsert.StackOffset;1751 }1752 }1753 1754 LLVM_DEBUG({1755 dbgs() << "Creating stack access with SPVal = " << SPVal1756 << "; stack offset = " << Item.FIEToInsert.StackOffset1757 << " Is push = " << (Item.Action == WorklistItem::InsertPushOrPop)1758 << "\n";1759 });1760 Expected<MCInst> NewInstOrErr =1761 createStackAccess(SPVal, FPVal, Item.FIEToInsert,1762 Item.Action == WorklistItem::InsertPushOrPop);1763 if (auto E = NewInstOrErr.takeError())1764 return Error(std::move(E));1765 MCInst &NewInst = *NewInstOrErr;1766 if (InsertionPoint != CurBB->end()) {1767 LLVM_DEBUG({1768 dbgs() << "Adding before Inst: ";1769 InsertionPoint->dump();1770 dbgs() << "the following inst: ";1771 NewInst.dump();1772 });1773 BBIterTy Iter =1774 CurBB->insertInstruction(InsertionPoint, std::move(NewInst));1775 return ++Iter;1776 }1777 CurBB->addInstruction(std::move(NewInst));1778 LLVM_DEBUG(dbgs() << "Adding to BB!\n");1779 return CurBB->end();1780}1781 1782Expected<BBIterTy> ShrinkWrapping::processInsertionsList(1783 BBIterTy InsertionPoint, BinaryBasicBlock *CurBB,1784 std::vector<WorklistItem> &TodoList, int64_t SPVal, int64_t FPVal) {1785 bool HasInsertions = llvm::any_of(TodoList, [&](WorklistItem &Item) {1786 return Item.Action == WorklistItem::InsertLoadOrStore ||1787 Item.Action == WorklistItem::InsertPushOrPop;1788 });1789 1790 if (!HasInsertions)1791 return InsertionPoint;1792 1793 assert(((SPVal != StackPointerTracking::SUPERPOSITION &&1794 SPVal != StackPointerTracking::EMPTY) ||1795 (FPVal != StackPointerTracking::SUPERPOSITION &&1796 FPVal != StackPointerTracking::EMPTY)) &&1797 "Cannot insert if we have no idea of the stack state here");1798 1799 // Revert the effect of PSPT for this location, we want SP Value before1800 // insertions1801 if (InsertionPoint == CurBB->end()) {1802 for (WorklistItem &Item : TodoList) {1803 if (Item.Action != WorklistItem::InsertPushOrPop)1804 continue;1805 if (Item.FIEToInsert.IsStore)1806 SPVal += Item.FIEToInsert.Size;1807 if (Item.FIEToInsert.IsLoad)1808 SPVal -= Item.FIEToInsert.Size;1809 }1810 }1811 1812 // Reorder POPs to obey the correct dominance relation between them1813 llvm::stable_sort(TodoList, [&](const WorklistItem &A,1814 const WorklistItem &B) {1815 if ((A.Action != WorklistItem::InsertPushOrPop || !A.FIEToInsert.IsLoad) &&1816 (B.Action != WorklistItem::InsertPushOrPop || !B.FIEToInsert.IsLoad))1817 return false;1818 if ((A.Action != WorklistItem::InsertPushOrPop || !A.FIEToInsert.IsLoad))1819 return true;1820 if ((B.Action != WorklistItem::InsertPushOrPop || !B.FIEToInsert.IsLoad))1821 return false;1822 return DomOrder[B.AffectedReg] < DomOrder[A.AffectedReg];1823 });1824 1825 // Process insertions1826 for (WorklistItem &Item : TodoList) {1827 if (Item.Action == WorklistItem::Erase ||1828 Item.Action == WorklistItem::ChangeToAdjustment)1829 continue;1830 1831 auto InsertionPointOrErr =1832 processInsertion(InsertionPoint, CurBB, Item, SPVal, FPVal);1833 if (auto E = InsertionPointOrErr.takeError())1834 return Error(std::move(E));1835 InsertionPoint = *InsertionPointOrErr;1836 if (Item.Action == WorklistItem::InsertPushOrPop &&1837 Item.FIEToInsert.IsStore)1838 SPVal -= Item.FIEToInsert.Size;1839 if (Item.Action == WorklistItem::InsertPushOrPop &&1840 Item.FIEToInsert.IsLoad)1841 SPVal += Item.FIEToInsert.Size;1842 }1843 return InsertionPoint;1844}1845 1846Expected<bool> ShrinkWrapping::processInsertions() {1847 PredictiveStackPointerTracking PSPT(BF, Todo, Info, AllocatorId);1848 PSPT.run();1849 1850 bool Changes = false;1851 for (BinaryBasicBlock &BB : BF) {1852 // Process insertions before some inst.1853 for (auto I = BB.begin(); I != BB.end(); ++I) {1854 MCInst &Inst = *I;1855 auto TodoList = BC.MIB->tryGetAnnotationAs<std::vector<WorklistItem>>(1856 Inst, getAnnotationIndex());1857 if (!TodoList)1858 continue;1859 Changes = true;1860 std::vector<WorklistItem> List = *TodoList;1861 LLVM_DEBUG({1862 dbgs() << "Now processing insertions in " << BB.getName()1863 << " before inst: ";1864 Inst.dump();1865 });1866 auto Iter = I;1867 std::pair<int, int> SPTState =1868 *PSPT.getStateAt(Iter == BB.begin() ? (ProgramPoint)&BB : &*(--Iter));1869 auto IterOrErr =1870 processInsertionsList(I, &BB, List, SPTState.first, SPTState.second);1871 if (auto E = IterOrErr.takeError())1872 return Error(std::move(E));1873 I = *IterOrErr;1874 }1875 // Process insertions at the end of bb1876 auto WRI = Todo.find(&BB);1877 if (WRI != Todo.end()) {1878 std::pair<int, int> SPTState = *PSPT.getStateAt(*BB.rbegin());1879 if (auto E = processInsertionsList(BB.end(), &BB, WRI->second,1880 SPTState.first, SPTState.second)1881 .takeError())1882 return Error(std::move(E));1883 Changes = true;1884 }1885 }1886 return Changes;1887}1888 1889void ShrinkWrapping::processDeletions() {1890 LivenessAnalysis &LA = Info.getLivenessAnalysis();1891 for (BinaryBasicBlock &BB : BF) {1892 for (auto II = BB.begin(); II != BB.end(); ++II) {1893 MCInst &Inst = *II;1894 auto TodoList = BC.MIB->tryGetAnnotationAs<std::vector<WorklistItem>>(1895 Inst, getAnnotationIndex());1896 if (!TodoList)1897 continue;1898 // Process all deletions1899 for (WorklistItem &Item : *TodoList) {1900 if (Item.Action != WorklistItem::Erase &&1901 Item.Action != WorklistItem::ChangeToAdjustment)1902 continue;1903 1904 if (Item.Action == WorklistItem::ChangeToAdjustment) {1905 // Is flag reg alive across this func?1906 bool DontClobberFlags = LA.isAlive(&Inst, BC.MIB->getFlagsReg());1907 if (int Sz = BC.MIB->getPushSize(Inst)) {1908 BC.MIB->createStackPointerIncrement(Inst, Sz, DontClobberFlags);1909 continue;1910 }1911 if (int Sz = BC.MIB->getPopSize(Inst)) {1912 BC.MIB->createStackPointerDecrement(Inst, Sz, DontClobberFlags);1913 continue;1914 }1915 }1916 1917 LLVM_DEBUG({1918 dbgs() << "Erasing: ";1919 BC.printInstruction(dbgs(), Inst);1920 });1921 II = std::prev(BB.eraseInstruction(II));1922 break;1923 }1924 }1925 }1926}1927 1928void ShrinkWrapping::rebuildCFI() {1929 const bool FP = Info.getStackPointerTracking().HasFramePointer;1930 Info.invalidateAll();1931 if (!FP) {1932 rebuildCFIForSP();1933 Info.invalidateAll();1934 }1935 for (unsigned I = 0, E = BC.MRI->getNumRegs(); I != E; ++I) {1936 if (PushOffsetByReg[I] == 0 || PopOffsetByReg[I] == 0)1937 continue;1938 const int64_t SPValPush = PushOffsetByReg[I];1939 const int64_t SPValPop = PopOffsetByReg[I];1940 insertUpdatedCFI(I, SPValPush, SPValPop);1941 Info.invalidateAll();1942 }1943}1944 1945Expected<bool> ShrinkWrapping::perform(bool HotOnly) {1946 HasDeletedOffsetCFIs = BitVector(BC.MRI->getNumRegs(), false);1947 PushOffsetByReg = std::vector<int64_t>(BC.MRI->getNumRegs(), 0LL);1948 PopOffsetByReg = std::vector<int64_t>(BC.MRI->getNumRegs(), 0LL);1949 1950 // Update pass statistics1951 uint64_t TotalInstrs = 0ULL;1952 uint64_t TotalStoreInstrs = 0ULL;1953 for (BinaryBasicBlock *BB : BF.getLayout().blocks()) {1954 uint64_t BBExecCount = BB->getExecutionCount();1955 if (!BBExecCount || BBExecCount == BinaryBasicBlock::COUNT_NO_PROFILE)1956 continue;1957 for (const auto &Instr : *BB) {1958 if (BC.MIB->isPseudo(Instr))1959 continue;1960 if (BC.MIB->mayStore(Instr))1961 TotalStoreInstrs += BBExecCount;1962 TotalInstrs += BBExecCount;1963 }1964 }1965 InstrDynamicCount += TotalInstrs;1966 StoreDynamicCount += TotalStoreInstrs;1967 1968 if (!FA.hasFrameInfo(BF))1969 return false;1970 1971 if (HotOnly && (BF.getKnownExecutionCount() < BC.getHotThreshold()))1972 return false;1973 1974 if (opts::EqualizeBBCounts)1975 equalizeBBCounts(Info, BF);1976 1977 if (BF.checkForAmbiguousJumpTables()) {1978 LLVM_DEBUG(dbgs() << "BOLT-DEBUG: ambiguous JTs in " << BF.getPrintName()1979 << ".\n");1980 // We could call disambiguateJumpTables here, but it is probably not worth1981 // the cost (of duplicating potentially large jump tables that could regress1982 // dcache misses). Moreover, ambiguous JTs are rare and coming from code1983 // written in assembly language. Just bail.1984 return false;1985 }1986 SLM.initialize();1987 CSA.compute();1988 classifyCSRUses();1989 pruneUnwantedCSRs();1990 computeSaveLocations();1991 moveSaveRestores();1992 LLVM_DEBUG({1993 dbgs() << "Func before shrink-wrapping: \n";1994 BF.dump();1995 });1996 SLM.performChanges();1997 // Early exit if processInsertions doesn't detect any todo items1998 auto ModifiedOrErr = processInsertions();1999 if (auto E = ModifiedOrErr.takeError())2000 return Error(std::move(E));2001 const bool Modified = *ModifiedOrErr;2002 if (!Modified)2003 return false;2004 processDeletions();2005 if (foldIdenticalSplitEdges()) {2006 const std::pair<unsigned, uint64_t> Stats = BF.eraseInvalidBBs();2007 (void)Stats;2008 LLVM_DEBUG(dbgs() << "Deleted " << Stats.first2009 << " redundant split edge BBs (" << Stats.second2010 << " bytes) for " << BF.getPrintName() << "\n");2011 }2012 rebuildCFI();2013 // We may have split edges, creating BBs that need correct branching2014 BF.fixBranches();2015 LLVM_DEBUG({2016 dbgs() << "Func after shrink-wrapping: \n";2017 BF.dump();2018 });2019 return true;2020}2021 2022void ShrinkWrapping::printStats(BinaryContext &BC) {2023 BC.outs() << "BOLT-INFO: Shrink wrapping moved " << SpillsMovedRegularMode2024 << " spills inserting load/stores and " << SpillsMovedPushPopMode2025 << " spills inserting push/pops\n";2026 if (!InstrDynamicCount || !StoreDynamicCount)2027 return;2028 BC.outs() << "BOLT-INFO: Shrink wrapping reduced " << SpillsMovedDynamicCount2029 << " store executions ("2030 << format("%.1lf%%",2031 (100.0 * SpillsMovedDynamicCount / InstrDynamicCount))2032 << " total instructions executed, "2033 << format("%.1lf%%",2034 (100.0 * SpillsMovedDynamicCount / StoreDynamicCount))2035 << " store instructions)\n";2036 BC.outs() << "BOLT-INFO: Shrink wrapping failed at reducing "2037 << SpillsFailedDynamicCount << " store executions ("2038 << format("%.1lf%%",2039 (100.0 * SpillsFailedDynamicCount / InstrDynamicCount))2040 << " total instructions executed, "2041 << format("%.1lf%%",2042 (100.0 * SpillsFailedDynamicCount / StoreDynamicCount))2043 << " store instructions)\n";2044}2045 2046// Operators necessary as a result of using MCAnnotation2047raw_ostream &operator<<(raw_ostream &OS,2048 const std::vector<ShrinkWrapping::WorklistItem> &Vec) {2049 OS << "SWTodo[";2050 const char *Sep = "";2051 for (const ShrinkWrapping::WorklistItem &Item : Vec) {2052 OS << Sep;2053 switch (Item.Action) {2054 case ShrinkWrapping::WorklistItem::Erase:2055 OS << "Erase";2056 break;2057 case ShrinkWrapping::WorklistItem::ChangeToAdjustment:2058 OS << "ChangeToAdjustment";2059 break;2060 case ShrinkWrapping::WorklistItem::InsertLoadOrStore:2061 OS << "InsertLoadOrStore";2062 break;2063 case ShrinkWrapping::WorklistItem::InsertPushOrPop:2064 OS << "InsertPushOrPop";2065 break;2066 }2067 Sep = ", ";2068 }2069 OS << "]";2070 return OS;2071}2072 2073raw_ostream &2074operator<<(raw_ostream &OS,2075 const std::vector<StackLayoutModifier::WorklistItem> &Vec) {2076 OS << "SLMTodo[";2077 const char *Sep = "";2078 for (const StackLayoutModifier::WorklistItem &Item : Vec) {2079 OS << Sep;2080 switch (Item.Action) {2081 case StackLayoutModifier::WorklistItem::None:2082 OS << "None";2083 break;2084 case StackLayoutModifier::WorklistItem::AdjustLoadStoreOffset:2085 OS << "AdjustLoadStoreOffset";2086 break;2087 case StackLayoutModifier::WorklistItem::AdjustCFI:2088 OS << "AdjustCFI";2089 break;2090 }2091 Sep = ", ";2092 }2093 OS << "]";2094 return OS;2095}2096 2097bool operator==(const ShrinkWrapping::WorklistItem &A,2098 const ShrinkWrapping::WorklistItem &B) {2099 return (A.Action == B.Action && A.AffectedReg == B.AffectedReg &&2100 A.Adjustment == B.Adjustment &&2101 A.FIEToInsert.IsLoad == B.FIEToInsert.IsLoad &&2102 A.FIEToInsert.IsStore == B.FIEToInsert.IsStore &&2103 A.FIEToInsert.RegOrImm == B.FIEToInsert.RegOrImm &&2104 A.FIEToInsert.Size == B.FIEToInsert.Size &&2105 A.FIEToInsert.IsSimple == B.FIEToInsert.IsSimple &&2106 A.FIEToInsert.StackOffset == B.FIEToInsert.StackOffset);2107}2108 2109bool operator==(const StackLayoutModifier::WorklistItem &A,2110 const StackLayoutModifier::WorklistItem &B) {2111 return (A.Action == B.Action && A.OffsetUpdate == B.OffsetUpdate);2112}2113 2114} // end namespace bolt2115} // end namespace llvm2116