12973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach//===----- AggressiveAntiDepBreaker.cpp - Anti-dep breaker ----------------===// 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 174de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin#define DEBUG_TYPE "post-RA-sched" 18348777110a960f0e017025dd5141cb29472c3984David Goodwin#include "AggressiveAntiDepBreaker.h" 19348777110a960f0e017025dd5141cb29472c3984David Goodwin#include "llvm/CodeGen/MachineBasicBlock.h" 20348777110a960f0e017025dd5141cb29472c3984David Goodwin#include "llvm/CodeGen/MachineFrameInfo.h" 21348777110a960f0e017025dd5141cb29472c3984David Goodwin#include "llvm/CodeGen/MachineInstr.h" 221525260b3e50cc578939ef41b60609689eecfdd2Andrew Trick#include "llvm/CodeGen/RegisterClassInfo.h" 23e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin#include "llvm/Support/CommandLine.h" 24348777110a960f0e017025dd5141cb29472c3984David Goodwin#include "llvm/Support/Debug.h" 25348777110a960f0e017025dd5141cb29472c3984David Goodwin#include "llvm/Support/ErrorHandling.h" 26348777110a960f0e017025dd5141cb29472c3984David Goodwin#include "llvm/Support/raw_ostream.h" 27d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetInstrInfo.h" 28d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetMachine.h" 29d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetRegisterInfo.h" 30348777110a960f0e017025dd5141cb29472c3984David Goodwinusing namespace llvm; 31348777110a960f0e017025dd5141cb29472c3984David Goodwin 323e72d301e03de8edcd603a5d3e9486748dfa6887David Goodwin// If DebugDiv > 0 then only break antidep with (ID % DebugDiv) == DebugMod 333e72d301e03de8edcd603a5d3e9486748dfa6887David Goodwinstatic cl::opt<int> 343e72d301e03de8edcd603a5d3e9486748dfa6887David GoodwinDebugDiv("agg-antidep-debugdiv", 35347fa3fa26592b9792d100f3bf79b0695cf746f0Bob Wilson cl::desc("Debug control for aggressive anti-dep breaker"), 36347fa3fa26592b9792d100f3bf79b0695cf746f0Bob Wilson cl::init(0), cl::Hidden); 373e72d301e03de8edcd603a5d3e9486748dfa6887David Goodwinstatic cl::opt<int> 383e72d301e03de8edcd603a5d3e9486748dfa6887David GoodwinDebugMod("agg-antidep-debugmod", 39347fa3fa26592b9792d100f3bf79b0695cf746f0Bob Wilson cl::desc("Debug control for aggressive anti-dep breaker"), 40347fa3fa26592b9792d100f3bf79b0695cf746f0Bob Wilson cl::init(0), cl::Hidden); 413e72d301e03de8edcd603a5d3e9486748dfa6887David Goodwin 42990d2857654cb80e46d207533834be3047494830David GoodwinAggressiveAntiDepState::AggressiveAntiDepState(const unsigned TargetRegs, 43990d2857654cb80e46d207533834be3047494830David Goodwin MachineBasicBlock *BB) : 449c2a034730b289a2cf48bc91aa2ef69737a7afbbBill Wendling NumTargetRegs(TargetRegs), GroupNodes(TargetRegs, 0), 459c2a034730b289a2cf48bc91aa2ef69737a7afbbBill Wendling GroupNodeIndices(TargetRegs, 0), 469c2a034730b289a2cf48bc91aa2ef69737a7afbbBill Wendling KillIndices(TargetRegs, 0), 479c2a034730b289a2cf48bc91aa2ef69737a7afbbBill Wendling DefIndices(TargetRegs, 0) 489c2a034730b289a2cf48bc91aa2ef69737a7afbbBill Wendling{ 49990d2857654cb80e46d207533834be3047494830David Goodwin const unsigned BBSize = BB->size(); 50990d2857654cb80e46d207533834be3047494830David Goodwin for (unsigned i = 0; i < NumTargetRegs; ++i) { 51990d2857654cb80e46d207533834be3047494830David Goodwin // Initialize all registers to be in their own group. Initially we 52990d2857654cb80e46d207533834be3047494830David Goodwin // assign the register to the same-indexed GroupNode. 53e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin GroupNodeIndices[i] = i; 54990d2857654cb80e46d207533834be3047494830David Goodwin // Initialize the indices to indicate that no registers are live. 55990d2857654cb80e46d207533834be3047494830David Goodwin KillIndices[i] = ~0u; 56990d2857654cb80e46d207533834be3047494830David Goodwin DefIndices[i] = BBSize; 57990d2857654cb80e46d207533834be3047494830David Goodwin } 58e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin} 59e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin 60e4a4147c877777fddfff50a89cac81a596f1a8baBill Wendlingunsigned AggressiveAntiDepState::GetGroup(unsigned Reg) { 61e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin unsigned Node = GroupNodeIndices[Reg]; 62e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin while (GroupNodes[Node] != Node) 63e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin Node = GroupNodes[Node]; 64e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin 65e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin return Node; 66e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin} 67e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin 6887d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwinvoid AggressiveAntiDepState::GetGroupRegs( 6987d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin unsigned Group, 7087d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin std::vector<unsigned> &Regs, 7187d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin std::multimap<unsigned, AggressiveAntiDepState::RegisterReference> *RegRefs) 72e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin{ 73990d2857654cb80e46d207533834be3047494830David Goodwin for (unsigned Reg = 0; Reg != NumTargetRegs; ++Reg) { 7487d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin if ((GetGroup(Reg) == Group) && (RegRefs->count(Reg) > 0)) 75e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin Regs.push_back(Reg); 76e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin } 77e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin} 78e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin 79e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwinunsigned AggressiveAntiDepState::UnionGroups(unsigned Reg1, unsigned Reg2) 80e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin{ 81e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin assert(GroupNodes[0] == 0 && "GroupNode 0 not parent!"); 82e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin assert(GroupNodeIndices[0] == 0 && "Reg 0 not in Group 0!"); 832973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 84e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin // find group for each register 85e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin unsigned Group1 = GetGroup(Reg1); 86e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin unsigned Group2 = GetGroup(Reg2); 872973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 88e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin // if either group is 0, then that must become the parent 89e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin unsigned Parent = (Group1 == 0) ? Group1 : Group2; 90e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin unsigned Other = (Parent == Group1) ? Group2 : Group1; 91e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin GroupNodes.at(Other) = Parent; 92e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin return Parent; 93e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin} 942973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 95e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwinunsigned AggressiveAntiDepState::LeaveGroup(unsigned Reg) 96e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin{ 97e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin // Create a new GroupNode for Reg. Reg's existing GroupNode must 98e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin // stay as is because there could be other GroupNodes referring to 99e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin // it. 100e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin unsigned idx = GroupNodes.size(); 101e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin GroupNodes.push_back(idx); 102e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin GroupNodeIndices[Reg] = idx; 103e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin return idx; 104e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin} 105e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin 106e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwinbool AggressiveAntiDepState::IsLive(unsigned Reg) 107e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin{ 108e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin // KillIndex must be defined and DefIndex not defined for a register 109e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin // to be live. 110e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin return((KillIndices[Reg] != ~0u) && (DefIndices[Reg] == ~0u)); 111e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin} 112e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin 113e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin 114e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin 115348777110a960f0e017025dd5141cb29472c3984David GoodwinAggressiveAntiDepBreaker:: 1160855dee564f80160abf95497475306af38ab7f84David GoodwinAggressiveAntiDepBreaker(MachineFunction& MFi, 117fa796dd720f1b34596a043f17f098fac18ecc028Jakob Stoklund Olesen const RegisterClassInfo &RCI, 1185b1b4489cf3a0f56f8be0673fc5cc380a32d277bEvan Cheng TargetSubtargetInfo::RegClassVector& CriticalPathRCs) : 119348777110a960f0e017025dd5141cb29472c3984David Goodwin AntiDepBreaker(), MF(MFi), 120348777110a960f0e017025dd5141cb29472c3984David Goodwin MRI(MF.getRegInfo()), 12146df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng TII(MF.getTarget().getInstrInfo()), 122348777110a960f0e017025dd5141cb29472c3984David Goodwin TRI(MF.getTarget().getRegisterInfo()), 123fa796dd720f1b34596a043f17f098fac18ecc028Jakob Stoklund Olesen RegClassInfo(RCI), 124557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin State(NULL) { 12587d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin /* Collect a bitset of all registers that are only broken if they 12687d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin are on the critical path. */ 12787d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin for (unsigned i = 0, e = CriticalPathRCs.size(); i < e; ++i) { 12887d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin BitVector CPSet = TRI->getAllocatableSet(MF, CriticalPathRCs[i]); 12987d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin if (CriticalPathSet.none()) 13087d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin CriticalPathSet = CPSet; 13187d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin else 13287d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin CriticalPathSet |= CPSet; 13387d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin } 1342973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 1355393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << "AntiDep Critical-Path Registers:"); 1362973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach DEBUG(for (int r = CriticalPathSet.find_first(); r != -1; 13787d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin r = CriticalPathSet.find_next(r)) 1385393b2523419af71971be2286f34d3c8e2501898David Greene dbgs() << " " << TRI->getName(r)); 1395393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << '\n'); 140348777110a960f0e017025dd5141cb29472c3984David Goodwin} 141348777110a960f0e017025dd5141cb29472c3984David Goodwin 142348777110a960f0e017025dd5141cb29472c3984David GoodwinAggressiveAntiDepBreaker::~AggressiveAntiDepBreaker() { 143e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin delete State; 144e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin} 145348777110a960f0e017025dd5141cb29472c3984David Goodwin 146e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwinvoid AggressiveAntiDepBreaker::StartBlock(MachineBasicBlock *BB) { 147e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin assert(State == NULL); 148990d2857654cb80e46d207533834be3047494830David Goodwin State = new AggressiveAntiDepState(TRI->getNumRegs(), BB); 149348777110a960f0e017025dd5141cb29472c3984David Goodwin 1505a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng bool IsReturnBlock = (!BB->empty() && BB->back().isReturn()); 15138306d53f9319d0a36a059b229b807578cb2e5c5Bill Wendling std::vector<unsigned> &KillIndices = State->GetKillIndices(); 15238306d53f9319d0a36a059b229b807578cb2e5c5Bill Wendling std::vector<unsigned> &DefIndices = State->GetDefIndices(); 153348777110a960f0e017025dd5141cb29472c3984David Goodwin 154b45e4deb102d47602f5b941da7f412ecc9a867e9Jakob Stoklund Olesen // Examine the live-in regs of all successors. 15546df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 156348777110a960f0e017025dd5141cb29472c3984David Goodwin SE = BB->succ_end(); SI != SE; ++SI) 15746df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(), 158348777110a960f0e017025dd5141cb29472c3984David Goodwin E = (*SI)->livein_end(); I != E; ++I) { 159396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCRegAliasIterator AI(*I, TRI, true); AI.isValid(); ++AI) { 160396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen unsigned Reg = *AI; 161597faa8f1fd208d6ed99d1771293d77ac486f092Jakob Stoklund Olesen State->UnionGroups(Reg, 0); 162597faa8f1fd208d6ed99d1771293d77ac486f092Jakob Stoklund Olesen KillIndices[Reg] = BB->size(); 163597faa8f1fd208d6ed99d1771293d77ac486f092Jakob Stoklund Olesen DefIndices[Reg] = ~0u; 164348777110a960f0e017025dd5141cb29472c3984David Goodwin } 16546df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng } 166348777110a960f0e017025dd5141cb29472c3984David Goodwin 167348777110a960f0e017025dd5141cb29472c3984David Goodwin // Mark live-out callee-saved registers. In a return block this is 168348777110a960f0e017025dd5141cb29472c3984David Goodwin // all callee-saved registers. In non-return this is any 169348777110a960f0e017025dd5141cb29472c3984David Goodwin // callee-saved register that is not saved in the prolog. 170348777110a960f0e017025dd5141cb29472c3984David Goodwin const MachineFrameInfo *MFI = MF.getFrameInfo(); 171348777110a960f0e017025dd5141cb29472c3984David Goodwin BitVector Pristine = MFI->getPristineRegs(BB); 172015f228861ef9b337366f92f637d4e8d624bb006Craig Topper for (const uint16_t *I = TRI->getCalleeSavedRegs(&MF); *I; ++I) { 173348777110a960f0e017025dd5141cb29472c3984David Goodwin unsigned Reg = *I; 174348777110a960f0e017025dd5141cb29472c3984David Goodwin if (!IsReturnBlock && !Pristine.test(Reg)) continue; 175396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { 176396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen unsigned AliasReg = *AI; 177e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin State->UnionGroups(AliasReg, 0); 178348777110a960f0e017025dd5141cb29472c3984David Goodwin KillIndices[AliasReg] = BB->size(); 179348777110a960f0e017025dd5141cb29472c3984David Goodwin DefIndices[AliasReg] = ~0u; 180348777110a960f0e017025dd5141cb29472c3984David Goodwin } 181348777110a960f0e017025dd5141cb29472c3984David Goodwin } 182348777110a960f0e017025dd5141cb29472c3984David Goodwin} 183348777110a960f0e017025dd5141cb29472c3984David Goodwin 184348777110a960f0e017025dd5141cb29472c3984David Goodwinvoid AggressiveAntiDepBreaker::FinishBlock() { 185e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin delete State; 186e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin State = NULL; 187348777110a960f0e017025dd5141cb29472c3984David Goodwin} 188348777110a960f0e017025dd5141cb29472c3984David Goodwin 189348777110a960f0e017025dd5141cb29472c3984David Goodwinvoid AggressiveAntiDepBreaker::Observe(MachineInstr *MI, unsigned Count, 190347fa3fa26592b9792d100f3bf79b0695cf746f0Bob Wilson unsigned InsertPosIndex) { 191348777110a960f0e017025dd5141cb29472c3984David Goodwin assert(Count < InsertPosIndex && "Instruction index out of expected range!"); 192348777110a960f0e017025dd5141cb29472c3984David Goodwin 1935b3c308970f9fe1f6a2e0df265dcd40ea8ad50a8David Goodwin std::set<unsigned> PassthruRegs; 1945b3c308970f9fe1f6a2e0df265dcd40ea8ad50a8David Goodwin GetPassthruRegs(MI, PassthruRegs); 1955b3c308970f9fe1f6a2e0df265dcd40ea8ad50a8David Goodwin PrescanInstruction(MI, Count, PassthruRegs); 1965b3c308970f9fe1f6a2e0df265dcd40ea8ad50a8David Goodwin ScanInstruction(MI, Count); 1975b3c308970f9fe1f6a2e0df265dcd40ea8ad50a8David Goodwin 1985393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << "Observe: "); 199348777110a960f0e017025dd5141cb29472c3984David Goodwin DEBUG(MI->dump()); 2005393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << "\tRegs:"); 201348777110a960f0e017025dd5141cb29472c3984David Goodwin 20238306d53f9319d0a36a059b229b807578cb2e5c5Bill Wendling std::vector<unsigned> &DefIndices = State->GetDefIndices(); 203990d2857654cb80e46d207533834be3047494830David Goodwin for (unsigned Reg = 0; Reg != TRI->getNumRegs(); ++Reg) { 204348777110a960f0e017025dd5141cb29472c3984David Goodwin // If Reg is current live, then mark that it can't be renamed as 205348777110a960f0e017025dd5141cb29472c3984David Goodwin // we don't know the extent of its live-range anymore (now that it 206348777110a960f0e017025dd5141cb29472c3984David Goodwin // has been scheduled). If it is not live but was defined in the 207348777110a960f0e017025dd5141cb29472c3984David Goodwin // previous schedule region, then set its def index to the most 208348777110a960f0e017025dd5141cb29472c3984David Goodwin // conservative location (i.e. the beginning of the previous 209348777110a960f0e017025dd5141cb29472c3984David Goodwin // schedule region). 210e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin if (State->IsLive(Reg)) { 211e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin DEBUG(if (State->GetGroup(Reg) != 0) 2122973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach dbgs() << " " << TRI->getName(Reg) << "=g" << 213e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin State->GetGroup(Reg) << "->g0(region live-out)"); 214e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin State->UnionGroups(Reg, 0); 2152973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach } else if ((DefIndices[Reg] < InsertPosIndex) 2162973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach && (DefIndices[Reg] >= Count)) { 217348777110a960f0e017025dd5141cb29472c3984David Goodwin DefIndices[Reg] = Count; 218348777110a960f0e017025dd5141cb29472c3984David Goodwin } 219348777110a960f0e017025dd5141cb29472c3984David Goodwin } 2205393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << '\n'); 221348777110a960f0e017025dd5141cb29472c3984David Goodwin} 222348777110a960f0e017025dd5141cb29472c3984David Goodwin 223348777110a960f0e017025dd5141cb29472c3984David Goodwinbool AggressiveAntiDepBreaker::IsImplicitDefUse(MachineInstr *MI, 224347fa3fa26592b9792d100f3bf79b0695cf746f0Bob Wilson MachineOperand& MO) 225348777110a960f0e017025dd5141cb29472c3984David Goodwin{ 226348777110a960f0e017025dd5141cb29472c3984David Goodwin if (!MO.isReg() || !MO.isImplicit()) 227348777110a960f0e017025dd5141cb29472c3984David Goodwin return false; 228348777110a960f0e017025dd5141cb29472c3984David Goodwin 229348777110a960f0e017025dd5141cb29472c3984David Goodwin unsigned Reg = MO.getReg(); 230348777110a960f0e017025dd5141cb29472c3984David Goodwin if (Reg == 0) 231348777110a960f0e017025dd5141cb29472c3984David Goodwin return false; 232348777110a960f0e017025dd5141cb29472c3984David Goodwin 233348777110a960f0e017025dd5141cb29472c3984David Goodwin MachineOperand *Op = NULL; 234348777110a960f0e017025dd5141cb29472c3984David Goodwin if (MO.isDef()) 235348777110a960f0e017025dd5141cb29472c3984David Goodwin Op = MI->findRegisterUseOperand(Reg, true); 236348777110a960f0e017025dd5141cb29472c3984David Goodwin else 237348777110a960f0e017025dd5141cb29472c3984David Goodwin Op = MI->findRegisterDefOperand(Reg); 238348777110a960f0e017025dd5141cb29472c3984David Goodwin 239348777110a960f0e017025dd5141cb29472c3984David Goodwin return((Op != NULL) && Op->isImplicit()); 240348777110a960f0e017025dd5141cb29472c3984David Goodwin} 241348777110a960f0e017025dd5141cb29472c3984David Goodwin 242348777110a960f0e017025dd5141cb29472c3984David Goodwinvoid AggressiveAntiDepBreaker::GetPassthruRegs(MachineInstr *MI, 243348777110a960f0e017025dd5141cb29472c3984David Goodwin std::set<unsigned>& PassthruRegs) { 244348777110a960f0e017025dd5141cb29472c3984David Goodwin for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 245348777110a960f0e017025dd5141cb29472c3984David Goodwin MachineOperand &MO = MI->getOperand(i); 246348777110a960f0e017025dd5141cb29472c3984David Goodwin if (!MO.isReg()) continue; 2472973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach if ((MO.isDef() && MI->isRegTiedToUseOperand(i)) || 248348777110a960f0e017025dd5141cb29472c3984David Goodwin IsImplicitDefUse(MI, MO)) { 249348777110a960f0e017025dd5141cb29472c3984David Goodwin const unsigned Reg = MO.getReg(); 250348777110a960f0e017025dd5141cb29472c3984David Goodwin PassthruRegs.insert(Reg); 251396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) 252396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen PassthruRegs.insert(*SubRegs); 253348777110a960f0e017025dd5141cb29472c3984David Goodwin } 254348777110a960f0e017025dd5141cb29472c3984David Goodwin } 255348777110a960f0e017025dd5141cb29472c3984David Goodwin} 256348777110a960f0e017025dd5141cb29472c3984David Goodwin 257557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin/// AntiDepEdges - Return in Edges the anti- and output- dependencies 258557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin/// in SU that we want to consider for breaking. 25966db3a0f10e96ae190c8a46a1a8d5242928d068cDan Gohmanstatic void AntiDepEdges(const SUnit *SU, std::vector<const SDep*>& Edges) { 260557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin SmallSet<unsigned, 4> RegSet; 26166db3a0f10e96ae190c8a46a1a8d5242928d068cDan Gohman for (SUnit::const_pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end(); 262348777110a960f0e017025dd5141cb29472c3984David Goodwin P != PE; ++P) { 26312dd99dc308150a6beff32aafc824e1d6fec1139David Goodwin if ((P->getKind() == SDep::Anti) || (P->getKind() == SDep::Output)) { 264348777110a960f0e017025dd5141cb29472c3984David Goodwin unsigned Reg = P->getReg(); 265557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin if (RegSet.count(Reg) == 0) { 266348777110a960f0e017025dd5141cb29472c3984David Goodwin Edges.push_back(&*P); 267557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin RegSet.insert(Reg); 268348777110a960f0e017025dd5141cb29472c3984David Goodwin } 269348777110a960f0e017025dd5141cb29472c3984David Goodwin } 270348777110a960f0e017025dd5141cb29472c3984David Goodwin } 271348777110a960f0e017025dd5141cb29472c3984David Goodwin} 272348777110a960f0e017025dd5141cb29472c3984David Goodwin 27387d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin/// CriticalPathStep - Return the next SUnit after SU on the bottom-up 27487d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin/// critical path. 27566db3a0f10e96ae190c8a46a1a8d5242928d068cDan Gohmanstatic const SUnit *CriticalPathStep(const SUnit *SU) { 27666db3a0f10e96ae190c8a46a1a8d5242928d068cDan Gohman const SDep *Next = 0; 27787d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin unsigned NextDepth = 0; 27887d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin // Find the predecessor edge with the greatest depth. 27987d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin if (SU != 0) { 28066db3a0f10e96ae190c8a46a1a8d5242928d068cDan Gohman for (SUnit::const_pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end(); 28187d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin P != PE; ++P) { 28266db3a0f10e96ae190c8a46a1a8d5242928d068cDan Gohman const SUnit *PredSU = P->getSUnit(); 28387d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin unsigned PredLatency = P->getLatency(); 28487d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin unsigned PredTotalLatency = PredSU->getDepth() + PredLatency; 28587d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin // In the case of a latency tie, prefer an anti-dependency edge over 28687d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin // other types of edges. 28787d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin if (NextDepth < PredTotalLatency || 28887d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin (NextDepth == PredTotalLatency && P->getKind() == SDep::Anti)) { 28987d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin NextDepth = PredTotalLatency; 29087d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin Next = &*P; 29187d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin } 29287d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin } 29387d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin } 29487d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin 29587d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin return (Next) ? Next->getSUnit() : 0; 29687d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin} 29787d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin 29867a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwinvoid AggressiveAntiDepBreaker::HandleLastUse(unsigned Reg, unsigned KillIdx, 2992973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach const char *tag, 3002973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach const char *header, 3013e72d301e03de8edcd603a5d3e9486748dfa6887David Goodwin const char *footer) { 30238306d53f9319d0a36a059b229b807578cb2e5c5Bill Wendling std::vector<unsigned> &KillIndices = State->GetKillIndices(); 30338306d53f9319d0a36a059b229b807578cb2e5c5Bill Wendling std::vector<unsigned> &DefIndices = State->GetDefIndices(); 3042973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>& 30567a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin RegRefs = State->GetRegRefs(); 30667a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin 30767a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin if (!State->IsLive(Reg)) { 30867a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin KillIndices[Reg] = KillIdx; 30967a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin DefIndices[Reg] = ~0u; 31067a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin RegRefs.erase(Reg); 31167a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin State->LeaveGroup(Reg); 3123e72d301e03de8edcd603a5d3e9486748dfa6887David Goodwin DEBUG(if (header != NULL) { 3135393b2523419af71971be2286f34d3c8e2501898David Greene dbgs() << header << TRI->getName(Reg); header = NULL; }); 3145393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << "->g" << State->GetGroup(Reg) << tag); 31567a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin } 31667a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin // Repeat for subregisters. 317396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 318396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen unsigned SubregReg = *SubRegs; 31967a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin if (!State->IsLive(SubregReg)) { 32067a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin KillIndices[SubregReg] = KillIdx; 32167a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin DefIndices[SubregReg] = ~0u; 32267a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin RegRefs.erase(SubregReg); 32367a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin State->LeaveGroup(SubregReg); 3243e72d301e03de8edcd603a5d3e9486748dfa6887David Goodwin DEBUG(if (header != NULL) { 3255393b2523419af71971be2286f34d3c8e2501898David Greene dbgs() << header << TRI->getName(Reg); header = NULL; }); 3265393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << " " << TRI->getName(SubregReg) << "->g" << 32767a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin State->GetGroup(SubregReg) << tag); 32867a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin } 32967a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin } 3303e72d301e03de8edcd603a5d3e9486748dfa6887David Goodwin 3315393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(if ((header == NULL) && (footer != NULL)) dbgs() << footer); 33267a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin} 33367a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin 3342973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbachvoid AggressiveAntiDepBreaker::PrescanInstruction(MachineInstr *MI, 3352973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach unsigned Count, 336347fa3fa26592b9792d100f3bf79b0695cf746f0Bob Wilson std::set<unsigned>& PassthruRegs) { 33738306d53f9319d0a36a059b229b807578cb2e5c5Bill Wendling std::vector<unsigned> &DefIndices = State->GetDefIndices(); 3382973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>& 339e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin RegRefs = State->GetRegRefs(); 340e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin 34167a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin // Handle dead defs by simulating a last-use of the register just 3427a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner // after the def. A dead def can occur because the def is truly 34367a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin // dead, or because only a subregister is live at the def. If we 34467a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin // don't do this the dead def will be incorrectly merged into the 34567a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin // previous def. 346348777110a960f0e017025dd5141cb29472c3984David Goodwin for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 347348777110a960f0e017025dd5141cb29472c3984David Goodwin MachineOperand &MO = MI->getOperand(i); 348348777110a960f0e017025dd5141cb29472c3984David Goodwin if (!MO.isReg() || !MO.isDef()) continue; 349348777110a960f0e017025dd5141cb29472c3984David Goodwin unsigned Reg = MO.getReg(); 350348777110a960f0e017025dd5141cb29472c3984David Goodwin if (Reg == 0) continue; 3512973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 3523e72d301e03de8edcd603a5d3e9486748dfa6887David Goodwin HandleLastUse(Reg, Count + 1, "", "\tDead Def: ", "\n"); 353348777110a960f0e017025dd5141cb29472c3984David Goodwin } 354348777110a960f0e017025dd5141cb29472c3984David Goodwin 3555393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << "\tDef Groups:"); 356348777110a960f0e017025dd5141cb29472c3984David Goodwin for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 357348777110a960f0e017025dd5141cb29472c3984David Goodwin MachineOperand &MO = MI->getOperand(i); 358348777110a960f0e017025dd5141cb29472c3984David Goodwin if (!MO.isReg() || !MO.isDef()) continue; 359348777110a960f0e017025dd5141cb29472c3984David Goodwin unsigned Reg = MO.getReg(); 360348777110a960f0e017025dd5141cb29472c3984David Goodwin if (Reg == 0) continue; 361348777110a960f0e017025dd5141cb29472c3984David Goodwin 3622973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach DEBUG(dbgs() << " " << TRI->getName(Reg) << "=g" << State->GetGroup(Reg)); 363348777110a960f0e017025dd5141cb29472c3984David Goodwin 36467a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin // If MI's defs have a special allocation requirement, don't allow 365348777110a960f0e017025dd5141cb29472c3984David Goodwin // any def registers to be changed. Also assume all registers 366348777110a960f0e017025dd5141cb29472c3984David Goodwin // defined in a call must not be changed (ABI). 3675a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (MI->isCall() || MI->hasExtraDefRegAllocReq() || 36846df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng TII->isPredicated(MI)) { 3695393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(if (State->GetGroup(Reg) != 0) dbgs() << "->g0(alloc-req)"); 370e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin State->UnionGroups(Reg, 0); 371348777110a960f0e017025dd5141cb29472c3984David Goodwin } 372348777110a960f0e017025dd5141cb29472c3984David Goodwin 373348777110a960f0e017025dd5141cb29472c3984David Goodwin // Any aliased that are live at this point are completely or 37467a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin // partially defined here, so group those aliases with Reg. 375396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCRegAliasIterator AI(Reg, TRI, false); AI.isValid(); ++AI) { 376396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen unsigned AliasReg = *AI; 377e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin if (State->IsLive(AliasReg)) { 378e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin State->UnionGroups(Reg, AliasReg); 3792973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach DEBUG(dbgs() << "->g" << State->GetGroup(Reg) << "(via " << 380348777110a960f0e017025dd5141cb29472c3984David Goodwin TRI->getName(AliasReg) << ")"); 381348777110a960f0e017025dd5141cb29472c3984David Goodwin } 382348777110a960f0e017025dd5141cb29472c3984David Goodwin } 3832973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 384348777110a960f0e017025dd5141cb29472c3984David Goodwin // Note register reference... 385348777110a960f0e017025dd5141cb29472c3984David Goodwin const TargetRegisterClass *RC = NULL; 386348777110a960f0e017025dd5141cb29472c3984David Goodwin if (i < MI->getDesc().getNumOperands()) 387397fc4874efe9c17e737d4c5c50bd19dc3bf27f5Jakob Stoklund Olesen RC = TII->getRegClass(MI->getDesc(), i, TRI, MF); 388e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin AggressiveAntiDepState::RegisterReference RR = { &MO, RC }; 389348777110a960f0e017025dd5141cb29472c3984David Goodwin RegRefs.insert(std::make_pair(Reg, RR)); 390348777110a960f0e017025dd5141cb29472c3984David Goodwin } 391348777110a960f0e017025dd5141cb29472c3984David Goodwin 3925393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << '\n'); 39367a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin 39467a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin // Scan the register defs for this instruction and update 39567a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin // live-ranges. 39667a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 39767a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin MachineOperand &MO = MI->getOperand(i); 39867a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin if (!MO.isReg() || !MO.isDef()) continue; 39967a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin unsigned Reg = MO.getReg(); 40067a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin if (Reg == 0) continue; 4013e72d301e03de8edcd603a5d3e9486748dfa6887David Goodwin // Ignore KILLs and passthru registers for liveness... 402518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isKill() || (PassthruRegs.count(Reg) != 0)) 4033e72d301e03de8edcd603a5d3e9486748dfa6887David Goodwin continue; 40467a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin 4053e72d301e03de8edcd603a5d3e9486748dfa6887David Goodwin // Update def for Reg and aliases. 406396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) 407396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen DefIndices[*AI] = Count; 40867a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin } 409348777110a960f0e017025dd5141cb29472c3984David Goodwin} 410348777110a960f0e017025dd5141cb29472c3984David Goodwin 411348777110a960f0e017025dd5141cb29472c3984David Goodwinvoid AggressiveAntiDepBreaker::ScanInstruction(MachineInstr *MI, 412347fa3fa26592b9792d100f3bf79b0695cf746f0Bob Wilson unsigned Count) { 4135393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << "\tUse Groups:"); 4142973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>& 415e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin RegRefs = State->GetRegRefs(); 416348777110a960f0e017025dd5141cb29472c3984David Goodwin 41746df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng // If MI's uses have special allocation requirement, don't allow 41846df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng // any use registers to be changed. Also assume all registers 41946df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng // used in a call must not be changed (ABI). 42046df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng // FIXME: The issue with predicated instruction is more complex. We are being 42146df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng // conservatively here because the kill markers cannot be trusted after 42246df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng // if-conversion: 42346df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng // %R6<def> = LDR %SP, %reg0, 92, pred:14, pred:%reg0; mem:LD4[FixedStack14] 42446df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng // ... 42546df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng // STR %R0, %R6<kill>, %reg0, 0, pred:0, pred:%CPSR; mem:ST4[%395] 42646df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng // %R6<def> = LDR %SP, %reg0, 100, pred:0, pred:%CPSR; mem:LD4[FixedStack12] 42746df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng // STR %R0, %R6<kill>, %reg0, 0, pred:14, pred:%reg0; mem:ST4[%396](align=8) 42846df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng // 42946df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng // The first R6 kill is not really a kill since it's killed by a predicated 43046df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng // instruction which may not be executed. The second R6 def may or may not 43146df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng // re-define R6 so it's not safe to change it since the last R6 use cannot be 43246df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng // changed. 4335a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng bool Special = MI->isCall() || 4345a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng MI->hasExtraSrcRegAllocReq() || 43546df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng TII->isPredicated(MI); 43646df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng 437348777110a960f0e017025dd5141cb29472c3984David Goodwin // Scan the register uses for this instruction and update 438348777110a960f0e017025dd5141cb29472c3984David Goodwin // live-ranges, groups and RegRefs. 439348777110a960f0e017025dd5141cb29472c3984David Goodwin for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 440348777110a960f0e017025dd5141cb29472c3984David Goodwin MachineOperand &MO = MI->getOperand(i); 441348777110a960f0e017025dd5141cb29472c3984David Goodwin if (!MO.isReg() || !MO.isUse()) continue; 442348777110a960f0e017025dd5141cb29472c3984David Goodwin unsigned Reg = MO.getReg(); 443348777110a960f0e017025dd5141cb29472c3984David Goodwin if (Reg == 0) continue; 4442973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 4452973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach DEBUG(dbgs() << " " << TRI->getName(Reg) << "=g" << 4462973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach State->GetGroup(Reg)); 447348777110a960f0e017025dd5141cb29472c3984David Goodwin 448348777110a960f0e017025dd5141cb29472c3984David Goodwin // It wasn't previously live but now it is, this is a kill. Forget 449348777110a960f0e017025dd5141cb29472c3984David Goodwin // the previous live-range information and start a new live-range 450348777110a960f0e017025dd5141cb29472c3984David Goodwin // for the register. 45167a8a7b3bd5afefc8057e365bd5f5c7330b3dd1aDavid Goodwin HandleLastUse(Reg, Count, "(last-use)"); 452348777110a960f0e017025dd5141cb29472c3984David Goodwin 45346df4eb46e784036cf895db271fe29e1cf2a975aEvan Cheng if (Special) { 4545393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(if (State->GetGroup(Reg) != 0) dbgs() << "->g0(alloc-req)"); 455e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin State->UnionGroups(Reg, 0); 456348777110a960f0e017025dd5141cb29472c3984David Goodwin } 457348777110a960f0e017025dd5141cb29472c3984David Goodwin 458348777110a960f0e017025dd5141cb29472c3984David Goodwin // Note register reference... 459348777110a960f0e017025dd5141cb29472c3984David Goodwin const TargetRegisterClass *RC = NULL; 460348777110a960f0e017025dd5141cb29472c3984David Goodwin if (i < MI->getDesc().getNumOperands()) 461397fc4874efe9c17e737d4c5c50bd19dc3bf27f5Jakob Stoklund Olesen RC = TII->getRegClass(MI->getDesc(), i, TRI, MF); 462e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin AggressiveAntiDepState::RegisterReference RR = { &MO, RC }; 463348777110a960f0e017025dd5141cb29472c3984David Goodwin RegRefs.insert(std::make_pair(Reg, RR)); 464348777110a960f0e017025dd5141cb29472c3984David Goodwin } 4652973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 4665393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << '\n'); 467348777110a960f0e017025dd5141cb29472c3984David Goodwin 468348777110a960f0e017025dd5141cb29472c3984David Goodwin // Form a group of all defs and uses of a KILL instruction to ensure 469348777110a960f0e017025dd5141cb29472c3984David Goodwin // that all registers are renamed as a group. 470518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isKill()) { 4715393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << "\tKill Group:"); 472348777110a960f0e017025dd5141cb29472c3984David Goodwin 473348777110a960f0e017025dd5141cb29472c3984David Goodwin unsigned FirstReg = 0; 474348777110a960f0e017025dd5141cb29472c3984David Goodwin for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 475348777110a960f0e017025dd5141cb29472c3984David Goodwin MachineOperand &MO = MI->getOperand(i); 476348777110a960f0e017025dd5141cb29472c3984David Goodwin if (!MO.isReg()) continue; 477348777110a960f0e017025dd5141cb29472c3984David Goodwin unsigned Reg = MO.getReg(); 478348777110a960f0e017025dd5141cb29472c3984David Goodwin if (Reg == 0) continue; 4792973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 480348777110a960f0e017025dd5141cb29472c3984David Goodwin if (FirstReg != 0) { 4815393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << "=" << TRI->getName(Reg)); 482e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin State->UnionGroups(FirstReg, Reg); 483348777110a960f0e017025dd5141cb29472c3984David Goodwin } else { 4845393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << " " << TRI->getName(Reg)); 485348777110a960f0e017025dd5141cb29472c3984David Goodwin FirstReg = Reg; 486348777110a960f0e017025dd5141cb29472c3984David Goodwin } 487348777110a960f0e017025dd5141cb29472c3984David Goodwin } 4882973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 4895393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << "->g" << State->GetGroup(FirstReg) << '\n'); 490348777110a960f0e017025dd5141cb29472c3984David Goodwin } 491348777110a960f0e017025dd5141cb29472c3984David Goodwin} 492348777110a960f0e017025dd5141cb29472c3984David Goodwin 493348777110a960f0e017025dd5141cb29472c3984David GoodwinBitVector AggressiveAntiDepBreaker::GetRenameRegisters(unsigned Reg) { 494348777110a960f0e017025dd5141cb29472c3984David Goodwin BitVector BV(TRI->getNumRegs(), false); 495348777110a960f0e017025dd5141cb29472c3984David Goodwin bool first = true; 496348777110a960f0e017025dd5141cb29472c3984David Goodwin 497348777110a960f0e017025dd5141cb29472c3984David Goodwin // Check all references that need rewriting for Reg. For each, use 498348777110a960f0e017025dd5141cb29472c3984David Goodwin // the corresponding register class to narrow the set of registers 499348777110a960f0e017025dd5141cb29472c3984David Goodwin // that are appropriate for renaming. 5002973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach std::pair<std::multimap<unsigned, 501e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin AggressiveAntiDepState::RegisterReference>::iterator, 502e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin std::multimap<unsigned, 503e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin AggressiveAntiDepState::RegisterReference>::iterator> 504e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin Range = State->GetRegRefs().equal_range(Reg); 5052973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach for (std::multimap<unsigned, 5062973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach AggressiveAntiDepState::RegisterReference>::iterator Q = Range.first, 5072973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach QE = Range.second; Q != QE; ++Q) { 508348777110a960f0e017025dd5141cb29472c3984David Goodwin const TargetRegisterClass *RC = Q->second.RC; 509348777110a960f0e017025dd5141cb29472c3984David Goodwin if (RC == NULL) continue; 510348777110a960f0e017025dd5141cb29472c3984David Goodwin 511348777110a960f0e017025dd5141cb29472c3984David Goodwin BitVector RCBV = TRI->getAllocatableSet(MF, RC); 512348777110a960f0e017025dd5141cb29472c3984David Goodwin if (first) { 513348777110a960f0e017025dd5141cb29472c3984David Goodwin BV |= RCBV; 514348777110a960f0e017025dd5141cb29472c3984David Goodwin first = false; 515348777110a960f0e017025dd5141cb29472c3984David Goodwin } else { 516348777110a960f0e017025dd5141cb29472c3984David Goodwin BV &= RCBV; 517348777110a960f0e017025dd5141cb29472c3984David Goodwin } 518348777110a960f0e017025dd5141cb29472c3984David Goodwin 5195393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << " " << RC->getName()); 520348777110a960f0e017025dd5141cb29472c3984David Goodwin } 5212973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 522348777110a960f0e017025dd5141cb29472c3984David Goodwin return BV; 5232973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach} 524348777110a960f0e017025dd5141cb29472c3984David Goodwin 525348777110a960f0e017025dd5141cb29472c3984David Goodwinbool AggressiveAntiDepBreaker::FindSuitableFreeRegisters( 52654097836f31660bd5e84c34ee8c92d237844315fDavid Goodwin unsigned AntiDepGroupIndex, 52754097836f31660bd5e84c34ee8c92d237844315fDavid Goodwin RenameOrderType& RenameOrder, 52854097836f31660bd5e84c34ee8c92d237844315fDavid Goodwin std::map<unsigned, unsigned> &RenameMap) { 52938306d53f9319d0a36a059b229b807578cb2e5c5Bill Wendling std::vector<unsigned> &KillIndices = State->GetKillIndices(); 53038306d53f9319d0a36a059b229b807578cb2e5c5Bill Wendling std::vector<unsigned> &DefIndices = State->GetDefIndices(); 5312973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>& 532e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin RegRefs = State->GetRegRefs(); 533e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin 53487d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin // Collect all referenced registers in the same group as 53587d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin // AntiDepReg. These all need to be renamed together if we are to 53687d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin // break the anti-dependence. 537348777110a960f0e017025dd5141cb29472c3984David Goodwin std::vector<unsigned> Regs; 53887d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin State->GetGroupRegs(AntiDepGroupIndex, Regs, &RegRefs); 539348777110a960f0e017025dd5141cb29472c3984David Goodwin assert(Regs.size() > 0 && "Empty register group!"); 540348777110a960f0e017025dd5141cb29472c3984David Goodwin if (Regs.size() == 0) 541348777110a960f0e017025dd5141cb29472c3984David Goodwin return false; 542348777110a960f0e017025dd5141cb29472c3984David Goodwin 543348777110a960f0e017025dd5141cb29472c3984David Goodwin // Find the "superest" register in the group. At the same time, 544348777110a960f0e017025dd5141cb29472c3984David Goodwin // collect the BitVector of registers that can be used to rename 545348777110a960f0e017025dd5141cb29472c3984David Goodwin // each register. 5462973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach DEBUG(dbgs() << "\tRename Candidates for Group g" << AntiDepGroupIndex 5472973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach << ":\n"); 548348777110a960f0e017025dd5141cb29472c3984David Goodwin std::map<unsigned, BitVector> RenameRegisterMap; 549348777110a960f0e017025dd5141cb29472c3984David Goodwin unsigned SuperReg = 0; 550348777110a960f0e017025dd5141cb29472c3984David Goodwin for (unsigned i = 0, e = Regs.size(); i != e; ++i) { 551348777110a960f0e017025dd5141cb29472c3984David Goodwin unsigned Reg = Regs[i]; 552348777110a960f0e017025dd5141cb29472c3984David Goodwin if ((SuperReg == 0) || TRI->isSuperRegister(SuperReg, Reg)) 553348777110a960f0e017025dd5141cb29472c3984David Goodwin SuperReg = Reg; 554348777110a960f0e017025dd5141cb29472c3984David Goodwin 555348777110a960f0e017025dd5141cb29472c3984David Goodwin // If Reg has any references, then collect possible rename regs 556348777110a960f0e017025dd5141cb29472c3984David Goodwin if (RegRefs.count(Reg) > 0) { 5575393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << "\t\t" << TRI->getName(Reg) << ":"); 5582973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 559348777110a960f0e017025dd5141cb29472c3984David Goodwin BitVector BV = GetRenameRegisters(Reg); 560348777110a960f0e017025dd5141cb29472c3984David Goodwin RenameRegisterMap.insert(std::pair<unsigned, BitVector>(Reg, BV)); 561348777110a960f0e017025dd5141cb29472c3984David Goodwin 5625393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << " ::"); 563348777110a960f0e017025dd5141cb29472c3984David Goodwin DEBUG(for (int r = BV.find_first(); r != -1; r = BV.find_next(r)) 5645393b2523419af71971be2286f34d3c8e2501898David Greene dbgs() << " " << TRI->getName(r)); 5655393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << "\n"); 566348777110a960f0e017025dd5141cb29472c3984David Goodwin } 567348777110a960f0e017025dd5141cb29472c3984David Goodwin } 568348777110a960f0e017025dd5141cb29472c3984David Goodwin 569348777110a960f0e017025dd5141cb29472c3984David Goodwin // All group registers should be a subreg of SuperReg. 570348777110a960f0e017025dd5141cb29472c3984David Goodwin for (unsigned i = 0, e = Regs.size(); i != e; ++i) { 571348777110a960f0e017025dd5141cb29472c3984David Goodwin unsigned Reg = Regs[i]; 572348777110a960f0e017025dd5141cb29472c3984David Goodwin if (Reg == SuperReg) continue; 573348777110a960f0e017025dd5141cb29472c3984David Goodwin bool IsSub = TRI->isSubRegister(SuperReg, Reg); 574348777110a960f0e017025dd5141cb29472c3984David Goodwin assert(IsSub && "Expecting group subregister"); 575348777110a960f0e017025dd5141cb29472c3984David Goodwin if (!IsSub) 576348777110a960f0e017025dd5141cb29472c3984David Goodwin return false; 577348777110a960f0e017025dd5141cb29472c3984David Goodwin } 578348777110a960f0e017025dd5141cb29472c3984David Goodwin 57900621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin#ifndef NDEBUG 58000621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin // If DebugDiv > 0 then only rename (renamecnt % DebugDiv) == DebugMod 58100621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin if (DebugDiv > 0) { 58200621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin static int renamecnt = 0; 58300621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin if (renamecnt++ % DebugDiv != DebugMod) 58400621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin return false; 5852973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 5865393b2523419af71971be2286f34d3c8e2501898David Greene dbgs() << "*** Performing rename " << TRI->getName(SuperReg) << 58700621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin " for debug ***\n"; 58800621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin } 58900621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin#endif 59000621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin 59154097836f31660bd5e84c34ee8c92d237844315fDavid Goodwin // Check each possible rename register for SuperReg in round-robin 59254097836f31660bd5e84c34ee8c92d237844315fDavid Goodwin // order. If that register is available, and the corresponding 59354097836f31660bd5e84c34ee8c92d237844315fDavid Goodwin // registers are available for the other group subregisters, then we 59454097836f31660bd5e84c34ee8c92d237844315fDavid Goodwin // can use those registers to rename. 5957e1b566322ecb5ff752c9a5f2feb503b6fb75262Rafael Espindola 5967e1b566322ecb5ff752c9a5f2feb503b6fb75262Rafael Espindola // FIXME: Using getMinimalPhysRegClass is very conservative. We should 5977e1b566322ecb5ff752c9a5f2feb503b6fb75262Rafael Espindola // check every use of the register and find the largest register class 5987e1b566322ecb5ff752c9a5f2feb503b6fb75262Rafael Espindola // that can be used in all of them. 5992973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach const TargetRegisterClass *SuperRC = 6007e1b566322ecb5ff752c9a5f2feb503b6fb75262Rafael Espindola TRI->getMinimalPhysRegClass(SuperReg, MVT::Other); 6012973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 60239b5c0c049a19c7a7feffc9506da07923cc136e4Jakob Stoklund Olesen ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(SuperRC); 603fa796dd720f1b34596a043f17f098fac18ecc028Jakob Stoklund Olesen if (Order.empty()) { 6045393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << "\tEmpty Super Regclass!!\n"); 60554097836f31660bd5e84c34ee8c92d237844315fDavid Goodwin return false; 60654097836f31660bd5e84c34ee8c92d237844315fDavid Goodwin } 60754097836f31660bd5e84c34ee8c92d237844315fDavid Goodwin 6085393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << "\tFind Registers:"); 6093e72d301e03de8edcd603a5d3e9486748dfa6887David Goodwin 61054097836f31660bd5e84c34ee8c92d237844315fDavid Goodwin if (RenameOrder.count(SuperRC) == 0) 611fa796dd720f1b34596a043f17f098fac18ecc028Jakob Stoklund Olesen RenameOrder.insert(RenameOrderType::value_type(SuperRC, Order.size())); 61254097836f31660bd5e84c34ee8c92d237844315fDavid Goodwin 613fa796dd720f1b34596a043f17f098fac18ecc028Jakob Stoklund Olesen unsigned OrigR = RenameOrder[SuperRC]; 614fa796dd720f1b34596a043f17f098fac18ecc028Jakob Stoklund Olesen unsigned EndR = ((OrigR == Order.size()) ? 0 : OrigR); 615fa796dd720f1b34596a043f17f098fac18ecc028Jakob Stoklund Olesen unsigned R = OrigR; 61654097836f31660bd5e84c34ee8c92d237844315fDavid Goodwin do { 617fa796dd720f1b34596a043f17f098fac18ecc028Jakob Stoklund Olesen if (R == 0) R = Order.size(); 61854097836f31660bd5e84c34ee8c92d237844315fDavid Goodwin --R; 619fa796dd720f1b34596a043f17f098fac18ecc028Jakob Stoklund Olesen const unsigned NewSuperReg = Order[R]; 6209b041c92efb5b0f6e74e154f0a6151968dc1ab58Jim Grosbach // Don't consider non-allocatable registers 62114d1dd95c7c969e07defebb6fe65df2fae1b30cfJakob Stoklund Olesen if (!MRI.isAllocatable(NewSuperReg)) continue; 622348777110a960f0e017025dd5141cb29472c3984David Goodwin // Don't replace a register with itself. 62300621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin if (NewSuperReg == SuperReg) continue; 6242973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 6255393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << " [" << TRI->getName(NewSuperReg) << ':'); 62600621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin RenameMap.clear(); 62700621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin 62800621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin // For each referenced group register (which must be a SuperReg or 62900621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin // a subregister of SuperReg), find the corresponding subregister 63000621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin // of NewSuperReg and make sure it is free to be renamed. 63100621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin for (unsigned i = 0, e = Regs.size(); i != e; ++i) { 63200621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin unsigned Reg = Regs[i]; 63300621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin unsigned NewReg = 0; 63400621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin if (Reg == SuperReg) { 63500621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin NewReg = NewSuperReg; 63600621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin } else { 63700621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin unsigned NewSubRegIdx = TRI->getSubRegIndex(SuperReg, Reg); 63800621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin if (NewSubRegIdx != 0) 63900621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin NewReg = TRI->getSubReg(NewSuperReg, NewSubRegIdx); 64000621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin } 64100621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin 6425393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << " " << TRI->getName(NewReg)); 6432973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 64400621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin // Check if Reg can be renamed to NewReg. 64500621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin BitVector BV = RenameRegisterMap[Reg]; 64600621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin if (!BV.test(NewReg)) { 6475393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << "(no rename)"); 64800621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin goto next_super_reg; 64900621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin } 65000621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin 65100621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin // If NewReg is dead and NewReg's most recent def is not before 65200621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin // Regs's kill, it's safe to replace Reg with NewReg. We 65300621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin // must also check all aliases of NewReg, because we can't define a 65400621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin // register when any sub or super is already live. 65500621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin if (State->IsLive(NewReg) || (KillIndices[Reg] > DefIndices[NewReg])) { 6565393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << "(live)"); 65700621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin goto next_super_reg; 65800621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin } else { 65900621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin bool found = false; 660396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCRegAliasIterator AI(NewReg, TRI, false); AI.isValid(); ++AI) { 661396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen unsigned AliasReg = *AI; 6622973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach if (State->IsLive(AliasReg) || 6632973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach (KillIndices[Reg] > DefIndices[AliasReg])) { 6645393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << "(alias " << TRI->getName(AliasReg) << " live)"); 66500621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin found = true; 66600621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin break; 66700621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin } 668348777110a960f0e017025dd5141cb29472c3984David Goodwin } 66900621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin if (found) 67000621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin goto next_super_reg; 671348777110a960f0e017025dd5141cb29472c3984David Goodwin } 6722973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 67300621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin // Record that 'Reg' can be renamed to 'NewReg'. 67400621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin RenameMap.insert(std::pair<unsigned, unsigned>(Reg, NewReg)); 675348777110a960f0e017025dd5141cb29472c3984David Goodwin } 6762973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 67700621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin // If we fall-out here, then every register in the group can be 67800621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin // renamed, as recorded in RenameMap. 67900621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin RenameOrder.erase(SuperRC); 68000621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin RenameOrder.insert(RenameOrderType::value_type(SuperRC, R)); 6815393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << "]\n"); 68200621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin return true; 68300621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin 68400621efb40edb7fe16bf2af6d4699c9d024a28e7David Goodwin next_super_reg: 6855393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << ']'); 68654097836f31660bd5e84c34ee8c92d237844315fDavid Goodwin } while (R != EndR); 687348777110a960f0e017025dd5141cb29472c3984David Goodwin 6885393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << '\n'); 689348777110a960f0e017025dd5141cb29472c3984David Goodwin 690348777110a960f0e017025dd5141cb29472c3984David Goodwin // No registers are free and available! 691348777110a960f0e017025dd5141cb29472c3984David Goodwin return false; 692348777110a960f0e017025dd5141cb29472c3984David Goodwin} 693348777110a960f0e017025dd5141cb29472c3984David Goodwin 694348777110a960f0e017025dd5141cb29472c3984David Goodwin/// BreakAntiDependencies - Identifiy anti-dependencies within the 695348777110a960f0e017025dd5141cb29472c3984David Goodwin/// ScheduleDAG and break them by renaming registers. 696348777110a960f0e017025dd5141cb29472c3984David Goodwin/// 697e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwinunsigned AggressiveAntiDepBreaker::BreakAntiDependencies( 69866db3a0f10e96ae190c8a46a1a8d5242928d068cDan Gohman const std::vector<SUnit>& SUnits, 69966db3a0f10e96ae190c8a46a1a8d5242928d068cDan Gohman MachineBasicBlock::iterator Begin, 70066db3a0f10e96ae190c8a46a1a8d5242928d068cDan Gohman MachineBasicBlock::iterator End, 701e29e8e100ea38be1771e5f010a5511cbb990d515Devang Patel unsigned InsertPosIndex, 702e29e8e100ea38be1771e5f010a5511cbb990d515Devang Patel DbgValueVector &DbgValues) { 703e29e8e100ea38be1771e5f010a5511cbb990d515Devang Patel 70438306d53f9319d0a36a059b229b807578cb2e5c5Bill Wendling std::vector<unsigned> &KillIndices = State->GetKillIndices(); 70538306d53f9319d0a36a059b229b807578cb2e5c5Bill Wendling std::vector<unsigned> &DefIndices = State->GetDefIndices(); 7062973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>& 707e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin RegRefs = State->GetRegRefs(); 708e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin 709348777110a960f0e017025dd5141cb29472c3984David Goodwin // The code below assumes that there is at least one instruction, 710348777110a960f0e017025dd5141cb29472c3984David Goodwin // so just duck out immediately if the block is empty. 7114de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin if (SUnits.empty()) return 0; 7122973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 71354097836f31660bd5e84c34ee8c92d237844315fDavid Goodwin // For each regclass the next register to use for renaming. 71454097836f31660bd5e84c34ee8c92d237844315fDavid Goodwin RenameOrderType RenameOrder; 715348777110a960f0e017025dd5141cb29472c3984David Goodwin 716348777110a960f0e017025dd5141cb29472c3984David Goodwin // ...need a map from MI to SUnit. 71766db3a0f10e96ae190c8a46a1a8d5242928d068cDan Gohman std::map<MachineInstr *, const SUnit *> MISUnitMap; 718348777110a960f0e017025dd5141cb29472c3984David Goodwin for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 71966db3a0f10e96ae190c8a46a1a8d5242928d068cDan Gohman const SUnit *SU = &SUnits[i]; 72066db3a0f10e96ae190c8a46a1a8d5242928d068cDan Gohman MISUnitMap.insert(std::pair<MachineInstr *, const SUnit *>(SU->getInstr(), 72166db3a0f10e96ae190c8a46a1a8d5242928d068cDan Gohman SU)); 722348777110a960f0e017025dd5141cb29472c3984David Goodwin } 723348777110a960f0e017025dd5141cb29472c3984David Goodwin 72487d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin // Track progress along the critical path through the SUnit graph as 72587d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin // we walk the instructions. This is needed for regclasses that only 72687d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin // break critical-path anti-dependencies. 72766db3a0f10e96ae190c8a46a1a8d5242928d068cDan Gohman const SUnit *CriticalPathSU = 0; 72887d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin MachineInstr *CriticalPathMI = 0; 72987d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin if (CriticalPathSet.any()) { 73087d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 73166db3a0f10e96ae190c8a46a1a8d5242928d068cDan Gohman const SUnit *SU = &SUnits[i]; 7322973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach if (!CriticalPathSU || 7332973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach ((SU->getDepth() + SU->Latency) > 73487d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin (CriticalPathSU->getDepth() + CriticalPathSU->Latency))) { 73587d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin CriticalPathSU = SU; 73687d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin } 73787d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin } 7382973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 73987d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin CriticalPathMI = CriticalPathSU->getInstr(); 74087d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin } 74187d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin 7422973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach#ifndef NDEBUG 7435393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << "\n===== Aggressive anti-dependency breaking\n"); 7445393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << "Available regs:"); 745557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin for (unsigned Reg = 0; Reg < TRI->getNumRegs(); ++Reg) { 746557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin if (!State->IsLive(Reg)) 7475393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << " " << TRI->getName(Reg)); 748348777110a960f0e017025dd5141cb29472c3984David Goodwin } 7495393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << '\n'); 750348777110a960f0e017025dd5141cb29472c3984David Goodwin#endif 751348777110a960f0e017025dd5141cb29472c3984David Goodwin 752348777110a960f0e017025dd5141cb29472c3984David Goodwin // Attempt to break anti-dependence edges. Walk the instructions 753348777110a960f0e017025dd5141cb29472c3984David Goodwin // from the bottom up, tracking information about liveness as we go 754348777110a960f0e017025dd5141cb29472c3984David Goodwin // to help determine which registers are available. 755348777110a960f0e017025dd5141cb29472c3984David Goodwin unsigned Broken = 0; 756348777110a960f0e017025dd5141cb29472c3984David Goodwin unsigned Count = InsertPosIndex - 1; 757348777110a960f0e017025dd5141cb29472c3984David Goodwin for (MachineBasicBlock::iterator I = End, E = Begin; 758348777110a960f0e017025dd5141cb29472c3984David Goodwin I != E; --Count) { 759348777110a960f0e017025dd5141cb29472c3984David Goodwin MachineInstr *MI = --I; 760348777110a960f0e017025dd5141cb29472c3984David Goodwin 761504d1d2fa4103bddcc6e1ad26697029c79b4aeb7Hal Finkel if (MI->isDebugValue()) 762504d1d2fa4103bddcc6e1ad26697029c79b4aeb7Hal Finkel continue; 763504d1d2fa4103bddcc6e1ad26697029c79b4aeb7Hal Finkel 7645393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << "Anti: "); 765348777110a960f0e017025dd5141cb29472c3984David Goodwin DEBUG(MI->dump()); 766348777110a960f0e017025dd5141cb29472c3984David Goodwin 767348777110a960f0e017025dd5141cb29472c3984David Goodwin std::set<unsigned> PassthruRegs; 768348777110a960f0e017025dd5141cb29472c3984David Goodwin GetPassthruRegs(MI, PassthruRegs); 769348777110a960f0e017025dd5141cb29472c3984David Goodwin 770348777110a960f0e017025dd5141cb29472c3984David Goodwin // Process the defs in MI... 771348777110a960f0e017025dd5141cb29472c3984David Goodwin PrescanInstruction(MI, Count, PassthruRegs); 7722973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 773557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin // The dependence edges that represent anti- and output- 77487d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin // dependencies that are candidates for breaking. 77566db3a0f10e96ae190c8a46a1a8d5242928d068cDan Gohman std::vector<const SDep *> Edges; 77666db3a0f10e96ae190c8a46a1a8d5242928d068cDan Gohman const SUnit *PathSU = MISUnitMap[MI]; 777557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin AntiDepEdges(PathSU, Edges); 77887d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin 77987d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin // If MI is not on the critical path, then we don't rename 78087d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin // registers in the CriticalPathSet. 78187d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin BitVector *ExcludeRegs = NULL; 78287d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin if (MI == CriticalPathMI) { 78387d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin CriticalPathSU = CriticalPathStep(CriticalPathSU); 78487d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin CriticalPathMI = (CriticalPathSU) ? CriticalPathSU->getInstr() : 0; 7852973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach } else { 78687d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin ExcludeRegs = &CriticalPathSet; 78787d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin } 78887d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin 789348777110a960f0e017025dd5141cb29472c3984David Goodwin // Ignore KILL instructions (they form a group in ScanInstruction 790348777110a960f0e017025dd5141cb29472c3984David Goodwin // but don't cause any anti-dependence breaking themselves) 791518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (!MI->isKill()) { 792348777110a960f0e017025dd5141cb29472c3984David Goodwin // Attempt to break each anti-dependency... 793348777110a960f0e017025dd5141cb29472c3984David Goodwin for (unsigned i = 0, e = Edges.size(); i != e; ++i) { 79466db3a0f10e96ae190c8a46a1a8d5242928d068cDan Gohman const SDep *Edge = Edges[i]; 795348777110a960f0e017025dd5141cb29472c3984David Goodwin SUnit *NextSU = Edge->getSUnit(); 7962973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 79712dd99dc308150a6beff32aafc824e1d6fec1139David Goodwin if ((Edge->getKind() != SDep::Anti) && 79812dd99dc308150a6beff32aafc824e1d6fec1139David Goodwin (Edge->getKind() != SDep::Output)) continue; 7992973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 800348777110a960f0e017025dd5141cb29472c3984David Goodwin unsigned AntiDepReg = Edge->getReg(); 8015393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << "\tAntidep reg: " << TRI->getName(AntiDepReg)); 802348777110a960f0e017025dd5141cb29472c3984David Goodwin assert(AntiDepReg != 0 && "Anti-dependence on reg0?"); 8032973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 80414d1dd95c7c969e07defebb6fe65df2fae1b30cfJakob Stoklund Olesen if (!MRI.isAllocatable(AntiDepReg)) { 805348777110a960f0e017025dd5141cb29472c3984David Goodwin // Don't break anti-dependencies on non-allocatable registers. 8065393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << " (non-allocatable)\n"); 807348777110a960f0e017025dd5141cb29472c3984David Goodwin continue; 80887d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin } else if ((ExcludeRegs != NULL) && ExcludeRegs->test(AntiDepReg)) { 80987d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin // Don't break anti-dependencies for critical path registers 81087d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin // if not on the critical path 8115393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << " (not critical-path)\n"); 81287d21b92fc42f6b3bd8567a83fc5b5191c1205e5David Goodwin continue; 813348777110a960f0e017025dd5141cb29472c3984David Goodwin } else if (PassthruRegs.count(AntiDepReg) != 0) { 814348777110a960f0e017025dd5141cb29472c3984David Goodwin // If the anti-dep register liveness "passes-thru", then 815348777110a960f0e017025dd5141cb29472c3984David Goodwin // don't try to change it. It will be changed along with 816348777110a960f0e017025dd5141cb29472c3984David Goodwin // the use if required to break an earlier antidep. 8175393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << " (passthru)\n"); 818348777110a960f0e017025dd5141cb29472c3984David Goodwin continue; 819348777110a960f0e017025dd5141cb29472c3984David Goodwin } else { 820348777110a960f0e017025dd5141cb29472c3984David Goodwin // No anti-dep breaking for implicit deps 821348777110a960f0e017025dd5141cb29472c3984David Goodwin MachineOperand *AntiDepOp = MI->findRegisterDefOperand(AntiDepReg); 8222973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach assert(AntiDepOp != NULL && 8232973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach "Can't find index for defined register operand"); 824348777110a960f0e017025dd5141cb29472c3984David Goodwin if ((AntiDepOp == NULL) || AntiDepOp->isImplicit()) { 8255393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << " (implicit)\n"); 826348777110a960f0e017025dd5141cb29472c3984David Goodwin continue; 827348777110a960f0e017025dd5141cb29472c3984David Goodwin } 8282973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 829348777110a960f0e017025dd5141cb29472c3984David Goodwin // If the SUnit has other dependencies on the SUnit that 830348777110a960f0e017025dd5141cb29472c3984David Goodwin // it anti-depends on, don't bother breaking the 831348777110a960f0e017025dd5141cb29472c3984David Goodwin // anti-dependency since those edges would prevent such 832348777110a960f0e017025dd5141cb29472c3984David Goodwin // units from being scheduled past each other 833348777110a960f0e017025dd5141cb29472c3984David Goodwin // regardless. 834557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin // 835557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin // Also, if there are dependencies on other SUnits with the 836557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin // same register as the anti-dependency, don't attempt to 837557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin // break it. 83866db3a0f10e96ae190c8a46a1a8d5242928d068cDan Gohman for (SUnit::const_pred_iterator P = PathSU->Preds.begin(), 839348777110a960f0e017025dd5141cb29472c3984David Goodwin PE = PathSU->Preds.end(); P != PE; ++P) { 840557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin if (P->getSUnit() == NextSU ? 841557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin (P->getKind() != SDep::Anti || P->getReg() != AntiDepReg) : 842557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin (P->getKind() == SDep::Data && P->getReg() == AntiDepReg)) { 843557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin AntiDepReg = 0; 844557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin break; 845557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin } 846557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin } 84766db3a0f10e96ae190c8a46a1a8d5242928d068cDan Gohman for (SUnit::const_pred_iterator P = PathSU->Preds.begin(), 848557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin PE = PathSU->Preds.end(); P != PE; ++P) { 849557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin if ((P->getSUnit() == NextSU) && (P->getKind() != SDep::Anti) && 850557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin (P->getKind() != SDep::Output)) { 8515393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << " (real dependency)\n"); 852348777110a960f0e017025dd5141cb29472c3984David Goodwin AntiDepReg = 0; 853348777110a960f0e017025dd5141cb29472c3984David Goodwin break; 8542973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach } else if ((P->getSUnit() != NextSU) && 8552973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach (P->getKind() == SDep::Data) && 856557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin (P->getReg() == AntiDepReg)) { 8575393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << " (other dependency)\n"); 858557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin AntiDepReg = 0; 859557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin break; 860348777110a960f0e017025dd5141cb29472c3984David Goodwin } 861348777110a960f0e017025dd5141cb29472c3984David Goodwin } 8622973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 863348777110a960f0e017025dd5141cb29472c3984David Goodwin if (AntiDepReg == 0) continue; 864348777110a960f0e017025dd5141cb29472c3984David Goodwin } 8652973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 866348777110a960f0e017025dd5141cb29472c3984David Goodwin assert(AntiDepReg != 0); 867348777110a960f0e017025dd5141cb29472c3984David Goodwin if (AntiDepReg == 0) continue; 8682973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 869348777110a960f0e017025dd5141cb29472c3984David Goodwin // Determine AntiDepReg's register group. 870e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin const unsigned GroupIndex = State->GetGroup(AntiDepReg); 871348777110a960f0e017025dd5141cb29472c3984David Goodwin if (GroupIndex == 0) { 8725393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << " (zero group)\n"); 873348777110a960f0e017025dd5141cb29472c3984David Goodwin continue; 874348777110a960f0e017025dd5141cb29472c3984David Goodwin } 8752973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 8765393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << '\n'); 8772973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 878348777110a960f0e017025dd5141cb29472c3984David Goodwin // Look for a suitable register to use to break the anti-dependence. 879348777110a960f0e017025dd5141cb29472c3984David Goodwin std::map<unsigned, unsigned> RenameMap; 88054097836f31660bd5e84c34ee8c92d237844315fDavid Goodwin if (FindSuitableFreeRegisters(GroupIndex, RenameOrder, RenameMap)) { 8815393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << "\tBreaking anti-dependence edge on " 882348777110a960f0e017025dd5141cb29472c3984David Goodwin << TRI->getName(AntiDepReg) << ":"); 8832973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 884348777110a960f0e017025dd5141cb29472c3984David Goodwin // Handle each group register... 885348777110a960f0e017025dd5141cb29472c3984David Goodwin for (std::map<unsigned, unsigned>::iterator 886348777110a960f0e017025dd5141cb29472c3984David Goodwin S = RenameMap.begin(), E = RenameMap.end(); S != E; ++S) { 887348777110a960f0e017025dd5141cb29472c3984David Goodwin unsigned CurrReg = S->first; 888348777110a960f0e017025dd5141cb29472c3984David Goodwin unsigned NewReg = S->second; 8892973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 8902973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach DEBUG(dbgs() << " " << TRI->getName(CurrReg) << "->" << 8912973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach TRI->getName(NewReg) << "(" << 892348777110a960f0e017025dd5141cb29472c3984David Goodwin RegRefs.count(CurrReg) << " refs)"); 8932973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 894348777110a960f0e017025dd5141cb29472c3984David Goodwin // Update the references to the old register CurrReg to 895348777110a960f0e017025dd5141cb29472c3984David Goodwin // refer to the new register NewReg. 8962973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach std::pair<std::multimap<unsigned, 8972973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach AggressiveAntiDepState::RegisterReference>::iterator, 898e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin std::multimap<unsigned, 8992973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach AggressiveAntiDepState::RegisterReference>::iterator> 900348777110a960f0e017025dd5141cb29472c3984David Goodwin Range = RegRefs.equal_range(CurrReg); 9012973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach for (std::multimap<unsigned, 9022973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach AggressiveAntiDepState::RegisterReference>::iterator 903348777110a960f0e017025dd5141cb29472c3984David Goodwin Q = Range.first, QE = Range.second; Q != QE; ++Q) { 904348777110a960f0e017025dd5141cb29472c3984David Goodwin Q->second.Operand->setReg(NewReg); 905533934e06e99a86e8c93f8ec9b9d3b2c527b747eJim Grosbach // If the SU for the instruction being updated has debug 906533934e06e99a86e8c93f8ec9b9d3b2c527b747eJim Grosbach // information related to the anti-dependency register, make 907533934e06e99a86e8c93f8ec9b9d3b2c527b747eJim Grosbach // sure to update that as well. 908533934e06e99a86e8c93f8ec9b9d3b2c527b747eJim Grosbach const SUnit *SU = MISUnitMap[Q->second.Operand->getParent()]; 909086723d244952aee690a8aa39485a0fa0d3a7700Jim Grosbach if (!SU) continue; 910e29e8e100ea38be1771e5f010a5511cbb990d515Devang Patel for (DbgValueVector::iterator DVI = DbgValues.begin(), 911e29e8e100ea38be1771e5f010a5511cbb990d515Devang Patel DVE = DbgValues.end(); DVI != DVE; ++DVI) 912e29e8e100ea38be1771e5f010a5511cbb990d515Devang Patel if (DVI->second == Q->second.Operand->getParent()) 913e29e8e100ea38be1771e5f010a5511cbb990d515Devang Patel UpdateDbgValue(DVI->first, AntiDepReg, NewReg); 914348777110a960f0e017025dd5141cb29472c3984David Goodwin } 9152973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 916348777110a960f0e017025dd5141cb29472c3984David Goodwin // We just went back in time and modified history; the 917348777110a960f0e017025dd5141cb29472c3984David Goodwin // liveness information for CurrReg is now inconsistent. Set 918348777110a960f0e017025dd5141cb29472c3984David Goodwin // the state as if it were dead. 919e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin State->UnionGroups(NewReg, 0); 920348777110a960f0e017025dd5141cb29472c3984David Goodwin RegRefs.erase(NewReg); 921348777110a960f0e017025dd5141cb29472c3984David Goodwin DefIndices[NewReg] = DefIndices[CurrReg]; 922348777110a960f0e017025dd5141cb29472c3984David Goodwin KillIndices[NewReg] = KillIndices[CurrReg]; 9232973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 924e10deca33e74a7c70ab585f78eee3fb52937f668David Goodwin State->UnionGroups(CurrReg, 0); 925348777110a960f0e017025dd5141cb29472c3984David Goodwin RegRefs.erase(CurrReg); 926348777110a960f0e017025dd5141cb29472c3984David Goodwin DefIndices[CurrReg] = KillIndices[CurrReg]; 927348777110a960f0e017025dd5141cb29472c3984David Goodwin KillIndices[CurrReg] = ~0u; 928348777110a960f0e017025dd5141cb29472c3984David Goodwin assert(((KillIndices[CurrReg] == ~0u) != 929348777110a960f0e017025dd5141cb29472c3984David Goodwin (DefIndices[CurrReg] == ~0u)) && 930348777110a960f0e017025dd5141cb29472c3984David Goodwin "Kill and Def maps aren't consistent for AntiDepReg!"); 931348777110a960f0e017025dd5141cb29472c3984David Goodwin } 9322973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 933348777110a960f0e017025dd5141cb29472c3984David Goodwin ++Broken; 9345393b2523419af71971be2286f34d3c8e2501898David Greene DEBUG(dbgs() << '\n'); 935348777110a960f0e017025dd5141cb29472c3984David Goodwin } 936348777110a960f0e017025dd5141cb29472c3984David Goodwin } 937348777110a960f0e017025dd5141cb29472c3984David Goodwin } 938348777110a960f0e017025dd5141cb29472c3984David Goodwin 939348777110a960f0e017025dd5141cb29472c3984David Goodwin ScanInstruction(MI, Count); 940348777110a960f0e017025dd5141cb29472c3984David Goodwin } 9412973b57093b017f2e3b5f5edd0be9d4ea180f0e9Jim Grosbach 942348777110a960f0e017025dd5141cb29472c3984David Goodwin return Broken; 943348777110a960f0e017025dd5141cb29472c3984David Goodwin} 944