[SimplifyCFG] Be more aggressive

[jmolloy]

Summary

Up the phi node folding threshold from a cheap "1" to a meagre "2".

Update tests for extra added selects and slight code churn.

[jmolloy]

Update to add a new test, checking that the idiomatic "clamp()" function is correctly optimized to two selects.

[hfinkel]

test/Transforms/SimplifyCFG/clamp.ll

6

Please actually check for the clamp code you expect.

[hfinkel]

lib/Transforms/Utils/SimplifyCFG.cpp

60

And please add a comment here explaining why the number is 2 (so that we'll get the clamp pattern, etc.).

[jmolloy]

Hi Hal,

Thanks for the review. Changes made.

Cheers,

James

[hfinkel]

Can you please provide a summary of how this affects our normal performance benchmarks?

lib/Transforms/Utils/SimplifyCFG.cpp

57

Do you mean two selects?

[jmolloy]

Hi Hal,

Sure. There is no difference in any of the industry-standard test suites I have. In LNT, I see two small regressions and 9 small improvements (on AArch64):

Regressions:

• telecomm-gsm: 4.0%
• Nodesplitting-dbl: 1.04%

Improvements:

• aha: -7.8%
• lambda: -6.16%
• covariance (from polybench): -3.65%
• gemver: -2.65%
• +5 more sub-2% improvements.

Cheers,

James

lib/Transforms/Utils/SimplifyCFG.cpp

57

No; the heuristic has to be enough that it will hoist *one* select, to then remove the branch and in the end cause two selects.

[hfinkel]

When I run this change on my POWER7 box, I see no improvements and one major regression:

MultiSource/Benchmarks/Olden/power/power
23.3258% +/- 9.53904%

I'll attempt to figure out what is going on here.

Generally speaking, I'd like to discuss a bit more, from a modeling perspective, what makes this a good idea? And, should we be using the same threshold for both FoldTwoEntryPHINode and SpeculativelyExecuteBB? We have costs for the instructions, do we need a cost for the branch? Do we need to consider whether or not we're speculating multiple instructions that are dependent on each other vs. independent?

lib/Transforms/Utils/SimplifyCFG.cpp

57

Okay, please explain that in the comment (there is no need to be terse).

[jmolloy]

Hi Hal,

I can make the comment change, no problem.

With regards modelling, I think this is going to be a very difficult problem if we want to model more accurately. The penalty for speculating instructions is a function of the number and type of instructions speculated, the in-orderness of the CPU, the predictability of the branch condition, and probably a bunch of other factors too.

I feel that, given how much better the optimizer can reason about things when they're in a single basic block, that for small sequences like this the speculated version should be the canonical form. Then CodeGenPrepare or something similarly nearer the backend can make a target-specific decision whether to expand it or not. So really, the heuristic here is mainly a cutoff to stop horribly expensive stuff from being speculated, but the backend should have the final say.

That is, the indirect benefits outweigh the direct benefits, so more accurately modelling the direct cost in SimplifyCFG we may end up making the wrong decision.

James

[hfinkel]

To provide one more data point: On an Intel Sandy Bridge box, I see no regressions and one speedup:

SingleSource/Benchmarks/CoyoteBench/huffbench
-11.4659% +/- 3.75373%

[hfinkel]

In D7507#122614, @jmolloy wrote:

Hi Hal,

I can make the comment change, no problem.

With regards modelling, I think this is going to be a very difficult problem if we want to model more accurately. The penalty for speculating instructions is a function of the number and type of instructions speculated, the in-orderness of the CPU, the predictability of the branch condition, and probably a bunch of other factors too.

I feel that, given how much better the optimizer can reason about things when they're in a single basic block, that for small sequences like this the speculated version should be the canonical form. Then CodeGenPrepare or something similarly nearer the backend can make a target-specific decision whether to expand it or not. So really, the heuristic here is mainly a cutoff to stop horribly expensive stuff from being speculated, but the backend should have the final say.

That is, the indirect benefits outweigh the direct benefits, so more accurately modelling the direct cost in SimplifyCFG we may end up making the wrong decision.

Fair enough, but sometimes we need to take the "do no harm" approach. Nevertheless, it turns out my P7 performance regression was a combination of a faulty script and a compiler crash, so we can ignore that (it is a good thing that I investigated it, however, because it turns out it was a serious regression). I think that we may need to return to the modeling question here, but I think we can move forward with this for now (all of my testing is neutral, both on PPC and on X86, with a speedup on x86). LGTM.

James

[jmolloy]

Thanks Hal,

Landed in r229099.

James

lib/Transforms/Utils/SimplifyCFG.cpp

 #include <algorithm>
 #include <map>
 #include <set>
 using namespace llvm;
 using namespace PatternMatch;
 
 #define DEBUG_TYPE "simplifycfg"
 
+// Chosen as 2 so as to be cheap, but still to have enough power to fold
+// a select, so the "clamp" idiom (of a min followed by a max) will be caught.
 static cl::opt<unsigned>
-PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(1),
-   cl::desc("Control the amount of phi node folding to perform (default = 1)"));
+PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(2),
+   cl::desc("Control the amount of phi node folding to perform (default = 2)"));
 
 static cl::opt<bool>
 DupRet("simplifycfg-dup-ret", cl::Hidden, cl::init(false),
        cl::desc("Duplicate return instructions into unconditional branches"));
 
 static cl::opt<bool>
 SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true),
        cl::desc("Sink common instructions down to the end block"));

