[CGP] Limit distance between overflow math and cmp

[samparker]

Summary

Inserting an overflowing arithmetic intrinsic can increase register pressure by producing two values at a point where only one is needed, while the second use maybe several blocks away. This increase in pressure could be more detrimental on performance than rematerialising one of the original instructions.

So, check that the arithmetic and compare instructions are no further apart than their immediate successor/predecessor. covers the existing test cases.

[spatel]

This will need to be rebased to account for D58995 / rL355512,
and we may want to do some preliminary testing to confirm that compile-time is not impacted (cc @tejohnson ).
I'm not opposed to the patch, but I don't know enough about DominatorTree mechanics to approve, so someone else will need to review this patch too.

[samparker]

Okay, rebased.

[dmgreen]

Hello. I think the idea of this sounds sensible, to limit things if the instruction are too far apart, I'm just not sure of using domtree's to do that.

lib/CodeGen/CodeGenPrepare.cpp

1196 ↗

(On Diff #189510)

I'm not sure this will reliably calculate a meaningful distance for a lot of trees. And I'm not sure that the children of a node are necessarily always in the same deterministic order. The node level may be better, but the distance in the domtree is probably not be the best measure.

Maybe, because the Distance is small, can we just search back through preds to find the block? We already know which one dominates, and most times they will be in the same block. We would have to be careful of compile time, but if we don't have to search more that Distance, and Distance is fairly small, hopefully it will work OK.

1199 ↗

(On Diff #189510)

2 is a magic number? Is it worth making a cl:opt for it, so it at least has a name?

[samparker]

lib/CodeGen/CodeGenPrepare.cpp

1196 ↗

(On Diff #189510)

This sounds perfectly reasonable to me. I'll do a BFS and limit the depth using the cl::opt.

[spatel]

In D59024#1422562, @dmgreen wrote:

Hello. I think the idea of this sounds sensible, to limit things if the instruction are too far apart, I'm just not sure of using domtree's to do that.

This is a hack, but given that this code has been shown to be compile-time sensitive: what if we limit the transform to cases where the instructions are in the same block or a direct predecessor block? IIUC, that would prevent the transform for the motivating cases here, but not affect any of the existing tests.

[spatel]

Independent of this patch, but may affect how we proceed:
https://bugs.llvm.org/show_bug.cgi?id=41004

[samparker]

Thanks Sanjay, a simple search works for us too. I've updated to check the immediate successors.

[dmgreen]

lib/CodeGen/CodeGenPrepare.cpp

1193 ↗

(On Diff #190052)

Can you use std::find (or llvm::find)?

[samparker]

Cheers Dave, that's far nicer.

[dmgreen]

Looks OK to me.

llvm/trunk/lib/CodeGen/CodeGenPrepare.cpp

if (BO->hasOneUse() && BO->user_back() == Cmp) {
     // compares to help out SDAG.)
     InsertPt = Cmp;
   } else {
     // The math and compare may be independent instructions. Check dominance to
     // determine the insertion point for the intrinsic.
     bool MathDominates = DT.dominates(BO, Cmp);
     if (!MathDominates && !DT.dominates(Cmp, BO))
       return false;
+
+    // Check that the insertion doesn't create a value that is live across more
+    // than two blocks, so to minimise the increase in register pressure.
+    if (BO->getParent() != Cmp->getParent()) {
+      BasicBlock *Dominator = MathDominates ? BO->getParent() : Cmp->getParent();
+      BasicBlock *Dominated = MathDominates ? Cmp->getParent() : BO->getParent();
+      auto Successors = successors(Dominator);
+      if (llvm::find(Successors, Dominated) == Successors.end())
+        return false;
+    }
+
     InsertPt = MathDominates ? cast<Instruction>(BO) : cast<Instruction>(Cmp);
   }
 
   IRBuilder<> Builder(InsertPt);
   Value *MathOV = Builder.CreateBinaryIntrinsic(IID, Arg0, Arg1);
   Value *Math = Builder.CreateExtractValue(MathOV, 0, "math");
   Value *OV = Builder.CreateExtractValue(MathOV, 1, "ov");
   BO->replaceAllUsesWith(Math);

llvm/trunk/test/Transforms/CodeGenPrepare/ARM/overflow-intrinsics.ll

+; RUN: opt -codegenprepare -S < %s | FileCheck %s
+
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
+target triple = "thumbv8m.main-arm-none-eabi"
+
+; CHECK-LABEL: uadd_overflow_too_far_cmp_dom
+; CHECK-NOT: with.overflow.i32
+define i32 @uadd_overflow_too_far_cmp_dom(i32 %arg0) {
+entry:
+  %cmp = icmp ne i32 %arg0, 0
+  br i1 %cmp, label %if.else, label %if.then
+
+if.then:
+  call void @foo()
+  br label %exit
+
+if.else:
+  call void @bar()
+  br label %if.end
+
+if.end:
+  %dec = add nsw i32 %arg0, -1
+  br label %exit
+
+exit:
+  %res = phi i32 [ %arg0, %if.then ], [ %dec, %if.end ]
+  ret i32 %res
+}
+
+; CHECK-LABEL: uadd_overflow_too_far_math_dom
+; CHECK-NOT: with.overflow.i32
+define i32 @uadd_overflow_too_far_math_dom(i32 %arg0, i32 %arg1) {
+entry:
+  %dec = add nsw i32 %arg0, -1
+  %cmp = icmp ugt i32 %arg0, 1
+  br i1 %cmp, label %if.else, label %if.then
+
+if.then:
+  call void @foo()
+  br label %if.end
+
+if.else:
+  call void @bar()
+  br label %if.end
+
+if.end:
+  %cmp.i.i = icmp ne i32 %arg0, 0
+  %tobool = zext i1 %cmp.i.i to i32
+  br label %exit
+
+exit:
+  ret i32 %tobool
+}
+
+declare void @foo()
+declare void @bar()