Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

change contents of ScalarEvolution from private to protected #83052

Open
wants to merge 15 commits into
base: main
Choose a base branch
from

Conversation

skewballfox
Copy link

@skewballfox skewballfox commented Feb 26, 2024

hi, new to contributing to LLVM. Necessary to resolve Enzyme#1607. Enzyme inherits from ScalarEvolution and was previously relying on #define private public to make this work.

I ran this through clang format, and compiled both locally, if there is more test I need to run prior to pushing commits to PRs in the future, please let me know

SE Methods that still need to be modified

  • loopIsFiniteByAssumption
  • computeExitLimit
  • computeExitLimitFromCond (no change)
  • computeExitLimitFromCondCached (no change)
  • computeExitLimitFromCondImpl
  • computeExitLimitFromSingleExitSwitch
  • howManyLessThans
  • computeExitLimitFromICmp

update:

So I've finished adding the code from MustExit into SE, and the additions are passing the existing test. Need to add some new test for checking the added code though. If there are existing test in Enzyme that need to be migrated, I'd appreciate someone pointing those out to me. Searching for references to MustExitScalarEvolution wasn't returning any results where it was being directly tested under enzyme/test/Enzyme

Some of the code from MustExitScalarEvolution was copied from llvm main as of 3 years ago. I looked up the date that those changes were integrated, and this is the version of ScalarEvolution just prior to that date. I'm checking the diffs to see what parts of the additions for Enzyme can be reworked or removed.

Copy link

Thank you for submitting a Pull Request (PR) to the LLVM Project!

This PR will be automatically labeled and the relevant teams will be
notified.

If you wish to, you can add reviewers by using the "Reviewers" section on this page.

If this is not working for you, it is probably because you do not have write
permissions for the repository. In which case you can instead tag reviewers by
name in a comment by using @ followed by their GitHub username.

If you have received no comments on your PR for a week, you can request a review
by "ping"ing the PR by adding a comment “Ping”. The common courtesy "ping" rate
is once a week. Please remember that you are asking for valuable time from other developers.

If you have further questions, they may be answered by the LLVM GitHub User Guide.

You can also ask questions in a comment on this PR, on the LLVM Discord or on the forums.

@llvmbot
Copy link
Collaborator

llvmbot commented Feb 26, 2024

@llvm/pr-subscribers-llvm-analysis

Author: Joshua Ferguson (skewballfox)

Changes

hi, new to contributing to LLVM. Necessary to resolve Enzyme#1607. Enzyme inherits from ScalarEvolution and was previously relying on #define private public to make this work.

I ran this through clang format, and compiled both locally, if there is more test I need to run prior to pushing commits to PRs in the future, please let me know


Full diff: https://github.com/llvm/llvm-project/pull/83052.diff

1 Files Affected:

  • (modified) llvm/include/llvm/Analysis/ScalarEvolution.h (+1-1)
diff --git a/llvm/include/llvm/Analysis/ScalarEvolution.h b/llvm/include/llvm/Analysis/ScalarEvolution.h
index 0880f9c65aa45d..1b03437de30c28 100644
--- a/llvm/include/llvm/Analysis/ScalarEvolution.h
+++ b/llvm/include/llvm/Analysis/ScalarEvolution.h
@@ -1345,7 +1345,7 @@ class ScalarEvolution {
     }
   };
 
