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