[SimplifyCFG] Trim duplicate basic blocks in switch cases

[dylanmckay]

Summary

Adds a case to SimplifyCFG which checks for switch case basic blocks
that are identical and prunes them.

This breaks several tests which I am not sure how to fix.

Broken tests:

LLVM :: CodeGen/AArch64/arm64-jumptable.ll
LLVM :: CodeGen/ARM/jump-table-islands-split.ll
LLVM :: Transforms/SimplifyCFG/CoveredLookupTable.ll
LLVM :: Transforms/SimplifyCFG/X86/switch-table-bug.ll
LLVM :: Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll

X86/switch_to_lookup_table.ll is trivial to fix.

Motivated by Rust issue #26496.
Fixes LLVM bug 24220.

CC'ing Phillip because he filed the Bugzilla bug.

Adding Renato and Tim as this breaks ARM and AArch64 tests.

[t.p.northover]

I think it's a side-effect of the CFG-tidying AArch64 and ARM do after expanding atomic accesses. I'd suggest passing "-aarch64-atomic-cfg-tidy=false" and "-arm-atomic-cfg-tidy=false" at the top of each test. It's irrelevant to what they're actually trying to do.

BTW, llvm-commits isn't a subscriber here yet. Is that intentional?

[sanjoy]

lib/Transforms/Utils/SimplifyCFG.cpp

3404

Should this live as BasicBlock::isIdenticalTo?

3407

Nit: no braces needed here.

3416

No braces needed here.

3425

I'd change the assert's message to We should've handled this case earlier. and remove the comment.

3462

Don't you need to adjust PHI nodes in CurSuccessor, since it now has a new incoming block?

[dylanmckay]

Added flags to ARM and AArch64 tests as suggested by Tim - this fixes the tests.

Added a hidden command line parameter to disable duplicate basic block merging. This fixes the two broken X86 tests, which were trivially broken due to basic block renaming. This also fixes CoveredLookupTable.ll for the same reason.

• Moved basic block comparison into a method on BasicBlock
• Removed redundant braces
• Changed assert message

[dylanmckay]

lib/Transforms/Utils/SimplifyCFG.cpp

3461

Does it really have a new incoming block? The block that contains the switch statement will still be the successor because all case statements are apart of the same basic block?

It is highly likely that I am misunderstanding, however.

[dylanmckay]

Note that all tests are fixed now - Tim's suggestion fixed the ARM and AArch64 tests.

The X86 tests and CoveredLookupTable.ll were broken solely because they assumed the names of the successors did not change. This is irrelevant to the test, so I simply disabled duplicate block merging for them.

[sanjoy]

include/llvm/IR/BasicBlock.h

318

Prefix the sentence with a \brief like in the other methods.

lib/IR/BasicBlock.cpp

453

Nit: spacing.

lib/Transforms/Utils/SimplifyCFG.cpp

3411

Why do you need AC and DL?

3461

PHI nodes have to have an entry for each incoming edge -- if multiple
edges come from the same predecessor then you need multiple entries in
the PHI node for that predecessor (all of which should have the same
incoming value).

So if you start with

declare void @foo()

define void @main(i1 %c) {
 entry:
  br i1 %c, label %match_case2, label %sw

 sw:
  %value = alloca i32
  store i32 5, i32* %value
  %val = load i32, i32* %value
  
  switch i32 %val, label %join [
    i32 1, label %match_case
    i32 48, label %match_case1
    i32 92, label %match_case2
    i32 23, label %match_case3
  ]

match_case:
  call void @foo()
  unreachable

match_case1:
  call void @foo()
  unreachable

match_case2:
  %x = phi i32 [ 10, %entry ], [ 20, %sw ]
  call void @foo()
  unreachable

match_case3:
  call void @foo()
  unreachable

join:
  ret void
}

transforming it to

declare void @foo()

define void @main(i1 %c) {
 entry:
  br i1 %c, label %match_case2, label %sw

 sw:
  %value = alloca i32
  store i32 5, i32* %value
  %val = load i32, i32* %value
  
  switch i32 %val, label %join [
    i32 1, label %match_case
    i32 48, label %match_case1
    i32 92, label %match_case2
    i32 23, label %match_case2 ;; change here
  ]

match_case:
  call void @foo()
  unreachable

match_case1:
  call void @foo()
  unreachable

match_case2:
  %x = phi i32 [ 10, %entry ], [ 20, %sw ]
  call void @foo()
  unreachable

match_case3:
  call void @foo()
  unreachable

join:
  ret void
}