-private:
+protected:
   /// A CallbackVH to arrange for ScalarEvolution to be notified whenever a
   /// Value is deleted.
   class SCEVCallbackVH final : public CallbackVH {

Copy link
Member

@wsmoses wsmoses left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM but let's wait to see if there are any comments from others first.

@nikic nikic requested review from fhahn and preames February 26, 2024 20:26
Copy link
Contributor

@nikic nikic left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Not a fan of doing this, as a matter of principle. What you are doing in MustExecuteScalarEvolution is a bad idea, and I do not want to endorse it. You should try to upstream your changes, though I suspect that at least some of them are better handled in other ways.

@wsmoses
Copy link
Member

wsmoses commented Feb 26, 2024

I'm also a fan of the MustExitScalarEvolution functionality being merged upstream as the proper solution (e.g. perhaps a flag that indicates that SE can assume all loops terminate, independent of the existence of LLVM Loop metadata to specify).

For context, the usage of MustExitScalarEvolution within Enzyme, is that unlike regular SE which has additional checks for exiting, users of MustExitSE are performing analysis within a context where these checks are unnecessary (and substantially decremental for performance). Specifically they are used to compute the maximum number of values from the original program which may need to be explicitly preserved. A separate check for termination is not needed, since the newly generated code will only run after the original code (and thus an infinite loop will never result in the generated code being run). Failure to deduce a fixed loop size, however, results in the values being stored in a dynamically resized list rather than a fixed-size array.

@skewballfox since you're a first time LLVM contributor (who was trying to use Enzyme on Windows and found this was able to help remedy and made this PR), I'm revoking my approval and this should not be merged until the discussion has concluded.

@wsmoses
Copy link
Member

wsmoses commented Feb 26, 2024

@skewballfox a much bigger lift, but would you be able to add the optional must-exit functionality into SE itself?

cc @matinraayai

@skewballfox
Copy link
Author

you're a first time LLVM contributor (who was trying to use Enzyme on Windows and found this was able to help remedy and made this PR),

I'm actually on fedora and someone mentioned this as a good place to start contributing to LLVM coming from rust.

a much bigger lift, but would you be able to add the optional must-exit functionality into SE itself?

I can do that, or at least attempt to. Noob question, how should I go about testing changes to ScalarEvolution? I'm guessing there are some relevant test under enzyme I should migrate with that as well?

@wsmoses
Copy link
Member

wsmoses commented Feb 26, 2024

Being slightly lazy and looking up an old PR which did related things, maybe 99d2582#diff-1e66dd3ceb17c18388ad57f6e7a16e77a836ab1420975572a95b66727a529299 is a good starting point

@fhahn
Copy link
Contributor

fhahn commented Feb 26, 2024

Not a fan of doing this, as a matter of principle.

I agree, it would be better to address this upstream.

@nikic
Copy link
Contributor

nikic commented Feb 27, 2024

Note that marking the function as willreturn will already make SCEV assume that loops in the function are finite.

@wsmoses
Copy link
Member

wsmoses commented Feb 27, 2024

@nikic yeah I'm not sure willreturn will work in this case, since the original input function may not be willreturn. E.g. we don't re-optimize the function (including from other calling contexts) with willreturn, but this addition is only needed for cache size calculations which are only used if at runtime the function returned from the original code.

@skewballfox
Copy link
Author

skewballfox commented Feb 27, 2024

sorry if ask any dumb questions, my c++ is a bit rusty.

Would it be acceptable to make ExitLimitCache public? I'm in the process of making MustExitScalarEvolution a public nested class of ScalarEvolution. Currently MustExitScalarEvolution depends on ExitLimitCache, and the former needs to be public for it's use in Enzyme

@nikic
Copy link
Contributor

nikic commented Feb 27, 2024

@nikic yeah I'm not sure willreturn will work in this case, since the original input function may not be willreturn. E.g. we don't re-optimize the function (including from other calling contexts) with willreturn, but this addition is only needed for cache size calculations which are only used if at runtime the function returned from the original code.

Ah, you are running SCEV on the original function, not the new one Enzyme is generating? Then yeah, marking it as willreturn wouldn't be right and you do need some kind of flag or hook.

@wsmoses
Copy link
Member

wsmoses commented Feb 27, 2024 via email

@skewballfox
Copy link
Author

I'm starting to get this implemented. In order to avoid taking the implementation in the wrong direction, I'd like to get feedback whether this is a solution you guys are okay with:

  • moving ScalarEvolutionMustExit out of Enzyme and into the headers and source files for ScalarEvolution, in the llvm namespace but outside of ScalarEvolution, and moving any necessy utility functions into a new file under Analysis/Utils/EnzymeFunctionUtils
  • declaring ScalarEvolutionMustExit as a friend class within ScalarEvolution
  • changing the instantiation of ScalarEvolutionMustExit to take a reference to a ScalarEvolution instance, and stores that internally

If you guys would prefer this to be handled another way, let me know. totally open to suggestions

@wsmoses
Copy link
Member

wsmoses commented Feb 27, 2024 via email

@wsmoses
Copy link
Member

wsmoses commented Feb 27, 2024 via email

Copy link

github-actions bot commented Feb 29, 2024

✅ With the latest revision this PR passed the C/C++ code formatter.

@skewballfox
Copy link
Author

I wasn't sure if you meant for me to integrate the flag into the existing code like the ScalarPredicate or NoWrap flags, so I added one directly to ScalarEvolution. I'll start pushing after each method. If at any point I need to change something about the implementation, let me know

@skewballfox
Copy link
Author

Just a heads up, I'm not done I finished moving the methods but I need to port existing test and look into the ci check errors.
Hopefully will finish before Monday

@skewballfox skewballfox requested a review from nikic March 1, 2024 20:04
Copy link
Contributor

@nikic nikic left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It looks like a lot of the changes here are not really changes from Enzyme, but failures to integrate upstream SCEV changes back into Enzyme's copy. These should be dropped from this patch (and maybe ported to Enzyme's copy independently of this PR?)

