Re: [RFC] avoid type conversion through versioning loop
On Mon, Mar 22, 2021 at 7:41 AM guojiufu via Gcc wrote:
>
> Hi All,
>
> As we know, type conversion is not in favor of optimization, and may
> cause performance issue.
>
> For example:
> for (unsigned int i = 0; i < n; ++i)
>a[m + i] = 1; //or a[30 + i] =
>
> In this code, the index to access arrays is 'unsinged int' (32bit),
> while the register operations (like index increase i++) would on longer
> bits
> on 64bit machines, and then conversion between 32bits and 64bits and
> happen.
>
> 19: L19:
> 10: NOTE_INSN_BASIC_BLOCK 4
> 11: %9:DI=%5:DI<<0x2
> 17: %5:SI=%5:SI+0x1
> 18: %5:DI=zero_extend(%5:SI) #clear high 32bits
> 14: [%3:DI+%9:DI]=%10:SI
> 40: {pc={(ctr:DI!=0x1)?L19:pc};ctr:DI=ctr:DI-0x1;clobber scratch;clobber
> scratch;}
>
> In some cases, the shorter integer type would not overflow,
> and then the type conversion could be eliminated in some cases.
> So, I'm thinking of an optimization to avoid those conversions.
> The idea looks like current loop-versioning. Using the above example:
>
> for (unsigned int i = 0; i < n; ++i)
> a[30 + i] = 1;
>
> change to:
>
> if (n <= UINT_MAX) // ++i does not cause overflow, n + 30 <= UINT_MAX
>for (long l_i = 0; l_i < l_n; ++l_i)
> a[30 + l_i] = 1;
> else
>for (unsigned int i = 0; i < n; ++i)
> a[30 + i] = 1;
>
> With this kind of transformation, it would be in favor of scev, and
> some other optimizations could be beneficial: like vectorization.
>
> How about this idea? Thanks for any comments!
Better than doing loop versioning is to enhance SCEV (and thus also
dependence analysis) to track extra conditions they need to handle
cases similar as to how niter analysis computes it's 'assumptions'
condition. That allows the versioning to be done when there's an
actual beneficial transform (like vectorization) rather than just
upfront for the eventual chance that there'll be any. Ideally such
transform would then choose IVs in their transformed copy that
are analyzable w/o repeating such versioning exercise for the next
transform.
Richard.
Re: [RFC] avoid type conversion through versioning loop
On Mon, Mar 22, 2021 at 09:22:26AM +0100, Richard Biener via Gcc wrote: > Better than doing loop versioning is to enhance SCEV (and thus also > dependence analysis) to track extra conditions they need to handle > cases similar as to how niter analysis computes it's 'assumptions' > condition. That allows the versioning to be done when there's an > actual beneficial transform (like vectorization) rather than just > upfront for the eventual chance that there'll be any. Ideally such > transform would then choose IVs in their transformed copy that > are analyzable w/o repeating such versioning exercise for the next > transform. And it might be beneficial to perform some type promotion/demotion pass, either early during vectorization or separately before vectorization on a loop copy guarded with the ifns e.g. ifconv uses too. Find out what type sizes the loop use, first try to demote computations to narrower types in the vectorized loop candidate (e.g. if something is computed in a wider type only to have the result demoted to narrower type), then pick up the widest type size still in use in the loop (ok, this assumes we don't mix multiple vector sizes in the loop, but currently our vectorizer doesn't do that) and try to promote computations that could be promoted to that type size. We do partially something like that during vect patterns for bool types, but not other types I think. Jakub
Re: GSOC-2021
On Sun, 2021-03-21 at 00:31 +0530, Namitha S via Gcc wrote: > Hi, > I am Namitha S, an undergrad from Amrita University. This mail is > regarding > GSOC-2021, I wanted to know more about the project "Extend the static > analysis pass". I've gone through the wiki and finished the tasks > listed > out in the before you apply section. I've already read the mail > replies > that were written earlier for a query related to the same project > Are there any other things you'd recommend looking at?. Looking back > to > hear back. Hi I'm the author of the static analysis pass and would be the mentor for any student(s) accepted for projects relating to it for GSoC. There are various subprojects listed on that wiki page, some of which other students have already expressed interest in (kernel support and C++, although there's at least 2 projects' worth of material in the latter). Do you have a preference for any of them? No-one has yet expressed at interest in SARIF support, so that might make for a good self-contained GSoC project to propose. Hope this is helpful Dave
Re: GSoC
Hi Isitha (and Philip!) If I'm reading Isitha's email correctly, it talks about static analysis, whereas Philip's talks about GCC Rust, so some wires got crossed somewhere. I'm the author of the GCC static analysis pass. I should confess that I still feel like I'm learning static analysis myself - I too own a copy of the Nielson, Nielson & Hankin book you mention, but have only skimmed it. FWIW, I find the very early papers by Patrick and Radhia Cousot from the beginning of the field much easier to read, as they take more time spelling out the meaning of the mathematics. I should also confess that the analysis pass takes some liberties compared to a formal approach, grabbing ideas from here and there, plugging them into 30+-year-old codebase in a way that I hope is a reasonable trade-off between speed, (lack of) soundness, (lack of) completeness, and readability of output by end-user. The static analysis pass is meant to be reasonably modular, so the various suggested projects listed on the wiki page ought to be implementable without knowing everything all at once. However, as Philip says, GSoC imposes a particular timeline, and I don't know to what extent might be a dealbreaker. Hope this is helpful Dave On Fri, 2021-03-19 at 13:24 +, Philip Herron wrote: > Hi Isitha, > > Thanks for your interest in GCC Rust, it's an exciting project that > is > early on in development, so there is plenty of scoping for making > your mark > on the compiler. In regards to your proposal feel free to join our > Zulip > server https://gcc-rust.zulipchat.com/ and it can be discussed with > the > community. > > As for the Google Summer of Code timeline, I would have to defer to > their > rules. Maybe others here know better in this mailing list but as far > as I > know, to complete the google summer of code there are dated > milestones of > review so this might break the rules if you have exams and are unable > to > allocate the time towards it. > > Hope this helps, I hope it works out for you. > > Thanks > > --Phil > > > > On Fri, 19 Mar 2021 at 08:04, Isitha Subasinghe via Gcc > > wrote: > > > To whom it may concern, > > > > I am a student interested in participating in GSoC this year. After > > having > > a look at some of the available PL projects, gccrs caught my > > attention. I > > love Rust and have an interest in exploring more about type theory > > and > > automatic garbage collection. > > > > My background is that I am a Masters's student at the University of > > Melbourne in Australia, I have undertaken a graduate-level compiler > > class > > where we implemented a stack-based compiler in Haskell. > > > > I am quite interested in working on the static analysis project but > > wanted > > feedback to iron out and address my proposal before I submit it. > > > > I am quite confident in my C/C++ skills but somewhat unsure about > > the level > > of knowledge of static analysis that I would need. Unfortunately, I > > am yet > > to take any classes in this particular subfield but I am absolutely > > happy > > to learn on my own time and have purchased the book Principles of > > Program > > Analysis to assist with this matter. > > > > Also, I did want to notify you that I would be available for less > > than the > > entire coding duration of GSoC due to university commitments. > > Unfortunately, my exams overlap with GSoC, and it is hard to > > compromise on > > University studies since I am hoping to do a PhD in PL after the > > completion > > of my master's. I would be absolutely happy to make up this time at > > the end > > of the year where I have a 3-month break. > > > > Best Regards, > > Isitha > > >
Re: [RFC] avoid type conversion through versioning loop
On 2021-03-22 16:31, Jakub Jelinek via Gcc wrote: On Mon, Mar 22, 2021 at 09:22:26AM +0100, Richard Biener via Gcc wrote: Better than doing loop versioning is to enhance SCEV (and thus also dependence analysis) to track extra conditions they need to handle cases similar as to how niter analysis computes it's 'assumptions' condition. That allows the versioning to be done when there's an actual beneficial transform (like vectorization) rather than just upfront for the eventual chance that there'll be any. Ideally such transform would then choose IVs in their transformed copy that are analyzable w/o repeating such versioning exercise for the next transform. And it might be beneficial to perform some type promotion/demotion pass, either early during vectorization or separately before vectorization on a loop copy guarded with the ifns e.g. ifconv uses too. Find out what type sizes the loop use, first try to demote computations to narrower types in the vectorized loop candidate (e.g. if something is computed in a wider type only to have the result demoted to narrower type), then pick up the widest type size still in use in the loop (ok, this assumes we don't mix multiple vector sizes in the loop, but currently our vectorizer doesn't do that) and try to promote computations that could be promoted to that type size. We do partially something like that during vect patterns for bool types, but not other types I think. Jakub Thanks for the suggestions! Enhancing SCEV could help other optimizations and improve performance in some cases. While one of the direct ideas of using the '64bit type' is to eliminate conversions, even for some cases which are not easy to be optimized through ifconv/vectorization, for examples: unsigned int i = 0; while (a[i]>1e-3) i++; unsigned int i = 0; while (p1[i] == p2[i] && p1[i] != '\0') i++; Or only do versioning on type for this kind of loop? Any suggestions? BR. Jiufu Guo.
