[SimplifyCFG] Fix inconsistency in block size assessment for threading

[mkazantsev]

Summary

Sometimes SimplifyCFG may decide to perform jump threading. In order
to do it, it follows the following algorithm:

1. Checks if the block is small enough for threading;
2. If yes, inserts a PR Phi relying that the next iteration will remove it by performing jump threading;
3. The next iteration checks the block again and performs the threading.

This logic has a corner case: inserting the PR Phi increases block's size
by 1. If the block size at first check was max possible, one more Phi will
exceed this size, and we will neither perform threading nor remove the
created Phi node. As result, we will end up with worse IR than before.

This patch fixes this situation by excluding Phis from block size computation.
Excluding Phis from size computation for threading also makes sense by
itself because in case of threadign all those Phis will be removed.

[mkazantsev]

clang-format

[xbolva00]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2199

Skip llvm.assume too?

[nikic]

llvm/test/Transforms/PhaseOrdering/inlining-alignment-assumptions.ll

17

This test should be adjusted with extra store -1 to retain the previous behavior, otherwise it doesn't show what it's supposed to be showing.

[mkazantsev]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2199

Not sure if it makes sense, given that this restriction's point (or at least one of them) is to save compile time.

llvm/test/Transforms/PhaseOrdering/inlining-alignment-assumptions.ll

17

Ok.

[mkazantsev]

Fixed test.

[mkazantsev]

Ping

[mkazantsev]

Ping.

[asbirlea]

LGTM, but please wait to see if nikic@ has additional comments.

[nikic]

LG as well. The phis are a threading opportunity, not a cost.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2198

This comment is a bit confusing to me. I would reason the other way around here and say "We will delete Phis while threading, so Phis should not be accounted in block's size".

llvm/test/Transforms/PhaseOrdering/inlining-alignment-assumptions.ll

17

The changes in this test will probably have gone away due to a change to alignment assumptions that has landed in the meantime.

[mkazantsev]

Thanks!

[mkazantsev]

commit f01d9e6fc3e291a2faed8c9b7dcbabf760f32bd6
Author: Max Kazantsev <[e-mail]>
Date:   Tue Jun 30 12:38:15 2020 +0700

    [SimplifyCFG] Fix inconsistency in block size assessment for threading

    Sometimes SimplifyCFG may decide to perform jump threading. In order
    to do it, it follows the following algorithm:

    1. Checks if the block is small enough for threading;
    2. If yes, inserts a PR Phi relying that the next iteration will remove it
       by performing jump threading;
    3. The next iteration checks the block again and performs the threading.

    This logic has a corner case: inserting the PR Phi increases block's size
    by 1. If the block size at first check was max possible, one more Phi will
    exceed this size, and we will neither perform threading nor remove the
    created Phi node. As result, we will end up with worse IR than before.

    This patch fixes this situation by excluding Phis from block size computation.
    Excluding Phis from size computation for threading also makes sense by
    itself because in case of threadign all those Phis will be removed.

    Differential Revision: https://reviews.llvm.org/D81835
    Reviewed By: asbirlea, nikic

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

static cl::opt<bool> SpeculateOneExpensiveInst(
     cl::desc("Allow exactly one expensive instruction to be speculatively "
              "executed"));
 
 static cl::opt<unsigned> MaxSpeculationDepth(
     "max-speculation-depth", cl::Hidden, cl::init(10),
     cl::desc("Limit maximum recursion depth when calculating costs of "
              "speculatively executed instructions"));
 
+static cl::opt<int>
+MaxSmallBlockSize("simplifycfg-max-small-block-size", cl::Hidden, cl::init(10),
+                  cl::desc("Max size of a block which is still considered "
+                           "small enough to thread through"));
+
 STATISTIC(NumBitMaps, "Number of switch instructions turned into bitmaps");
 STATISTIC(NumLinearMaps,
           "Number of switch instructions turned into linear mapping");
 STATISTIC(NumLookupTables,
           "Number of switch instructions turned into lookup tables");
 STATISTIC(
     NumLookupTablesHoles,
     "Number of switch instructions turned into lookup tables (holes checked)");
