File Manager

003 File Manager

Current Path: /usr/src/contrib/llvm-project/llvm/lib/CodeGen

usr / src / contrib / llvm-project / llvm / lib / CodeGen /

📁 ..
📄 AggressiveAntiDepBreaker.cpp(37.23 KB)
📄 AggressiveAntiDepBreaker.h(6.8 KB)
📄 AllocationOrder.cpp(1.96 KB)
📄 AllocationOrder.h(2.96 KB)
📄 Analysis.cpp(32.62 KB)
📁 AsmPrinter
📄 AtomicExpandPass.cpp(71.86 KB)
📄 BBSectionsPrepare.cpp(18.8 KB)
📄 BasicTargetTransformInfo.cpp(1.53 KB)
📄 BranchFolding.cpp(77.92 KB)
📄 BranchFolding.h(7.36 KB)
📄 BranchRelaxation.cpp(19.45 KB)
📄 BreakFalseDeps.cpp(9.79 KB)
📄 BuiltinGCs.cpp(4.88 KB)
📄 CFGuardLongjmp.cpp(3.73 KB)
📄 CFIInstrInserter.cpp(17.53 KB)
📄 CalcSpillWeights.cpp(10.22 KB)
📄 CallingConvLower.cpp(10.4 KB)
📄 CodeGen.cpp(5.28 KB)
📄 CodeGenPrepare.cpp(295.01 KB)
📄 CommandFlags.cpp(24.89 KB)
📄 CriticalAntiDepBreaker.cpp(27.91 KB)
📄 CriticalAntiDepBreaker.h(4.22 KB)
📄 DFAPacketizer.cpp(10.91 KB)
📄 DeadMachineInstructionElim.cpp(6.52 KB)
📄 DetectDeadLanes.cpp(20.74 KB)
📄 DwarfEHPrepare.cpp(9.01 KB)
📄 EarlyIfConversion.cpp(37.51 KB)
📄 EdgeBundles.cpp(3.21 KB)
📄 ExecutionDomainFix.cpp(14.67 KB)
📄 ExpandMemCmp.cpp(33.66 KB)
📄 ExpandPostRAPseudos.cpp(7.28 KB)
📄 ExpandReductions.cpp(7.23 KB)
📄 FEntryInserter.cpp(1.81 KB)
📄 FaultMaps.cpp(4.99 KB)
📄 FinalizeISel.cpp(2.65 KB)
📄 FixupStatepointCallerSaved.cpp(11.06 KB)
📄 FuncletLayout.cpp(2.21 KB)
📄 GCMetadata.cpp(5.1 KB)
📄 GCMetadataPrinter.cpp(748 B)
📄 GCRootLowering.cpp(11.46 KB)
📄 GCStrategy.cpp(708 B)
📁 GlobalISel
📄 GlobalMerge.cpp(24.52 KB)
📄 HardwareLoops.cpp(18.44 KB)
📄 IfConversion.cpp(89.43 KB)
📄 ImplicitNullChecks.cpp(25.14 KB)
📄 IndirectBrExpandPass.cpp(7.79 KB)
📄 InlineSpiller.cpp(58.24 KB)
📄 InterferenceCache.cpp(8.83 KB)
📄 InterferenceCache.h(7.22 KB)
📄 InterleavedAccessPass.cpp(16.59 KB)
📄 InterleavedLoadCombinePass.cpp(42.35 KB)
📄 IntrinsicLowering.cpp(17.08 KB)
📄 LLVMTargetMachine.cpp(10.25 KB)
📄 LatencyPriorityQueue.cpp(5.64 KB)
📄 LazyMachineBlockFrequencyInfo.cpp(3.36 KB)
📄 LexicalScopes.cpp(12.16 KB)
📄 LiveDebugValues.cpp(78.98 KB)
📄 LiveDebugVariables.cpp(51.79 KB)
📄 LiveDebugVariables.h(2.15 KB)
📄 LiveInterval.cpp(46.67 KB)
📄 LiveIntervalCalc.cpp(7.62 KB)
📄 LiveIntervalUnion.cpp(6.36 KB)
📄 LiveIntervals.cpp(64.59 KB)
📄 LivePhysRegs.cpp(11.08 KB)
📄 LiveRangeCalc.cpp(15.72 KB)
📄 LiveRangeEdit.cpp(17.03 KB)
📄 LiveRangeShrink.cpp(8.69 KB)
📄 LiveRangeUtils.h(2.12 KB)
📄 LiveRegMatrix.cpp(7.47 KB)
📄 LiveRegUnits.cpp(4.72 KB)
📄 LiveStacks.cpp(2.95 KB)
📄 LiveVariables.cpp(30.26 KB)
📄 LocalStackSlotAllocation.cpp(17.26 KB)
📄 LoopTraversal.cpp(2.89 KB)
📄 LowLevelType.cpp(1.93 KB)
📄 LowerEmuTLS.cpp(5.66 KB)
📄 MBFIWrapper.cpp(1.57 KB)
📄 MIRCanonicalizerPass.cpp(12.46 KB)
📄 MIRNamerPass.cpp(2.16 KB)
📁 MIRParser
📄 MIRPrinter.cpp(32.67 KB)
📄 MIRPrintingPass.cpp(1.99 KB)
📄 MIRVRegNamerUtils.cpp(6.04 KB)
📄 MIRVRegNamerUtils.h(3.25 KB)
📄 MachineBasicBlock.cpp(50.47 KB)
📄 MachineBlockFrequencyInfo.cpp(10.13 KB)
📄 MachineBlockPlacement.cpp(137.61 KB)
📄 MachineBranchProbabilityInfo.cpp(3.5 KB)
📄 MachineCSE.cpp(31.82 KB)
📄 MachineCombiner.cpp(28.13 KB)
📄 MachineCopyPropagation.cpp(29.21 KB)
📄 MachineDebugify.cpp(6.47 KB)
📄 MachineDominanceFrontier.cpp(1.83 KB)
📄 MachineDominators.cpp(4.86 KB)
📄 MachineFrameInfo.cpp(9.77 KB)
📄 MachineFunction.cpp(42.97 KB)
📄 MachineFunctionPass.cpp(4.78 KB)
📄 MachineFunctionPrinterPass.cpp(2.3 KB)
📄 MachineInstr.cpp(76.39 KB)
📄 MachineInstrBundle.cpp(11.49 KB)
📄 MachineLICM.cpp(57.05 KB)
📄 MachineLoopInfo.cpp(4.98 KB)
📄 MachineLoopUtils.cpp(5.16 KB)
📄 MachineModuleInfo.cpp(9.9 KB)
📄 MachineModuleInfoImpls.cpp(1.5 KB)
📄 MachineOperand.cpp(39.6 KB)
📄 MachineOptimizationRemarkEmitter.cpp(3.29 KB)
📄 MachineOutliner.cpp(42.13 KB)
📄 MachinePipeliner.cpp(111.33 KB)
📄 MachinePostDominators.cpp(2.42 KB)
📄 MachineRegionInfo.cpp(4.75 KB)
📄 MachineRegisterInfo.cpp(22.97 KB)
📄 MachineSSAUpdater.cpp(12.99 KB)
📄 MachineScheduler.cpp(136.89 KB)
📄 MachineSink.cpp(51.94 KB)
📄 MachineSizeOpts.cpp(8.76 KB)
📄 MachineStripDebug.cpp(3.76 KB)
📄 MachineTraceMetrics.cpp(49.58 KB)
📄 MachineVerifier.cpp(107.98 KB)
📄 MacroFusion.cpp(7.55 KB)
📄 ModuloSchedule.cpp(85.09 KB)
📄 NonRelocatableStringpool.cpp(1.65 KB)
📄 OptimizePHIs.cpp(6.7 KB)
📄 PHIElimination.cpp(27.73 KB)
📄 PHIEliminationUtils.cpp(2.56 KB)
📄 PHIEliminationUtils.h(972 B)
📄 ParallelCG.cpp(3.71 KB)
📄 PatchableFunction.cpp(3.44 KB)
📄 PeepholeOptimizer.cpp(78.41 KB)
📄 PostRAHazardRecognizer.cpp(3.5 KB)
📄 PostRASchedulerList.cpp(24.31 KB)
📄 PreISelIntrinsicLowering.cpp(7.91 KB)
📄 ProcessImplicitDefs.cpp(5.4 KB)
📄 PrologEpilogInserter.cpp(50.45 KB)
📄 PseudoSourceValue.cpp(4.71 KB)
📄 RDFGraph.cpp(58.39 KB)
📄 RDFLiveness.cpp(40.7 KB)
📄 RDFRegisters.cpp(11.29 KB)
📄 ReachingDefAnalysis.cpp(21.74 KB)
📄 RegAllocBase.cpp(6.31 KB)
📄 RegAllocBase.h(4.63 KB)
📄 RegAllocBasic.cpp(11.33 KB)
📄 RegAllocFast.cpp(45.78 KB)
📄 RegAllocGreedy.cpp(123.32 KB)
📄 RegAllocPBQP.cpp(33.14 KB)
📄 RegUsageInfoCollector.cpp(7.39 KB)
📄 RegUsageInfoPropagate.cpp(5.07 KB)
📄 RegisterClassInfo.cpp(6.62 KB)
📄 RegisterCoalescer.cpp(151.71 KB)
📄 RegisterCoalescer.h(4.04 KB)
📄 RegisterPressure.cpp(48.86 KB)
📄 RegisterScavenging.cpp(27.48 KB)
📄 RegisterUsageInfo.cpp(3.18 KB)
📄 RenameIndependentSubregs.cpp(14.79 KB)
📄 ResetMachineFunctionPass.cpp(3.48 KB)
📄 SafeStack.cpp(34.12 KB)
📄 SafeStackLayout.cpp(5.3 KB)
📄 SafeStackLayout.h(2.41 KB)
📄 ScalarizeMaskedMemIntrin.cpp(31.46 KB)
📄 ScheduleDAG.cpp(21.34 KB)
📄 ScheduleDAGInstrs.cpp(54.59 KB)
📄 ScheduleDAGPrinter.cpp(3.21 KB)
📄 ScoreboardHazardRecognizer.cpp(7.96 KB)
📁 SelectionDAG
📄 ShadowStackGCLowering.cpp(14.16 KB)
📄 ShrinkWrap.cpp(23.03 KB)
📄 SjLjEHPrepare.cpp(18.93 KB)
📄 SlotIndexes.cpp(9.35 KB)
📄 SpillPlacement.cpp(12.58 KB)
📄 SpillPlacement.h(6.67 KB)
📄 SplitKit.cpp(66.39 KB)
📄 SplitKit.h(23.7 KB)
📄 StackColoring.cpp(49.03 KB)
📄 StackMapLivenessAnalysis.cpp(6.16 KB)
📄 StackMaps.cpp(19.74 KB)
📄 StackProtector.cpp(22.94 KB)
📄 StackSlotColoring.cpp(17.12 KB)
📄 SwiftErrorValueTracking.cpp(11.37 KB)
📄 SwitchLoweringUtils.cpp(18.33 KB)
📄 TailDuplication.cpp(3.32 KB)
📄 TailDuplicator.cpp(38.29 KB)
📄 TargetFrameLoweringImpl.cpp(6.24 KB)
📄 TargetInstrInfo.cpp(51.1 KB)
📄 TargetLoweringBase.cpp(82.53 KB)
📄 TargetLoweringObjectFileImpl.cpp(80.52 KB)
📄 TargetOptionsImpl.cpp(2 KB)
📄 TargetPassConfig.cpp(48.89 KB)
📄 TargetRegisterInfo.cpp(19.15 KB)
📄 TargetSchedule.cpp(13.16 KB)
📄 TargetSubtargetInfo.cpp(1.89 KB)
📄 TwoAddressInstructionPass.cpp(62.08 KB)
📄 TypePromotion.cpp(32.46 KB)
📄 UnreachableBlockElim.cpp(7.48 KB)
📄 ValueTypes.cpp(19.87 KB)
📄 VirtRegMap.cpp(21.4 KB)
📄 WasmEHPrepare.cpp(17.48 KB)
📄 WinEHPrepare.cpp(51.16 KB)
📄 XRayInstrumentation.cpp(9.66 KB)

