[AMDGPU] Add Lower Bound to PipelineSolver

[jrbyrnes]

Summary

This patch provides an algorithm to compute the lower bound on the cost of the SUs that have not yet been assigned to a SG. It finds the minimum cost SG for a given SU based on the current partial pipeline, but does not assign the SU to the SG. Thus, it will not create added dependencies / affect cost for the other remaining unassigned SUs. Then, at each branch in the search tree, we are able to use the lower bound on the cost of the remaining SUs for additional pruning.

The net benefit of this feature is difficult to conclude through analytical means, and should be done experimentally. While the LB does improve pruning, it increases the time complexity of processing a branch in the search tree. The cost computation is expensive, and the LB computes the cost for all unassigned SUs for every branch in the search tree.

Change-Id: I803200917c6d02f0ac8b916b61741b2b7d72d1e0

[jrbyrnes]

Fix incomplete comment

[jrbyrnes]

Avoid a very small number of calls to calculateLowerBound

[jsilvanus]

Thanks for implementing this!

llvm/lib/Target/AMDGPU/AMDGPUIGroupLP.cpp

576

Maybe move the vector out of the loops to reduce allocations, and clear() here instead?

590

In addEdges, we could abort once the added cost exceeds MinCostForSU (if MinCostForSU != -1). Not sure if that would be worth the effort.

[jrbyrnes]

Address Review Comments

[jrbyrnes]

In D133731#3785721, @jsilvanus wrote:

Thanks for implementing this!

Hey Jannik -- of course, thanks for the comments / good suggestions!

[jsilvanus]

llvm/lib/Target/AMDGPU/AMDGPUIGroupLP.cpp

576

Why not move out of the other two loops as well?
Maybe with a comment that this is for performance only, and only needed in the most inner loop.

[jrbyrnes]

A few optimizations to improve general performance, and perf of LB.

[arsenm]

llvm/lib/Target/AMDGPU/AMDGPUIGroupLP.cpp

68

Typo calcalutes

566

I'd assume this can be a SmallVector

[jrbyrnes]

Address review comments

[arsenm]

I know little about the scheduler but this seems reasonable

llvm/lib/Target/AMDGPU/AMDGPUIGroupLP.cpp

794

Single quotes

[jrbyrnes]

Rebase into future. Since this patch was already accepted, I will land it upstream if there are no objections within a couple days.

[jrbyrnes]

Landed via 3c42a58c4f20ae3b6

[Jake-Egan]

Hi this new test is failing on AIX, could you take a look please?
https://lab.llvm.org/buildbot/#/builders/214/builds/6792/steps/6/logs/FAIL__LLVM__igrouplp-pipelinesolver-lowerbound_ll

[jrbyrnes]

Reopened due to commit reversion

[jrbyrnes]

Abandoning since rules provides framework for closely fitting pipelines to user specifications.

If there are objections to abandonment, I will reopen via PR.

llvm/lib/Target/AMDGPU/AMDGPUIGroupLP.cpp

static cl::opt<bool> UseCostHeur(
     "amdgpu-igrouplp-exact-solver-cost-heur", cl::init(true), cl::Hidden,
     cl::desc("Whether to use the cost heuristic to make choices as we "
              "traverse the search space using the exact solver. Defaulted "
              "to on, and if turned off, we will use the node order -- "
              "attempting to put the later nodes in the later sched groups. "
              "Experimentally, results are mixed, so this should be set on a "
              "case-by-case basis."));
 
