This is an archive of the discontinued LLVM Phabricator instance.

[BranchRelaxation] Fall through only if block has no unconditional branches
ClosedPublic

Authored by gandhi21299 on Sep 23 2022, 11:19 AM.

Details

Summary

Prior to inserting an unconditional branch from X to its
fall through basic block, check if X has any terminators to
avoid inserting additional branches.

Diff Detail

Event Timeline

gandhi21299 created this revision.Sep 23 2022, 11:19 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 23 2022, 11:19 AM
gandhi21299 requested review of this revision.Sep 23 2022, 11:19 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 23 2022, 11:19 AM
  • changed CHECK-NEXT to CHECK because of a blank line before
gandhi21299 edited the summary of this revision. (Show Details)Sep 23 2022, 11:27 AM
arsenm added inline comments.Sep 23 2022, 11:27 AM
llvm/lib/CodeGen/BranchRelaxation.cpp
493–503

I'd expect for this to be covered by getFallThrough check for false. Did something weird happen with an unanalyzable branch?

bcahoon added inline comments.Sep 23 2022, 11:28 AM
llvm/test/CodeGen/AMDGPU/branch-relax-no-terminators.ll
1 ↗(On Diff #462558)

Perhaps the test should check the generated output rather than the debug info? The debug info is only generated if asserts are enabled, and I'm not sure why it shows the fail/pass criteria.

Could also use a MIR test

gandhi21299 added inline comments.Sep 23 2022, 11:37 AM
llvm/lib/CodeGen/BranchRelaxation.cpp
493–503

We found a case where fixupUnconditionalBranch() appends a s_branch X to a block with terminators s_cbranch X, s_branch Y.

efriedma added inline comments.
llvm/lib/CodeGen/BranchRelaxation.cpp
493–503

There's a comment in getFallThrough: "If there is some explicit branch to the fallthrough block, it can obviously reach, even though the branch should get folded to fall through implicitly." Maybe that bit of code is what's confusing the logic here?

(I'm not sure why that logic exists...)

gandhi21299 added inline comments.Sep 23 2022, 1:31 PM
llvm/lib/CodeGen/BranchRelaxation.cpp
493–503

Yea there is no check for the "explicit branch" or any form of branch at all.

bcahoon added inline comments.Sep 23 2022, 1:47 PM
llvm/lib/CodeGen/BranchRelaxation.cpp
493–503

There's a comment in getFallThrough: "If there is some explicit branch to the fallthrough block, it can obviously reach, even though the branch should get folded to fall through implicitly." Maybe that bit of code is what's confusing the logic here?

Yes - this is the code that causes the problem. I'm also not sure why that logic is there, though it's been around since 2009.

The basic block where getFallThrough returns true contains the following branches:

BB1:
  other instructions
  s_cbranch_execnz BB2
  s_branch BB3
BB2:
  • changed the IR debug info test to output test
  • working on an MIR test
gandhi21299 marked an inline comment as done.Sep 23 2022, 2:17 PM
efriedma added inline comments.Sep 23 2022, 4:27 PM
llvm/lib/CodeGen/BranchRelaxation.cpp
493–503

That makes sense... but I'm not sure checking for PrevBB->terminators().empty() is the right way to fix that. You can have fallthrough with terminators. For example:

BB1:  
  other instructions
  s_cbranch_execnz BB3
BB2:
gandhi21299 added inline comments.Sep 26 2022, 10:17 AM
llvm/lib/CodeGen/BranchRelaxation.cpp
493–503

In the example, a branch won't be inserted which is what we expect right? Or am I missing something?

bcahoon added inline comments.Sep 26 2022, 10:46 AM
llvm/lib/CodeGen/BranchRelaxation.cpp
493–503

A branch is needed because a new block is inserted between BB1 and BB2 that shouldn't be executed when control goes from BB1 -> BB2. So, after the transformation,

BB1:
  other instructions
  s_cbranch_execnz BB3
  s_branch BB2
BB4:

BB2:
  • Instead of checking the number of terminators to allow for fallthrough, analyze the branches and only allow fallthroughs if no terminator is an unconditional branch. Remove conditional branch if the destination is the fallthrough block.
  • Add an MIR test.
gandhi21299 retitled this revision from [BranchRelaxation] Fall through only if block has no terminators to [BranchRelaxation] Fall through only if block has no unconditional branches.Sep 30 2022, 3:53 PM
arsenm added inline comments.Oct 3 2022, 12:41 PM
llvm/lib/CodeGen/BranchRelaxation.cpp
498

I don't think I've ever seen someone use the and macro before

  • Replaced 'and' with '&&'
gandhi21299 marked an inline comment as done.Oct 3 2022, 5:16 PM
bcahoon added inline comments.Oct 3 2022, 6:55 PM
llvm/lib/CodeGen/BranchRelaxation.cpp
455

Do you need this to return true/false. Doesn't seem like the return value is checked?

495

Is it possible to add the assert to your change? Unless it's not needed anymore.

499

No need for braces for the single statement body.

gandhi21299 marked 2 inline comments as done.
  • Removed braces for a single-line code block
  • Changed return type of EnforceFallThrough to void
gandhi21299 added inline comments.Oct 3 2022, 7:26 PM
llvm/lib/CodeGen/BranchRelaxation.cpp
495

I made EnforceFallthrough usable more generally so it would be inconsistent to insert the assertion in the lambda.

Passed internal CI

gandhi21299 marked 6 inline comments as done.Oct 7 2022, 9:59 AM

@efriedma How does this patch look?

The logic here has gotten more confusing, not less. Please just don't call getFallThrough; you can directly reason about the result of analyzeBranch.

From TargetInstrInfo.h:

/// 1. If this block ends with no branches (it just falls through to its succ)
///    just return false, leaving TBB/FBB null.
/// 2. If this block ends with only an unconditional branch, it sets TBB to be
///    the destination block.
/// 3. If this block ends with a conditional branch and it falls through to a
///    successor block, it sets TBB to be the branch destination block and a
///    list of operands that evaluate the condition. These operands can be
///    passed to other TargetInstrInfo methods to create new branches.
/// 4. If this block ends with a conditional branch followed by an
///    unconditional branch, it returns the 'true' destination in TBB, the
///    'false' destination in FBB, and a list of operands that evaluate the
///    condition.  These operands can be passed to other TargetInstrInfo
///    methods to create new branches.

1 is fallthrough. 2 is not fallthrough. 3 is fallthrough. 4 is not fallthrough.


Not sure I understand the logic here when analyzeBranch fails; you just assume the block doesn't fall through?

gandhi21299 updated this revision to Diff 466161.EditedOct 7 2022, 12:47 PM
  • calling getFallthrough() is redundant as the specific case asserts that a fallthrough exists for PrevBB. I simplified the code and eliminated the use of getFallthrough().

The logic here has gotten more confusing, not less. Please just don't call getFallThrough; you can directly reason about the result of analyzeBranch.

From TargetInstrInfo.h:

/// 1. If this block ends with no branches (it just falls through to its succ)
///    just return false, leaving TBB/FBB null.
/// 2. If this block ends with only an unconditional branch, it sets TBB to be
///    the destination block.
/// 3. If this block ends with a conditional branch and it falls through to a
///    successor block, it sets TBB to be the branch destination block and a
///    list of operands that evaluate the condition. These operands can be
///    passed to other TargetInstrInfo methods to create new branches.
/// 4. If this block ends with a conditional branch followed by an
///    unconditional branch, it returns the 'true' destination in TBB, the
///    'false' destination in FBB, and a list of operands that evaluate the
///    condition.  These operands can be passed to other TargetInstrInfo
///    methods to create new branches.

1 is fallthrough. 2 is not fallthrough. 3 is fallthrough. 4 is not fallthrough.


Not sure I understand the logic here when analyzeBranch fails; you just assume the block doesn't fall through?

analyzeBranch returns false when it is able to infer the terminators of the basic block. That is, determine TBB and FBB. This patch effectively leverages the cases for fallthrough as you mentioned for a specific case - only fall through for cases 1 and 3. Albeit I agree that not using getFallthrough() makes the code simpler and probably should not be used as the case already asserts that a fall through certainly exists for PrevBB (PrevBB is defined to be the block immediately prior to DestBB).

Okay, that's more straightforward.

I think we need to distinguish between (2) and (3) somehow (unconditional branch, vs. conditional branch + fallthrough). Should we be checking Cond.empty()?

analyzeBranch returns false when it is able to infer the terminators of the basic block

Right... and when it fails to analyze (i.e. returns true), you assume there is no fallthrough. I don't think that's a safe assumption.

  • Use Cond.empty() to distinguish between the case of uncondBr vs condBr + fallthrough

analyzeBranch returns false when it is able to infer the terminators of the basic block

Right... and when it fails to analyze (i.e. returns true), you assume there is no fallthrough. I don't think that's a safe assumption.

Two possiblities: (1) there may be a known control barrier in the end of this block or, (2) the barrier may be predicated during IfConversion. In either case, fallthrough should be allowed.

  • handle the case when the block ends in a barrier
arsenm added inline comments.Oct 11 2022, 8:48 AM
llvm/lib/CodeGen/BranchRelaxation.cpp
501–503

Is this case covered in the test?

llvm/test/CodeGen/AMDGPU/branch-relax-no-terminators.mir
4–7

Should use update_mir_test_checks at this point

865

You should be able to drop the IR section

gandhi21299 added inline comments.Oct 12 2022, 9:00 AM
llvm/lib/CodeGen/BranchRelaxation.cpp
501–503

I tried out various branching opcodes out there on AMDGPU, none of them satisfied the condition.

gandhi21299 added inline comments.Oct 12 2022, 9:11 AM
llvm/test/CodeGen/AMDGPU/branch-relax-no-terminators.mir
4–7

llc: Unknown command line argument '--amdgpu-s-branch-bits=5' when running update_mir_test_checks.py on this test.

  • simplified test, ran update_mir_test_checks.py
gandhi21299 marked 2 inline comments as done.Oct 12 2022, 9:34 AM
efriedma added inline comments.Oct 12 2022, 11:04 AM
llvm/lib/CodeGen/BranchRelaxation.cpp
501–503

I'd prefer to just check else if (FailToAnalyze && PrevBB->isSuccessor(DestBB)), rather than try to figure out the specific properties of the terminator of PrevBB.

arsenm added inline comments.Oct 12 2022, 11:14 AM
llvm/lib/CodeGen/BranchRelaxation.cpp
501–503

I'm not a fan of putting untested code in to satisfy theoretical conditions. If there's a case we don't know how to handle, I would just put a report_fatal_error in for when a target that does needs this runs into it

efriedma added inline comments.Oct 12 2022, 11:26 AM
llvm/lib/CodeGen/BranchRelaxation.cpp
501–503

You could end up in this situation with a predicated "ret" instruction on 32-bit ARM, I think, but we don't use BranchRelaxation there. Not sure if there any any unanalyzable fallthrough terminators on any of the targets that currently use BranchRelaxation; if there aren't, I guess a report_fatal_error is sufficient.

  • report fatal error instead of falling through an unanalyzable case.
ruiling added inline comments.
llvm/lib/CodeGen/BranchRelaxation.cpp
493–503

I am not quite sure whether a simplified approach would work here: Check whether there is explicit branch to FT in PrevBB? if no, insert unconditional branch at the end of PrevBB to FT, otherwise do nothing. Does this solve the problem here? The remaining question is how to detect whether there is pre-existing branch to FT in PrevBB? I think we can do an iteration over the terminators of PrevBB to find if there is any branch instruction that has a MBB operand referencing DestBB.
The overall idea would look like:

if ((auto *FT = PrevBB->getFallThrough()) {
  iterating over the terminators of PrevBB, see if there is any branch instruction which has a MachineOperand that references FT
  if (explicit branch to FT NOT found)
    insert unconditional branch and recalculate block size
}

Does this sounds good to you? @efriedma @arsenm

gandhi21299 added inline comments.Oct 12 2022, 11:40 PM
llvm/lib/CodeGen/BranchRelaxation.cpp
493–503

That is essentially what I have done via breaking getFallThrough() and avoiding a call to it. The problem with getFallThrough(), as discussed previously, is that it consists of confusing logic. I use analyzeBranch() to determine the successors of PrevBB, which is the same as iterating over terminators and checking their operands.

ruiling added inline comments.Oct 13 2022, 1:14 AM
llvm/lib/CodeGen/BranchRelaxation.cpp
493–503

That is essentially what I have done via breaking getFallThrough() and avoiding a call to it.

ok, now that you guys have made the decision like that, feel free to ignore my comments. Sorry I did not follow all the discussion carefully.

gandhi21299 marked an inline comment as done.Oct 13 2022, 1:03 PM
arsenm added inline comments.Oct 13 2022, 9:05 PM
llvm/lib/CodeGen/BranchRelaxation.cpp
502

Can just move this up as

if (analyzeBranch())
  report_fatal_error
  • Moved report_fatal_error(...) up as requested.
arsenm accepted this revision.Oct 13 2022, 9:38 PM
This revision is now accepted and ready to land.Oct 13 2022, 9:38 PM
This revision was landed with ongoing or failed builds.Oct 13 2022, 9:49 PM
This revision was automatically updated to reflect the committed changes.

Thanks everyone for the review!