Editing: ReachingDefAnalysis.cpp

//===---- ReachingDefAnalysis.cpp - Reaching Def Analysis ---*- C++ -*-----===//
//
// 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 "llvm/ADT/SmallSet.h"
#include "llvm/CodeGen/LivePhysRegs.h"
#include "llvm/CodeGen/ReachingDefAnalysis.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/Support/Debug.h"

using namespace llvm;

#define DEBUG_TYPE "reaching-deps-analysis"

char ReachingDefAnalysis::ID = 0;
INITIALIZE_PASS(ReachingDefAnalysis, DEBUG_TYPE, "ReachingDefAnalysis", false,
                true)

static bool isValidReg(const MachineOperand &MO) {
  return MO.isReg() && MO.getReg();
}

static bool isValidRegUse(const MachineOperand &MO) {
  return isValidReg(MO) && MO.isUse();
}

static bool isValidRegUseOf(const MachineOperand &MO, int PhysReg) {
  return isValidRegUse(MO) && MO.getReg() == PhysReg;
}

static bool isValidRegDef(const MachineOperand &MO) {
  return isValidReg(MO) && MO.isDef();
}

static bool isValidRegDefOf(const MachineOperand &MO, int PhysReg) {
  return isValidRegDef(MO) && MO.getReg() == PhysReg;
}

