Yet Another Hoopl Question
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
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
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
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
| 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
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
participants (4)
-
Edward Z. Yang -
Jan Stolarek -
Simon Marlow -
Simon Peyton-Jones