//===- FunctionPropertiesAnalysis.cpp - Function Properties Analysis ------===//
//
// 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 defines the FunctionPropertiesInfo and FunctionPropertiesAnalysis
// classes used to extract function properties.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/FunctionPropertiesAnalysis.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/Support/CommandLine.h"
#include <deque>

using namespace llvm;

namespace llvm {
cl::opt<bool> EnableDetailedFunctionProperties(
    "enable-detailed-function-properties", cl::Hidden, cl::init(false),
    cl::desc("Whether or not to compute detailed function properties."));

static cl::opt<unsigned> BigBasicBlockInstructionThreshold(
    "big-basic-block-instruction-threshold", cl::Hidden, cl::init(500),
    cl::desc("The minimum number of instructions a basic block should contain "
             "before being considered big."));

static cl::opt<unsigned> MediumBasicBlockInstructionThreshold(
    "medium-basic-block-instruction-threshold", cl::Hidden, cl::init(15),
    cl::desc("The minimum number of instructions a basic block should contain "
             "before being considered medium-sized."));
} // namespace llvm

static cl::opt<unsigned> CallWithManyArgumentsThreshold(
    "call-with-many-arguments-threshold", cl::Hidden, cl::init(4),
    cl::desc("The minimum number of arguments a function call must have before "
             "it is considered having many arguments."));

namespace {
int64_t getNumBlocksFromCond(const BasicBlock &BB) {
  int64_t Ret = 0;
  if (const auto *BI = dyn_cast<BranchInst>(BB.getTerminator())) {
    if (BI->isConditional())
      Ret += BI->getNumSuccessors();
  } else if (const auto *SI = dyn_cast<SwitchInst>(BB.getTerminator())) {
    Ret += (SI->getNumCases() + (nullptr != SI->getDefaultDest()));
  }
  return Ret;
}

int64_t getUses(const Function &F) {
  return ((!F.hasLocalLinkage()) ? 1 : 0) + F.getNumUses();
}
} // namespace

void FunctionPropertiesInfo::reIncludeBB(const BasicBlock &BB) {
  updateForBB(BB, +1);
}

