//===- LoopPass.cpp - Loop Pass and Loop Pass Manager ---------------------===//

//

// 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 LoopPass and LPPassManager. All loop optimization

// and transformation passes are derived from LoopPass. LPPassManager is

// responsible for managing LoopPasses.

//

//===----------------------------------------------------------------------===//

#include "llvm/Analysis/LoopPass.h"

#include "llvm/Analysis/LoopInfo.h"

#include "llvm/IR/Dominators.h"

#include "llvm/IR/LLVMContext.h"

#include "llvm/IR/OptBisect.h"

#include "llvm/IR/PassTimingInfo.h"

#include "llvm/IR/PrintPasses.h"

#include "llvm/InitializePasses.h"

#include "llvm/Support/Debug.h"

#include "llvm/Support/TimeProfiler.h"

#include "llvm/Support/Timer.h"

#include "llvm/Support/raw_ostream.h"

using namespace llvm;

#define DEBUG_TYPE "loop-pass-manager"

namespace {

/// PrintLoopPass - Print a Function corresponding to a Loop.

///

class PrintLoopPassWrapper : public LoopPass {

  raw_ostream &OS;

  std::string Banner;

public:

  static char ID;

  PrintLoopPassWrapper() : LoopPass(ID), OS(dbgs()) {}

  PrintLoopPassWrapper(raw_ostream &OS, const std::string &Banner)

      : LoopPass(ID), OS(OS), Banner(Banner) {}

  void getAnalysisUsage(AnalysisUsage &AU) const override {

    AU.setPreservesAll();

  }

  bool runOnLoop(Loop *L, LPPassManager &) override {

    auto BBI = llvm::find_if(L->blocks(), [](BasicBlock *BB) { return BB; });

    if (BBI != L->blocks().end() &&

        isFunctionInPrintList((*BBI)->getParent()->getName())) {

      printLoop(*L, OS, Banner);

    }

    return false;

  }

  StringRef getPassName() const override { return "Print Loop IR"; }

};

char PrintLoopPassWrapper::ID = 0;

}

//===----------------------------------------------------------------------===//

// LPPassManager

//

char LPPassManager::ID = 0;

LPPassManager::LPPassManager() : FunctionPass(ID) {

  LI = nullptr;

  CurrentLoop = nullptr;

}

// Insert loop into loop nest (LoopInfo) and loop queue (LQ).

void LPPassManager::addLoop(Loop &L) {

  if (L.isOutermost()) {

    // This is the top level loop.

    LQ.push_front(&L);

    return;

  }

  // Insert L into the loop queue after the parent loop.

  for (auto I = LQ.begin(), E = LQ.end(); I != E; ++I) {

    if (*I == L.getParentLoop()) {

      // deque does not support insert after.

      ++I;

      LQ.insert(I, 1, &L);

      return;

    }

  }

}

// Recurse through all subloops and all loops  into LQ.

static void addLoopIntoQueue(Loop *L, std::deque<Loop *> &LQ) {

  LQ.push_back(L);

  for (Loop *I : reverse(*L))

    addLoopIntoQueue(I, LQ);

}

/// Pass Manager itself does not invalidate any analysis info.

void LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const {

  // LPPassManager needs LoopInfo. In the long term LoopInfo class will

  // become part of LPPassManager.

  Info.addRequired<LoopInfoWrapperPass>();

  Info.addRequired<DominatorTreeWrapperPass>();

  Info.setPreservesAll();

}

void LPPassManager::markLoopAsDeleted(Loop &L) {

  assert((&L == CurrentLoop || CurrentLoop->contains(&L)) &&

         "Must not delete loop outside the current loop tree!");

  // If this loop appears elsewhere within the queue, we also need to remove it

  // there. However, we have to be careful to not remove the back of the queue

  // as that is assumed to match the current loop.

  assert(LQ.back() == CurrentLoop && "Loop queue back isn't the current loop!");

  llvm::erase(LQ, &L);

  if (&L == CurrentLoop) {

    CurrentLoopDeleted = true;

    // Add this loop back onto the back of the queue to preserve our invariants.

    LQ.push_back(&L);

  }

}

/// run - Execute all of the passes scheduled for execution.  Keep track of

/// whether any of the passes modifies the function, and if so, return true.

