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