is incorrect (i.e. you'll fail verification) -- you also need to update %x to be phi i32 [ 10, %entry ], [ 20, %sw ], [ 20, %sw ].

[dylanmckay]

Removed unused type parameters.

They were remnants from a copy-paste of another type signature.

[dylanmckay]

include/llvm/IR/BasicBlock.h

318

The AUTOBRIEF Doxygen option was enabled a few months ago - this is no longer necessary and presents visual noise.

I will however add it if you think consistency is worth it.

[sanjoy]

include/llvm/IR/BasicBlock.h

318

this is no longer necessary and presents visual noise.

SGTM (i.e. it is fine to not add \brief).

[reames]

A couple of minor comments.

Have you thought about approaching this as prefix merging? If you found two successors with identical prefixes, it might be worth merging them and inserting a branch at the end to distinguish between the distinct suffixes. This would subsume your current optimization. I'm not suggesting you drop this and do that instead, but it might be an interesting follow on depending on what you actual code patterns are.

lib/IR/BasicBlock.cpp

435

I suspect this pattern already exists elsewhere in SimplifyCFG. I'd encourage you to submit a refactoring to extract it separately. I won't requite this.

Adding a maximum instructions paramater might make this more useful. (i.e. is identical to, but conservative if longer than N instructions.)

437

I believe this is a linear search implementation. (i.e. this saves nothing and is strictly extra work.)

440

Cursor1? Cur is a not a common name in LLVM. I have seen Itr used which would convey the same intent.

448

This *looks* like it will walk off the end of BB 2 if it is shorter than the this. The isIdenticalTo check should fail first since instructions won't match, but please add an assert to make this obvious.

lib/Transforms/Utils/SimplifyCFG.cpp

3432

I'm worried about large basic blocks here. Possibly cap this around 20-30 instructions?

3434

Do you need to notify the other successor this block is no longer a predecessor? PHI updates, etc?

4457

I wouldn't bother with the option.

[dylanmckay]

Phillip's idea is a good one - it would be fairly easy to generalize this optimization so that it performes "prefix merging".

Do you think the new optimization should still live in SimplifyCFG? One problem with keeping it in SimplifyCFG is that block merging will interfere with tests even worse than with this patch (which is why the current patch adds a command line option to disable merging), causing them to wonder "where has my basic block gone?".

If the patch were to be split into a separate pass, it would be quite a small pass which would be overkill. Perhaps it would be better to keep the optimization in SimplifyCFG and keep the command line option for testing purposes.

Thoughts?

lib/Transforms/Utils/SimplifyCFG.cpp

3461

I understand this now - thanks for the explanation Sanjoy!

[reames]

If you decide to go forward with the prefix matching, SimplifyCFG is
absolutely the right place. I'm really bothered by the fact that target
specific tests are sensitive to a target independent transform pass at
all. I didn't follow that part of the review, but any way we can fix
that? Working around it further by introducing a new pass is definitely
not something we should do.

Philip

[dylanmckay]

The problem is that they are doing something akin to this:

define void @foo() {
    switch i32 %val, label %join [
        ; CHECK_NEXT: match_1
        i32 1, label %match_1
        ; CHECK_NEXT: match_2
        i32 2, label %match_2
        ; CHECK_NEXT: match_3
        i32 3, label %match_3
    ]
    match_1: br label %join
    match_2: br label %join
    match_3: br label %join

    join:
        ret void
}

They are hardcoding names of basic blocks, which this optimization mangles, so for example, all match arms would be optimized to match_1.

We could use LIT's regexps to fix this (that's my only idea) - there are only three tests which fail because of this:

LLVM :: Transforms/SimplifyCFG/CoveredLookupTable.ll
LLVM :: Transforms/SimplifyCFG/X86/switch-table-bug.ll
LLVM :: Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll

[dylanmckay]

