//===- bolt/Passes/FrameOptimizer.cpp -------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements the FrameOptimizerPass class.
//
//===----------------------------------------------------------------------===//

#include "bolt/Passes/FrameOptimizer.h"
#include "bolt/Core/ParallelUtilities.h"
#include "bolt/Passes/BinaryFunctionCallGraph.h"
#include "bolt/Passes/DataflowInfoManager.h"
#include "bolt/Passes/ShrinkWrapping.h"
#include "bolt/Passes/StackAvailableExpressions.h"
#include "bolt/Passes/StackReachingUses.h"
#include "bolt/Utils/CommandLineOpts.h"
#include "llvm/Support/Timer.h"
#include <deque>
#include <unordered_map>

#define DEBUG_TYPE "fop"

using namespace llvm;

namespace opts {
extern cl::opt<unsigned> Verbosity;
extern cl::opt<bool> TimeOpts;
extern cl::OptionCategory BoltOptCategory;

using namespace bolt;

cl::opt<FrameOptimizationType>
FrameOptimization("frame-opt",
  cl::init(FOP_NONE),
  cl::desc("optimize stack frame accesses"),
  cl::values(
    clEnumValN(FOP_NONE, "none", "do not perform frame optimization"),
    clEnumValN(FOP_HOT, "hot", "perform FOP on hot functions"),
    clEnumValN(FOP_ALL, "all", "perform FOP on all functions")),
  cl::ZeroOrMore,
  cl::cat(BoltOptCategory));

cl::opt<bool> RemoveStores(
    "frame-opt-rm-stores", cl::init(FOP_NONE),
    cl::desc("apply additional analysis to remove stores (experimental)"),
    cl::cat(BoltOptCategory));

} // namespace opts

