[MergeICmp] Split blocks that do other work.

[trentxintong]

Summary

We do not try to move the instructions and split the block till we
know the blocks can be split, i.e. BCE-cmp-insts can be separated from
non-BCE-cmp-insts.

[trentxintong]

Add a DEBUG msg.

[trentxintong]

Update comment in a test

[trentxintong]

Friendly Ping.

[courbet]

Thanks a lot for the patch.

lib/Transforms/Scalar/MergeICmps.cpp

147

Typo: extra "this".

153

Typo: Additionally.

171

Typo: side effects.

359

This will unconditionally split the block even if any subsequent condition for merging fails. This has following issues:

• The pass will modify code even when it does nothing.
• The splitting is not accounted for in the value returned by simplify(), so the analysis pass might not be correctly invalidated if we later decide to do nothing.

To fix this, you could add the block to the chain with a tag and do the actual splitting in simplify().

For the first point: What about adding a test with a single splittable block and check that the pass introduces no changes ?

[trentxintong]

lib/Transforms/Scalar/MergeICmps.cpp

359

Actually tryToSplitBCECmpBlock will not move instructions around if it can not split the block. i.e. it first tests whether all non-bce-cmp instructions can be separated from bce-cmp instructions.

The way I think about the problem is that we have a chain and within the chain there may be blocks that do work other than the BCE compare which stops us from collapsing the chain into a memcmp. This block can be the first block of the chain or in middle of the chain.

In case its the first block in the chain, we can choose to split it (or discard it in case we can not split it), which is what we do with this patch. NOTE: the way split is done will not affect what is recorded in BCECmpBlock. More specifically, a new block is created and all the non-bce-cmp instructions are moved to the new BB. The old BB stays what it is as far as bce-cmp instructions are concerned.

In case its in middle of the chain, its a bit more complicated, we need to terminate the chain, process what has been collected and restart anew (This has not been implemented, but i can see how we can implement this even with this patch. i.e. we can break out of the loop and process what has been collected. Then try to rerun the chain collecting/collapsing process again on the modified IR).

[courbet]

lib/Transforms/Scalar/MergeICmps.cpp

359

Sure, I understand what this fixes and I think it's worth fixing.
My point was that I don't think that we should eagerly split the first block if is can be split, but we should first collect this block along with other "normal" BCECmp blocks, and split it only when we know that the chain itself is mergeable (in simplify). Otherwise we might split a block just to realize later that the chain was not actually mergeable, in which case we've done useless work for nothing. That's why I was suggesting adding a test with a single block (i.e. a non-mergeable chain), to check that the pass would do nothing to it.

[trentxintong]

lib/Transforms/Scalar/MergeICmps.cpp

359

Make sense. Let me do that.

[trentxintong]

Address comment.

[trentxintong]

Update an assert.

[trentxintong]

Simplify how split instructions are moved.

[trentxintong]

Update checks in a test case.

[trentxintong]

@courbet Ping. Thanks

[courbet]

Thanks, only stylistic comments left.

lib/Transforms/Scalar/MergeICmps.cpp

112

Add: "The block might do extra work besides the atom comparison, in which case doesOtherWork() returns true. Under some conditions, the block can be split into the atom comparison part and the "other work" part (see couldSplit()).

149

canSplit() ?

160

style: the function should start with lowercase.

160

I think you can call that just split() given that this is a member function of BCECmpBlock.

504

nit: C->splitBCECmpBlock() ?

test/Transforms/MergeICmps/X86/tuple-four-int8.ll

23

The comment is not very clear. Maybe something like:
"This is merged into a 3-byte memcmp for blocks land.elem1, land.elem2 and entry (the latter being split in the cmp part and the address computation part), and an extra 1-byte compare for land.elem0."

[trentxintong]

Address stylistic comments.

lib/Transforms/Scalar/MergeICmps.cpp