Upon further reflection, I believe regular expressions are the best choice (as the x86 tests shouldn't care about the names of basic blocks - they should only care that i.e. the switch statements are converted to selects).

I will fix the tests properly, remove the extraneous command line param, generalise to a basic block prefix merge optimisation and open a new diff once this is done.

Thanks for the reviews Sanjoy and Phillip, I will make sure to address all points in the next patch.

[dylanmckay]

I’m not sure if the prefix merging is possible - I’ve got it to the point
where SimplifyCFG recognizes common instructions in the basic block head,
factors it into a separate block, which is then directly branched to by the
switch instruction.

The problem is that a branch to the different tails needs to be made via a
PHI node. Using this, there needs to be distinct predecessors in order to
differentiate between the two head blocks. Of course, the problem is that
both code paths into the common block come from a single switch statement
in a single basic block.

In code (after the block prefix has been factored out).

declare void @foo();

define void @main() {
entry:

switch i32 %1, label %join [

    i32 1, label %common_head
    i32 2, label %common_head
]

; the factored out head common to tail1 and tail2
common_head:

call void foo()
; SEE HERE: How to distinguish between branches from same basic block
%label_to = phi label [%tail1, %entry], [%tail2, %entry]
br %label_to

tail1: unreachable ; stub
tail2: unreachable ; stub

join:

ret void

}

Am I missing something?
​

[dylanmckay]

Ping.

include/llvm/IR/BasicBlock.h

public:
   /// Being a ``landing pad'' means that the basic block is the destination of
   /// the 'unwind' edge of an invoke instruction.
   bool isLandingPad() const;
 
   /// \brief Return the landingpad instruction associated with the landing pad.
   LandingPadInst *getLandingPadInst();
   const LandingPadInst *getLandingPadInst() const;
 
+  /// Checks if the bodies of two basic blocks are identical.
+  bool isIdenticalTo(const BasicBlock &Other) const;
+
 private:
   /// \brief Increment the internal refcount of the number of BlockAddresses
   /// referencing this BasicBlock by \p Amt.
   ///
   /// This is almost always 0, sometimes one possibly, but almost never 2, and
   /// inconceivably 3 or more.
   void AdjustBlockAddressRefCount(int Amt) {
     setValueSubclassData(getSubclassDataFromValue()+Amt);

lib/IR/BasicBlock.cpp

 
 /// Return the landingpad instruction associated with the landing pad.
 LandingPadInst *BasicBlock::getLandingPadInst() {
   return dyn_cast<LandingPadInst>(getFirstNonPHI());
 }
 const LandingPadInst *BasicBlock::getLandingPadInst() const {
   return dyn_cast<LandingPadInst>(getFirstNonPHI());
 }
+
+bool BasicBlock::isIdenticalTo(const BasicBlock &Other) const {
+  // Two blocks cannot be equivalent if they are different sizes.
+  if (this->size() != Other.size())
+    return false;
+
+  auto Cur1 = this->begin();
+  auto Cur2 = Other.begin();
+
+  while(Cur1 != this->end()) {
+
+    if (!(*Cur1).isIdenticalTo(&*Cur2))
+      return false;
+
+    ++Cur1;
+    ++Cur2;
+  }
+
+  assert(Cur1 == this->end() && Cur2 == Other.end() &&
+      "we should've handled this earlier");
+
+  return true;
+}

lib/Transforms/Utils/SimplifyCFG.cpp

 static cl::opt<bool>
 SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true),
        cl::desc("Sink common instructions down to the end block"));
 
 static cl::opt<bool> HoistCondStores(
     "simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true),
     cl::desc("Hoist conditional stores if an unconditional store precedes"));
 
+static cl::opt<bool> KeepDuplicateBlocks(
+    "simplifycfg-keep-duplicate-blocks", cl::Hidden, cl::init(false),
+    cl::desc("Keep duplicated switch case basic blocks"));
+
 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)");
 STATISTIC(NumTableCmpReuses, "Number of reused switch table lookup compares");
 STATISTIC(NumSinkCommons, "Number of common instructions sunk down to the end block");
 STATISTIC(NumSpeculations, "Number of speculative executed instructions");
 
if (HasWeight && Weights.size() >= 2) {
     SI->setMetadata(LLVMContext::MD_prof,
                     MDBuilder(SI->getParent()->getContext()).
                     createBranchWeights(MDWeights));
   }
 
   return !DeadCases.empty();
 }
 