void ReachingDefAnalysis::enterBasicBlock(MachineBasicBlock *MBB) {
  unsigned MBBNumber = MBB->getNumber();
  assert(MBBNumber < MBBReachingDefs.size() &&
         "Unexpected basic block number.");
  MBBReachingDefs[MBBNumber].resize(NumRegUnits);

// Reset instruction counter in each basic block.
  CurInstr = 0;

// Set up LiveRegs to represent registers entering MBB.
  // Default values are 'nothing happened a long time ago'.
  if (LiveRegs.empty())
    LiveRegs.assign(NumRegUnits, ReachingDefDefaultVal);

// This is the entry block.
  if (MBB->pred_empty()) {
    for (const auto &LI : MBB->liveins()) {
      for (MCRegUnitIterator Unit(LI.PhysReg, TRI); Unit.isValid(); ++Unit) {
        // Treat function live-ins as if they were defined just before the first
        // instruction.  Usually, function arguments are set up immediately
        // before the call.
        if (LiveRegs[*Unit] != -1) {
          LiveRegs[*Unit] = -1;
          MBBReachingDefs[MBBNumber][*Unit].push_back(-1);
        }
      }
    }
    LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << ": entry\n");
    return;
  }

// Try to coalesce live-out registers from predecessors.
  for (MachineBasicBlock *pred : MBB->predecessors()) {
    assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
           "Should have pre-allocated MBBInfos for all MBBs");
    const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
    // Incoming is null if this is a backedge from a BB
    // we haven't processed yet
    if (Incoming.empty())
      continue;

