HexagonLoopIdiomRecognition.cpp | Explore in Territory

//===- HexagonLoopIdiomRecognition.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
//
//===----------------------------------------------------------------------===//

#include "HexagonLoopIdiomRecognition.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopAnalysisManager.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/IntrinsicsHexagon.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/KnownBits.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/TargetParser/Triple.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iterator>
#include <map>
#include <set>
#include <utility>
#include <vector>

#define DEBUG_TYPE …

usingnamespacellvm;

static cl::opt<bool> DisableMemcpyIdiom("disable-memcpy-idiom",
  cl::Hidden, cl::init(false),
  cl::desc("Disable generation of memcpy in loop idiom recognition"));

static cl::opt<bool> DisableMemmoveIdiom("disable-memmove-idiom",
  cl::Hidden, cl::init(false),
  cl::desc("Disable generation of memmove in loop idiom recognition"));

static cl::opt<unsigned> RuntimeMemSizeThreshold("runtime-mem-idiom-threshold",
  cl::Hidden, cl::init(0), cl::desc("Threshold (in bytes) for the runtime "
  "check guarding the memmove."));

static cl::opt<unsigned> CompileTimeMemSizeThreshold(
  "compile-time-mem-idiom-threshold", cl::Hidden, cl::init(64),
  cl::desc("Threshold (in bytes) to perform the transformation, if the "
    "runtime loop count (mem transfer size) is known at compile-time."));

static cl::opt<bool> OnlyNonNestedMemmove("only-nonnested-memmove-idiom",
  cl::Hidden, cl::init(true),
  cl::desc("Only enable generating memmove in non-nested loops"));

static cl::opt<bool> HexagonVolatileMemcpy(
    "disable-hexagon-volatile-memcpy", cl::Hidden, cl::init(false),
    cl::desc("Enable Hexagon-specific memcpy for volatile destination."));

static cl::opt<unsigned> SimplifyLimit("hlir-simplify-limit", cl::init(10000),
  cl::Hidden, cl::desc("Maximum number of simplification steps in HLIR"));

static const char *HexagonVolatileMemcpyName
  = …;


namespace llvm {

void initializeHexagonLoopIdiomRecognizeLegacyPassPass(PassRegistry &);
Pass *createHexagonLoopIdiomPass();

} // end namespace llvm

namespace {

class HexagonLoopIdiomRecognize { … };

class HexagonLoopIdiomRecognizeLegacyPass : public LoopPass { … };

struct Simplifier { … };

  struct PE { … };

  LLVM_ATTRIBUTE_USED
  raw_ostream &operator<<(raw_ostream &OS, const PE &P) { … }

} // end anonymous namespace

char HexagonLoopIdiomRecognizeLegacyPass::ID = …;

INITIALIZE_PASS_BEGIN(HexagonLoopIdiomRecognizeLegacyPass, "hexagon-loop-idiom",
                      "Recognize Hexagon-specific loop idioms", false, false)
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
INITIALIZE_PASS_DEPENDENCY(LCSSAWrapperPass)
INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
INITIALIZE_PASS_END(HexagonLoopIdiomRecognizeLegacyPass, "hexagon-loop-idiom",
                    "Recognize Hexagon-specific loop idioms", false, false)

template <typename FuncT>
void Simplifier::Context::traverse(Value *V, FuncT F) { … }

void Simplifier::Context::print(raw_ostream &OS, const Value *V) const { … }

void Simplifier::Context::initialize(Instruction *Exp) { … }

void Simplifier::Context::record(Value *V) { … }

void Simplifier::Context::use(Value *V) { … }

void Simplifier::Context::unuse(Value *V) { … }

Value *Simplifier::Context::subst(Value *Tree, Value *OldV, Value *NewV) { … }

void Simplifier::Context::replace(Value *OldV, Value *NewV) { … }

void Simplifier::Context::cleanup() { … }

bool Simplifier::Context::equal(const Instruction *I,
                                const Instruction *J) const { … }

Value *Simplifier::Context::find(Value *Tree, Value *Sub) const { … }

void Simplifier::Context::link(Instruction *I, BasicBlock *B,
      BasicBlock::iterator At) { … }

Value *Simplifier::Context::materialize(BasicBlock *B,
      BasicBlock::iterator At) { … }

Value *Simplifier::simplify(Context &C) { … }

//===----------------------------------------------------------------------===//
//
//          Implementation of PolynomialMultiplyRecognize
//
//===----------------------------------------------------------------------===//

namespace {

  class PolynomialMultiplyRecognize { … };

} // end anonymous namespace

Value *PolynomialMultiplyRecognize::getCountIV(BasicBlock *BB) { … }

static void replaceAllUsesOfWithIn(Value *I, Value *J, BasicBlock *BB) { … }

bool PolynomialMultiplyRecognize::matchLeftShift(SelectInst *SelI,
      Value *CIV, ParsedValues &PV) { … }

