[SimplifyCFG] Ignore free instructions when computing cost for folding branch to common dest

[aeubanks]

Summary

When determining whether to fold branches to a common destination by
merging two blocks, SimplifyCFG will count the number of instructions to
be moved into the first basic block. However, there's no reason to count
free instructions like bitcasts and other similar instructions.

This resolves missed branch foldings with -fstrict-vtable-pointers in
llvm-test-suite's lambda benchmark.

[aeubanks]

I'll precommit the test/update newly failing tests if this looks good

[lebedev.ri]

Please do.
I've been meaning to do something along those lines.

This probably should probably be TTI-cost driven completely, not simply instruction count, but the cost model here is dubious even ignoring that.

[xbolva00]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

3253

Skip also AssumeInst?

[aeubanks]

update

[aeubanks]

vector-reductions-logical.ll looks bad, will need investigation

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

3253

should be handled with the new code
and actually, same with DbgInfoIntrinsic, which I've updated

[lebedev.ri]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

3253

Surely assumes aren't speculatable?

[aeubanks]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

3253

oh yes you're right
anyway, can be handled in a separate patch

[aeubanks]

llvm/test/Transforms/PhaseOrdering/X86/vector-reductions-logical.ll

142 ↗

(On Diff #369180)

Now this branch is getting folded into the next basic block. Then at the end of -O2 when every fpext is eliminated, the final simplifycfg will fold every branch (since each block only consists of at most one extra instruction besides the cmp and branch), except for this block which is now slightly bigger.
Any ideas on how to fix this?

[lebedev.ri]

llvm/test/Transforms/PhaseOrdering/X86/vector-reductions-logical.ll

142 ↗

(On Diff #369180)

I do not understand why this test is being affected at all, there are no zero-cost instructions here?

[aeubanks]

llvm/test/Transforms/PhaseOrdering/X86/vector-reductions-logical.ll

142 ↗

(On Diff #369180)

seems like we consider %vecext17 = extractelement <4 x float> %t, i32 0 to be free

https://github.com/llvm/llvm-project/blob/063af63b9664151b3a9206feefa9a6a36a471e80/llvm/lib/Target/X86/X86TargetTransformInfo.cpp#L3433

I tried looking at the history, this special case seems very old

[lebedev.ri]

llvm/test/Transforms/PhaseOrdering/X86/vector-reductions-logical.ll

142 ↗

(On Diff #369180)

Ah, right, that makes sense.
Didn't look, but not sure there is a nice fix here.

[aeubanks]

llvm/test/Transforms/PhaseOrdering/X86/vector-reductions-logical.ll

142 ↗

(On Diff #369180)

@spatel any thoughts on this?

[Prazek]

This looks resonable. BTW are {launder,strip}.inariant.group intrinsics considered to be free now? I remember fixing this in InlineCost, but this seems to be other cost heuristic. They totally should be considered free.

[spatel]

llvm/test/Transforms/PhaseOrdering/X86/vector-reductions-logical.ll

142 ↗

(On Diff #369180)

It's unfortunately a regression, but as the related tests show, we're not getting ideal results (2 vector compares) on most examples.

The cost model is telling the truth from its limited perspective - the extract from elt 0 is free, but the rest are not (they require shuffles).

We need to be able to view these as sequences rather than as individual instructions or basic blocks either here or in SLP to improve things.

A quick hack solution might be to adjust the bonus budget in the presence of vector ops. Ie, if code has vectors, we try harder to speculate instructions because we assume that the cost of branching is likely greater than it appears, and we recognize that creating larger basic blocks has positive impact on SLP.

[lebedev.ri]

llvm/test/Transforms/PhaseOrdering/X86/vector-reductions-logical.ll

142 ↗

(On Diff #369180)

Now that simplifycfg does not speculate known not-taken branches,
my next step was to introduce a multiplier to be appled to speculation budgets
for known-taken branches.

So i think the vector hack makes sense.

[aeubanks]

llvm/test/Transforms/PhaseOrdering/X86/vector-reductions-logical.ll

142 ↗

(On Diff #369180)

what's the right way to check if an instruction is a vector op?

[lebedev.ri]

llvm/test/Transforms/PhaseOrdering/X86/vector-reductions-logical.ll

142 ↗

(On Diff #369180)

I guess you want to add Instruction::isVectorOp().
Perhaps we just want to check that any of: produced type, argument types
is a vector type?

[aeubanks]

add bonus when we see a vector op

[aeubanks]

In D108837#2970575, @Prazek wrote:

This looks resonable. BTW are {launder,strip}.inariant.group intrinsics considered to be free now? I remember fixing this in InlineCost, but this seems to be other cost heuristic. They totally should be considered free.

https://github.com/llvm/llvm-project/blob/83df94067d367d91dcc37e269a3d7317ebe97bb4/llvm/include/llvm/Analysis/TargetTransformInfoImpl.h#L588

[aeubanks]

In D108837#2972812, @aeubanks wrote:

In D108837#2970575, @Prazek wrote:

This looks resonable. BTW are {launder,strip}.inariant.group intrinsics considered to be free now? I remember fixing this in InlineCost, but this seems to be other cost heuristic. They totally should be considered free.

https://github.com/llvm/llvm-project/blob/83df94067d367d91dcc37e269a3d7317ebe97bb4/llvm/include/llvm/Analysis/TargetTransformInfoImpl.h#L588

Looks like you added this in https://reviews.llvm.org/D51814 :)

[lebedev.ri]

Could you please split this into

1. introducing instruction::isvectorop
2. adding bonus when vector ops are present? i'm not sure it should be an increment, and i don't think this is the right function
3. rest of the patch?

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

3154

I think this should be in Instruction.
Is there any instruction that takes scalars only but produces vector?

3246

I think this should be a cl::opt, and applied as a multiplier to BonusInstThreshold.

[aeubanks]

In D108837#2972861, @lebedev.ri wrote:

Could you please split this into

1. introducing instruction::isvectorop
2. adding bonus when vector ops are present? i'm not sure it should be an increment, and i don't think this is the right function
3. rest of the patch?

D108935

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

3154

Instruction doesn't have methods that inspect the operands (except some equality methods). Currently this is specific to SimplifyCFG so I think at least for now it should be here.

Not sure if any instruction takes scalars and produces vectors, but those should count?

[lebedev.ri]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

3154

Err, right, they are, missed the I.getType()->isVectorTy() || , sorry.

[aeubanks]

rebase

[aeubanks]

some tests are crashing in CloneInstructionsIntoPredecessorBlockAndUpdateSSAUses(), reduced to running simplifycfg on

define i32 @test(i32 %len) local_unnamed_addr {
entry:
  br i1 undef, label %for.cond.preheader, label %if.end

for.cond.preheader:                               ; preds = %entry
  %0 = bitcast [1 x i64]* undef to i8*
  %cmp15 = icmp slt i32 1, %len
  br i1 %cmp15, label %for.body.lr.ph, label %if.end.loopexit

for.body.lr.ph:                                   ; preds = %for.cond.preheader
  br label %for.body

for.body:                                         ; preds = %for.body, %for.body.lr.ph
  call void @llvm.lifetime.start.p0i8(i64 8, i8* %0)
  br label %for.body

if.end.loopexit:                                  ; preds = %for.cond.preheader
  br label %if.end

if.end:                                           ; preds = %if.end.loopexit, %entry
  ret i32 0
}

; Function Attrs: argmemonly nofree nosync nounwind willreturn
declare void @llvm.lifetime.start.p0i8(i64 immarg, i8* nocapture) #0

declare void @foo() local_unnamed_addr

; Function Attrs: argmemonly nofree nosync nounwind willreturn
declare void @llvm.lifetime.end.p0i8(i64 immarg, i8* nocapture) #0

attributes #0 = { argmemonly nofree nosync nounwind willreturn }

taking a look

[aeubanks]

Seems to be in the code added recently in https://reviews.llvm.org/rG909cba969981032c5740774ca84a34b7f76b909b

with

diff --cc llvm/lib/Transforms/Utils/SimplifyCFG.cpp
index ac386761e12b,ac386761e12b..32bba11659e7
--- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
@@@ -1107,6 -1107,6 +1107,9 @@@ static void CloneInstructionsIntoPredec
        auto *UI = cast<Instruction>(U.getUser());
        auto *PN = dyn_cast<PHINode>(UI);
        if (!PN) {
++        BonusInst.dump();
++        UI->dump();
++        errs() << (UI->getParent() == BB) << " " << BonusInst.comesBefore(UI) << "\n";
          assert(UI->getParent() == BB && BonusInst.comesBefore(UI) &&
                 "If the user is not a PHI node, then it should be in the same "
                 "block as, and come after, the original bonus instruction.");

I'm seeing

  %.old = bitcast [1 x i64]* undef to i8*
  call void @llvm.lifetime.start.p0i8(i64 8, i8* %.old)
0 opt: ../../llvm/lib/IR/Instruction.cpp:114: bool llvm::Instruction::comesBefore(const llvm::Instruction *) const: Assertion `Parent == Other->Parent && "cross-BB instruction order comparison"' failed.

[aeubanks]

don't skip over recently added IsBCSSAUse check for free instructions
should be good to review now

[spatel]

We handled any controversy in the earlier patches, so this is now the minimal patch as described. LGTM

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

3272–3273

Nit: I'd put the comment before the 'if' line that it explains.

llvm/test/Transforms/PhaseOrdering/X86/vector-reductions-logical.ll

142 ↗

(On Diff #369180)

Checking the types seems like it would do.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

if (isa<DbgInfoIntrinsic>(I)) {
       NewI->insertBefore(PBI);
     }
   }
 
   ++NumFoldBranchToCommonDest;
   return true;
 }
 
 /// Return if an instruction's type or any of its operands' types are a vector
 /// type.
 static bool isVectorOp(Instruction &I) {
   return I.getType()->isVectorTy() || any_of(I.operands(), [](Use &U) {
            return U->getType()->isVectorTy();
          });
 }
 
 /// If this basic block is simple enough, and if a predecessor branches to us
bool llvm::FoldBranchToCommonDest(BranchInst *BI, DomTreeUpdater *DTU,
 
   // Only allow this transformation if computing the condition doesn't involve
   // too many instructions and these involved instructions can be executed
   // unconditionally. We denote all involved instructions except the condition
   // as "bonus instructions", and only allow this transformation when the
   // number of the bonus instructions we'll need to create when cloning into
   // each predecessor does not exceed a certain threshold.
   unsigned NumBonusInsts = 0;
   bool SawVectorOp = false;
   const unsigned PredCount = Preds.size();
   for (Instruction &I : *BB) {
     // Don't check the branch condition comparison itself.
     if (&I == Cond)
       continue;
     // Ignore dbg intrinsics, and the terminator.
     if (isa<DbgInfoIntrinsic>(I) || isa<BranchInst>(I))
       continue;
     // I must be safe to execute unconditionally.
     if (!isSafeToSpeculativelyExecute(&I))
       return false;
     SawVectorOp |= isVectorOp(I);
+    // Ignore free instructions.
+    if (TTI && TTI->getUserCost(&I, CostKind) == TargetTransformInfo::TCC_Free)
+      continue;
 
     // Account for the cost of duplicating this instruction into each
     // predecessor.
     NumBonusInsts += PredCount;
 
     // Early exits once we reach the limit.
     if (NumBonusInsts >
         BonusInstThreshold * BranchFoldToCommonDestVectorMultiplier)
       return false;
 
     auto IsBCSSAUse = [BB, &I](Use &U) {
       auto *UI = cast<Instruction>(U.getUser());
       if (auto *PN = dyn_cast<PHINode>(UI))
         return PN->getIncomingBlock(U) == BB;
       return UI->getParent() == BB && I.comesBefore(UI);
     };
 
     // Does this instruction require rewriting of uses?
     if (!all_of(I.uses(), IsBCSSAUse))
       return false;

llvm/test/CodeGen/AArch64/csr-split.ll

 
 define dso_local signext i32 @test2(i32* %p1) local_unnamed_addr  {
 ; CHECK-LABEL: test2:
 ; CHECK:       // %bb.0: // %entry
 ; CHECK-NEXT:    stp x30, x19, [sp, #-16]! // 16-byte Folded Spill
 ; CHECK-NEXT:    .cfi_def_cfa_offset 16
 ; CHECK-NEXT:    .cfi_offset w19, -8
 ; CHECK-NEXT:    .cfi_offset w30, -16
-; CHECK-NEXT:    cbz x0, .LBB1_2
-; CHECK-NEXT:  // %bb.1: // %if.end
+; CHECK-NEXT:    cbz x0, .LBB1_3
+; CHECK-NEXT:  // %bb.1: // %entry
 ; CHECK-NEXT:    adrp x8, a
 ; CHECK-NEXT:    ldrsw x8, [x8, :lo12:a]
 ; CHECK-NEXT:    mov x19, x0
 ; CHECK-NEXT:    cmp x8, x0
-; CHECK-NEXT:    b.eq .LBB1_3
-; CHECK-NEXT:  .LBB1_2: // %return
-; CHECK-NEXT:    mov w0, wzr
-; CHECK-NEXT:    ldp x30, x19, [sp], #16 // 16-byte Folded Reload
-; CHECK-NEXT:    ret
-; CHECK-NEXT:  .LBB1_3: // %if.then2
+; CHECK-NEXT:    b.ne .LBB1_3
+; CHECK-NEXT:  // %bb.2: // %if.then2
 ; CHECK-NEXT:    bl callVoid
 ; CHECK-NEXT:    mov x0, x19
 ; CHECK-NEXT:    ldp x30, x19, [sp], #16 // 16-byte Folded Reload
 ; CHECK-NEXT:    b callNonVoid
+; CHECK-NEXT:  .LBB1_3: // %return
+; CHECK-NEXT:    mov w0, wzr
+; CHECK-NEXT:    ldp x30, x19, [sp], #16 // 16-byte Folded Reload
+; CHECK-NEXT:    ret
 ;
 ; CHECK-APPLE-LABEL: test2:
 ; CHECK-APPLE:       ; %bb.0: ; %entry
 ; CHECK-APPLE-NEXT:    stp x20, x19, [sp, #-32]! ; 16-byte Folded Spill
 ; CHECK-APPLE-NEXT:    stp x29, x30, [sp, #16] ; 16-byte Folded Spill
 ; CHECK-APPLE-NEXT:    .cfi_def_cfa_offset 32
 ; CHECK-APPLE-NEXT:    .cfi_offset w30, -8
 ; CHECK-APPLE-NEXT:    .cfi_offset w29, -16
 ; CHECK-APPLE-NEXT:    .cfi_offset w19, -24
 ; CHECK-APPLE-NEXT:    .cfi_offset w20, -32
-; CHECK-APPLE-NEXT:    cbz x0, LBB1_2
-; CHECK-APPLE-NEXT:  ; %bb.1: ; %if.end
+; CHECK-APPLE-NEXT:    cbz x0, LBB1_3
+; CHECK-APPLE-NEXT:  ; %bb.1: ; %entry
 ; CHECK-APPLE-NEXT:  Lloh2:
 ; CHECK-APPLE-NEXT:    adrp x8, _a@PAGE
 ; CHECK-APPLE-NEXT:  Lloh3:
 ; CHECK-APPLE-NEXT:    ldrsw x8, [x8, _a@PAGEOFF]
 ; CHECK-APPLE-NEXT:    mov x19, x0
 ; CHECK-APPLE-NEXT:    cmp x8, x0
-; CHECK-APPLE-NEXT:    b.eq LBB1_3
-; CHECK-APPLE-NEXT:  LBB1_2: ; %return
-; CHECK-APPLE-NEXT:    ldp x29, x30, [sp, #16] ; 16-byte Folded Reload
-; CHECK-APPLE-NEXT:    mov w0, wzr
-; CHECK-APPLE-NEXT:    ldp x20, x19, [sp], #32 ; 16-byte Folded Reload
-; CHECK-APPLE-NEXT:    ret
-; CHECK-APPLE-NEXT:  LBB1_3: ; %if.then2
+; CHECK-APPLE-NEXT:    b.ne LBB1_3
+; CHECK-APPLE-NEXT:  ; %bb.2: ; %if.then2
 ; CHECK-APPLE-NEXT:    bl _callVoid
 ; CHECK-APPLE-NEXT:    ldp x29, x30, [sp, #16] ; 16-byte Folded Reload
 ; CHECK-APPLE-NEXT:    mov x0, x19
 ; CHECK-APPLE-NEXT:    ldp x20, x19, [sp], #32 ; 16-byte Folded Reload
 ; CHECK-APPLE-NEXT:    b _callNonVoid
+; CHECK-APPLE-NEXT:  LBB1_3: ; %return
+; CHECK-APPLE-NEXT:    ldp x29, x30, [sp, #16] ; 16-byte Folded Reload
+; CHECK-APPLE-NEXT:    mov w0, wzr
+; CHECK-APPLE-NEXT:    ldp x20, x19, [sp], #32 ; 16-byte Folded Reload
+; CHECK-APPLE-NEXT:    ret
 ; CHECK-APPLE-NEXT:    .loh AdrpLdr Lloh2, Lloh3
 entry:
   %tobool = icmp eq i32* %p1, null
   br i1 %tobool, label %return, label %if.end
 
 if.end:                                           ; preds = %entry
   %0 = load i32, i32* @a, align 4, !tbaa !2
   %conv = sext i32 %0 to i64

llvm/test/Transforms/SimplifyCFG/fold-branch-to-common-dest-free-cost.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -S -passes=simplifycfg -bonus-inst-threshold=1 | FileCheck %s
 
 declare i8* @llvm.strip.invariant.group.p0i8(i8*)
 
 declare void @g1()
 declare void @g2()
 
 define void @f(i8* %a, i8* %b, i1 %c, i1 %d, i1 %e) {
 ; CHECK-LABEL: @f(
-; CHECK-NEXT:    br i1 [[C:%.*]], label [[L1:%.*]], label [[L3:%.*]]
-; CHECK:       l1:
 ; CHECK-NEXT:    [[A1:%.*]] = call i8* @llvm.strip.invariant.group.p0i8(i8* [[A:%.*]])
 ; CHECK-NEXT:    [[B1:%.*]] = call i8* @llvm.strip.invariant.group.p0i8(i8* [[B:%.*]])
 ; CHECK-NEXT:    [[I:%.*]] = icmp eq i8* [[A1]], [[B1]]
-; CHECK-NEXT:    br i1 [[I]], label [[L2:%.*]], label [[L3]]
+; CHECK-NEXT:    [[OR_COND:%.*]] = select i1 [[C:%.*]], i1 [[I]], i1 false
+; CHECK-NEXT:    br i1 [[OR_COND]], label [[L2:%.*]], label [[L3:%.*]]
 ; CHECK:       l2:
 ; CHECK-NEXT:    call void @g1()
 ; CHECK-NEXT:    br label [[RET:%.*]]
 ; CHECK:       l3:
 ; CHECK-NEXT:    call void @g2()
 ; CHECK-NEXT:    br label [[RET]]
 ; CHECK:       ret:
 ; CHECK-NEXT:    ret void