On Fri, 2011-11-04 at 14:55 +0100, Richard Guenther wrote: > On Sun, Oct 30, 2011 at 5:10 PM, William J. Schmidt > <wschm...@linux.vnet.ibm.com> wrote: > > > > You do not seem to transform stmts on-the-fly, so for > > a1 = c + d; > a2 = c + 2*d; > a3 = c + 3*d; > > are you able to generate > > a1 = c + d; > a2 = a1 + d; > a3 = a2 + d; > > ? On-the-fly operation would also handle this if the candidate info > for a2 is kept as c + 2*d. Though it's probably worth lookign at > > a1 = c + d; > a2 = a1 + d; > a3 = c + 3*d; > > and see if that still figures out that a3 = a2 + d (thus, do you, > when you find the candidate a1 + 1 * d, fold in candidate information > for a1? thus, try to reduce it to an ultimate base?) > > Thanks, > Richard.
Just a couple of quick thoughts here. As I mentioned, this patch is only for the cases where the stride is a constant. The only interesting patterns I could think of for that case is what I'm currently handling, where an add-immediate feeds a multiply, e.g., y = (x + c) * d where c and d are constants. Once the stride is a variable, we have not only those cases, but also cases like you show here where the multiply feeds into an add. Those can be handled with the existing infrastructure in a slightly different way. The main differences are: - The cand_stmt will be the add in this case. We always want the candidate to be the statement that we hope to replace. - The base_name will be the "ultimate base," so that all the original candidates in your example will have c for the base. This may involve looking back through casts. - The index will be the multiplier applied to the stride. The logic for finding the nearest dominating basis will be pretty much identical. The candidate table again contains enough information that we don't need to do on-the-fly replacement, but can examine all the related candidates at once. This will be important for the add-feeding-multiply case with an SSA name stride, since we sometimes need to introduce multiplies by a constant in order to remove general multiplies of two registers. But again, that's all for a follow-on patch. My thought was to get this one set of easy candidates handled in a first patch so you could get a look at the general infrastructure without having to review a huge chunk of code at once. Once that patch is in place, the next stages would be: 2. SSA-name strides, both multiply-add and add-multiply forms. 3. Cases involving conditional increments (looking through PHIs). 4. Cases where the multiplies are hidden in addressing expressions. I have a pretty good idea where I'm going with stages 2 and 3. Stage 4 is where things are likely to get a bit bloodier, and I will be glad for any advice about the best way to handle those as we get to that point. Thanks again, Bill
