HexagonHardwareLoops.cpp | Explore in Territory

//===- HexagonHardwareLoops.cpp - Identify and generate hardware loops ----===//
//
// 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 pass identifies loops where we can generate the Hexagon hardware
// loop instruction.  The hardware loop can perform loop branches with a
// zero-cycle overhead.
//
// The pattern that defines the induction variable can changed depending on
// prior optimizations.  For example, the IndVarSimplify phase run by 'opt'
// normalizes induction variables, and the Loop Strength Reduction pass
// run by 'llc' may also make changes to the induction variable.
// The pattern detected by this phase is due to running Strength Reduction.
//
// Criteria for hardware loops:
//  - Countable loops (w/ ind. var for a trip count)
//  - Assumes loops are normalized by IndVarSimplify
//  - Try inner-most loops first
//  - No function calls in loops.
//
//===----------------------------------------------------------------------===//

#include "HexagonInstrInfo.h"
#include "HexagonSubtarget.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <cstdint>
#include <cstdlib>
#include <iterator>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <vector>

usingnamespacellvm;

#define DEBUG_TYPE …

#ifndef NDEBUG
static cl::opt<int> HWLoopLimit("hexagon-max-hwloop", cl::Hidden, cl::init(-1));

// Option to create preheader only for a specific function.
static cl::opt<std::string> PHFn("hexagon-hwloop-phfn", cl::Hidden,
                                 cl::init(""));
#endif

// Option to create a preheader if one doesn't exist.
static cl::opt<bool> HWCreatePreheader("hexagon-hwloop-preheader",
    cl::Hidden, cl::init(true),
    cl::desc("Add a preheader to a hardware loop if one doesn't exist"));

// Turn it off by default. If a preheader block is not created here, the
// software pipeliner may be unable to find a block suitable to serve as
// a preheader. In that case SWP will not run.
static cl::opt<bool> SpecPreheader("hwloop-spec-preheader", cl::Hidden,
                                   cl::desc("Allow speculation of preheader "
                                            "instructions"));

STATISTIC(NumHWLoops, "Number of loops converted to hardware loops");

namespace llvm {

  FunctionPass *createHexagonHardwareLoops();
  void initializeHexagonHardwareLoopsPass(PassRegistry&);

} // end namespace llvm

namespace {

  class CountValue;

  struct HexagonHardwareLoops : public MachineFunctionPass { … };

  char HexagonHardwareLoops::ID = …;
#ifndef NDEBUG
  int HexagonHardwareLoops::Counter = 0;
#endif

  /// Abstraction for a trip count of a loop. A smaller version
  /// of the MachineOperand class without the concerns of changing the
  /// operand representation.
  class CountValue { … };

} // end anonymous namespace