// Find the most recent reaching definition from a predecessor.
    for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit)
      LiveRegs[Unit] = std::max(LiveRegs[Unit], Incoming[Unit]);
  }

// Insert the most recent reaching definition we found.
  for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit)
    if (LiveRegs[Unit] != ReachingDefDefaultVal)
      MBBReachingDefs[MBBNumber][Unit].push_back(LiveRegs[Unit]);
}

void ReachingDefAnalysis::leaveBasicBlock(MachineBasicBlock *MBB) {
  assert(!LiveRegs.empty() && "Must enter basic block first.");
  unsigned MBBNumber = MBB->getNumber();
  assert(MBBNumber < MBBOutRegsInfos.size() &&
         "Unexpected basic block number.");
  // Save register clearances at end of MBB - used by enterBasicBlock().
  MBBOutRegsInfos[MBBNumber] = LiveRegs;

// While processing the basic block, we kept `Def` relative to the start
  // of the basic block for convenience. However, future use of this information
  // only cares about the clearance from the end of the block, so adjust
  // everything to be relative to the end of the basic block.
  for (int &OutLiveReg : MBBOutRegsInfos[MBBNumber])
    if (OutLiveReg != ReachingDefDefaultVal)
      OutLiveReg -= CurInstr;
  LiveRegs.clear();
}

void ReachingDefAnalysis::processDefs(MachineInstr *MI) {
  assert(!MI->isDebugInstr() && "Won't process debug instructions");

unsigned MBBNumber = MI->getParent()->getNumber();
  assert(MBBNumber < MBBReachingDefs.size() &&
         "Unexpected basic block number.");

for (auto &MO : MI->operands()) {
    if (!isValidRegDef(MO))
      continue;
    for (MCRegUnitIterator Unit(MO.getReg(), TRI); Unit.isValid(); ++Unit) {
      // This instruction explicitly defines the current reg unit.
      LLVM_DEBUG(dbgs() << printReg(*Unit, TRI) << ":\t" << CurInstr
                        << '\t' << *MI);

// How many instructions since this reg unit was last written?
      if (LiveRegs[*Unit] != CurInstr) {
        LiveRegs[*Unit] = CurInstr;
        MBBReachingDefs[MBBNumber][*Unit].push_back(CurInstr);
      }
    }
  }
  InstIds[MI] = CurInstr;
  ++CurInstr;
}

void ReachingDefAnalysis::reprocessBasicBlock(MachineBasicBlock *MBB) {
  unsigned MBBNumber = MBB->getNumber();
  assert(MBBNumber < MBBReachingDefs.size() &&
         "Unexpected basic block number.");

// Count number of non-debug instructions for end of block adjustment.
  int NumInsts = 0;
  for (const MachineInstr &MI : *MBB)
    if (!MI.isDebugInstr())
      NumInsts++;

// When reprocessing a block, the only thing we need to do is check whether
  // there is now a more recent incoming reaching definition from a predecessor.
  for (MachineBasicBlock *pred : MBB->predecessors()) {
    assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
           "Should have pre-allocated MBBInfos for all MBBs");
    const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
    // Incoming may be empty for dead predecessors.
    if (Incoming.empty())
      continue;

for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit) {
      int Def = Incoming[Unit];
      if (Def == ReachingDefDefaultVal)
        continue;

auto Start = MBBReachingDefs[MBBNumber][Unit].begin();
      if (Start != MBBReachingDefs[MBBNumber][Unit].end() && *Start < 0) {
        if (*Start >= Def)
          continue;

// Update existing reaching def from predecessor to a more recent one.
        *Start = Def;
      } else {
        // Insert new reaching def from predecessor.
        MBBReachingDefs[MBBNumber][Unit].insert(Start, Def);
      }

// Update reaching def at end of of BB. Keep in mind that these are
      // adjusted relative to the end of the basic block.
      if (MBBOutRegsInfos[MBBNumber][Unit] < Def - NumInsts)
        MBBOutRegsInfos[MBBNumber][Unit] = Def - NumInsts;
    }
  }
}

