Page MenuHomePhabricator

[TRE][NFC] Refactor Basic Block Processing
ClosedPublic

Authored by laytonio on Jun 20 2020, 4:41 PM.

Details

Summary

Simplify and improve readability.

Diff Detail

Event Timeline

laytonio created this revision.Jun 20 2020, 4:41 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 20 2020, 4:41 PM

Do we want to land this before D82085?

Otherwise, LGTM

llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
774

I'm pretty sure the address-taken check here is wrong, and this doesn't interact correctly with unreachable code. Probably we should teach eliminateCall to RAUW away dead uses instead, and then let some other code call removeUnreachableBlocks to do the cleanup properly.

I guess this isn't new code, though.

laytonio marked an inline comment as done.Jun 23 2020, 6:51 AM

I'll wait and rebase after D82085.

llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
774

I don't think there is anything we could use to RAUW that would be semantic preserving, not that it matters much I guess since this block is now dead. I looked at the other uses of FoldReturnIntoUncondBranch (there are only 2) to see how other passes handle the possibility of creating a dead block. SimplifyCFG just checks the predecessors and deletes the block. CodeGenPrepare checks the predecessors and the address-taken and deletes the block. The BasicBlock destructor seems to correctly handle the case where a dead block has its address taken, and even a nice comment explaining how you could end up in that situation. Therefore, I think we are safe to remove the address-taken check and just delete the block if it has no predecessors.

efriedma added inline comments.Jun 23 2020, 3:20 PM
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
774

I don't think there is anything we could use to RAUW that would be semantic preserving, not that it matters much I guess since this block is now dead.

Exactly, the value doesn't matter because it's dead.

I looked at the other uses of FoldReturnIntoUncondBranch (there are only 2) to see how other passes handle the possibility of creating a dead block. SimplifyCFG just checks the predecessors and deletes the block. CodeGenPrepare checks the predecessors and the address-taken and deletes the block

Consider the following example, which currently crashes tailcallelim:

define i32 @foo() {
  %z = call i32 @foo()
  ret i32 %z

  ret i32 %z
}

removeUnreachableBlocks avoids the problem by calling dropAllReferences() (which only works because it's erasing all the unreachable blocks at once). CodeGenPrepare avoids the problem by accident, I think; some of the checks implicitly exclude or manipulate dead code.

laytonio marked an inline comment as done.Jun 23 2020, 7:01 PM
laytonio added inline comments.
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
774

I feel like I may be misunderstanding what you're saying. In your example you are passing in a function with a dead block. Where as this only applies to something like the following:

define i32 @foo() {
  %z = call i32 @foo()
  br label %retblock

retblock:
  ret i32 %z
}

Where we transform to this:

define i32 @foo() {
  %z = call i32 @foo()
  ret i32 %z

retblock:
  ret i32 %z
}

In order to eliminate the call. Is it not valid to just delete the now dead block? It seems a little bug prone to just RAUW when the replacement doesn't maintain the semantics, but that is just my opinion.

efriedma added inline comments.Jun 23 2020, 7:48 PM
llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp
774

The general point is just that if you haven't run removeUnreachableBlocks, there can unreachable uses floating around of any instruction that defines a value. Before you erase an instruction, you have to erase/fix any uses of that instruction. To erase a basic block, you have to erase every instruction in that basic block.

Actually, taking another look at this, I guess it isn't possible to have an instruction with uses at this point. We checked that the only instructions in the block are phi, debug intrinsics, and return. FoldReturnIntoUncondBranch eliminates any phi nodes, and debug intrinsics and return don't define a value. So I guess you're right, we're okay here.

avl added a subscriber: avl.Jul 12 2020, 3:03 PM

I'll wait and rebase after D82085.

It looks like D82085 needs more work(it did not pass two staged build). I suggest not to wait D82085 and go head with D82269.

laytonio updated this revision to Diff 277628.Jul 13 2020, 6:10 PM

Remove hasAddressTaken check
Update comment
Use pred_empty

laytonio marked 3 inline comments as done.Jul 13 2020, 6:11 PM
efriedma accepted this revision.Sep 17 2020, 6:02 PM

LGTM. Sorry about the delay.

This revision is now accepted and ready to land.Sep 17 2020, 6:02 PM

Thanks for the review! Could you commit this for me?

This revision was automatically updated to reflect the committed changes.