401 lines · cpp
1//===- bolt/Passes/FrameOptimizer.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 FrameOptimizerPass class.10//11//===----------------------------------------------------------------------===//12 13#include "bolt/Passes/FrameOptimizer.h"14#include "bolt/Core/BinaryFunctionCallGraph.h"15#include "bolt/Core/ParallelUtilities.h"16#include "bolt/Passes/DataflowInfoManager.h"17#include "bolt/Passes/ShrinkWrapping.h"18#include "bolt/Passes/StackAvailableExpressions.h"19#include "bolt/Passes/StackReachingUses.h"20#include "bolt/Utils/CommandLineOpts.h"21#include "llvm/Support/Timer.h"22#include <deque>23 24#define DEBUG_TYPE "fop"25 26using namespace llvm;27 28namespace opts {29extern cl::opt<unsigned> Verbosity;30extern cl::opt<bool> TimeOpts;31extern cl::OptionCategory BoltOptCategory;32 33using namespace bolt;34 35cl::opt<FrameOptimizationType>36FrameOptimization("frame-opt",37 cl::init(FOP_NONE),38 cl::desc("optimize stack frame accesses"),39 cl::values(40 clEnumValN(FOP_NONE, "none", "do not perform frame optimization"),41 clEnumValN(FOP_HOT, "hot", "perform FOP on hot functions"),42 clEnumValN(FOP_ALL, "all", "perform FOP on all functions")),43 cl::ZeroOrMore,44 cl::cat(BoltOptCategory));45 46static cl::opt<bool> RemoveStores(47 "frame-opt-rm-stores", cl::init(FOP_NONE),48 cl::desc("apply additional analysis to remove stores (experimental)"),49 cl::cat(BoltOptCategory));50 51} // namespace opts52 53namespace llvm {54namespace bolt {55 56void FrameOptimizerPass::removeUnnecessaryLoads(const RegAnalysis &RA,57 const FrameAnalysis &FA,58 BinaryFunction &BF) {59 StackAvailableExpressions SAE(RA, FA, BF);60 SAE.run();61 62 LLVM_DEBUG(dbgs() << "Performing unnecessary loads removal\n");63 std::deque<std::pair<BinaryBasicBlock *, MCInst *>> ToErase;64 bool Changed = false;65 const auto ExprEnd = SAE.expr_end();66 MCPlusBuilder *MIB = BF.getBinaryContext().MIB.get();67 for (BinaryBasicBlock &BB : BF) {68 LLVM_DEBUG(dbgs() << "\tNow at BB " << BB.getName() << "\n");69 const MCInst *Prev = nullptr;70 for (MCInst &Inst : BB) {71 LLVM_DEBUG({72 dbgs() << "\t\tNow at ";73 Inst.dump();74 for (auto I = Prev ? SAE.expr_begin(*Prev) : SAE.expr_begin(BB);75 I != ExprEnd; ++I) {76 dbgs() << "\t\t\tReached by: ";77 (*I)->dump();78 }79 });80 // if Inst is a load from stack and the current available expressions show81 // this value is available in a register or immediate, replace this load82 // with move from register or from immediate.83 ErrorOr<const FrameIndexEntry &> FIEX = FA.getFIEFor(Inst);84 if (!FIEX) {85 Prev = &Inst;86 continue;87 }88 // FIXME: Change to remove IsSimple == 0. We're being conservative here,89 // but once replaceMemOperandWithReg is ready, we should feed it with all90 // sorts of complex instructions.91 if (FIEX->IsLoad == false || FIEX->IsSimple == false ||92 FIEX->StackOffset >= 0) {93 Prev = &Inst;94 continue;95 }96 97 for (auto I = Prev ? SAE.expr_begin(*Prev) : SAE.expr_begin(BB);98 I != ExprEnd; ++I) {99 const MCInst *AvailableInst = *I;100 ErrorOr<const FrameIndexEntry &> FIEY = FA.getFIEFor(*AvailableInst);101 if (!FIEY)102 continue;103 assert(FIEY->IsStore && FIEY->IsSimple);104 if (FIEX->StackOffset != FIEY->StackOffset || FIEX->Size != FIEY->Size)105 continue;106 // TODO: Change push/pops to stack adjustment instruction107 if (MIB->isPop(Inst))108 continue;109 110 ++NumRedundantLoads;111 FreqRedundantLoads += BB.getKnownExecutionCount();112 Changed = true;113 LLVM_DEBUG(dbgs() << "Redundant load instruction: ");114 LLVM_DEBUG(Inst.dump());115 LLVM_DEBUG(dbgs() << "Related store instruction: ");116 LLVM_DEBUG(AvailableInst->dump());117 LLVM_DEBUG(dbgs() << "@BB: " << BB.getName() << "\n");118 // Replace load119 if (FIEY->IsStoreFromReg) {120 if (!MIB->replaceMemOperandWithReg(Inst, FIEY->RegOrImm)) {121 LLVM_DEBUG(dbgs() << "FAILED to change operand to a reg\n");122 break;123 }124 FreqLoadsChangedToReg += BB.getKnownExecutionCount();125 MIB->removeAnnotation(Inst, "FrameAccessEntry");126 LLVM_DEBUG(dbgs() << "Changed operand to a reg\n");127 if (MIB->isRedundantMove(Inst)) {128 ++NumLoadsDeleted;129 FreqLoadsDeleted += BB.getKnownExecutionCount();130 LLVM_DEBUG(dbgs() << "Created a redundant move\n");131 // Delete it!132 ToErase.push_front(std::make_pair(&BB, &Inst));133 }134 } else {135 char Buf[8] = {0, 0, 0, 0, 0, 0, 0, 0};136 support::ulittle64_t::ref(Buf + 0) = FIEY->RegOrImm;137 LLVM_DEBUG(dbgs() << "Changing operand to an imm... ");138 if (!MIB->replaceMemOperandWithImm(Inst, StringRef(Buf, 8), 0)) {139 LLVM_DEBUG(dbgs() << "FAILED\n");140 } else {141 FreqLoadsChangedToImm += BB.getKnownExecutionCount();142 MIB->removeAnnotation(Inst, "FrameAccessEntry");143 LLVM_DEBUG(dbgs() << "Ok\n");144 }145 }146 LLVM_DEBUG(dbgs() << "Changed to: ");147 LLVM_DEBUG(Inst.dump());148 break;149 }150 Prev = &Inst;151 }152 }153 if (Changed)154 LLVM_DEBUG(dbgs() << "FOP modified \"" << BF.getPrintName() << "\"\n");155 156 // TODO: Implement an interface of eraseInstruction that works out the157 // complete list of elements to remove.158 for (std::pair<BinaryBasicBlock *, MCInst *> I : ToErase)159 I.first->eraseInstruction(I.first->findInstruction(I.second));160}161 162void FrameOptimizerPass::removeUnusedStores(const FrameAnalysis &FA,163 BinaryFunction &BF) {164 StackReachingUses SRU(FA, BF);165 SRU.run();166 167 LLVM_DEBUG(dbgs() << "Performing unused stores removal\n");168 std::vector<std::pair<BinaryBasicBlock *, MCInst *>> ToErase;169 bool Changed = false;170 for (BinaryBasicBlock &BB : BF) {171 LLVM_DEBUG(dbgs() << "\tNow at BB " << BB.getName() << "\n");172 const MCInst *Prev = nullptr;173 for (MCInst &Inst : llvm::reverse(BB)) {174 LLVM_DEBUG({175 dbgs() << "\t\tNow at ";176 Inst.dump();177 for (auto I = Prev ? SRU.expr_begin(*Prev) : SRU.expr_begin(BB);178 I != SRU.expr_end(); ++I) {179 dbgs() << "\t\t\tReached by: ";180 (*I)->dump();181 }182 });183 ErrorOr<const FrameIndexEntry &> FIEX = FA.getFIEFor(Inst);184 if (!FIEX) {185 Prev = &Inst;186 continue;187 }188 if (FIEX->IsLoad || !FIEX->IsSimple || FIEX->StackOffset >= 0) {189 Prev = &Inst;190 continue;191 }192 193 if (SRU.isStoreUsed(*FIEX,194 Prev ? SRU.expr_begin(*Prev) : SRU.expr_begin(BB))) {195 Prev = &Inst;196 continue;197 }198 // TODO: Change push/pops to stack adjustment instruction199 if (BF.getBinaryContext().MIB->isPush(Inst))200 continue;201 202 ++NumRedundantStores;203 FreqRedundantStores += BB.getKnownExecutionCount();204 Changed = true;205 LLVM_DEBUG(dbgs() << "Unused store instruction: ");206 LLVM_DEBUG(Inst.dump());207 LLVM_DEBUG(dbgs() << "@BB: " << BB.getName() << "\n");208 LLVM_DEBUG(dbgs() << "FIE offset = " << FIEX->StackOffset209 << " size = " << (int)FIEX->Size << "\n");210 // Delete it!211 ToErase.emplace_back(&BB, &Inst);212 Prev = &Inst;213 }214 }215 216 for (std::pair<BinaryBasicBlock *, MCInst *> I : ToErase)217 I.first->eraseInstruction(I.first->findInstruction(I.second));218 219 if (Changed)220 LLVM_DEBUG(dbgs() << "FOP modified \"" << BF.getPrintName() << "\"\n");221}222 223Error FrameOptimizerPass::runOnFunctions(BinaryContext &BC) {224 if (opts::FrameOptimization == FOP_NONE)225 return Error::success();226 227 if (!BC.isX86()) {228 BC.errs() << "BOLT-ERROR: " << getName() << " is supported only on X86\n";229 exit(1);230 }231 232 std::unique_ptr<BinaryFunctionCallGraph> CG;233 std::unique_ptr<FrameAnalysis> FA;234 std::unique_ptr<RegAnalysis> RA;235 236 {237 NamedRegionTimer T1("callgraph", "create call graph", "FOP",238 "FOP breakdown", opts::TimeOpts);239 CG = std::make_unique<BinaryFunctionCallGraph>(buildCallGraph(BC));240 }241 242 {243 NamedRegionTimer T1("frameanalysis", "frame analysis", "FOP",244 "FOP breakdown", opts::TimeOpts);245 FA = std::make_unique<FrameAnalysis>(BC, *CG);246 }247 248 {249 NamedRegionTimer T1("reganalysis", "reg analysis", "FOP", "FOP breakdown",250 opts::TimeOpts);251 RA = std::make_unique<RegAnalysis>(BC, &BC.getBinaryFunctions(), CG.get());252 }253 254 // Perform caller-saved register optimizations, then callee-saved register255 // optimizations (shrink wrapping)256 for (auto &I : BC.getBinaryFunctions()) {257 if (!FA->hasFrameInfo(I.second))258 continue;259 // Restrict pass execution if user asked to only run on hot functions260 if (opts::FrameOptimization == FOP_HOT) {261 if (I.second.getKnownExecutionCount() < BC.getHotThreshold())262 continue;263 LLVM_DEBUG(264 dbgs() << "Considering " << I.second.getPrintName()265 << " for frame optimizations because its execution count ( "266 << I.second.getKnownExecutionCount()267 << " ) exceeds our hotness threshold ( "268 << BC.getHotThreshold() << " )\n");269 }270 271 {272 NamedRegionTimer T1("removeloads", "remove loads", "FOP", "FOP breakdown",273 opts::TimeOpts);274 if (!FA->hasStackArithmetic(I.second))275 removeUnnecessaryLoads(*RA, *FA, I.second);276 }277 278 if (opts::RemoveStores) {279 NamedRegionTimer T1("removestores", "remove stores", "FOP",280 "FOP breakdown", opts::TimeOpts);281 if (!FA->hasStackArithmetic(I.second))282 removeUnusedStores(*FA, I.second);283 }284 // Don't even start shrink wrapping if no profiling info is available285 if (I.second.getKnownExecutionCount() == 0)286 continue;287 }288 289 {290 NamedRegionTimer T1("shrinkwrapping", "shrink wrapping", "FOP",291 "FOP breakdown", opts::TimeOpts);292 if (Error E = performShrinkWrapping(*RA, *FA, BC))293 return Error(std::move(E));294 }295 296 BC.outs() << "BOLT-INFO: FOP optimized " << NumRedundantLoads297 << " redundant load(s) and " << NumRedundantStores298 << " unused store(s)\n";299 BC.outs() << "BOLT-INFO: Frequency of redundant loads is "300 << FreqRedundantLoads << " and frequency of unused stores is "301 << FreqRedundantStores << "\n";302 BC.outs() << "BOLT-INFO: Frequency of loads changed to use a register is "303 << FreqLoadsChangedToReg304 << " and frequency of loads changed to use an immediate is "305 << FreqLoadsChangedToImm << "\n";306 BC.outs() << "BOLT-INFO: FOP deleted " << NumLoadsDeleted307 << " load(s) (dyn count: " << FreqLoadsDeleted << ") and "308 << NumRedundantStores << " store(s)\n";309 FA->printStats();310 ShrinkWrapping::printStats(BC);311 return Error::success();312}313 314Error FrameOptimizerPass::performShrinkWrapping(const RegAnalysis &RA,315 const FrameAnalysis &FA,316 BinaryContext &BC) {317 // Initialize necessary annotations to allow safe parallel accesses to318 // annotation index in MIB319 BC.MIB->getOrCreateAnnotationIndex(CalleeSavedAnalysis::getSaveTagName());320 BC.MIB->getOrCreateAnnotationIndex(CalleeSavedAnalysis::getRestoreTagName());321 BC.MIB->getOrCreateAnnotationIndex(StackLayoutModifier::getTodoTagName());322 BC.MIB->getOrCreateAnnotationIndex(StackLayoutModifier::getSlotTagName());323 BC.MIB->getOrCreateAnnotationIndex(324 StackLayoutModifier::getOffsetCFIRegTagName());325 BC.MIB->getOrCreateAnnotationIndex("ReachingDefs");326 BC.MIB->getOrCreateAnnotationIndex("ReachingUses");327 BC.MIB->getOrCreateAnnotationIndex("LivenessAnalysis");328 BC.MIB->getOrCreateAnnotationIndex("StackReachingUses");329 BC.MIB->getOrCreateAnnotationIndex("PostDominatorAnalysis");330 BC.MIB->getOrCreateAnnotationIndex("DominatorAnalysis");331 BC.MIB->getOrCreateAnnotationIndex("StackPointerTracking");332 BC.MIB->getOrCreateAnnotationIndex("StackPointerTrackingForInternalCalls");333 BC.MIB->getOrCreateAnnotationIndex("StackAvailableExpressions");334 BC.MIB->getOrCreateAnnotationIndex("StackAllocationAnalysis");335 BC.MIB->getOrCreateAnnotationIndex("ShrinkWrap-Todo");336 BC.MIB->getOrCreateAnnotationIndex("PredictiveStackPointerTracking");337 BC.MIB->getOrCreateAnnotationIndex("ReachingInsnsBackward");338 BC.MIB->getOrCreateAnnotationIndex("ReachingInsns");339 BC.MIB->getOrCreateAnnotationIndex("AccessesDeletedPos");340 BC.MIB->getOrCreateAnnotationIndex("DeleteMe");341 342 std::vector<std::pair<uint64_t, const BinaryFunction *>> Top10Funcs;343 auto LogFunc = [&](BinaryFunction &BF) {344 auto Lower = llvm::lower_bound(345 Top10Funcs, BF.getKnownExecutionCount(),346 [](const std::pair<uint64_t, const BinaryFunction *> &Elmt,347 uint64_t Value) { return Elmt.first > Value; });348 if (Lower == Top10Funcs.end() && Top10Funcs.size() >= 10)349 return;350 Top10Funcs.insert(Lower,351 std::make_pair<>(BF.getKnownExecutionCount(), &BF));352 if (Top10Funcs.size() > 10)353 Top10Funcs.resize(10);354 };355 (void)LogFunc;356 357 ParallelUtilities::PredicateTy SkipPredicate = [&](const BinaryFunction &BF) {358 if (BF.getFunctionScore() == 0)359 return true;360 361 return false;362 };363 364 const bool HotOnly = opts::FrameOptimization == FOP_HOT;365 366 Error SWError = Error::success();367 368 ParallelUtilities::WorkFuncWithAllocTy WorkFunction =369 [&](BinaryFunction &BF, MCPlusBuilder::AllocatorIdTy AllocatorId) {370 DataflowInfoManager Info(BF, &RA, &FA, AllocatorId);371 ShrinkWrapping SW(FA, BF, Info, AllocatorId);372 373 auto ChangedOrErr = SW.perform(HotOnly);374 if (auto E = ChangedOrErr.takeError()) {375 std::lock_guard<std::mutex> Lock(FuncsChangedMutex);376 SWError = joinErrors(std::move(SWError), Error(std::move(E)));377 return;378 }379 const bool Changed = *ChangedOrErr;380 if (Changed) {381 std::lock_guard<std::mutex> Lock(FuncsChangedMutex);382 FuncsChanged.insert(&BF);383 LLVM_DEBUG(LogFunc(BF));384 }385 };386 387 ParallelUtilities::runOnEachFunctionWithUniqueAllocId(388 BC, ParallelUtilities::SchedulingPolicy::SP_INST_QUADRATIC, WorkFunction,389 SkipPredicate, "shrink-wrapping");390 391 if (!Top10Funcs.empty()) {392 BC.outs() << "BOLT-INFO: top 10 functions changed by shrink wrapping:\n";393 for (const auto &Elmt : Top10Funcs)394 BC.outs() << Elmt.first << " : " << Elmt.second->getPrintName() << "\n";395 }396 return SWError;397}398 399} // namespace bolt400} // namespace llvm401