bool SimplifyCFGOpt::SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB,
   return true;
 }
 
 /// Return true if we can thread a branch across this block.
 static bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB) {
   unsigned Size = 0;
 
   for (Instruction &I : BB->instructionsWithoutDebug()) {
-    if (Size > 10)
+    if (Size > MaxSmallBlockSize)
       return false; // Don't clone large BB's.
+    // We insert PRE Phis purely for threading, so Phis should not be
+    // accounted in block's size.
+    if (!isa<PHINode>(I))
       ++Size;
 
     // We can only support instructions that do not define values that are
     // live outside of the current basic block.
     for (User *U : I.users()) {
       Instruction *UI = cast<Instruction>(U);
       if (UI->getParent() != BB || isa<PHINode>(UI))
         return false;
     }

llvm/test/Transforms/PhaseOrdering/inlining-alignment-assumptions.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -O2 -preserve-alignment-assumptions-during-inlining=0 < %s | FileCheck %s --check-prefixes=CHECK,ASSUMPTIONS-OFF,FALLBACK-0
 ; RUN: opt -S -O2 -preserve-alignment-assumptions-during-inlining=1 < %s | FileCheck %s --check-prefixes=CHECK,ASSUMPTIONS-ON,FALLBACK-1
 ; RUN: opt -S -O2 < %s | FileCheck %s --check-prefixes=CHECK,ASSUMPTIONS-OFF,FALLBACK-DEFAULT
 
 target datalayout = "e-p:64:64-p5:32:32-A5"
 
 ; This illustrates an optimization difference caused by instruction counting
 ; heuristics, which are affected by the additional instructions of the
 ; alignment assumption.
 
 define internal i1 @callee1(i1 %c, i64* align 8 %ptr) {
   store volatile i64 0, i64* %ptr
   ret i1 %c
 }
 
 define void @caller1(i1 %c, i64* align 1 %ptr) {
 ; ASSUMPTIONS-OFF-LABEL: @caller1(
-; ASSUMPTIONS-OFF-NEXT:    br i1 [[C:%.*]], label [[TRUE2:%.*]], label [[FALSE2:%.*]]
-; ASSUMPTIONS-OFF:       true2:
-; ASSUMPTIONS-OFF-NEXT:    store volatile i64 0, i64* [[PTR:%.*]], align 8
+; ASSUMPTIONS-OFF-NEXT:    br i1 [[C:%.*]], label [[TRUE2_CRITEDGE:%.*]], label [[FALSE1:%.*]]
+; ASSUMPTIONS-OFF:       false1:
+; ASSUMPTIONS-OFF-NEXT:    store volatile i64 1, i64* [[PTR:%.*]], align 4
+; ASSUMPTIONS-OFF-NEXT:    store volatile i64 0, i64* [[PTR]], align 8
 ; ASSUMPTIONS-OFF-NEXT:    store volatile i64 -1, i64* [[PTR]], align 4
 ; ASSUMPTIONS-OFF-NEXT:    store volatile i64 -1, i64* [[PTR]], align 4
 ; ASSUMPTIONS-OFF-NEXT:    store volatile i64 -1, i64* [[PTR]], align 4
 ; ASSUMPTIONS-OFF-NEXT:    store volatile i64 -1, i64* [[PTR]], align 4
 ; ASSUMPTIONS-OFF-NEXT:    store volatile i64 -1, i64* [[PTR]], align 4
-; ASSUMPTIONS-OFF-NEXT:    store volatile i64 2, i64* [[PTR]], align 4
+; ASSUMPTIONS-OFF-NEXT:    store volatile i64 -1, i64* [[PTR]], align 4
+; ASSUMPTIONS-OFF-NEXT:    store volatile i64 3, i64* [[PTR]], align 4
 ; ASSUMPTIONS-OFF-NEXT:    ret void
-; ASSUMPTIONS-OFF:       false2:
-; ASSUMPTIONS-OFF-NEXT:    store volatile i64 1, i64* [[PTR]], align 4
+; ASSUMPTIONS-OFF:       true2.critedge:
 ; ASSUMPTIONS-OFF-NEXT:    store volatile i64 0, i64* [[PTR]], align 8
 ; ASSUMPTIONS-OFF-NEXT:    store volatile i64 -1, i64* [[PTR]], align 4
 ; ASSUMPTIONS-OFF-NEXT:    store volatile i64 -1, i64* [[PTR]], align 4
 ; ASSUMPTIONS-OFF-NEXT:    store volatile i64 -1, i64* [[PTR]], align 4
 ; ASSUMPTIONS-OFF-NEXT:    store volatile i64 -1, i64* [[PTR]], align 4
 ; ASSUMPTIONS-OFF-NEXT:    store volatile i64 -1, i64* [[PTR]], align 4
-; ASSUMPTIONS-OFF-NEXT:    store volatile i64 3, i64* [[PTR]], align 4
+; ASSUMPTIONS-OFF-NEXT:    store volatile i64 -1, i64* [[PTR]], align 4
+; ASSUMPTIONS-OFF-NEXT:    store volatile i64 2, i64* [[PTR]], align 4
 ; ASSUMPTIONS-OFF-NEXT:    ret void
 ;
 ; ASSUMPTIONS-ON-LABEL: @caller1(
 ; ASSUMPTIONS-ON-NEXT:    br i1 [[C:%.*]], label [[TRUE1:%.*]], label [[FALSE1:%.*]]
 ; ASSUMPTIONS-ON:       true1:
-; ASSUMPTIONS-ON-NEXT:    [[C_PR:%.*]] = phi i1 [ false, [[FALSE1]] ], [ true, [[TMP0:%.*]] ]
 ; ASSUMPTIONS-ON-NEXT:    [[PTRINT:%.*]] = ptrtoint i64* [[PTR:%.*]] to i64
 ; ASSUMPTIONS-ON-NEXT:    [[MASKEDPTR:%.*]] = and i64 [[PTRINT]], 7
 ; ASSUMPTIONS-ON-NEXT:    [[MASKCOND:%.*]] = icmp eq i64 [[MASKEDPTR]], 0
 ; ASSUMPTIONS-ON-NEXT:    tail call void @llvm.assume(i1 [[MASKCOND]])
 ; ASSUMPTIONS-ON-NEXT:    store volatile i64 0, i64* [[PTR]], align 8
 ; ASSUMPTIONS-ON-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
 ; ASSUMPTIONS-ON-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
 ; ASSUMPTIONS-ON-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
 ; ASSUMPTIONS-ON-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
 ; ASSUMPTIONS-ON-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
-; ASSUMPTIONS-ON-NEXT:    br i1 [[C_PR]], label [[TRUE2:%.*]], label [[FALSE2:%.*]]
+; ASSUMPTIONS-ON-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
+; ASSUMPTIONS-ON-NEXT:    br i1 [[C]], label [[TRUE2:%.*]], label [[FALSE2:%.*]]
 ; ASSUMPTIONS-ON:       false1:
 ; ASSUMPTIONS-ON-NEXT:    store volatile i64 1, i64* [[PTR]], align 4
 ; ASSUMPTIONS-ON-NEXT:    br label [[TRUE1]]
 ; ASSUMPTIONS-ON:       true2:
 ; ASSUMPTIONS-ON-NEXT:    store volatile i64 2, i64* [[PTR]], align 8
 ; ASSUMPTIONS-ON-NEXT:    ret void
 ; ASSUMPTIONS-ON:       false2:
 ; ASSUMPTIONS-ON-NEXT:    store volatile i64 3, i64* [[PTR]], align 8
 ; ASSUMPTIONS-ON-NEXT:    ret void
 ;
   br i1 %c, label %true1, label %false1
 
 true1:
   %c2 = call i1 @callee1(i1 %c, i64* %ptr)
   store volatile i64 -1, i64* %ptr
   store volatile i64 -1, i64* %ptr
   store volatile i64 -1, i64* %ptr
   store volatile i64 -1, i64* %ptr
   store volatile i64 -1, i64* %ptr
+  store volatile i64 -1, i64* %ptr
   br i1 %c2, label %true2, label %false2
 
 false1:
   store volatile i64 1, i64* %ptr
   br label %true1
 
 true2:
   store volatile i64 2, i64* %ptr

llvm/test/Transforms/SimplifyCFG/unprofitable-pr.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -simplifycfg -S < %s | FileCheck %s
-; RUN: opt -passes=simplify-cfg -S < %s | FileCheck %s
+; RUN: opt -simplifycfg -simplifycfg-max-small-block-size=10 -S < %s | FileCheck %s
+; RUN: opt -passes=simplify-cfg -simplifycfg-max-small-block-size=10 -S < %s | FileCheck %s
 
 target datalayout = "e-p:64:64-p5:32:32-A5"
 
 declare void @llvm.assume(i1)
 
 define void @test_01(i1 %c, i64* align 1 %ptr) local_unnamed_addr #0 {
 ; CHECK-LABEL: @test_01(
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[TRUE2_CRITEDGE:%.*]], label [[FALSE1:%.*]]
true2:                                            ; preds = %true1
   store volatile i64 2, i64* %ptr, align 8
   ret void
 
 false2:                                           ; preds = %true1
   store volatile i64 3, i64* %ptr, align 8
   ret void
 }
 
-; FIXME: SimplifyCFG is doing something weird here. It should have split the
-; blocks like in the test above, but instead it creates .pr Phi node which
-; only complicates things.
+; Corner case: the block has max possible size for which we still do PRE.
 define void @test_02(i1 %c, i64* align 1 %ptr) local_unnamed_addr #0 {
 ; CHECK-LABEL: @test_02(
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[TRUE2_CRITEDGE:%.*]], label [[FALSE1:%.*]]
+; CHECK:       false1:
+; CHECK-NEXT:    store volatile i64 1, i64* [[PTR:%.*]], align 4
+; CHECK-NEXT:    [[PTRINT:%.*]] = ptrtoint i64* [[PTR]] to i64
+; CHECK-NEXT:    [[MASKEDPTR:%.*]] = and i64 [[PTRINT]], 7
+; CHECK-NEXT:    [[MASKCOND:%.*]] = icmp eq i64 [[MASKEDPTR]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[MASKCOND]])
+; CHECK-NEXT:    store volatile i64 0, i64* [[PTR]], align 8
+; CHECK-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
+; CHECK-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
+; CHECK-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
+; CHECK-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
+; CHECK-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
+; CHECK-NEXT:    store volatile i64 3, i64* [[PTR]], align 8
+; CHECK-NEXT:    ret void
+; CHECK:       true2.critedge:
+; CHECK-NEXT:    [[PTRINT_C:%.*]] = ptrtoint i64* [[PTR]] to i64
+; CHECK-NEXT:    [[MASKEDPTR_C:%.*]] = and i64 [[PTRINT_C]], 7
+; CHECK-NEXT:    [[MASKCOND_C:%.*]] = icmp eq i64 [[MASKEDPTR_C]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[MASKCOND_C]])
+; CHECK-NEXT:    store volatile i64 0, i64* [[PTR]], align 8
+; CHECK-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
+; CHECK-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
+; CHECK-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
+; CHECK-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
+; CHECK-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
+; CHECK-NEXT:    store volatile i64 2, i64* [[PTR]], align 8
+; CHECK-NEXT:    ret void
+;
+  br i1 %c, label %true1, label %false1
+
+true1:                                            ; preds = %false1, %0
+  %ptrint = ptrtoint i64* %ptr to i64
+  %maskedptr = and i64 %ptrint, 7
+  %maskcond = icmp eq i64 %maskedptr, 0
+  tail call void @llvm.assume(i1 %maskcond)
+  store volatile i64 0, i64* %ptr, align 8
+  store volatile i64 -1, i64* %ptr, align 8
+  store volatile i64 -1, i64* %ptr, align 8
+  store volatile i64 -1, i64* %ptr, align 8
+  store volatile i64 -1, i64* %ptr, align 8
+  store volatile i64 -1, i64* %ptr, align 8
+  br i1 %c, label %true2, label %false2
+
+false1:                                           ; preds = %0
+  store volatile i64 1, i64* %ptr, align 4
+  br label %true1
+
+true2:                                            ; preds = %true1
+  store volatile i64 2, i64* %ptr, align 8
+  ret void
+
+false2:                                           ; preds = %true1
+  store volatile i64 3, i64* %ptr, align 8
+  ret void
+}
+
+; This block is too huge for PRE.
+define void @test_03(i1 %c, i64* align 1 %ptr) local_unnamed_addr #0 {
+; CHECK-LABEL: @test_03(
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[TRUE1:%.*]], label [[FALSE1:%.*]]
 ; CHECK:       true1:
-; CHECK-NEXT:    [[C_PR:%.*]] = phi i1 [ [[C]], [[FALSE1]] ], [ true, [[TMP0:%.*]] ]
 ; CHECK-NEXT:    [[PTRINT:%.*]] = ptrtoint i64* [[PTR:%.*]] to i64
 ; CHECK-NEXT:    [[MASKEDPTR:%.*]] = and i64 [[PTRINT]], 7
 ; CHECK-NEXT:    [[MASKCOND:%.*]] = icmp eq i64 [[MASKEDPTR]], 0
 ; CHECK-NEXT:    tail call void @llvm.assume(i1 [[MASKCOND]])
 ; CHECK-NEXT:    store volatile i64 0, i64* [[PTR]], align 8
 ; CHECK-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
 ; CHECK-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
 ; CHECK-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
 ; CHECK-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
 ; CHECK-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
-; CHECK-NEXT:    br i1 [[C_PR]], label [[TRUE2:%.*]], label [[FALSE2:%.*]]
+; CHECK-NEXT:    store volatile i64 -1, i64* [[PTR]], align 8
+; CHECK-NEXT:    br i1 [[C]], label [[TRUE2:%.*]], label [[FALSE2:%.*]]
 ; CHECK:       false1:
 ; CHECK-NEXT:    store volatile i64 1, i64* [[PTR]], align 4
 ; CHECK-NEXT:    br label [[TRUE1]]
 ; CHECK:       true2:
 ; CHECK-NEXT:    store volatile i64 2, i64* [[PTR]], align 8
 ; CHECK-NEXT:    ret void
 ; CHECK:       false2:
 ; CHECK-NEXT:    store volatile i64 3, i64* [[PTR]], align 8
 ; CHECK-NEXT:    ret void
 ;
   br i1 %c, label %true1, label %false1
 
 true1:                                            ; preds = %false1, %0
   %ptrint = ptrtoint i64* %ptr to i64
   %maskedptr = and i64 %ptrint, 7
   %maskcond = icmp eq i64 %maskedptr, 0
   tail call void @llvm.assume(i1 %maskcond)
   store volatile i64 0, i64* %ptr, align 8
   store volatile i64 -1, i64* %ptr, align 8
   store volatile i64 -1, i64* %ptr, align 8
   store volatile i64 -1, i64* %ptr, align 8
   store volatile i64 -1, i64* %ptr, align 8
   store volatile i64 -1, i64* %ptr, align 8
+  store volatile i64 -1, i64* %ptr, align 8
   br i1 %c, label %true2, label %false2
 
 false1:                                           ; preds = %0
   store volatile i64 1, i64* %ptr, align 4
   br label %true1
 
 true2:                                            ; preds = %true1
   store volatile i64 2, i64* %ptr, align 8
   ret void
 
 false2:                                           ; preds = %true1
   store volatile i64 3, i64* %ptr, align 8
   ret void
 }