GCNRematStrategy.h

Go to the documentation of this file.

//===-- GCNRematStrategy.h - Rematerialization strategy -*- 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
//
//===----------------------------------------------------------------------===//
//
/// \file
/// Rematerialization strategy, based on the target-independent rematerializer.
//
//===----------------------------------------------------------------------===//
 
#ifndef LLVM_LIB_TARGET_AMDGPU_GCNREMATSTRATEGY_H
#define LLVM_LIB_TARGET_AMDGPU_GCNREMATSTRATEGY_H
 
#include "GCNRegPressure.h"
#include "SIMachineFunctionInfo.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/CodeGen/Rematerializer.h"
 
namespace llvm {
 
/// Rematerializes registers across code regions to achieve register pressure
/// targets. The strategy updates region boundaries and live-ins/live-outs as it
/// rematerializes. It uses the target independent rematerializers to expose
/// rematerializable registers and perform rematerializations.
///
/// The strategy only supports rematerializing registers that meet all of the
/// following constraints.
/// 1. The register is virtual and has a single defining instruction.
/// 2. The single defining instruction is either deemed rematerializable by the
///    target-independent logic, or if not, has no non-constant and
///    non-ignorable physical register use.
/// 3  The register has no virtual register use whose live range would be
///    extended by the rematerialization.
/// 4. The register has at least one user outside its defining region. If
///    rematerialized, one copy is made per using region and the original
///    register stays if the defining region has users.
/// 5. The register is not used by or using another register that is going to be
///    rematerialized.
class GCNRematStrategy {
  using RegionBoundaries = Rematerializer::RegionBoundaries;
  using RegisterIdx = Rematerializer::RegisterIdx;
 
public:
  /// Creates a strategy that can rematerialize across \p Regions whose live-ins
  /// \p LiveIns and live-outs \p LiveOuts are provided. The underlying
  /// rematerializer is created and initialized.
  GCNRematStrategy(MachineFunction &MF,
                   MutableArrayRef<RegionBoundaries> Regions,
                   MutableArrayRef<GCNRPTracker::LiveRegSet> LiveIns,
                   MutableArrayRef<GCNRPTracker::LiveRegSet> LiveOuts,
                   LiveIntervals &LIS, const MachineBlockFrequencyInfo &MBFI)
      : Regions(Regions, LiveIns, LiveOuts, LIS, MBFI, MF.getRegInfo()),
        Remater(MF, Regions, LIS), MF(MF), MRI(MF.getRegInfo()), LIS(LIS) {}
 
  /// Rematerializes with the goal of reducing the maximum pressure in all \ref
  /// Regions to \p MaxSGPRs SGPRs and \p MaxVGPRs VGPRs. \p SpillReduction
  /// indicates whether that register pressure target allows to reduce spilling,
  /// which influences rematerialization decisions. Regions which are
  /// rematerialized from/into/over have their corresponding index set in \p
  /// AffectedRegions. When not null, \p MaxPressure provides initial maximum
  /// pressure for all regions and contains updated maximum pressures when the
  /// function returns.
  void rematerializeFor(unsigned MaxSGPRs, unsigned MaxVGPRs,
                        bool SpillReduction, BitVector &AffectedRegions,
                        MutableArrayRef<GCNRegPressure> *MaxPressure = nullptr);
 
  /// Starts recording rematerializations for eventual rollback.
  void startRecordingRemats() {
    assert(!Recorder && "recorder already defined");
    Recorder = std::make_unique<RematRecorder>(Remater);
  }
 
  /// Stops recording rematerializations and clears all recorded ones.
  void clearRecordedRemats() {
    assert(Recorder && "recorder not defined");
    Remater.removeListener(&Recorder->Listener);
    Recorder.reset(nullptr);
  }
 
  /// Rolls back all recorded rematerializations.
  void rollbackRecordedRemats();
 
private:
  /// Groups information about code regions to rematerialize across.
  struct RematRegions {
    /// Boundaries of regions across which the strategy rematerializes.
    /// FIXME: the rematerializer updates them when necessary, but the strategy
    /// should be responsible for that.
    ArrayRef<RegionBoundaries> Bounds;
 
    RematRegions(ArrayRef<RegionBoundaries> Regions,
                 MutableArrayRef<GCNRPTracker::LiveRegSet> LiveIns,
                 MutableArrayRef<GCNRPTracker::LiveRegSet> LiveOuts,
                 LiveIntervals &LIS, const MachineBlockFrequencyInfo &MBFI,
                 const MachineRegisterInfo &MRI);
 
    /// Returns the number of rematerialization regions.
    unsigned size() const { return Bounds.size(); }
 
    uint64_t getFrequency(unsigned RegionIdx) const {
      return Frequencies[RegionIdx];
    }
 
    uint64_t getFrequencyOr(unsigned RegionIdx, uint64_t Default = 0) const {
      uint64_t RegionFreq = Frequencies[RegionIdx];
      return RegionFreq ? RegionFreq : Default;
    }
 
