Page MenuHomePhabricator

[MIR] Improve PRE condition of MachineCSE optimization
AcceptedPublic

Authored by anton-afanasyev on Jun 28 2019, 8:03 AM.

Details

Summary

Two equal instrs are partially redundant if their basic blocks are reachable
from one to another but one doesn't dominate another. For this case
one can hoist them to their common dominator block. But such hoisting makes
optimization sense only if their blocks are reachable from one to another
without passing through their common dominator. This change makes this check
preventing PRE from useless instr duplication (leading to hoisting after CSE
elimination).

Event Timeline

Herald added a project: Restricted Project. · View Herald TranscriptJun 28 2019, 8:03 AM

(is this missing a test?)

(is this missing a test?)

Oops, sure, I'm to add it.

Ping!
This patch fixes https://llvm.org/pr42405 implicitly.

asbirlea added inline comments.Jul 8 2019, 3:03 PM
llvm/lib/CodeGen/MachineCSE.cpp
824

Unrelated with this patch: Check CMBB != nullptr?

anton-afanasyev marked 2 inline comments as done.Jul 8 2019, 3:15 PM
anton-afanasyev added inline comments.
llvm/lib/CodeGen/MachineCSE.cpp
824

Good point, I haven't faced this issue, but this is actually potentially a bug. I'm to include fix right to this patch. Thank you!

anton-afanasyev marked an inline comment as done.

Add small fix

Just to make sure I understand the change correctly:
This can still hoist instructions outside of their BB and execute them speculatively even if you can't prove that all possible paths execute the instruction, am I right?

Just to make sure I understand the change correctly:
This can still hoist instructions outside of their BB and execute them speculatively even if you can't prove that all possible paths execute the instruction, am I right?

Hi @aymanmus, yes, you are right, and this fact is confusing me. You are right -- the speculativeinstruction execution shouldn't be possible after optimization, even if the average performance is growing up. This wasn't intented when I implemented PRE, I'm to take actions for fixing this.

Thanks Anton.
Can you please keep us updated with any progress in this regard?

Thanks Anton.
Can you please keep us updated with any progress in this regard?

Sure. I'm to take one-two days more for fixing effort, otherwise I will have to revert my original commit.

Hi all! I've figured out that my current implementation of PRE is incorrect and it needs to be either corrected, restricted or reverted.
The issue is that current PRE can actually hoist instruction executing it speculatively for some CFG paths which potentially leads to perf degradation. However I believe that current heuristic PRE is rather useful if it is restricted enough. Good restriction (apart from this revision) is implemented by @lkail here: https://reviews.llvm.org/D64394, it is based on basic block frequencies comparision.

@asbirlea, @aymanmus, @igorb -- does this restriction solve your particular issues with perf degradation?
Yes, this restriction still allows speculative execution (so one need to forbid hoisting of "illegal" instructions like throwable ones), but this execution consider to be beneficial.

igorb accepted this revision.Tue, Aug 13, 4:10 AM

LGTM

This revision is now accepted and ready to land.Tue, Aug 13, 4:10 AM