+static cl::opt<bool> EnableLowerBound(
+    "amdgpu-igrouplp-exact-solver-lower-bound", cl::Hidden,
+    cl::desc("Whether to use a lower bound when calculating the cost "
+             "for a partial fit using the exact solver. The lower bound "
+             "calcalutes the cost of assigning the remaining instructions "
+             "under idealized conditions. The LB reduces the overall search "
+             "space but adds time complexity per branch explored."),
+    cl::init(false));
+
 // Components of the mask that determines which instruction types may be may be
 // classified into a SchedGroup.
 enum class SchedGroupMask {
   NONE = 0u,
   ALU = 1u << 0,
   VALU = 1u << 1,
   SALU = 1u << 2,
   MFMA = 1u << 3,
private:
 
   // Count of the number of created SchedGroups, used to initialize SGID.
   static unsigned NumSchedGroups;
 
   ScheduleDAGInstrs *DAG;
 
   const SIInstrInfo *TII;
 
-  // Try to add and edge from SU A to SU B.
+  // Try to add and edge from SU A to SU B. This returns false if there is a
+  // dependency which makes adding the A->B edge impossible, otherwise it
+  // returns true. The result is that it will return true even if no edge was
+  // added. For example, if there is already an edge between A->B, this will
+  // return true, even though DAG->addEdge does not add edge.
   bool tryAddEdge(SUnit *A, SUnit *B);
 
   // Use SGMask to determine whether we can classify MI as a member of this
   // SchedGroup object.
   bool canAddMI(const MachineInstr &MI) const;
 
 public:
   // Collection of SUnits that are classified as members of this group.
class PipelineSolver {
 
   // The cost penalty of not assigning a SU to a SchedGroup
   int MissPenalty = 0;
 
   // Costs in terms of the number of edges we are unable to add
   int BestCost = -1;
   int CurrCost = 0;
 
+  // A lower bound on the optimal cost for a complete pipeline
+  int StaticLowerBound = 0;
+
   // Index pointing to the conflicting instruction that is currently being
   // fitted
   int CurrConflInstNo = 0;
   // Index to the pipeline that is currently being fitted
   int CurrSyncGroupIdx = 0;
   // The first non trivial pipeline
   int BeginSyncGroupIdx = 0;
 
class PipelineSolver {
   // The polynomial time algorithm which attempts to find a good fit
   bool solveGreedy();
   // Whether or not the current solution is optimal
   bool checkOptimal();
   // Populate the ready list, prioiritizing fewest missed edges first
   void populateReadyList(SUToCandSGsPair &CurrSU,
                          SmallVectorImpl<std::pair<int, int>> &ReadyList,
                          SmallVectorImpl<SchedGroup> &SyncPipeline);
+  // Calculate best cost assignment of an unassigned SU without assigning it.
+  // The sum of these costs across SUs represents a Lower Bound on the true best
+  // cost for the set of unassigned SUs.
+  int calculateLowerBound();
   // Add edges corresponding to the SchedGroups as assigned by solver
   void makePipeline();
   // Add the edges from the SU to the other SchedGroups in pipeline, and
   // return the number of edges missed.
   int addEdges(SmallVectorImpl<SchedGroup> &SyncPipeline, SUnit *SU, int SGID,
-               std::vector<std::pair<SUnit *, SUnit *>> &AddedEdges);
+               std::vector<std::pair<SUnit *, SUnit *>> &AddedEdges,
+               int BestCost = -1);
   // Remove the edges passed via AddedEdges
   void removeEdges(const std::vector<std::pair<SUnit *, SUnit *>> &AddedEdges);
   // Convert the passed in maps to arrays for bidirectional iterators
   void convertSyncMapsToArrays();
 
   void reset();
 
 public:
for (; I != E; ++I) {
         GroupA.link(GroupB);
       }
     }
   }
 }
 
 int PipelineSolver::addEdges(
     SmallVectorImpl<SchedGroup> &SyncPipeline, SUnit *SU, int SGID,
-    std::vector<std::pair<SUnit *, SUnit *>> &AddedEdges) {
+    std::vector<std::pair<SUnit *, SUnit *>> &AddedEdges, int BestCost) {
   int AddedCost = 0;
   bool MakePred = false;
 
   // The groups in the pipeline are in reverse order. Thus,
   // by traversing them from last to first, we are traversing
   // them in the order as they were introduced in the code. After we
   // pass the group the SU is being assigned to, it should be
   // linked as a predecessor of the subsequent SchedGroups
   auto GroupNo = (int)SyncPipeline.size() - 1;
   for (; GroupNo >= 0; GroupNo--) {
+    if (BestCost != -1 && AddedCost >= BestCost)
+      return AddedCost;
     if (SyncPipeline[GroupNo].getSGID() == SGID) {
       MakePred = true;
       continue;
     }
     auto Group = &SyncPipeline[GroupNo];
     AddedCost += Group->link(*SU, MakePred, AddedEdges);
     assert(AddedCost >= 0);
   }
 
   return AddedCost;
 }
 
 void PipelineSolver::removeEdges(
     const std::vector<std::pair<SUnit *, SUnit *>> &EdgesToRemove) {
   // Only remove the edges that we have added when testing
   // the fit.
   for (auto &PredSuccPair : EdgesToRemove) {
     SUnit *Pred = PredSuccPair.first;
     SUnit *Succ = PredSuccPair.second;
 
     auto Match =
-        std::find_if(Succ->Preds.begin(), Succ->Preds.end(),
-                     [&Pred](SDep &P) { return P.getSUnit() == Pred; });
+        std::find_if(Succ->Preds.begin(), Succ->Preds.end(), [&Pred](SDep &P) {
+          return P.getSUnit() == Pred && P.isArtificial();
+        });
     if (Match != Succ->Preds.end()) {
       assert(Match->isArtificial());
       Succ->removePred(*Match);
     }
   }
 }
 
 void PipelineSolver::advancePosition() {
if (static_cast<size_t>(CurrSyncGroupIdx) == PipelineInstrs.size()) {
     }
     assert(BestCost >= 0);
   }
 
   bool DoneExploring = false;
   if (MaxBranchesExplored > 0 && BranchesExplored >= MaxBranchesExplored)
     DoneExploring = true;
 