    uint64_t getFrequencyOrMax(unsigned RegionIdx) const {
      return getFrequencyOr(RegionIdx, MaxFreq);
    }
 
    uint64_t getFrequencyOrMin(unsigned RegionIdx) const {
      return getFrequencyOr(RegionIdx, MinFreq);
    }
 
    /// Returns up-to-date live-ins for region \p RegionIdx.
    const GCNRPTracker::LiveRegSet &getLiveIns(unsigned RegionIdx) const {
      assert(RegionIdx < size() && "out of bounds");
      return LiveIns[RegionIdx];
    }
 
    /// Returns up-to-date live-outs for region \p RegionIdx.
    const GCNRPTracker::LiveRegSet &getLiveOuts(unsigned RegionIdx) const {
      assert(RegionIdx < size() && "out of bounds");
      return LiveOuts[RegionIdx];
    }
 
    /// Computes the up-to-date maximum register pressure in \p RegionIdx.
    GCNRegPressure computeMaxRegPressure(unsigned RegionIdx) const;
 
    /// Removes register \p Reg from the live-ins of regions set in \p LiveIn
    /// and the live-outs of regions set in \p LiveOut.
    void removeFromLiveMaps(Register Reg, const BitVector &LiveIn,
                            const BitVector &LiveOut);
 
    /// Adds register \p Reg with mask \p Mask to the live-ins of regions set in
    /// \p LiveIn and the live-outs of regions set in \p LiveOut.
    void addToLiveMaps(Register Reg, LaneBitmask Mask, const BitVector &LiveIn,
                       const BitVector &LiveOut);
 
  private:
    static const uint64_t FreqScaleFactor = 1024;
 
    /// Current live-ins and live-outs for each region.
    MutableArrayRef<GCNRPTracker::LiveRegSet> LiveIns, LiveOuts;
    /// Scaled per-region execution frequencies. 0 when unknown.
    SmallVector<uint64_t> Frequencies;
    /// Scaled minimum and maximum observed frequencies.
    uint64_t MinFreq, MaxFreq;
 
    LiveIntervals &LIS;
    const MachineRegisterInfo &MRI;
  };
 
  /// Tracks progress in reducing register pressure against a target.
  struct RematTargets {
    /// Register pressure targets for all regions.
    SmallVector<GCNRPTarget> RPTargets;
    /// Regions which are above the RP target.
    BitVector ExcessRP;
    /// Regions to rematerialize across.
    const RematRegions &Regions;
    /// Whether the register pressure target allows to reduce spilling.
    const bool SpillReduction;
 
    /// Sets a target \ref of maximum \p MaxSGPRs SGPRs and \p MaxVGPRs VGPRs
    /// per region. \p SpillReduction indicates whether that register pressure
    /// target allows to reduce spilling. When not null, \p MaxPressure provides
    /// initial maximum pressure for all regions.
    RematTargets(unsigned MaxSGPRs, unsigned MaxVGPRs, bool SpillReduction,
                 const MachineFunction &MF, const RematRegions &Regions,
                 ArrayRef<GCNRegPressure> *MaxPressure = nullptr);
 
    /// Returns whether the RP target is thought to be achieved in all regions.
    bool allAchieved() const { return ExcessRP.none(); }
 
    /// In all regions set in \p UpdateRegions, saves pressure \p RPSave and
    /// clear it as a target if its RP target has been reached.
    void updateRPTargets(const BitVector &UpdateRegions,
                         const GCNRegPressure &RPSave);
 
    /// Fully recomputes RP from the DAG in \p UpdateRegions. Among those
    /// regions, sets again all targets that were optimistically marked as
    /// satisfied but are actually not, and returns whether there were any such
    /// regions.
    bool updateAndVerifyRPTargets(const BitVector &UpdateRegions);
 
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
    Printable print() const;
#endif
  };
 
  /// A scored rematerialization candidate. Higher scores indicate more
  /// beneficial rematerializations. A null score indicates the
  /// rematerialization is not helpful to reduce RP in regions with excess RP.
  struct RematCandidate {
    /// The register index handle in the rematerializer.
    RegisterIdx RegIdx;
    /// Regions in which the register is live-in/live-out/live anywhere.
    BitVector LiveIn, LiveOut, Live;
    /// Subset of \ref Live regions in which the rematerialization is not
    /// guaranteed to reduce RP (i.e., regions in which the register is not
    /// live-through and unused).
    BitVector UnpredictableRPSave;
    /// Expected register pressure decrease induced by rematerializing this
    /// candidate.
    GCNRegPressure RPSave;
 
    RematCandidate(RegisterIdx RegIdx, unsigned NumRegions)
        : RegIdx(RegIdx), LiveIn(NumRegions), LiveOut(NumRegions),
          Live(NumRegions), UnpredictableRPSave(NumRegions) {}
 
