[RDF] Fix live def propagation through basic block

llvm-svn: 283371

2 files changed, 274 insertions, 45 deletions

diff --git a/llvm/lib/Target/Hexagon/RDFLiveness.cpp b/llvm/lib/Target/Hexagon/RDFLiveness.cpp
index d3b2d579e5b..55248899b5f 100644
--- a/llvm/lib/Target/Hexagon/RDFLiveness.cpp
+++ b/llvm/lib/Target/Hexagon/RDFLiveness.cpp
@@ -836,7 +836,7 @@ void Liveness::traverse(MachineBasicBlock *B, RefMap &LiveIn) {
     dbgs() << "  Local:  " << Print<RegisterSet>(LiveMap[B], DFG) << '\n';
   }
 
-  // Add phi uses that are live on exit from this block.
+  // Add reaching defs of phi uses that are live on exit from this block.
   RefMap &PUs = PhiLOX[B];
   for (auto S : PUs)
     LiveIn[S.first].insert(S.second.begin(), S.second.end());
@@ -847,62 +847,77 @@ void Liveness::traverse(MachineBasicBlock *B, RefMap &LiveIn) {
     dbgs() << "  Local:  " << Print<RegisterSet>(LiveMap[B], DFG) << '\n';
   }
 
-  // Stop tracking all uses defined in this block: erase those records
-  // where the reaching def is located in B and which cover all reached
-  // uses.
-  auto Copy = LiveIn;
+  // The LiveIn map at this point has all defs that are live-on-exit from B,
+  // as if they were live-on-entry to B. First, we need to filter out all
+  // defs that are present in this block. Then we will add reaching defs of
+  // all upward-exposed uses.
+
+  // To filter out the defs, first make a copy of LiveIn, and then re-populate
+  // LiveIn with the defs that should remain.
+  RefMap LiveInCopy = LiveIn;
   LiveIn.clear();
 
