AMDGPU: Use DFS to avoid second loop over function

[• dberlin]

Do you actually use Visited outside of the iterator (It's not visible
in this patch if you do)?
If not, you should just use depth_first, not depth_first_ext.

[arsenm]

In D12046#225002, @dberlin wrote:

Do you actually use Visited outside of the iterator (It's not visible
in this patch if you do)?
If not, you should just use depth_first, not depth_first_ext.

No. I thought might have a use for it, but this doesn't use it yet. The comment on it also says "This iterator stores the 'visited' set in an external set, which allows it to be more efficient, and allows external clients to use the set for other purposes." so I figured if it's faster to just leave it

[• tstellarAMD]

LGTM.

[• dberlin]

The comment means space efficient, in terms of set reuse of existing sets.
Leaving it is likely to just confuse future readers
:)

[arsenm]

r245772 without the Visited

lib/Target/AMDGPU/SIFixSGPRLiveRanges.cpp

 /// %use
 ///
 /// Adding this use will make the def live throughout the IF branch, which is
 /// what we want.
 
 #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"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachinePostDominators.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
const SIRegisterInfo *TRI = static_cast<const SIRegisterInfo *>(
       MF.getSubtarget().getRegisterInfo());
 
   LIS = &getAnalysis<LiveIntervals>();
   LV = &getAnalysis<LiveVariables>();
 
   MachinePostDominatorTree *PDT = &getAnalysis<MachinePostDominatorTree>();
   std::vector<std::pair<unsigned, LiveRange *>> SGPRLiveRanges;
 
+  MachineBasicBlock *Entry = MF.begin();
+  SmallPtrSet<MachineBasicBlock *, 16> Visited;
 
-  // 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_ext(Entry, Visited)) {
+    for (const MachineInstr &MI : *MBB) {
       for (const MachineOperand &MO : MI.defs()) {
         if (MO.isImplicit())
           continue;
         unsigned Def = MO.getReg();
         if (TargetRegisterInfo::isVirtualRegister(Def)) {
           if (TRI->isSGPRClass(MRI.getRegClass(Def))) {
             // 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)
       continue;
 
     MachineBasicBlock::iterator NCDTerm = NCD->getFirstTerminator();
 
     if (NCDTerm != NCD->end() && NCDTerm->getOpcode() == AMDGPU::SI_ELSE) {