bool LPPassManager::runOnFunction(Function &F) {

  auto &LIWP = getAnalysis<LoopInfoWrapperPass>();

  LI = &LIWP.getLoopInfo();

  Module &M = *F.getParent();

#if 0

  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();

#endif

  bool Changed = false;

  // Collect inherited analysis from Module level pass manager.

  populateInheritedAnalysis(TPM->activeStack);

  // Populate the loop queue in reverse program order. There is no clear need to

  // process sibling loops in either forward or reverse order. There may be some

  // advantage in deleting uses in a later loop before optimizing the

  // definitions in an earlier loop. If we find a clear reason to process in

  // forward order, then a forward variant of LoopPassManager should be created.

  //

  // Note that LoopInfo::iterator visits loops in reverse program

  // order. Here, reverse_iterator gives us a forward order, and the LoopQueue

  // reverses the order a third time by popping from the back.

  for (Loop *L : reverse(*LI))

    addLoopIntoQueue(L, LQ);

  if (LQ.empty()) // No loops, skip calling finalizers

    return false;

  // Initialization

  for (Loop *L : LQ) {

    for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {

      LoopPass *P = getContainedPass(Index);

      Changed |= P->doInitialization(L, *this);

    }

  }

  // Walk Loops

  unsigned InstrCount, FunctionSize = 0;

  StringMap<std::pair<unsigned, unsigned>> FunctionToInstrCount;

  bool EmitICRemark = M.shouldEmitInstrCountChangedRemark();

  // Collect the initial size of the module and the function we're looking at.

  if (EmitICRemark) {

    InstrCount = initSizeRemarkInfo(M, FunctionToInstrCount);

    FunctionSize = F.getInstructionCount();

  }

  while (!LQ.empty()) {

    CurrentLoopDeleted = false;

    CurrentLoop = LQ.back();

    // Run all passes on the current Loop.

    for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {

      LoopPass *P = getContainedPass(Index);

      llvm::TimeTraceScope LoopPassScope("RunLoopPass", P->getPassName());

      dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG,

                   CurrentLoop->getHeader()->getName());

      dumpRequiredSet(P);

      initializeAnalysisImpl(P);

      bool LocalChanged = false;

      {

        PassManagerPrettyStackEntry X(P, *CurrentLoop->getHeader());

        TimeRegion PassTimer(getPassTimer(P));

#ifdef EXPENSIVE_CHECKS

        uint64_t RefHash = P->structuralHash(F);

#endif

        LocalChanged = P->runOnLoop(CurrentLoop, *this);

#ifdef EXPENSIVE_CHECKS

        if (!LocalChanged && (RefHash != P->structuralHash(F))) {

          llvm::errs() << "Pass modifies its input and doesn't report it: "

                       << P->getPassName() << "\n";

          llvm_unreachable("Pass modifies its input and doesn't report it");

        }

#endif

        Changed |= LocalChanged;

        if (EmitICRemark) {

          unsigned NewSize = F.getInstructionCount();

          // Update the size of the function, emit a remark, and update the

          // size of the module.

          if (NewSize != FunctionSize) {

            int64_t Delta = static_cast<int64_t>(NewSize) -

                            static_cast<int64_t>(FunctionSize);

            emitInstrCountChangedRemark(P, M, Delta, InstrCount,

                                        FunctionToInstrCount, &F);

            InstrCount = static_cast<int64_t>(InstrCount) + Delta;

            FunctionSize = NewSize;

          }

        }

      }

      if (LocalChanged)

        dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG,

                     CurrentLoopDeleted ? "<deleted loop>"

                                        : CurrentLoop->getName());

      dumpPreservedSet(P);

      if (!CurrentLoopDeleted) {

        // Manually check that this loop is still healthy. This is done

        // instead of relying on LoopInfo::verifyLoop since LoopInfo

        // is a function pass and it's really expensive to verify every

        // loop in the function every time. That level of checking can be

        // enabled with the -verify-loop-info option.

        {

          TimeRegion PassTimer(getPassTimer(&LIWP));

          CurrentLoop->verifyLoop();

        }

        // Here we apply same reasoning as in the above case. Only difference

        // is that LPPassManager might run passes which do not require LCSSA

        // form (LoopPassPrinter for example). We should skip verification for

        // such passes.

        // FIXME: Loop-sink currently break LCSSA. Fix it and reenable the

        // verification!

#if 0

        if (mustPreserveAnalysisID(LCSSAVerificationPass::ID))

          assert(CurrentLoop->isRecursivelyLCSSAForm(*DT, *LI));

#endif

        // Then call the regular verifyAnalysis functions.

        verifyPreservedAnalysis(P);

        F.getContext().yield();

      }

      if (LocalChanged)

        removeNotPreservedAnalysis(P);

      recordAvailableAnalysis(P);

      removeDeadPasses(P,

                       CurrentLoopDeleted ? "<deleted>"

                                          : CurrentLoop->getHeader()->getName(),

                       ON_LOOP_MSG);

      if (CurrentLoopDeleted)

        // Do not run other passes on this loop.

        break;

    }

    // If the loop was deleted, release all the loop passes. This frees up

    // some memory, and avoids trouble with the pass manager trying to call

    // verifyAnalysis on them.

    if (CurrentLoopDeleted) {

      for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {

        Pass *P = getContainedPass(Index);

        freePass(P, "<deleted>", ON_LOOP_MSG);

      }

    }

    // Pop the loop from queue after running all passes.

    LQ.pop_back();

  }

  // Finalization

  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {

    LoopPass *P = getContainedPass(Index);

    Changed |= P->doFinalization();

  }

  return Changed;

}

