llvm/lib/CodeGen/CriticalAntiDepBreaker.h

   1 //===- llvm/CodeGen/CriticalAntiDepBreaker.h - Anti-Dep Support -*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements the CriticalAntiDepBreaker class, which
  10 // implements register anti-dependence breaking along a blocks
  11 // critical path during post-RA scheduler.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_LIB_CODEGEN_CRITICALANTIDEPBREAKER_H
  16 #define LLVM_LIB_CODEGEN_CRITICALANTIDEPBREAKER_H
  17
  18 #include "llvm/ADT/BitVector.h"
  19 #include "llvm/CodeGen/AntiDepBreaker.h"
  20 #include "llvm/Support/Compiler.h"
  21 #include <map>
  22 #include <vector>
  23
  24 namespace llvm {
  25
  26 class MachineBasicBlock;
  27 class MachineFunction;
  28 class MachineInstr;
  29 class MachineOperand;
  30 class MachineRegisterInfo;
  31 class RegisterClassInfo;
  32 class TargetInstrInfo;
  33 class TargetRegisterClass;
  34 class TargetRegisterInfo;
  35
  36 class LLVM_LIBRARY_VISIBILITY CriticalAntiDepBreaker : public AntiDepBreaker {
  37     MachineFunction& MF;
  38     MachineRegisterInfo &MRI;
  39     const TargetInstrInfo *TII;
  40     const TargetRegisterInfo *TRI;
  41     const RegisterClassInfo &RegClassInfo;
  42
  43     /// The set of allocatable registers.
  44     /// We'll be ignoring anti-dependencies on non-allocatable registers,
  45     /// because they may not be safe to break.
  46     const BitVector AllocatableSet;
  47
  48     /// For live regs that are only used in one register class in a
  49     /// live range, the register class. If the register is not live, the
  50     /// corresponding value is null. If the register is live but used in
  51     /// multiple register classes, the corresponding value is -1 casted to a
  52     /// pointer.
  53     std::vector<const TargetRegisterClass *> Classes;
  54
  55     /// Map registers to all their references within a live range.
  56     std::multimap<unsigned, MachineOperand *> RegRefs;
  57
  58     using RegRefIter =
  59         std::multimap<unsigned, MachineOperand *>::const_iterator;
  60
  61     /// The index of the most recent kill (proceeding bottom-up),
  62     /// or ~0u if the register is not live.
  63     std::vector<unsigned> KillIndices;
  64
  65     /// The index of the most recent complete def (proceeding
  66     /// bottom up), or ~0u if the register is live.
  67     std::vector<unsigned> DefIndices;
  68
  69     /// A set of registers which are live and cannot be changed to
  70     /// break anti-dependencies.
  71     BitVector KeepRegs;
  72
  73   public:
  74     CriticalAntiDepBreaker(MachineFunction& MFi, const RegisterClassInfo &RCI);
  75     ~CriticalAntiDepBreaker() override;
  76
  77     /// Initialize anti-dep breaking for a new basic block.
  78     void StartBlock(MachineBasicBlock *BB) override;
  79
  80     /// Identifiy anti-dependencies along the critical path
  81     /// of the ScheduleDAG and break them by renaming registers.
  82     unsigned BreakAntiDependencies(const std::vector<SUnit> &SUnits,
  83                                    MachineBasicBlock::iterator Begin,
  84                                    MachineBasicBlock::iterator End,
  85                                    unsigned InsertPosIndex,
  86                                    DbgValueVector &DbgValues) override;
  87
  88     /// Update liveness information to account for the current
  89     /// instruction, which will not be scheduled.
  90     void Observe(MachineInstr &MI, unsigned Count,
  91                  unsigned InsertPosIndex) override;
  92
  93     /// Finish anti-dep breaking for a basic block.
  94     void FinishBlock() override;
  95
  96   private:
  97     void PrescanInstruction(MachineInstr &MI);
  98     void ScanInstruction(MachineInstr &MI, unsigned Count);
  99     bool isNewRegClobberedByRefs(RegRefIter RegRefBegin,
 100                                  RegRefIter RegRefEnd,
 101                                  unsigned NewReg);
 102     unsigned findSuitableFreeRegister(RegRefIter RegRefBegin,
 103                                       RegRefIter RegRefEnd,
 104                                       unsigned AntiDepReg,
 105                                       unsigned LastNewReg,
 106                                       const TargetRegisterClass *RC,
 107                                       SmallVectorImpl<unsigned> &Forbid);
 108   };
 109
 110 } // end namespace llvm
 111
 112 #endif // LLVM_LIB_CODEGEN_CRITICALANTIDEPBREAKER_H