void ReachingDefAnalysis::processBasicBlock(
    const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
  MachineBasicBlock *MBB = TraversedMBB.MBB;
  LLVM_DEBUG(dbgs() << printMBBReference(*MBB)
                    << (!TraversedMBB.IsDone ? ": incomplete\n"
                                             : ": all preds known\n"));

if (!TraversedMBB.PrimaryPass) {
    // Reprocess MBB that is part of a loop.
    reprocessBasicBlock(MBB);
    return;
  }

enterBasicBlock(MBB);
  for (MachineInstr &MI : *MBB) {
    if (!MI.isDebugInstr())
      processDefs(&MI);
  }
  leaveBasicBlock(MBB);
}

bool ReachingDefAnalysis::runOnMachineFunction(MachineFunction &mf) {
  MF = &mf;
  TRI = MF->getSubtarget().getRegisterInfo();
  LLVM_DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n");
  init();
  traverse();
  return false;
}

void ReachingDefAnalysis::releaseMemory() {
  // Clear the internal vectors.
  MBBOutRegsInfos.clear();
  MBBReachingDefs.clear();
  InstIds.clear();
  LiveRegs.clear();
}

void ReachingDefAnalysis::reset() {
  releaseMemory();
  init();
  traverse();
}

void ReachingDefAnalysis::init() {
  NumRegUnits = TRI->getNumRegUnits();
  MBBReachingDefs.resize(MF->getNumBlockIDs());
  // Initialize the MBBOutRegsInfos
  MBBOutRegsInfos.resize(MF->getNumBlockIDs());
  LoopTraversal Traversal;
  TraversedMBBOrder = Traversal.traverse(*MF);
}

void ReachingDefAnalysis::traverse() {
  // Traverse the basic blocks.
  for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder)
    processBasicBlock(TraversedMBB);
#ifndef NDEBUG
  // Make sure reaching defs are sorted and unique.
  for (MBBDefsInfo &MBBDefs : MBBReachingDefs) {
    for (MBBRegUnitDefs &RegUnitDefs : MBBDefs) {
      int LastDef = ReachingDefDefaultVal;
      for (int Def : RegUnitDefs) {
        assert(Def > LastDef && "Defs must be sorted and unique");
        LastDef = Def;
      }
    }
  }
#endif
}

int ReachingDefAnalysis::getReachingDef(MachineInstr *MI, int PhysReg) const {
  assert(InstIds.count(MI) && "Unexpected machine instuction.");
  int InstId = InstIds.lookup(MI);
  int DefRes = ReachingDefDefaultVal;
  unsigned MBBNumber = MI->getParent()->getNumber();
  assert(MBBNumber < MBBReachingDefs.size() &&
         "Unexpected basic block number.");
  int LatestDef = ReachingDefDefaultVal;
  for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
    for (int Def : MBBReachingDefs[MBBNumber][*Unit]) {
      if (Def >= InstId)
        break;
      DefRes = Def;
    }
    LatestDef = std::max(LatestDef, DefRes);
  }
  return LatestDef;
}

MachineInstr* ReachingDefAnalysis::getReachingLocalMIDef(MachineInstr *MI,
                                                    int PhysReg) const {
  return getInstFromId(MI->getParent(), getReachingDef(MI, PhysReg));
}

bool ReachingDefAnalysis::hasSameReachingDef(MachineInstr *A, MachineInstr *B,
                                             int PhysReg) const {
  MachineBasicBlock *ParentA = A->getParent();
  MachineBasicBlock *ParentB = B->getParent();
  if (ParentA != ParentB)
    return false;

return getReachingDef(A, PhysReg) == getReachingDef(B, PhysReg);
}

MachineInstr *ReachingDefAnalysis::getInstFromId(MachineBasicBlock *MBB,
                                                 int InstId) const {
  assert(static_cast<size_t>(MBB->getNumber()) < MBBReachingDefs.size() &&
         "Unexpected basic block number.");
  assert(InstId < static_cast<int>(MBB->size()) &&
         "Unexpected instruction id.");

if (InstId < 0)
    return nullptr;

for (auto &MI : *MBB) {
    auto F = InstIds.find(&MI);
    if (F != InstIds.end() && F->second == InstId)
      return &MI;
  }

return nullptr;
}

