Yet Another Hoopl Question

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Yet Another Hoopl Question

Jan Stolarek
I have yet another Hoopl question. One of my rewrites allocates a new unique local register and this register is later added as a fact. So I have Cmm code that looks like this:

  I32[(old + 4)] = complicated_expr

which is rewritten to:

  newReg1 = complicated_expr
  I32[(old + 4)] = newReg1

and then I add { I32[(old + 4)] = newReg1 } as a fact. When Hoopl reaches end of the iteration it realizes it has learned some new facts, so it keeps the facts (including fact about a new unique register) and discards rewritten graph (including said new register). In the next iteration it performs the rewrite again, allocating a different new register and adding fact about this different register. At the end of this iteration same thing happens again: facts are kept, rewrite is discarded. And so my code falls into an infinite loop, because every time I'm allocating a different register and every time hoopl thinks it learned sth new and discards the rewritten graph. How can I perform this rewrite and avoid falling into a loop?

Janek



Reply | Threaded
Open this post in threaded view
|

Yet Another Hoopl Question

Simon Marlow-7
On 13/08/13 13:03, Jan Stolarek wrote:

> I have yet another Hoopl question. One of my rewrites allocates a new unique local register and this register is later added as a fact. So I have Cmm code that looks like this:
>
>    I32[(old + 4)] = complicated_expr
>
> which is rewritten to:
>
>    newReg1 = complicated_expr
>    I32[(old + 4)] = newReg1
>
> and then I add { I32[(old + 4)] = newReg1 } as a fact. When Hoopl reaches end of the iteration it realizes it has learned some new facts, so it keeps the facts (including fact about a new unique register) and discards rewritten graph (including said new register). In the next iteration it performs the rewrite again, allocating a different new register and adding fact about this different register. At the end of this iteration same thing happens again: facts are kept, rewrite is discarded. And so my code falls into an infinite loop, because every time I'm allocating a different register and every time hoopl thinks it learned sth new and discards the rewritten graph. How can I perform this rewrite and avoid falling into a loop?

Your transfer function is not monotonic, because each time you apply it
it gives a different result.

The next question is "well how do I do this then?". I'm not quite sure,
maybe you need to use a deterministic name supply monad.

Cheers,
        Simon




Reply | Threaded
Open this post in threaded view
|

Yet Another Hoopl Question

Edward Z. Yang
Forgive me for asking the classic question: "What are you really trying to do?"

Edward

Excerpts from Simon Marlow's message of Tue Aug 13 09:25:51 -0400 2013:

> On 13/08/13 13:03, Jan Stolarek wrote:
> > I have yet another Hoopl question. One of my rewrites allocates a new unique local register and this register is later added as a fact. So I have Cmm code that looks like this:
> >
> >    I32[(old + 4)] = complicated_expr
> >
> > which is rewritten to:
> >
> >    newReg1 = complicated_expr
> >    I32[(old + 4)] = newReg1
> >
> > and then I add { I32[(old + 4)] = newReg1 } as a fact. When Hoopl reaches end of the iteration it realizes it has learned some new facts, so it keeps the facts (including fact about a new unique register) and discards rewritten graph (including said new register). In the next iteration it performs the rewrite again, allocating a different new register and adding fact about this different register. At the end of this iteration same thing happens again: facts are kept, rewrite is discarded. And so my code falls into an infinite loop, because every time I'm allocating a different register and every time hoopl thinks it learned sth new and discards the rewritten graph. How can I perform this rewrite and avoid falling into a loop?
>
> Your transfer function is not monotonic, because each time you apply it
> it gives a different result.
>
> The next question is "well how do I do this then?". I'm not quite sure,
> maybe you need to use a deterministic name supply monad.
>
> Cheers,
>     Simon
>



Reply | Threaded
Open this post in threaded view
|

Yet Another Hoopl Question

Jan Stolarek
> The next question is "well how do I do this then?". I'm not quite sure,
> maybe you need to use a deterministic name supply monad.

So why are Hoopl's rewrite functions specialized to UniqSM monad? My understanding so far was that this is precisely because we need access to Uniq supply to generate new labels and registers during rewriting. I'm guessing that nobody intended that these newly generated things will be added as facts?


> Forgive me for asking the classic question: "What are you really trying to do?"

I'm doing copy (constant) propagation and one of my intentions is to minimize traffic to/from the stack when possible. Since I cannot propagate complicated_expr, I rewrite a store to a stack location with

  newReg1 = complicated_expr
  I32[(old + 4)] = newReg1

By recording second assignment as a fact it is now possible to replace references to I32[(old + 4)] with references to newReg1, which will effectively make "I32[(old + 4)] = newReg1" assignment dead. So now information will be kept in registers instead of the stack. Of course it is still possible that there will be not enough registers and we'll have to spill some things to the stack.

Janek




Reply | Threaded
Open this post in threaded view
|

Yet Another Hoopl Question

Simon Peyton Jones
|  So why are Hoopl's rewrite functions specialized to UniqSM monad? My
|  understanding so far was that this is precisely because we need access to Uniq
|  supply to generate new labels and registers during rewriting. I'm guessing that
|  nobody intended that these newly generated things will be added as facts?

Correct.

|  complicated_expr, I rewrite a store to a stack location with
|  
|    newReg1 = complicated_expr
|    I32[(old + 4)] = newReg1

Yes, as Simon says, you need a deterministic name for newReg1. An obvious choice would be
        reg_L3_7
if this was the 7th instruction of a block whose label was L3.  Then the register name would be unaffected by any other rewrites, in any other block, or earlier in this block.  

But that's not altogether easy, since LocalRegs are identified by a Unique, not a string.

One possibility is to do this transformation once and for all, *before* the constant-prop pass, since it is not dependent on the facts generated by the pass.

Simon




Reply | Threaded
Open this post in threaded view
|

Yet Another Hoopl Question

Jan Stolarek
> One possibility is to do this transformation once and for all, *before* the constant-prop pass,
> since it is not dependent on the facts generated by the pass.
Yes, that was Geoffrey's suggestion as well. I'll do that once I fix some remaining issues in copy propagation.

Janek