AggressiveAntiDepBreaker.h revision 199481
1//=- llvm/CodeGen/AggressiveAntiDepBreaker.h - Anti-Dep Support -*- C++ -*-=// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the AggressiveAntiDepBreaker class, which 11// implements register anti-dependence breaking during post-RA 12// scheduling. It attempts to break all anti-dependencies within a 13// block. 14// 15//===----------------------------------------------------------------------===// 16 17#ifndef LLVM_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H 18#define LLVM_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H 19 20#include "AntiDepBreaker.h" 21#include "llvm/CodeGen/MachineBasicBlock.h" 22#include "llvm/CodeGen/MachineFrameInfo.h" 23#include "llvm/CodeGen/MachineFunction.h" 24#include "llvm/CodeGen/MachineRegisterInfo.h" 25#include "llvm/CodeGen/ScheduleDAG.h" 26#include "llvm/Target/TargetSubtarget.h" 27#include "llvm/Target/TargetRegisterInfo.h" 28#include "llvm/ADT/BitVector.h" 29#include "llvm/ADT/SmallSet.h" 30 31namespace llvm { 32 /// Class AggressiveAntiDepState 33 /// Contains all the state necessary for anti-dep breaking. We place 34 /// into a separate class so be can conveniently save/restore it to 35 /// enable multi-pass anti-dep breaking. 36 class AggressiveAntiDepState { 37 public: 38 /// RegisterReference - Information about a register reference 39 /// within a liverange 40 typedef struct { 41 /// Operand - The registers operand 42 MachineOperand *Operand; 43 /// RC - The register class 44 const TargetRegisterClass *RC; 45 } RegisterReference; 46 47 private: 48 /// GroupNodes - Implements a disjoint-union data structure to 49 /// form register groups. A node is represented by an index into 50 /// the vector. A node can "point to" itself to indicate that it 51 /// is the parent of a group, or point to another node to indicate 52 /// that it is a member of the same group as that node. 53 std::vector<unsigned> GroupNodes; 54 55 /// GroupNodeIndices - For each register, the index of the GroupNode 56 /// currently representing the group that the register belongs to. 57 /// Register 0 is always represented by the 0 group, a group 58 /// composed of registers that are not eligible for anti-aliasing. 59 unsigned GroupNodeIndices[TargetRegisterInfo::FirstVirtualRegister]; 60 61 /// RegRefs - Map registers to all their references within a live range. 62 std::multimap<unsigned, RegisterReference> RegRefs; 63 64 /// KillIndices - The index of the most recent kill (proceding bottom-up), 65 /// or ~0u if the register is not live. 66 unsigned KillIndices[TargetRegisterInfo::FirstVirtualRegister]; 67 68 /// DefIndices - The index of the most recent complete def (proceding bottom 69 /// up), or ~0u if the register is live. 70 unsigned DefIndices[TargetRegisterInfo::FirstVirtualRegister]; 71 72 public: 73 AggressiveAntiDepState(MachineBasicBlock *BB); 74 75 /// GetKillIndices - Return the kill indices. 76 unsigned *GetKillIndices() { return KillIndices; } 77 78 /// GetDefIndices - Return the define indices. 79 unsigned *GetDefIndices() { return DefIndices; } 80 81 /// GetRegRefs - Return the RegRefs map. 82 std::multimap<unsigned, RegisterReference>& GetRegRefs() { return RegRefs; } 83 84 // GetGroup - Get the group for a register. The returned value is 85 // the index of the GroupNode representing the group. 86 unsigned GetGroup(unsigned Reg); 87 88 // GetGroupRegs - Return a vector of the registers belonging to a 89 // group. If RegRefs is non-NULL then only included referenced registers. 90 void GetGroupRegs( 91 unsigned Group, 92 std::vector<unsigned> &Regs, 93 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference> *RegRefs); 94 95 // UnionGroups - Union Reg1's and Reg2's groups to form a new 96 // group. Return the index of the GroupNode representing the 97 // group. 98 unsigned UnionGroups(unsigned Reg1, unsigned Reg2); 99 100 // LeaveGroup - Remove a register from its current group and place 101 // it alone in its own group. Return the index of the GroupNode 102 // representing the registers new group. 103 unsigned LeaveGroup(unsigned Reg); 104 105 /// IsLive - Return true if Reg is live 106 bool IsLive(unsigned Reg); 107 }; 108 109 110 /// Class AggressiveAntiDepBreaker 111 class AggressiveAntiDepBreaker : public AntiDepBreaker { 112 MachineFunction& MF; 113 MachineRegisterInfo &MRI; 114 const TargetRegisterInfo *TRI; 115 116 /// AllocatableSet - The set of allocatable registers. 117 /// We'll be ignoring anti-dependencies on non-allocatable registers, 118 /// because they may not be safe to break. 119 const BitVector AllocatableSet; 120 121 /// CriticalPathSet - The set of registers that should only be 122 /// renamed if they are on the critical path. 123 BitVector CriticalPathSet; 124 125 /// State - The state used to identify and rename anti-dependence 126 /// registers. 127 AggressiveAntiDepState *State; 128 129 /// SavedState - The state for the start of an anti-dep 130 /// region. Used to restore the state at the beginning of each 131 /// pass 132 AggressiveAntiDepState *SavedState; 133 134 public: 135 AggressiveAntiDepBreaker(MachineFunction& MFi, 136 TargetSubtarget::RegClassVector& CriticalPathRCs); 137 ~AggressiveAntiDepBreaker(); 138 139 /// GetMaxTrials - As anti-dependencies are broken, additional 140 /// dependencies may be exposed, so multiple passes are required. 141 unsigned GetMaxTrials(); 142 143 /// NeedCandidates - Candidates required. 144 bool NeedCandidates() { return true; } 145 146 /// Start - Initialize anti-dep breaking for a new basic block. 147 void StartBlock(MachineBasicBlock *BB); 148 149 /// BreakAntiDependencies - Identifiy anti-dependencies along the critical path 150 /// of the ScheduleDAG and break them by renaming registers. 151 /// 152 unsigned BreakAntiDependencies(std::vector<SUnit>& SUnits, 153 CandidateMap& Candidates, 154 MachineBasicBlock::iterator& Begin, 155 MachineBasicBlock::iterator& End, 156 unsigned InsertPosIndex); 157 158 /// Observe - Update liveness information to account for the current 159 /// instruction, which will not be scheduled. 160 /// 161 void Observe(MachineInstr *MI, unsigned Count, unsigned InsertPosIndex); 162 163 /// Finish - Finish anti-dep breaking for a basic block. 164 void FinishBlock(); 165 166 private: 167 typedef std::map<const TargetRegisterClass *, 168 TargetRegisterClass::const_iterator> RenameOrderType; 169 170 /// IsImplicitDefUse - Return true if MO represents a register 171 /// that is both implicitly used and defined in MI 172 bool IsImplicitDefUse(MachineInstr *MI, MachineOperand& MO); 173 174 /// GetPassthruRegs - If MI implicitly def/uses a register, then 175 /// return that register and all subregisters. 176 void GetPassthruRegs(MachineInstr *MI, std::set<unsigned>& PassthruRegs); 177 178 void HandleLastUse(unsigned Reg, unsigned KillIdx, const char *tag); 179 void PrescanInstruction(MachineInstr *MI, unsigned Count, 180 std::set<unsigned>& PassthruRegs); 181 void ScanInstruction(MachineInstr *MI, unsigned Count); 182 BitVector GetRenameRegisters(unsigned Reg); 183 bool FindSuitableFreeRegisters(unsigned AntiDepGroupIndex, 184 RenameOrderType& RenameOrder, 185 std::map<unsigned, unsigned> &RenameMap); 186 }; 187} 188 189#endif 190