hotspot/src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.lir/src/org/graalvm/compiler/lir/gen/PhiResolver.java - platform/libcore - Git at Google

 /*
  * Copyright (c) 2009, 2015, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
  * under the terms of the GNU General Public License version 2 only, as
  * published by the Free Software Foundation.
  *
  * This code is distributed in the hope that it will be useful, but WITHOUT
  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  * version 2 for more details (a copy is included in the LICENSE file that
  * accompanied this code).
  *
  * You should have received a copy of the GNU General Public License version
  * 2 along with this work; if not, write to the Free Software Foundation,
  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  *
  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  * or visit www.oracle.com if you need additional information or have any
  * questions.
  */
 package org.graalvm.compiler.lir.gen;

 import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
 import static jdk.vm.ci.code.ValueUtil.isIllegal;
 import static jdk.vm.ci.code.ValueUtil.isLegal;
 import static jdk.vm.ci.meta.Value.ILLEGAL;

 import java.util.ArrayList;
 import java.util.HashMap;
 import java.util.List;

 import org.graalvm.compiler.core.common.CollectionsFactory;
 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
 import org.graalvm.compiler.lir.LIRInsertionBuffer;
 import org.graalvm.compiler.lir.LIRInstruction;
 import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory;

 import jdk.vm.ci.meta.AllocatableValue;
 import jdk.vm.ci.meta.Value;

 /**
  * Converts phi instructions into moves.
  *
  * Resolves cycles:
  *
  * <pre>
  *
  *  r1 := r2  becomes  temp := r1
  *  r2 := r1           r1 := r2
  *                     r2 := temp
  * </pre>
  *
  * and orders moves:
  *
  * <pre>
  *  r2 := r3  becomes  r1 := r2
  *  r1 := r2           r2 := r3
  * </pre>
  */
 public class PhiResolver {

     /**
      * Tracks a data flow dependency between a source operand and any number of the destination
      * operands.
      */
     static class PhiResolverNode {

         /**
          * A source operand whose value flows into the {@linkplain #destinations destination}
          * operands.
          */
         final Value operand;

         /**
          * The operands whose values are defined by the {@linkplain #operand source} operand.
          */
         final ArrayList<PhiResolverNode> destinations;

         /**
          * Denotes if a move instruction has already been emitted to initialize the value of
          * {@link #operand}.
          */
         boolean assigned;

         /**
          * Specifies if this operand been visited for the purpose of emitting a move instruction.
          */
         boolean visited;

         /**
          * Specifies if this is the initial definition in data flow path for a given value.
          */
         boolean startNode;

         PhiResolverNode(Value operand) {
             this.operand = operand;
             destinations = new ArrayList<>(4);
         }

         @Override
         public String toString() {
             StringBuilder buf = new StringBuilder(operand.toString());
             if (!destinations.isEmpty()) {
                 buf.append(" ->");
                 for (PhiResolverNode node : destinations) {
                     buf.append(' ').append(node.operand);
                 }
             }
             return buf.toString();
         }
     }

     private final LIRGeneratorTool gen;
     private final MoveFactory moveFactory;
     private final LIRInsertionBuffer buffer;
     private final int insertBefore;

     /**
      * The operand loop header phi for the operand currently being process in {@link #dispose()}.
      */
     private PhiResolverNode loop;

     private Value temp;

     private final ArrayList<PhiResolverNode> variableOperands = new ArrayList<>(3);
     private final ArrayList<PhiResolverNode> otherOperands = new ArrayList<>(3);

     /**
      * Maps operands to nodes.
      */
     private final HashMap<Value, PhiResolverNode> operandToNodeMap = CollectionsFactory.newMap();

     public static PhiResolver create(LIRGeneratorTool gen) {
         AbstractBlockBase<?> block = gen.getCurrentBlock();
         assert block != null;
         List<LIRInstruction> instructions = gen.getResult().getLIR().getLIRforBlock(block);

         return new PhiResolver(gen, new LIRInsertionBuffer(), instructions, instructions.size());
     }

     public static PhiResolver create(LIRGeneratorTool gen, LIRInsertionBuffer buffer, List<LIRInstruction> instructions, int insertBefore) {
         return new PhiResolver(gen, buffer, instructions, insertBefore);
     }

     protected PhiResolver(LIRGeneratorTool gen, LIRInsertionBuffer buffer, List<LIRInstruction> instructions, int insertBefore) {
         this.gen = gen;
         moveFactory = gen.getSpillMoveFactory();
         temp = ILLEGAL;

         this.buffer = buffer;
         this.buffer.init(instructions);
         this.insertBefore = insertBefore;

     }

     public void dispose() {
         // resolve any cycles in moves from and to variables
         for (int i = variableOperands.size() - 1; i >= 0; i--) {
             PhiResolverNode node = variableOperands.get(i);
             if (!node.visited) {
                 loop = null;
                 move(node, null);
                 node.startNode = true;
                 assert isIllegal(temp) : "moveTempTo() call missing";
             }
         }

         // generate move for move from non variable to arbitrary destination
         for (int i = otherOperands.size() - 1; i >= 0; i--) {
             PhiResolverNode node = otherOperands.get(i);
             for (int j = node.destinations.size() - 1; j >= 0; j--) {
                 emitMove(node.destinations.get(j).operand, node.operand);
             }
         }
         buffer.finish();
     }

     public void move(Value dest, Value src) {
         assert isVariable(dest) : "destination must be virtual";
         // tty.print("move "); src.print(); tty.print(" to "); dest.print(); tty.cr();
         assert isLegal(src) : "source for phi move is illegal";
         assert isLegal(dest) : "destination for phi move is illegal";
         PhiResolverNode srcNode = sourceNode(src);
         PhiResolverNode destNode = destinationNode(dest);
         srcNode.destinations.add(destNode);
     }

     private PhiResolverNode createNode(Value operand, boolean source) {
         PhiResolverNode node;
         if (isVariable(operand)) {
             node = operandToNodeMap.get(operand);
             assert node == null || node.operand.equals(operand);
             if (node == null) {
                 node = new PhiResolverNode(operand);
                 operandToNodeMap.put(operand, node);
             }
             // Make sure that all variables show up in the list when
             // they are used as the source of a move.
             if (source) {
                 if (!variableOperands.contains(node)) {
                     variableOperands.add(node);
                 }
             }
         } else {
             assert source;
             node = new PhiResolverNode(operand);
             otherOperands.add(node);
         }
         return node;
     }

     private PhiResolverNode destinationNode(Value opr) {
         return createNode(opr, false);
     }

     private void emitMove(Value dest, Value src) {
         assert isLegal(src);
         assert isLegal(dest);
         LIRInstruction move = moveFactory.createMove((AllocatableValue) dest, src);
         buffer.append(insertBefore, move);
     }

     // Traverse assignment graph in depth first order and generate moves in post order
     // ie. two assignments: b := c, a := b start with node c:
     // Call graph: move(c, NULL) -> move(b, c) -> move(a, b)
     // Generates moves in this order: move b to a and move c to b
     // ie. cycle a := b, b := a start with node a
     // Call graph: move(a, NULL) -> move(b, a) -> move(a, b)
     // Generates moves in this order: move b to temp, move a to b, move temp to a
     private void move(PhiResolverNode dest, PhiResolverNode src) {
         if (!dest.visited) {
             dest.visited = true;
             for (int i = dest.destinations.size() - 1; i >= 0; i--) {
                 move(dest.destinations.get(i), dest);
             }
         } else if (!dest.startNode) {
             // cycle in graph detected
             assert loop == null : "only one loop valid!";
             loop = dest;
             moveToTemp(src.operand);
             return;
         } // else dest is a start node

         if (!dest.assigned) {
             if (loop == dest) {
                 moveTempTo(dest.operand);
                 dest.assigned = true;
             } else if (src != null) {
                 emitMove(dest.operand, src.operand);
                 dest.assigned = true;
             }
         }
     }

     private void moveTempTo(Value dest) {
         assert isLegal(temp);
         emitMove(dest, temp);
         temp = ILLEGAL;
     }

     private void moveToTemp(Value src) {
         assert isIllegal(temp);
         temp = gen.newVariable(src.getValueKind());
         emitMove(temp, src);
     }

     private PhiResolverNode sourceNode(Value opr) {
         return createNode(opr, true);
     }
 }
	/*
	* Copyright (c) 2009, 2015, Oracle and/or its affiliates. All rights reserved.
	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
	*
	* This code is free software; you can redistribute it and/or modify it
	* under the terms of the GNU General Public License version 2 only, as
	* published by the Free Software Foundation.
	*
	* This code is distributed in the hope that it will be useful, but WITHOUT
	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	* version 2 for more details (a copy is included in the LICENSE file that
	* accompanied this code).
	*
	* You should have received a copy of the GNU General Public License version
	* 2 along with this work; if not, write to the Free Software Foundation,
	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
	*
	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
	* or visit www.oracle.com if you need additional information or have any
	* questions.
	*/
	package org.graalvm.compiler.lir.gen;

	import static org.graalvm.compiler.lir.LIRValueUtil.isVariable;
	import static jdk.vm.ci.code.ValueUtil.isIllegal;
	import static jdk.vm.ci.code.ValueUtil.isLegal;
	import static jdk.vm.ci.meta.Value.ILLEGAL;

	import java.util.ArrayList;
	import java.util.HashMap;
	import java.util.List;

	import org.graalvm.compiler.core.common.CollectionsFactory;
	import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
	import org.graalvm.compiler.lir.LIRInsertionBuffer;
	import org.graalvm.compiler.lir.LIRInstruction;
	import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory;

	import jdk.vm.ci.meta.AllocatableValue;
	import jdk.vm.ci.meta.Value;

	/**
	* Converts phi instructions into moves.
	*
	* Resolves cycles:
	*
	* <pre>
	*
	* r1 := r2 becomes temp := r1
	* r2 := r1 r1 := r2
	* r2 := temp
	* </pre>
	*
	* and orders moves:
	*
	* <pre>
	* r2 := r3 becomes r1 := r2
	* r1 := r2 r2 := r3
	* </pre>
	*/
	public class PhiResolver {

	/**
	* Tracks a data flow dependency between a source operand and any number of the destination
	* operands.
	*/
	static class PhiResolverNode {

	/**
	* A source operand whose value flows into the {@linkplain #destinations destination}
	* operands.
	*/
	final Value operand;

	/**
	* The operands whose values are defined by the {@linkplain #operand source} operand.
	*/
	final ArrayList<PhiResolverNode> destinations;

	/**
	* Denotes if a move instruction has already been emitted to initialize the value of
	* {@link #operand}.
	*/
	boolean assigned;

	/**
	* Specifies if this operand been visited for the purpose of emitting a move instruction.
	*/
	boolean visited;

	/**
	* Specifies if this is the initial definition in data flow path for a given value.
	*/
	boolean startNode;

	PhiResolverNode(Value operand) {
	this.operand = operand;
	destinations = new ArrayList<>(4);
	}

	@Override
	public String toString() {
	StringBuilder buf = new StringBuilder(operand.toString());
	if (!destinations.isEmpty()) {
	buf.append(" ->");
	for (PhiResolverNode node : destinations) {
	buf.append(' ').append(node.operand);
	}
	}
	return buf.toString();
	}
	}

	private final LIRGeneratorTool gen;
	private final MoveFactory moveFactory;
	private final LIRInsertionBuffer buffer;
	private final int insertBefore;

	/**
	* The operand loop header phi for the operand currently being process in {@link #dispose()}.
	*/
	private PhiResolverNode loop;

	private Value temp;

	private final ArrayList<PhiResolverNode> variableOperands = new ArrayList<>(3);
	private final ArrayList<PhiResolverNode> otherOperands = new ArrayList<>(3);

	/**
	* Maps operands to nodes.
	*/
	private final HashMap<Value, PhiResolverNode> operandToNodeMap = CollectionsFactory.newMap();

	public static PhiResolver create(LIRGeneratorTool gen) {
	AbstractBlockBase<?> block = gen.getCurrentBlock();
	assert block != null;
	List<LIRInstruction> instructions = gen.getResult().getLIR().getLIRforBlock(block);

	return new PhiResolver(gen, new LIRInsertionBuffer(), instructions, instructions.size());
	}

	public static PhiResolver create(LIRGeneratorTool gen, LIRInsertionBuffer buffer, List<LIRInstruction> instructions, int insertBefore) {
	return new PhiResolver(gen, buffer, instructions, insertBefore);
	}

	protected PhiResolver(LIRGeneratorTool gen, LIRInsertionBuffer buffer, List<LIRInstruction> instructions, int insertBefore) {
	this.gen = gen;
	moveFactory = gen.getSpillMoveFactory();
	temp = ILLEGAL;

	this.buffer = buffer;
	this.buffer.init(instructions);
	this.insertBefore = insertBefore;

	}

	public void dispose() {
	// resolve any cycles in moves from and to variables
	for (int i = variableOperands.size() - 1; i >= 0; i--) {
	PhiResolverNode node = variableOperands.get(i);
	if (!node.visited) {
	loop = null;
	move(node, null);
	node.startNode = true;
	assert isIllegal(temp) : "moveTempTo() call missing";
	}
	}

	// generate move for move from non variable to arbitrary destination
	for (int i = otherOperands.size() - 1; i >= 0; i--) {
	PhiResolverNode node = otherOperands.get(i);
	for (int j = node.destinations.size() - 1; j >= 0; j--) {
	emitMove(node.destinations.get(j).operand, node.operand);
	}
	}
	buffer.finish();
	}

	public void move(Value dest, Value src) {
	assert isVariable(dest) : "destination must be virtual";
	// tty.print("move "); src.print(); tty.print(" to "); dest.print(); tty.cr();
	assert isLegal(src) : "source for phi move is illegal";
	assert isLegal(dest) : "destination for phi move is illegal";
	PhiResolverNode srcNode = sourceNode(src);
	PhiResolverNode destNode = destinationNode(dest);
	srcNode.destinations.add(destNode);
	}

	private PhiResolverNode createNode(Value operand, boolean source) {
	PhiResolverNode node;
	if (isVariable(operand)) {
	node = operandToNodeMap.get(operand);
	assert node == null \|\| node.operand.equals(operand);
	if (node == null) {
	node = new PhiResolverNode(operand);
	operandToNodeMap.put(operand, node);
	}
	// Make sure that all variables show up in the list when
	// they are used as the source of a move.
	if (source) {
	if (!variableOperands.contains(node)) {
	variableOperands.add(node);
	}
	}
	} else {
	assert source;
	node = new PhiResolverNode(operand);
	otherOperands.add(node);
	}
	return node;
	}

	private PhiResolverNode destinationNode(Value opr) {
	return createNode(opr, false);
	}

	private void emitMove(Value dest, Value src) {
	assert isLegal(src);
	assert isLegal(dest);
	LIRInstruction move = moveFactory.createMove((AllocatableValue) dest, src);
	buffer.append(insertBefore, move);
	}

	// Traverse assignment graph in depth first order and generate moves in post order
	// ie. two assignments: b := c, a := b start with node c:
	// Call graph: move(c, NULL) -> move(b, c) -> move(a, b)
	// Generates moves in this order: move b to a and move c to b
	// ie. cycle a := b, b := a start with node a
	// Call graph: move(a, NULL) -> move(b, a) -> move(a, b)
	// Generates moves in this order: move b to temp, move a to b, move temp to a
	private void move(PhiResolverNode dest, PhiResolverNode src) {
	if (!dest.visited) {
	dest.visited = true;
	for (int i = dest.destinations.size() - 1; i >= 0; i--) {
	move(dest.destinations.get(i), dest);
	}
	} else if (!dest.startNode) {
	// cycle in graph detected
	assert loop == null : "only one loop valid!";
	loop = dest;
	moveToTemp(src.operand);
	return;
	} // else dest is a start node

	if (!dest.assigned) {
	if (loop == dest) {
	moveTempTo(dest.operand);
	dest.assigned = true;
	} else if (src != null) {
	emitMove(dest.operand, src.operand);
	dest.assigned = true;
	}
	}
	}

	private void moveTempTo(Value dest) {
	assert isLegal(temp);
	emitMove(dest, temp);
	temp = ILLEGAL;
	}

	private void moveToTemp(Value src) {
	assert isIllegal(temp);
	temp = gen.newVariable(src.getValueKind());
	emitMove(temp, src);
	}

	private PhiResolverNode sourceNode(Value opr) {
	return createNode(opr, true);
	}
	}