HexagonEarlyIfConv.cpp | Explore in Territory

//===- HexagonEarlyIfConv.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 implements a Hexagon-specific if-conversion pass that runs on the
// SSA form.
// In SSA it is not straightforward to represent instructions that condi-
// tionally define registers, since a conditionally-defined register may
// only be used under the same condition on which the definition was based.
// To avoid complications of this nature, this patch will only generate
// predicated stores, and speculate other instructions from the "if-conver-
// ted" block.
// The code will recognize CFG patterns where a block with a conditional
// branch "splits" into a "true block" and a "false block". Either of these
// could be omitted (in case of a triangle, for example).
// If after conversion of the side block(s) the CFG allows it, the resul-
// ting blocks may be merged. If the "join" block contained PHI nodes, they
// will be replaced with MUX (or MUX-like) instructions to maintain the
// semantics of the PHI.
//
// Example:
//
//         %40 = L2_loadrub_io killed %39, 1
//         %41 = S2_tstbit_i killed %40, 0
//         J2_jumpt killed %41, <%bb.5>, implicit dead %pc
//         J2_jump <%bb.4>, implicit dead %pc
//     Successors according to CFG: %bb.4(62) %bb.5(62)
//
// %bb.4: derived from LLVM BB %if.then
//     Predecessors according to CFG: %bb.3
//         %11 = A2_addp %6, %10
//         S2_storerd_io %32, 16, %11
//     Successors according to CFG: %bb.5
//
// %bb.5: derived from LLVM BB %if.end
//     Predecessors according to CFG: %bb.3 %bb.4
//         %12 = PHI %6, <%bb.3>, %11, <%bb.4>
//         %13 = A2_addp %7, %12
//         %42 = C2_cmpeqi %9, 10
//         J2_jumpf killed %42, <%bb.3>, implicit dead %pc
//         J2_jump <%bb.6>, implicit dead %pc
//     Successors according to CFG: %bb.6(4) %bb.3(124)
//
// would become:
//
//         %40 = L2_loadrub_io killed %39, 1
//         %41 = S2_tstbit_i killed %40, 0
// spec->  %11 = A2_addp %6, %10
// pred->  S2_pstorerdf_io %41, %32, 16, %11
//         %46 = PS_pselect %41, %6, %11
//         %13 = A2_addp %7, %46
//         %42 = C2_cmpeqi %9, 10
//         J2_jumpf killed %42, <%bb.3>, implicit dead %pc
//         J2_jump <%bb.6>, implicit dead %pc
//     Successors according to CFG: %bb.6 %bb.3

#include "Hexagon.h"
#include "HexagonInstrInfo.h"
#include "HexagonSubtarget.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineBranchProbabilityInfo.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/DebugLoc.h"
#include "llvm/Pass.h"
#include "llvm/Support/BranchProbability.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <iterator>

#define DEBUG_TYPE …

usingnamespacellvm;

namespace llvm {

  FunctionPass *createHexagonEarlyIfConversion();
  void initializeHexagonEarlyIfConversionPass(PassRegistry& Registry);

} // end namespace llvm

static cl::opt<bool> EnableHexagonBP("enable-hexagon-br-prob", cl::Hidden,
  cl::init(true), cl::desc("Enable branch probability info"));
static cl::opt<unsigned> SizeLimit("eif-limit", cl::init(6), cl::Hidden,
  cl::desc("Size limit in Hexagon early if-conversion"));
static cl::opt<bool> SkipExitBranches("eif-no-loop-exit", cl::init(false),
  cl::Hidden, cl::desc("Do not convert branches that may exit the loop"));

namespace {

  struct PrintMB { … };
  raw_ostream &operator<< (raw_ostream &OS, const PrintMB &P) { … }

  struct FlowPattern { … };

  struct PrintFP { … };
  raw_ostream &operator<<(raw_ostream &OS,
                          const PrintFP &P) LLVM_ATTRIBUTE_UNUSED;
  raw_ostream &operator<<(raw_ostream &OS, const PrintFP &P) { … }

