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.StructuredGraph; 36 import org.graalvm.compiler.nodes.ValueNode; 37 import org.graalvm.compiler.nodes.calc.CompareNode; 38 import org.graalvm.compiler.nodes.calc.ConditionalNode; 39 import org.graalvm.compiler.nodes.calc.IntegerLessThanNode; 40 import org.graalvm.compiler.nodes.extended.GuardingNode; 41 42 import jdk.vm.ci.code.CodeUtil; 43 import jdk.vm.ci.meta.DeoptimizationAction; 44 import jdk.vm.ci.meta.DeoptimizationReason; 45 import jdk.vm.ci.meta.JavaConstant; 46 47 public class CountedLoopInfo { 48 49 private final LoopEx loop; 50 private InductionVariable iv; 51 private ValueNode end; 52 private boolean oneOff; 53 private AbstractBeginNode body; 54 55 CountedLoopInfo(LoopEx loop, InductionVariable iv, ValueNode end, boolean oneOff, AbstractBeginNode body) { 56 this.loop = loop; 57 this.iv = iv; 58 this.end = end; 59 this.oneOff = oneOff; 60 this.body = body; 61 } 62 63 public ValueNode maxTripCountNode() { 64 return maxTripCountNode(false); 65 } 66 67 public ValueNode maxTripCountNode(boolean assumePositive) { 68 StructuredGraph graph = iv.valueNode().graph(); 69 Stamp stamp = iv.valueNode().stamp(); 70 ValueNode range = sub(graph, end, iv.initNode()); 71 72 ValueNode oneDirection; 73 if (iv.direction() == Direction.Up) { 74 oneDirection = ConstantNode.forIntegerStamp(stamp, 1, graph); 75 } else { 76 assert iv.direction() == Direction.Down; 77 oneDirection = ConstantNode.forIntegerStamp(stamp, -1, graph); 78 } 79 if (oneOff) { 80 range = add(graph, range, oneDirection); 81 } 82 // round-away-from-zero divison: (range + stride -/+ 1) / stride 83 ValueNode denominator = add(graph, sub(graph, range, oneDirection), iv.strideNode()); 84 ValueNode div = divBefore(graph, loop.entryPoint(), denominator, iv.strideNode()); 85 86 if (assumePositive) { 87 return div; 88 } 89 ConstantNode zero = ConstantNode.forIntegerStamp(stamp, 0, graph); 90 return graph.unique(new ConditionalNode(graph.unique(new IntegerLessThanNode(zero, div)), div, zero)); 91 } 92 93 /** 94 * @return true if the loop has constant bounds and the trip count is representable as a 95 * positive integer. 96 */ 97 public boolean isConstantMaxTripCount() { 98 /* 99 * It's possible that the iteration range is too large to treat this as constant because it 100 * will overflow. 101 */ 102 return (hasConstantBounds() && rawConstantMaxTripCount() >= 0); 103 } 104 105 /** 106 * @return true if the bounds on the iteration space are all constants. 107 */ 108 public boolean hasConstantBounds() { 109 return end instanceof ConstantNode && iv.isConstantInit() && iv.isConstantStride(); 110 } 111 112 public long constantMaxTripCount() { 113 assert isConstantMaxTripCount(); 114 return rawConstantMaxTripCount(); 115 } 116 117 /** 118 * Compute the raw value of the trip count for this loop. Since we don't have unsigned values 119 * this may be outside representable positive values. 120 */ 121 protected long rawConstantMaxTripCount() { 122 assert iv.direction() != null; 123 long off = oneOff ? iv.direction() == Direction.Up ? 1 : -1 : 0; 124 long endValue = ((ConstantNode) end).asJavaConstant().asLong(); 125 try { 126 // If no overflow occurs then negative values represent a trip count of 0 127 long max = Math.subtractExact(Math.addExact(endValue, off), iv.constantInit()) / iv.constantStride(); 128 return Math.max(0, max); 129 } catch (ArithmeticException e) { 130 /* 131 * The computation overflowed to return a negative value. It's possible some 132 * optimization could handle this value as an unsigned and produce the right answer but 133 * we hide this value by default. 134 */ 135 return -1; 136 } 137 } 138 139 public boolean isExactTripCount() { 140 return loop.loopBegin().loopExits().count() == 1; 141 } 142 143 public ValueNode exactTripCountNode() { 144 assert isExactTripCount(); 145 return maxTripCountNode(); 146 } 147 148 public boolean isConstantExactTripCount() { 149 assert isExactTripCount(); 150 return isConstantMaxTripCount(); 151 } 152 153 public long constantExactTripCount() { 154 assert isExactTripCount(); 155 return constantMaxTripCount(); 156 } 157 158 @Override 159 public String toString() { 160 return "iv=" + iv + " until " + end + (oneOff ? iv.direction() == Direction.Up ? "+1" : "-1" : ""); 161 } 162 163 public ValueNode getLimit() { 164 return end; 165 } 166 167 public ValueNode getStart() { 168 return iv.initNode(); 169 } 170 171 public boolean isLimitIncluded() { 172 return oneOff; 173 } 174 175 public AbstractBeginNode getBody() { 176 return body; 177 } 178 179 public Direction getDirection() { 180 return iv.direction(); 181 } 182 183 public InductionVariable getCounter() { 184 return iv; 185 } 186 187 public GuardingNode getOverFlowGuard() { 188 return loop.loopBegin().getOverflowGuard(); 189 } 190 191 public GuardingNode createOverFlowGuard() { 192 GuardingNode overflowGuard = getOverFlowGuard(); 193 if (overflowGuard != null) { 194 return overflowGuard; 195 } 196 IntegerStamp stamp = (IntegerStamp) iv.valueNode().stamp(); 197 StructuredGraph graph = iv.valueNode().graph(); 198 CompareNode cond; // we use a negated guard with a < condition to achieve a >= 199 ConstantNode one = ConstantNode.forIntegerStamp(stamp, 1, graph); 200 if (iv.direction() == Direction.Up) { 201 ValueNode v1 = sub(graph, ConstantNode.forIntegerStamp(stamp, CodeUtil.maxValue(stamp.getBits()), graph), sub(graph, iv.strideNode(), one)); 202 if (oneOff) { 203 v1 = sub(graph, v1, one); 204 } 205 cond = graph.unique(new IntegerLessThanNode(v1, end)); 206 } else { 207 assert iv.direction() == Direction.Down; 208 ValueNode v1 = add(graph, ConstantNode.forIntegerStamp(stamp, CodeUtil.minValue(stamp.getBits()), graph), sub(graph, one, iv.strideNode())); 209 if (oneOff) { 210 v1 = add(graph, v1, one); 211 } 212 cond = graph.unique(new IntegerLessThanNode(end, v1)); 213 } 214 assert graph.getGuardsStage().allowsFloatingGuards(); 215 overflowGuard = graph.unique(new GuardNode(cond, AbstractBeginNode.prevBegin(loop.entryPoint()), DeoptimizationReason.LoopLimitCheck, DeoptimizationAction.InvalidateRecompile, true, 216 JavaConstant.NULL_POINTER)); // TODO gd: use speculation 217 loop.loopBegin().setOverflowGuard(overflowGuard); 218 return overflowGuard; 219 } 220 221 public IntegerStamp getStamp() { 222 return (IntegerStamp) iv.valueNode().stamp(); 223 } 224 }