Branch removal (original) (raw)

Patrick Metzler Patrick.Metzler at gmx.net
Thu Sep 27 11:36:16 PDT 2012

Hi Vladimir,

Thanks for your fast answers.

Could you give a java code example you are trying to optimize?

A minimized source code example would be (see below for the complete example I'm working on):

MyObject a, aSwap; // ... code left out here ... for (E e : arrayList) { aSwap = a.getCopy(); aSwap.do(); if (e.condition()) a = aSwap; }

I want the assignment following 'if' to be a 'conditional move'.

After parsing, the two branches resulting of the 'if' statement are connected to two different Loop nodes:

      ...    ____
         |  |    |
         Loop    |
        /        |

__ ... | | | / | | Loop | | \ | | ... ... ... \ | | If ... ... / \ | | IfTrue IfFalse | |_/ _|

(Here, IfTrue corresponds to e.condition()==false, i.e. the assignment is not executed. '...' stands for multiple basic blocks here.)

I want to delete the else (IfTrue) branch, which is empty in the source code but not in the IDEA graph, including the second Loop. Then I want to provide the data input to CallStaticJava (a.getCopy()) through the CMove.

You can't replace such Phi because its data inputs come from different conditions (If nodes). You can only replace Phi from "diamond" shaped graphs:

Is it possible to first transform the sub graph into a CFG diamond and then optimize it?

Best regards, Patrick

Complete source code (borrowed from the JGraphT library, http://jgrapht.org/):

public void runKruskal(final Graph<V, E> graph) { Forest forest = new Forest(graph.vertexSet()); Forest forestSwap; double spanningTreeCost; Set edgeList; Set edgeListSwap; ArrayList allEdges = new ArrayList(graph.edgeSet()); Collections.sort(allEdges, new Comparator() { @Override public int compare(E edge1, E edge2) { return Double.valueOf(graph.getEdgeWeight(edge1)) .compareTo(graph.getEdgeWeight(edge2)); } });

spanningTreeCost = 0; edgeList = new HashSet();

for (E edge : allEdges) { forestSwap = forest.getCopy(); edgeListSwap = new HashSet(edgeList); V source = graph.getEdgeSource(edge); V target = graph.getEdgeTarget(edge);

 forestSwap.union(source, target);
 edgeListSwap.add(edge);

 /* Branch to eliminate */
 if (!forestSwap.find(source).equals(forestSwap.find(target))) {
   forest = forestSwap;
   edgeList = edgeListSwap;
   spanningTreeCost += graph.getEdgeWeight(edge);
 }

} }

More information about the hotspot-compiler-dev mailing list