This is an archive of the discontinued LLVM Phabricator instance.

[MachineBlockPlacement] Don't make blocks "uneditable"
ClosedPublic

Authored by sanjoy on Dec 14 2016, 4:01 PM.

Details

Summary

NB: I'm new to this area, so please review with care and distrust. :)

This fixes an issue with MachineBlockPlacement due to a badly timed call
to analyzeBranch with AllowModify set to true. The timeline is as
follows:

  1. MachineBlockPlacement::maybeTailDuplicateBlock calls TailDup.shouldTailDuplicate on its argument, which in turn calls analyzeBranch with AllowModify set to true.
  2. This analyzeBranch call edits the terminator sequence of the block based on the physical layout of the machine function, turning an unanalyzable non-fallthrough block to a unanalyzable fallthrough block. Normally MBP bails out of rearranging such blocks, but this block was unanalyzable non-fallthrough (and thus rearrangeable) the first time MBP looked at it, and so it goes ahead and decides where it should be placed in the function.
  3. When placing this block MBP fails to analyze and thus update the block in keeping with the new physical layout.

Concretely, before (1) we have something like:

LBL0:
  < unknown terminator op that may branch to LBL1 >
  jmp LBL1

LBL1:
  ... A

LBL2:
  ... B

In (2), analyze branch simplifies this to

LBL0:
  < unknown terminator op that may branch to LBL2 >
  ;; jmp LBL1 <- redundant jump removed

LBL1:
  ... A

LBL2:
  ... B

In (3), MachineBlockPlacement goes ahead with its plan of putting LBL2
after the first block since that is profitable.

LBL0:
  < unknown terminator op that may branch to LBL2 >
  ;; jmp LBL1 <- redundant jump

LBL2:
  ... B

LBL1:
  ... A

and the program now has incorrect behavior (we no longer fall-through
from LBL0 to LBL1) because MBP can no longer edit LBL0.

There are several possible solutions, but I went with removing the teeth
off of the analyzeBranch calls in TailDuplicator. That makes thinking
about the result of these calls easier, and nothing in the lit test
suite broke when I did it.

I've also added some bookkeeping to the MachineBlockPlacement pass and
used that to write an assert that would have caught this issue.

Event Timeline

sanjoy updated this revision to Diff 81491.Dec 14 2016, 4:01 PM
sanjoy retitled this revision from to [MachineBlockPlacement] Don't make blocks "uneditable".
sanjoy updated this object.
sanjoy added reviewers: iteratee, chandlerc, gberry, MatzeB.
sanjoy added a subscriber: llvm-commits.
iteratee edited edge metadata.Dec 14 2016, 4:39 PM

I'm OK with the debugging, but I think it's a little over-engineered. Basically you're keeping a list of all the blocks that you think have unanalyzable fallthrough and then you want to assert if during updateTerminators you encounter a block with unanalyzable fallthrough that is not on that list. Is that correct? If so simply keeping that set and testing for membership is sufficient, and simpler.

I'm also OK removing the teeth in TailDuplicator. It bothers me that analyzeBranch has that flag at all.

My real surprise moment is that analyzeBranch would choose to modify a branch that it claims it can't analyze. Really! I'm not convinced that's correct, but I'm fine with some defensive programming in response to it.

lib/CodeGen/MachineBlockPlacement.cpp
179

I think this should just be a list global to the pass. Each unanalyzable fallthrough gets merged exactly once.

209

I don't really like this function. This is basically all blocks without unanalyzable fallthrough. I'd rather just test for membership at the point where we need it.

1599–1600

Rather than polluting the merge api, BB is available right here, just mark it.

I'm OK with the debugging, but I think it's a little over-engineered. Basically you're keeping a list of all the blocks that you think have unanalyzable fallthrough and then you want to assert if during updateTerminators you encounter a block with unanalyzable fallthrough that is not on that list. Is that correct? If so simply keeping that set and testing for membership is sufficient, and simpler.

Sounds good -- I'll move the set to live on the MachineFunctionPass object then.

I'm also OK removing the teeth in TailDuplicator.

It bothers me that analyzeBranch has that flag at all.

Me too. :)

My real surprise moment is that analyzeBranch would choose to modify a branch that it claims it can't analyze. Really! I'm not convinced that's correct, but I'm fine with some defensive programming in response to it.

I agree that's hard to defend, and I was initially considering fixing analyzeBranch to edit a branch only if it would return false. However, it is also reasonable to also say that the transform it did here is a pretty obvious peephole transform which it _should_ be able to do without fully understanding the branch.

I think an overall better solution is to have two TII hooks, analyzeBranch and simplifyBranch. simplifyBranch can then be specified to not indicate anything about the understandability of the terminator sequence -- its job would be to do locally obvious peephole simplification without any global understanding.

sanjoy updated this revision to Diff 81500.Dec 14 2016, 5:05 PM
sanjoy edited edge metadata.
  • review
iteratee accepted this revision.Dec 14 2016, 6:01 PM
iteratee edited edge metadata.

One minor fix, but otherwise LGTM

lib/CodeGen/MachineBlockPlacement.cpp
1680

Can you make the assert comment here more descriptive, something like:
"Unexpected block with un-analyzable fallthrough detected."

This revision is now accepted and ready to land.Dec 14 2016, 6:01 PM
This revision was automatically updated to reflect the committed changes.