int
ReachingDefAnalysis::getClearance(MachineInstr *MI, MCPhysReg PhysReg) const {
  assert(InstIds.count(MI) && "Unexpected machine instuction.");
  return InstIds.lookup(MI) - getReachingDef(MI, PhysReg);
}

bool
ReachingDefAnalysis::hasLocalDefBefore(MachineInstr *MI, int PhysReg) const {
  return getReachingDef(MI, PhysReg) >= 0;
}

void ReachingDefAnalysis::getReachingLocalUses(MachineInstr *Def, int PhysReg,
                                               InstSet &Uses) const {
  MachineBasicBlock *MBB = Def->getParent();
  MachineBasicBlock::iterator MI = MachineBasicBlock::iterator(Def);
  while (++MI != MBB->end()) {
    if (MI->isDebugInstr())
      continue;

// If/when we find a new reaching def, we know that there's no more uses
    // of 'Def'.
    if (getReachingLocalMIDef(&*MI, PhysReg) != Def)
      return;

for (auto &MO : MI->operands()) {
      if (!isValidRegUseOf(MO, PhysReg))
        continue;

Uses.insert(&*MI);
      if (MO.isKill())
        return;
    }
  }
}

bool
ReachingDefAnalysis::getLiveInUses(MachineBasicBlock *MBB, int PhysReg,
                                   InstSet &Uses) const {
  for (auto &MI : *MBB) {
    if (MI.isDebugInstr())
      continue;
    for (auto &MO : MI.operands()) {
      if (!isValidRegUseOf(MO, PhysReg))
        continue;
      if (getReachingDef(&MI, PhysReg) >= 0)
        return false;
      Uses.insert(&MI);
    }
  }
  return isReachingDefLiveOut(&MBB->back(), PhysReg);
}

void
ReachingDefAnalysis::getGlobalUses(MachineInstr *MI, int PhysReg,
                                   InstSet &Uses) const {
  MachineBasicBlock *MBB = MI->getParent();

// Collect the uses that each def touches within the block.
  getReachingLocalUses(MI, PhysReg, Uses);

// Handle live-out values.
  if (auto *LiveOut = getLocalLiveOutMIDef(MI->getParent(), PhysReg)) {
    if (LiveOut != MI)
      return;

SmallVector<MachineBasicBlock*, 4> ToVisit;
    ToVisit.insert(ToVisit.begin(), MBB->successors().begin(),
                   MBB->successors().end());
    SmallPtrSet<MachineBasicBlock*, 4>Visited;
    while (!ToVisit.empty()) {
      MachineBasicBlock *MBB = ToVisit.back();
      ToVisit.pop_back();
      if (Visited.count(MBB) || !MBB->isLiveIn(PhysReg))
        continue;
      if (getLiveInUses(MBB, PhysReg, Uses))
        ToVisit.insert(ToVisit.end(), MBB->successors().begin(),
                       MBB->successors().end());
      Visited.insert(MBB);
    }
  }
}

void ReachingDefAnalysis::getLiveOuts(MachineBasicBlock *MBB, int PhysReg,
                                      InstSet &Defs) const {
  SmallPtrSet<MachineBasicBlock*, 2> VisitedBBs;
  getLiveOuts(MBB, PhysReg, Defs, VisitedBBs);
}

void
ReachingDefAnalysis::getLiveOuts(MachineBasicBlock *MBB, int PhysReg,
                                 InstSet &Defs, BlockSet &VisitedBBs) const {
  if (VisitedBBs.count(MBB))
    return;

VisitedBBs.insert(MBB);
  LivePhysRegs LiveRegs(*TRI);
  LiveRegs.addLiveOuts(*MBB);
  if (!LiveRegs.contains(PhysReg))
    return;

if (auto *Def = getLocalLiveOutMIDef(MBB, PhysReg))
    Defs.insert(Def);
  else
    for (auto *Pred : MBB->predecessors())
      getLiveOuts(Pred, PhysReg, Defs, VisitedBBs);
}

MachineInstr *ReachingDefAnalysis::getUniqueReachingMIDef(MachineInstr *MI,
                                                          int PhysReg) const {
  // If there's a local def before MI, return it.
  MachineInstr *LocalDef = getReachingLocalMIDef(MI, PhysReg);
  if (LocalDef && InstIds.lookup(LocalDef) < InstIds.lookup(MI))
    return LocalDef;

SmallPtrSet<MachineBasicBlock*, 4> VisitedBBs;
  SmallPtrSet<MachineInstr*, 2> Incoming;
  for (auto *Pred : MI->getParent()->predecessors())
    getLiveOuts(Pred, PhysReg, Incoming, VisitedBBs);

// If we have a local def and an incoming instruction, then there's not a
  // unique instruction def.
  if (!Incoming.empty() && LocalDef)
    return nullptr;
  else if (Incoming.size() == 1)
    return *Incoming.begin();
  else
    return LocalDef;
}

