AMDGPU: Do operand folding in program order

[arsenm]

Summary

Before it was possible to partially fold use instructions
before the defs. After the xor is folded into a copy, the same
mov can end up in the fold list twice, so on the second attempt
it will fail expecting to see a register to fold.

[rampitec]

Given implied structured CFG LGTM.

[arsenm]

Unstructured is fine, defs just should be visited before uses

[arsenm]

r305821

lib/Target/AMDGPU/SIFoldOperands.cpp

 //===-- SIFoldOperands.cpp - Fold operands --- ----------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 /// \file
 //===----------------------------------------------------------------------===//
 //
 
 #include "AMDGPU.h"
 #include "AMDGPUSubtarget.h"
 #include "SIInstrInfo.h"
 #include "SIMachineFunctionInfo.h"
+#include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetMachine.h"
 
bool SIFoldOperands::runOnMachineFunction(MachineFunction &MF) {
 
   // omod is ignored by hardware if IEEE bit is enabled. omod also does not
   // correctly handle signed zeros.
   //
   // TODO: Check nsz on instructions when fast math flags are preserved to MI
   // level.
   bool IsIEEEMode = ST->enableIEEEBit(MF) || !MFI->hasNoSignedZerosFPMath();
 
-  for (MachineFunction::iterator BI = MF.begin(), BE = MF.end();
-       BI != BE; ++BI) {
-
-    MachineBasicBlock &MBB = *BI;
+  for (MachineBasicBlock *MBB : depth_first(&MF)) {
     MachineBasicBlock::iterator I, Next;
-    for (I = MBB.begin(); I != MBB.end(); I = Next) {
+    for (I = MBB->begin(); I != MBB->end(); I = Next) {
       Next = std::next(I);
       MachineInstr &MI = *I;
 
       tryFoldInst(TII, &MI);
 
       if (!TII->isFoldableCopy(MI)) {
         if (IsIEEEMode || !tryFoldOMod(MI))
           tryFoldClamp(MI);

test/CodeGen/AMDGPU/fold-operands-order.mir

+# RUN: llc -mtriple=amdgcn--amdhsa -mcpu=hawaii -verify-machineinstrs -run-pass si-fold-operands -o - %s | FileCheck -check-prefix=GCN %s
+
+--- |
+  define amdgpu_kernel void @mov_in_use_list_2x() {
+    unreachable
+  }
+
+...
+---
+
+# Blocks should be processed in program order to make sure folds
+# aren't made in users before the def is seen.
+
+# GCN-LABEL: name: mov_in_use_list_2x{{$}}
+# GCN: %2 = V_MOV_B32_e32 0, implicit %exec
+# GCN-NEXT: %3 = COPY undef %0
+
+# GCN: %1 = V_MOV_B32_e32 0, implicit %exec
+
+
+name: mov_in_use_list_2x
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: vgpr_32, preferred-register: '' }
+  - { id: 1, class: vgpr_32, preferred-register: '' }
+  - { id: 2, class: vgpr_32, preferred-register: '' }
+  - { id: 3, class: vgpr_32, preferred-register: '' }
+liveins:
+body:             |
+  bb.0:
+    successors: %bb.2
+
+    S_BRANCH %bb.2
+
+  bb.1:
+    successors: %bb.2
+
+    %2 = COPY %1
+    %3 = V_XOR_B32_e64 killed %2, undef %0, implicit %exec
+
+  bb.2:
+    successors: %bb.1
+
+    %1 = V_MOV_B32_e32 0, implicit %exec
+    S_BRANCH %bb.1
+
+...