if (auto *const GEP = dyn_cast<GetElementPtrInst>(Addr)) {
         Result.GEP = GEP;
         Result.LoadI = LoadI;
       }
     }
   }
   return Result;
 }
 
 // A basic block with a comparison between two BCE atoms.
 // Note: the terminology is misleading: the comparison is symmetric, so there
 // is no real {l/r}hs. What we want though is to have the same base on the
 // left (resp. right), so that we can detect consecutive loads. To ensure this
 // we put the smallest atom on the left.
 class BCECmpBlock {
  public:
   BCECmpBlock() {}
 
public:
 
   const BCEAtom &Lhs() const { return Lhs_; }
   const BCEAtom &Rhs() const { return Rhs_; }
   int SizeBits() const { return SizeBits_; }
 
   // Returns true if the block does other works besides comparison.
   bool doesOtherWork() const;
 
+  // Return true if this all the relevant instructions in the BCE cmp block can
+  // be sunk below this instruction. By doing this, we know we can separate the
+  // BCE-cmp-block instructions with the non-BCE-cmp-block instructions.
+  bool canSinkBCECmpInst(const Instruction *, DenseSet<Instruction *> &) const;
+
+  // Return true if we can separate the BCE cmp insts and the non-BCE cmp
+  // insts. Additonally, split the old block. False otherwise.
+  bool tryToSplitBCECmpBlock();
+
   // The basic block where this comparison happens.
   BasicBlock *BB = nullptr;
   // The ICMP for this comparison.
   ICmpInst *CmpI = nullptr;
   // The terminating branch.
   BranchInst *BranchI = nullptr;
 
  private:
   BCEAtom Lhs_;
   BCEAtom Rhs_;
   int SizeBits_ = 0;
 };
 
+bool BCECmpBlock::canSinkBCECmpInst(const Instruction *Inst,
+                                    DenseSet<Instruction *> &BlockInsts) const {
+  // If this instruction has side effect and its in middle of the BCE cmp block
+  // instructions, then bail for now.
+  // TODO: use alias analysis to tell whether there is real interference.
+  if (Inst->mayHaveSideEffects())
+    return false;
+  // Make sure this instruction does not use any of the BCE cmp block
+  // instructions as operand.
+  for (auto BI : BlockInsts) {
+    if (is_contained(Inst->operands(), BI))
+      return false;
+  }
+  return true;
+}
+
+bool BCECmpBlock::tryToSplitBCECmpBlock() {
+  DenseSet<Instruction *> BlockInsts(
+      {Lhs_.GEP, Rhs_.GEP, Lhs_.LoadI, Rhs_.LoadI, CmpI, BranchI});
+  llvm::SmallVector<Instruction *, 4> OtherInsts;
+  for (Instruction &Inst : *BB) {
+    if (!BlockInsts.count(&Inst)) {
+      if (!canSinkBCECmpInst(&Inst, BlockInsts))
+        return false;
+      // This is a non-BCE-cmp-block instruction. And it can be separated
+      // from the BCE-cmp-block instruction.
+      OtherInsts.push_back(&Inst);
+    }
+  }
+
+  // Do the actual spliting.
+  BasicBlock *NBB =
+      BasicBlock::Create(BB->getContext(), "", BB->getParent(), BB);
+  BranchInst::Create(BB, NBB);
+  for (Instruction *Inst : OtherInsts) {
+    Inst->moveBefore(NBB->getTerminator());
+  }
+
+  return true;
+}
+
 bool BCECmpBlock::doesOtherWork() const {
   AssertConsistent();
   // All the instructions we care about in the BCE cmp block.
   DenseSet<Instruction *> BlockInsts(
       {Lhs_.GEP, Rhs_.GEP, Lhs_.LoadI, Rhs_.LoadI, CmpI, BranchI});
   // TODO(courbet): Can we allow some other things ? This is very conservative.
   // We might be able to get away with anything does does not have any side
   // effects outside of the basic block.
auto Result = visitICmp(
         CmpI, FalseBlock == PhiBlock ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE);
     Result.CmpI = CmpI;
     Result.BranchI = BranchI;
     return Result;
   }
   return {};
 }
 
