From a1218728d325e8e833b596438888f1dda0f68fa2 Mon Sep 17 00:00:00 2001
From: Krzysztof Parzyszek <kparzysz@codeaurora.org>
Date: Thu, 8 Sep 2016 20:48:42 +0000
Subject: [PATCH] [RDF] Further improve handling of multiple phis reached from
 shadows

llvm-svn: 280987
---
 llvm/lib/Target/Hexagon/RDFLiveness.cpp           | 47 ++++++++---------------
 llvm/test/CodeGen/Hexagon/rdf-multiple-phis-up.ll | 40 +++++++++++++++++++
 2 files changed, 56 insertions(+), 31 deletions(-)
 create mode 100644 llvm/test/CodeGen/Hexagon/rdf-multiple-phis-up.ll

diff --git a/llvm/lib/Target/Hexagon/RDFLiveness.cpp b/llvm/lib/Target/Hexagon/RDFLiveness.cpp
index 1257d52..3dfa768 100644
--- a/llvm/lib/Target/Hexagon/RDFLiveness.cpp
+++ b/llvm/lib/Target/Hexagon/RDFLiveness.cpp
@@ -109,9 +109,8 @@ NodeList Liveness::getAllReachingDefs(RegisterRef RefRR,
       continue;
     // Stop at the covering/overwriting def of the initial register reference.
     RegisterRef RR = TA.Addr->getRegRef();
-    if (RAI.covers(RR, RefRR))
-      if (!DFG.IsPreservingDef(TA))
-        continue;
+    if (!DFG.IsPreservingDef(TA) && RAI.covers(RR, RefRR))
+      continue;
     // Get the next level of reaching defs. This will include multiple
     // reaching defs for shadows.
     for (auto S : DFG.getRelatedRefs(TA.Addr->getOwner(DFG), TA))
@@ -336,13 +335,6 @@ void Liveness::computePhiInfo() {
   std::map<NodeId,std::map<NodeId,RegisterSet>> PhiUp;
   std::vector<NodeId> PhiUQ;  // Work list of phis for upward propagation.
 
-  auto isEntryPhi = [this] (NodeId P) -> bool {
-    auto PA = DFG.addr<PhiNode*>(P);
-    NodeAddr<BlockNode*> BA = PA.Addr->getOwner(DFG);
-    MachineBasicBlock *BB = BA.Addr->getCode();
-    return BB == &BB->getParent()->front();
-  };
-
   // Go over all phis.
   for (NodeAddr<PhiNode*> PhiA : Phis) {
     // Go over all defs and collect the reached uses that are non-phi uses
@@ -440,38 +432,31 @@ void Liveness::computePhiInfo() {
     // the set of registers defined between this phi (PhiA) and the owner phi
     // of the reaching def.
     NodeSet SeenUses;
+
     for (auto I : PhiRefs) {
       if (!DFG.IsRef<NodeAttrs::Use>(I) || SeenUses.count(I.Id))
         continue;
       NodeAddr<UseNode*> UA = I;
-      std::map<NodeId,RegisterSet> &PUM = PhiUp[UA.Id];
-      RegisterSet DefRRs;
-      NodeId RP = 0;  // Phi node reached upwards.
+
+      // Given a phi use UA, traverse all related phi uses (including UA).
+      // The related phi uses may reach different phi nodes or may reach the
+      // same phi node. If multiple uses reach the same phi P, the intervening
+      // defs must be accumulated for all such uses. To group all such uses
+      // into one set, map their node ids to the first use id that reaches P.
+      std::map<NodeId,NodeId> FirstUse; // Phi reached up -> first phi use.
 
       for (NodeAddr<UseNode*> VA : DFG.getRelatedRefs(PhiA, UA)) {
         SeenUses.insert(VA.Id);
+        RegisterSet DefRRs;
         for (NodeAddr<DefNode*> DA : getAllReachingDefs(VA)) {
           if (DA.Addr->getFlags() & NodeAttrs::PhiRef) {
-            // For all related phi uses, if they are reached by a phi def,
-            // all the reaching defs must belong to the same phi node.
-            // The only exception to that are the function entry phis, but
-            // are not playing any role in the subsequent propagation.
-            NodeId P = DA.Addr->getOwner(DFG).Id;
-            if (RP == 0)
-              RP = P;
-            assert(P == RP || (isEntryPhi(P) && isEntryPhi(RP)));
-          } else
-            DefRRs.insert(DA.Addr->getRegRef());
+            NodeId RP = DA.Addr->getOwner(DFG).Id;
+            NodeId FU = FirstUse.insert({RP,VA.Id}).first->second;
+            PhiUp[FU][RP].insert(DefRRs.begin(), DefRRs.end());
+          }
+          DefRRs.insert(DA.Addr->getRegRef());
         }
       }
-      // Do not add reaching information for entry phis. The data collection
-      // above was done under the assumption that registers on all phis
-      // contain all actual data-flow (i.e. a phi for R0 will not convey
-      // data-flow information for D0). This is not true for entry phis.
-      // They are not participating in the propagation anyway, so that is
-      // not a problem.
-      if (RP && !isEntryPhi(RP))
-        PUM[RP] = DefRRs;
     }
   }
 
diff --git a/llvm/test/CodeGen/Hexagon/rdf-multiple-phis-up.ll b/llvm/test/CodeGen/Hexagon/rdf-multiple-phis-up.ll
new file mode 100644
index 0000000..d23846a
--- /dev/null
+++ b/llvm/test/CodeGen/Hexagon/rdf-multiple-phis-up.ll
@@ -0,0 +1,40 @@
+; RUN: llc -march=hexagon < %s | FileCheck %s
+; REQUIRES: asserts
+
+; Check that we do not crash.
+; CHECK: call foo
+
+target triple = "hexagon"
+
+%struct.0 = type { i8*, i8*, [2 x i8*], i32, i32, i8*, i32, i32, i32, i32, i32, [2 x i32], i32, i32, i32, i32, i32, i32, i32, i32, i32, i32 }
+
+define i32 @fred(i8* %p0) local_unnamed_addr #0 {
+entry:
+  %0 = bitcast i8* %p0 to %struct.0*
+  br i1 undef, label %if.then21, label %for.body.i
+
+if.then21:                                        ; preds = %entry
+  %.pr = load i32, i32* undef, align 4
+  switch i32 %.pr, label %cleanup [
+    i32 1, label %for.body.i
+    i32 3, label %if.then60
+  ]
+
+for.body.i:                                       ; preds = %for.body.i, %if.then21, %entry
+  %1 = load i8, i8* undef, align 1
+  %cmp7.i = icmp ugt i8 %1, -17
+  br i1 %cmp7.i, label %cleanup, label %for.body.i
+
+if.then60:                                        ; preds = %if.then21
+  %call61 = call i32 @foo(%struct.0* nonnull %0) #0
+  br label %cleanup
+
+cleanup:                                          ; preds = %if.then60, %for.body.i, %if.then21
+  ret i32 undef
+}
+
+declare i32 @foo(%struct.0*) local_unnamed_addr #0
+
+
+attributes #0 = { nounwind }
+
-- 
2.7.4