-  for (auto I : Copy) {
-    auto &Defs = LiveIn[I.first];
-    NodeSet Rest;
-    for (auto R : I.second) {
+  for (const std::pair<RegisterRef,NodeSet> &LE : LiveInCopy) {
+    RegisterRef LRef = LE.first;
+    NodeSet &NewDefs = LiveIn[LRef]; // To be filled.
+    const NodeSet &OldDefs = LE.second;
+    for (NodeId R : OldDefs) {
+      // R is a def node that was live-on-exit
       auto DA = DFG.addr<DefNode*>(R);
-      RegisterRef DDR = DA.Addr->getRegRef();
       NodeAddr<InstrNode*> IA = DA.Addr->getOwner(DFG);
       NodeAddr<BlockNode*> BA = IA.Addr->getOwner(DFG);
-      // Defs from a different block need to be preserved. Defs from this
-      // block will need to be processed further, except for phi defs, the
-      // liveness of which is handled through the PhiLON/PhiLOX maps.
-      if (B != BA.Addr->getCode())
-        Defs.insert(R);
-      else {
-        bool IsPreserving = DFG.IsPreservingDef(DA);
-        if (IA.Addr->getKind() != NodeAttrs::Phi && !IsPreserving) {
-          bool Covering = RegisterAggr::isCoverOf(DDR, I.first,
-                                                  DFG.getLMI(), TRI);
-          NodeId U = DA.Addr->getReachedUse();
-          while (U && Covering) {
-            auto DUA = DFG.addr<UseNode*>(U);
-            if (!(DUA.Addr->getFlags() & NodeAttrs::Undef)) {
-              RegisterRef Q = DUA.Addr->getRegRef();
-              Covering = RegisterAggr::isCoverOf(DA.Addr->getRegRef(), Q,
-                                                 DFG.getLMI(), TRI);
-            }
-            U = DUA.Addr->getSibling();
-          }
-          if (!Covering)
-            Rest.insert(R);
-        }
+      if (B != BA.Addr->getCode()) {
+        // Defs from a different block need to be preserved. Defs from this
+        // block will need to be processed further, except for phi defs, the
+        // liveness of which is handled through the PhiLON/PhiLOX maps.
+        NewDefs.insert(R);
+        continue;
       }
-    }
 
-    // Non-covering defs from B.
-    for (auto R : Rest) {
-      auto DA = DFG.addr<DefNode*>(R);
-      RegisterRef DRR = DA.Addr->getRegRef();
+      // Defs from this block need to stop the liveness from being
+      // propagated upwards. This only applies to non-preserving defs,
+      // and to the parts of the register actually covered by those defs.
+      // (Note that phi defs should always be preserving.)
       RegisterAggr RRs(DFG.getLMI(), TRI);
+
+      if (!DFG.IsPreservingDef(DA)) {
+        assert(!(IA.Addr->getFlags() & NodeAttrs::Phi));
+        // DA is a non-phi def that is live-on-exit from this block, and
+        // that is also located in this block. LRef is a register ref
+        // whose use this def reaches. If DA covers LRef, then no part
+        // of LRef is exposed upwards.
+        if (RRs.insert(DA.Addr->getRegRef()).hasCoverOf(LRef))
+          continue;
+      }
+
+      // DA itself was not sufficient to cover LRef. In general, it is
+      // the last in a chain of aliased defs before the exit from this block.
+      // There could be other defs in this block that are a part of that
+      // chain. Check that now: accumulate the registers from these defs,
+      // and if they all together cover LRef, it is not live-on-entry.
       for (NodeAddr<DefNode*> TA : getAllReachingDefs(DA)) {
-        NodeAddr<InstrNode*> IA = TA.Addr->getOwner(DFG);
-        NodeAddr<BlockNode*> BA = IA.Addr->getOwner(DFG);
-        // Preserving defs do not count towards covering.
+        // DefNode -> InstrNode -> BlockNode.
+        NodeAddr<InstrNode*> ITA = TA.Addr->getOwner(DFG);
+        NodeAddr<BlockNode*> BTA = ITA.Addr->getOwner(DFG);
+        // Reaching defs are ordered in the upward direction.
+        if (BTA.Addr->getCode() != B) {
+          // We have reached past the beginning of B, and the accumulated
+          // registers are not covering LRef. The first def from the
+          // upward chain will be live.
+          // FIXME: This is where the live-in lane mask could be set.
+          //        It cannot be be changed directly, because it is a part
+          //        of the map key (LRef).
+          NewDefs.insert(TA.Id);
+          break;
+        }
+
+        // TA is in B. Only add this def to the accumulated cover if it is
+        // not preserving.
         if (!(TA.Addr->getFlags() & NodeAttrs::Preserving))
           RRs.insert(TA.Addr->getRegRef());
-        if (BA.Addr->getCode() == B)
-          continue;
-        if (RRs.hasCoverOf(DRR))
+        // If this is enough to cover LRef, then stop.
+        if (RRs.hasCoverOf(LRef))
           break;
-        Defs.insert(TA.Id);
       }
     }
   }
diff --git a/llvm/test/CodeGen/Hexagon/rdf-filter-defs.ll b/llvm/test/CodeGen/Hexagon/rdf-filter-defs.ll
new file mode 100644
index 00000000000..735b20e697f
--- /dev/null
+++ b/llvm/test/CodeGen/Hexagon/rdf-filter-defs.ll
@@ -0,0 +1,214 @@
+; RUN: llc -march=hexagon -verify-machineinstrs < %s | FileCheck %s
+
+; Check that this testcase compiles successfully.
+; CHECK: dealloc_return
+
+target triple = "hexagon"
+
+%type.0 = type { %type.1, %type.3, i32, i32 }
+%type.1 = type { %type.2 }
+%type.2 = type { i8 }
+%type.3 = type { i8*, [12 x i8] }
+%type.4 = type { i8 }
+
+define weak_odr dereferenceable(28) %type.0* @fred(%type.0* %p0, i32 %p1, %type.0* dereferenceable(28) %p2, i32 %p3, i32 %p4) local_unnamed_addr align 2 {
+b0:
+  %t0 = getelementptr inbounds %type.0, %type.0* %p0, i32 0, i32 2
+  %t1 = load i32, i32* %t0, align 4
+  %t2 = icmp ult i32 %t1, %p1
+  %t3 = getelementptr inbounds %type.0, %type.0* %p2, i32 0, i32 2
+  br i1 %t2, label %b2, label %b1
+
+b1:
+  %t4 = load i32, i32* %t3, align 4
+  %t5 = icmp ult i32 %t4, %p3
+  br i1 %t5, label %b2, label %b3
+
+b2:
+  %t6 = bitcast %type.0* %p0 to %type.4*
+  tail call void @blah(%type.4* %t6)
+  %t7 = load i32, i32* %t3, align 4
+  %t8 = load i32, i32* %t0, align 4
+  br label %b3
+
+b3:
+  %t9 = phi i32 [ %t8, %b2 ], [ %t1, %b1 ]
+  %t10 = phi i32 [ %t7, %b2 ], [ %t4, %b1 ]
+  %t11 = sub i32 %t10, %p3
+  %t12 = icmp ult i32 %t11, %p4
+  %t13 = select i1 %t12, i32 %t11, i32 %p4
+  %t14 = xor i32 %t9, -1
+  %t15 = icmp ult i32 %t13, %t14
+  br i1 %t15, label %b5, label %b4
+
+b4:
+  %t16 = bitcast %type.0* %p0 to %type.4*
+  tail call void @danny(%type.4* %t16)
+  br label %b5
+
+b5:
+  %t17 = icmp eq i32 %t13, 0
+  br i1 %t17, label %b33, label %b6
+
+b6:
+  %t18 = load i32, i32* %t0, align 4
+  %t19 = add i32 %t18, %t13
+  %t20 = icmp eq i32 %t19, -1
+  br i1 %t20, label %b7, label %b8
+
+b7:
+  %t21 = bitcast %type.0* %p0 to %type.4*
+  tail call void @danny(%type.4* %t21)
+  br label %b8
+
+b8:
+  %t22 = getelementptr inbounds %type.0, %type.0* %p0, i32 0, i32 3
+  %t23 = load i32, i32* %t22, align 4
+  %t24 = icmp ult i32 %t23, %t19
+  br i1 %t24, label %b9, label %b10
+
+b9:
+  %t25 = load i32, i32* %t0, align 4
+  tail call void @sammy(%type.0* nonnull %p0, i32 %t19, i32 %t25)
+  %t26 = load i32, i32* %t22, align 4
+  br label %b15
+
+b10:
+  %t27 = icmp eq i32 %t19, 0
+  br i1 %t27, label %b11, label %b15
+
+b11:
+  %t28 = icmp ugt i32 %t23, 15
+  %t29 = getelementptr inbounds %type.0, %type.0* %p0, i32 0, i32 1
+  br i1 %t28, label %b12, label %b13
+
+b12:
+  %t30 = getelementptr inbounds %type.3, %type.3* %t29, i32 0, i32 0
+  %t31 = load i8*, i8** %t30, align 4
+  br label %b14
+
+b13:
+  %t32 = bitcast %type.3* %t29 to i8*
+  br label %b14
+
+b14:
+  %t33 = phi i8* [ %t31, %b12 ], [ %t32, %b13 ]
+  store i32 0, i32* %t0, align 4
+  br label %b31
+
+b15:
+  %t34 = phi i32 [ %t26, %b9 ], [ %t23, %b10 ]
+  %t35 = icmp ugt i32 %t34, 15
+  %t36 = getelementptr inbounds %type.0, %type.0* %p0, i32 0, i32 1
+  br i1 %t35, label %b16, label %b17
+
+b16:
+  %t37 = getelementptr inbounds %type.3, %type.3* %t36, i32 0, i32 0
+  %t38 = load i8*, i8** %t37, align 4
+  br label %b18
+
+b17:
+  %t39 = bitcast %type.3* %t36 to i8*
+  %t40 = bitcast %type.3* %t36 to i8*
+  br label %b18
+
+b18:
+  %t41 = phi i8* [ %t38, %b16 ], [ %t39, %b17 ]
+  %t42 = phi i8* [ %t38, %b16 ], [ %t40, %b17 ]
+  %t43 = getelementptr inbounds i8, i8* %t41, i32 %p1
+  %t44 = getelementptr inbounds i8, i8* %t43, i32 %t13
+  %t45 = getelementptr inbounds i8, i8* %t42, i32 %p1
+  %t46 = load i32, i32* %t0, align 4
+  %t47 = sub i32 %t46, %p1
+  tail call void @llvm.memmove.p0i8.p0i8.i32(i8* %t44, i8* %t45, i32 %t47, i32 1, i1 false) #1
+  %t48 = icmp eq %type.0* %p0, %p2
+  %t49 = load i32, i32* %t22, align 4
+  %t50 = icmp ugt i32 %t49, 15
+  br i1 %t50, label %b19, label %b20
+
+b19:
+  %t51 = getelementptr inbounds %type.3, %type.3* %t36, i32 0, i32 0
+  %t52 = load i8*, i8** %t51, align 4
+  br label %b21
+
+b20:
+  %t53 = bitcast %type.3* %t36 to i8*
+  br label %b21
+
+b21:
+  %t54 = phi i8* [ %t52, %b19 ], [ %t53, %b20 ]
+  %t55 = getelementptr inbounds i8, i8* %t54, i32 %p1
+  br i1 %t48, label %b22, label %b26
+
+b22:
+  br i1 %t50, label %b23, label %b24
+
+b23:
+  %t56 = getelementptr inbounds %type.3, %type.3* %t36, i32 0, i32 0
+  %t57 = load i8*, i8** %t56, align 4
+  br label %b25
+
+b24:
+  %t58 = bitcast %type.3* %t36 to i8*
+  br label %b25
+
+b25:
+  %t59 = phi i8* [ %t57, %b23 ], [ %t58, %b24 ]
+  %t60 = icmp ult i32 %p1, %p3
+  %t61 = select i1 %t60, i32 %t13, i32 0
+  %t62 = add i32 %t61, %p3
+  %t63 = getelementptr inbounds i8, i8* %t59, i32 %t62
+  tail call void @llvm.memmove.p0i8.p0i8.i32(i8* %t55, i8* %t63, i32 %t13, i32 1, i1 false) #1
+  br label %b27
+
+b26:
+  %t64 = getelementptr inbounds %type.0, %type.0* %p2, i32 0, i32 3
+  %t65 = load i32, i32* %t64, align 4
+  %t66 = icmp ugt i32 %t65, 15
+  %t67 = getelementptr inbounds %type.0, %type.0* %p2, i32 0, i32 1
+  %t68 = getelementptr inbounds %type.3, %type.3* %t67, i32 0, i32 0
+  %t69 = load i8*, i8** %t68, align 4
+  %t70 = bitcast %type.3* %t67 to i8*
+  %t71 = select i1 %t66, i8* %t69, i8* %t70
+  %t72 = getelementptr inbounds i8, i8* %t71, i32 %p3
+  tail call void @llvm.memcpy.p0i8.p0i8.i32(i8* %t55, i8* %t72, i32 %t13, i32 1, i1 false) #1
+  br label %b27
+
+b27:
+  %t73 = load i32, i32* %t22, align 4
+  %t74 = icmp ugt i32 %t73, 15
+  br i1 %t74, label %b28, label %b29
+
+b28:
+  %t75 = getelementptr inbounds %type.3, %type.3* %t36, i32 0, i32 0
+  %t76 = load i8*, i8** %t75, align 4
+  br label %b30
+
+b29:
+  %t77 = bitcast %type.3* %t36 to i8*
+  br label %b30
+
+b30:
+  %t78 = phi i8* [ %t76, %b28 ], [ %t77, %b29 ]
+  store i32 %t19, i32* %t0, align 4
+  %t79 = getelementptr inbounds i8, i8* %t78, i32 %t19
+  br label %b31
+
+b31:
+  %t80 = phi i8* [ %t33, %b14 ], [ %t79, %b30 ]
+  store i8 0, i8* %t80, align 1
+  br label %b33
+
+b33:
+  ret %type.0* %p0
+}
+
+declare void @llvm.memcpy.p0i8.p0i8.i32(i8* nocapture writeonly, i8* nocapture readonly, i32, i32, i1) #0
+declare void @llvm.memmove.p0i8.p0i8.i32(i8* nocapture, i8* nocapture readonly, i32, i32, i1) #0
+
+declare void @blah(%type.4*) local_unnamed_addr
+declare void @danny(%type.4*) local_unnamed_addr
+declare void @sammy(%type.0*, i32, i32) local_unnamed_addr align 2
+
+attributes #0 = { argmemonly nounwind }
+attributes #1 = { nounwind }