void FunctionPropertiesInfo::updateForBB(const BasicBlock &BB,
                                         int64_t Direction) {
  assert(Direction == 1 || Direction == -1);
  BasicBlockCount += Direction;
  BlocksReachedFromConditionalInstruction +=
      (Direction * getNumBlocksFromCond(BB));
  for (const auto &I : BB) {
    if (auto *CS = dyn_cast<CallBase>(&I)) {
      const auto *Callee = CS->getCalledFunction();
      if (Callee && !Callee->isIntrinsic() && !Callee->isDeclaration())
        DirectCallsToDefinedFunctions += Direction;
    }
    if (I.getOpcode() == Instruction::Load) {
      LoadInstCount += Direction;
    } else if (I.getOpcode() == Instruction::Store) {
      StoreInstCount += Direction;
    }
  }
  TotalInstructionCount += Direction * BB.sizeWithoutDebug();

  if (EnableDetailedFunctionProperties) {
    unsigned SuccessorCount = succ_size(&BB);
    if (SuccessorCount == 1)
      BasicBlocksWithSingleSuccessor += Direction;
    else if (SuccessorCount == 2)
      BasicBlocksWithTwoSuccessors += Direction;
    else if (SuccessorCount > 2)
      BasicBlocksWithMoreThanTwoSuccessors += Direction;

    unsigned PredecessorCount = pred_size(&BB);
    if (PredecessorCount == 1)
      BasicBlocksWithSinglePredecessor += Direction;
    else if (PredecessorCount == 2)
      BasicBlocksWithTwoPredecessors += Direction;
    else if (PredecessorCount > 2)
      BasicBlocksWithMoreThanTwoPredecessors += Direction;

    if (TotalInstructionCount > BigBasicBlockInstructionThreshold)
      BigBasicBlocks += Direction;
    else if (TotalInstructionCount > MediumBasicBlockInstructionThreshold)
      MediumBasicBlocks += Direction;
    else
      SmallBasicBlocks += Direction;

    // Calculate critical edges by looking through all successors of a basic
    // block that has multiple successors and finding ones that have multiple
    // predecessors, which represent critical edges.
    if (SuccessorCount > 1) {
      for (const auto *Successor : successors(&BB)) {
        if (pred_size(Successor) > 1)
          CriticalEdgeCount += Direction;
      }
    }

    ControlFlowEdgeCount += Direction * SuccessorCount;

    if (const auto *BI = dyn_cast<BranchInst>(BB.getTerminator())) {
      if (!BI->isConditional())
        UnconditionalBranchCount += Direction;
    }

    for (const Instruction &I : BB.instructionsWithoutDebug()) {
      if (I.isCast())
        CastInstructionCount += Direction;

      if (I.getType()->isFloatTy())
        FloatingPointInstructionCount += Direction;
      else if (I.getType()->isIntegerTy())
        IntegerInstructionCount += Direction;

      if (isa<IntrinsicInst>(I))
        ++IntrinsicCount;

      if (const auto *Call = dyn_cast<CallInst>(&I)) {
        if (Call->isIndirectCall())
          IndirectCallCount += Direction;
        else
          DirectCallCount += Direction;

        if (Call->getType()->isIntegerTy())
          CallReturnsIntegerCount += Direction;
        else if (Call->getType()->isFloatingPointTy())
          CallReturnsFloatCount += Direction;
        else if (Call->getType()->isPointerTy())
          CallReturnsPointerCount += Direction;
        else if (Call->getType()->isVectorTy()) {
          if (Call->getType()->getScalarType()->isIntegerTy())
            CallReturnsVectorIntCount += Direction;
          else if (Call->getType()->getScalarType()->isFloatingPointTy())
            CallReturnsVectorFloatCount += Direction;
          else if (Call->getType()->getScalarType()->isPointerTy())
            CallReturnsVectorPointerCount += Direction;
        }

        if (Call->arg_size() > CallWithManyArgumentsThreshold)
          CallWithManyArgumentsCount += Direction;

        for (const auto &Arg : Call->args()) {
          if (Arg->getType()->isPointerTy()) {
            CallWithPointerArgumentCount += Direction;
            break;
          }
        }
      }

#define COUNT_OPERAND(OPTYPE)                                                  \
  if (isa<OPTYPE>(Operand)) {                                                  \
    OPTYPE##OperandCount += Direction;                                         \
    continue;                                                                  \
  }

      for (unsigned int OperandIndex = 0; OperandIndex < I.getNumOperands();
           ++OperandIndex) {
        Value *Operand = I.getOperand(OperandIndex);
        COUNT_OPERAND(GlobalValue)
        COUNT_OPERAND(ConstantInt)
        COUNT_OPERAND(ConstantFP)
        COUNT_OPERAND(Constant)
        COUNT_OPERAND(Instruction)
        COUNT_OPERAND(BasicBlock)
        COUNT_OPERAND(InlineAsm)
        COUNT_OPERAND(Argument)

        // We only get to this point if we haven't matched any of the other
        // operand types.
        UnknownOperandCount += Direction;
      }

#undef CHECK_OPERAND
    }
  }
}

void FunctionPropertiesInfo::updateAggregateStats(const Function &F,
                                                  const LoopInfo &LI) {

  Uses = getUses(F);
  TopLevelLoopCount = llvm::size(LI);
  MaxLoopDepth = 0;
  std::deque<const Loop *> Worklist;
  llvm::append_range(Worklist, LI);
  while (!Worklist.empty()) {
    const auto *L = Worklist.front();
    MaxLoopDepth =
        std::max(MaxLoopDepth, static_cast<int64_t>(L->getLoopDepth()));
    Worklist.pop_front();
    llvm::append_range(Worklist, L->getSubLoops());
  }
}

FunctionPropertiesInfo FunctionPropertiesInfo::getFunctionPropertiesInfo(
    Function &F, FunctionAnalysisManager &FAM) {
  return getFunctionPropertiesInfo(F, FAM.getResult<DominatorTreeAnalysis>(F),
                                   FAM.getResult<LoopAnalysis>(F));
}

FunctionPropertiesInfo FunctionPropertiesInfo::getFunctionPropertiesInfo(
    const Function &F, const DominatorTree &DT, const LoopInfo &LI) {

  FunctionPropertiesInfo FPI;
  for (const auto &BB : F)
    if (DT.isReachableFromEntry(&BB))
      FPI.reIncludeBB(BB);
  FPI.updateAggregateStats(F, LI);
  return FPI;
}

