HexagonExpandCondsets.cpp | Explore in Territory

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

// Replace mux instructions with the corresponding legal instructions.
// It is meant to work post-SSA, but still on virtual registers. It was
// originally placed between register coalescing and machine instruction
// scheduler.
// In this place in the optimization sequence, live interval analysis had
// been performed, and the live intervals should be preserved. A large part
// of the code deals with preserving the liveness information.
//
// Liveness tracking aside, the main functionality of this pass is divided
// into two steps. The first step is to replace an instruction
//   %0 = C2_mux %1, %2, %3
// with a pair of conditional transfers
//   %0 = A2_tfrt %1, %2
//   %0 = A2_tfrf %1, %3
// It is the intention that the execution of this pass could be terminated
// after this step, and the code generated would be functionally correct.
//
// If the uses of the source values %1 and %2 are kills, and their
// definitions are predicable, then in the second step, the conditional
// transfers will then be rewritten as predicated instructions. E.g.
//   %0 = A2_or %1, %2
//   %3 = A2_tfrt %99, killed %0
// will be rewritten as
//   %3 = A2_port %99, %1, %2
//
// This replacement has two variants: "up" and "down". Consider this case:
//   %0 = A2_or %1, %2
//   ... [intervening instructions] ...
//   %3 = A2_tfrt %99, killed %0
// variant "up":
//   %3 = A2_port %99, %1, %2
//   ... [intervening instructions, %0->vreg3] ...
//   [deleted]
// variant "down":
//   [deleted]
//   ... [intervening instructions] ...
//   %3 = A2_port %99, %1, %2
//
// Both, one or none of these variants may be valid, and checks are made
// to rule out inapplicable variants.
//
// As an additional optimization, before either of the two steps above is
// executed, the pass attempts to coalesce the target register with one of
// the source registers, e.g. given an instruction
//   %3 = C2_mux %0, %1, %2
// %3 will be coalesced with either %1 or %2. If this succeeds,
// the instruction would then be (for example)
//   %3 = C2_mux %0, %3, %2
// and, under certain circumstances, this could result in only one predicated
// instruction:
//   %3 = A2_tfrf %0, %2
//

// Splitting a definition of a register into two predicated transfers
// creates a complication in liveness tracking. Live interval computation
// will see both instructions as actual definitions, and will mark the
// first one as dead. The definition is not actually dead, and this
// situation will need to be fixed. For example:
//   dead %1 = A2_tfrt ...  ; marked as dead
//   %1 = A2_tfrf ...
//
// Since any of the individual predicated transfers may end up getting
// removed (in case it is an identity copy), some pre-existing def may
// be marked as dead after live interval recomputation:
//   dead %1 = ...          ; marked as dead
//   ...
//   %1 = A2_tfrf ...       ; if A2_tfrt is removed
// This case happens if %1 was used as a source in A2_tfrt, which means
// that is it actually live at the A2_tfrf, and so the now dead definition
// of %1 will need to be updated to non-dead at some point.
//
// This issue could be remedied by adding implicit uses to the predicated
// transfers, but this will create a problem with subsequent predication,
// since the transfers will no longer be possible to reorder. To avoid
// that, the initial splitting will not add any implicit uses. These
// implicit uses will be added later, after predication. The extra price,
// however, is that finding the locations where the implicit uses need
// to be added, and updating the live ranges will be more involved.

#include "HexagonInstrInfo.h"
#include "HexagonRegisterInfo.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/CodeGen/LiveInterval.h"
#include "llvm/CodeGen/LiveIntervals.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/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/SlotIndexes.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/Function.h"
#include "llvm/InitializePasses.h"
#include "llvm/MC/LaneBitmask.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <iterator>
#include <map>
#include <set>
#include <utility>

#define DEBUG_TYPE …

usingnamespacellvm;

static cl::opt<unsigned> OptTfrLimit("expand-condsets-tfr-limit",
  cl::init(~0U), cl::Hidden, cl::desc("Max number of mux expansions"));
static cl::opt<unsigned> OptCoaLimit("expand-condsets-coa-limit",
  cl::init(~0U), cl::Hidden, cl::desc("Max number of segment coalescings"));

namespace llvm {

  void initializeHexagonExpandCondsetsPass(PassRegistry&);
  FunctionPass *createHexagonExpandCondsets();

} // end namespace llvm

namespace {

  class HexagonExpandCondsets : public MachineFunctionPass { … };

} // end anonymous namespace

char HexagonExpandCondsets::ID = …;

namespace llvm {

  char &HexagonExpandCondsetsID = …;

} // end namespace llvm