+/// Attempts to remove redundant duplicate case successors.
+///
+/// We only check adjacent case values because they are the most
+/// likely to be the same in real-world code, and it avoids the
+/// O(n^2) complexity of checking every case.
+///
+/// Returns `true` if the instruction was modified.
+static bool EliminateDuplicateSwitchSuccessors(SwitchInst *SI) {
+
+  // We don't care if the switch has one case.
+  if (SI->getNumCases() <= 1)
+    return false;
+
+  SwitchInst::CaseIt I = SI->case_begin(), E = SI->case_end();
+
+  // Loop for every case.
+  while(1) {
+
+    BasicBlock *CurSuccessor = I.getCaseSuccessor();
+    ++I;
+
+    // Check if we finished iteration.
+    if (I == E)
+      break;
+
+    BasicBlock *NextSuccessor = I.getCaseSuccessor();
+
+    // If the basic blocks are identical, we can remove one because
+    // it is redundant.
+    if (CurSuccessor->isIdenticalTo(*NextSuccessor)) {
+        // Throw away one of the successors.
+        I.setSuccessor(CurSuccessor);
+    }
+  }
+
+  return false;
+}
+
 /// If BB would be eligible for simplification by
 /// TryToSimplifyUncondBranchFromEmptyBlock (i.e. it is empty and terminated
 /// by an unconditional branch), look at the phi node for BB in the successor
 /// block and see if the incoming value is equal to CaseValue. If so, return
 /// the phi node, and set PhiIndex to BB's index in the phi node.
 static PHINode *FindPHIForConditionForwarding(ConstantInt *CaseValue,
                                               BasicBlock *BB,
                                               int *PhiIndex) {
   if (BB->getFirstNonPHIOrDbg() != BB->getTerminator())
     return nullptr; // BB must be empty to be a candidate for simplification.
   if (!BB->getSinglePredecessor())
     return nullptr; // BB must be dominated by the switch.
 
   BranchInst *Branch = dyn_cast<BranchInst>(BB->getTerminator());
   if (!Branch || !Branch->isUnconditional())
     return nullptr; // Terminator must be unconditional branch.
 
   BasicBlock *Succ = Branch->getSuccessor(0);
 
   BasicBlock::iterator I = Succ->begin();
   while (PHINode *PHI = dyn_cast<PHINode>(I++)) {
     int Idx = PHI->getBasicBlockIndex(BB);
     assert(Idx >= 0 && "PHI has no entry for predecessor?");
 
     Value *InValue = PHI->getIncomingValue(Idx);
     if (InValue != CaseValue) continue;
 
     *PhiIndex = Idx;
     return PHI;
   }
if (EliminateDeadSwitchCases(SI, AC, DL))
     return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
 
   if (SwitchToSelect(SI, Builder, AC, DL))
     return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
 
   if (ForwardSwitchConditionToPHI(SI))
     return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
 
+  if (!KeepDuplicateBlocks && EliminateDuplicateSwitchSuccessors(SI))
+    return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
+
   if (SwitchToLookupTable(SI, Builder, DL, TTI))
     return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true;
 
   return false;
 }
 
 bool SimplifyCFGOpt::SimplifyIndirectBr(IndirectBrInst *IBI) {
   BasicBlock *BB = IBI->getParent();

test/CodeGen/AArch64/arm64-jumptable.ll

-; RUN: llc -mtriple=arm64-apple-ios < %s | FileCheck %s
-; RUN: llc -mtriple=arm64-linux-gnu < %s | FileCheck %s --check-prefix=CHECK-LINUX
+; RUN: llc -mtriple=arm64-apple-ios -aarch64-atomic-cfg-tidy=false < %s | FileCheck %s
+; RUN: llc -mtriple=arm64-linux-gnu -aarch64-atomic-cfg-tidy=false < %s | FileCheck %s --check-prefix=CHECK-LINUX
 ; <rdar://11417675>
 
 define void @sum(i32* %to) {
 entry:
   switch i32 undef, label %exit [
     i32 1, label %bb1
     i32 2, label %bb2
     i32 3, label %bb3

test/CodeGen/ARM/jump-table-islands-split.ll

-; RUN: llc -mtriple=thumbv7s-apple-ios8.0 -o - %s | FileCheck %s
+; RUN: llc -mtriple=thumbv7s-apple-ios8.0 -arm-atomic-cfg-tidy=false -o - %s | FileCheck %s
 
 declare void @foo(double)
 declare i32 @llvm.arm.space(i32, i32)
 
 ; The constpool entry used to call @foo should be directly between where we want
 ; the tbb and its table. Fortunately, the flow is simple enough that we can
 ; eliminate the entry calculation (ADD) and use the ADR as the base.
 ;

test/Transforms/SimplifyCFG/CoveredLookupTable.ll

-; RUN: opt -simplifycfg -S %s | FileCheck %s
+; RUN: opt -simplifycfg -S %s -simplifycfg-keep-duplicate-blocks | FileCheck %s
 ; rdar://15268442
 
 target datalayout = "e-p:64:64:64-S128-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f16:16:16-f32:32:32-f64:64:64-f128:128:128-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 target triple = "x86_64-apple-darwin12.0.0"
 
 ; CHECK-LABEL: define i3 @coveredswitch_test(
 ; CHECK: entry:
 ; CHECK-NEXT: sub i3 %input, -4

test/Transforms/SimplifyCFG/X86/switch-table-bug.ll

-; RUN: opt -S -simplifycfg < %s -mtriple=x86_64-apple-darwin12.0.0 | FileCheck %s
+; RUN: opt -S -simplifycfg < %s -mtriple=x86_64-apple-darwin12.0.0 -simplifycfg-keep-duplicate-blocks | FileCheck %s
 ; rdar://17735071
 target datalayout = "e-p:64:64:64-S128-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f16:16:16-f32:32:32-f64:64:64-f128:128:128-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 target triple = "x86_64-apple-darwin12.0.0"
 
 ; When tableindex can't fit into i2, we should extend the type to i3.
 ; CHECK-LABEL: @_TFO6reduce1E5toRawfS0_FT_Si
 ; CHECK: entry:
 ; CHECK-NEXT: sub i2 %0, -2

test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll

-; RUN: opt < %s -simplifycfg -S -mtriple=x86_64-unknown-linux-gnu | FileCheck %s
+; RUN: opt < %s -simplifycfg -S -mtriple=x86_64-unknown-linux-gnu -simplifycfg-keep-duplicate-blocks | FileCheck %s
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; The table for @f
 ; CHECK: @switch.table = private unnamed_addr constant [7 x i32] [i32 55, i32 123, i32 0, i32 -1, i32 27, i32 62, i32 1]
 
 ; The float table for @h

test/Transforms/SimplifyCFG/switch-duplicate-successors.ll

+; RUN: opt %s -S -simplifycfg | FileCheck %s
+
+declare void @foo()
+
+; This test checks that SimplifyCFG correctly recognizes
+; that switch arms point to duplicate basic blocks, and
+; removes references to all all unneeded blocks.
+define void @main() {
+; CHECK-LABEL: @main
+
+; CHECK: switch i32 %1, label %join [
+
+; CHECK-NEXT: i32 1, label %match_case
+; CHECK-NEXT: i32 48, label %match_case
+; CHECK-NEXT: i32 92, label %match_case
+; CHECK-NEXT: i32 23, label %match_case
+; CHECK-NEXT: i32 4, label %match_case
+; CHECK-NEXT: i32 70, label %match_case
+; CHECK-NEXT: i32 29, label %match_case
+; CHECK-NEXT: i32 36, label %match_case
+; CHECK-NEXT: i32 34, label %match_case
+; CHECK-NEXT: i32 58, label %match_case
+
+  %value = alloca i32
+  store i32 5, i32* %value
+  %1 = load i32, i32* %value
+  
+  switch i32 %1, label %join [
+    i32 1, label %match_case
+    i32 48, label %match_case1
+    i32 92, label %match_case2
+    i32 23, label %match_case3
+    i32 4, label %match_case4
+    i32 70, label %match_case5
+    i32 29, label %match_case6
+    i32 36, label %match_case7
+    i32 34, label %match_case8
+    i32 58, label %match_case9
+  ]
+
+match_case:
+  call void @foo()
+  unreachable
+
+match_case1:
+  call void @foo()
+  unreachable
+
+match_case2:
+  call void @foo()
+  unreachable
+
+match_case3:
+  call void @foo()
+  unreachable
+
+match_case4:
+  call void @foo()
+  unreachable
+
+match_case5:
+  call void @foo()
+  unreachable
+
+match_case6:
+  call void @foo()
+  unreachable
+
+match_case7:
+  call void @foo()
+  unreachable
+
+match_case8:
+  call void @foo()
+  unreachable
+
+match_case9:
+  call void @foo()
+  unreachable
+
+join:
+  ret void
+}
+