Tobias Grosser wrote: > I would like to improve the way how we handle scalar variables and ivs > during graphite transformation. > I am not sure, if I got it right and where to put my code in the backend. > So it would be great, if you could read over my ideas. > > The problem: > ============ > In graphite we represent the complete loop structure using polyhedrons to > apply our transformations. > To go back to gimple we have to generate new loop structures and delete > the old loop structures. > One step is to remove old ivs and generate new ones. > > > Example: > > 1. original bb: > ------------------------ > D.1918_7 = a[i_22]; > D.1919_8 = D.1918_7 + 1; > a[j_21] = D.1919_8; > j_9 = j_21 + 1; > ------------------------ > > > 2. Add new ivs > > graphiteIV_1 = PHI (0, graphiteIV_2) > ------------------------ > D.1918_7 = a[i_22]; > D.1919_8 = D.1918_7 + 1; > a[j_21] = D.1919_8; > j_9 = j_21 + 1; > ------------------------ > graphiteIV_2 = graphiteIV_1 + 1 > > > 3. Move ivs usages to the ivs. > > graphiteIV_1 = PHI (0, graphiteIV_2) > ------------------------ > D.1918_7 = a[i_22]; > D.1919_8 = D.1918_7 + 1; > a[graphiteIV_1] = D.1919_8; > j_9 = j_21 + 1; > ------------------------ > graphiteIV_2 = graphiteIV_1 + 1 > > > 4. remove ivs (Here {j_9, j_21}) > > ------------------------ > D.1918_7 = a[i_22];157235101 disconnected > D.1919_8 = D.1918_7 + 1; > a[graphiteIV_1] = D.1919_8; > ------------------------
That's my understanding as well. > The problem seems to become more complicate, if there exist two or more > ivs. More complicated if you want to make sure all dead variables are removed (with the associated definition code), but is it critical, given that a PRE/CSE will clean this up afterwards? > How I would like to solve it: > ============================= > > During gimple->graphite transformation we ignore all scalar variables, > that we can represent using scev. (These contain also all the ivs) > > Here {D.1918_7, D.1919_8} are not representable, as they depend on the > value of a[i_22]. Therefore we can not ignore them. > But {j_9, j_21} will be representable and we ignore them. > > During graphite we have all ivs virtually removed. This would be very good. I fully agree, yet more motivated by dependence removal rather than clean-output goals (cf. PRE/CSE argument). > The next step is during code generation: > We remove all scalar variables, we ignored before, and recreate for the > places, where they where used, new scalar variables, that depend on the > new ivs. The tricky part might be that those so-called "new variables" have to be named like the old ones, although plenty of new variables will have been synthesized in the mean time. > Why remove all and not just the ivs? > ------------------------------------ > > There are two points. > > 1. Detection ivs is much work. So I prefer this general algorithm, as I > hope it is easier to implement and runs faster. Agree. > 2. If we can ignore the scalar variables, we can also ignore their > dependencies. So we have more freedom to schedule the bbs. Exactly. > > See you > Tobi > > P.S.: To start working on my code I would like to get block-0.c running. > Jan, can I help you with anything?