INITIALIZE_PASS_BEGIN(HexagonHardwareLoops, "hwloops",
                      "Hexagon Hardware Loops", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
INITIALIZE_PASS_END(HexagonHardwareLoops, "hwloops",
                    "Hexagon Hardware Loops", false, false)

FunctionPass *llvm::createHexagonHardwareLoops() { … }

bool HexagonHardwareLoops::runOnMachineFunction(MachineFunction &MF) { … }

bool HexagonHardwareLoops::findInductionRegister(MachineLoop *L,
                                                 Register &Reg,
                                                 int64_t &IVBump,
                                                 MachineInstr *&IVOp
                                                 ) const { … }

// Return the comparison kind for the specified opcode.
HexagonHardwareLoops::Comparison::Kind
HexagonHardwareLoops::getComparisonKind(unsigned CondOpc,
                                        MachineOperand *InitialValue,
                                        const MachineOperand *EndValue,
                                        int64_t IVBump) const { … }

/// Analyze the statements in a loop to determine if the loop has
/// a computable trip count and, if so, return a value that represents
/// the trip count expression.
///
/// This function iterates over the phi nodes in the loop to check for
/// induction variable patterns that are used in the calculation for
/// the number of time the loop is executed.
CountValue *HexagonHardwareLoops::getLoopTripCount(MachineLoop *L,
    SmallVectorImpl<MachineInstr *> &OldInsts) { … }

/// Helper function that returns the expression that represents the
/// number of times a loop iterates.  The function takes the operands that
/// represent the loop start value, loop end value, and induction value.
/// Based upon these operands, the function attempts to compute the trip count.
CountValue *HexagonHardwareLoops::computeCount(MachineLoop *Loop,
                                               const MachineOperand *Start,
                                               const MachineOperand *End,
                                               Register IVReg,
                                               int64_t IVBump,
                                               Comparison::Kind Cmp) const { … }

/// Return true if the operation is invalid within hardware loop.
bool HexagonHardwareLoops::isInvalidLoopOperation(const MachineInstr *MI,
                                                  bool IsInnerHWLoop) const { … }

/// Return true if the loop contains an instruction that inhibits
/// the use of the hardware loop instruction.
bool HexagonHardwareLoops::containsInvalidInstruction(MachineLoop *L,
    bool IsInnerHWLoop) const { … }

/// Returns true if the instruction is dead.  This was essentially
/// copied from DeadMachineInstructionElim::isDead, but with special cases
/// for inline asm, physical registers and instructions with side effects
/// removed.
bool HexagonHardwareLoops::isDead(const MachineInstr *MI,
                              SmallVectorImpl<MachineInstr *> &DeadPhis) const { … }

void HexagonHardwareLoops::removeIfDead(MachineInstr *MI) { … }

/// Check if the loop is a candidate for converting to a hardware
/// loop.  If so, then perform the transformation.
///
/// This function works on innermost loops first.  A loop can be converted
/// if it is a counting loop; either a register value or an immediate.
///
/// The code makes several assumptions about the representation of the loop
/// in llvm.
bool HexagonHardwareLoops::convertToHardwareLoop(MachineLoop *L,
                                                 bool &RecL0used,
                                                 bool &RecL1used) { … }

bool HexagonHardwareLoops::orderBumpCompare(MachineInstr *BumpI,
                                            MachineInstr *CmpI) { … }

/// This function is required to break recursion. Visiting phis in a loop may
/// result in recursion during compilation. We break the recursion by making
/// sure that we visit a MachineOperand and its definition in a
/// MachineInstruction only once. If we attempt to visit more than once, then
/// there is recursion, and will return false.
bool HexagonHardwareLoops::isLoopFeeder(MachineLoop *L, MachineBasicBlock *A,
                                        MachineInstr *MI,
                                        const MachineOperand *MO,
                                        LoopFeederMap &LoopFeederPhi) const { … }

/// Return true if a Phi may generate a value that can underflow.
/// This function calls loopCountMayWrapOrUnderFlow for each Phi operand.
bool HexagonHardwareLoops::phiMayWrapOrUnderflow(
    MachineInstr *Phi, const MachineOperand *EndVal, MachineBasicBlock *MBB,
    MachineLoop *L, LoopFeederMap &LoopFeederPhi) const { … }

/// Return true if the induction variable can underflow in the first iteration.
/// An example, is an initial unsigned value that is 0 and is decrement in the
/// first itertion of a do-while loop.  In this case, we cannot generate a
/// hardware loop because the endloop instruction does not decrement the loop
/// counter if it is <= 1. We only need to perform this analysis if the
/// initial value is a register.
///
/// This function assumes the initial value may underfow unless proven
/// otherwise. If the type is signed, then we don't care because signed
/// underflow is undefined. We attempt to prove the initial value is not
/// zero by perfoming a crude analysis of the loop counter. This function
/// checks if the initial value is used in any comparison prior to the loop
/// and, if so, assumes the comparison is a range check. This is inexact,
/// but will catch the simple cases.
bool HexagonHardwareLoops::loopCountMayWrapOrUnderFlow(
    const MachineOperand *InitVal, const MachineOperand *EndVal,
    MachineBasicBlock *MBB, MachineLoop *L,
    LoopFeederMap &LoopFeederPhi) const { … }

bool HexagonHardwareLoops::checkForImmediate(const MachineOperand &MO,
                                             int64_t &Val) const { … }

void HexagonHardwareLoops::setImmediate(MachineOperand &MO, int64_t Val) { … }

bool HexagonHardwareLoops::fixupInductionVariable(MachineLoop *L) { … }

/// createPreheaderForLoop - Create a preheader for a given loop.
MachineBasicBlock *HexagonHardwareLoops::createPreheaderForLoop(
      MachineLoop *L) { … }
llvm/llvm/lib/Target/Hexagon/HexagonHardwareLoops.cpp
