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

[Sebastian Pop]

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.

> 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.

> 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.

> 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.

> 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.

Sebastian
-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by The Linux Foundation