    /// Initializes the candidate with state-independent characteristics.
    /// This doesn't update the actual score (call \ref update for this).
    /// Note: LiveIn/LiveOut must be pre-populated before calling this.
    void init(const RematRegions &RF, const Rematerializer &Remater,
              const MachineRegisterInfo &MRI);
 
    /// Updates the rematerialization's score w.r.t. the current \p Targets.
    void update(const RematTargets &Targets);
 
    /// Determines whether this rematerialization may be beneficial in at
    /// least one region with excess RP.
    bool maybeBeneficial(const RematTargets &Targets) const;
 
    /// Rematerializes the candidate using the \p Remater.
    void rematerialize(Rematerializer &Remater) const;
 
    /// Returns whether the current score is null, indicating the
    /// rematerialization is useless.
    bool hasNullScore() const { return !RegionImpact; }
 
    /// Compare score components of non-null scores pair-wise. Scores
    /// shouldn't be null (as defined by \ref hasNullScore).
    bool operator<(const RematCandidate &O) const {
      assert(!hasNullScore() && "this has null score");
      assert(!O.hasNullScore() && "other has null score");
      if (MaxFreq != O.MaxFreq)
        return MaxFreq < O.MaxFreq;
      if (FreqDiff != O.FreqDiff)
        return FreqDiff < O.FreqDiff;
      if (RegionImpact != O.RegionImpact)
        return RegionImpact < O.RegionImpact;
      // Break ties using register index handles. If the two registers are
      // connected in some dependency DAG of rematerializable registers, this
      // will tend to give a higher score to the register further from the
      // dependency DAG's root. If the two registers are disconnected, this
      // will give a higher score to the register with lower virtual register
      // index. In general, within a region, this should prefer registers
      // defined earlier that have longer live ranges in their defining region
      // (since the registers we consider are always live-out in their
      // defining region).
      return RegIdx > O.RegIdx;
    }
 
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
    Printable print() const;
#endif
 
  private:
    // The three members below are the scoring components, top to bottom from
    // most important to least important when comparing candidates.
 
    /// Frequency of impacted target region with highest known frequency. This
    /// only matters when the strategy is trying to reduce spilling, so it is
    /// always 0 when it is not.
    uint64_t MaxFreq;
    /// Frequency difference between defining and using regions. Negative
    /// values indicate we are rematerializing to higher frequency regions;
    /// positive values indicate the contrary.
    int64_t FreqDiff;
    /// Expected number of target regions impacted by the rematerialization,
    /// scaled by the size of the register being rematerialized.
    unsigned RegionImpact;
  };
 
  struct RematRecorder {
    struct LiveMapUpdate {
      /// The register index handle in the rematerializer.
      RegisterIdx RegIdx;
      /// Regions in which the original register was live-in or live-out.
      BitVector LiveIn, LiveOut;
 
      LiveMapUpdate(RegisterIdx RegIdx, const BitVector &LiveIn,
                    const BitVector &LiveOut)
          : RegIdx(RegIdx), LiveIn(LiveIn), LiveOut(LiveOut) {}
    };
 
    /// Rematerializer listener which can rollback rematerializations.
    Rollbacker Listener;
    /// Registers removed from live-maps along with bitvectors indicationg the
    /// regions in which they were live-ins and live-outs.
    SmallVector<LiveMapUpdate> LiveMapUpdates;
 
    /// Attaches the rollback listener to the rematerializer.
    RematRecorder(Rematerializer &Remater) { Remater.addListener(&Listener); }
  };
 
  /// Code regions to rematerialize across. Region bounds are updated by the
  /// rematerializer as necessary when rematerializations occur at region
  /// boundaries.
  RematRegions Regions;
  /// Rematerializer, initialized with the same rematerialization regions as the
  /// strategy.
  Rematerializer Remater;
  /// Candidates for rematerializations.
  SmallVector<RematCandidate, 0> Candidates;
  /// Whether candidates were already created, implying that the rematerializer
  /// was also fully initialized.
  bool CandidatesCreated = false;
  /// When not null, records all rematerializations.
  std::unique_ptr<RematRecorder> Recorder;
 
  const MachineFunction &MF;
  const MachineRegisterInfo &MRI;
  LiveIntervals &LIS;
 
  /// Creates rematerialization candidates. The strategy has more restrictions
  /// on what it can rematerialize compared to the rematerializer.
  void createCandidates();
 
  /// Determines whether users of rematerialization candidate \p CandIdx are
  /// compatible with the strategy's rematerialization constraints/limitations.
  /// Registers in \p MarkedRegs have already been deemed rematerializable by
  /// the strategy.
  bool candidateHasValidUsers(RegisterIdx CandIdx,
                              const SmallSet<Register, 4> &MarkedRegs) const;
};
 
} // namespace llvm
 
#endif // LLVM_LIB_TARGET_AMDGPU_GCNREMATSTRATEGY_H