void FunctionPropertiesInfo::print(raw_ostream &OS) const {
#define PRINT_PROPERTY(PROP_NAME) OS << #PROP_NAME ": " << PROP_NAME << "\n";

  PRINT_PROPERTY(BasicBlockCount)
  PRINT_PROPERTY(BlocksReachedFromConditionalInstruction)
  PRINT_PROPERTY(Uses)
  PRINT_PROPERTY(DirectCallsToDefinedFunctions)
  PRINT_PROPERTY(LoadInstCount)
  PRINT_PROPERTY(StoreInstCount)
  PRINT_PROPERTY(MaxLoopDepth)
  PRINT_PROPERTY(TopLevelLoopCount)
  PRINT_PROPERTY(TotalInstructionCount)

  if (EnableDetailedFunctionProperties) {
    PRINT_PROPERTY(BasicBlocksWithSingleSuccessor)
    PRINT_PROPERTY(BasicBlocksWithTwoSuccessors)
    PRINT_PROPERTY(BasicBlocksWithMoreThanTwoSuccessors)
    PRINT_PROPERTY(BasicBlocksWithSinglePredecessor)
    PRINT_PROPERTY(BasicBlocksWithTwoPredecessors)
    PRINT_PROPERTY(BasicBlocksWithMoreThanTwoPredecessors)
    PRINT_PROPERTY(BigBasicBlocks)
    PRINT_PROPERTY(MediumBasicBlocks)
    PRINT_PROPERTY(SmallBasicBlocks)
    PRINT_PROPERTY(CastInstructionCount)
    PRINT_PROPERTY(FloatingPointInstructionCount)
    PRINT_PROPERTY(IntegerInstructionCount)
    PRINT_PROPERTY(ConstantIntOperandCount)
    PRINT_PROPERTY(ConstantFPOperandCount)
    PRINT_PROPERTY(ConstantOperandCount)
    PRINT_PROPERTY(InstructionOperandCount)
    PRINT_PROPERTY(BasicBlockOperandCount)
    PRINT_PROPERTY(GlobalValueOperandCount)
    PRINT_PROPERTY(InlineAsmOperandCount)
    PRINT_PROPERTY(ArgumentOperandCount)
    PRINT_PROPERTY(UnknownOperandCount)
    PRINT_PROPERTY(CriticalEdgeCount)
    PRINT_PROPERTY(ControlFlowEdgeCount)
    PRINT_PROPERTY(UnconditionalBranchCount)
    PRINT_PROPERTY(IntrinsicCount)
    PRINT_PROPERTY(DirectCallCount)
    PRINT_PROPERTY(IndirectCallCount)
    PRINT_PROPERTY(CallReturnsIntegerCount)
    PRINT_PROPERTY(CallReturnsFloatCount)
    PRINT_PROPERTY(CallReturnsPointerCount)
    PRINT_PROPERTY(CallReturnsVectorIntCount)
    PRINT_PROPERTY(CallReturnsVectorFloatCount)
    PRINT_PROPERTY(CallReturnsVectorPointerCount)
    PRINT_PROPERTY(CallWithManyArgumentsCount)
    PRINT_PROPERTY(CallWithPointerArgumentCount)
  }

#undef PRINT_PROPERTY

  OS << "\n";
}

AnalysisKey FunctionPropertiesAnalysis::Key;

FunctionPropertiesInfo
FunctionPropertiesAnalysis::run(Function &F, FunctionAnalysisManager &FAM) {
  return FunctionPropertiesInfo::getFunctionPropertiesInfo(F, FAM);
}

PreservedAnalyses
FunctionPropertiesPrinterPass::run(Function &F, FunctionAnalysisManager &AM) {
  OS << "Printing analysis results of CFA for function "
     << "'" << F.getName() << "':"
     << "\n";
  AM.getResult<FunctionPropertiesAnalysis>(F).print(OS);
  return PreservedAnalyses::all();
}

