LGTM. How to change NeedRevision flag?

I don't have strong preference for bwd direction. Let's get this fix in. Are all tests and sanities passing?

Thank you for checking on mainMBB and fallBB. Which direction: forward or backward - do you prefer for isEFLAGSLiveAfter()?

Yes, check for mi.killsRegister(X86::EFLAGS)) before a def (in backward order).
The instructions in mainMBB and fallBB during xbegin() expansion do not deal with EFLAGS. If a subsequent pass makes changes in mainMBB and fallBB that might impact the liveness of EFLAGS, that pass should make proper updates. Having

mainMBB->addLiveIn(X86::EFLAGS);
fallMBB->addLiveIn(X86::EFLAGS);

is good too.

Hi Craig, thank you for working on this bug.

Where is the Xtensa instruction set architecture (ISA) document on which this patch is based on?

Hi Mitch,

Hi David, Diego, thanks for the comments. Sorry for the delayed response.

Agree, but this depends what tests/apps we are concerned about. LNT tests didn't show many outliers.
In addition to Chromium, which applications have been known as outliers in terms of DSE compile-time contribution in the past?

Hi Chad, thanks for helping with that. Is compile-time increase the remaining problem?
One quick fix could be to change 100 to 10 for the max number on non-local attempts in a function:

static const unsigned MaxNonLocalAttempts = 100;

We've chosen 100 arbitrarily. The newly added DSE tests should pass with 10.

LGTM

Thanks, Chad. Can we commit the patch at this point?
It solves one DSE enhancement known for several years.
I believe the patch has been thoroughly reviewed and tested.

Mitch, I added a relevant comment above DT->dominates(BB, Pred).

Added a comment to clarify avoidance of blocks (to search for redundant stores) that form a cycle with BB, as requested by Mitch.
Update to ToT is not necessary because the recent changes to DeadStoreElimination.cpp has been reverted.

ping?

Could someone with commit access commit this patch, if there is no objection from reviewers?

Hi Bruno,

Any objection to commit this patch?

Added option -enable-nonlocal-dse to enable/disable the feature.

Hi Bruno,

Hi Bruno, the patch has been rebased, and should apply cleanly on ToT.

Rebased.
Address Mitch's comments.

Thanks, Bruno. If necessary we need to balance non-local DSE for compile-time and run-time performance.

addressed two comments by Mitch

Hi Bruno,

Hi Mitch, thanks for the thoughtful comments; we are making a good progress.
I will make the two changes: using successor iterator and adding the comment, in the next revision.

ping?

ping?

changes for style and coding standards

Thanks for suggestions/comments, Mitch. My responses are inlined below.

The new version now handles a redundant store in the if-block in if-then-else - based on a suggestion by Mitch. We use SafeBlocks set, which is initialized and updated in DSE::HandleNonLocalDependency() and used in helper FindSafePreds(). SafeBlocks keeps track of all predecessor blocks that are safe to search through. A new test - ifthenelse.ll - has been added.

ping?

Addressed Erik's comments:
*) Your algorithm has quadratic complexity in worst case. I know this is the same as for the single block algorithm, but extending it to multiple blocks might worsen the situation. Maybe you add some sort of upper bound for the number of dependency checks?

Note that the code for BB DSE stays the same, it is just indented two spaces to the right.
The new code begins at:

// DSE across BB
else if (InstDep.isNonLocal()) { ...

and it includes helper FindUncondPredsIncludingSimpleLoops().