Page MenuHomePhabricator

mkazantsev (Max Kazantsev)
User

Projects

User does not belong to any projects.

User Details

User Since
Jan 23 2017, 8:11 PM (229 w, 2 d)

Recent Activity

Today

mkazantsev updated the diff for D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

Returned integer type check of branch conditions, removed test TODOs, removed null TTI with non-null DT which looks extremely fishy.

Thu, Jun 17, 6:29 AM · Restricted Project
mkazantsev planned changes to D104111: [LoopDeletion] Support selects when symbolically evaluating 1st iteration.

Per underlying patch change

Thu, Jun 17, 5:56 AM · Restricted Project
mkazantsev planned changes to D103959: [LoopDeletion] Handle Phis with similar inputs from different block.

Per underlying patch change

Thu, Jun 17, 5:56 AM · Restricted Project
mkazantsev updated the diff for D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

Reworked using InstSimplify. It's good enough for my case. Let's hope that at least this has acceptable CT overhead.

Thu, Jun 17, 4:46 AM · Restricted Project
mkazantsev planned changes to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

Then trying InstSimplify...

Thu, Jun 17, 3:43 AM · Restricted Project
mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

:(

Thu, Jun 17, 3:41 AM · Restricted Project
mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

Oh, thanks! Didn't notice that. I'll now try to prototype an alternative solution with InstSimplify. But honestly, I'd be super surprised if SCEV's non-recursive prove is more expensive than this (and clearly SCEV's canonicalization is more powerful).

Thu, Jun 17, 3:09 AM · Restricted Project
mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

This is surprising to me -- why does this require changes to InstSimplify?

InstSimplify does not provide public API for this:

const SCEV *LHSS = getSCEVOnFirstIteration(LHS, L, SE, FirstIterSCEV);
const SCEV *RHSS = getSCEVOnFirstIteration(RHS, L, SE, FirstIterSCEV);
S = SE.getAddExpr(LHSS, RHSS);

It has SimplifyAddInst that works with custom arguments, but it's currently static within the cpp file. I'd need to expose all of them. At least this, maybe more.

Thu, Jun 17, 2:50 AM · Restricted Project
mkazantsev updated the diff for D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

Cut down to non-recursive reasoning. @nikic could you please check the CT impact? If it's now, then it's all about complex recursive rules of proof, and this is where we can seek to simplify SCEV's reasoning.

Thu, Jun 17, 2:46 AM · Restricted Project
mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

@reames

One thing I'm wondering about is whether we're invalidating SCEV too aggressively in one of the existing transforms. I don't have strong evidence of this, but computing SCEVs for a loop isn't *that* expensive, and given a properly structured loop pipeline should happen approximately once. I'd be tempted to instrument the various "forgetX" calls and run one of the worst offenders compile time wise. Do all of the invalidation make sense? Just based on a quick skim of the code, I see a couple call sites in LoopSimplifyCFG and IndVarSimplify which look likely to invalidate far more than is required. In particular, if we were invalidating multiple times in a loop nest, that could cause degenerate compile time.

Thu, Jun 17, 1:56 AM · Restricted Project

Tue, Jun 15

mkazantsev added a comment to D104319: [SCEV] Retain AddExpr flags when subtracting a foldable constant..

+1 to what Eli said.

Tue, Jun 15, 10:02 PM · Restricted Project
mkazantsev accepted D104322: [SCEV] PtrToInt on non-integral pointers is allowed.
Tue, Jun 15, 9:48 PM · Restricted Project
mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

P.S. and as for SCCP - that's a good point I didn't think of. Need to make some experiments to see if it helps.

Tue, Jun 15, 1:14 AM · Restricted Project
mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

Reducing my whole suggestion to absurd, if I win 0.2% CT somewhere else in SCEV, can we go with this?

Tue, Jun 15, 1:06 AM · Restricted Project
mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

Thanks Nikita, I think I have some arguments for this philosophical debate. :)

Tue, Jun 15, 1:04 AM · Restricted Project

Fri, Jun 11

mkazantsev requested review of D104111: [LoopDeletion] Support selects when symbolically evaluating 1st iteration.
Fri, Jun 11, 4:59 AM · Restricted Project
mkazantsev committed rG8840c94a3380: [Test] One more elaborate test with selects for loop deletion (authored by mkazantsev).
[Test] One more elaborate test with selects for loop deletion
Fri, Jun 11, 4:42 AM
mkazantsev committed rG8dc2c1a0abdd: [Test] Add loop deletion test with switch (authored by mkazantsev).
[Test] Add loop deletion test with switch
Fri, Jun 11, 4:05 AM
mkazantsev accepted D104066: [SCEV] Use knowledge of stride to prove loops finite for LT exit count computation.

Looks fine, but agreed with Eli. Please don't land it for some more days to find and fix miscompiles from underlying patches (if any).

Fri, Jun 11, 2:51 AM · Restricted Project
mkazantsev accepted D104075: [ScalarEvolution] Merge howManyGreaterThans with howManyLessThans..

LGTM, but I think we can remove more copy-paste (see comment). Can go as follow-up.

Fri, Jun 11, 2:46 AM · Restricted Project

Thu, Jun 10

mkazantsev added a comment to D101970: [X86FixupLEAs] Transform the sequence LEA/SUB to SUB/SUB.

I'm a bit surprised that it wasn't reverted. The default policy is revert whatever is broken and then fix it. We have numerous internal failures & broken CI cycles because of this, and the fix is not merged yet (and not clear when it will be merged). @Carrot could you please revert this and return back along with fix?

Thu, Jun 10, 9:00 PM · Restricted Project

Wed, Jun 9

mkazantsev requested changes to D103991: [SCEV] Extend mustprogress reasoning to ne exit tests.

Please add tests for this this exit doesn't dominate the latch.

Wed, Jun 9, 9:32 PM · Restricted Project
mkazantsev added inline comments to D103959: [LoopDeletion] Handle Phis with similar inputs from different block.
Wed, Jun 9, 9:01 PM · Restricted Project
mkazantsev requested review of D103959: [LoopDeletion] Handle Phis with similar inputs from different block.
Wed, Jun 9, 5:46 AM · Restricted Project
mkazantsev committed rG0120e6c295e4: [Test] Add more elaborate case of symbolic execution of 1-iteration loop (authored by mkazantsev).
[Test] Add more elaborate case of symbolic execution of 1-iteration loop
Wed, Jun 9, 5:09 AM
mkazantsev added a comment to D100559: [GC][NFC] Make getGCStrategy by name available in IR.

So it's not a singleton, it's something that is cached inside of GCModuleInfo. And this patch preserves this behavior. You can as well say that SCEV constant 1 of type i32 is a singleton, but it's not: it is something that is cached within a particular instance of ScalarEvolution.

Wed, Jun 9, 1:32 AM · Restricted Project

Tue, Jun 8

mkazantsev added a comment to D103877: [SCEV] Keep common NUW flags when inlining Add operands..

Good point, I was not aware that the flags need to apply for any order of evaluation

Tue, Jun 8, 9:56 PM · Restricted Project
mkazantsev accepted D103877: [SCEV] Keep common NUW flags when inlining Add operands..

For nuw it should be fine. LGTM!

Tue, Jun 8, 9:54 PM · Restricted Project
mkazantsev accepted D103913: [LoopBoundSplit] Ignore phi node which is not scevable.
Tue, Jun 8, 9:50 PM · Restricted Project
mkazantsev added a comment to D103922: [X86FixupLEAs] Sub register usage of LEA dest should block LEA/SUB optimization.

I confirm that the initial miscompile we found gets fixed by this patch. I can't approve the patch because I'm not familiar with the component though.

Tue, Jun 8, 9:21 PM · Restricted Project
mkazantsev added a comment to D103877: [SCEV] Keep common NUW flags when inlining Add operands..

As far as I understand what is a nsw for multi-argument add, it means that there should be no wrap in between if we add the operands one by one in any order. Imagine the case when a = c = SINT_MIN and b = d = SINT_MAX. We can say that a+b has <nsw>, c+d has <nsw>, and (a+b) + (c+d) also has nsw. But if we say that getAddExpr(getAddExpr(a, b, nsw), getAddExpr(c, d, nsw), nsw) = getAddExpr(a, b, c, d, nsw), it's not true if we compute the latter as a + c + b + d. It will overflow on a + c already. Is my understanding wrong here?

Tue, Jun 8, 8:02 AM · Restricted Project
mkazantsev added a comment to D101970: [X86FixupLEAs] Transform the sequence LEA/SUB to SUB/SUB.

We are still observing a miscompile caused by the newer version of this patch. I'll try to provide you a repro.

Surely you can provide the .ll after middle-end optimizations?

Tue, Jun 8, 3:20 AM · Restricted Project
mkazantsev added a comment to D101970: [X86FixupLEAs] Transform the sequence LEA/SUB to SUB/SUB.

Filed https://bugs.llvm.org/show_bug.cgi?id=50615. The original repro is in Java, but I hope the logs there are enough to figure out what's going on. The log shows that the described transform did apply.

Tue, Jun 8, 1:45 AM · Restricted Project
mkazantsev added a comment to D101970: [X86FixupLEAs] Transform the sequence LEA/SUB to SUB/SUB.

We are still observing a miscompile caused by the newer version of this patch. I'll try to provide you a repro.

Tue, Jun 8, 12:35 AM · Restricted Project

Mon, Jun 7

mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

SCEV is much more powerful in terms of simplification. Imagine the situation when some Phi takes value of a + b + c on the 1st iteration (and unknown on all others), then gets subtracted by a, then by b, and then by c, and then the result is compared against zero. If we want InstSimplify to do something like this, we will need to re-implement recrusive expression aggregation, simplification, in summary - we will need to re-invent SCEV.

Mon, Jun 7, 9:13 PM · Restricted Project

Sun, Jun 6

mkazantsev added inline comments to D102234: [SimpleLoopBoundSplit] Split Bound of Loop which has conditional branch with IV.
Sun, Jun 6, 11:57 PM · Restricted Project
mkazantsev accepted D102234: [SimpleLoopBoundSplit] Split Bound of Loop which has conditional branch with IV.

My fuzzer didn't reveal any new failures, so there is a chance it's working as expected. :) LGTM with some nits.