FunctionPropertiesUpdater::FunctionPropertiesUpdater(
    FunctionPropertiesInfo &FPI, CallBase &CB)
    : FPI(FPI), CallSiteBB(*CB.getParent()), Caller(*CallSiteBB.getParent()) {
  assert(isa<CallInst>(CB) || isa<InvokeInst>(CB));
  // For BBs that are likely to change, we subtract from feature totals their
  // contribution. Some features, like max loop counts or depths, are left
  // invalid, as they will be updated post-inlining.
  SmallPtrSet<const BasicBlock *, 4> LikelyToChangeBBs;
  // The CB BB will change - it'll either be split or the callee's body (single
  // BB) will be pasted in.
  LikelyToChangeBBs.insert(&CallSiteBB);

  // The caller's entry BB may change due to new alloca instructions.
  LikelyToChangeBBs.insert(&*Caller.begin());

  // The successors may become unreachable in the case of `invoke` inlining.
  // We track successors separately, too, because they form a boundary, together
  // with the CB BB ('Entry') between which the inlined callee will be pasted.
  Successors.insert_range(successors(&CallSiteBB));

  // the outcome of the inlining may be that some edges get lost (DCEd BBs
  // because inlining brought some constant, for example). We don't know which
  // edges will be removed, so we list all of them as potentially removable.
  // Some BBs have (at this point) duplicate edges. Remove duplicates, otherwise
  // the DT updater will not apply changes correctly.
  DenseSet<const BasicBlock *> Inserted;
  for (auto *Succ : successors(&CallSiteBB))
    if (Inserted.insert(Succ).second)
      DomTreeUpdates.emplace_back(DominatorTree::UpdateKind::Delete,
                                  const_cast<BasicBlock *>(&CallSiteBB),
                                  const_cast<BasicBlock *>(Succ));
  // Reuse Inserted (which has some allocated capacity at this point) below, if
  // we have an invoke.
  Inserted.clear();
  // Inlining only handles invoke and calls. If this is an invoke, and inlining
  // it pulls another invoke, the original landing pad may get split, so as to
  // share its content with other potential users. So the edge up to which we
  // need to invalidate and then re-account BB data is the successors of the
  // current landing pad. We can leave the current lp, too - if it doesn't get
  // split, then it will be the place traversal stops. Either way, the
  // discounted BBs will be checked if reachable and re-added.
  if (const auto *II = dyn_cast<InvokeInst>(&CB)) {
    const auto *UnwindDest = II->getUnwindDest();
    Successors.insert_range(successors(UnwindDest));
    // Same idea as above, we pretend we lose all these edges.
    for (auto *Succ : successors(UnwindDest))
      if (Inserted.insert(Succ).second)
        DomTreeUpdates.emplace_back(DominatorTree::UpdateKind::Delete,
                                    const_cast<BasicBlock *>(UnwindDest),
                                    const_cast<BasicBlock *>(Succ));
  }

  // Exclude the CallSiteBB, if it happens to be its own successor (1-BB loop).
  // We are only interested in BBs the graph moves past the callsite BB to
  // define the frontier past which we don't want to re-process BBs. Including
  // the callsite BB in this case would prematurely stop the traversal in
  // finish().
  Successors.erase(&CallSiteBB);

  LikelyToChangeBBs.insert_range(Successors);

  // Commit the change. While some of the BBs accounted for above may play dual
  // role - e.g. caller's entry BB may be the same as the callsite BB - set
  // insertion semantics make sure we account them once. This needs to be
  // followed in `finish`, too.
  for (const auto *BB : LikelyToChangeBBs)
    FPI.updateForBB(*BB, -1);
}

DominatorTree &FunctionPropertiesUpdater::getUpdatedDominatorTree(
    FunctionAnalysisManager &FAM) const {
  auto &DT =
      FAM.getResult<DominatorTreeAnalysis>(const_cast<Function &>(Caller));

  SmallVector<DominatorTree::UpdateType, 2> FinalDomTreeUpdates;

  DenseSet<const BasicBlock *> Inserted;
  for (auto *Succ : successors(&CallSiteBB))
    if (Inserted.insert(Succ).second)
      FinalDomTreeUpdates.push_back({DominatorTree::UpdateKind::Insert,
                                     const_cast<BasicBlock *>(&CallSiteBB),
                                     const_cast<BasicBlock *>(Succ)});

  // Perform the deletes last, so that any new nodes connected to nodes
  // participating in the edge deletion are known to the DT.
  for (auto &Upd : DomTreeUpdates)
    if (!llvm::is_contained(successors(Upd.getFrom()), Upd.getTo()))
      FinalDomTreeUpdates.push_back(Upd);

  DT.applyUpdates(FinalDomTreeUpdates);
#ifdef EXPENSIVE_CHECKS
  assert(DT.verify(DominatorTree::VerificationLevel::Full));
#endif
  return DT;
}

