1 /* 2 * Copyright (c) 2012, 2018, 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 24 25 package org.graalvm.compiler.loop; 26 27 import static java.lang.Math.abs; 28 import static org.graalvm.compiler.loop.MathUtil.unsignedDivBefore; 29 import static org.graalvm.compiler.nodes.calc.BinaryArithmeticNode.add; 30 import static org.graalvm.compiler.nodes.calc.BinaryArithmeticNode.sub; 31 32 import org.graalvm.compiler.core.common.NumUtil; 33 import org.graalvm.compiler.core.common.type.IntegerStamp; 34 import org.graalvm.compiler.core.common.type.Stamp; 35 import org.graalvm.compiler.core.common.util.UnsignedLong; 36 import org.graalvm.compiler.debug.DebugCloseable; 37 import org.graalvm.compiler.loop.InductionVariable.Direction; 38 import org.graalvm.compiler.nodes.AbstractBeginNode; 39 import org.graalvm.compiler.nodes.ConstantNode; 40 import org.graalvm.compiler.nodes.GuardNode; 41 import org.graalvm.compiler.nodes.IfNode; 42 import org.graalvm.compiler.nodes.LogicNode; 43 import org.graalvm.compiler.nodes.NodeView; 44 import org.graalvm.compiler.nodes.StructuredGraph; 45 import org.graalvm.compiler.nodes.ValueNode; 46 import org.graalvm.compiler.nodes.calc.ConditionalNode; 47 import org.graalvm.compiler.nodes.calc.IntegerLessThanNode; 48 import org.graalvm.compiler.nodes.calc.NegateNode; 49 import org.graalvm.compiler.nodes.extended.GuardingNode; 50 import org.graalvm.compiler.nodes.util.GraphUtil; 51 52 import jdk.vm.ci.meta.DeoptimizationAction; 53 import jdk.vm.ci.meta.DeoptimizationReason; 54 import jdk.vm.ci.meta.SpeculationLog; 55 56 public class CountedLoopInfo { 57 58 private final LoopEx loop; 59 private InductionVariable iv; 60 private ValueNode end; 61 private boolean oneOff; 62 private AbstractBeginNode body; 63 private IfNode ifNode; 64 65 CountedLoopInfo(LoopEx loop, InductionVariable iv, IfNode ifNode, ValueNode end, boolean oneOff, AbstractBeginNode body) { 66 assert iv.direction() != null; 67 this.loop = loop; 68 this.iv = iv; 69 this.end = end; 70 this.oneOff = oneOff; 71 this.body = body; 72 this.ifNode = ifNode; 73 } 74 75 /** 76 * Returns a node that computes the maximum trip count of this loop. That is the trip count of 77 * this loop assuming it is not exited by an other exit than the {@linkplain #getLimitTest() 78 * count check}. 79 * 80 * This count is exact if {@link #isExactTripCount()} returns true. 81 * 82 * THIS VALUE SHOULD BE TREATED AS UNSIGNED. 83 */ 84 public ValueNode maxTripCountNode() { 85 return maxTripCountNode(false); 86 } 87 88 /** 89 * Returns a node that computes the maximum trip count of this loop. That is the trip count of 90 * this loop assuming it is not exited by an other exit than the {@linkplain #getLimitTest() 91 * count check}. 92 * 93 * This count is exact if {@link #isExactTripCount()} returns true. 94 * 95 * THIS VALUE SHOULD BE TREATED AS UNSIGNED. 96 * 97 * @param assumeLoopEntered if true the check that the loop is entered at all will be omitted. 98 */ 99 public ValueNode maxTripCountNode(boolean assumeLoopEntered) { 100 StructuredGraph graph = iv.valueNode().graph(); 101 Stamp stamp = iv.valueNode().stamp(NodeView.DEFAULT); 102 103 ValueNode max; 104 ValueNode min; 105 ValueNode absStride; 106 if (iv.direction() == Direction.Up) { 107 absStride = iv.strideNode(); 108 max = end; 109 min = iv.initNode(); 110 } else { 111 assert iv.direction() == Direction.Down; 112 absStride = NegateNode.create(iv.strideNode(), NodeView.DEFAULT); 113 max = iv.initNode(); 114 min = end; 115 } 116 ValueNode range = sub(max, min); 117 118 ConstantNode one = ConstantNode.forIntegerStamp(stamp, 1); 119 if (oneOff) { 120 range = add(range, one); 121 } 122 // round-away-from-zero divison: (range + stride -/+ 1) / stride 123 ValueNode denominator = add(range, sub(absStride, one)); 124 ValueNode div = unsignedDivBefore(graph, loop.entryPoint(), denominator, absStride, null); 125 126 if (assumeLoopEntered) { 127 return graph.addOrUniqueWithInputs(div); 128 } 129 ConstantNode zero = ConstantNode.forIntegerStamp(stamp, 0); 130 LogicNode noEntryCheck = IntegerLessThanNode.create(max, min, NodeView.DEFAULT); 131 return graph.addOrUniqueWithInputs(ConditionalNode.create(noEntryCheck, zero, div, NodeView.DEFAULT)); 132 } 133 134 /** 135 * @return true if the loop has constant bounds. 136 */ 137 public boolean isConstantMaxTripCount() { 138 return end instanceof ConstantNode && iv.isConstantInit() && iv.isConstantStride(); 139 } 140 141 public UnsignedLong constantMaxTripCount() { 142 assert isConstantMaxTripCount(); 143 return new UnsignedLong(rawConstantMaxTripCount()); 144 } 145 146 /** 147 * Compute the raw value of the trip count for this loop. THIS IS AN UNSIGNED VALUE; 148 */ 149 private long rawConstantMaxTripCount() { 150 assert iv.direction() != null; 151 long endValue = end.asJavaConstant().asLong(); 152 long initValue = iv.constantInit(); 153 long range; 154 long absStride; 155 if (iv.direction() == Direction.Up) { 156 if (endValue < initValue) { 157 return 0; 158 } 159 range = endValue - iv.constantInit(); 160 absStride = iv.constantStride(); 161 } else { 162 assert iv.direction() == Direction.Down; 163 if (initValue < endValue) { 164 return 0; 165 } 166 range = iv.constantInit() - endValue; 167 absStride = -iv.constantStride(); 168 } 169 if (oneOff) { 170 range += 1; 171 } 172 long denominator = range + absStride - 1; 173 return Long.divideUnsigned(denominator, absStride); 174 } 175 176 public boolean isExactTripCount() { 177 return loop.loop().getNaturalExits().size() == 1; 178 } 179 180 public ValueNode exactTripCountNode() { 181 assert isExactTripCount(); 182 return maxTripCountNode(); 183 } 184 185 public boolean isConstantExactTripCount() { 186 assert isExactTripCount(); 187 return isConstantMaxTripCount(); 188 } 189 190 public UnsignedLong constantExactTripCount() { 191 assert isExactTripCount(); 192 return constantMaxTripCount(); 193 } 194 195 @Override 196 public String toString() { 197 return "iv=" + iv + " until " + end + (oneOff ? iv.direction() == Direction.Up ? "+1" : "-1" : ""); 198 } 199 200 public ValueNode getLimit() { 201 return end; 202 } 203 204 public IfNode getLimitTest() { 205 return ifNode; 206 } 207 208 public ValueNode getStart() { 209 return iv.initNode(); 210 } 211 212 public boolean isLimitIncluded() { 213 return oneOff; 214 } 215 216 public AbstractBeginNode getBody() { 217 return body; 218 } 219 220 public AbstractBeginNode getCountedExit() { 221 if (getLimitTest().trueSuccessor() == getBody()) { 222 return getLimitTest().falseSuccessor(); 223 } else { 224 assert getLimitTest().falseSuccessor() == getBody(); 225 return getLimitTest().trueSuccessor(); 226 } 227 } 228 229 public Direction getDirection() { 230 return iv.direction(); 231 } 232 233 public InductionVariable getCounter() { 234 return iv; 235 } 236 237 public GuardingNode getOverFlowGuard() { 238 return loop.loopBegin().getOverflowGuard(); 239 } 240 241 public boolean counterNeverOverflows() { 242 if (iv.isConstantStride() && abs(iv.constantStride()) == 1) { 243 return true; 244 } 245 IntegerStamp endStamp = (IntegerStamp) end.stamp(NodeView.DEFAULT); 246 ValueNode strideNode = iv.strideNode(); 247 IntegerStamp strideStamp = (IntegerStamp) strideNode.stamp(NodeView.DEFAULT); 248 GraphUtil.tryKillUnused(strideNode); 249 if (getDirection() == Direction.Up) { 250 long max = NumUtil.maxValue(endStamp.getBits()); 251 return endStamp.upperBound() <= max - (strideStamp.upperBound() - 1) - (oneOff ? 1 : 0); 252 } else if (getDirection() == Direction.Down) { 253 long min = NumUtil.minValue(endStamp.getBits()); 254 return min + (1 - strideStamp.lowerBound()) + (oneOff ? 1 : 0) <= endStamp.lowerBound(); 255 } 256 return false; 257 } 258 259 @SuppressWarnings("try") 260 public GuardingNode createOverFlowGuard() { 261 GuardingNode overflowGuard = getOverFlowGuard(); 262 if (overflowGuard != null || counterNeverOverflows()) { 263 return overflowGuard; 264 } 265 try (DebugCloseable position = loop.loopBegin().withNodeSourcePosition()) { 266 IntegerStamp stamp = (IntegerStamp) iv.valueNode().stamp(NodeView.DEFAULT); 267 StructuredGraph graph = iv.valueNode().graph(); 268 LogicNode cond; // we use a negated guard with a < condition to achieve a >= 269 ConstantNode one = ConstantNode.forIntegerStamp(stamp, 1, graph); 270 if (iv.direction() == Direction.Up) { 271 ValueNode v1 = sub(ConstantNode.forIntegerStamp(stamp, NumUtil.maxValue(stamp.getBits())), sub(iv.strideNode(), one)); 272 if (oneOff) { 273 v1 = sub(v1, one); 274 } 275 cond = graph.addOrUniqueWithInputs(IntegerLessThanNode.create(v1, end, NodeView.DEFAULT)); 276 } else { 277 assert iv.direction() == Direction.Down; 278 ValueNode v1 = add(ConstantNode.forIntegerStamp(stamp, NumUtil.minValue(stamp.getBits())), sub(one, iv.strideNode())); 279 if (oneOff) { 280 v1 = add(v1, one); 281 } 282 cond = graph.addOrUniqueWithInputs(IntegerLessThanNode.create(end, v1, NodeView.DEFAULT)); 283 } 284 assert graph.getGuardsStage().allowsFloatingGuards(); 285 overflowGuard = graph.unique(new GuardNode(cond, AbstractBeginNode.prevBegin(loop.entryPoint()), DeoptimizationReason.LoopLimitCheck, DeoptimizationAction.InvalidateRecompile, true, 286 SpeculationLog.NO_SPECULATION, null)); // TODO gd: use speculation 287 loop.loopBegin().setOverflowGuard(overflowGuard); 288 return overflowGuard; 289 } 290 } 291 292 public IntegerStamp getStamp() { 293 return (IntegerStamp) iv.valueNode().stamp(NodeView.DEFAULT); 294 } 295 }