Sun, Jun 6, 11:54 PM · Restricted Project
mkazantsev added a comment to D102234: [SimpleLoopBoundSplit] Split Bound of Loop which has conditional branch with IV.

I'm getting incline towards accepting this, but the fact that you keep finding bugs worries me. Please give me some time, I will run a corpus of Fuzzer tests with this pass locally to see if something breaks. If yes, I will try to give you a reproducer.

Sun, Jun 6, 8:49 PM · Restricted Project
mkazantsev added inline comments to D102234: [SimpleLoopBoundSplit] Split Bound of Loop which has conditional branch with IV.
Sun, Jun 6, 8:47 PM · Restricted Project
mkazantsev accepted D103118: [SCEV] Compute exit counts for unsigned IVs using mustprogress semantics.

Fine by me if you add a unit test which shows that it works as expected with volatile load.

Sun, Jun 6, 8:43 PM · Restricted Project
mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

Can we go ahead and merge it, or you want to further reduce the CT impact?

Sun, Jun 6, 8:35 PM · Restricted Project

Thu, Jun 3

mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

All failures so far were related to irreducible CFG (which made RPOT meaningless), which is now completely ruled out. @stefanp could you please check that this version works ok with PowerPC?

Thu, Jun 3, 2:39 AM · Restricted Project

Wed, Jun 2

mkazantsev added inline comments to D102234: [SimpleLoopBoundSplit] Split Bound of Loop which has conditional branch with IV.
Wed, Jun 2, 3:33 AM · Restricted Project
mkazantsev added a comment to D102234: [SimpleLoopBoundSplit] Split Bound of Loop which has conditional branch with IV.

Looking much better now. Few more nits & a question regarding ne, which is a potential correctness concern.

Wed, Jun 2, 3:28 AM · Restricted Project

Tue, Jun 1

mkazantsev accepted D102635: [LoopUnroll] Use tripcount from exiting header, if latch not exiting..

Looks ok by me, but please make sure you address Philip's concerns.

Tue, Jun 1, 11:46 PM · Restricted Project
mkazantsev added a comment to D102982: [LoopUnroll] Use smallest exact trip count from any exit.

Could you please mark it as "changes planned" until the underlying patch is ready or merged?

Tue, Jun 1, 8:32 PM · Restricted Project
mkazantsev accepted D103255: [LV] Mark increment of main vector loop induction variable as NUW..

Looks legit, thanks!

Tue, Jun 1, 8:31 PM · Restricted Project
mkazantsev accepted D103456: [NFC] Fix 'Load' name masking..
Tue, Jun 1, 8:28 PM · Restricted Project
mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

What are the latest compile time data for this patch?

There have been several separate follow-ups to address the compile time, but I believe we never measured it all together.

Could we get new data? @nikic? I am not sure if followups were not reverted as well so if follow up patches can recommited as NFC(I) patches, it would be great.

The followups were all reverted and integrated into this one. I see no point in merging them separately, unless we want more pain with reverts (if it is needed again). They are just part of the algorithm.

Nice, so only this patch needs to tested for compile time. But if less than +0.5%, it should be acceptable. There were many improvements in ct, so I do think there is some space for less cheap optimizations.

Tue, Jun 1, 3:20 AM · Restricted Project
mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

Can this patch optimize code from comment #4 in https://bugs.llvm.org/show_bug.cgi?id=47491 ?

Btw, any comment?

Let me check.

Tue, Jun 1, 3:18 AM · Restricted Project
mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

Can this patch optimize code from comment #4 in https://bugs.llvm.org/show_bug.cgi?id=47491 ?

Btw, any comment?

Tue, Jun 1, 2:42 AM · Restricted Project
mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

What are the latest compile time data for this patch?

There have been several separate follow-ups to address the compile time, but I believe we never measured it all together.

Could we get new data? @nikic? I am not sure if followups were not reverted as well so if follow up patches can recommited as NFC(I) patches, it would be great.

Tue, Jun 1, 2:42 AM · Restricted Project

Mon, May 31

mkazantsev added a comment to D103424: [IndVars] Don't forget value when inferring nowrap flags.

Did you try a lightweight (and absolutely NFCish) approach of dropping SCEV 1 time instead of 2? Like

if (!BO->hasNoUnsignedWrap() &&
    willNotOverflow(SE, BO->getOpcode(), /* Signed */ false, LHS, RHS)) {
  BO->setHasNoUnsignedWrap();
  Changed = true;
}
Mon, May 31, 11:42 PM · Restricted Project
mkazantsev updated the diff for D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

Root cause: another case of irreducible CFG I didn't filter out. As result, RPOT makes no sense. Checked in failing unit test as https://reviews.llvm.org/rG4ef47eaed952. Added an assert decting this.

Mon, May 31, 9:36 PM · Restricted Project
mkazantsev committed rG4ef47eaed952: [Test] Add one more loop deletion irreducible CFG test (authored by mkazantsev).
[Test] Add one more loop deletion irreducible CFG test
Mon, May 31, 9:12 PM
mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

Thanks, I was able to reproduce the failure locally. Investigating.

Mon, May 31, 7:27 PM · Restricted Project
mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

What are the latest compile time data for this patch?

Mon, May 31, 8:33 AM · Restricted Project
mkazantsev planned changes to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

Oh I see... That's nasty. In this case, could you please help me to reproduce it? I wasn't able to find the sources of this test in LLVM repository. IR dump before Loop Deletion would work too.

Mon, May 31, 8:28 AM · Restricted Project
mkazantsev added inline comments to D103118: [SCEV] Compute exit counts for unsigned IVs using mustprogress semantics.
Mon, May 31, 2:57 AM · Restricted Project
mkazantsev added inline comments to D103255: [LV] Mark increment of main vector loop induction variable as NUW..
Mon, May 31, 2:28 AM · Restricted Project
mkazantsev added inline comments to D102234: [SimpleLoopBoundSplit] Split Bound of Loop which has conditional branch with IV.
Mon, May 31, 2:09 AM · Restricted Project
mkazantsev added inline comments to D102234: [SimpleLoopBoundSplit] Split Bound of Loop which has conditional branch with IV.
Mon, May 31, 2:06 AM · Restricted Project

Sun, May 30

mkazantsev requested review of D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).
Sun, May 30, 11:10 PM · Restricted Project
mkazantsev updated the diff for D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

So far it seems that all problems are caused by compile time increase. There is already no room for shrinking the scope, so I'm returning this with option (turned off by default).

Sun, May 30, 11:10 PM · Restricted Project
mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

The last failure also looks like a timeout, I don't see any indication of miscompile:

FAIL: test-suite :: MultiSource/Benchmarks/MallocBench/gs/gs.test (73 of 2021)
******************** TEST 'test-suite :: MultiSource/Benchmarks/MallocBench/gs/gs.test' FAILED ********************
Sun, May 30, 10:24 PM · Restricted Project
mkazantsev planned changes to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).
Sun, May 30, 9:24 PM · Restricted Project
mkazantsev reopened D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).
Sun, May 30, 9:24 PM · Restricted Project
mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

Reviewing the failures, I see several issues that might be relevant:

Sun, May 30, 9:23 PM · Restricted Project
mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

Thanks for the revert! I'll see into what's happening.

Sun, May 30, 8:37 PM · Restricted Project

Thu, May 27

mkazantsev added a reverting change for rG51d334a845a0: [NFCI] Lazily evaluate SCEVs of PHIs: rG6a2af607ad35: Revert "[NFCI] Lazily evaluate SCEVs of PHIs".
Thu, May 27, 9:06 PM
mkazantsev committed rG6a2af607ad35: Revert "[NFCI] Lazily evaluate SCEVs of PHIs" (authored by mkazantsev).
Revert "[NFCI] Lazily evaluate SCEVs of PHIs"
Thu, May 27, 9:06 PM
mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

@nikic could you please run this one too? I think it can be useful in real cases with countable loops.

Thu, May 27, 2:17 AM · Restricted Project
mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

Added one more early bailout:

commit 7d418dadf6b1e6fd9bcccf7c5b5e1db74992ee70 (HEAD -> main, origin/main)
Author: Max Kazantsev <mkazantsev@azul.com>
Date:   Thu May 27 15:18:30 2021 +0700
Thu, May 27, 1:30 AM · Restricted Project
mkazantsev committed rG7d418dadf6b1: [NFCI][LoopDeletion] Do not call complex analysis for known non-zero BTC (authored by mkazantsev).
[NFCI][LoopDeletion] Do not call complex analysis for known non-zero BTC
Thu, May 27, 1:30 AM
mkazantsev committed rGc467585682dc: [NFC] Reuse existing variables instead of re-requesting successors (authored by mkazantsev).
[NFC] Reuse existing variables instead of re-requesting successors
Thu, May 27, 1:30 AM
mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

Thanks! I'll see what else can be done. Though, I think the right solution is to speed up SCEV queries in general and not try to cripple particular opts.

Thu, May 27, 12:54 AM · Restricted Project

Wed, May 26

mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

@nikic could you please evaluate impact of 2 patches above? They should do a great deal of decreasing SCEV usage.

Wed, May 26, 11:54 PM · Restricted Project
mkazantsev added inline comments to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).
Wed, May 26, 11:37 PM · Restricted Project
mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

This should also help:

commit 51d334a845a082338735b0fdfc620a4b15fa26fe (HEAD -> main, origin/main)
Author: Max Kazantsev <mkazantsev@azul.com>
Date:   Thu May 27 13:20:57 2021 +0700
Wed, May 26, 11:36 PM · Restricted Project
mkazantsev committed rG51d334a845a0: [NFCI] Lazily evaluate SCEVs of PHIs (authored by mkazantsev).
[NFCI] Lazily evaluate SCEVs of PHIs
Wed, May 26, 11:36 PM
mkazantsev committed rG59d938e649e6: [NFC] Formatting fix (authored by mkazantsev).
[NFC] Formatting fix
Wed, May 26, 10:51 PM
mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

One step to improve the situation:

commit b0b2bf3b5da950679db1431aae431a6dedea2245 (HEAD -> main, origin/main)
Author: Max Kazantsev <mkazantsev@azul.com>
Date:   Thu May 27 11:47:30 2021 +0700
Wed, May 26, 10:45 PM · Restricted Project
mkazantsev committed rGb0b2bf3b5da9: [NFCI][LoopDeletion] Only query SCEV about loop successor if another successor… (authored by mkazantsev).
[NFCI][LoopDeletion] Only query SCEV about loop successor if another successor…
Wed, May 26, 10:45 PM
mkazantsev added inline comments to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).
Wed, May 26, 9:34 PM · Restricted Project
mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

