From ac03979a67abcff8cad34ce639855b7f4d3a5d0a Mon Sep 17 00:00:00 2001 From: Matt Arsenault Date: Sat, 22 Aug 2015 00:43:38 +0000 Subject: [PATCH] AMDGPU: Use DFS to avoid second loop over function git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@245772 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Target/AMDGPU/SIFixSGPRLiveRanges.cpp | 28 +++++++++++------------ 1 file changed, 13 insertions(+), 15 deletions(-) diff --git a/lib/Target/AMDGPU/SIFixSGPRLiveRanges.cpp b/lib/Target/AMDGPU/SIFixSGPRLiveRanges.cpp index 898646d429f..5f25c69fde0 100644 --- a/lib/Target/AMDGPU/SIFixSGPRLiveRanges.cpp +++ b/lib/Target/AMDGPU/SIFixSGPRLiveRanges.cpp @@ -47,6 +47,7 @@ #include "AMDGPU.h" #include "SIInstrInfo.h" #include "SIRegisterInfo.h" +#include "llvm/ADT/DepthFirstIterator.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/LiveVariables.h" #include "llvm/CodeGen/MachineFunctionPass.h" @@ -119,10 +120,13 @@ bool SIFixSGPRLiveRanges::runOnMachineFunction(MachineFunction &MF) { LiveIntervals *LIS = &getAnalysis(); LiveVariables *LV = getAnalysisIfAvailable(); + MachineBasicBlock *Entry = MF.begin(); - // First pass, collect all live intervals for SGPRs - for (const MachineBasicBlock &MBB : MF) { - for (const MachineInstr &MI : MBB) { + // Use a depth first order so that in SSA, we encounter all defs before + // uses. Once the defs of the block have been found, attempt to insert + // SGPR_USE instructions in successor blocks if required. + for (MachineBasicBlock *MBB : depth_first(Entry)) { + for (const MachineInstr &MI : *MBB) { for (const MachineOperand &MO : MI.defs()) { if (MO.isImplicit()) continue; @@ -132,29 +136,23 @@ bool SIFixSGPRLiveRanges::runOnMachineFunction(MachineFunction &MF) { // Only consider defs that are live outs. We don't care about def / // use within the same block. LiveRange &LR = LIS->getInterval(Def); - if (LIS->isLiveOutOfMBB(LR, &MBB)) + if (LIS->isLiveOutOfMBB(LR, MBB)) SGPRLiveRanges.push_back(std::make_pair(Def, &LR)); } } else if (TRI->isSGPRClass(TRI->getPhysRegClass(Def))) { - SGPRLiveRanges.push_back( - std::make_pair(Def, &LIS->getRegUnit(Def))); + SGPRLiveRanges.push_back(std::make_pair(Def, &LIS->getRegUnit(Def))); } } } - } - // Second pass fix the intervals - for (MachineFunction::iterator BI = MF.begin(), BE = MF.end(); - BI != BE; ++BI) { - MachineBasicBlock &MBB = *BI; - if (MBB.succ_size() < 2) + if (MBB->succ_size() < 2) continue; // We have structured control flow, so the number of successors should be // two. - assert(MBB.succ_size() == 2); - MachineBasicBlock *SuccA = *MBB.succ_begin(); - MachineBasicBlock *SuccB = *(++MBB.succ_begin()); + assert(MBB->succ_size() == 2); + MachineBasicBlock *SuccA = *MBB->succ_begin(); + MachineBasicBlock *SuccB = *(++MBB->succ_begin()); MachineBasicBlock *NCD = PDT->findNearestCommonDominator(SuccA, SuccB); if (!NCD) -- 2.34.1