bool PolynomialMultiplyRecognize::matchRightShift(SelectInst *SelI,
      ParsedValues &PV) { … }

bool PolynomialMultiplyRecognize::scanSelect(SelectInst *SelI,
      BasicBlock *LoopB, BasicBlock *PrehB, Value *CIV, ParsedValues &PV,
      bool PreScan) { … }

bool PolynomialMultiplyRecognize::isPromotableTo(Value *Val,
      IntegerType *DestTy) { … }

void PolynomialMultiplyRecognize::promoteTo(Instruction *In,
      IntegerType *DestTy, BasicBlock *LoopB) { … }

bool PolynomialMultiplyRecognize::promoteTypes(BasicBlock *LoopB,
      BasicBlock *ExitB) { … }

bool PolynomialMultiplyRecognize::findCycle(Value *Out, Value *In,
      ValueSeq &Cycle) { … }

void PolynomialMultiplyRecognize::classifyCycle(Instruction *DivI,
      ValueSeq &Cycle, ValueSeq &Early, ValueSeq &Late) { … }

bool PolynomialMultiplyRecognize::classifyInst(Instruction *UseI,
      ValueSeq &Early, ValueSeq &Late) { … }

bool PolynomialMultiplyRecognize::commutesWithShift(Instruction *I) { … }

bool PolynomialMultiplyRecognize::highBitsAreZero(Value *V,
      unsigned IterCount) { … }

bool PolynomialMultiplyRecognize::keepsHighBitsZero(Value *V,
      unsigned IterCount) { … }

bool PolynomialMultiplyRecognize::isOperandShifted(Instruction *I, Value *Op) { … }

bool PolynomialMultiplyRecognize::convertShiftsToLeft(BasicBlock *LoopB,
      BasicBlock *ExitB, unsigned IterCount) { … }

void PolynomialMultiplyRecognize::cleanupLoopBody(BasicBlock *LoopB) { … }

unsigned PolynomialMultiplyRecognize::getInverseMxN(unsigned QP) { … }

Value *PolynomialMultiplyRecognize::generate(BasicBlock::iterator At,
      ParsedValues &PV) { … }

static bool hasZeroSignBit(const Value *V) { … }

void PolynomialMultiplyRecognize::setupPreSimplifier(Simplifier &S) { … }

void PolynomialMultiplyRecognize::setupPostSimplifier(Simplifier &S) { … }

bool PolynomialMultiplyRecognize::recognize() { … }

int HexagonLoopIdiomRecognize::getSCEVStride(const SCEVAddRecExpr *S) { … }

bool HexagonLoopIdiomRecognize::isLegalStore(Loop *CurLoop, StoreInst *SI) { … }

/// mayLoopAccessLocation - Return true if the specified loop might access the
/// specified pointer location, which is a loop-strided access.  The 'Access'
/// argument specifies what the verboten forms of access are (read or write).
static bool
mayLoopAccessLocation(Value *Ptr, ModRefInfo Access, Loop *L,
                      const SCEV *BECount, unsigned StoreSize,
                      AliasAnalysis &AA,
                      SmallPtrSetImpl<Instruction *> &Ignored) { … }

void HexagonLoopIdiomRecognize::collectStores(Loop *CurLoop, BasicBlock *BB,
      SmallVectorImpl<StoreInst*> &Stores) { … }

bool HexagonLoopIdiomRecognize::processCopyingStore(Loop *CurLoop,
      StoreInst *SI, const SCEV *BECount) { … }

// Check if the instructions in Insts, together with their dependencies
// cover the loop in the sense that the loop could be safely eliminated once
// the instructions in Insts are removed.
bool HexagonLoopIdiomRecognize::coverLoop(Loop *L,
      SmallVectorImpl<Instruction*> &Insts) const { … }

/// runOnLoopBlock - Process the specified block, which lives in a counted loop
/// with the specified backedge count.  This block is known to be in the current
/// loop and not in any subloops.
bool HexagonLoopIdiomRecognize::runOnLoopBlock(Loop *CurLoop, BasicBlock *BB,
      const SCEV *BECount, SmallVectorImpl<BasicBlock*> &ExitBlocks) { … }

bool HexagonLoopIdiomRecognize::runOnCountableLoop(Loop *L) { … }

bool HexagonLoopIdiomRecognize::run(Loop *L) { … }

bool HexagonLoopIdiomRecognizeLegacyPass::runOnLoop(Loop *L,
                                                    LPPassManager &LPM) { … }

Pass *llvm::createHexagonLoopIdiomPass() { … }

PreservedAnalyses
HexagonLoopIdiomRecognitionPass::run(Loop &L, LoopAnalysisManager &AM,
                                     LoopStandardAnalysisResults &AR,
                                     LPMUpdater &U) { … }
llvm/llvm/lib/Target/Hexagon/HexagonLoopIdiomRecognition.cpp
