1348777110a960f0e017025dd5141cb29472c3984David Goodwin//=- llvm/CodeGen/AggressiveAntiDepBreaker.h - Anti-Dep Support -*- C++ -*-=// 2348777110a960f0e017025dd5141cb29472c3984David Goodwin// 3348777110a960f0e017025dd5141cb29472c3984David Goodwin// The LLVM Compiler Infrastructure 4348777110a960f0e017025dd5141cb29472c3984David Goodwin// 5348777110a960f0e017025dd5141cb29472c3984David Goodwin// This file is distributed under the University of Illinois Open Source 6348777110a960f0e017025dd5141cb29472c3984David Goodwin// License. See LICENSE.TXT for details. 7348777110a960f0e017025dd5141cb29472c3984David Goodwin// 8348777110a960f0e017025dd5141cb29472c3984David Goodwin//===----------------------------------------------------------------------===// 9348777110a960f0e017025dd5141cb29472c3984David Goodwin// 10348777110a960f0e017025dd5141cb29472c3984David Goodwin// This file implements the AggressiveAntiDepBreaker class, which 11348777110a960f0e017025dd5141cb29472c3984David Goodwin// implements register anti-dependence breaking during post-RA 12348777110a960f0e017025dd5141cb29472c3984David Goodwin// scheduling. It attempts to break all anti-dependencies within a 13348777110a960f0e017025dd5141cb29472c3984David Goodwin// block. 14348777110a960f0e017025dd5141cb29472c3984David Goodwin// 15348777110a960f0e017025dd5141cb29472c3984David Goodwin//===----------------------------------------------------------------------===// 16348777110a960f0e017025dd5141cb29472c3984David Goodwin 17348777110a960f0e017025dd5141cb29472c3984David Goodwin#ifndef LLVM_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H 18348777110a960f0e017025dd5141cb29472c3984David Goodwin#define LLVM_CODEGEN_AGGRESSIVEANTIDEPBREAKER_H 19348777110a960f0e017025dd5141cb29472c3984David Goodwin 2082c7248518a8b759a567fbb4b3176542ad2cf414David Goodwin#include "AntiDepBreaker.h" 21a1514e24cc24b050f53a12650e047799358833a1Chandler Carruth#include "llvm/ADT/BitVector.h" 22a1514e24cc24b050f53a12650e047799358833a1Chandler Carruth#include "llvm/ADT/SmallSet.h" 23348777110a960f0e017025dd5141cb29472c3984David Goodwin#include "llvm/CodeGen/MachineBasicBlock.h" 24348777110a960f0e017025dd5141cb29472c3984David Goodwin#include "llvm/CodeGen/MachineFrameInfo.h" 25348777110a960f0e017025dd5141cb29472c3984David Goodwin#include "llvm/CodeGen/MachineFunction.h" 26348777110a960f0e017025dd5141cb29472c3984David Goodwin#include "llvm/CodeGen/MachineRegisterInfo.h" 27348777110a960f0e017025dd5141cb29472c3984David Goodwin#include "llvm/CodeGen/ScheduleDAG.h" 287fa889b946266f5cf3f386acf2487aed244e5d10Chris Lattner#include "llvm/Target/TargetRegisterInfo.h" 29a1514e24cc24b050f53a12650e047799358833a1Chandler Carruth#include "llvm/Target/TargetSubtargetInfo.h" 30557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin#include <map> 31348777110a960f0e017025dd5141cb29472c3984David Goodwin 32348777110a960f0e017025dd5141cb29472c3984David Goodwinnamespace llvm { 33fa796dd720f1b34596a043f17f098fac18ecc028Jakob Stoklund Olesenclass RegisterClassInfo; 34fa796dd720f1b34596a043f17f098fac18ecc028Jakob Stoklund Olesen 352973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach /// Class AggressiveAntiDepState 36557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin /// Contains all the state necessary for anti-dep breaking. 37e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin class AggressiveAntiDepState { 38e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin public: 39348777110a960f0e017025dd5141cb29472c3984David Goodwin /// RegisterReference - Information about a register reference 40348777110a960f0e017025dd5141cb29472c3984David Goodwin /// within a liverange 41348777110a960f0e017025dd5141cb29472c3984David Goodwin typedef struct { 42348777110a960f0e017025dd5141cb29472c3984David Goodwin /// Operand - The registers operand 43348777110a960f0e017025dd5141cb29472c3984David Goodwin MachineOperand *Operand; 44348777110a960f0e017025dd5141cb29472c3984David Goodwin /// RC - The register class 45348777110a960f0e017025dd5141cb29472c3984David Goodwin const TargetRegisterClass *RC; 46348777110a960f0e017025dd5141cb29472c3984David Goodwin } RegisterReference; 47348777110a960f0e017025dd5141cb29472c3984David Goodwin 48e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin private: 49990d2857654cb80e46d207533834be3047494830David Goodwin /// NumTargetRegs - Number of non-virtual target registers 50990d2857654cb80e46d207533834be3047494830David Goodwin /// (i.e. TRI->getNumRegs()). 51990d2857654cb80e46d207533834be3047494830David Goodwin const unsigned NumTargetRegs; 52990d2857654cb80e46d207533834be3047494830David Goodwin 53348777110a960f0e017025dd5141cb29472c3984David Goodwin /// GroupNodes - Implements a disjoint-union data structure to 54348777110a960f0e017025dd5141cb29472c3984David Goodwin /// form register groups. A node is represented by an index into 55348777110a960f0e017025dd5141cb29472c3984David Goodwin /// the vector. A node can "point to" itself to indicate that it 56348777110a960f0e017025dd5141cb29472c3984David Goodwin /// is the parent of a group, or point to another node to indicate 57348777110a960f0e017025dd5141cb29472c3984David Goodwin /// that it is a member of the same group as that node. 58348777110a960f0e017025dd5141cb29472c3984David Goodwin std::vector<unsigned> GroupNodes; 592973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 60348777110a960f0e017025dd5141cb29472c3984David Goodwin /// GroupNodeIndices - For each register, the index of the GroupNode 61348777110a960f0e017025dd5141cb29472c3984David Goodwin /// currently representing the group that the register belongs to. 62348777110a960f0e017025dd5141cb29472c3984David Goodwin /// Register 0 is always represented by the 0 group, a group 63348777110a960f0e017025dd5141cb29472c3984David Goodwin /// composed of registers that are not eligible for anti-aliasing. 64dfb4eeb25c635ee6ad525bd13928a53b7c10d007Bill Wendling std::vector<unsigned> GroupNodeIndices; 652973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 66e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin /// RegRefs - Map registers to all their references within a live range. 67348777110a960f0e017025dd5141cb29472c3984David Goodwin std::multimap<unsigned, RegisterReference> RegRefs; 682973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 69348777110a960f0e017025dd5141cb29472c3984David Goodwin /// KillIndices - The index of the most recent kill (proceding bottom-up), 70348777110a960f0e017025dd5141cb29472c3984David Goodwin /// or ~0u if the register is not live. 7138306d53f9319d0a36a059b229b807578cb2e5c5Bill Wendling std::vector<unsigned> KillIndices; 722973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 73348777110a960f0e017025dd5141cb29472c3984David Goodwin /// DefIndices - The index of the most recent complete def (proceding bottom 74348777110a960f0e017025dd5141cb29472c3984David Goodwin /// up), or ~0u if the register is live. 7538306d53f9319d0a36a059b229b807578cb2e5c5Bill Wendling std::vector<unsigned> DefIndices; 76348777110a960f0e017025dd5141cb29472c3984David Goodwin 77348777110a960f0e017025dd5141cb29472c3984David Goodwin public: 78990d2857654cb80e46d207533834be3047494830David Goodwin AggressiveAntiDepState(const unsigned TargetRegs, MachineBasicBlock *BB); 792973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 80e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin /// GetKillIndices - Return the kill indices. 8138306d53f9319d0a36a059b229b807578cb2e5c5Bill Wendling std::vector<unsigned> &GetKillIndices() { return KillIndices; } 82348777110a960f0e017025dd5141cb29472c3984David Goodwin 83e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin /// GetDefIndices - Return the define indices. 8438306d53f9319d0a36a059b229b807578cb2e5c5Bill Wendling std::vector<unsigned> &GetDefIndices() { return DefIndices; } 85348777110a960f0e017025dd5141cb29472c3984David Goodwin 86e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin /// GetRegRefs - Return the RegRefs map. 87e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin std::multimap<unsigned, RegisterReference>& GetRegRefs() { return RegRefs; } 88348777110a960f0e017025dd5141cb29472c3984David Goodwin 89348777110a960f0e017025dd5141cb29472c3984David Goodwin // GetGroup - Get the group for a register. The returned value is 90348777110a960f0e017025dd5141cb29472c3984David Goodwin // the index of the GroupNode representing the group. 91348777110a960f0e017025dd5141cb29472c3984David Goodwin unsigned GetGroup(unsigned Reg); 922973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 93348777110a960f0e017025dd5141cb29472c3984David Goodwin // GetGroupRegs - Return a vector of the registers belonging to a 9487d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin // group. If RegRefs is non-NULL then only included referenced registers. 9587d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin void GetGroupRegs( 9687d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin unsigned Group, 9787d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin std::vector<unsigned> &Regs, 982973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach std::multimap<unsigned, 992973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach AggressiveAntiDepState::RegisterReference> *RegRefs); 100348777110a960f0e017025dd5141cb29472c3984David Goodwin 101348777110a960f0e017025dd5141cb29472c3984David Goodwin // UnionGroups - Union Reg1's and Reg2's groups to form a new 102348777110a960f0e017025dd5141cb29472c3984David Goodwin // group. Return the index of the GroupNode representing the 103348777110a960f0e017025dd5141cb29472c3984David Goodwin // group. 104348777110a960f0e017025dd5141cb29472c3984David Goodwin unsigned UnionGroups(unsigned Reg1, unsigned Reg2); 105348777110a960f0e017025dd5141cb29472c3984David Goodwin 106348777110a960f0e017025dd5141cb29472c3984David Goodwin // LeaveGroup - Remove a register from its current group and place 107348777110a960f0e017025dd5141cb29472c3984David Goodwin // it alone in its own group. Return the index of the GroupNode 108348777110a960f0e017025dd5141cb29472c3984David Goodwin // representing the registers new group. 109348777110a960f0e017025dd5141cb29472c3984David Goodwin unsigned LeaveGroup(unsigned Reg); 110348777110a960f0e017025dd5141cb29472c3984David Goodwin 111348777110a960f0e017025dd5141cb29472c3984David Goodwin /// IsLive - Return true if Reg is live 112348777110a960f0e017025dd5141cb29472c3984David Goodwin bool IsLive(unsigned Reg); 113e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin }; 114e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin 115e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin 1162973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach /// Class AggressiveAntiDepBreaker 117e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin class AggressiveAntiDepBreaker : public AntiDepBreaker { 118e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin MachineFunction& MF; 119e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin MachineRegisterInfo &MRI; 12046df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng const TargetInstrInfo *TII; 121e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin const TargetRegisterInfo *TRI; 122fa796dd720f1b34596a043f17f098fac18ecc028Jakob Stoklund Olesen const RegisterClassInfo &RegClassInfo; 12387d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin 12487d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin /// CriticalPathSet - The set of registers that should only be 12587d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin /// renamed if they are on the critical path. 12687d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin BitVector CriticalPathSet; 127e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin 128e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin /// State - The state used to identify and rename anti-dependence 129e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin /// registers. 130e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin AggressiveAntiDepState *State; 131e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin 132e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin public: 1332973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach AggressiveAntiDepBreaker(MachineFunction& MFi, 1345b1b4489cf3a0f56f8be0673fc5cc380a32d277bEvan Cheng const RegisterClassInfo &RCI, 1355b1b4489cf3a0f56f8be0673fc5cc380a32d277bEvan Cheng TargetSubtargetInfo::RegClassVector& CriticalPathRCs); 136e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin ~AggressiveAntiDepBreaker(); 1372973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 138e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin /// Start - Initialize anti-dep breaking for a new basic block. 13936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void StartBlock(MachineBasicBlock *BB) override; 140e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin 1412973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach /// BreakAntiDependencies - Identifiy anti-dependencies along the critical 1422973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach /// path 143e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin /// of the ScheduleDAG and break them by renaming registers. 144e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin /// 14566db3a0f10e96ae190c8a46a1a8d5242928d068cDan Gohman unsigned BreakAntiDependencies(const std::vector<SUnit>& SUnits, 14666db3a0f10e96ae190c8a46a1a8d5242928d068cDan Gohman MachineBasicBlock::iterator Begin, 14766db3a0f10e96ae190c8a46a1a8d5242928d068cDan Gohman MachineBasicBlock::iterator End, 148e29e8e100ea38be1771e5f010a5511cbb990d515Devang Patel unsigned InsertPosIndex, 14936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DbgValueVector &DbgValues) override; 150e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin 151e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin /// Observe - Update liveness information to account for the current 152e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin /// instruction, which will not be scheduled. 153e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin /// 15436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void Observe(MachineInstr *MI, unsigned Count, 15536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned InsertPosIndex) override; 156e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin 157e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin /// Finish - Finish anti-dep breaking for a basic block. 15836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void FinishBlock() override; 159e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin 160e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin private: 161fa796dd720f1b34596a043f17f098fac18ecc028Jakob Stoklund Olesen /// Keep track of a position in the allocation order for each regclass. 162fa796dd720f1b34596a043f17f098fac18ecc028Jakob Stoklund Olesen typedef std::map<const TargetRegisterClass *, unsigned> RenameOrderType; 16354097836f31660bd5e84c34ee8c92d237844315fDavid Goodwin 164348777110a960f0e017025dd5141cb29472c3984David Goodwin /// IsImplicitDefUse - Return true if MO represents a register 165348777110a960f0e017025dd5141cb29472c3984David Goodwin /// that is both implicitly used and defined in MI 166348777110a960f0e017025dd5141cb29472c3984David Goodwin bool IsImplicitDefUse(MachineInstr *MI, MachineOperand& MO); 1672973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 168348777110a960f0e017025dd5141cb29472c3984David Goodwin /// GetPassthruRegs - If MI implicitly def/uses a register, then 169348777110a960f0e017025dd5141cb29472c3984David Goodwin /// return that register and all subregisters. 170348777110a960f0e017025dd5141cb29472c3984David Goodwin void GetPassthruRegs(MachineInstr *MI, std::set<unsigned>& PassthruRegs); 171348777110a960f0e017025dd5141cb29472c3984David Goodwin 1723e72d301e03de8edcd603a5d3e9486748dfa6887David Goodwin void HandleLastUse(unsigned Reg, unsigned KillIdx, const char *tag, 173dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const char *header = nullptr, 174dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const char *footer = nullptr); 1753e72d301e03de8edcd603a5d3e9486748dfa6887David Goodwin 176348777110a960f0e017025dd5141cb29472c3984David Goodwin void PrescanInstruction(MachineInstr *MI, unsigned Count, 177348777110a960f0e017025dd5141cb29472c3984David Goodwin std::set<unsigned>& PassthruRegs); 178348777110a960f0e017025dd5141cb29472c3984David Goodwin void ScanInstruction(MachineInstr *MI, unsigned Count); 179348777110a960f0e017025dd5141cb29472c3984David Goodwin BitVector GetRenameRegisters(unsigned Reg); 180348777110a960f0e017025dd5141cb29472c3984David Goodwin bool FindSuitableFreeRegisters(unsigned AntiDepGroupIndex, 18154097836f31660bd5e84c34ee8c92d237844315fDavid Goodwin RenameOrderType& RenameOrder, 182348777110a960f0e017025dd5141cb29472c3984David Goodwin std::map<unsigned, unsigned> &RenameMap); 183348777110a960f0e017025dd5141cb29472c3984David Goodwin }; 184348777110a960f0e017025dd5141cb29472c3984David Goodwin} 185348777110a960f0e017025dd5141cb29472c3984David Goodwin 186348777110a960f0e017025dd5141cb29472c3984David Goodwin#endif 187