AggressiveAntiDepBreaker.h revision 38306d53f9319d0a36a059b229b807578cb2e5c5
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#include <map> 31 32namespace llvm { 33 /// Class AggressiveAntiDepState 34 /// Contains all the state necessary for anti-dep breaking. 35 class AggressiveAntiDepState { 36 public: 37 /// RegisterReference - Information about a register reference 38 /// within a liverange 39 typedef struct { 40 /// Operand - The registers operand 41 MachineOperand *Operand; 42 /// RC - The register class 43 const TargetRegisterClass *RC; 44 } RegisterReference; 45 46 private: 47 /// NumTargetRegs - Number of non-virtual target registers 48 /// (i.e. TRI->getNumRegs()). 49 const unsigned NumTargetRegs; 50 51 /// GroupNodes - Implements a disjoint-union data structure to 52 /// form register groups. A node is represented by an index into 53 /// the vector. A node can "point to" itself to indicate that it 54 /// is the parent of a group, or point to another node to indicate 55 /// that it is a member of the same group as that node. 56 std::vector<unsigned> GroupNodes; 57 58 /// GroupNodeIndices - For each register, the index of the GroupNode 59 /// currently representing the group that the register belongs to. 60 /// Register 0 is always represented by the 0 group, a group 61 /// composed of registers that are not eligible for anti-aliasing. 62 std::vector<unsigned> GroupNodeIndices; 63 64 /// RegRefs - Map registers to all their references within a live range. 65 std::multimap<unsigned, RegisterReference> RegRefs; 66 67 /// KillIndices - The index of the most recent kill (proceding bottom-up), 68 /// or ~0u if the register is not live. 69 std::vector<unsigned> KillIndices; 70 71 /// DefIndices - The index of the most recent complete def (proceding bottom 72 /// up), or ~0u if the register is live. 73 std::vector<unsigned> DefIndices; 74 75 public: 76 AggressiveAntiDepState(const unsigned TargetRegs, MachineBasicBlock *BB); 77 78 /// GetKillIndices - Return the kill indices. 79 std::vector<unsigned> &GetKillIndices() { return KillIndices; } 80 81 /// GetDefIndices - Return the define indices. 82 std::vector<unsigned> &GetDefIndices() { return DefIndices; } 83 84 /// GetRegRefs - Return the RegRefs map. 85 std::multimap<unsigned, RegisterReference>& GetRegRefs() { return RegRefs; } 86 87 // GetGroup - Get the group for a register. The returned value is 88 // the index of the GroupNode representing the group. 89 unsigned GetGroup(unsigned Reg); 90 91 // GetGroupRegs - Return a vector of the registers belonging to a 92 // group. If RegRefs is non-NULL then only included referenced registers. 93 void GetGroupRegs( 94 unsigned Group, 95 std::vector<unsigned> &Regs, 96 std::multimap<unsigned, 97 AggressiveAntiDepState::RegisterReference> *RegRefs); 98 99 // UnionGroups - Union Reg1's and Reg2's groups to form a new 100 // group. Return the index of the GroupNode representing the 101 // group. 102 unsigned UnionGroups(unsigned Reg1, unsigned Reg2); 103 104 // LeaveGroup - Remove a register from its current group and place 105 // it alone in its own group. Return the index of the GroupNode 106 // representing the registers new group. 107 unsigned LeaveGroup(unsigned Reg); 108 109 /// IsLive - Return true if Reg is live 110 bool IsLive(unsigned Reg); 111 }; 112 113 114 /// Class AggressiveAntiDepBreaker 115 class AggressiveAntiDepBreaker : public AntiDepBreaker { 116 MachineFunction& MF; 117 MachineRegisterInfo &MRI; 118 const TargetInstrInfo *TII; 119 const TargetRegisterInfo *TRI; 120 121 /// AllocatableSet - The set of allocatable registers. 122 /// We'll be ignoring anti-dependencies on non-allocatable registers, 123 /// because they may not be safe to break. 124 const BitVector AllocatableSet; 125 126 /// CriticalPathSet - The set of registers that should only be 127 /// renamed if they are on the critical path. 128 BitVector CriticalPathSet; 129 130 /// State - The state used to identify and rename anti-dependence 131 /// registers. 132 AggressiveAntiDepState *State; 133 134 public: 135 AggressiveAntiDepBreaker(MachineFunction& MFi, 136 TargetSubtarget::RegClassVector& CriticalPathRCs); 137 ~AggressiveAntiDepBreaker(); 138 139 /// Start - Initialize anti-dep breaking for a new basic block. 140 void StartBlock(MachineBasicBlock *BB); 141 142 /// BreakAntiDependencies - Identifiy anti-dependencies along the critical 143 /// path 144 /// of the ScheduleDAG and break them by renaming registers. 145 /// 146 unsigned BreakAntiDependencies(const std::vector<SUnit>& SUnits, 147 MachineBasicBlock::iterator Begin, 148 MachineBasicBlock::iterator End, 149 unsigned InsertPosIndex); 150 151 /// Observe - Update liveness information to account for the current 152 /// instruction, which will not be scheduled. 153 /// 154 void Observe(MachineInstr *MI, unsigned Count, unsigned InsertPosIndex); 155 156 /// Finish - Finish anti-dep breaking for a basic block. 157 void FinishBlock(); 158 159 private: 160 typedef std::map<const TargetRegisterClass *, 161 TargetRegisterClass::const_iterator> RenameOrderType; 162 163 /// IsImplicitDefUse - Return true if MO represents a register 164 /// that is both implicitly used and defined in MI 165 bool IsImplicitDefUse(MachineInstr *MI, MachineOperand& MO); 166 167 /// GetPassthruRegs - If MI implicitly def/uses a register, then 168 /// return that register and all subregisters. 169 void GetPassthruRegs(MachineInstr *MI, std::set<unsigned>& PassthruRegs); 170 171 void HandleLastUse(unsigned Reg, unsigned KillIdx, const char *tag, 172 const char *header =NULL, const char *footer =NULL); 173 174 void PrescanInstruction(MachineInstr *MI, unsigned Count, 175 std::set<unsigned>& PassthruRegs); 176 void ScanInstruction(MachineInstr *MI, unsigned Count); 177 BitVector GetRenameRegisters(unsigned Reg); 178 bool FindSuitableFreeRegisters(unsigned AntiDepGroupIndex, 179 RenameOrderType& RenameOrder, 180 std::map<unsigned, unsigned> &RenameMap); 181 }; 182} 183 184#endif 185