MachineInstr *ReachingDefAnalysis::getMIOperand(MachineInstr *MI,
                                                unsigned Idx) const {
  assert(MI->getOperand(Idx).isReg() && "Expected register operand");
  return getUniqueReachingMIDef(MI, MI->getOperand(Idx).getReg());
}

MachineInstr *ReachingDefAnalysis::getMIOperand(MachineInstr *MI,
                                                MachineOperand &MO) const {
  assert(MO.isReg() && "Expected register operand");
  return getUniqueReachingMIDef(MI, MO.getReg());
}

bool ReachingDefAnalysis::isRegUsedAfter(MachineInstr *MI, int PhysReg) const {
  MachineBasicBlock *MBB = MI->getParent();
  LivePhysRegs LiveRegs(*TRI);
  LiveRegs.addLiveOuts(*MBB);

// Yes if the register is live out of the basic block.
  if (LiveRegs.contains(PhysReg))
    return true;

// Walk backwards through the block to see if the register is live at some
  // point.
  for (auto Last = MBB->rbegin(), End = MBB->rend(); Last != End; ++Last) {
    LiveRegs.stepBackward(*Last);
    if (LiveRegs.contains(PhysReg))
      return InstIds.lookup(&*Last) > InstIds.lookup(MI);
  }
  return false;
}

bool ReachingDefAnalysis::isRegDefinedAfter(MachineInstr *MI,
                                            int PhysReg) const {
  MachineBasicBlock *MBB = MI->getParent();
  if (getReachingDef(MI, PhysReg) != getReachingDef(&MBB->back(), PhysReg))
    return true;

if (auto *Def = getLocalLiveOutMIDef(MBB, PhysReg))
    return Def == getReachingLocalMIDef(MI, PhysReg);

return false;
}

bool
ReachingDefAnalysis::isReachingDefLiveOut(MachineInstr *MI, int PhysReg) const {
  MachineBasicBlock *MBB = MI->getParent();
  LivePhysRegs LiveRegs(*TRI);
  LiveRegs.addLiveOuts(*MBB);
  if (!LiveRegs.contains(PhysReg))
    return false;

MachineInstr *Last = &MBB->back();
  int Def = getReachingDef(MI, PhysReg);
  if (getReachingDef(Last, PhysReg) != Def)
    return false;

// Finally check that the last instruction doesn't redefine the register.
  for (auto &MO : Last->operands())
    if (isValidRegDefOf(MO, PhysReg))
      return false;

return true;
}

MachineInstr* ReachingDefAnalysis::getLocalLiveOutMIDef(MachineBasicBlock *MBB,
                                                        int PhysReg) const {
  LivePhysRegs LiveRegs(*TRI);
  LiveRegs.addLiveOuts(*MBB);
  if (!LiveRegs.contains(PhysReg))
    return nullptr;

MachineInstr *Last = &MBB->back();
  int Def = getReachingDef(Last, PhysReg);
  for (auto &MO : Last->operands())
    if (isValidRegDefOf(MO, PhysReg))
      return Last;

return Def < 0 ? nullptr : getInstFromId(MBB, Def);
}

static bool mayHaveSideEffects(MachineInstr &MI) {
  return MI.mayLoadOrStore() || MI.mayRaiseFPException() ||
         MI.hasUnmodeledSideEffects() || MI.isTerminator() ||
         MI.isCall() || MI.isBarrier() || MI.isBranch() || MI.isReturn();
}

// Can we safely move 'From' to just before 'To'? To satisfy this, 'From' must
// not define a register that is used by any instructions, after and including,
// 'To'. These instructions also must not redefine any of Froms operands.
template<typename Iterator>
bool ReachingDefAnalysis::isSafeToMove(MachineInstr *From,
                                       MachineInstr *To) const {
  if (From->getParent() != To->getParent())
    return false;

SmallSet<int, 2> Defs;
  // First check that From would compute the same value if moved.
  for (auto &MO : From->operands()) {
    if (!isValidReg(MO))
      continue;
    if (MO.isDef())
      Defs.insert(MO.getReg());
    else if (!hasSameReachingDef(From, To, MO.getReg()))
      return false;
  }

// Now walk checking that the rest of the instructions will compute the same
  // value and that we're not overwriting anything. Don't move the instruction
  // past any memory, control-flow or other ambiguous instructions.
  for (auto I = ++Iterator(From), E = Iterator(To); I != E; ++I) {
    if (mayHaveSideEffects(*I))
      return false;
    for (auto &MO : I->operands())
      if (MO.isReg() && MO.getReg() && Defs.count(MO.getReg()))
        return false;
  }
  return true;
}

