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