Patch was reverted due to issue witch cached MemDep result. There is a code like this:

%arrayidx248 = getelementptr inbounds [0 x i8], ptr @zz_lengths, i64 0, i64 %idxprom247
%cond.in.in = select i1 %switch8091, ptr %orec_size, ptr %arrayidx248
%cond.in = load i8, ptr %cond.in.in, align 1, !tbaa !5

And on second iteration of processBlock() %switch8091 value is proved to be false, so select is removed and replaced with %arrayidx248, but we didn't invalidate already cached SelectDep entry of load from first GVN iteration - need to figure out how to add this logic into MemoryDependenceResults::removeInstruction method.

Thank you for the review! I will wait some time in case of other reviewers' objections and then merge it.

In D142705#4112126, @mkazantsev wrote:

(we need only its condition and position to insert materialized value, so reporting select i1 %cond, i32 undef, i32 undef is ok: we don't care about its true and false values, addresses for %cond = true and %cond = false will be passed separately).

Then why can't you just always insert it on this block's terminator? Why iterate through its instructions and try to find this garbage?

Insert select before predecessor's terminator to simplify clobbers search

I want to put more context for this change that may cover some questions regarding the algorithm and its limitations. Let's consider the following simple case:

  BB1
  / |
BB2 |
  \ |
  BB3

Address review comments

In D143167#4102182, @mkazantsev wrote:

Looks reasonable. I'm not familiar with this code part in general, so please wait some time in case if someone has concerns, but looks pretty straightforward.

Update patch

Separate patch for removing isSafeToSpeculativelyExecute() checks: https://reviews.llvm.org/D143255

Added synthetic test for simplifyCastInst

Split patches

Split patch

Remove isSafeToSpeculativelyExecute() checks

Separate patch with code changes: https://reviews.llvm.org/D143171

Split renaming and code changes

Since naming conventions are indeed broken across many PHITransAddr methods, maybe it's worth to clean up them first.

Thank you for the reviews!

I have a question regarding code example: it looks like a case of load hoisting from SuccBB and basic block after splitting of (PredBB, LoadBB) critical edge. If so, the same result can be achieved by:

1. running SimplifyCFGOpt::HoistThenElseCodeToIf after GVN. Its implementation is very constrained (can hoist only first N exactly the same instructions from ThenBB and ElseBB, so very sensitive to instruction order)
2. Run GVNHoist pass after GVN -- the most general solution. Unfortunately it's disabled by default and placed before GVN in pass pipeline (although GVN exposes lots of hoisting opportunities, and its authors advise to run it before and after GVN-PRE).

Check that load types are matched (add negative test for that)

Rebase
Split pre-commit test

Treat select as Def dependency

Since extending MemDepResult looks not feasable (and replacing it to tag-pointer pair also looks bad because it frequently passed by value), I think we can treat select dependency as Def. It also fits naturally into existing GVN infra, and the meaning of Def dependency is already overloaded (it can be other load/store/alloca/memory intrinsic/etc.)

Split findDominatingLoad() rework into separate patch

Split AnalyzeLoadAvailability refactoring into separate patch: https://reviews.llvm.org/D141664

Ping (this pass is mostly profitable for RISC-V target, because zext on this target has non-zero cost, and the intention is to report Coremark results for RISC-V with this optimization enabled, like with DFA jump threading)

Compile-time results on llvm-test-suite + SPEC2006 + SPEC2017:

Program                                                                         loop-int-wrap-predication.NumPredicatedChains

Rebased on ToT
Add predication on separate conditions
Add simple cost model (do not predicate big loops)

Fix diff

Addressing review comments

Insert freeze of select condition