void FunctionPropertiesUpdater::finish(FunctionAnalysisManager &FAM) const {
  // Update feature values from the BBs that were copied from the callee, or
  // might have been modified because of inlining. The latter have been
  // subtracted in the FunctionPropertiesUpdater ctor.
  // There could be successors that were reached before but now are only
  // reachable from elsewhere in the CFG.
  // One example is the following diamond CFG (lines are arrows pointing down):
  //    A
  //  /   \
  // B     C
  // |     |
  // |     D
  // |     |
  // |     E
  //  \   /
  //    F
  // There's a call site in C that is inlined. Upon doing that, it turns out
  // it expands to
  //   call void @llvm.trap()
  //   unreachable
  // F isn't reachable from C anymore, but we did discount it when we set up
  // FunctionPropertiesUpdater, so we need to re-include it here.
  // At the same time, D and E were reachable before, but now are not anymore,
  // so we need to leave D out (we discounted it at setup), and explicitly
  // remove E.
  SetVector<const BasicBlock *> Reinclude;
  SetVector<const BasicBlock *> Unreachable;
  auto &DT = getUpdatedDominatorTree(FAM);

  if (&CallSiteBB != &*Caller.begin())
    Reinclude.insert(&*Caller.begin());

  // Distribute the successors to the 2 buckets.
  for (const auto *Succ : Successors)
    if (DT.isReachableFromEntry(Succ))
      Reinclude.insert(Succ);
    else
      Unreachable.insert(Succ);

  // For reinclusion, we want to stop at the reachable successors, who are at
  // the beginning of the worklist; but, starting from the callsite bb and
  // ending at those successors, we also want to perform a traversal.
  // IncludeSuccessorsMark is the index after which we include successors.
  const auto IncludeSuccessorsMark = Reinclude.size();
  bool CSInsertion = Reinclude.insert(&CallSiteBB);
  (void)CSInsertion;
  assert(CSInsertion);
  for (size_t I = 0; I < Reinclude.size(); ++I) {
    const auto *BB = Reinclude[I];
    FPI.reIncludeBB(*BB);
    if (I >= IncludeSuccessorsMark)
      Reinclude.insert_range(successors(BB));
  }

  // For exclusion, we don't need to exclude the set of BBs that were successors
  // before and are now unreachable, because we already did that at setup. For
  // the rest, as long as a successor is unreachable, we want to explicitly
  // exclude it.
  const auto AlreadyExcludedMark = Unreachable.size();
  for (size_t I = 0; I < Unreachable.size(); ++I) {
    const auto *U = Unreachable[I];
    if (I >= AlreadyExcludedMark)
      FPI.updateForBB(*U, -1);
    for (const auto *Succ : successors(U))
      if (!DT.isReachableFromEntry(Succ))
        Unreachable.insert(Succ);
  }

  const auto &LI = FAM.getResult<LoopAnalysis>(const_cast<Function &>(Caller));
  FPI.updateAggregateStats(Caller, LI);
#ifdef EXPENSIVE_CHECKS
  assert(isUpdateValid(Caller, FPI, FAM));
#endif
}

bool FunctionPropertiesUpdater::isUpdateValid(Function &F,
                                              const FunctionPropertiesInfo &FPI,
                                              FunctionAnalysisManager &FAM) {
  if (!FAM.getResult<DominatorTreeAnalysis>(F).verify(
          DominatorTree::VerificationLevel::Full))
    return false;
  DominatorTree DT(F);
  LoopInfo LI(DT);
  auto Fresh = FunctionPropertiesInfo::getFunctionPropertiesInfo(F, DT, LI);
  return FPI == Fresh;
}