test/CodeGen/AArch64/analyzecmp.ll

 ; RUN: llc -O3 -mcpu=cortex-a57 < %s | FileCheck %s 
 
-; CHECK-LABLE: @test
-; CHECK: tst [[CMP:x[0-9]+]], #0x8000000000000000
-; CHECK: csel [[R0:x[0-9]+]], [[S0:x[0-9]+]], [[S1:x[0-9]+]], eq
-; CHECK: csel [[R1:x[0-9]+]], [[S2:x[0-9]+]], [[S3:x[0-9]+]], eq
+; CHECK-LABEL: @test
+; CHECK: and 
+; CHECK: csel
+; CHECK: csel
 target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
 target triple = "arm64--linux-gnueabi"
 
 define void @test(i64 %a, i64* %ptr1, i64* %ptr2) #0 align 2 {
 entry:
   %conv = and i64 %a, 4294967295
   %add = add nsw i64 %conv, -1
   %div = sdiv i64 %add, 64

test/CodeGen/AArch64/arm64-promote-const.ll

 
 ; Two different uses of the sane constant in two different basic blocks,
 ; one is in a phi.
 define <16 x i8> @test5(<16 x i8> %arg, i32 %path) {
 ; PROMOTED-LABEL: test5:
 ; In stress mode, constant vector are promoted
 ; Since, the constant is the same as the previous function,
 ; the same address must be used
-; PROMOTED: adrp [[PAGEADDR:x[0-9]+]], [[CSTV1]]@PAGE
-; PROMOTED-NEXT: ldr q[[REGNUM:[0-9]+]], {{\[}}[[PAGEADDR]], [[CSTV1]]@PAGEOFF]
-; PROMOTED-NEXT: cbz w0, [[LABEL:LBB.*]]
-; Next BB
-; PROMOTED: add.16b [[DESTV:v[0-9]+]], v0, v[[REGNUM]]
-; PROMOTED-NEXT: mul.16b v[[REGNUM]], [[DESTV]], v[[REGNUM]]
-; Next BB
-; PROMOTED-NEXT: [[LABEL]]:
-; PROMOTED-NEXT: mul.16b [[TMP1:v[0-9]+]], v[[REGNUM]], v[[REGNUM]]
-; PROMOTED-NEXT: mul.16b [[TMP2:v[0-9]+]], [[TMP1]], [[TMP1]]
-; PROMOTED-NEXT: mul.16b [[TMP3:v[0-9]+]], [[TMP2]], [[TMP2]]
-; PROMOTED-NEXT: mul.16b v0, [[TMP3]], [[TMP3]]
-; PROMOTED-NEXT: ret
+; PROMOTED: ldr
+; PROMOTED-NOT: ldr
+; PROMOTED: ret
 
 ; REGULAR-LABEL: test5:
-; REGULAR: cbz w0, [[LABELelse:LBB.*]]
-; Next BB
-; REGULAR: adrp [[PAGEADDR:x[0-9]+]], [[CSTLABEL:lCP.*]]@PAGE
-; REGULAR-NEXT: ldr q[[REGNUM:[0-9]+]], {{\[}}[[PAGEADDR]], [[CSTLABEL]]@PAGEOFF]
-; REGULAR-NEXT: add.16b [[DESTV:v[0-9]+]], v0, v[[REGNUM]]
-; REGULAR-NEXT: mul.16b v[[DESTREGNUM:[0-9]+]], [[DESTV]], v[[REGNUM]]
-; REGULAR-NEXT: b [[LABELend:LBB.*]]
-; Next BB
-; REGULAR-NEXT: [[LABELelse]]
-; REGULAR-NEXT: adrp [[PAGEADDR:x[0-9]+]], [[CSTLABEL:lCP.*]]@PAGE
-; REGULAR-NEXT: ldr q[[DESTREGNUM]], {{\[}}[[PAGEADDR]], [[CSTLABEL]]@PAGEOFF]
-; Next BB
-; REGULAR-NEXT: [[LABELend]]:
-; REGULAR-NEXT: mul.16b [[TMP1:v[0-9]+]], v[[DESTREGNUM]], v[[DESTREGNUM]]
-; REGULAR-NEXT: mul.16b [[TMP2:v[0-9]+]], [[TMP1]], [[TMP1]]
-; REGULAR-NEXT: mul.16b [[TMP3:v[0-9]+]], [[TMP2]], [[TMP2]]
-; REGULAR-NEXT: mul.16b v0, [[TMP3]], [[TMP3]]
-; REGULAR-NEXT: ret
+; REGULAR: ldr
+; REGULAR: ret
 entry:
   %tobool = icmp eq i32 %path, 0
   br i1 %tobool, label %if.end, label %if.then
 
 if.then:                                          ; preds = %entry
   %add.i = add <16 x i8> %arg, <i8 -40, i8 -93, i8 -118, i8 -99, i8 -75, i8 -105, i8 74, i8 -110, i8 62, i8 -115, i8 -119, i8 -120, i8 34, i8 -124, i8 0, i8 -128>
   %mul.i26 = mul <16 x i8> %add.i, <i8 -40, i8 -93, i8 -118, i8 -99, i8 -75, i8 -105, i8 74, i8 -110, i8 62, i8 -115, i8 -119, i8 -120, i8 34, i8 -124, i8 0, i8 -128>
   br label %if.end

test/Transforms/SimplifyCFG/clamp.ll

+; RUN: opt < %s -simplifycfg -S | FileCheck %s
+
+define float @clamp(float %a, float %b, float %c) {
+; CHECK-LABEL: @clamp
+; CHECK:  %cmp = fcmp ogt float %a, %c
+; CHECK:  %cmp1 = fcmp olt float %a, %b
+; CHECK:  %cond = select i1 %cmp1, float %b, float %a
+; CHECK:  %cond5 = select i1 %cmp, float %c, float %cond
+; CHECK:  ret float %cond5
+entry:
+  %cmp = fcmp ogt float %a, %c
+  br i1 %cmp, label %cond.end4, label %cond.false
+
+cond.false:                                       ; preds = %entry
+  %cmp1 = fcmp olt float %a, %b
+  %cond = select i1 %cmp1, float %b, float %a
+  br label %cond.end4
+
+cond.end4:                                        ; preds = %entry, %cond.false
+  %cond5 = phi float [ %cond, %cond.false ], [ %c, %entry ]
+  ret float %cond5
+}