[LLVMdev] [polly] scev codegen (first step to remove the dependence on ivcanon pass)
Tobias Grosser
tobias at grosser.es
Mon Dec 3 11:12:46 PST 2012
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
More information about the llvm-dev
mailing list