This is an archive of the discontinued LLVM Phabricator instance.

Proper handling of diamond-like cases in if-conversion
ClosedPublic

Authored by kparzysz on Jan 13 2016, 2:27 PM.

Details

Summary

If converter was somewhat careless about "diamond" cases, where there was no join block, or in other words, where the true/false blocks did not have analyzable branches. In such cases, it was possible for it to remove the (necessary) branches, resulting in a loss of entire basic blocks.

Diff Detail

Event Timeline

kparzysz updated this revision to Diff 44791.Jan 13 2016, 2:27 PM
kparzysz retitled this revision from to Proper handling of diamond-like cases in if-conversion.
kparzysz updated this object.
kparzysz added a reviewer: MatzeB.
kparzysz set the repository for this revision to rL LLVM.
kparzysz added a subscriber: llvm-commits.
MatzeB edited edge metadata.Jan 19 2016, 11:58 AM

I am not too familiar with the if conversion code, but reading it so far it looks to me like ValidDiamond is not supposed to handle case where there is not common join block. I would expect a branch ending in return to hit the ValidSimple() case.

My understanding if the code is that return instructions are not analyzable and the code sequence at the beginning of ValidDiamond() should reject cases where both blocks do not end in analyzable branches (the 4th if should reject them I think).

if (!TT && blockAlwaysFallThrough(TrueBBI))
  TT = getNextBlock(TrueBBI.BB);
if (!FT && blockAlwaysFallThrough(FalseBBI))
  FT = getNextBlock(FalseBBI.BB);
if (TT != FT)
  return false;
if (!TT && (TrueBBI.IsBrAnalyzable || FalseBBI.IsBrAnalyzable))
  return false;
if  (TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1)
  return false;

Can you reproduce the issue with other backends? I am not convinced yet that the problem is not AnalyzeBranch() reporting unexpected values.

kparzysz added a comment.EditedJan 19 2016, 12:19 PM

The 4th statement will return if TT is null (actually both TT and FT), and both branches are analyzable. You are right---returns are not analyzable, and this condition is not triggered. The AnalyzeBranch from Hexagon does not differ in that respect from that from other targets.

I have tried other backends, but I couldn't get just the right optimizations to kick in. Both function calls need to be tail calls, and a jump table needs to be created. Moreover, the block with the jump table branch needs to be a target of a conditional branch that will be recognized as a diamond by the if converter. For other backends, the code never looked right enough to trigger this condition, but I don't think there is anything Hexagon-specific (except the testcase itself).

The 4th statement will return if TT is null (actually both TT and FT), and both branches are analyzable. You are right---returns are not analyzable, and this condition is not triggered. The AnalyzeBranch from Hexagon does not differ in that respect from that from other targets.

Your patch description states that you fix diamond cases with no join block (doesn't sound like a diamond case to me, and I'm not convinced the code in ValidDiamond is supposed to handle that). Anyway if both TT and FT end in a return, then I would expect TT and FT to be nullptr at this point and as none of the two branches was analyzable we end in a return false

The 4th statement will return if TT is null (actually both TT and FT), and both branches are analyzable. You are right---returns are not analyzable, and this condition is not triggered. The AnalyzeBranch from Hexagon does not differ in that respect from that from other targets.

Your patch description states that you fix diamond cases with no join block (doesn't sound like a diamond case to me, and I'm not convinced the code in ValidDiamond is supposed to handle that). Anyway if both TT and FT end in a return, then I would expect TT and FT to be nullptr at this point and as none of the two branches was analyzable we end in a return false

Ignore this comment, you will indeed not hit this case. I still have to read the code some more to understand why ValidSimple() doesn't kick in here and whether ValidDiamond() is supposed to handle this case.

Yes, the "diamond" in this context is a misnomer as the diamond code tries to handle cases without a join block (which is obviously not an actual diamond). I think it used to only handle real diamonds and then was extended to handle more relaxed cases. The function names remain but they do more than what the names suggest.

MatzeB accepted this revision.Jan 19 2016, 2:49 PM
MatzeB edited edge metadata.

LGTM, with nitpick addressed.

lib/CodeGen/IfConversion.cpp
1492–1493

I'd prefer an explicit MachineBasicBlock::iterator here instead of auto.

This revision is now accepted and ready to land.Jan 19 2016, 2:49 PM
This revision was automatically updated to reflect the committed changes.
kparzysz marked an inline comment as done.Jan 20 2016, 5:21 AM
kparzysz added inline comments.
lib/CodeGen/IfConversion.cpp
1492–1493

Done.