[Mesa-dev] Value Range Propagation in NIR (GSoC)

[Thomas Helland]

Hi,

For those that don't know I've submitted a proposal for this years GSoC.
I've proposed to implement value range propagation and loop unrolling in
NIR.
Since I'm no expert on compilers I've read up on some litterature:

I started with "Constant propagation with conditional branches"  (thanks
Connor).
This paper describes an algorithm, "sparse conditional constant
propagation",
that seems to be the defacto standard in compilers today.

I also found the paper;
"Accurate static branch prediction by value range propagation " (VRP).
This describes a value range propagation implementation based on SCCP.
(This also allows one to set heuristics to calculate educated guesses for
the
probability of a certain branch, but that's probably more than we're
interested in.)

There is also a GCC paper (with whatever licensing issues that may apply);
"A propagation engine for GCC".
They have a shared engine for doing all propagation passes.
It handles the worklists, and the logic to traverse these.
The implementing passes then supply callbacks to define the lattice rules.
They reply back if the instruction was interesting or not,
and the propagation engine basically handles the rest.

Maybe that's an interesting solution? Or it might not be worth the hassle?
We already have copy propagation, and with value range propagation
we probably don't want separate constant propagation?
(I'm hoping to write the pass so that it handles both constants and value
ranges.)
The GCC guys have used this engine to get copy propagation that propagates
copies accross conditionals, maybe this makes such a solution more
interesting?

Connor: I just remembered you saying something about your freedesktop
git repo, so I poked around some and found that you have already done
some work on VRP based on SCCP? How far did you get?

If we just want to make an SCCP inspired VRP pass then Connor has work in
progress.
Finishing that, and loop unrolling, may not be enough work for GSoC?
Or maybe Connor wants to finish it of himself, and I should spend my time
implementing some other pass instead, alongside loop unrolling?

Realising Connor has partially started on this I thought it was a good
idea to get some feedback and ideas from others (if I need to change my
proposal)
All suggestions, ideas and opinions are more than welcome.
Fire at will, I'm all ears =)

Regards,
Thomas
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freedesktop.org/archives/mesa-dev/attachments/20150407/f714b4ac/attachment.html>