1 /*
   2  * Copyright (c) 2012, 2015, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  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 package org.graalvm.compiler.loop;
  24 
  25 import static org.graalvm.compiler.loop.MathUtil.add;
  26 import static org.graalvm.compiler.loop.MathUtil.divBefore;
  27 import static org.graalvm.compiler.loop.MathUtil.sub;
  28 
  29 import org.graalvm.compiler.core.common.type.IntegerStamp;
  30 import org.graalvm.compiler.core.common.type.Stamp;
  31 import org.graalvm.compiler.loop.InductionVariable.Direction;
  32 import org.graalvm.compiler.nodes.AbstractBeginNode;
  33 import org.graalvm.compiler.nodes.ConstantNode;
  34 import org.graalvm.compiler.nodes.GuardNode;
  35 import org.graalvm.compiler.nodes.IfNode;
  36 import org.graalvm.compiler.nodes.StructuredGraph;
  37 import org.graalvm.compiler.nodes.ValueNode;
  38 import org.graalvm.compiler.nodes.calc.CompareNode;
  39 import org.graalvm.compiler.nodes.calc.ConditionalNode;
  40 import org.graalvm.compiler.nodes.calc.IntegerLessThanNode;
  41 import org.graalvm.compiler.nodes.extended.GuardingNode;
  42 
  43 import jdk.vm.ci.code.CodeUtil;
  44 import jdk.vm.ci.meta.DeoptimizationAction;
  45 import jdk.vm.ci.meta.DeoptimizationReason;
  46 import jdk.vm.ci.meta.JavaConstant;
  47 
  48 public class CountedLoopInfo {
  49 
  50     private final LoopEx loop;
  51     private InductionVariable iv;
  52     private ValueNode end;
  53     private boolean oneOff;
  54     private AbstractBeginNode body;
  55     private IfNode ifNode;
  56 
  57     CountedLoopInfo(LoopEx loop, InductionVariable iv, IfNode ifNode, ValueNode end, boolean oneOff, AbstractBeginNode body) {
  58         this.loop = loop;
  59         this.iv = iv;
  60         this.end = end;
  61         this.oneOff = oneOff;
  62         this.body = body;
  63         this.ifNode = ifNode;
  64     }
  65 
  66     public ValueNode maxTripCountNode() {
  67         return maxTripCountNode(false);
  68     }
  69 
  70     public ValueNode maxTripCountNode(boolean assumePositive) {
  71         StructuredGraph graph = iv.valueNode().graph();
  72         Stamp stamp = iv.valueNode().stamp();
  73         ValueNode range = sub(graph, end, iv.initNode());
  74 
  75         ValueNode oneDirection;
  76         if (iv.direction() == Direction.Up) {
  77             oneDirection = ConstantNode.forIntegerStamp(stamp, 1, graph);
  78         } else {
  79             assert iv.direction() == Direction.Down;
  80             oneDirection = ConstantNode.forIntegerStamp(stamp, -1, graph);
  81         }
  82         if (oneOff) {
  83             range = add(graph, range, oneDirection);
  84         }
  85         // round-away-from-zero divison: (range + stride -/+ 1) / stride
  86         ValueNode denominator = range;
  87         if (!oneDirection.stamp().equals(iv.strideNode().stamp())) {
  88             ValueNode subedRanged = sub(graph, range, oneDirection);
  89             denominator = add(graph, subedRanged, iv.strideNode());
  90         }
  91         ValueNode div = divBefore(graph, loop.entryPoint(), denominator, iv.strideNode());
  92 
  93         if (assumePositive) {
  94             return div;
  95         }
  96         ConstantNode zero = ConstantNode.forIntegerStamp(stamp, 0, graph);
  97         return graph.unique(new ConditionalNode(graph.unique(new IntegerLessThanNode(zero, div)), div, zero));
  98     }
  99 
 100     /**
 101      * @return true if the loop has constant bounds and the trip count is representable as a
 102      *         positive integer.
 103      */
 104     public boolean isConstantMaxTripCount() {
 105         /*
 106          * It's possible that the iteration range is too large to treat this as constant because it
 107          * will overflow.
 108          */
 109         return (hasConstantBounds() && rawConstantMaxTripCount() >= 0);
 110     }
 111 
 112     /**
 113      * @return true if the bounds on the iteration space are all constants.
 114      */
 115     public boolean hasConstantBounds() {
 116         return end instanceof ConstantNode && iv.isConstantInit() && iv.isConstantStride();
 117     }
 118 
 119     public long constantMaxTripCount() {
 120         assert isConstantMaxTripCount();
 121         return rawConstantMaxTripCount();
 122     }
 123 
 124     /**
 125      * Compute the raw value of the trip count for this loop. Since we don't have unsigned values
 126      * this may be outside representable positive values.
 127      */
 128     protected long rawConstantMaxTripCount() {
 129         assert iv.direction() != null;
 130         long off = oneOff ? iv.direction() == Direction.Up ? 1 : -1 : 0;
 131         long endValue = ((ConstantNode) end).asJavaConstant().asLong();
 132         try {
 133             // If no overflow occurs then negative values represent a trip count of 0
 134             long max = Math.subtractExact(Math.addExact(endValue, off), iv.constantInit()) / iv.constantStride();
 135             return Math.max(0, max);
 136         } catch (ArithmeticException e) {
 137             /*
 138              * The computation overflowed to return a negative value. It's possible some
 139              * optimization could handle this value as an unsigned and produce the right answer but
 140              * we hide this value by default.
 141              */
 142             return -1;
 143         }
 144     }
 145 
 146     public boolean isExactTripCount() {
 147         return loop.loopBegin().loopExits().count() == 1;
 148     }
 149 
 150     public ValueNode exactTripCountNode() {
 151         assert isExactTripCount();
 152         return maxTripCountNode();
 153     }
 154 
 155     public boolean isConstantExactTripCount() {
 156         assert isExactTripCount();
 157         return isConstantMaxTripCount();
 158     }
 159 
 160     public long constantExactTripCount() {
 161         assert isExactTripCount();
 162         return constantMaxTripCount();
 163     }
 164 
 165     @Override
 166     public String toString() {
 167         return "iv=" + iv + " until " + end + (oneOff ? iv.direction() == Direction.Up ? "+1" : "-1" : "");
 168     }
 169 
 170     public ValueNode getLimit() {
 171         return end;
 172     }
 173 
 174     public IfNode getLimitTest() {
 175         return ifNode;
 176     }
 177 
 178     public ValueNode getStart() {
 179         return iv.initNode();
 180     }
 181 
 182     public boolean isLimitIncluded() {
 183         return oneOff;
 184     }
 185 
 186     public AbstractBeginNode getBody() {
 187         return body;
 188     }
 189 
 190     public Direction getDirection() {
 191         return iv.direction();
 192     }
 193 
 194     public InductionVariable getCounter() {
 195         return iv;
 196     }
 197 
 198     public GuardingNode getOverFlowGuard() {
 199         return loop.loopBegin().getOverflowGuard();
 200     }
 201 
 202     public GuardingNode createOverFlowGuard() {
 203         GuardingNode overflowGuard = getOverFlowGuard();
 204         if (overflowGuard != null) {
 205             return overflowGuard;
 206         }
 207         IntegerStamp stamp = (IntegerStamp) iv.valueNode().stamp();
 208         StructuredGraph graph = iv.valueNode().graph();
 209         CompareNode cond; // we use a negated guard with a < condition to achieve a >=
 210         ConstantNode one = ConstantNode.forIntegerStamp(stamp, 1, graph);
 211         if (iv.direction() == Direction.Up) {
 212             ValueNode v1 = sub(graph, ConstantNode.forIntegerStamp(stamp, CodeUtil.maxValue(stamp.getBits()), graph), sub(graph, iv.strideNode(), one));
 213             if (oneOff) {
 214                 v1 = sub(graph, v1, one);
 215             }
 216             cond = graph.unique(new IntegerLessThanNode(v1, end));
 217         } else {
 218             assert iv.direction() == Direction.Down;
 219             ValueNode v1 = add(graph, ConstantNode.forIntegerStamp(stamp, CodeUtil.minValue(stamp.getBits()), graph), sub(graph, one, iv.strideNode()));
 220             if (oneOff) {
 221                 v1 = add(graph, v1, one);
 222             }
 223             cond = graph.unique(new IntegerLessThanNode(end, v1));
 224         }
 225         assert graph.getGuardsStage().allowsFloatingGuards();
 226         overflowGuard = graph.unique(new GuardNode(cond, AbstractBeginNode.prevBegin(loop.entryPoint()), DeoptimizationReason.LoopLimitCheck, DeoptimizationAction.InvalidateRecompile, true,
 227                         JavaConstant.NULL_POINTER)); // TODO gd: use speculation
 228         loop.loopBegin().setOverflowGuard(overflowGuard);
 229         return overflowGuard;
 230     }
 231 
 232     public IntegerStamp getStamp() {
 233         return (IntegerStamp) iv.valueNode().stamp();
 234     }
 235 }
--- EOF ---