[MergeICmp] We can discard initial blocks that do other work

[trentxintong]

Summary

We can discard initial blocks that do other work
We do not need to limit ourselves to just the first block in the chain.

[davide]

This looks correct to me but please wait for Clement's opinion on it.

[courbet]

LGTM. This is a better approach than my r324341 :)

llvm/trunk/lib/Transforms/Scalar/MergeICmps.cpp

for (size_t BlockIdx = 0; BlockIdx < Blocks.size(); ++BlockIdx) {
     Comparison.BB = Block;
     if (!Comparison.IsValid()) {
       DEBUG(dbgs() << "skip: not a valid BCECmpBlock\n");
       return;
     }
     if (Comparison.doesOtherWork()) {
       DEBUG(dbgs() << "block '" << Comparison.BB->getName()
                    << "' does extra work besides compare\n");
-      if (BlockIdx == 0) {  // First block.
-        // TODO(courbet): The first block can do other things, and we should
+      if (Comparisons.empty()) {
+        // TODO(courbet): The initial block can do other things, and we should
         // split them apart in a separate block before the comparison chain.
         // Right now we just discard it and make the chain shorter.
         DEBUG(dbgs()
               << "ignoring first block '" << Comparison.BB->getName()
               << "' that does extra work besides compare\n");
         continue;
       }
       // TODO(courbet): Right now we abort the whole chain. We could be
for (size_t BlockIdx = 0; BlockIdx < Blocks.size(); ++BlockIdx) {
     DEBUG(dbgs() << "Block '" << Comparison.BB->getName()<< "': Found cmp of "
                  << Comparison.SizeBits() << " bits between "
                  << Comparison.Lhs().Base() << " + " << Comparison.Lhs().Offset
                  << " and " << Comparison.Rhs().Base() << " + "
                  << Comparison.Rhs().Offset << "\n");
     DEBUG(dbgs() << "\n");
     Comparisons.push_back(Comparison);
   }
-  assert(!Comparisons.empty() && "chain with no BCE basic blocks");
+
+  // It is possible we have no suitable comparison to merge.
+  if (Comparisons.empty()) {
+    DEBUG(dbgs() << "chain with no BCE basic blocks, no merge\n");
+    return;
+  }
   EntryBlock_ = Comparisons[0].BB;
   Comparisons_ = std::move(Comparisons);
 #ifdef MERGEICMPS_DOT_ON
   errs() << "BEFORE REORDERING:\n\n";
   dump();
 #endif  // MERGEICMPS_DOT_ON
   // Reorder blocks by LHS. We can do that without changing the
   // semantics because we are only accessing dereferencable memory.

llvm/trunk/test/Transforms/MergeICmps/X86/multiple-blocks-does-work.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -mergeicmps -mtriple=x86_64-unknown-unknown -S | FileCheck %s --check-prefix=X86
+
+%"struct.std::pair" = type { i32, i32, i32, i32 }
+
+declare void @foo(...)
+
+; We can discard %entry and %land.rhs.i, but still merge the last 2 blocks.
+define zeroext i1 @opeq1(
+; X86-LABEL: @opeq1(
+; X86:      land.rhs.i.2:
+; X86-NEXT:    [[THIRD_I:%.*]] = getelementptr inbounds %"struct.std::pair", %"struct.std::pair"* [[A:%.*]], i64 0, i32 2 
+; X86-NEXT:    [[THIRD1_I:%.*]] = getelementptr inbounds %"struct.std::pair", %"struct.std::pair"* [[B:%.*]], i64 0, i32 2
+; X86-NEXT:    [[CSTR:%.*]] = bitcast i32* [[THIRD_I]] to i8*
+; X86-NEXT:    [[CSTR1:%.*]] = bitcast i32* [[THIRD1_I]] to i8*
+; X86-NEXT:    [[MEMCMP:%.*]] = call i32 @memcmp(i8* [[CSTR]], i8* [[CSTR1]], i64 8)
+; X86-NEXT:    [[TMP0:%.*]] = icmp eq i32 [[MEMCMP]], 0
+; X86-NEXT:    br label [[OPEQ1_EXIT:%.*]]
+; X86:       opeq1.exit:
+; X86-NEXT:    [[TMP1:%.*]] = phi i1 [ false, %entry ], [ false, %land.rhs.i ], [ [[TMP0]], %land.rhs.i.2 ] 
+; X86-NEXT:    ret i1 [[TMP1]]
+;
+  %"struct.std::pair"* nocapture readonly dereferenceable(16) %a,
+  %"struct.std::pair"* nocapture readonly dereferenceable(16) %b) local_unnamed_addr #0 {
+entry:
+  %first.i = getelementptr inbounds %"struct.std::pair", %"struct.std::pair"* %a, i64 0, i32 0
+  %0 = load i32, i32* %first.i, align 4
+  %first1.i = getelementptr inbounds %"struct.std::pair", %"struct.std::pair"* %b, i64 0, i32 0
+  %1 = load i32, i32* %first1.i, align 4
+  ; Does other work.
+  call void (...) @foo()
+  %cmp.i = icmp eq i32 %0, %1
+  br i1 %cmp.i, label %land.rhs.i, label %opeq1.exit
+
+land.rhs.i:
+  %second.i = getelementptr inbounds %"struct.std::pair", %"struct.std::pair"* %a, i64 0, i32 1
+  %2 = load i32, i32* %second.i, align 4
+  %second2.i = getelementptr inbounds %"struct.std::pair", %"struct.std::pair"* %b, i64 0, i32 1
+  %3 = load i32, i32* %second2.i, align 4
+  ; Does other work.
+  call void (...) @foo()
+  %cmp2.i = icmp eq i32 %2, %3
+  br i1 %cmp2.i, label %land.rhs.i.2, label %opeq1.exit
+
+land.rhs.i.2:
+  %third.i = getelementptr inbounds %"struct.std::pair", %"struct.std::pair"* %a, i64 0, i32 2 
+  %4 = load i32, i32* %third.i, align 4
+  %third2.i = getelementptr inbounds %"struct.std::pair", %"struct.std::pair"* %b, i64 0, i32 2
+  %5 = load i32, i32* %third2.i, align 4
+  %cmp3.i = icmp eq i32 %4, %5
+  br i1 %cmp3.i, label %land.rhs.i.3, label %opeq1.exit
+
+land.rhs.i.3:
+  %fourth.i = getelementptr inbounds %"struct.std::pair", %"struct.std::pair"* %a, i64 0, i32 3
+  %6 = load i32, i32* %fourth.i, align 4
+  %fourth2.i = getelementptr inbounds %"struct.std::pair", %"struct.std::pair"* %b, i64 0, i32 3
+  %7 = load i32, i32* %fourth2.i, align 4
+  %cmp4.i = icmp eq i32 %6, %7
+  br label %opeq1.exit
+
+opeq1.exit:
+  %8 = phi i1 [ false, %entry ], [ false, %land.rhs.i] , [ false, %land.rhs.i.2 ], [ %cmp4.i, %land.rhs.i.3 ]
+  ret i1 %8
+}