Main.java revision 4559f000b323b64e4bd179b72cfb788b30b25b23
10304e182adee81be32c744fd3c0d28add29974ffMingyao Yang/* 20304e182adee81be32c744fd3c0d28add29974ffMingyao Yang* Copyright (C) 2015 The Android Open Source Project 30304e182adee81be32c744fd3c0d28add29974ffMingyao Yang* 40304e182adee81be32c744fd3c0d28add29974ffMingyao Yang* Licensed under the Apache License, Version 2.0 (the "License"); 50304e182adee81be32c744fd3c0d28add29974ffMingyao Yang* you may not use this file except in compliance with the License. 60304e182adee81be32c744fd3c0d28add29974ffMingyao Yang* You may obtain a copy of the License at 70304e182adee81be32c744fd3c0d28add29974ffMingyao Yang* 80304e182adee81be32c744fd3c0d28add29974ffMingyao Yang* http://www.apache.org/licenses/LICENSE-2.0 90304e182adee81be32c744fd3c0d28add29974ffMingyao Yang* 100304e182adee81be32c744fd3c0d28add29974ffMingyao Yang* Unless required by applicable law or agreed to in writing, software 110304e182adee81be32c744fd3c0d28add29974ffMingyao Yang* distributed under the License is distributed on an "AS IS" BASIS, 120304e182adee81be32c744fd3c0d28add29974ffMingyao Yang* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 130304e182adee81be32c744fd3c0d28add29974ffMingyao Yang* See the License for the specific language governing permissions and 140304e182adee81be32c744fd3c0d28add29974ffMingyao Yang* limitations under the License. 150304e182adee81be32c744fd3c0d28add29974ffMingyao Yang*/ 160304e182adee81be32c744fd3c0d28add29974ffMingyao Yang 170304e182adee81be32c744fd3c0d28add29974ffMingyao Yangpublic class Main { 180304e182adee81be32c744fd3c0d28add29974ffMingyao Yang 190304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // CHECK-START: int Main.sieve(int) BCE (before) 200304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // CHECK: BoundsCheck 210304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // CHECK: ArraySet 220304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // CHECK: BoundsCheck 230304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // CHECK: ArrayGet 240304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // CHECK: BoundsCheck 250304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // CHECK: ArraySet 260304e182adee81be32c744fd3c0d28add29974ffMingyao Yang 270304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // CHECK-START: int Main.sieve(int) BCE (after) 280304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // CHECK-NOT: BoundsCheck 290304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // CHECK: ArraySet 300304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // CHECK-NOT: BoundsCheck 310304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // CHECK: ArrayGet 320304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // CHECK: BoundsCheck 330304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // CHECK: ArraySet 340304e182adee81be32c744fd3c0d28add29974ffMingyao Yang 350304e182adee81be32c744fd3c0d28add29974ffMingyao Yang static int sieve(int size) { 360304e182adee81be32c744fd3c0d28add29974ffMingyao Yang int primeCount = 0; 370304e182adee81be32c744fd3c0d28add29974ffMingyao Yang boolean[] flags = new boolean[size + 1]; 380304e182adee81be32c744fd3c0d28add29974ffMingyao Yang for (int i = 1; i < size; i++) flags[i] = true; // Can eliminate. 390304e182adee81be32c744fd3c0d28add29974ffMingyao Yang for (int i = 2; i < size; i++) { 400304e182adee81be32c744fd3c0d28add29974ffMingyao Yang if (flags[i]) { // Can eliminate. 410304e182adee81be32c744fd3c0d28add29974ffMingyao Yang primeCount++; 420304e182adee81be32c744fd3c0d28add29974ffMingyao Yang for (int k = i + 1; k <= size; k += i) 430304e182adee81be32c744fd3c0d28add29974ffMingyao Yang flags[k - 1] = false; // Can't eliminate yet due to (k+i) may overflow. 440304e182adee81be32c744fd3c0d28add29974ffMingyao Yang } 450304e182adee81be32c744fd3c0d28add29974ffMingyao Yang } 460304e182adee81be32c744fd3c0d28add29974ffMingyao Yang return primeCount; 470304e182adee81be32c744fd3c0d28add29974ffMingyao Yang } 480304e182adee81be32c744fd3c0d28add29974ffMingyao Yang 498c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 500304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // CHECK-START: void Main.narrow(int[], int) BCE (before) 510304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // CHECK: BoundsCheck 520304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // CHECK: ArraySet 530304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // CHECK: BoundsCheck 540304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // CHECK: ArraySet 550304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // CHECK: BoundsCheck 560304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // CHECK: ArraySet 570304e182adee81be32c744fd3c0d28add29974ffMingyao Yang 580304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // CHECK-START: void Main.narrow(int[], int) BCE (after) 590304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // CHECK-NOT: BoundsCheck 600304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // CHECK: ArraySet 610304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // CHECK-NOT: BoundsCheck 620304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // CHECK: ArraySet 630304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // CHECK: BoundsCheck 640304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // CHECK: ArraySet 658c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-NOT: BoundsCheck 668c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 678c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 688c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 690304e182adee81be32c744fd3c0d28add29974ffMingyao Yang 708c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang static void narrow(int[] array, int offset) { 710304e182adee81be32c744fd3c0d28add29974ffMingyao Yang if (offset < 0) { 720304e182adee81be32c744fd3c0d28add29974ffMingyao Yang return; 730304e182adee81be32c744fd3c0d28add29974ffMingyao Yang } 740304e182adee81be32c744fd3c0d28add29974ffMingyao Yang if (offset < array.length) { 750304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // offset is in range [0, array.length-1]. 760304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // Bounds check can be eliminated. 770304e182adee81be32c744fd3c0d28add29974ffMingyao Yang array[offset] = 1; 780304e182adee81be32c744fd3c0d28add29974ffMingyao Yang 790304e182adee81be32c744fd3c0d28add29974ffMingyao Yang int biased_offset1 = offset + 1; 800304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // biased_offset1 is in range [1, array.length]. 810304e182adee81be32c744fd3c0d28add29974ffMingyao Yang if (biased_offset1 < array.length) { 820304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // biased_offset1 is in range [1, array.length-1]. 830304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // Bounds check can be eliminated. 840304e182adee81be32c744fd3c0d28add29974ffMingyao Yang array[biased_offset1] = 1; 850304e182adee81be32c744fd3c0d28add29974ffMingyao Yang } 860304e182adee81be32c744fd3c0d28add29974ffMingyao Yang 870304e182adee81be32c744fd3c0d28add29974ffMingyao Yang int biased_offset2 = offset + 0x70000000; 880304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // biased_offset2 is in range [0x70000000, array.length-1+0x70000000]. 890304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // It may overflow and be negative. 900304e182adee81be32c744fd3c0d28add29974ffMingyao Yang if (biased_offset2 < array.length) { 910304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // Even with this test, biased_offset2 can be negative so we can't 920304e182adee81be32c744fd3c0d28add29974ffMingyao Yang // eliminate this bounds check. 930304e182adee81be32c744fd3c0d28add29974ffMingyao Yang array[biased_offset2] = 1; 940304e182adee81be32c744fd3c0d28add29974ffMingyao Yang } 958c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 968c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // offset_sub1 won't underflow since offset is no less than 0. 978c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang int offset_sub1 = offset - Integer.MAX_VALUE; 988c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang if (offset_sub1 >= 0) { 998c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[offset_sub1] = 1; // Bounds check can be eliminated. 1008c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 1018c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 1028c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // offset_sub2 can underflow. 1038c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang int offset_sub2 = offset_sub1 - Integer.MAX_VALUE; 1048c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang if (offset_sub2 >= 0) { 1058c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[offset_sub2] = 1; // Bounds check can't be eliminated. 1068c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 1078c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 1088c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 1098c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 1108c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 1118c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-START: void Main.constantIndexing(int[]) BCE (before) 1128c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 1138c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 1148c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 1158c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 1168c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 1178c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 1188c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 1198c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-START: void Main.constantIndexing(int[]) BCE (after) 1208c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 1218c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 1228c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-NOT: BoundsCheck 1238c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 1248c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 1258c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 1268c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 1278c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang static void constantIndexing(int[] array) { 1288c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[5] = 1; 1298c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[4] = 1; 1308c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[6] = 1; 1318c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 1328c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 1338c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 1348c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-START: void Main.loopPattern1(int[]) BCE (before) 1358c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 1368c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 1378c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 1388c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 1398c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 1408c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 1418c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 1428c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 1438c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 1448c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 1458c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 1468c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 1478c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 1488c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 1498c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 1508c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-START: void Main.loopPattern1(int[]) BCE (after) 1518c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-NOT: BoundsCheck 1528c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 1538c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-NOT: BoundsCheck 1548c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 1558c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-NOT: BoundsCheck 1568c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 1578c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 1588c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 1598c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 1608c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 1618c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 1628c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 1638c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-NOT: BoundsCheck 1648c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 1658c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 1668c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang static void loopPattern1(int[] array) { 1678c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang for (int i = 0; i < array.length; i++) { 1688c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[i] = 1; // Bounds check can be eliminated. 1698c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 1708c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 1718c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang for (int i = 1; i < array.length; i++) { 1728c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[i] = 1; // Bounds check can be eliminated. 1738c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 1748c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 1758c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang for (int i = 1; i < array.length - 1; i++) { 1768c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[i] = 1; // Bounds check can be eliminated. 1778c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 1788c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 1798c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang for (int i = -1; i < array.length; i++) { 1808c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[i] = 1; // Bounds check can't be eliminated. 1818c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 1828c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 1838c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang for (int i = 0; i <= array.length; i++) { 1848c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[i] = 1; // Bounds check can't be eliminated. 1858c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 1868c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 1878c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang for (int i = 0; i < array.length; i += 2) { 1888c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // We don't have any assumption on max array length yet. 1898c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // Bounds check can't be eliminated due to overflow concern. 1908c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[i] = 1; 1918c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 1928c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 1938c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang for (int i = 1; i < array.length; i += 2) { 1948c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // Bounds check can be eliminated since i is odd so the last 1958c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // i that's less than array.length is at most (Integer.MAX_VALUE - 2). 1968c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[i] = 1; 1978c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 1988c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 1998c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 2008c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 2018c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-START: void Main.loopPattern2(int[]) BCE (before) 2028c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 2038c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 2048c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 2058c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 2068c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 2078c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 2088c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 2098c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 2108c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 2118c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 2128c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 2138c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 2148c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 2158c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-START: void Main.loopPattern2(int[]) BCE (after) 2168c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-NOT: BoundsCheck 2178c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 2188c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-NOT: BoundsCheck 2198c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 2208c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-NOT: BoundsCheck 2218c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 2228c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 2238c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 2248c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 2258c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 2268c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-NOT: BoundsCheck 2278c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 2288c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 2298c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang static void loopPattern2(int[] array) { 2308c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang for (int i = array.length - 1; i >= 0; i--) { 2318c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[i] = 1; // Bounds check can be eliminated. 2328c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 2338c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 2348c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang for (int i = array.length; i > 0; i--) { 2358c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[i - 1] = 1; // Bounds check can be eliminated. 2368c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 2378c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 2388c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang for (int i = array.length - 1; i > 0; i--) { 2398c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[i] = 1; // Bounds check can be eliminated. 2408c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 2418c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 2428c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang for (int i = array.length; i >= 0; i--) { 2438c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[i] = 1; // Bounds check can't be eliminated. 2448c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 2458c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 2468c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang for (int i = array.length; i >= 0; i--) { 2478c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[i - 1] = 1; // Bounds check can't be eliminated. 2488c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 2498c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 2508c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang for (int i = array.length; i > 0; i -= 20) { 2518c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // For i >= 0, (i - 20 - 1) is guaranteed not to underflow. 2528c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[i - 1] = 1; // Bounds check can be eliminated. 2538c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 2548c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 2558c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 2568c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 2578c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-START: void Main.loopPattern3(int[]) BCE (before) 2588c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 2598c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 2608c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 2618c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-START: void Main.loopPattern3(int[]) BCE (after) 2628c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 2638c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 2648c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 2658c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang static void loopPattern3(int[] array) { 2668c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang java.util.Random random = new java.util.Random(); 2678c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang for (int i = 0; ; i++) { 2688c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang if (random.nextInt() % 1000 == 0 && i < array.length) { 2698c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // Can't eliminate the bound check since not every i++ is 2708c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // matched with a array length check, so there is some chance that i 2718c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // overflows and is negative. 2728c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[i] = 1; 2738c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 2740304e182adee81be32c744fd3c0d28add29974ffMingyao Yang } 2750304e182adee81be32c744fd3c0d28add29974ffMingyao Yang } 2760304e182adee81be32c744fd3c0d28add29974ffMingyao Yang 2778c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 2788c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-START: void Main.constantNewArray() BCE (before) 2798c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 2808c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 2818c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 2828c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 2838c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 2848c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 2858c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 2868c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 2878c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 2888c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 2898c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 2908c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-START: void Main.constantNewArray() BCE (after) 2918c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-NOT: BoundsCheck 2928c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 2938c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 2948c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 2958c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-NOT: BoundsCheck 2968c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 2978c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-NOT: BoundsCheck 2988c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 2998c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 3008c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 3018c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 3028c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang static void constantNewArray() { 3038c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang int[] array = new int[10]; 3048c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang for (int i = 0; i < 10; i++) { 3058c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[i] = 1; // Bounds check can be eliminated. 3068c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 3078c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 3088c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang for (int i = 0; i <= 10; i++) { 3098c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[i] = 1; // Bounds check can't be eliminated. 3108c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 3118c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 3128c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[0] = 1; // Bounds check can be eliminated. 3138c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[9] = 1; // Bounds check can be eliminated. 3148c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[10] = 1; // Bounds check can't be eliminated. 3158c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 3168c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 3174559f000b323b64e4bd179b72cfb788b30b25b23Mingyao Yang 3184559f000b323b64e4bd179b72cfb788b30b25b23Mingyao Yang static byte readData() { 3194559f000b323b64e4bd179b72cfb788b30b25b23Mingyao Yang return 1; 3204559f000b323b64e4bd179b72cfb788b30b25b23Mingyao Yang } 3214559f000b323b64e4bd179b72cfb788b30b25b23Mingyao Yang 3224559f000b323b64e4bd179b72cfb788b30b25b23Mingyao Yang // CHECK-START: void Main.circularBufferProducer() BCE (before) 3234559f000b323b64e4bd179b72cfb788b30b25b23Mingyao Yang // CHECK: BoundsCheck 3244559f000b323b64e4bd179b72cfb788b30b25b23Mingyao Yang // CHECK: ArraySet 3254559f000b323b64e4bd179b72cfb788b30b25b23Mingyao Yang 3264559f000b323b64e4bd179b72cfb788b30b25b23Mingyao Yang // CHECK-START: void Main.circularBufferProducer() BCE (after) 3274559f000b323b64e4bd179b72cfb788b30b25b23Mingyao Yang // CHECK-NOT: BoundsCheck 3284559f000b323b64e4bd179b72cfb788b30b25b23Mingyao Yang // CHECK: ArraySet 3294559f000b323b64e4bd179b72cfb788b30b25b23Mingyao Yang 3304559f000b323b64e4bd179b72cfb788b30b25b23Mingyao Yang static void circularBufferProducer() { 3314559f000b323b64e4bd179b72cfb788b30b25b23Mingyao Yang byte[] array = new byte[4096]; 3324559f000b323b64e4bd179b72cfb788b30b25b23Mingyao Yang int i = 0; 3334559f000b323b64e4bd179b72cfb788b30b25b23Mingyao Yang while (true) { 3344559f000b323b64e4bd179b72cfb788b30b25b23Mingyao Yang array[i & (array.length - 1)] = readData(); 3354559f000b323b64e4bd179b72cfb788b30b25b23Mingyao Yang i++; 3364559f000b323b64e4bd179b72cfb788b30b25b23Mingyao Yang } 3374559f000b323b64e4bd179b72cfb788b30b25b23Mingyao Yang } 3384559f000b323b64e4bd179b72cfb788b30b25b23Mingyao Yang 3394559f000b323b64e4bd179b72cfb788b30b25b23Mingyao Yang 3408c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-START: void Main.pyramid1(int[]) BCE (before) 3418c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 3428c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 3438c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 3448c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 3458c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 3468c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-START: void Main.pyramid1(int[]) BCE (after) 3478c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-NOT: BoundsCheck 3488c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 3498c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-NOT: BoundsCheck 3508c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 3518c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 3528c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // Set array to something like {0, 1, 2, 3, 2, 1, 0}. 3538c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang static void pyramid1(int[] array) { 3548c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang for (int i = 0; i < (array.length + 1) / 2; i++) { 3558c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[i] = i; 3568c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[array.length - 1 - i] = i; 3578c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 3588c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 3598c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 3608c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 3618c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-START: void Main.pyramid2(int[]) BCE (before) 3628c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 3638c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 3648c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 3658c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 3668c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 3678c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-START: void Main.pyramid2(int[]) BCE (after) 3688c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-NOT: BoundsCheck 3698c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 3708c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-NOT: BoundsCheck 3718c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 3728c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 3738c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // Set array to something like {0, 1, 2, 3, 2, 1, 0}. 3748c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang static void pyramid2(int[] array) { 3758c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang for (int i = 0; i < (array.length + 1) >> 1; i++) { 3768c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[i] = i; 3778c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[array.length - 1 - i] = i; 3788c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 3798c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 3808c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 3818c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 3828c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-START: void Main.pyramid3(int[]) BCE (before) 3838c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 3848c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 3858c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 3868c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 3878c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 3888c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-START: void Main.pyramid3(int[]) BCE (after) 3898c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-NOT: BoundsCheck 3908c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 3918c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-NOT: BoundsCheck 3928c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 3938c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 3948c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // Set array to something like {0, 1, 2, 3, 2, 1, 0}. 3958c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang static void pyramid3(int[] array) { 3968c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang for (int i = 0; i < (array.length + 1) >>> 1; i++) { 3978c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[i] = i; 3988c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[array.length - 1 - i] = i; 3998c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 4008c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 4018c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 4028c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 4038c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // TODO: bce on the array accesses in this method. 4048c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang static boolean isPyramid(int[] array) { 4058c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang int i = 0; 4068c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang int j = array.length - 1; 4078c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang while (i <= j) { 4088c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang if (array[i] != i) { 4098c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang return false; 4108c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 4118c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang if (array[j] != i) { 4128c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang return false; 4138c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 4148c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang i++; j--; 4158c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 4168c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang return true; 4178c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 4188c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 4198c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 4208c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-START: void Main.bubbleSort(int[]) GVN (before) 4218c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 4228c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArrayGet 4238c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 4248c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArrayGet 4258c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 4268c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArrayGet 4278c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 4288c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArrayGet 4298c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 4308c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 4318c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 4328c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 4338c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 4348c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-START: void Main.bubbleSort(int[]) GVN (after) 4358c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 4368c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArrayGet 4378c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: BoundsCheck 4388c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArrayGet 4398c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-NOT: ArrayGet 4408c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-NOT: ArrayGet 4418c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-NOT: BoundsCheck 4428c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 4438c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-NOT: BoundsCheck 4448c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 4458c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 4468c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-START: void Main.bubbleSort(int[]) BCE (after) 4478c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-NOT: BoundsCheck 4488c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArrayGet 4498c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-NOT: BoundsCheck 4508c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArrayGet 4518c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-NOT: ArrayGet 4528c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-NOT: ArrayGet 4538c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-NOT: BoundsCheck 4548c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 4558c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK-NOT: BoundsCheck 4568c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang // CHECK: ArraySet 4578c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 4588c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang static void bubbleSort(int[] array) { 4598c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang for (int i = 0; i < array.length - 1; i++) { 4608c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang for (int j = 0; j < array.length - i - 1; j++) { 4618c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang if (array[j] > array[j + 1]) { 4628c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang int temp = array[j + 1]; 4638c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[j + 1] = array[j]; 4648c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array[j] = temp; 4658c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 4668c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 4678c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 4688c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 4698c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 4708c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 4710304e182adee81be32c744fd3c0d28add29974ffMingyao Yang public static void main(String[] args) { 4720304e182adee81be32c744fd3c0d28add29974ffMingyao Yang sieve(20); 4738c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 4748c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang int[] array = {5, 2, 3, 7, 0, 1, 6, 4}; 4758c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang bubbleSort(array); 4768c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang for (int i = 0; i < 8; i++) { 4778c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang if (array[i] != i) { 4788c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang System.out.println("bubble sort failed!"); 4798c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 4808c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 4818c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 4828c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array = new int[7]; 4838c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang pyramid1(array); 4848c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang if (!isPyramid(array)) { 4858c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang System.out.println("pyramid1 failed!"); 4868c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 4878c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 4888c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang array = new int[8]; 4898c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang pyramid2(array); 4908c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang if (!isPyramid(array)) { 4918c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang System.out.println("pyramid2 failed!"); 4928c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 4938c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang 4948c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang java.util.Arrays.fill(array, -1); 4958c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang pyramid3(array); 4968c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang if (!isPyramid(array)) { 4978c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang System.out.println("pyramid3 failed!"); 4988c8bad89ff367712a6f5bbf3a5836cd398391067Mingyao Yang } 4990304e182adee81be32c744fd3c0d28add29974ffMingyao Yang } 5000304e182adee81be32c744fd3c0d28add29974ffMingyao Yang} 501