This is an archive of the discontinued LLVM Phabricator instance.

IfConversion: Fix branch predication bug.
ClosedPublic

Authored by iteratee on Aug 26 2016, 11:27 AM.

Details

Summary

This bug shows up with diamonds that share unpredicable, unanalyzable branches.
There's an included test case from Hexagon. What was happening was that we were
attempting to predicate the branch instruction despite the fact that it was
checked to be the same. Now for unanalyzable branches we skip over the branch
instructions when predicating the block.

Diff Detail

Event Timeline

iteratee updated this revision to Diff 69413.Aug 26 2016, 11:27 AM
iteratee retitled this revision from to IfConversion: Fix branch predication bug..
iteratee updated this object.
iteratee added a reviewer: kparzysz.
iteratee set the repository for this revision to rL LLVM.
iteratee added a subscriber: llvm-commits.
iteratee updated this revision to Diff 69417.Aug 26 2016, 11:36 AM
iteratee removed rL LLVM as the repository for this revision.

Add forgotten testcase.

iteratee set the repository for this revision to rL LLVM.Aug 26 2016, 11:46 AM
iteratee edited reviewers, added: davidxl; removed: kparzysz.Aug 26 2016, 11:57 AM
iteratee added a subscriber: kparzysz.
davidxl added inline comments.Aug 26 2016, 2:39 PM
lib/CodeGen/IfConversion.cpp
1815–1820

Is trueBranch always analyzable?

1849

Why skipping debug value here? Does that affect the NumDups2 adjustment below?

iteratee added inline comments.Aug 26 2016, 3:06 PM
lib/CodeGen/IfConversion.cpp
1815–1820

No, but we have previously verified that both blocks have the same branch instructions, so we only need one copy.

1849

Does that affect the NumDups2 adjustment below?

No. NumDups2 doesn't count debug values.

Would it be clearer if it read (DI2->isBranch() || DI2->isDebugValue())?

The goal is to skip all the branch instructions, because they have been checked to match MBB1 and don't need to predicated.
This is where the actual crash was occurring. We were attempting to predicate the branch instruction when we didn't need to.

davidxl added inline comments.Aug 26 2016, 3:21 PM
lib/CodeGen/IfConversion.cpp
1849

Ok. Can you add some comments?

Can you also add assertion to make sure that the instructions from two blocks are indeed common?

iteratee updated this revision to Diff 69447.Aug 26 2016, 4:19 PM
iteratee removed rL LLVM as the repository for this revision.

Added assertion that branches are the same.
Added comments that we have already checked the sameness.
Verified that if I remove the earlier check for branch sameness, the later assertion does fire.

iteratee marked an inline comment as done.Aug 26 2016, 4:20 PM
iteratee added inline comments.
lib/CodeGen/IfConversion.cpp
797

I shrank the space here, but don't see a need for a new diff.

iteratee set the repository for this revision to rL LLVM.Aug 26 2016, 4:22 PM
davidxl added inline comments.Aug 26 2016, 5:11 PM
lib/CodeGen/IfConversion.cpp
1815–1820

Is it an expectation later that the terminator instruction (in two BBs) are either both removed or they both exist -- i.e. what verifySameInstructions does?

You patch looks right, but can you check why the problem does not appear before ? Is it because NumDups2 computation is different?

1843

Why not always skip it?

iteratee updated this revision to Diff 69454.Aug 26 2016, 5:48 PM
iteratee removed rL LLVM as the repository for this revision.

Narrowed scope of branch match assertion to the un-analyzable case.

lib/CodeGen/IfConversion.cpp
1815–1820

They are expected to match except for a possible unconditional branch, and they may be reversed from each other.
If they are unanalyzable, they must match exactly.

It didn't occur because by rescanning, we find new opportunities to if-convert.

Previously if the branch instruction were unpredicable, the block was not considered a candidate for diamond if-conversion. Now, as long as the branch instruction at the end of the 2 blocks is the same, we are willing to diamond convert.

That means we now miss the case of a "diamond" where both sides end in an unanalyzable but predicable branch.

1843

For analyzable branches, the actual branch instruction may not be necessary. e.g. a diamond, where the join block is either merged, or a fallthrough. In that case, the caller will handle the branch.

davidxl accepted this revision.Aug 27 2016, 4:10 PM
davidxl edited edge metadata.

lgtm

This revision is now accepted and ready to land.Aug 27 2016, 4:10 PM
This revision was automatically updated to reflect the committed changes.