Branch removal

[Patrick Metzler]

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

   spanningTreeCost = 0;
   edgeList = new HashSet<E>();

   for (E edge : allEdges) {
     forestSwap = forest.getCopy();
     edgeListSwap = new HashSet<E>(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);
     }
   }
}