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