Fix Phi optimization

[ratefuchs]

The code calling our Phi optimization is currently commented out. However, before we use it, we should fix the following bug: If all the predecessors of a Phi node have the same tarval, we replace our Phi with a Const node. But I think it is possible that the predecessors are Phis and have that tarval because of a (int-tarval, unknown)-combination. Consider the following example:

int r = 1;
int i = 0;
while (i < 10) {
    while (i < 5) {
        System.out.println(r);
        r = 1;
        i = i + 1;
    }
    r = r+1;
    i=i+1;
}

The r from println depends on a Phi for the inner while loop. It sees r=1 in the inner loop as one predecessor and the Phi for r from the outer loop as its other. When visiting this outer Phi, it sees r=1 from the beginning and r=r+1 (which is unknown at the start). This leads to a value of 1. The inner Phi now optimizes itself although it is not constant!

When performing the fixpoint iteration, nodes may only be replaced after the fixpoint has been found (except if we have Const nodes instead of just Const-tarvals)!

[Nidan]

We may only optimize a phi iff

• all preceding nodes have the same non-unknown, non-bad tarval (as implemented right now)
• and all preceding nodes of all recursively preceding phis also have neither unknown no bad tarvals

Does this look correct?

[maxvogel]

True. As far as my understanding goes, we mix up some stuff anyways. If there is a const_node, we wouldn't really need get/set_irn_link as the const infomation is stronger.

However, you are right aswell. Currently, the fix point iteration is not correct. I think that in each "iteration"/each time the a (non-Const) node is visited, the following scheme is necessary (it's not 100% precise, but you should get an idea):

ir_tarval* oldTarval = (ir_tarval*)get_irn_link(node);
// ... process predecessors for changes and compute 
ir_tarval* newTarval = ...
// provided, that both tarval modes are Is
if (get_tarval_long(oldTarval) == get_tarval_long(newTarval)) 
    exchange(...)

The only remaining issue is, whether this criteria for the fixpoint iteration which is only locally for the currently handled node is sufficient.

[maxvogel]

I have rewritten the phi optimization from scratch, however I was not able to test it yet. I will test and probably push tomorrow

[maxvogel]

In my latest commit (d0a36bd), Simon's example still gets optimized wrong, but I think that is because the node is processed too often. Consider a queue with nodes a, b, c and a is processed and a change to its tarval happens, so we push b to the queue again. Then, b does already the see the change when its processed for the first time but then again at the end of the queue. With my proposed criterion (comparing tarvals of previous and current iteration) to evaluate if a phi node can be replaced by a const node, this leads to wrong behaviour. Therefor, is it ok to only push nodes to the queue, when the node is not anymore in the queue? Then we need to use a deque to iterate over the worklist or a map/set to store the information, if the node is currently in the queue or not.

Also, currently we only handle Phi nodes whose mode is mode_Is. Can we also optimize Phi M nodes? Are there other modes interesting for us?

The current implementation tries to be more transparent as to how nodes are processed and what is done with the collected information and it would be nice, if someone could review it.

[Nidan]

Currently we generate an endless loop in run/Simon_103.mj and run/Simon_105.mj . Four more Testcases fail due to different output: Test run/Simon_104.mj output differs Test run/Simon_119.mj output differs Test run/Simon_124.mj output differs Test run/fannkuch.mj output differs

I think a node may not be in the worklist twice, so a set or map is preferrable to a deque. Maybe even enforce a top to bottom ordering inside the worklist (We could use firm's node number for a map<node_nr, node *> construct)

[maxvogel]

I've actually implemented that a node cannot be added to worklist, if it is already in it, however I need to figure out the segfaults I keep getting. A top to bottom ordering shouldn't be necessary for the fix point iteration.

[Nidan]

Not necessary, I agree, but it might reduce the number of node we have to look at.

I found and fixed two segfaults in 815ee51, one when a node has no tarval yet, one when handling minus nodes (which have no second node to get a tarval from). The tests now fail for the same reason (looks like optimizing a phi too early), whether updateTarvalForArithmeticNode is used or not, so I left it commented in.