bool ReachingDefAnalysis::isSafeToMoveForwards(MachineInstr *From,
                                               MachineInstr *To) const {
  return isSafeToMove<MachineBasicBlock::reverse_iterator>(From, To);
}

bool ReachingDefAnalysis::isSafeToMoveBackwards(MachineInstr *From,
                                                MachineInstr *To) const {
  return isSafeToMove<MachineBasicBlock::iterator>(From, To);
}

bool ReachingDefAnalysis::isSafeToRemove(MachineInstr *MI,
                                         InstSet &ToRemove) const {
  SmallPtrSet<MachineInstr*, 1> Ignore;
  SmallPtrSet<MachineInstr*, 2> Visited;
  return isSafeToRemove(MI, Visited, ToRemove, Ignore);
}

bool
ReachingDefAnalysis::isSafeToRemove(MachineInstr *MI, InstSet &ToRemove,
                                    InstSet &Ignore) const {
  SmallPtrSet<MachineInstr*, 2> Visited;
  return isSafeToRemove(MI, Visited, ToRemove, Ignore);
}

bool
ReachingDefAnalysis::isSafeToRemove(MachineInstr *MI, InstSet &Visited,
                                    InstSet &ToRemove, InstSet &Ignore) const {
  if (Visited.count(MI) || Ignore.count(MI))
    return true;
  else if (mayHaveSideEffects(*MI)) {
    // Unless told to ignore the instruction, don't remove anything which has
    // side effects.
    return false;
  }

Visited.insert(MI);
  for (auto &MO : MI->operands()) {
    if (!isValidRegDef(MO))
      continue;

SmallPtrSet<MachineInstr*, 4> Uses;
    getGlobalUses(MI, MO.getReg(), Uses);

for (auto I : Uses) {
      if (Ignore.count(I) || ToRemove.count(I))
        continue;
      if (!isSafeToRemove(I, Visited, ToRemove, Ignore))
        return false;
    }
  }
  ToRemove.insert(MI);
  return true;
}

void ReachingDefAnalysis::collectKilledOperands(MachineInstr *MI,
                                                InstSet &Dead) const {
  Dead.insert(MI);
  auto IsDead = [this, &Dead](MachineInstr *Def, int PhysReg) {
    unsigned LiveDefs = 0;
    for (auto &MO : Def->operands()) {
      if (!isValidRegDef(MO))
        continue;
      if (!MO.isDead())
        ++LiveDefs;
    }

if (LiveDefs > 1)
      return false;

SmallPtrSet<MachineInstr*, 4> Uses;
    getGlobalUses(Def, PhysReg, Uses);
    for (auto *Use : Uses)
      if (!Dead.count(Use))
        return false;
    return true;
  };

for (auto &MO : MI->operands()) {
    if (!isValidRegUse(MO))
      continue;
    if (MachineInstr *Def = getMIOperand(MI, MO))
      if (IsDead(Def, MO.getReg()))
        collectKilledOperands(Def, Dead);
  }
}

bool ReachingDefAnalysis::isSafeToDefRegAt(MachineInstr *MI,
                                           int PhysReg) const {
  SmallPtrSet<MachineInstr*, 1> Ignore;
  return isSafeToDefRegAt(MI, PhysReg, Ignore);
}

bool ReachingDefAnalysis::isSafeToDefRegAt(MachineInstr *MI, int PhysReg,
                                           InstSet &Ignore) const {
  // Check for any uses of the register after MI.
  if (isRegUsedAfter(MI, PhysReg)) {
    if (auto *Def = getReachingLocalMIDef(MI, PhysReg)) {
      SmallPtrSet<MachineInstr*, 2> Uses;
      getReachingLocalUses(Def, PhysReg, Uses);
      for (auto *Use : Uses)
        if (!Ignore.count(Use))
          return false;
    } else
      return false;
  }

MachineBasicBlock *MBB = MI->getParent();
  // Check for any defs after MI.
  if (isRegDefinedAfter(MI, PhysReg)) {
    auto I = MachineBasicBlock::iterator(MI);
    for (auto E = MBB->end(); I != E; ++I) {
      if (Ignore.count(&*I))
        continue;
      for (auto &MO : I->operands())
        if (isValidRegDefOf(MO, PhysReg))
          return false;
    }
  }
  return true;
}

003 File Manager

Editing: ReachingDefAnalysis.cpp

Upload File

Create Folder