  class HexagonEarlyIfConversion : public MachineFunctionPass { … };

} // end anonymous namespace

char HexagonEarlyIfConversion::ID = …;

INITIALIZE_PASS(…)

bool HexagonEarlyIfConversion::isPreheader(const MachineBasicBlock *B) const { … }

bool HexagonEarlyIfConversion::matchFlowPattern(MachineBasicBlock *B,
    MachineLoop *L, FlowPattern &FP) { … }

// KLUDGE: HexagonInstrInfo::analyzeBranch won't work on a block that
// contains EH_LABEL.
bool HexagonEarlyIfConversion::hasEHLabel(const MachineBasicBlock *B) const { … }

// KLUDGE: HexagonInstrInfo::analyzeBranch may be unable to recognize
// that a block can never fall-through.
bool HexagonEarlyIfConversion::hasUncondBranch(const MachineBasicBlock *B)
      const { … }

bool HexagonEarlyIfConversion::isValidCandidate(const MachineBasicBlock *B)
      const { … }

bool HexagonEarlyIfConversion::usesUndefVReg(const MachineInstr *MI) const { … }

bool HexagonEarlyIfConversion::isValid(const FlowPattern &FP) const { … }

unsigned HexagonEarlyIfConversion::computePhiCost(const MachineBasicBlock *B,
      const FlowPattern &FP) const { … }

unsigned HexagonEarlyIfConversion::countPredicateDefs(
      const MachineBasicBlock *B) const { … }

bool HexagonEarlyIfConversion::isProfitable(const FlowPattern &FP) const { … }

bool HexagonEarlyIfConversion::visitBlock(MachineBasicBlock *B,
      MachineLoop *L) { … }

bool HexagonEarlyIfConversion::visitLoop(MachineLoop *L) { … }

bool HexagonEarlyIfConversion::isPredicableStore(const MachineInstr *MI)
      const { … }

bool HexagonEarlyIfConversion::isSafeToSpeculate(const MachineInstr *MI)
      const { … }

bool HexagonEarlyIfConversion::isPredicate(unsigned R) const { … }

unsigned HexagonEarlyIfConversion::getCondStoreOpcode(unsigned Opc,
      bool IfTrue) const { … }

void HexagonEarlyIfConversion::predicateInstr(MachineBasicBlock *ToB,
      MachineBasicBlock::iterator At, MachineInstr *MI,
      unsigned PredR, bool IfTrue) { … }

// Predicate/speculate non-branch instructions from FromB into block ToB.
// Leave the branches alone, they will be handled later. Btw, at this point
// FromB should have at most one branch, and it should be unconditional.
void HexagonEarlyIfConversion::predicateBlockNB(MachineBasicBlock *ToB,
      MachineBasicBlock::iterator At, MachineBasicBlock *FromB,
      unsigned PredR, bool IfTrue) { … }

unsigned HexagonEarlyIfConversion::buildMux(MachineBasicBlock *B,
      MachineBasicBlock::iterator At, const TargetRegisterClass *DRC,
      unsigned PredR, unsigned TR, unsigned TSR, unsigned FR, unsigned FSR) { … }

void HexagonEarlyIfConversion::updatePhiNodes(MachineBasicBlock *WhereB,
      const FlowPattern &FP) { … }

void HexagonEarlyIfConversion::convert(const FlowPattern &FP) { … }

void HexagonEarlyIfConversion::removeBlock(MachineBasicBlock *B) { … }

void HexagonEarlyIfConversion::eliminatePhis(MachineBasicBlock *B) { … }

void HexagonEarlyIfConversion::mergeBlocks(MachineBasicBlock *PredB,
      MachineBasicBlock *SuccB) { … }

void HexagonEarlyIfConversion::simplifyFlowGraph(const FlowPattern &FP) { … }

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

//===----------------------------------------------------------------------===//
//                         Public Constructor Functions
//===----------------------------------------------------------------------===//
FunctionPass *llvm::createHexagonEarlyIfConversion() { … }
llvm/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp
