Ping

Ping

Ping

Ping

I don't know, does it have any negative CT impact? If not, then I think this should be done.

Do we know if we can forget smth when strenghtening flags without harming the compile time to get the more precise resutlt in these cases?

D149648 shows that SCEV is more powerful than value tracking (the latter cannot figure out the range from dominating checks).

Bringing SCEV to LICM brings potential correctness issues. I'll rather try to support this in value tracking.

Ok, getting SCEV here brings potential correctness issues... Let's keep Value tracking.

Rolling back to SCEV version.

I'm planning to roll back to SCEV version. Value Tracking doesn't infer things from dominating conditions.

Rebased & split off sub code from add as Serguei and Anna have proposed.

NFC. Used m_NSWAdd.

Some NFC reafactoring due to request to untwine sub and add logic.

Fixed bug (typo) that caused messup with checks in tests. Bug was

if (ProvedNoOverflowAfterReassociate)
  return false;

instead of

if (!ProvedNoOverflowAfterReassociate)
  return false;

Friday evening refactoring is evil.

Err, indeed I messed up with test TODOs.

Typo fixed, check reduced to nsw check.

LG, thanks!

Is it possible to create a unit test?

Ok thanks, at least we'll know if it breaks.

If we prove that two values are the same, their SCEVs can also be proven the same (and not necessarity SCEVUnknown). If a load is equal to some non-load. then load's SCEV can be non-SCEVUnknown.

Consider example:

%sum = add i32 %x, %y
%load_p= gep ptr %p, i32 %sum
%load1 = load %i32 load_p

I agree that these two things should be the same.

This will require rebase.

In D148001#4295213, @skatkov wrote:

General question: don't you want to separate sub and add handling in completely different functions.
To be honest, there will be small code duplication but in this case no need to mixup add and sub logic.
It will be easier to review and support in the future.

If duplication is a problem you can create functions for sub and add to keep first and last lines are in common.

Reworked w/o SCEV, using ValueTracking's API as Nikita has proposed.

In D149132#4296348, @nikic wrote:

Proof: https://alive2.llvm.org/ce/z/imgdNt

Somewhat skeptical about introducing SCEV use in LICM. As you are actually reasoning about loop invariants here, do we need SCEV? Would using computeOverflowForSignedSub() from ValueTracking work, possibly even provide better results?

Just curious, what makes it so expensive? Is it SafetyInfo update?

I also agree that we should possibly consider dropping this transform at all.

Added even more comments.

Rebased on top of split off piece. I also tried to simplify the explanation and math formulae.

@anna I have split off the minimul piece of functionality as D149132. Will rebase this one now.

Ping

LG, thanks! It's better to have more verification than needed than less than needed. :) Bugs with corrupted caches are so annoying.

I don't quite understand your example. Two AddRecs with same start/step bound to one loop with different flags simply cannot exist, it would be one entity in UniqueSCEVs. And if we were able to infer nuw it for it in some situation, it means we have proven that it does not overflow (meaning that the loop doesn't make more than UINT_MAX iterations) regardless of uses. I don't think flag inference should rely on users at all, because there is expander, and it could create new uses out of thin air.

Please rebase.

LG, thanks

Confirmed with alive2.
Bugged version: https://alive2.llvm.org/ce/z/L4ps9v
Fixed version: https://alive2.llvm.org/ce/z/QdrG5U

I'd suspect that contextual analysis on SCEV creation might have negative CT impact.

Some style comments & request to see if smth is doable in verifier with this cache.

Whenever a new cache is introduced, it is highly recommended to add logic to ScalarEvoltion::verify for it to make sure it is sane. Can you please add that?

Bug fixed, logic expanded.