llvm/include/llvm/Analysis/ScalarEvolution.h Outdated Show resolved Hide resolved
llvm/lib/Analysis/ScalarEvolution.cpp Outdated Show resolved Hide resolved
llvm/lib/Analysis/ScalarEvolution.cpp Outdated Show resolved Hide resolved
llvm/lib/Analysis/ScalarEvolution.cpp Outdated Show resolved Hide resolved
llvm/lib/Analysis/ScalarEvolution.cpp Outdated Show resolved Hide resolved
llvm/lib/Analysis/ScalarEvolution.cpp Outdated Show resolved Hide resolved
// TODO note this doesn't go through [loop, unreachable], and we could get more
// performance by doing this can consider doing some domtree magic potentially
static inline llvm::SmallPtrSet<llvm::BasicBlock *, 4>
getGuaranteedUnreachable(llvm::Function *F) {
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@wsmoses Could you please provide some context on what's up with this whole "guaranteed unreachable" logic?

Copy link

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

ping @wsmoses

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Ah, yeah so basically the gist is as follows.

Suppose we have some code from the loop that results in unreacahble blocks. For example:

for (int i=0; i<N; i++) {
    if (i > array.size()) {
       printf("Bounds error\n");
       exit(1);
    }
    something(i);
}

Again in our (enzyme) case here, we can assume we only need the loop limits if we successfully run the function (e.g. exit via a return). Thus we'd prefer to learn that this look has a bound of N, rather than unknown (since otherwise the loop could exit at an arbitrary time, via an exit call / unreachable).

This actually makes a huge performance difference in practice since a lot of codes have this bounds checking (and other related things), and not deducing the fixed bound forces us to use a dynamic reallocation rather than a static allocation size of N.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The guaranteed unreachable stuff is basically finding blocks/paths which are guaranteed to result in unreachable. E.g. if you had something like

if (Condition) {
  a()
} else {
 b()
}
exit(); // aka unreachable

we can ignore this entire sub-cfg even if the individual blocks terminators are not unreachable (since any path through the block will necessarily result in an unreachable).

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

In the context of SE, I think the best way to integrate this may be a list of blocks/branches/etc for SE to ignore in the context of computing the available exits.

In this context we're choosing ones that are guaranteed to hit unreachable, but I think the nicer one to integrate would be something along the lines of IgnoredExitingBlocks. Of course to properly test this we may need to still have a version of getUnreachable somewhere to build a version of the SE exiting for loop test, but that way SE remains general

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@preames preames removed their request for review March 13, 2024 21:27
@skewballfox
Copy link
Author

skewballfox commented Mar 15, 2024

@nikic I've finished the changes you requested. The only thing left is to test Scalar Evolution with AssumeLoopExit set to true. I see from the LLVM docs this is supposed to be a regression test

I'm still working out the details of how this should be done. Here's my very fuzzy understanding of what needs to happen

  • I either generate new llvmIR code (how wsmoses did using godbolt), or reuse the existing ir code under llvm/test/Analysis/ScalarEvolution to capture the baseline behavior
  • I add an ifdef macro to set assumeLoopExist to true when instantiation SE, similar to how EXPENSIVE_CHECKS works. I have that locally but haven't pushed it
  • I suspect I'm diffing the two the actual vs expected change.

Is that rough sketch correct? how do I integrate test for this feature with the existing test? I'm not seeing anything relevant to ScalarEvolution or analysis in llvm-test-suite when searching keywords

EDIT: btw, I plan on squashing the commits and resolving the conflicts after getting confirmation everything else is done. I went to do it yesterday but saw where in the docs they recommend holding off on rebasing to make changes easier to track

@ZuseZ4
Copy link

ZuseZ4 commented Mar 30, 2024

ping @nikic Do you have any hints for him on what testcases to add?

@OwenTrokeBillard
Copy link

Great work everyone. What is blocking this, if anything? It appears to be essentially ready but with no activity for a while.

If @nikic is busy, is anyone else available to take a look?

llvm/include/llvm/Analysis/ScalarEvolution.h Outdated Show resolved Hide resolved
llvm/include/llvm/Analysis/ScalarEvolution.h Outdated Show resolved Hide resolved
llvm/include/llvm/Analysis/Utils/EnzymeFunctionUtils.h Outdated Show resolved Hide resolved
llvm/lib/Analysis/ScalarEvolution.cpp Outdated Show resolved Hide resolved
llvm/lib/Analysis/ScalarEvolution.cpp Outdated Show resolved Hide resolved
@nikic
Copy link
Contributor

nikic commented Apr 17, 2024

You'll want to test this via unit tests in llvm/unittest/Analysis/ScalarEvolutionTest.cpp. I'd recommend to split this up into multiple PRs:

  • Add the AssumeLoopExits flag. Only check this inside loopIsFiniteByAssumption() and just add one test for it (because we already have coverage for the general functionality).
  • Add the GuaranteedUnreachable functionality. This will need a test for each place you check it. I think the GuaranteedUnreachable checks don't need to be guarded by AssumeLoopExits, this seems largely orthogonal.
  • Other changes done by Enzyme -- though it still looks like most of these are just Enzyme having outdated code and not actually changes we want to do. Only the PROP_PHI change looks obviously intentional.

Copy link
Collaborator

@efriedma-quic efriedma-quic left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

If I'm understanding the discussion correctly, the value the Enzyme code ultimately needs is "if the loop exits via the given edge, what was the backedge-taken count"? This is not something we currently compute because it's not that useful for most of the transforms we care about: for example, if you're fully unrolling a loop, you need to prove the loop actually exits. But as noted before, it's useful if you want to compute values on exit from a loop. indvars could use it to rewrite exit values if it was available.

Given that, I don't think adding a flag to ScalarEvolution to change its behavior is the right approach. We don't really want to to change the meaning of existing interfaces. We just want to add a new API to BackedgeTakenInfo to ask for this info. And then, instead of bailing out of the exit-limit computation when we can't prove the loop is finite, we just do the computation anyway, and mark the computation as "only valid if the loop actually exits via this edge" in the BackedgeTakenInfo. So only the new API returns the computed result.

The resulting modifications look pretty similar: instead of making AssumeLoopFinite skip checks that would bail out, just make those checks set a boolean in the returned BackedgeTakenInfo.

In this approach, you shouldn't need GuaranteedUnreachable, I think; the "unreachable" edges would still be there, but they wouldn't block relevant computations.


I suspect just pretending the other exits don't exist could lead to subtly wrong results in ScalarEvolution::howManyLessThans, when it sets nowrap flags on some generated expressions.

if (!EnableFiniteLoopControl || !ControllingFiniteLoop ||
!isLoopInvariant(RHS, L))
break;
RHS = getAddExpr(getOne(RHS->getType()), RHS);
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The assignment to RHS should be outside the "if"?

if (IsSigned)
RHS = getAddExpr(sv, SCEV::FlagNSW);
else
RHS = getAddExpr(sv, SCEV::FlagNUW);
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This looks like duplicated code from above (the EnableFiniteLoopControl bit).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Build with Clang + MSVC
8 participants