-  return (DoneExploring || BestCost == 0);
+  return (DoneExploring || BestCost == StaticLowerBound);
 }
 
 void PipelineSolver::populateReadyList(
     SUToCandSGsPair &CurrSU, SmallVectorImpl<std::pair<int, int>> &ReadyList,
     SmallVectorImpl<SchedGroup> &SyncPipeline) {
   assert(CurrSU.second.size() >= 1);
   auto I = CurrSU.second.rbegin();
   auto E = CurrSU.second.rend();
-  for (; I != E; ++I) {
-    std::vector<std::pair<SUnit *, SUnit *>> AddedEdges;
+  for (; I != E; ++I) {
+
     int CandSGID = *I;
     SchedGroup *Match;
     for (auto &SG : SyncPipeline) {
       if (SG.getSGID() == CandSGID)
         Match = &SG;
     }
 
     if (UseCostHeur) {
       if (Match->isFull()) {
         ReadyList.push_back(std::make_pair(*I, MissPenalty));
         continue;
       }
+      AddedEdges.clear();
 
       int TempCost = addEdges(SyncPipeline, CurrSU.first, CandSGID, AddedEdges);
       ReadyList.push_back(std::make_pair(*I, TempCost));
       removeEdges(AddedEdges);
     } else
       ReadyList.push_back(std::make_pair(*I, -1));
   }
 
   if (UseCostHeur) {
     std::sort(ReadyList.begin(), ReadyList.end(),
               [](std::pair<int, int> A, std::pair<int, int> B) {
                 return A.second < B.second;
               });
   }
 
   assert(ReadyList.size() == CurrSU.second.size());
 }
 
+int PipelineSolver::calculateLowerBound() {
+  if (CurrSyncGroupIdx >= (int)CurrPipeline.size())
+    return 0;
+  int TempConflInstNo = CurrConflInstNo;
+  int TmpSyncGroupIdx = CurrSyncGroupIdx;
+  int MinimumCost = 0;
+  std::vector<std::pair<SUnit *, SUnit *>> AddedEdges;
+
+  for (; TmpSyncGroupIdx < (int)CurrPipeline.size(); TmpSyncGroupIdx++) {
+    auto SyncPipeline = CurrPipeline[TmpSyncGroupIdx];
+    for (; TempConflInstNo < (int)PipelineInstrs[TmpSyncGroupIdx].size();
+         TempConflInstNo++) {
+      auto CurrSU = PipelineInstrs[TmpSyncGroupIdx][TempConflInstNo];
+      auto I = CurrSU.second.rbegin();
+      auto E = CurrSU.second.rend();
+      int MinCostForSU = -1;
+      for (; I != E; I++) {
+        int CandSGID = *I;
+        SchedGroup *Match;
+        for (auto &SG : SyncPipeline) {
+          if (SG.getSGID() == CandSGID)
+            Match = &SG;
+        }
+
+        if (Match->isFull()) {
+          if (MinCostForSU == -1 || MissPenalty < MinCostForSU)
+            MinCostForSU = MissPenalty;
+          continue;
+        }
+        AddedEdges.clear();
+        int TempCost = addEdges(SyncPipeline, CurrSU.first, CandSGID,
+                                AddedEdges, MinCostForSU);
+        if (MinCostForSU == -1 || TempCost < MinCostForSU)
+          MinCostForSU = TempCost;
+
+        removeEdges(AddedEdges);
+        if (MinCostForSU == 0)
+          break;
+      }
+      MinimumCost += MinCostForSU;
+    }
+    TempConflInstNo = 0;
+  }
+  return MinimumCost;
+}
+
 bool PipelineSolver::solveExact() {
   if (checkOptimal())
     return true;
 
   if (static_cast<size_t>(CurrSyncGroupIdx) == PipelineInstrs.size())
     return false;
 
   assert(static_cast<size_t>(CurrSyncGroupIdx) < PipelineInstrs.size());
   assert(static_cast<size_t>(CurrConflInstNo) <
          PipelineInstrs[CurrSyncGroupIdx].size());
   SUToCandSGsPair CurrSU = PipelineInstrs[CurrSyncGroupIdx][CurrConflInstNo];
   LLVM_DEBUG(dbgs() << "Fitting SU(" << CurrSU.first->NodeNum
                     << ") in Pipeline # " << CurrSyncGroupIdx << "\n");
 
   // SchedGroup -> Cost pairs
   SmallVector<std::pair<int, int>, 4> ReadyList;
   // Prioritize the candidate sched groups in terms of lowest cost first
   populateReadyList(CurrSU, ReadyList, CurrPipeline[CurrSyncGroupIdx]);
+  std::vector<std::pair<SUnit *, SUnit *>> AddedEdges;
 
   auto I = ReadyList.begin();
   auto E = ReadyList.end();
   for (; I != E; ++I) {
     // If we are trying SGs in least cost order, and the current SG is cost
     // infeasible, then all subsequent SGs will also be cost infeasible, so we
     // can prune.
     if (BestCost != -1 && (CurrCost + I->second > BestCost))
       return false;
 
     int CandSGID = I->first;
     int AddedCost = 0;
-    std::vector<std::pair<SUnit *, SUnit *>> AddedEdges;
     auto &SyncPipeline = CurrPipeline[CurrSyncGroupIdx];
     SchedGroup *Match;
     for (auto &SG : SyncPipeline) {
       if (SG.getSGID() == CandSGID)
         Match = &SG;
     }
 
     if (Match->isFull())
       continue;
 
     LLVM_DEBUG(dbgs() << "Assigning to SchedGroup with Mask "
                       << (int)Match->getMask() << "and ID " << CandSGID
                       << "\n");
     Match->add(*CurrSU.first);
+    AddedEdges.clear();
     AddedCost = addEdges(SyncPipeline, CurrSU.first, CandSGID, AddedEdges);
     LLVM_DEBUG(dbgs() << "Cost of Assignment: " << AddedCost << "\n");
     CurrCost += AddedCost;
     advancePosition();
     ++BranchesExplored;
     bool FinishedExploring = false;
     // If the Cost after adding edges is greater than a known solution,
     // backtrack
-    if (CurrCost < BestCost || BestCost == -1) {
+    int LBCost =
+        (EnableLowerBound && BestCost != -1) ? calculateLowerBound() : 0;
+    if (BestCost == -1 || CurrCost + LBCost < BestCost) {
       if (solveExact()) {
-        FinishedExploring = BestCost != 0;
+        FinishedExploring = BestCost != StaticLowerBound;
         if (!FinishedExploring)
           return true;
       }
     }
 
     retreatPosition();
     CurrCost -= AddedCost;
     removeEdges(AddedEdges);
bool PipelineSolver::solveExact() {
   CurrCost += MissPenalty;
   advancePosition();
 
   LLVM_DEBUG(dbgs() << "NOT Assigned (" << CurrSU.first->NodeNum << ")\n");
 
   bool FinishedExploring = false;
   if (CurrCost < BestCost || BestCost == -1) {
     if (solveExact()) {
-      bool FinishedExploring = BestCost != 0;
+      bool FinishedExploring = BestCost != StaticLowerBound;
       if (!FinishedExploring)
         return true;
     }
   }
 
   retreatPosition();
   CurrCost -= MissPenalty;
   return FinishedExploring;
for (; I != E; ++I) {
 
       LLVM_DEBUG(dbgs() << "Trying SGID # " << CandSGID << " with Mask "
                         << (int)Match->getMask() << "\n");
 
       if (Match->isFull()) {
         LLVM_DEBUG(dbgs() << "SGID # " << CandSGID << " is full\n");
         continue;
       }
-      TempCost = addEdges(SyncPipeline, CurrSU.first, CandSGID, AddedEdges);
+      TempCost = addEdges(SyncPipeline, CurrSU.first, CandSGID, AddedEdges,
+                          BestNodeCost);
       LLVM_DEBUG(dbgs() << "Cost of Group " << TempCost << "\n");
       if (TempCost < BestNodeCost || BestNodeCost == -1) {
         BestGroup = Match;
         BestNodeCost = TempCost;
         BestGroupID = CandSGID;
       }
       removeEdges(AddedEdges);
       if (BestNodeCost == 0)
void PipelineSolver::solve() {
   MissPenalty = (ProblemSize / 2) + 1;
 
   LLVM_DEBUG(DAG->dump());
   if (EnableExactSolver || BelowCutoff) {
     LLVM_DEBUG(dbgs() << "Starting Greedy pipeline solver\n");
     solveGreedy();
     reset();
     LLVM_DEBUG(dbgs() << "Greedy produced best cost of " << BestCost << "\n");
-    if (BestCost > 0) {
+    StaticLowerBound = calculateLowerBound();
+    LLVM_DEBUG(dbgs() << "Lower Bound on Pipeline Cost is " << StaticLowerBound
+                      << "\n");
+    if (BestCost > StaticLowerBound) {
       LLVM_DEBUG(dbgs() << "Starting EXACT pipeline solver\n");
       solveExact();
       LLVM_DEBUG(dbgs() << "Exact produced best cost of " << BestCost << "\n");
     }
   } else { // Use the Greedy Algorithm by default
     LLVM_DEBUG(dbgs() << "Starting GREEDY pipeline solver\n");
     solveGreedy();
   }
int SchedGroup::link(SUnit &SU, bool MakePred,
   int MissedEdges = 0;
   for (auto A : Collection) {
     SUnit *B = &SU;
     if (A == B || A->getInstr()->getOpcode() == AMDGPU::SCHED_GROUP_BARRIER)
       continue;
     if (MakePred)
       std::swap(A, B);
 
-    if (DAG->IsReachable(B, A))
-      continue;
-    // tryAddEdge returns false if there is a dependency that makes adding
-    // the A->B edge impossible, otherwise it returns true;
     bool Added = tryAddEdge(A, B);
     if (Added)
       AddedEdges.push_back(std::make_pair(A, B));
     else
       ++MissedEdges;
   }
 
   return MissedEdges;

llvm/test/CodeGen/AMDGPU/igrouplp-pipelinesolver-lowerbound.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -march=amdgcn -mcpu=gfx90a -verify-machineinstrs -misched-cluster=0 -amdgpu-igrouplp-exact-solver-max-branches=250000 < %s | FileCheck -check-prefix=EXACT %s
+; RUN: llc -march=amdgcn -mcpu=gfx90a -verify-machineinstrs -misched-cluster=0 -amdgpu-igrouplp-exact-solver=1 -amdgpu-igrouplp-exact-solver-max-branches=200000 -amdgpu-igrouplp-exact-solver-cost-heur=1 < %s | FileCheck -check-prefix=LB %s
+
+define amdgpu_kernel void @test_sched_group_barrier_pipeline_alternating_READ_VALU_WRITE(<32 x i32> addrspace(1)* noalias %in, <32 x i32> addrspace(1)* noalias %out) #0 {
+; EXACT-LABEL: test_sched_group_barrier_pipeline_alternating_READ_VALU_WRITE:
+; EXACT:       ; %bb.0:
+; EXACT-NEXT:    s_load_dwordx4 s[0:3], s[0:1], 0x24
+; EXACT-NEXT:    v_lshlrev_b32_e32 v16, 7, v0
+; EXACT-NEXT:    ; kill: killed $sgpr0_sgpr1
+; EXACT-NEXT:    s_waitcnt lgkmcnt(0)
+; EXACT-NEXT:    global_load_dwordx4 v[12:15], v16, s[0:1] offset:32
+; EXACT-NEXT:    global_load_dwordx4 v[4:7], v16, s[0:1] offset:48
+; EXACT-NEXT:    ; sched_group_barrier mask(0x00000020) size(1) SyncID(0)
+; EXACT-NEXT:    s_waitcnt vmcnt(1)
+; EXACT-NEXT:    v_mul_lo_u32 v13, v13, v13
+; EXACT-NEXT:    s_waitcnt vmcnt(0)
+; EXACT-NEXT:    v_mul_lo_u32 v7, v7, v7
+; EXACT-NEXT:    global_load_dwordx4 v[0:3], v16, s[0:1]
+; EXACT-NEXT:    v_mul_lo_u32 v6, v6, v6
+; EXACT-NEXT:    v_mul_lo_u32 v12, v12, v12
+; EXACT-NEXT:    v_mul_lo_u32 v15, v15, v15
+; EXACT-NEXT:    v_mul_lo_u32 v14, v14, v14
+; EXACT-NEXT:    ; sched_group_barrier mask(0x00000002) size(2) SyncID(0)
+; EXACT-NEXT:    s_waitcnt vmcnt(0)
+; EXACT-NEXT:    v_mul_lo_u32 v3, v3, v3
+; EXACT-NEXT:    v_mul_lo_u32 v2, v2, v2
+; EXACT-NEXT:    v_mul_lo_u32 v1, v1, v1
+; EXACT-NEXT:    v_mul_lo_u32 v0, v0, v0
+; EXACT-NEXT:    global_store_dwordx4 v16, v[0:3], s[2:3]
+; EXACT-NEXT:    global_load_dwordx4 v[0:3], v16, s[0:1] offset:112
+; EXACT-NEXT:    s_waitcnt vmcnt(0)
+; EXACT-NEXT:    v_mul_lo_u32 v3, v3, v3
+; EXACT-NEXT:    v_mul_lo_u32 v2, v2, v2
+; EXACT-NEXT:    v_mul_lo_u32 v1, v1, v1
+; EXACT-NEXT:    v_mul_lo_u32 v0, v0, v0
+; EXACT-NEXT:    global_store_dwordx4 v16, v[0:3], s[2:3] offset:112
+; EXACT-NEXT:    global_load_dwordx4 v[0:3], v16, s[0:1] offset:96
+; EXACT-NEXT:    s_waitcnt vmcnt(0)
+; EXACT-NEXT:    v_mul_lo_u32 v3, v3, v3
+; EXACT-NEXT:    v_mul_lo_u32 v2, v2, v2
+; EXACT-NEXT:    v_mul_lo_u32 v1, v1, v1
+; EXACT-NEXT:    v_mul_lo_u32 v0, v0, v0
+; EXACT-NEXT:    global_store_dwordx4 v16, v[0:3], s[2:3] offset:96
+; EXACT-NEXT:    v_mul_lo_u32 v5, v5, v5
+; EXACT-NEXT:    v_mul_lo_u32 v4, v4, v4
+; EXACT-NEXT:    global_store_dwordx4 v16, v[4:7], s[2:3] offset:48
+; EXACT-NEXT:    global_load_dwordx4 v[4:7], v16, s[0:1] offset:64
+; EXACT-NEXT:    ; sched_group_barrier mask(0x00000040) size(1) SyncID(0)
+; EXACT-NEXT:    ; sched_group_barrier mask(0x00000020) size(1) SyncID(0)
+; EXACT-NEXT:    ; sched_group_barrier mask(0x00000002) size(2) SyncID(0)
+; EXACT-NEXT:    s_waitcnt vmcnt(0)
+; EXACT-NEXT:    v_mul_lo_u32 v7, v7, v7
+; EXACT-NEXT:    v_mul_lo_u32 v6, v6, v6
+; EXACT-NEXT:    v_mul_lo_u32 v5, v5, v5
+; EXACT-NEXT:    v_mul_lo_u32 v4, v4, v4
+; EXACT-NEXT:    global_store_dwordx4 v16, v[4:7], s[2:3] offset:64
+; EXACT-NEXT:    global_store_dwordx4 v16, v[12:15], s[2:3] offset:32
+; EXACT-NEXT:    global_load_dwordx4 v[8:11], v16, s[0:1] offset:16
+; EXACT-NEXT:    ; sched_group_barrier mask(0x00000040) size(1) SyncID(0)
+; EXACT-NEXT:    ; sched_group_barrier mask(0x00000020) size(1) SyncID(0)
+; EXACT-NEXT:    ; sched_group_barrier mask(0x00000002) size(2) SyncID(0)
+; EXACT-NEXT:    ; sched_group_barrier mask(0x00000040) size(1) SyncID(0)
+; EXACT-NEXT:    ; sched_group_barrier mask(0x00000020) size(1) SyncID(0)
+; EXACT-NEXT:    ; sched_group_barrier mask(0x00000002) size(2) SyncID(0)
+; EXACT-NEXT:    ; sched_group_barrier mask(0x00000040) size(1) SyncID(0)
+; EXACT-NEXT:    ; sched_group_barrier mask(0x00000020) size(1) SyncID(0)
+; EXACT-NEXT:    ; sched_group_barrier mask(0x00000002) size(2) SyncID(0)
+; EXACT-NEXT:    ; sched_group_barrier mask(0x00000040) size(1) SyncID(0)
+; EXACT-NEXT:    ; sched_group_barrier mask(0x00000020) size(1) SyncID(0)
+; EXACT-NEXT:    ; sched_group_barrier mask(0x00000002) size(2) SyncID(0)
+; EXACT-NEXT:    ; sched_group_barrier mask(0x00000040) size(1) SyncID(0)
+; EXACT-NEXT:    ; sched_group_barrier mask(0x00000020) size(1) SyncID(0)
+; EXACT-NEXT:    s_waitcnt vmcnt(0)
+; EXACT-NEXT:    v_mul_lo_u32 v9, v9, v9
+; EXACT-NEXT:    v_mul_lo_u32 v8, v8, v8
+; EXACT-NEXT:    v_mul_lo_u32 v11, v11, v11
+; EXACT-NEXT:    v_mul_lo_u32 v10, v10, v10
+; EXACT-NEXT:    global_store_dwordx4 v16, v[8:11], s[2:3] offset:16
+; EXACT-NEXT:    global_load_dwordx4 v[8:11], v16, s[0:1] offset:80
+; EXACT-NEXT:    ; sched_group_barrier mask(0x00000002) size(2) SyncID(0)
+; EXACT-NEXT:    s_waitcnt vmcnt(0)
+; EXACT-NEXT:    v_mul_lo_u32 v11, v11, v11
+; EXACT-NEXT:    v_mul_lo_u32 v10, v10, v10
+; EXACT-NEXT:    v_mul_lo_u32 v9, v9, v9
+; EXACT-NEXT:    v_mul_lo_u32 v8, v8, v8
+; EXACT-NEXT:    global_store_dwordx4 v16, v[8:11], s[2:3] offset:80
+; EXACT-NEXT:    ; sched_group_barrier mask(0x00000040) size(1) SyncID(0)
+; EXACT-NEXT:    ; sched_group_barrier mask(0x00000020) size(1) SyncID(0)
+; EXACT-NEXT:    ; sched_group_barrier mask(0x00000002) size(2) SyncID(0)
+; EXACT-NEXT:    ; sched_group_barrier mask(0x00000040) size(1) SyncID(0)
+; EXACT-NEXT:    s_endpgm
+;
+; LB-LABEL: test_sched_group_barrier_pipeline_alternating_READ_VALU_WRITE:
+; LB:       ; %bb.0:
+; LB-NEXT:    s_load_dwordx4 s[0:3], s[0:1], 0x24
+; LB-NEXT:    v_lshlrev_b32_e32 v12, 7, v0
+; LB-NEXT:    s_waitcnt lgkmcnt(0)
+; LB-NEXT:    global_load_dwordx4 v[8:11], v12, s[0:1] offset:64
+; LB-NEXT:    ; sched_group_barrier mask(0x00000020) size(1) SyncID(0)
+; LB-NEXT:    s_waitcnt vmcnt(0)
+; LB-NEXT:    v_mul_lo_u32 v11, v11, v11
+; LB-NEXT:    v_mul_lo_u32 v10, v10, v10
+; LB-NEXT:    v_mul_lo_u32 v9, v9, v9
+; LB-NEXT:    v_mul_lo_u32 v8, v8, v8
+; LB-NEXT:    global_store_dwordx4 v12, v[8:11], s[2:3] offset:64
+; LB-NEXT:    global_load_dwordx4 v[0:3], v12, s[0:1]
+; LB-NEXT:    ; sched_group_barrier mask(0x00000002) size(2) SyncID(0)
+; LB-NEXT:    ; sched_group_barrier mask(0x00000040) size(1) SyncID(0)
+; LB-NEXT:    ; sched_group_barrier mask(0x00000020) size(1) SyncID(0)
+; LB-NEXT:    s_waitcnt vmcnt(0)
+; LB-NEXT:    v_mul_lo_u32 v3, v3, v3
+; LB-NEXT:    v_mul_lo_u32 v2, v2, v2
+; LB-NEXT:    global_load_dwordx4 v[8:11], v12, s[0:1] offset:32
+; LB-NEXT:    ; sched_group_barrier mask(0x00000002) size(2) SyncID(0)
+; LB-NEXT:    s_waitcnt vmcnt(0)
+; LB-NEXT:    v_mul_lo_u32 v9, v9, v9
+; LB-NEXT:    v_mul_lo_u32 v8, v8, v8
+; LB-NEXT:    v_mul_lo_u32 v11, v11, v11
+; LB-NEXT:    v_mul_lo_u32 v10, v10, v10
+; LB-NEXT:    global_store_dwordx4 v12, v[8:11], s[2:3] offset:32
+; LB-NEXT:    global_load_dwordx4 v[4:7], v12, s[0:1] offset:112
+; LB-NEXT:    ; sched_group_barrier mask(0x00000040) size(1) SyncID(0)
+; LB-NEXT:    ; sched_group_barrier mask(0x00000020) size(1) SyncID(0)
+; LB-NEXT:    s_waitcnt vmcnt(0)
+; LB-NEXT:    v_mul_lo_u32 v7, v7, v7
+; LB-NEXT:    v_mul_lo_u32 v6, v6, v6
+; LB-NEXT:    v_mul_lo_u32 v1, v1, v1
+; LB-NEXT:    v_mul_lo_u32 v0, v0, v0
+; LB-NEXT:    global_store_dwordx4 v12, v[0:3], s[2:3]
+; LB-NEXT:    global_load_dwordx4 v[0:3], v12, s[0:1] offset:96
+; LB-NEXT:    ; sched_group_barrier mask(0x00000002) size(2) SyncID(0)
+; LB-NEXT:    s_waitcnt vmcnt(0)
+; LB-NEXT:    v_mul_lo_u32 v3, v3, v3
+; LB-NEXT:    v_mul_lo_u32 v2, v2, v2
+; LB-NEXT:    v_mul_lo_u32 v1, v1, v1
+; LB-NEXT:    v_mul_lo_u32 v0, v0, v0
+; LB-NEXT:    global_store_dwordx4 v12, v[0:3], s[2:3] offset:96
+; LB-NEXT:    global_load_dwordx4 v[0:3], v12, s[0:1] offset:80
+; LB-NEXT:    s_waitcnt vmcnt(0)
+; LB-NEXT:    v_mul_lo_u32 v3, v3, v3
+; LB-NEXT:    v_mul_lo_u32 v2, v2, v2
+; LB-NEXT:    v_mul_lo_u32 v1, v1, v1
+; LB-NEXT:    v_mul_lo_u32 v0, v0, v0
+; LB-NEXT:    global_store_dwordx4 v12, v[0:3], s[2:3] offset:80
+; LB-NEXT:    v_mul_lo_u32 v5, v5, v5
+; LB-NEXT:    v_mul_lo_u32 v4, v4, v4
+; LB-NEXT:    global_store_dwordx4 v12, v[4:7], s[2:3] offset:112
+; LB-NEXT:    global_load_dwordx4 v[4:7], v12, s[0:1] offset:48
+; LB-NEXT:    ; sched_group_barrier mask(0x00000040) size(1) SyncID(0)
+; LB-NEXT:    ; sched_group_barrier mask(0x00000020) size(1) SyncID(0)
+; LB-NEXT:    ; sched_group_barrier mask(0x00000002) size(2) SyncID(0)
+; LB-NEXT:    ; sched_group_barrier mask(0x00000040) size(1) SyncID(0)
+; LB-NEXT:    ; sched_group_barrier mask(0x00000020) size(1) SyncID(0)
+; LB-NEXT:    ; sched_group_barrier mask(0x00000002) size(2) SyncID(0)
+; LB-NEXT:    ; sched_group_barrier mask(0x00000040) size(1) SyncID(0)
+; LB-NEXT:    ; sched_group_barrier mask(0x00000020) size(1) SyncID(0)
+; LB-NEXT:    ; sched_group_barrier mask(0x00000002) size(2) SyncID(0)
+; LB-NEXT:    s_waitcnt vmcnt(0)
+; LB-NEXT:    v_mul_lo_u32 v5, v5, v5
+; LB-NEXT:    global_load_dwordx4 v[0:3], v12, s[0:1] offset:16
+; LB-NEXT:    v_mul_lo_u32 v4, v4, v4
+; LB-NEXT:    s_waitcnt vmcnt(0)
+; LB-NEXT:    v_mul_lo_u32 v1, v1, v1
+; LB-NEXT:    v_mul_lo_u32 v0, v0, v0
+; LB-NEXT:    v_mul_lo_u32 v3, v3, v3
+; LB-NEXT:    v_mul_lo_u32 v2, v2, v2
+; LB-NEXT:    global_store_dwordx4 v12, v[0:3], s[2:3] offset:16
+; LB-NEXT:    v_mul_lo_u32 v7, v7, v7
+; LB-NEXT:    v_mul_lo_u32 v6, v6, v6
+; LB-NEXT:    global_store_dwordx4 v12, v[4:7], s[2:3] offset:48
+; LB-NEXT:    ; sched_group_barrier mask(0x00000040) size(1) SyncID(0)
+; LB-NEXT:    ; sched_group_barrier mask(0x00000020) size(1) SyncID(0)
+; LB-NEXT:    ; sched_group_barrier mask(0x00000002) size(2) SyncID(0)
+; LB-NEXT:    ; sched_group_barrier mask(0x00000040) size(1) SyncID(0)
+; LB-NEXT:    ; sched_group_barrier mask(0x00000020) size(1) SyncID(0)
+; LB-NEXT:    ; sched_group_barrier mask(0x00000002) size(2) SyncID(0)
+; LB-NEXT:    ; sched_group_barrier mask(0x00000040) size(1) SyncID(0)
+; LB-NEXT:    s_endpgm
+  %tid = call i32 @llvm.amdgcn.workitem.id.x() #0
+  %gep1 = getelementptr <32 x i32>, <32 x i32> addrspace(1)* %in, i32 %tid
+  %load = load <32 x i32>, <32 x i32> addrspace(1)* %gep1
+  %mul = mul <32 x i32> %load, %load
+  %gep2 = getelementptr <32 x i32>, <32 x i32> addrspace(1)* %out, i32 %tid
+  store <32 x i32> %mul, <32 x i32> addrspace(1)* %gep2
+  ; 1 VMEM read
+  call void @llvm.amdgcn.sched.group.barrier(i32 32, i32 1, i32 0)
+  ; 2 VALU
+  call void @llvm.amdgcn.sched.group.barrier(i32 2, i32 2, i32 0)
+  ; 1 VMEM write
+  call void @llvm.amdgcn.sched.group.barrier(i32 64, i32 1, i32 0)
+  ; 1 VMEM read
+  call void @llvm.amdgcn.sched.group.barrier(i32 32, i32 1, i32 0)
+  ; 2 VALU
+  call void @llvm.amdgcn.sched.group.barrier(i32 2, i32 2, i32 0)
+  ; 1 VMEM write
+  call void @llvm.amdgcn.sched.group.barrier(i32 64, i32 1, i32 0)
+  ; 1 VMEM read
+  call void @llvm.amdgcn.sched.group.barrier(i32 32, i32 1, i32 0)
+  ; 2 VALU
+  call void @llvm.amdgcn.sched.group.barrier(i32 2, i32 2, i32 0)
+  ; 1 VMEM write
+  call void @llvm.amdgcn.sched.group.barrier(i32 64, i32 1, i32 0)
+  ; 1 VMEM read
+  call void @llvm.amdgcn.sched.group.barrier(i32 32, i32 1, i32 0)
+  ; 2 VALU
+  call void @llvm.amdgcn.sched.group.barrier(i32 2, i32 2, i32 0)
+  ; 1 VMEM write
+  call void @llvm.amdgcn.sched.group.barrier(i32 64, i32 1, i32 0)
+  ; 1 VMEM read
+  call void @llvm.amdgcn.sched.group.barrier(i32 32, i32 1, i32 0)
+  ; 2 VALU
+  call void @llvm.amdgcn.sched.group.barrier(i32 2, i32 2, i32 0)
+  ; 1 VMEM write
+  call void @llvm.amdgcn.sched.group.barrier(i32 64, i32 1, i32 0)
+  ; 1 VMEM read
+  call void @llvm.amdgcn.sched.group.barrier(i32 32, i32 1, i32 0)
+  ; 2 VALU
+  call void @llvm.amdgcn.sched.group.barrier(i32 2, i32 2, i32 0)
+  ; 1 VMEM write
+  call void @llvm.amdgcn.sched.group.barrier(i32 64, i32 1, i32 0)
+  ; 1 VMEM read
+  call void @llvm.amdgcn.sched.group.barrier(i32 32, i32 1, i32 0)
+  ; 2 VALU
+  call void @llvm.amdgcn.sched.group.barrier(i32 2, i32 2, i32 0)
+  ; 1 VMEM write
+  call void @llvm.amdgcn.sched.group.barrier(i32 64, i32 1, i32 0)
+  ; 1 VMEM read
+  call void @llvm.amdgcn.sched.group.barrier(i32 32, i32 1, i32 0)
+  ; 2 VALU
+  call void @llvm.amdgcn.sched.group.barrier(i32 2, i32 2, i32 0)
+  ; 1 VMEM write
+  call void @llvm.amdgcn.sched.group.barrier(i32 64, i32 1, i32 0)
+  ret void
+}
+
+declare i32 @llvm.amdgcn.workitem.id.x() #0
+declare void @llvm.amdgcn.sched.group.barrier(i32, i32, i32) #0
+declare <32 x float> @llvm.amdgcn.mfma.f32.32x32x1f32(float, float, <32 x float>, i32, i32, i32) #0
+
+attributes #0 = { nounwind "amdgpu-flat-work-group-size"="1,256" readnone speculatable}