[LLVMdev] [polly] scev codegen (first step to remove the dependence on ivcanon pass)

[Tobias Grosser]

On 12/03/2012 07:37 PM, Sebastian Pop wrote:
> Tobias Grosser wrote:
>
>> You create a map from the old_loop to a symbolic expression. What type would
>> this symbolic expression have? Would it be a SCEVExpr?
>
> evaluateAtIteration takes a scev, so apply will take a scev, or a map
> (loop->scev).  You can always build a ScevUnknown from an SSA name and use that
> in the apply.

OK, so we have the same idea of this.

>> At the moment, we calculate at the beginning of each
>> polly statement (a basic block) a value for each virtual induction
>> variable of the original loops. For your example we get something like
>> this.
>>
>> new_bb:
>>       new_iv_1 = add i32 c1, 0
>>       new_iv_2 = add i32 c1, 7
>>       new_iv_3 = add i32 c1, c2
>>
>>       ....
>>
>> I want to highlight here that the values new_iv_1, new_iv_2, new_iv_3
>> correspond to the number of loop iterations of the original loop. As we
>> currently require canonical induction variables, they are equivalent to
>> the value of the old canonical induction variable. However, generating
>> those values does not imply that we need to have canonical induction
>> variables in the original code. Even without canonical induction
>> variables, calculating such values is useful, as this simplifies the map
>> you describe above. Instead of going from Loop* to some symbolic
>> expression, you can just pass the corresponding Value* or ScevUnknown*.
>
> Yes, that's equivalent to what I described for the map (loop->expression):
> whether you have an expression or just an SSA name that computes that expression
> is equivalent.
 >
 >
 >
>> Passing a symbolic expression, as you propose, could allow further
>> simplifictions,
>
> I don't see how it could simplify anything: I think both are equivalent.

Passing symbolic expressions, instead of a plain SCEVUnknown could 
expose simplification opportunities on the SCEV level.


%const = sub i32 10, 5  // -5

Scev_1 = {20, +, 4}_1
Scev_2 = apply (loop_1 -> %const)    on Scev_1 = 20 + 4 * %const

If we pass %const as a SCEVUnknown, we can not further simplify the 
resulting SCEV. However, if we pass it as the constant value -5, we
can do the following simplification:

Scev_2 = apply (loop_1 -> -5)    on Scev_1 = 20 + 4*(-5) = 0

I don't think we there is currently a need to take advantage of 
simplifications at SCEV level. I would rather have this one working 
first. We can then have investigate the benefits of simplifications at
the SCEV level.

>> Now to the removal of the SCEVRewriter. I am not opposed to it, but
>> wonder what the benefit of removing it would be? Do you think moving
>> this transformation directly into SCEV is conceptually nicer or is there
>> some additional benefit.
>
> Other code would be able to call apply: it's a general operation that can be
> exposed to other users.

That makes sense.

>> 1. What happens to parameters
>>
>> Besides rewriting the loop ivs, the SCEVRewriter also rewrites parameters. It
>> takes a map [<SCEV* ->  Value*>] and replaces SCEV expressions which we have
>> recognized during code generation with a parameter value. This is necessary,
>> in case we generate OpenMP / OpenCL code and need to pass parameters to other
>> functions or modules.
>
> Maybe OpenMP / OpenCL codegen could separately handle the rewrite of in/out
> variables for the outlined functions: the scalar and vector codegen don't need
> to rewrite parameters.
>
> What about moving a reduced version rewriteScevParams in the general
> implementation of SCEV?  That would make it available for other users.

If there is a use for it or if it simplifies some code I am fine with this.

>> 2. Speed
>>
>> The SCEVRewriter only passes once over the SCEVExpr. In your approach,
>> we would pass three times over the SCEV, no?
>
> It depends on how you implement it.  You can do it in one swipe as well.

OK. Good.

Cheers
Tobi