The best solution I can come up with (and it is something I even started to do at some point) is to replace two queries to isKnownPredicate with one which returns Optional<bool>, that should give up to 2x CT improvement. I'll think if we can get some minor CT wins here.

Wed, May 26, 9:29 PM · Restricted Project
mkazantsev accepted D102928: [unroll] Use SCEV to evaluate branch conditions in cost model.

LGTM, but mind that maybe we'll have to downgrade isKnownPredicateAt to isKnownPredicate if it harms the CT.

Wed, May 26, 5:52 AM · Restricted Project
mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

Commited fixed version (this time right one). Let's see how it goes.

Wed, May 26, 5:48 AM · Restricted Project
mkazantsev committed rGbe1a23203b1d: Return "[LoopDeletion] Break backedge if we can prove that the loop is exited… (authored by mkazantsev).
Return "[LoopDeletion] Break backedge if we can prove that the loop is exited…
Wed, May 26, 5:48 AM
mkazantsev added a reverting change for rG43d2e51c2e86: Return "[LoopDeletion] Break backedge if we can prove that the loop is exited…: rG0de553dce009: Revert "Return "[LoopDeletion] Break backedge if we can prove that the loop is….
Wed, May 26, 5:30 AM
mkazantsev committed rG0de553dce009: Revert "Return "[LoopDeletion] Break backedge if we can prove that the loop is… (authored by mkazantsev).
Revert "Return "[LoopDeletion] Break backedge if we can prove that the loop is…
Wed, May 26, 5:30 AM
mkazantsev added a reverting change for D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3): rG0de553dce009: Revert "Return "[LoopDeletion] Break backedge if we can prove that the loop is….
Wed, May 26, 5:30 AM · Restricted Project
mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).
Wed, May 26, 5:27 AM · Restricted Project
mkazantsev committed rG43d2e51c2e86: Return "[LoopDeletion] Break backedge if we can prove that the loop is exited… (authored by mkazantsev).
Return "[LoopDeletion] Break backedge if we can prove that the loop is exited…
Wed, May 26, 5:27 AM
mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

Yes, the point is, RPOT (or any other traversal) is undefined for any cycles, should they be inner loops or contained non-loop cycles. I think the best is not to deal with them at all. It never ended well for any opt. :)

Wed, May 26, 4:52 AM · Restricted Project
mkazantsev committed rG5fb58d45989d: [Test] Add Loop Deletion test with irreducible CFG (authored by mkazantsev).
[Test] Add Loop Deletion test with irreducible CFG
Wed, May 26, 4:40 AM
mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

Correctness of Loop RPOT is crucial for the correctness of this transform. If it's broken, its user is also broken. I see no good reason why RPOT for this loop is (bb2, bb12, bb4) and not (bb2, bb4, bb12). If someone has an idea, please let me know.

Wed, May 26, 4:04 AM · Restricted Project
mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

@uabelho you are right. The problem is loop RPOT processes blocks in order (bb2, bb12, bb4), which is not correct. The expected order is (bb2, bb4, bb12). No clue why this happened, investigating.

Wed, May 26, 3:41 AM · Restricted Project
mkazantsev committed rG7ee863b8ebfa: [Test] Add simplified versions of tests for loop deletion that don't need… (authored by mkazantsev).
[Test] Add simplified versions of tests for loop deletion that don't need…
Wed, May 26, 2:39 AM
mkazantsev committed rG794fb5482efc: [Test] Add test on unrolling to make sure it won't fail (authored by mkazantsev).
[Test] Add test on unrolling to make sure it won't fail
Wed, May 26, 2:31 AM
mkazantsev added a comment to D102615: [LoopDeletion] Break backedge if we can prove that the loop is exited on 1st iteration (try 3).

@uabelho Looking into your example, I don't think enough evidence it's a miscompile. Your test has non-side-effecting infinite loop, which has undefined behavior. So it's legal to make the replacement. Can you construct the example without an infinite loop?

Hm, is it really? For input 1, 1, 0 I think it terminates and return the value 20 after executing this path:

entry -> if.end -> bb2 -> bb4 -> bb12 -> bb2 -> bb4 ->bb13 -> ret

?

Wed, May 26, 2:21 AM · Restricted Project