1 /*
   2  * Copyright (c) 2016, 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.core.test;
  26 
  27 import org.graalvm.compiler.api.directives.GraalDirectives;
  28 import org.graalvm.compiler.graph.Node;
  29 import org.graalvm.compiler.graph.iterators.NodeIterable;
  30 import org.graalvm.compiler.graph.spi.Canonicalizable;
  31 import org.graalvm.compiler.graph.spi.SimplifierTool;
  32 import org.graalvm.compiler.java.ComputeLoopFrequenciesClosure;
  33 import org.graalvm.compiler.nodes.LoopBeginNode;
  34 import org.graalvm.compiler.nodes.StructuredGraph;
  35 import org.graalvm.compiler.nodes.ValueNode;
  36 import org.graalvm.compiler.nodes.spi.CoreProviders;
  37 import org.graalvm.compiler.phases.BasePhase;
  38 import org.graalvm.compiler.phases.common.CanonicalizerPhase;
  39 import org.graalvm.compiler.phases.common.CanonicalizerPhase.CustomCanonicalizer;
  40 import org.graalvm.compiler.phases.contract.NodeCostUtil;
  41 import org.graalvm.compiler.phases.tiers.HighTierContext;
  42 import org.junit.Assert;
  43 import org.junit.Test;
  44 
  45 public class NodePropertiesTest extends GraalCompilerTest {
  46 
  47     public static Object sideEffect;
  48 
  49     public static Object[] array = new Object[]{new Object(), new Object(), new Object()};
  50 
  51     public static int test1Snippet(int a) {
  52         int x = 0;
  53         if (a > 0) {
  54             x = 1;
  55             sideEffect = null;
  56         } else {
  57             x = 2;
  58             sideEffect = null;
  59         }
  60         int b = 4;
  61         sideEffect = null;
  62         int c = b % 5;
  63         // can shift
  64         return a * x * c;
  65     }
  66 
  67     public static int test2Snippet(int a) {
  68         int x = 0;
  69         if (a > 0) {
  70             x = 1;
  71             sideEffect = null;
  72         } else {
  73             x = 2;
  74             sideEffect = null;
  75         }
  76         sideEffect = null;
  77         // cannot shift
  78         return a * x * 41;
  79     }
  80 
  81     public static final int ITERATIONS_LOOP_1 = 128;
  82     public static final int ITERATIONS_LOOP_2 = 256;
  83 
  84     public static int testLoop01(int a) {
  85         int res = 0;
  86         for (int i = 0; GraalDirectives.injectIterationCount(ITERATIONS_LOOP_1, i < a); i++) {
  87             res += i;
  88         }
  89         return res;
  90     }
  91 
  92     public static int testLoop02(int a) {
  93         int res = 0;
  94         for (int i = 0; GraalDirectives.injectIterationCount(ITERATIONS_LOOP_2, i < a); i++) {
  95             res += i;
  96         }
  97         return res;
  98     }
  99 
 100     public static int testLoop03(int a) {
 101         int res = 0;
 102         for (int i = 0; GraalDirectives.injectIterationCount(ITERATIONS_LOOP_1, i < a); i++) {
 103             res *= i;
 104         }
 105         return res;
 106     }
 107 
 108     public static int testLoop04(int a) {
 109         int res = 0;
 110         for (int i = 0; GraalDirectives.injectIterationCount(ITERATIONS_LOOP_1 * ITERATIONS_LOOP_2, i < a); i++) {
 111             res += i;
 112         }
 113         return res;
 114     }
 115 
 116     public static int testLoop05(int a) {
 117         int res = 0;
 118         for (int i = 0; GraalDirectives.injectIterationCount(ITERATIONS_LOOP_1, i < a); i++) {
 119             res += i;
 120             for (int j = 0; GraalDirectives.injectIterationCount(ITERATIONS_LOOP_2, j < ITERATIONS_LOOP_2); j++) {
 121                 res += i;
 122             }
 123         }
 124         return res;
 125     }
 126 
 127     public static int dontInline(int a) {
 128         int res = 1;
 129         for (int i = 0; i < a; i++) {
 130             for (int j = 0; j < i; j++) {
 131                 for (int k = 0; k < j; k++) {
 132                     res += i + j + k;
 133                 }
 134             }
 135         }
 136         sideEffect = res;
 137         return (Integer) sideEffect;
 138     }
 139 
 140     public static int untrused01(int a) {
 141         return dontInline(a);
 142     }
 143 
 144     public static int arrayLoadTest(int a) {
 145         return array[a].hashCode();
 146     }
 147 
 148     public static int arrayStoreTest(int a) {
 149         array[2] = a;
 150         return a;
 151     }
 152 
 153     public static int fieldLoad(int a) {
 154         return sideEffect.hashCode() * a;
 155     }
 156 
 157     public static int fieldStore(int a) {
 158         sideEffect = a;
 159         return a;
 160     }
 161 
 162     @Test
 163     public void testCanonicalizationExample() {
 164         HighTierContext htc = getDefaultHighTierContext();
 165         ImprovementSavingCanonicalizer c1 = new ImprovementSavingCanonicalizer();
 166         StructuredGraph g1 = parseForCompile(getResolvedJavaMethod("test1Snippet"));
 167         new CanonicalizerPhase(c1).apply(g1, htc);
 168         ImprovementSavingCanonicalizer c2 = new ImprovementSavingCanonicalizer();
 169         StructuredGraph g2 = parseForCompile(getResolvedJavaMethod("test2Snippet"));
 170         new CanonicalizerPhase(c2).apply(g2, htc);
 171         Assert.assertEquals(0, c1.savedCycles);
 172         Assert.assertEquals(0, c2.savedCycles);
 173     }
 174 
 175     private static void prepareGraphForLoopFrequencies(StructuredGraph g, HighTierContext htc) {
 176         // let canonicalizer work away branch probability nodes
 177         new CanonicalizerPhase().apply(g, htc);
 178         // recompute the loop frequencies
 179         ComputeLoopFrequenciesClosure.compute(g);
 180     }
 181 
 182     private static void assertFrequency(StructuredGraph g, int iterations) {
 183         NodeIterable<LoopBeginNode> loopBeginNodes = g.getNodes(LoopBeginNode.TYPE);
 184         LoopBeginNode loopBeginNode = loopBeginNodes.first();
 185         Assert.assertEquals("loop frequency of " + loopBeginNode, iterations, loopBeginNode.loopFrequency(), 0);
 186     }
 187 
 188     @Test
 189     public void testDifferentLoopFaster() {
 190         HighTierContext htc = getDefaultHighTierContext();
 191         StructuredGraph g1 = parseForCompile(getResolvedJavaMethod("testLoop01"));
 192         StructuredGraph g2 = parseForCompile(getResolvedJavaMethod("testLoop03"));
 193         prepareGraphForLoopFrequencies(g1, htc);
 194         prepareGraphForLoopFrequencies(g2, htc);
 195         assertFrequency(g1, ITERATIONS_LOOP_1);
 196         assertFrequency(g2, ITERATIONS_LOOP_1);
 197         GraphCostPhase gc1 = new GraphCostPhase();
 198         GraphCostPhase gc2 = new GraphCostPhase();
 199         gc1.apply(g1, htc);
 200         gc2.apply(g2, htc);
 201         g1.getDebug().log("Test testDifferentLoopFaster --> 1.Graph cycles:%f size:%f vs. 2.Graph cycles:%f size:%f\n", gc1.finalCycles, gc1.finalSize, gc2.finalCycles, gc2.finalSize);
 202         Assert.assertTrue(gc2.finalCycles > gc1.finalCycles);
 203         Assert.assertTrue(gc2.finalSize == gc1.finalSize);
 204     }
 205 
 206     @Test
 207     public void testSameLoopMoreIterationsCostlier() {
 208         HighTierContext htc = getDefaultHighTierContext();
 209         StructuredGraph g1 = parseForCompile(getResolvedJavaMethod("testLoop01"));
 210         StructuredGraph g2 = parseForCompile(getResolvedJavaMethod("testLoop02"));
 211         prepareGraphForLoopFrequencies(g1, htc);
 212         prepareGraphForLoopFrequencies(g2, htc);
 213         assertFrequency(g1, ITERATIONS_LOOP_1);
 214         assertFrequency(g2, ITERATIONS_LOOP_2);
 215         GraphCostPhase gc1 = new GraphCostPhase();
 216         GraphCostPhase gc2 = new GraphCostPhase();
 217         gc1.apply(g1, htc);
 218         gc2.apply(g2, htc);
 219         g1.getDebug().log("Test testSameLoopMoreIterationsCostlier --> 1.Graph cycles:%f size:%f vs. 2.Graph cycles:%f size:%f\n", gc1.finalCycles, gc1.finalSize, gc2.finalCycles, gc2.finalSize);
 220         Assert.assertTrue(gc2.finalCycles > gc1.finalCycles);
 221         Assert.assertTrue(gc2.finalSize == gc1.finalSize);
 222     }
 223 
 224     @Test
 225     public void testDifferentLoopsInnerOuter() {
 226         HighTierContext htc = getDefaultHighTierContext();
 227         StructuredGraph g1 = parseForCompile(getResolvedJavaMethod("testLoop04"));
 228         StructuredGraph g2 = parseForCompile(getResolvedJavaMethod("testLoop05"));
 229         prepareGraphForLoopFrequencies(g1, htc);
 230         prepareGraphForLoopFrequencies(g2, htc);
 231         assertFrequency(g1, ITERATIONS_LOOP_1 * ITERATIONS_LOOP_2);
 232         GraphCostPhase gc1 = new GraphCostPhase();
 233         GraphCostPhase gc2 = new GraphCostPhase();
 234         gc1.apply(g1, htc);
 235         gc2.apply(g2, htc);
 236         g1.getDebug().log("Test testDifferentLoopsInnerOuter --> 1.Graph cycles:%f size:%f vs. 2.Graph cycles:%f size:%f\n", gc1.finalCycles, gc1.finalSize, gc2.finalCycles, gc2.finalSize);
 237         Assert.assertTrue(gc2.finalSize > gc1.finalSize);
 238     }
 239 
 240     @Test
 241     public void testGraphCost() {
 242         StructuredGraph g1 = parseForCompile(getResolvedJavaMethod("test1Snippet"));
 243         StructuredGraph g2 = parseForCompile(getResolvedJavaMethod("test2Snippet"));
 244         HighTierContext htc = getDefaultHighTierContext();
 245         new CanonicalizerPhase().apply(g1, htc);
 246         new CanonicalizerPhase().apply(g2, htc);
 247         GraphCostPhase gc1 = new GraphCostPhase();
 248         GraphCostPhase gc2 = new GraphCostPhase();
 249         gc1.apply(g1, htc);
 250         gc2.apply(g2, htc);
 251         g1.getDebug().log("Test Graph Cost --> 1.Graph cost:%f vs. 2.Graph cost:%f\n", gc1.finalCycles, gc2.finalCycles);
 252         Assert.assertTrue(gc2.finalCycles > gc1.finalCycles);
 253         Assert.assertTrue(gc2.finalSize == gc1.finalSize);
 254     }
 255 
 256     @Test
 257     public void testExpectUntrusted() {
 258         StructuredGraph g1 = parseForCompile(getResolvedJavaMethod("untrused01"));
 259         HighTierContext htc = getDefaultHighTierContext();
 260         new CanonicalizerPhase().apply(g1, htc);
 261         GraphCostPhase gc1 = new GraphCostPhase();
 262         gc1.apply(g1, htc);
 263     }
 264 
 265     @Test
 266     public void testArrayLoad() {
 267         StructuredGraph g1 = parseForCompile(getResolvedJavaMethod("arrayLoadTest"));
 268         HighTierContext htc = getDefaultHighTierContext();
 269         new CanonicalizerPhase().apply(g1, htc);
 270         GraphCostPhase gc1 = new GraphCostPhase();
 271         gc1.apply(g1, htc);
 272         Assert.assertEquals(15, gc1.finalCycles, 25);
 273     }
 274 
 275     @Test
 276     public void testArrayStore() {
 277         StructuredGraph g1 = parseForCompile(getResolvedJavaMethod("arrayStoreTest"));
 278         HighTierContext htc = getDefaultHighTierContext();
 279         new CanonicalizerPhase().apply(g1, htc);
 280         GraphCostPhase gc1 = new GraphCostPhase();
 281         gc1.apply(g1, htc);
 282         Assert.assertEquals(15, gc1.finalCycles, 25);
 283     }
 284 
 285     @Test
 286     public void testFieldLoad() {
 287         StructuredGraph g1 = parseForCompile(getResolvedJavaMethod("fieldLoad"));
 288         HighTierContext htc = getDefaultHighTierContext();
 289         new CanonicalizerPhase().apply(g1, htc);
 290         GraphCostPhase gc1 = new GraphCostPhase();
 291         gc1.apply(g1, htc);
 292         Assert.assertEquals(15, gc1.finalCycles, 25);
 293     }
 294 
 295     @Test
 296     public void testFieldStore() {
 297         StructuredGraph g1 = parseForCompile(getResolvedJavaMethod("fieldStore"));
 298         HighTierContext htc = getDefaultHighTierContext();
 299         new CanonicalizerPhase().apply(g1, htc);
 300         GraphCostPhase gc1 = new GraphCostPhase();
 301         gc1.apply(g1, htc);
 302         Assert.assertEquals(15, gc1.finalCycles, 25);
 303     }
 304 
 305     static class ImprovementSavingCanonicalizer extends CustomCanonicalizer {
 306         private int savedCycles;
 307 
 308         @Override
 309         public void simplify(Node node, SimplifierTool tool) {
 310             if (node instanceof Canonicalizable.Binary<?>) {
 311                 @SuppressWarnings("unchecked")
 312                 Canonicalizable.Binary<ValueNode> bc = (Canonicalizable.Binary<ValueNode>) node;
 313                 Node canonicalized = bc.canonical(tool, bc.getX(), bc.getY());
 314                 if (canonicalized != node) {
 315                     savedCycles += node.estimatedNodeCycles().value - canonicalized.estimatedNodeCycles().value;
 316                 }
 317             }
 318         }
 319     }
 320 
 321     private static class GraphCostPhase extends BasePhase<CoreProviders> {
 322         private double finalCycles;
 323         private double finalSize;
 324 
 325         @Override
 326         protected void run(StructuredGraph graph, CoreProviders context) {
 327             finalCycles = NodeCostUtil.computeGraphCycles(graph, true);
 328             finalSize = NodeCostUtil.computeGraphSize(graph);
 329         }
 330 
 331     }
 332 
 333 }