/// Print passes managed by this manager

void LPPassManager::dumpPassStructure(unsigned Offset) {

  errs().indent(Offset*2) << "Loop Pass Manager\n";

  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {

    Pass *P = getContainedPass(Index);

    P->dumpPassStructure(Offset + 1);

    dumpLastUses(P, Offset+1);

  }

}

//===----------------------------------------------------------------------===//

// LoopPass

Pass *LoopPass::createPrinterPass(raw_ostream &O,

                                  const std::string &Banner) const {

  return new PrintLoopPassWrapper(O, Banner);

}

// Check if this pass is suitable for the current LPPassManager, if

// available. This pass P is not suitable for a LPPassManager if P

// is not preserving higher level analysis info used by other

// LPPassManager passes. In such case, pop LPPassManager from the

// stack. This will force assignPassManager() to create new

// LPPassManger as expected.

void LoopPass::preparePassManager(PMStack &PMS) {

  // Find LPPassManager

  while (!PMS.empty() &&

         PMS.top()->getPassManagerType() > PMT_LoopPassManager)

    PMS.pop();

  // If this pass is destroying high level information that is used

  // by other passes that are managed by LPM then do not insert

  // this pass in current LPM. Use new LPPassManager.

  if (PMS.top()->getPassManagerType() == PMT_LoopPassManager &&

      !PMS.top()->preserveHigherLevelAnalysis(this))

    PMS.pop();

}

/// Assign pass manager to manage this pass.

void LoopPass::assignPassManager(PMStack &PMS,

                                 PassManagerType PreferredType) {

  // Find LPPassManager

  while (!PMS.empty() &&

         PMS.top()->getPassManagerType() > PMT_LoopPassManager)

    PMS.pop();

  LPPassManager *LPPM;

  if (PMS.top()->getPassManagerType() == PMT_LoopPassManager)

    LPPM = (LPPassManager*)PMS.top();

  else {

    // Create new Loop Pass Manager if it does not exist.

    assert (!PMS.empty() && "Unable to create Loop Pass Manager");

    PMDataManager *PMD = PMS.top();

    // [1] Create new Loop Pass Manager

    LPPM = new LPPassManager();

    LPPM->populateInheritedAnalysis(PMS);

    // [2] Set up new manager's top level manager

    PMTopLevelManager *TPM = PMD->getTopLevelManager();

    TPM->addIndirectPassManager(LPPM);

    // [3] Assign manager to manage this new manager. This may create

    // and push new managers into PMS

    Pass *P = LPPM->getAsPass();

    TPM->schedulePass(P);

    // [4] Push new manager into PMS

    PMS.push(LPPM);

  }

  LPPM->add(this);

}

static std::string getDescription(const Loop &L) {

  return "loop";

}

bool LoopPass::skipLoop(const Loop *L) const {

  const Function *F = L->getHeader()->getParent();

  if (!F)

    return false;

  // Check the opt bisect limit.

  OptPassGate &Gate = F->getContext().getOptPassGate();

  if (Gate.isEnabled() &&

      !Gate.shouldRunPass(this->getPassName(), getDescription(*L)))

    return true;

  // Check for the OptimizeNone attribute.

  if (F->hasOptNone()) {

    // FIXME: Report this to dbgs() only once per function.

    LLVM_DEBUG(dbgs() << "Skipping pass '" << getPassName() << "' in function "

                      << F->getName() << "\n");

    // FIXME: Delete loop from pass manager's queue?

    return true;

  }

  return false;

}

LCSSAVerificationPass::LCSSAVerificationPass() : FunctionPass(ID) {

  initializeLCSSAVerificationPassPass(*PassRegistry::getPassRegistry());

}

char LCSSAVerificationPass::ID = 0;

INITIALIZE_PASS(LCSSAVerificationPass, "lcssa-verification", "LCSSA Verifier",

                false, false)