1198892Srdivacky//=- llvm/CodeGen/AggressiveAntiDepBreaker.h - Anti-Dep Support -*- C++ -*-=// 2198892Srdivacky// 3198892Srdivacky// The LLVM Compiler Infrastructure 4198892Srdivacky// 5198892Srdivacky// This file is distributed under the University of Illinois Open Source 6198892Srdivacky// License. See LICENSE.TXT for details. 7198892Srdivacky// 8198892Srdivacky//===----------------------------------------------------------------------===// 9198892Srdivacky// 10198892Srdivacky// This file implements the AggressiveAntiDepBreaker class, which 11198892Srdivacky// implements register anti-dependence breaking during post-RA 12198892Srdivacky// scheduling. It attempts to break all anti-dependencies within a 13198892Srdivacky// block. 14198892Srdivacky// 15198892Srdivacky//===----------------------------------------------------------------------===// 16198892Srdivacky 17198892Srdivacky#ifndef LLVM_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H 18198892Srdivacky#define LLVM_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H 19198892Srdivacky 20198892Srdivacky#include "AntiDepBreaker.h" 21249423Sdim#include "llvm/ADT/BitVector.h" 22249423Sdim#include "llvm/ADT/SmallSet.h" 23198892Srdivacky#include "llvm/CodeGen/MachineBasicBlock.h" 24198892Srdivacky#include "llvm/CodeGen/MachineFrameInfo.h" 25198892Srdivacky#include "llvm/CodeGen/MachineFunction.h" 26198892Srdivacky#include "llvm/CodeGen/MachineRegisterInfo.h" 27198892Srdivacky#include "llvm/CodeGen/ScheduleDAG.h" 28249423Sdim#include "llvm/Target/TargetRegisterInfo.h" 29224145Sdim#include "llvm/Target/TargetSubtargetInfo.h" 30199989Srdivacky#include <map> 31198892Srdivacky 32198892Srdivackynamespace llvm { 33224145Sdimclass RegisterClassInfo; 34224145Sdim 35202375Srdivacky /// Class AggressiveAntiDepState 36199989Srdivacky /// Contains all the state necessary for anti-dep breaking. 37198892Srdivacky class AggressiveAntiDepState { 38198892Srdivacky public: 39198892Srdivacky /// RegisterReference - Information about a register reference 40198892Srdivacky /// within a liverange 41198892Srdivacky typedef struct { 42198892Srdivacky /// Operand - The registers operand 43198892Srdivacky MachineOperand *Operand; 44198892Srdivacky /// RC - The register class 45198892Srdivacky const TargetRegisterClass *RC; 46198892Srdivacky } RegisterReference; 47198892Srdivacky 48198892Srdivacky private: 49200581Srdivacky /// NumTargetRegs - Number of non-virtual target registers 50200581Srdivacky /// (i.e. TRI->getNumRegs()). 51200581Srdivacky const unsigned NumTargetRegs; 52200581Srdivacky 53198892Srdivacky /// GroupNodes - Implements a disjoint-union data structure to 54198892Srdivacky /// form register groups. A node is represented by an index into 55198892Srdivacky /// the vector. A node can "point to" itself to indicate that it 56198892Srdivacky /// is the parent of a group, or point to another node to indicate 57198892Srdivacky /// that it is a member of the same group as that node. 58198892Srdivacky std::vector<unsigned> GroupNodes; 59202375Srdivacky 60198892Srdivacky /// GroupNodeIndices - For each register, the index of the GroupNode 61198892Srdivacky /// currently representing the group that the register belongs to. 62198892Srdivacky /// Register 0 is always represented by the 0 group, a group 63198892Srdivacky /// composed of registers that are not eligible for anti-aliasing. 64212904Sdim std::vector<unsigned> GroupNodeIndices; 65202375Srdivacky 66198892Srdivacky /// RegRefs - Map registers to all their references within a live range. 67198892Srdivacky std::multimap<unsigned, RegisterReference> RegRefs; 68202375Srdivacky 69198892Srdivacky /// KillIndices - The index of the most recent kill (proceding bottom-up), 70198892Srdivacky /// or ~0u if the register is not live. 71212904Sdim std::vector<unsigned> KillIndices; 72202375Srdivacky 73198892Srdivacky /// DefIndices - The index of the most recent complete def (proceding bottom 74198892Srdivacky /// up), or ~0u if the register is live. 75212904Sdim std::vector<unsigned> DefIndices; 76198892Srdivacky 77198892Srdivacky public: 78200581Srdivacky AggressiveAntiDepState(const unsigned TargetRegs, MachineBasicBlock *BB); 79202375Srdivacky 80198892Srdivacky /// GetKillIndices - Return the kill indices. 81212904Sdim std::vector<unsigned> &GetKillIndices() { return KillIndices; } 82198892Srdivacky 83198892Srdivacky /// GetDefIndices - Return the define indices. 84212904Sdim std::vector<unsigned> &GetDefIndices() { return DefIndices; } 85198892Srdivacky 86198892Srdivacky /// GetRegRefs - Return the RegRefs map. 87198892Srdivacky std::multimap<unsigned, RegisterReference>& GetRegRefs() { return RegRefs; } 88198892Srdivacky 89198892Srdivacky // GetGroup - Get the group for a register. The returned value is 90198892Srdivacky // the index of the GroupNode representing the group. 91198892Srdivacky unsigned GetGroup(unsigned Reg); 92202375Srdivacky 93198892Srdivacky // GetGroupRegs - Return a vector of the registers belonging to a 94199481Srdivacky // group. If RegRefs is non-NULL then only included referenced registers. 95199481Srdivacky void GetGroupRegs( 96199481Srdivacky unsigned Group, 97199481Srdivacky std::vector<unsigned> &Regs, 98202375Srdivacky std::multimap<unsigned, 99202375Srdivacky AggressiveAntiDepState::RegisterReference> *RegRefs); 100198892Srdivacky 101198892Srdivacky // UnionGroups - Union Reg1's and Reg2's groups to form a new 102198892Srdivacky // group. Return the index of the GroupNode representing the 103198892Srdivacky // group. 104198892Srdivacky unsigned UnionGroups(unsigned Reg1, unsigned Reg2); 105198892Srdivacky 106198892Srdivacky // LeaveGroup - Remove a register from its current group and place 107198892Srdivacky // it alone in its own group. Return the index of the GroupNode 108198892Srdivacky // representing the registers new group. 109198892Srdivacky unsigned LeaveGroup(unsigned Reg); 110198892Srdivacky 111198892Srdivacky /// IsLive - Return true if Reg is live 112198892Srdivacky bool IsLive(unsigned Reg); 113198892Srdivacky }; 114198892Srdivacky 115198892Srdivacky 116202375Srdivacky /// Class AggressiveAntiDepBreaker 117198892Srdivacky class AggressiveAntiDepBreaker : public AntiDepBreaker { 118198892Srdivacky MachineFunction& MF; 119198892Srdivacky MachineRegisterInfo &MRI; 120210299Sed const TargetInstrInfo *TII; 121198892Srdivacky const TargetRegisterInfo *TRI; 122224145Sdim const RegisterClassInfo &RegClassInfo; 123198892Srdivacky 124199481Srdivacky /// CriticalPathSet - The set of registers that should only be 125199481Srdivacky /// renamed if they are on the critical path. 126199481Srdivacky BitVector CriticalPathSet; 127199481Srdivacky 128198892Srdivacky /// State - The state used to identify and rename anti-dependence 129198892Srdivacky /// registers. 130198892Srdivacky AggressiveAntiDepState *State; 131198892Srdivacky 132198892Srdivacky public: 133202375Srdivacky AggressiveAntiDepBreaker(MachineFunction& MFi, 134224145Sdim const RegisterClassInfo &RCI, 135224145Sdim TargetSubtargetInfo::RegClassVector& CriticalPathRCs); 136198892Srdivacky ~AggressiveAntiDepBreaker(); 137202375Srdivacky 138198892Srdivacky /// Start - Initialize anti-dep breaking for a new basic block. 139198892Srdivacky void StartBlock(MachineBasicBlock *BB); 140198892Srdivacky 141202375Srdivacky /// BreakAntiDependencies - Identifiy anti-dependencies along the critical 142202375Srdivacky /// path 143198892Srdivacky /// of the ScheduleDAG and break them by renaming registers. 144198892Srdivacky /// 145207618Srdivacky unsigned BreakAntiDependencies(const std::vector<SUnit>& SUnits, 146207618Srdivacky MachineBasicBlock::iterator Begin, 147207618Srdivacky MachineBasicBlock::iterator End, 148223017Sdim unsigned InsertPosIndex, 149223017Sdim DbgValueVector &DbgValues); 150198892Srdivacky 151198892Srdivacky /// Observe - Update liveness information to account for the current 152198892Srdivacky /// instruction, which will not be scheduled. 153198892Srdivacky /// 154198892Srdivacky void Observe(MachineInstr *MI, unsigned Count, unsigned InsertPosIndex); 155198892Srdivacky 156198892Srdivacky /// Finish - Finish anti-dep breaking for a basic block. 157198892Srdivacky void FinishBlock(); 158198892Srdivacky 159198892Srdivacky private: 160224145Sdim /// Keep track of a position in the allocation order for each regclass. 161224145Sdim typedef std::map<const TargetRegisterClass *, unsigned> RenameOrderType; 162198953Srdivacky 163198892Srdivacky /// IsImplicitDefUse - Return true if MO represents a register 164198892Srdivacky /// that is both implicitly used and defined in MI 165198892Srdivacky bool IsImplicitDefUse(MachineInstr *MI, MachineOperand& MO); 166202375Srdivacky 167198892Srdivacky /// GetPassthruRegs - If MI implicitly def/uses a register, then 168198892Srdivacky /// return that register and all subregisters. 169198892Srdivacky void GetPassthruRegs(MachineInstr *MI, std::set<unsigned>& PassthruRegs); 170198892Srdivacky 171199989Srdivacky void HandleLastUse(unsigned Reg, unsigned KillIdx, const char *tag, 172199989Srdivacky const char *header =NULL, const char *footer =NULL); 173199989Srdivacky 174198892Srdivacky void PrescanInstruction(MachineInstr *MI, unsigned Count, 175198892Srdivacky std::set<unsigned>& PassthruRegs); 176198892Srdivacky void ScanInstruction(MachineInstr *MI, unsigned Count); 177198892Srdivacky BitVector GetRenameRegisters(unsigned Reg); 178198892Srdivacky bool FindSuitableFreeRegisters(unsigned AntiDepGroupIndex, 179198953Srdivacky RenameOrderType& RenameOrder, 180198892Srdivacky std::map<unsigned, unsigned> &RenameMap); 181198892Srdivacky }; 182198892Srdivacky} 183198892Srdivacky 184198892Srdivacky#endif 185