+static inline void enqueueBlock(std::vector<BCECmpBlock> &Comparisons,
+                                BCECmpBlock &Comparison) {
+  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);
+}
+
 // A chain of comparisons.
 class BCECmpChain {
  public:
   BCECmpChain(const std::vector<BasicBlock *> &Blocks, PHINode &Phi);
 
   int size() const { return Comparisons_.size(); }
 
 #ifdef MERGEICMPS_DOT_ON
for (size_t BlockIdx = 0; BlockIdx < Blocks.size(); ++BlockIdx) {
     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 (Comparisons.empty()) {
-        // TODO(courbet): The initial block can do other things, and we should
+        // This is the initial block in the chain, in case this block does other
+        // work, we try to split the block.
+        //
+        // If this is not the initial block in the chain, splitting it wont
+        // work.
+        //
+        // As once split, there will still be instructions before the BCE cmp
+        // instructions that do other work, i.e. within the chain. Unless
+        // we can abort the chain at this point and start anew.
+        if (Comparison.tryToSplitBCECmpBlock()) {
+          enqueueBlock(Comparisons, Comparison);
+        } else {
+          // 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 initial block '" << Comparison.BB->getName()
+          DEBUG(dbgs() << "ignoring initial block '" << Comparison.BB->getName()
                        << "' that does extra work besides compare\n");
+        }
         continue;
       }
       // TODO(courbet): Right now we abort the whole chain. We could be
       // merging only the blocks that don't do other work and resume the
       // chain from there. For example:
       //  if (a[0] == b[0]) {  // bb1
       //    if (a[1] == b[1]) {  // bb2
       //      some_value = 3; //bb3
if (Comparison.doesOtherWork()) {
       //    \            \           \               v
       //     +------------+-----------+----------> bb_phi
       //
       // We can only merge the first two comparisons, because bb3* does
       // "other work" (setting some_value to 3).
       // We could still merge bb1 and bb2 though.
       return;
     }
-    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);
+    enqueueBlock(Comparisons, Comparison);
   }
 
   // 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;