INITIALIZE_PASS_BEGIN(HexagonExpandCondsets, "expand-condsets",
  "Hexagon Expand Condsets", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(SlotIndexesWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LiveIntervalsWrapperPass)
INITIALIZE_PASS_END(HexagonExpandCondsets, "expand-condsets",
  "Hexagon Expand Condsets", false, false)

unsigned HexagonExpandCondsets::getMaskForSub(unsigned Sub) { … }

bool HexagonExpandCondsets::isCondset(const MachineInstr &MI) { … }

LaneBitmask HexagonExpandCondsets::getLaneMask(Register Reg, unsigned Sub) { … }

void HexagonExpandCondsets::addRefToMap(RegisterRef RR, ReferenceMap &Map,
      unsigned Exec) { … }

bool HexagonExpandCondsets::isRefInMap(RegisterRef RR, ReferenceMap &Map,
      unsigned Exec) { … }

void HexagonExpandCondsets::updateKillFlags(Register Reg) { … }

void HexagonExpandCondsets::updateDeadsInRange(Register Reg, LaneBitmask LM,
                                               LiveRange &Range) { … }

void HexagonExpandCondsets::updateDeadFlags(Register Reg) { … }

void HexagonExpandCondsets::recalculateLiveInterval(Register Reg) { … }

void HexagonExpandCondsets::removeInstr(MachineInstr &MI) { … }

void HexagonExpandCondsets::updateLiveness(const std::set<Register> &RegSet,
                                           bool Recalc, bool UpdateKills,
                                           bool UpdateDeads) { … }

void HexagonExpandCondsets::distributeLiveIntervals(
    const std::set<Register> &Regs) { … }

/// Get the opcode for a conditional transfer of the value in SO (source
/// operand). The condition (true/false) is given in Cond.
unsigned HexagonExpandCondsets::getCondTfrOpcode(const MachineOperand &SO,
      bool IfTrue) { … }

/// Generate a conditional transfer, copying the value SrcOp to the
/// destination register DstR:DstSR, and using the predicate register from
/// PredOp. The Cond argument specifies whether the predicate is to be
/// if(PredOp), or if(!PredOp).
MachineInstr *HexagonExpandCondsets::genCondTfrFor(MachineOperand &SrcOp,
      MachineBasicBlock::iterator At,
      unsigned DstR, unsigned DstSR, const MachineOperand &PredOp,
      bool PredSense, bool ReadUndef, bool ImpUse) { … }

/// Replace a MUX instruction MI with a pair A2_tfrt/A2_tfrf. This function
/// performs all necessary changes to complete the replacement.
bool HexagonExpandCondsets::split(MachineInstr &MI,
                                  std::set<Register> &UpdRegs) { … }

bool HexagonExpandCondsets::isPredicable(MachineInstr *MI) { … }

/// Find the reaching definition for a predicated use of RD. The RD is used
/// under the conditions given by PredR and Cond, and this function will ignore
/// definitions that set RD under the opposite conditions.
MachineInstr *HexagonExpandCondsets::getReachingDefForPred(RegisterRef RD,
      MachineBasicBlock::iterator UseIt, unsigned PredR, bool Cond) { … }

/// Check if the instruction MI can be safely moved over a set of instructions
/// whose side-effects (in terms of register defs and uses) are expressed in
/// the maps Defs and Uses. These maps reflect the conditional defs and uses
/// that depend on the same predicate register to allow moving instructions
/// over instructions predicated on the opposite condition.
bool HexagonExpandCondsets::canMoveOver(MachineInstr &MI, ReferenceMap &Defs,
                                        ReferenceMap &Uses) { … }

/// Check if the instruction accessing memory (TheI) can be moved to the
/// location ToI.
bool HexagonExpandCondsets::canMoveMemTo(MachineInstr &TheI, MachineInstr &ToI,
                                         bool IsDown) { … }

/// Generate a predicated version of MI (where the condition is given via
/// PredR and Cond) at the point indicated by Where.
void HexagonExpandCondsets::predicateAt(const MachineOperand &DefOp,
                                        MachineInstr &MI,
                                        MachineBasicBlock::iterator Where,
                                        const MachineOperand &PredOp, bool Cond,
                                        std::set<Register> &UpdRegs) { … }

/// In the range [First, Last], rename all references to the "old" register RO
/// to the "new" register RN, but only in instructions predicated on the given
/// condition.
void HexagonExpandCondsets::renameInRange(RegisterRef RO, RegisterRef RN,
      unsigned PredR, bool Cond, MachineBasicBlock::iterator First,
      MachineBasicBlock::iterator Last) { … }

/// For a given conditional copy, predicate the definition of the source of
/// the copy under the given condition (using the same predicate register as
/// the copy).
bool HexagonExpandCondsets::predicate(MachineInstr &TfrI, bool Cond,
                                      std::set<Register> &UpdRegs) { … }

/// Predicate all cases of conditional copies in the specified block.
bool HexagonExpandCondsets::predicateInBlock(MachineBasicBlock &B,
                                             std::set<Register> &UpdRegs) { … }

bool HexagonExpandCondsets::isIntReg(RegisterRef RR, unsigned &BW) { … }

bool HexagonExpandCondsets::isIntraBlocks(LiveInterval &LI) { … }

bool HexagonExpandCondsets::coalesceRegisters(RegisterRef R1, RegisterRef R2) { … }

/// Attempt to coalesce one of the source registers to a MUX instruction with
/// the destination register. This could lead to having only one predicated
/// instruction in the end instead of two.
bool HexagonExpandCondsets::coalesceSegments(
    const SmallVectorImpl<MachineInstr *> &Condsets,
    std::set<Register> &UpdRegs) { … }

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

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