This is an archive of the discontinued LLVM Phabricator instance.

[DomTreeUpdater] Ignore updates when both DT and PDT are nullptrs
ClosedPublic

Authored by NutshellySima on Jul 5 2018, 8:03 AM.

Details

Summary

Previously, when both DT and PDT are nullptrs and the UpdateStrategy is Lazy, DomTreeUpdater still pends updates inside.
After this patch, DomTreeUpdater will ignore all updates from(applyUpdates()/insertEdge*()/deleteEdge*()) in this case. (call delBB() still pends BasicBlock deletion until a flush event according to the doc).
The behavior of DomTreeUpdater previously documented won't change after the patch.

Diff Detail

Event Timeline

NutshellySima created this revision.Jul 5 2018, 8:03 AM
kuhar added a comment.Jul 9 2018, 8:40 AM

Have you considered detecting that both trees are null and overriding the update strategy to Eager in that case? I think that should functionally be equivalent, although more confusing when the strategy you get can be different from what someone just set :P I'm just wondering what pros/cons there are.

lib/IR/DomTreeUpdater.cpp
346

Same as below.

392

Can you save some work by moving it at the top of the function such that it doesn't have to validate updates if both trees are null?

Or is it intentional to validate them and catch some logic errors in this case as well?

(call delBB() still pends BasicBlock deletion until a flush event according to the doc).

This is an interesting idea as it gives callers a deferred deletion tool for Lazy and both trees are nullptr. It'd be worthwhile to add documentation somewhere to let others know about this. I know of at least one case when I was working on JumpThreading that the original code flushed LVI information about a block because it called an external routine that might delete the block (it was at the end of runImpl()). This feature gives others a simple way of calling potentially destructive calls, checking the return code, and cleaning up on success or failure.

Have you considered detecting that both trees are null and overriding the update strategy to Eager in that case? I think that should functionally be equivalent, although more confusing when the strategy you get can be different from what someone just set :P I'm just wondering what pros/cons there are.

  1. If I override the UpdateStrategy to Eager when both DT* and PDT* are nullptrs, users may be confused if they use DTU as the following
// An imaginary pass which tries to preserve both DT and PDT. It uses DTU inside so it doesn't need to deal with both strategies.
// We get DT* and PDT* from the pass manager.
void f() {
  DomTreeUpdater DTU (DT, PDT, Lazy); // Both DT and PDT are nullptrs.
  BasicBlock* BB = ...;
  ...
  DTU.delBB(BB); // Caller doesn't expect BB be deleted here.
  ... // Still try to access BB.
}

If the pass gets DT and PDT successfully, it will work. But if it can't access both DT and PDT, it will break.
I think this behavior will make others confused.

  1. So I add logic to ignore updates rather than making DTU with both DT/PDT==nullptr functionally equivalent with Eager ones.

(call delBB() still pends BasicBlock deletion until a flush event according to the doc).

This is an interesting idea as it gives callers a deferred deletion tool for Lazy and both trees are nullptr. It'd be worthwhile to add documentation somewhere to let others know about this. I know of at least one case when I was working on JumpThreading that the original code flushed LVI information about a block because it called an external routine that might delete the block (it was at the end of runImpl()). This feature gives others a simple way of calling potentially destructive calls, checking the return code, and cleaning up on success or failure.

Yes, I think we can document it.

lib/IR/DomTreeUpdater.cpp
392

Previously, I think because *Relaxed functions need to inspect whether the update is valid (it must be checked when DT!=null && PDT!=null), so I add a return value to indicate whether the update is valid.
Now, because there isn't any user of this return value, so I think it's better to remove the return value and move this upward.

Address comments.
Change return type of *Relaxed into void and avoid unnecessary checks.

NutshellySima marked 3 inline comments as done.Jul 11 2018, 10:15 AM
kuhar accepted this revision.Jul 11 2018, 10:20 AM

LGTM, but please wait to see if @brzycki has some comments before submitting the patch

This revision is now accepted and ready to land.Jul 11 2018, 10:20 AM

@NutshellySima I think you said that BasicBlocks that are deleted with deleteBB() aren't removed immediately and are held until a a flush() event, correct? I don't see any comments informing the users that this is the case. I consider it to be unexpected behavior and should be noted.

Code-wise it LGTM as well.

Add the doc on the behavior of deleteBB() when both DT and PDT are null under Lazy Strategy.

NutshellySima set the repository for this revision to rL LLVM.

Amend the document.

This revision was automatically updated to reflect the committed changes.