void BCECmpChain::mergeComparisons(ArrayRef<BCECmpBlock> Comparisons,
 
   if (Comparisons.size() >= 2) {
     DEBUG(dbgs() << "Merging " << Comparisons.size() << " comparisons\n");
     const auto TotalSize =
         std::accumulate(Comparisons.begin(), Comparisons.end(), 0,
                         [](int Size, const BCECmpBlock &C) {
                           return Size + C.SizeBits();
                         }) /
         8;
 
     // Incoming edges do not need to be updated, and both GEPs are already
     // computing the right address, we just need to:
     //   - replace the two loads and the icmp with the memcmp
     //   - update the branch
     //   - update the incoming values in the phi.
     FirstComparison.BranchI->eraseFromParent();
     FirstComparison.CmpI->eraseFromParent();

test/Transforms/MergeICmps/X86/split-block-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(...)  nounwind readnone
+
+; We can split %entry and create a memcmp(16 bytes).
+define zeroext i1 @opeq1(
+; X86-LABEL: @opeq1(
+; X86:         call void (...) @foo()
+; X86:      entry:
+; X86-NEXT:    [[THIRD_I:%.*]] = getelementptr inbounds %"struct.std::pair", %"struct.std::pair"* [[A:%.*]], i64 0, i32 0
+; X86-NEXT:    [[THIRD1_I:%.*]] = getelementptr inbounds %"struct.std::pair", %"struct.std::pair"* [[B:%.*]], i64 0, i32 0
+; 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 16)
+; X86-NEXT:    [[TMP0:%.*]] = icmp eq i32 [[MEMCMP]], 0
+; X86-NEXT:    br label [[OPEQ1_EXIT:%.*]]
+;
+  %"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
+  %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
+}

test/Transforms/MergeICmps/X86/tuple-four-int8.ll

 %"struct.std::_Tuple_impl.2" = type { %"struct.std::_Head_base" }
 %"struct.std::_Head_base" = type { i8 }
 %"struct.std::_Head_base.4" = type { i8 }
 %"struct.std::_Head_base.5" = type { i8 }
 %"struct.std::_Head_base.6" = type { i8 }
 
 define zeroext i1 @opeq(
 ; CHECK-LABEL: @opeq(
-; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[A_BASE:%.*]] = getelementptr inbounds %"class.std::tuple", %"class.std::tuple"* [[A:%.*]], i64 0, i32 0, i32 0, i32 0, i32 0, i32 0, i32 0
-; CHECK-NEXT:    [[A_ELEM3_ADDR:%.*]] = getelementptr inbounds i8, i8* [[A_BASE]], i64 3
-; CHECK-NEXT:    [[TMP0:%.*]] = load i8, i8* [[A_ELEM3_ADDR]], align 1
-; CHECK-NEXT:    [[B_BASE:%.*]] = getelementptr inbounds %"class.std::tuple", %"class.std::tuple"* [[B:%.*]], i64 0, i32 0, i32 0, i32 0, i32 0, i32 0, i32 0
-; CHECK-NEXT:    [[B_ELEM3_ADDR:%.*]] = getelementptr inbounds i8, i8* [[B_BASE]], i64 3
-; CHECK-NEXT:    [[TMP1:%.*]] = load i8, i8* [[B_ELEM3_ADDR]], align 1
-; CHECK-NEXT:    [[CMP_ELEM3:%.*]] = icmp eq i8 [[TMP0]], [[TMP1]]
-; CHECK-NEXT:    br i1 [[CMP_ELEM3]], label [[LAND_ELEM0:%.*]], label [[OPEQ_EXIT:%.*]]
+;
+; These 2 instructions are split. Then we can merge 3 bytes, instead of 2.
+; CHECK:         [[A_BASE:%.*]] = getelementptr inbounds %"class.std::tuple", %"class.std::tuple"* [[A:%.*]], i64 0, i32 0, i32 0, i32 0, i32 0, i32 0, i32 0
+; CHECK:         [[B_BASE:%.*]] = getelementptr inbounds %"class.std::tuple", %"class.std::tuple"* [[B:%.*]], i64 0, i32 0, i32 0, i32 0, i32 0, i32 0, i32 0 
+; CHECK:         br label [[LAND_ELEM0:%.*]]
 ; CHECK:       land.elem1:
 ; CHECK-NEXT:    [[A_ELEM1_ADDR:%.*]] = getelementptr inbounds i8, i8* [[A_BASE]], i64 1
 ; CHECK-NEXT:    [[B_ELEM1_ADDR:%.*]] = getelementptr inbounds i8, i8* [[B_BASE]], i64 1
-; CHECK-NEXT:    [[MEMCMP:%.*]] = call i32 @memcmp(i8* [[A_ELEM1_ADDR]], i8* [[B_ELEM1_ADDR]], i64 2)
+; CHECK-NEXT:    [[MEMCMP:%.*]] = call i32 @memcmp(i8* [[A_ELEM1_ADDR]], i8* [[B_ELEM1_ADDR]], i64 3)
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[MEMCMP]], 0
-; CHECK-NEXT:    br label [[OPEQ_EXIT]]
+; CHECK-NEXT:    br label [[OPEQ_EXIT:%.*]]
 ; CHECK:       land.elem0:
 ; CHECK-NEXT:    [[TMP3:%.*]] = load i8, i8* [[A_BASE]], align 1
 ; CHECK-NEXT:    [[TMP4:%.*]] = load i8, i8* [[B_BASE]], align 1
 ; CHECK-NEXT:    [[CMP_ELEM0:%.*]] = icmp eq i8 [[TMP3]], [[TMP4]]
 ; CHECK-NEXT:    br i1 [[CMP_ELEM0]], label [[LAND_ELEM1:%.*]], label [[OPEQ_EXIT]]
 ; CHECK:       opeq.exit:
-; CHECK-NEXT:    [[TMP5:%.*]] = phi i1 [ false, [[ENTRY:%.*]] ], [ [[CMP_ELEM0]], [[LAND_ELEM0]] ], [ [[TMP2]], [[LAND_ELEM1]] ]
+; CHECK-NEXT:    [[TMP5:%.*]] = phi i1 [ [[CMP_ELEM0]], [[LAND_ELEM0]] ], [ [[TMP2]], [[LAND_ELEM1]] ]
 ; CHECK-NEXT:    ret i1 [[TMP5]]
 ;
   %"class.std::tuple"* nocapture readonly dereferenceable(4) %a,
   %"class.std::tuple"* nocapture readonly dereferenceable(4) %b) local_unnamed_addr #1 {
 entry:
   %a.base = getelementptr inbounds %"class.std::tuple", %"class.std::tuple"* %a, i64 0, i32 0, i32 0, i32 0, i32 0, i32 0, i32 0
   %a.elem3.addr = getelementptr inbounds i8, i8* %a.base, i64 3
   %0 = load i8, i8* %a.elem3.addr, align 1