< prev index next >

src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.loop/src/org/graalvm/compiler/loop/LoopFragmentInside.java

Print this page
rev 52509 : [mq]: graal2


  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 
  24 
  25 package org.graalvm.compiler.loop;
  26 
  27 import java.util.ArrayList;
  28 import java.util.LinkedList;
  29 import java.util.List;
  30 
  31 import jdk.internal.vm.compiler.collections.EconomicMap;
  32 import jdk.internal.vm.compiler.collections.Equivalence;

  33 import org.graalvm.compiler.debug.DebugCloseable;
  34 import org.graalvm.compiler.debug.DebugContext;
  35 import org.graalvm.compiler.debug.GraalError;
  36 import org.graalvm.compiler.graph.Graph.DuplicationReplacement;
  37 import org.graalvm.compiler.graph.Node;
  38 import org.graalvm.compiler.graph.NodeBitMap;
  39 import org.graalvm.compiler.graph.iterators.NodeIterable;
  40 import org.graalvm.compiler.nodes.AbstractBeginNode;
  41 import org.graalvm.compiler.nodes.AbstractEndNode;
  42 import org.graalvm.compiler.nodes.AbstractMergeNode;
  43 import org.graalvm.compiler.nodes.BeginNode;
  44 import org.graalvm.compiler.nodes.ConstantNode;
  45 import org.graalvm.compiler.nodes.EndNode;
  46 import org.graalvm.compiler.nodes.FixedNode;
  47 import org.graalvm.compiler.nodes.FixedWithNextNode;
  48 import org.graalvm.compiler.nodes.FrameState;
  49 import org.graalvm.compiler.nodes.GuardPhiNode;
  50 import org.graalvm.compiler.nodes.IfNode;
  51 import org.graalvm.compiler.nodes.LogicNode;
  52 import org.graalvm.compiler.nodes.LoopBeginNode;
  53 import org.graalvm.compiler.nodes.LoopEndNode;
  54 import org.graalvm.compiler.nodes.LoopExitNode;
  55 import org.graalvm.compiler.nodes.MergeNode;
  56 import org.graalvm.compiler.nodes.NodeView;
  57 import org.graalvm.compiler.nodes.PhiNode;
  58 import org.graalvm.compiler.nodes.ProxyNode;
  59 import org.graalvm.compiler.nodes.SafepointNode;
  60 import org.graalvm.compiler.nodes.StateSplit;
  61 import org.graalvm.compiler.nodes.StructuredGraph;
  62 import org.graalvm.compiler.nodes.ValueNode;
  63 import org.graalvm.compiler.nodes.ValuePhiNode;
  64 import org.graalvm.compiler.nodes.VirtualState.NodeClosure;
  65 import org.graalvm.compiler.nodes.calc.AddNode;
  66 import org.graalvm.compiler.nodes.calc.CompareNode;


  67 import org.graalvm.compiler.nodes.calc.SubNode;

  68 import org.graalvm.compiler.nodes.memory.MemoryPhiNode;
  69 import org.graalvm.compiler.nodes.util.GraphUtil;
  70 


  71 public class LoopFragmentInside extends LoopFragment {
  72 
  73     /**
  74      * mergedInitializers. When an inside fragment's (loop)ends are merged to create a unique exit
  75      * point, some phis must be created : they phis together all the back-values of the loop-phis
  76      * These can then be used to update the loop-phis' forward edge value ('initializer') in the
  77      * peeling case. In the unrolling case they will be used as the value that replace the loop-phis
  78      * of the duplicated inside fragment
  79      */
  80     private EconomicMap<PhiNode, ValueNode> mergedInitializers;
  81     private final DuplicationReplacement dataFixBefore = new DuplicationReplacement() {
  82 
  83         @Override
  84         public Node replacement(Node oriInput) {
  85             if (!(oriInput instanceof ValueNode)) {
  86                 return oriInput;
  87             }
  88             return prim((ValueNode) oriInput);
  89         }
  90     };


 133     @Override
 134     public void insertBefore(LoopEx loop) {
 135         assert this.isDuplicate() && this.original().loop() == loop;
 136 
 137         patchNodes(dataFixBefore);
 138 
 139         AbstractBeginNode end = mergeEnds();
 140 
 141         mergeEarlyExits();
 142 
 143         original().patchPeeling(this);
 144 
 145         AbstractBeginNode entry = getDuplicatedNode(loop.loopBegin());
 146         loop.entryPoint().replaceAtPredecessor(entry);
 147         end.setNext(loop.entryPoint());
 148     }
 149 
 150     /**
 151      * Duplicate the body within the loop after the current copy copy of the body, updating the
 152      * iteration limit to account for the duplication.
 153      *
 154      * @param loop
 155      */
 156     public void insertWithinAfter(LoopEx loop) {
 157         insertWithinAfter(loop, true);
 158     }
 159 
 160     /**
 161      * Duplicate the body within the loop after the current copy copy of the body.
 162      *
 163      * @param loop
 164      * @param updateLimit true if the iteration limit should be adjusted.
 165      */
 166     public void insertWithinAfter(LoopEx loop, boolean updateLimit) {
 167         assert isDuplicate() && original().loop() == loop;
 168 
 169         patchNodes(dataFixWithinAfter);
 170 
 171         /*
 172          * Collect any new back edges values before updating them since they might reference each
 173          * other.
 174          */
 175         LoopBeginNode mainLoopBegin = loop.loopBegin();
 176         ArrayList<ValueNode> backedgeValues = new ArrayList<>();
 177         for (PhiNode mainPhiNode : mainLoopBegin.phis()) {
 178             ValueNode duplicatedNode = getDuplicatedNode(mainPhiNode.valueAt(1));
 179             if (duplicatedNode == null) {
 180                 if (mainLoopBegin.isPhiAtMerge(mainPhiNode.valueAt(1))) {
 181                     duplicatedNode = ((PhiNode) (mainPhiNode.valueAt(1))).valueAt(1);
 182                 } else {
 183                     assert mainPhiNode.valueAt(1).isConstant() : mainPhiNode.valueAt(1);
 184                 }
 185             }
 186             backedgeValues.add(duplicatedNode);
 187         }
 188         int index = 0;
 189         for (PhiNode mainPhiNode : mainLoopBegin.phis()) {
 190             ValueNode duplicatedNode = backedgeValues.get(index++);
 191             if (duplicatedNode != null) {
 192                 mainPhiNode.setValueAt(1, duplicatedNode);
 193             }
 194         }
 195 
 196         placeNewSegmentAndCleanup(loop);
 197 
 198         // Remove any safepoints from the original copy leaving only the duplicated one
 199         assert loop.whole().nodes().filter(SafepointNode.class).count() == nodes().filter(SafepointNode.class).count();
 200         for (SafepointNode safepoint : loop.whole().nodes().filter(SafepointNode.class)) {
 201             graph().removeFixed(safepoint);
 202         }
 203 
 204         int unrollFactor = mainLoopBegin.getUnrollFactor();
 205         StructuredGraph graph = mainLoopBegin.graph();
 206         if (updateLimit) {
 207             // Now use the previous unrollFactor to update the exit condition to power of two
 208             InductionVariable iv = loop.counted().getCounter();
 209             CompareNode compareNode = (CompareNode) loop.counted().getLimitTest().condition();
 210             ValueNode compareBound;
 211             if (compareNode.getX() == iv.valueNode()) {
 212                 compareBound = compareNode.getY();
 213             } else if (compareNode.getY() == iv.valueNode()) {
 214                 compareBound = compareNode.getX();







 215             } else {
 216                 throw GraalError.shouldNotReachHere();
 217             }
 218             long originalStride = unrollFactor == 1 ? iv.constantStride() : iv.constantStride() / unrollFactor;
 219             if (iv.direction() == InductionVariable.Direction.Up) {
 220                 ConstantNode aboveVal = graph.unique(ConstantNode.forIntegerStamp(iv.initNode().stamp(NodeView.DEFAULT), unrollFactor * originalStride));
 221                 ValueNode newLimit = graph.addWithoutUnique(new SubNode(compareBound, aboveVal));
 222                 compareNode.replaceFirstInput(compareBound, newLimit);
 223             } else if (iv.direction() == InductionVariable.Direction.Down) {
 224                 ConstantNode aboveVal = graph.unique(ConstantNode.forIntegerStamp(iv.initNode().stamp(NodeView.DEFAULT), unrollFactor * -originalStride));
 225                 ValueNode newLimit = graph.addWithoutUnique(new AddNode(compareBound, aboveVal));
 226                 compareNode.replaceFirstInput(compareBound, newLimit);





 227             }
 228         }
 229         mainLoopBegin.setUnrollFactor(unrollFactor * 2);
 230         mainLoopBegin.setLoopFrequency(mainLoopBegin.loopFrequency() / 2);
 231         graph.getDebug().dump(DebugContext.DETAILED_LEVEL, graph, "LoopPartialUnroll %s", loop);
 232 
 233         mainLoopBegin.getDebug().dump(DebugContext.VERBOSE_LEVEL, mainLoopBegin.graph(), "After insertWithinAfter %s", mainLoopBegin);
 234     }
 235 
 236     private void placeNewSegmentAndCleanup(LoopEx loop) {
 237         CountedLoopInfo mainCounted = loop.counted();
 238         LoopBeginNode mainLoopBegin = loop.loopBegin();
 239         // Discard the segment entry and its flow, after if merging it into the loop
 240         StructuredGraph graph = mainLoopBegin.graph();
 241         IfNode loopTest = mainCounted.getLimitTest();
 242         IfNode newSegmentTest = getDuplicatedNode(loopTest);
 243         AbstractBeginNode trueSuccessor = loopTest.trueSuccessor();
 244         AbstractBeginNode falseSuccessor = loopTest.falseSuccessor();
 245         FixedNode firstNode;
 246         boolean codeInTrueSide = false;
 247         if (trueSuccessor == mainCounted.getBody()) {
 248             firstNode = trueSuccessor.next();
 249             codeInTrueSide = true;




  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 
  24 
  25 package org.graalvm.compiler.loop;
  26 
  27 import java.util.ArrayList;
  28 import java.util.LinkedList;
  29 import java.util.List;
  30 
  31 import jdk.internal.vm.compiler.collections.EconomicMap;
  32 import jdk.internal.vm.compiler.collections.Equivalence;
  33 import org.graalvm.compiler.core.common.type.IntegerStamp;
  34 import org.graalvm.compiler.debug.DebugCloseable;
  35 import org.graalvm.compiler.debug.DebugContext;
  36 import org.graalvm.compiler.debug.GraalError;
  37 import org.graalvm.compiler.graph.Graph.DuplicationReplacement;
  38 import org.graalvm.compiler.graph.Node;
  39 import org.graalvm.compiler.graph.NodeBitMap;
  40 import org.graalvm.compiler.graph.iterators.NodeIterable;
  41 import org.graalvm.compiler.nodes.AbstractBeginNode;
  42 import org.graalvm.compiler.nodes.AbstractEndNode;
  43 import org.graalvm.compiler.nodes.AbstractMergeNode;
  44 import org.graalvm.compiler.nodes.BeginNode;
  45 import org.graalvm.compiler.nodes.ConstantNode;
  46 import org.graalvm.compiler.nodes.EndNode;
  47 import org.graalvm.compiler.nodes.FixedNode;
  48 import org.graalvm.compiler.nodes.FixedWithNextNode;
  49 import org.graalvm.compiler.nodes.FrameState;
  50 import org.graalvm.compiler.nodes.GuardPhiNode;
  51 import org.graalvm.compiler.nodes.IfNode;
  52 import org.graalvm.compiler.nodes.LogicNode;
  53 import org.graalvm.compiler.nodes.LoopBeginNode;
  54 import org.graalvm.compiler.nodes.LoopEndNode;
  55 import org.graalvm.compiler.nodes.LoopExitNode;
  56 import org.graalvm.compiler.nodes.MergeNode;
  57 import org.graalvm.compiler.nodes.NodeView;
  58 import org.graalvm.compiler.nodes.PhiNode;
  59 import org.graalvm.compiler.nodes.ProxyNode;
  60 import org.graalvm.compiler.nodes.SafepointNode;
  61 import org.graalvm.compiler.nodes.StateSplit;
  62 import org.graalvm.compiler.nodes.StructuredGraph;
  63 import org.graalvm.compiler.nodes.ValueNode;
  64 import org.graalvm.compiler.nodes.ValuePhiNode;
  65 import org.graalvm.compiler.nodes.VirtualState.NodeClosure;
  66 import org.graalvm.compiler.nodes.calc.AddNode;
  67 import org.graalvm.compiler.nodes.calc.CompareNode;
  68 import org.graalvm.compiler.nodes.calc.ConditionalNode;
  69 import org.graalvm.compiler.nodes.calc.IntegerBelowNode;
  70 import org.graalvm.compiler.nodes.calc.SubNode;
  71 import org.graalvm.compiler.nodes.extended.OpaqueNode;
  72 import org.graalvm.compiler.nodes.memory.MemoryPhiNode;
  73 import org.graalvm.compiler.nodes.util.GraphUtil;
  74 
  75 import jdk.vm.ci.code.CodeUtil;
  76 
  77 public class LoopFragmentInside extends LoopFragment {
  78 
  79     /**
  80      * mergedInitializers. When an inside fragment's (loop)ends are merged to create a unique exit
  81      * point, some phis must be created : they phis together all the back-values of the loop-phis
  82      * These can then be used to update the loop-phis' forward edge value ('initializer') in the
  83      * peeling case. In the unrolling case they will be used as the value that replace the loop-phis
  84      * of the duplicated inside fragment
  85      */
  86     private EconomicMap<PhiNode, ValueNode> mergedInitializers;
  87     private final DuplicationReplacement dataFixBefore = new DuplicationReplacement() {
  88 
  89         @Override
  90         public Node replacement(Node oriInput) {
  91             if (!(oriInput instanceof ValueNode)) {
  92                 return oriInput;
  93             }
  94             return prim((ValueNode) oriInput);
  95         }
  96     };


 139     @Override
 140     public void insertBefore(LoopEx loop) {
 141         assert this.isDuplicate() && this.original().loop() == loop;
 142 
 143         patchNodes(dataFixBefore);
 144 
 145         AbstractBeginNode end = mergeEnds();
 146 
 147         mergeEarlyExits();
 148 
 149         original().patchPeeling(this);
 150 
 151         AbstractBeginNode entry = getDuplicatedNode(loop.loopBegin());
 152         loop.entryPoint().replaceAtPredecessor(entry);
 153         end.setNext(loop.entryPoint());
 154     }
 155 
 156     /**
 157      * Duplicate the body within the loop after the current copy copy of the body, updating the
 158      * iteration limit to account for the duplication.


 159      */
 160     public void insertWithinAfter(LoopEx loop, EconomicMap<LoopBeginNode, OpaqueNode> opaqueUnrolledStrides) {










 161         assert isDuplicate() && original().loop() == loop;
 162 
 163         patchNodes(dataFixWithinAfter);
 164 
 165         /*
 166          * Collect any new back edges values before updating them since they might reference each
 167          * other.
 168          */
 169         LoopBeginNode mainLoopBegin = loop.loopBegin();
 170         ArrayList<ValueNode> backedgeValues = new ArrayList<>();
 171         for (PhiNode mainPhiNode : mainLoopBegin.phis()) {
 172             ValueNode duplicatedNode = getDuplicatedNode(mainPhiNode.valueAt(1));
 173             if (duplicatedNode == null) {
 174                 if (mainLoopBegin.isPhiAtMerge(mainPhiNode.valueAt(1))) {
 175                     duplicatedNode = ((PhiNode) (mainPhiNode.valueAt(1))).valueAt(1);
 176                 } else {
 177                     assert mainPhiNode.valueAt(1).isConstant() : mainPhiNode.valueAt(1);
 178                 }
 179             }
 180             backedgeValues.add(duplicatedNode);
 181         }
 182         int index = 0;
 183         for (PhiNode mainPhiNode : mainLoopBegin.phis()) {
 184             ValueNode duplicatedNode = backedgeValues.get(index++);
 185             if (duplicatedNode != null) {
 186                 mainPhiNode.setValueAt(1, duplicatedNode);
 187             }
 188         }
 189 
 190         placeNewSegmentAndCleanup(loop);
 191 
 192         // Remove any safepoints from the original copy leaving only the duplicated one
 193         assert loop.whole().nodes().filter(SafepointNode.class).count() == nodes().filter(SafepointNode.class).count();
 194         for (SafepointNode safepoint : loop.whole().nodes().filter(SafepointNode.class)) {
 195             graph().removeFixed(safepoint);
 196         }
 197 

 198         StructuredGraph graph = mainLoopBegin.graph();
 199         if (opaqueUnrolledStrides != null) {
 200             OpaqueNode opaque = opaqueUnrolledStrides.get(loop.loopBegin());
 201             CountedLoopInfo counted = loop.counted();
 202             ValueNode counterStride = counted.getCounter().strideNode();
 203             if (opaque == null) {
 204                 opaque = new OpaqueNode(AddNode.add(counterStride, counterStride, NodeView.DEFAULT));
 205                 ValueNode limit = counted.getLimit();
 206                 int bits = ((IntegerStamp) limit.stamp(NodeView.DEFAULT)).getBits();
 207                 ValueNode newLimit = SubNode.create(limit, opaque, NodeView.DEFAULT);
 208                 LogicNode overflowCheck;
 209                 ConstantNode extremum;
 210                 if (counted.getDirection() == InductionVariable.Direction.Up) {
 211                     // limit - counterStride could overflow negatively if limit - min <
 212                     // counterStride
 213                     extremum = ConstantNode.forIntegerBits(bits, CodeUtil.minValue(bits));
 214                     overflowCheck = IntegerBelowNode.create(SubNode.create(limit, extremum, NodeView.DEFAULT), opaque, NodeView.DEFAULT);
 215                 } else {
 216                     assert counted.getDirection() == InductionVariable.Direction.Down;
 217                     // limit - counterStride could overflow if max - limit < -counterStride
 218                     // i.e., counterStride < limit - max
 219                     extremum = ConstantNode.forIntegerBits(bits, CodeUtil.maxValue(bits));
 220                     overflowCheck = IntegerBelowNode.create(opaque, SubNode.create(limit, extremum, NodeView.DEFAULT), NodeView.DEFAULT);
 221                 }
 222                 newLimit = ConditionalNode.create(overflowCheck, extremum, newLimit, NodeView.DEFAULT);
 223                 CompareNode compareNode = (CompareNode) counted.getLimitTest().condition();
 224                 compareNode.replaceFirstInput(limit, graph.addOrUniqueWithInputs(newLimit));
 225                 opaqueUnrolledStrides.put(loop.loopBegin(), opaque);
 226             } else {
 227                 assert counted.getCounter().isConstantStride();
 228                 assert Math.addExact(counted.getCounter().constantStride(), counted.getCounter().constantStride()) == counted.getCounter().constantStride() * 2;
 229                 ValueNode previousValue = opaque.getValue();
 230                 opaque.setValue(graph.addOrUniqueWithInputs(AddNode.add(counterStride, previousValue, NodeView.DEFAULT)));
 231                 GraphUtil.tryKillUnused(previousValue);
 232             }
 233         }
 234         mainLoopBegin.setUnrollFactor(mainLoopBegin.getUnrollFactor() * 2);
 235         mainLoopBegin.setLoopFrequency(mainLoopBegin.loopFrequency() / 2);
 236         graph.getDebug().dump(DebugContext.DETAILED_LEVEL, graph, "LoopPartialUnroll %s", loop);
 237 
 238         mainLoopBegin.getDebug().dump(DebugContext.VERBOSE_LEVEL, mainLoopBegin.graph(), "After insertWithinAfter %s", mainLoopBegin);
 239     }
 240 
 241     private void placeNewSegmentAndCleanup(LoopEx loop) {
 242         CountedLoopInfo mainCounted = loop.counted();
 243         LoopBeginNode mainLoopBegin = loop.loopBegin();
 244         // Discard the segment entry and its flow, after if merging it into the loop
 245         StructuredGraph graph = mainLoopBegin.graph();
 246         IfNode loopTest = mainCounted.getLimitTest();
 247         IfNode newSegmentTest = getDuplicatedNode(loopTest);
 248         AbstractBeginNode trueSuccessor = loopTest.trueSuccessor();
 249         AbstractBeginNode falseSuccessor = loopTest.falseSuccessor();
 250         FixedNode firstNode;
 251         boolean codeInTrueSide = false;
 252         if (trueSuccessor == mainCounted.getBody()) {
 253             firstNode = trueSuccessor.next();
 254             codeInTrueSide = true;


< prev index next >