189 lines · c
1//==- llvm/CodeGen/AggressiveAntiDepBreaker.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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the AggressiveAntiDepBreaker class, which10// implements register anti-dependence breaking during post-RA11// scheduling. It attempts to break all anti-dependencies within a12// block.13//14//===----------------------------------------------------------------------===//15 16#ifndef LLVM_LIB_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H17#define LLVM_LIB_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H18 19#include "llvm/ADT/BitVector.h"20#include "llvm/CodeGen/AntiDepBreaker.h"21#include "llvm/CodeGen/TargetSubtargetInfo.h"22#include "llvm/Support/Compiler.h"23#include <map>24#include <set>25#include <vector>26 27namespace llvm {28 29class MachineBasicBlock;30class MachineFunction;31class MachineInstr;32class MachineOperand;33class MachineRegisterInfo;34class RegisterClassInfo;35class TargetInstrInfo;36class TargetRegisterClass;37class TargetRegisterInfo;38 39 /// Contains all the state necessary for anti-dep breaking.40class LLVM_LIBRARY_VISIBILITY AggressiveAntiDepState {41 public:42 /// Information about a register reference within a liverange43 struct RegisterReference {44 /// The registers operand45 MachineOperand *Operand;46 47 /// The register class48 const TargetRegisterClass *RC;49 };50 51 private:52 /// Number of non-virtual target registers (i.e. TRI->getNumRegs()).53 const unsigned NumTargetRegs;54 55 /// Implements a disjoint-union data structure to56 /// form register groups. A node is represented by an index into57 /// the vector. A node can "point to" itself to indicate that it58 /// is the parent of a group, or point to another node to indicate59 /// that it is a member of the same group as that node.60 std::vector<unsigned> GroupNodes;61 62 /// For each register, the index of the GroupNode63 /// currently representing the group that the register belongs to.64 /// Register 0 is always represented by the 0 group, a group65 /// composed of registers that are not eligible for anti-aliasing.66 std::vector<unsigned> GroupNodeIndices;67 68 /// Map registers to all their references within a live range.69 std::multimap<MCRegister, RegisterReference> RegRefs;70 71 /// The index of the most recent kill (proceeding bottom-up),72 /// or ~0u if the register is not live.73 std::vector<unsigned> KillIndices;74 75 /// The index of the most recent complete def (proceeding bottom76 /// up), or ~0u if the register is live.77 std::vector<unsigned> DefIndices;78 79 public:80 AggressiveAntiDepState(const unsigned TargetRegs, MachineBasicBlock *BB);81 82 /// Return the kill indices.83 std::vector<unsigned> &GetKillIndices() { return KillIndices; }84 85 /// Return the define indices.86 std::vector<unsigned> &GetDefIndices() { return DefIndices; }87 88 /// Return the RegRefs map.89 std::multimap<MCRegister, RegisterReference> &GetRegRefs() {90 return RegRefs;91 }92 93 // Get the group for a register. The returned value is94 // the index of the GroupNode representing the group.95 unsigned GetGroup(MCRegister Reg);96 97 // Return a vector of the registers belonging to a group.98 // If RegRefs is non-NULL then only included referenced registers.99 void GetGroupRegs(100 unsigned Group, std::vector<MCRegister> &Regs,101 std::multimap<MCRegister, AggressiveAntiDepState::RegisterReference>102 *RegRefs);103 104 // Union Reg1's and Reg2's groups to form a new group.105 // Return the index of the GroupNode representing the group.106 unsigned UnionGroups(MCRegister Reg1, MCRegister Reg2);107 108 // Remove a register from its current group and place109 // it alone in its own group. Return the index of the GroupNode110 // representing the registers new group.111 unsigned LeaveGroup(MCRegister Reg);112 113 /// Return true if Reg is live.114 bool IsLive(MCRegister Reg);115 };116 117 class LLVM_LIBRARY_VISIBILITY AggressiveAntiDepBreaker118 : public AntiDepBreaker {119 MachineFunction &MF;120 MachineRegisterInfo &MRI;121 const TargetInstrInfo *TII;122 const TargetRegisterInfo *TRI;123 const RegisterClassInfo &RegClassInfo;124 125 /// The set of registers that should only be126 /// renamed if they are on the critical path.127 BitVector CriticalPathSet;128 129 /// The state used to identify and rename anti-dependence registers.130 AggressiveAntiDepState *State = nullptr;131 132 public:133 AggressiveAntiDepBreaker(MachineFunction &MFi,134 const RegisterClassInfo &RCI,135 TargetSubtargetInfo::RegClassVector& CriticalPathRCs);136 AggressiveAntiDepBreaker &137 operator=(const AggressiveAntiDepBreaker &other) = delete;138 AggressiveAntiDepBreaker(const AggressiveAntiDepBreaker &other) = delete;139 ~AggressiveAntiDepBreaker() override;140 141 /// Initialize anti-dep breaking for a new basic block.142 void StartBlock(MachineBasicBlock *BB) override;143 144 /// Identifiy anti-dependencies along the critical path145 /// of the ScheduleDAG and break them by renaming registers.146 unsigned BreakAntiDependencies(const std::vector<SUnit> &SUnits,147 MachineBasicBlock::iterator Begin,148 MachineBasicBlock::iterator End,149 unsigned InsertPosIndex,150 DbgValueVector &DbgValues) override;151 152 /// Update liveness information to account for the current153 /// instruction, which will not be scheduled.154 void Observe(MachineInstr &MI, unsigned Count,155 unsigned InsertPosIndex) override;156 157 /// Finish anti-dep breaking for a basic block.158 void FinishBlock() override;159 160 private:161 /// Keep track of a position in the allocation order for each regclass.162 using RenameOrderType = std::map<const TargetRegisterClass *, unsigned>;163 164 /// Return true if MO represents a register165 /// that is both implicitly used and defined in MI166 bool IsImplicitDefUse(MachineInstr &MI, MachineOperand &MO);167 168 /// If MI implicitly def/uses a register, then169 /// return that register and all subregisters.170 void GetPassthruRegs(MachineInstr &MI, std::set<MCRegister> &PassthruRegs);171 172 void HandleLastUse(MCRegister Reg, unsigned KillIdx, const char *tag,173 const char *header = nullptr,174 const char *footer = nullptr);175 176 void PrescanInstruction(MachineInstr &MI, unsigned Count,177 const std::set<MCRegister> &PassthruRegs);178 void ScanInstruction(MachineInstr &MI, unsigned Count);179 BitVector GetRenameRegisters(MCRegister Reg);180 bool FindSuitableFreeRegisters(MCRegister SuperReg,181 unsigned AntiDepGroupIndex,182 RenameOrderType &RenameOrder,183 std::map<MCRegister, MCRegister> &RenameMap);184 };185 186} // end namespace llvm187 188#endif // LLVM_LIB_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H189