This is an archive of the discontinued LLVM Phabricator instance.

[BranchFolding] Remove redundant conditional branch.
Changes PlannedPublic

Authored by skatkov on Apr 17 2023, 4:59 AM.

Details

Summary
BB1: Conditional jump outside
        Fallthrough or explicit branch to BB2
BB2: The same conditional branch leading to somewhere else outside
        Fallthrough or explicit branch to BB3

can be transformed to

BB1: Conditional jump outside
        Fallthrough or explicit branch to BB2
BB2: Fallthrough or explicit branch to BB3

Diff Detail

Event Timeline

skatkov created this revision.Apr 17 2023, 4:59 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 17 2023, 4:59 AM
skatkov requested review of this revision.Apr 17 2023, 4:59 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 17 2023, 4:59 AM
skatkov edited the summary of this revision. (Show Details)Apr 17 2023, 8:56 AM
danilaml added inline comments.Apr 17 2023, 1:41 PM
llvm/lib/CodeGen/BranchFolding.cpp
1686

Does it also need to check that MBB has no other predecessors?

skatkov added inline comments.Apr 17 2023, 7:59 PM
llvm/lib/CodeGen/BranchFolding.cpp
1686

Line: 1676, MBB->pred_size() == 1 => MBB has only one predecessor.

goldstein.w.n added inline comments.Apr 17 2023, 8:25 PM
llvm/lib/CodeGen/BranchFolding.cpp
1684

Does this take into account comparisons against memory? The pointer (operand) stays the same but value in memory is modified in BB1?

skatkov added inline comments.Apr 17 2023, 8:30 PM
llvm/lib/CodeGen/BranchFolding.cpp
1684

BB1 is a predecessor or MBB? For MBB we check that it is IsBranchOnlyBlock(MBB).

you mean that predecessor may contains store AFTER conditional branch and conditional branch itself may reference memory?

1684

and -> or

goldstein.w.n added inline comments.Apr 17 2023, 8:37 PM
llvm/lib/CodeGen/BranchFolding.cpp
1676

Instead of only 1 pred, you could check that all predecessors share the conditions?

1679

There is more than just this 1 case no?

IIUC you have

BB1 Cond0
        T -> Narian
        F -> BB2

BB2 Cond0
       T -> Narnia
       F -> BB3
---
BB1 Cond0
      T -> Narnia
      F -> BB2
BB2 -> BB3

But you could also have:

BB1 Cond0
        T -> BB2
        F -> Narian

BB2 Cond0
       T -> BB3
       F -> Narnai
---
BB1 Cond0
      T -> BB2
      F -> Narnia
BB2 -> BB3
BB1 Cond0
        T -> Narian
        F -> BB2

BB2 Cond0
       T -> BB3
       F -> Narnai
---
BB1 Cond0
      T -> Narnia
      F -> BB2
BB2 -> Narnia
BB1 Cond0
        T -> Narian
        F -> BB2

BB2 Cond0
       T -> Narnia
       F -> BB3
---
BB1 Cond0
      T -> Narnia
      F -> BB2
BB2 -> BB3

In which could it would really just be that one of PriorTBB or PriorFBB equals MBB then where MBB goes based on which.

skatkov added inline comments.Apr 17 2023, 8:53 PM
llvm/lib/CodeGen/BranchFolding.cpp
1676

It makes the patch more complicated... but let's see what we can do here...

1679

The cases 2-3 you added are actually covered by this patch as I see.
The first one, when BB1 conditionally jumps to BB2 is something new which we can cover I guess...

goldstein.w.n added inline comments.Apr 17 2023, 9:14 PM
llvm/lib/CodeGen/BranchFolding.cpp
1679

Err I duplicates the current case as case 3. There are two cars where BB2 is true. But you should get both as you handle case 1.

1684

BB1 is a predecessor or MBB? For MBB we check that it is IsBranchOnlyBlock(MBB).

you mean that predecessor may contains store AFTER conditional branch and conditional branch itself may reference memory?

Yes, exactly.
If this is still in SSA then it's fine, but x86 machine instructions (and other) have rm modifier where operands match but results can vary

skatkov added inline comments.Apr 17 2023, 9:20 PM
llvm/lib/CodeGen/BranchFolding.cpp
1684

Interesting, something new to me. At least on x86_64 conditional instruction is JCC which actually only reads the eflags and has no access to memory. If there is no other modification of eflags - we are ok.

But at least I need to check two things:

  1. is it possible that there are some instructions after conditional branch which may affect the result of next equivalent conditional branch.
  2. Are there any platforms where two conditional branches, one right after another one, may produce the right results.

Thanks for good question.

1684

may produce the right results. -> may produce different results.

goldstein.w.n added inline comments.Apr 17 2023, 10:07 PM
llvm/lib/CodeGen/BranchFolding.cpp
1684

Interesting, something new to me. At least on x86_64 conditional instruction is JCC which actually only reads the eflags and has no access to memory. If there is no other modification of eflags - we are ok.

But at least I need to check two things:

  1. is it possible that there are some instructions after conditional branch which may affect the result of next equivalent conditional branch.
  2. Are there any platforms where two conditional branches, one right after another one, may produce the right results.

Thanks for good question.

I think I confused myself (and possibly you a bit).

I assumed match operands was matching the comparison that lead to it i.e

cmpl %rdi, (%rsi); jcc not just the jcc. If its just the jcc then yeah, there is no concern about the rm stuff.

If its just jcc, then yeah just checking that there are no instructions that write to the jump flags should be enough.

skatkov added inline comments.Apr 17 2023, 10:27 PM
llvm/lib/CodeGen/BranchFolding.cpp
1684

your question still makes sense. If on some platform there exist instruction which does a comparison and jump (for example, cbz on AARCH) I need to ensure that there is no modification of memory/register between two such operations...

In this patch I'm base on analyzeBranch utility. And It might be a problem. I'll try to create some tests which reproduce this problem and probably I need to find how to fix it.
Moreover if it is true problem then probably analyzeBranch is not enough and I need to do something more and probably in different place.

Would be nice to have few dedicated tests. All existing test changes are noisy

llvm/lib/CodeGen/BranchFolding.cpp
1682

until -> unless ?

skatkov planned changes to this revision.May 18 2023, 9:12 PM

At the moment, I do not see an easy way to implement this one in platform independent way. I put it on hold due to busy with other stuff.