namespace llvm {
namespace bolt {

void FrameOptimizerPass::removeUnnecessaryLoads(const RegAnalysis &RA,
                                                const FrameAnalysis &FA,
                                                BinaryFunction &BF) {
  StackAvailableExpressions SAE(RA, FA, BF);
  SAE.run();

  LLVM_DEBUG(dbgs() << "Performing unnecessary loads removal\n");
  std::deque<std::pair<BinaryBasicBlock *, MCInst *>> ToErase;
  bool Changed = false;
  const auto ExprEnd = SAE.expr_end();
  MCPlusBuilder *MIB = BF.getBinaryContext().MIB.get();
  for (BinaryBasicBlock &BB : BF) {
    LLVM_DEBUG(dbgs() << "\tNow at BB " << BB.getName() << "\n");
    const MCInst *Prev = nullptr;
    for (MCInst &Inst : BB) {
      LLVM_DEBUG({
        dbgs() << "\t\tNow at ";
        Inst.dump();
        for (auto I = Prev ? SAE.expr_begin(*Prev) : SAE.expr_begin(BB);
             I != ExprEnd; ++I) {
          dbgs() << "\t\t\tReached by: ";
          (*I)->dump();
        }
      });
      // if Inst is a load from stack and the current available expressions show
      // this value is available in a register or immediate, replace this load
      // with move from register or from immediate.
      ErrorOr<const FrameIndexEntry &> FIEX = FA.getFIEFor(Inst);
      if (!FIEX) {
        Prev = &Inst;
        continue;
      }
      // FIXME: Change to remove IsSimple == 0. We're being conservative here,
      // but once replaceMemOperandWithReg is ready, we should feed it with all
      // sorts of complex instructions.
      if (FIEX->IsLoad == false || FIEX->IsSimple == false ||
          FIEX->StackOffset >= 0) {
        Prev = &Inst;
        continue;
      }

      for (auto I = Prev ? SAE.expr_begin(*Prev) : SAE.expr_begin(BB);
           I != ExprEnd; ++I) {
        const MCInst *AvailableInst = *I;
        ErrorOr<const FrameIndexEntry &> FIEY = FA.getFIEFor(*AvailableInst);
        if (!FIEY)
          continue;
        assert(FIEY->IsStore && FIEY->IsSimple);
        if (FIEX->StackOffset != FIEY->StackOffset || FIEX->Size != FIEY->Size)
          continue;
        // TODO: Change push/pops to stack adjustment instruction
        if (MIB->isPop(Inst))
          continue;

        ++NumRedundantLoads;
        FreqRedundantLoads += BB.getKnownExecutionCount();
        Changed = true;
        LLVM_DEBUG(dbgs() << "Redundant load instruction: ");
        LLVM_DEBUG(Inst.dump());
        LLVM_DEBUG(dbgs() << "Related store instruction: ");
        LLVM_DEBUG(AvailableInst->dump());
        LLVM_DEBUG(dbgs() << "@BB: " << BB.getName() << "\n");
        // Replace load
        if (FIEY->IsStoreFromReg) {
          if (!MIB->replaceMemOperandWithReg(Inst, FIEY->RegOrImm)) {
            LLVM_DEBUG(dbgs() << "FAILED to change operand to a reg\n");
            break;
          }
          FreqLoadsChangedToReg += BB.getKnownExecutionCount();
          MIB->removeAnnotation(Inst, "FrameAccessEntry");
          LLVM_DEBUG(dbgs() << "Changed operand to a reg\n");
          if (MIB->isRedundantMove(Inst)) {
            ++NumLoadsDeleted;
            FreqLoadsDeleted += BB.getKnownExecutionCount();
            LLVM_DEBUG(dbgs() << "Created a redundant move\n");
            // Delete it!
            ToErase.push_front(std::make_pair(&BB, &Inst));
          }
        } else {
          char Buf[8] = {0, 0, 0, 0, 0, 0, 0, 0};
          support::ulittle64_t::ref(Buf + 0) = FIEY->RegOrImm;
          LLVM_DEBUG(dbgs() << "Changing operand to an imm... ");
          if (!MIB->replaceMemOperandWithImm(Inst, StringRef(Buf, 8), 0)) {
            LLVM_DEBUG(dbgs() << "FAILED\n");
          } else {
            FreqLoadsChangedToImm += BB.getKnownExecutionCount();
            MIB->removeAnnotation(Inst, "FrameAccessEntry");
            LLVM_DEBUG(dbgs() << "Ok\n");
          }
        }
        LLVM_DEBUG(dbgs() << "Changed to: ");
        LLVM_DEBUG(Inst.dump());
        break;
      }
      Prev = &Inst;
    }
  }
  if (Changed)
    LLVM_DEBUG(dbgs() << "FOP modified \"" << BF.getPrintName() << "\"\n");

  // TODO: Implement an interface of eraseInstruction that works out the
  // complete list of elements to remove.
  for (std::pair<BinaryBasicBlock *, MCInst *> I : ToErase)
    I.first->eraseInstruction(I.first->findInstruction(I.second));
}

void FrameOptimizerPass::removeUnusedStores(const FrameAnalysis &FA,
                                            BinaryFunction &BF) {
  StackReachingUses SRU(FA, BF);
  SRU.run();

  LLVM_DEBUG(dbgs() << "Performing unused stores removal\n");
  std::vector<std::pair<BinaryBasicBlock *, MCInst *>> ToErase;
  bool Changed = false;
  for (BinaryBasicBlock &BB : BF) {
    LLVM_DEBUG(dbgs() << "\tNow at BB " << BB.getName() << "\n");
    const MCInst *Prev = nullptr;
    for (MCInst &Inst : llvm::reverse(BB)) {
      LLVM_DEBUG({
        dbgs() << "\t\tNow at ";
        Inst.dump();
        for (auto I = Prev ? SRU.expr_begin(*Prev) : SRU.expr_begin(BB);
             I != SRU.expr_end(); ++I) {
          dbgs() << "\t\t\tReached by: ";
          (*I)->dump();
        }
      });
      ErrorOr<const FrameIndexEntry &> FIEX = FA.getFIEFor(Inst);
      if (!FIEX) {
        Prev = &Inst;
        continue;
      }
      if (FIEX->IsLoad || !FIEX->IsSimple || FIEX->StackOffset >= 0) {
        Prev = &Inst;
        continue;
      }

      if (SRU.isStoreUsed(*FIEX,
                          Prev ? SRU.expr_begin(*Prev) : SRU.expr_begin(BB))) {
        Prev = &Inst;
        continue;
      }
      // TODO: Change push/pops to stack adjustment instruction
      if (BF.getBinaryContext().MIB->isPush(Inst))
        continue;

      ++NumRedundantStores;
      FreqRedundantStores += BB.getKnownExecutionCount();
      Changed = true;
      LLVM_DEBUG(dbgs() << "Unused store instruction: ");
      LLVM_DEBUG(Inst.dump());
      LLVM_DEBUG(dbgs() << "@BB: " << BB.getName() << "\n");
      LLVM_DEBUG(dbgs() << "FIE offset = " << FIEX->StackOffset
                        << " size = " << (int)FIEX->Size << "\n");
      // Delete it!
      ToErase.emplace_back(&BB, &Inst);
      Prev = &Inst;
    }
  }

  for (std::pair<BinaryBasicBlock *, MCInst *> I : ToErase)
    I.first->eraseInstruction(I.first->findInstruction(I.second));

  if (Changed)
    LLVM_DEBUG(dbgs() << "FOP modified \"" << BF.getPrintName() << "\"\n");
}

void FrameOptimizerPass::runOnFunctions(BinaryContext &BC) {
  if (opts::FrameOptimization == FOP_NONE)
    return;

  std::unique_ptr<BinaryFunctionCallGraph> CG;
  std::unique_ptr<FrameAnalysis> FA;
  std::unique_ptr<RegAnalysis> RA;

  {
    NamedRegionTimer T1("callgraph", "create call graph", "FOP",
                        "FOP breakdown", opts::TimeOpts);
    CG = std::make_unique<BinaryFunctionCallGraph>(buildCallGraph(BC));
  }

  {
    NamedRegionTimer T1("frameanalysis", "frame analysis", "FOP",
                        "FOP breakdown", opts::TimeOpts);
    FA = std::make_unique<FrameAnalysis>(BC, *CG);
  }

  {
    NamedRegionTimer T1("reganalysis", "reg analysis", "FOP", "FOP breakdown",
                        opts::TimeOpts);
    RA = std::make_unique<RegAnalysis>(BC, &BC.getBinaryFunctions(), CG.get());
  }

  // Perform caller-saved register optimizations, then callee-saved register
  // optimizations (shrink wrapping)
  for (auto &I : BC.getBinaryFunctions()) {
    if (!FA->hasFrameInfo(I.second))
      continue;
    // Restrict pass execution if user asked to only run on hot functions
    if (opts::FrameOptimization == FOP_HOT) {
      if (I.second.getKnownExecutionCount() < BC.getHotThreshold())
        continue;
      LLVM_DEBUG(
          dbgs() << "Considering " << I.second.getPrintName()
                 << " for frame optimizations because its execution count ( "
                 << I.second.getKnownExecutionCount()
                 << " ) exceeds our hotness threshold ( "
                 << BC.getHotThreshold() << " )\n");
    }

    {
      NamedRegionTimer T1("removeloads", "remove loads", "FOP", "FOP breakdown",
                          opts::TimeOpts);
      if (!FA->hasStackArithmetic(I.second))
        removeUnnecessaryLoads(*RA, *FA, I.second);
    }

    if (opts::RemoveStores) {
      NamedRegionTimer T1("removestores", "remove stores", "FOP",
                          "FOP breakdown", opts::TimeOpts);
      if (!FA->hasStackArithmetic(I.second))
        removeUnusedStores(*FA, I.second);
    }
    // Don't even start shrink wrapping if no profiling info is available
    if (I.second.getKnownExecutionCount() == 0)
      continue;
  }

  {
    NamedRegionTimer T1("shrinkwrapping", "shrink wrapping", "FOP",
                        "FOP breakdown", opts::TimeOpts);
    performShrinkWrapping(*RA, *FA, BC);
  }

  outs() << "BOLT-INFO: FOP optimized " << NumRedundantLoads
         << " redundant load(s) and " << NumRedundantStores
         << " unused store(s)\n";
  outs() << "BOLT-INFO: Frequency of redundant loads is " << FreqRedundantLoads
         << " and frequency of unused stores is " << FreqRedundantStores
         << "\n";
  outs() << "BOLT-INFO: Frequency of loads changed to use a register is "
         << FreqLoadsChangedToReg
         << " and frequency of loads changed to use an immediate is "
         << FreqLoadsChangedToImm << "\n";
  outs() << "BOLT-INFO: FOP deleted " << NumLoadsDeleted
         << " load(s) (dyn count: " << FreqLoadsDeleted << ") and "
         << NumRedundantStores << " store(s)\n";
  FA->printStats();
  ShrinkWrapping::printStats();
}

void FrameOptimizerPass::performShrinkWrapping(const RegAnalysis &RA,
                                               const FrameAnalysis &FA,
                                               BinaryContext &BC) {
  // Initialize necessary annotations to allow safe parallel accesses to
  // annotation index in MIB
  BC.MIB->getOrCreateAnnotationIndex(CalleeSavedAnalysis::getSaveTagName());
  BC.MIB->getOrCreateAnnotationIndex(CalleeSavedAnalysis::getRestoreTagName());
  BC.MIB->getOrCreateAnnotationIndex(StackLayoutModifier::getTodoTagName());
  BC.MIB->getOrCreateAnnotationIndex(StackLayoutModifier::getSlotTagName());
  BC.MIB->getOrCreateAnnotationIndex(
      StackLayoutModifier::getOffsetCFIRegTagName());
  BC.MIB->getOrCreateAnnotationIndex("ReachingDefs");
  BC.MIB->getOrCreateAnnotationIndex("ReachingUses");
  BC.MIB->getOrCreateAnnotationIndex("LivenessAnalysis");
  BC.MIB->getOrCreateAnnotationIndex("StackReachingUses");
  BC.MIB->getOrCreateAnnotationIndex("PostDominatorAnalysis");
  BC.MIB->getOrCreateAnnotationIndex("DominatorAnalysis");
  BC.MIB->getOrCreateAnnotationIndex("StackPointerTracking");
  BC.MIB->getOrCreateAnnotationIndex("StackPointerTrackingForInternalCalls");
  BC.MIB->getOrCreateAnnotationIndex("StackAvailableExpressions");
  BC.MIB->getOrCreateAnnotationIndex("StackAllocationAnalysis");
  BC.MIB->getOrCreateAnnotationIndex("ShrinkWrap-Todo");
  BC.MIB->getOrCreateAnnotationIndex("PredictiveStackPointerTracking");
  BC.MIB->getOrCreateAnnotationIndex("ReachingInsnsBackward");
  BC.MIB->getOrCreateAnnotationIndex("ReachingInsns");
  BC.MIB->getOrCreateAnnotationIndex("AccessesDeletedPos");
  BC.MIB->getOrCreateAnnotationIndex("DeleteMe");

  std::vector<std::pair<uint64_t, const BinaryFunction *>> Top10Funcs;
  auto LogFunc = [&](BinaryFunction &BF) {
    auto Lower = llvm::lower_bound(
        Top10Funcs, BF.getKnownExecutionCount(),
        [](const std::pair<uint64_t, const BinaryFunction *> &Elmt,
           uint64_t Value) { return Elmt.first > Value; });
    if (Lower == Top10Funcs.end() && Top10Funcs.size() >= 10)
      return;
    Top10Funcs.insert(Lower,
                      std::make_pair<>(BF.getKnownExecutionCount(), &BF));
    if (Top10Funcs.size() > 10)
      Top10Funcs.resize(10);
  };
  (void)LogFunc;

  ParallelUtilities::PredicateTy SkipPredicate = [&](const BinaryFunction &BF) {
    if (BF.getFunctionScore() == 0)
      return true;

    return false;
  };

  const bool HotOnly = opts::FrameOptimization == FOP_HOT;

  ParallelUtilities::WorkFuncWithAllocTy WorkFunction =
      [&](BinaryFunction &BF, MCPlusBuilder::AllocatorIdTy AllocatorId) {
        DataflowInfoManager Info(BF, &RA, &FA, AllocatorId);
        ShrinkWrapping SW(FA, BF, Info, AllocatorId);

        if (SW.perform(HotOnly)) {
          std::lock_guard<std::mutex> Lock(FuncsChangedMutex);
          FuncsChanged.insert(&BF);
          LLVM_DEBUG(LogFunc(BF));
        }
      };

  ParallelUtilities::runOnEachFunctionWithUniqueAllocId(
      BC, ParallelUtilities::SchedulingPolicy::SP_INST_QUADRATIC, WorkFunction,
      SkipPredicate, "shrink-wrapping");

  if (!Top10Funcs.empty()) {
    outs() << "BOLT-INFO: top 10 functions changed by shrink wrapping:\n";
    for (const auto &Elmt : Top10Funcs)
      outs() << Elmt.first << " : " << Elmt.second->getPrintName() << "\n";
  }
}

} // namespace bolt
} // namespace llvm