1 /* 2 * Copyright (C) 2017 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 /** 18 * Tests for SAD (sum of absolute differences). 19 */ 20 public class Main { 21 22 /// CHECK-START: int Main.sadInt2Int(int[], int[]) loop_optimization (before) 23 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 24 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 25 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 26 /// CHECK-DAG: <<Phi2:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 27 /// CHECK-DAG: <<Get1:i\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 28 /// CHECK-DAG: <<Get2:i\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 29 /// CHECK-DAG: <<Sub:i\d+>> Sub [<<Get1>>,<<Get2>>] loop:<<Loop>> outer_loop:none 30 /// CHECK-DAG: <<Intrin:i\d+>> InvokeStaticOrDirect [<<Sub>>] intrinsic:MathAbsInt loop:<<Loop>> outer_loop:none 31 /// CHECK-DAG: Add [<<Phi2>>,<<Intrin>>] loop:<<Loop>> outer_loop:none 32 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 33 // 34 /// CHECK-START-{ARM,ARM64,MIPS64}: int Main.sadInt2Int(int[], int[]) loop_optimization (after) 35 /// CHECK-DAG: <<Cons:i\d+>> IntConstant {{2|4}} loop:none 36 /// CHECK-DAG: <<Set:d\d+>> VecSetScalars [{{i\d+}}] loop:none 37 /// CHECK-DAG: <<Phi:d\d+>> Phi [<<Set>>,{{d\d+}}] loop:<<Loop:B\d+>> outer_loop:none 38 /// CHECK-DAG: <<Ld1:d\d+>> VecLoad [{{l\d+}},<<I:i\d+>>] loop:<<Loop>> outer_loop:none 39 /// CHECK-DAG: <<Ld2:d\d+>> VecLoad [{{l\d+}},<<I>>] loop:<<Loop>> outer_loop:none 40 /// CHECK-DAG: <<SAD:d\d+>> VecSADAccumulate [<<Phi>>,<<Ld1>>,<<Ld2>>] loop:<<Loop>> outer_loop:none 41 /// CHECK-DAG: Add [<<I>>,<<Cons>>] loop:<<Loop>> outer_loop:none 42 private static int sadInt2Int(int[] x, int[] y) { 43 int min_length = Math.min(x.length, y.length); 44 int sad = 0; 45 for (int i = 0; i < min_length; i++) { 46 sad += Math.abs(x[i] - y[i]); 47 } 48 return sad; 49 } 50 51 /// CHECK-START: int Main.sadInt2IntAlt(int[], int[]) loop_optimization (before) 52 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 53 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 54 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 55 /// CHECK-DAG: <<Phi2:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 56 /// CHECK-DAG: <<Get1:i\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 57 /// CHECK-DAG: <<Get2:i\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 58 /// CHECK-DAG: <<Sub1:i\d+>> Sub [<<Get2>>,<<Get1>>] loop:<<Loop>> outer_loop:none 59 /// CHECK-DAG: <<Sub2:i\d+>> Sub [<<Get1>>,<<Get2>>] loop:<<Loop>> outer_loop:none 60 /// CHECK-DAG: <<Select:i\d+>> Select [<<Sub2>>,<<Sub1>>,{{z\d+}}] loop:<<Loop>> outer_loop:none 61 /// CHECK-DAG: Add [<<Phi2>>,<<Select>>] loop:<<Loop>> outer_loop:none 62 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 63 // 64 // No ABS? No SAD! 65 // 66 /// CHECK-START: int Main.sadInt2IntAlt(int[], int[]) loop_optimization (after) 67 /// CHECK-NOT: VecSADAccumulate 68 private static int sadInt2IntAlt(int[] x, int[] y) { 69 int min_length = Math.min(x.length, y.length); 70 int sad = 0; 71 for (int i = 0; i < min_length; i++) { 72 int s = x[i]; 73 int p = y[i]; 74 sad += s >= p ? s - p : p - s; 75 } 76 return sad; 77 } 78 79 /// CHECK-START: int Main.sadInt2IntAlt2(int[], int[]) loop_optimization (before) 80 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 81 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 82 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 83 /// CHECK-DAG: <<Phi2:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 84 /// CHECK-DAG: <<Get1:i\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 85 /// CHECK-DAG: <<Get2:i\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 86 /// CHECK-DAG: <<Sub:i\d+>> Sub [<<Get1>>,<<Get2>>] loop:<<Loop>> outer_loop:none 87 /// CHECK-DAG: <<Intrin:i\d+>> InvokeStaticOrDirect [<<Sub>>] intrinsic:MathAbsInt loop:<<Loop>> outer_loop:none 88 /// CHECK-DAG: Add [<<Phi2>>,<<Intrin>>] loop:<<Loop>> outer_loop:none 89 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 90 // 91 /// CHECK-START-{ARM,ARM64,MIPS64}: int Main.sadInt2IntAlt2(int[], int[]) loop_optimization (after) 92 /// CHECK-DAG: <<Cons:i\d+>> IntConstant {{2|4}} loop:none 93 /// CHECK-DAG: <<Set:d\d+>> VecSetScalars [{{i\d+}}] loop:none 94 /// CHECK-DAG: <<Phi:d\d+>> Phi [<<Set>>,{{d\d+}}] loop:<<Loop:B\d+>> outer_loop:none 95 /// CHECK-DAG: <<Ld1:d\d+>> VecLoad [{{l\d+}},<<I:i\d+>>] loop:<<Loop>> outer_loop:none 96 /// CHECK-DAG: <<Ld2:d\d+>> VecLoad [{{l\d+}},<<I>>] loop:<<Loop>> outer_loop:none 97 /// CHECK-DAG: <<SAD:d\d+>> VecSADAccumulate [<<Phi>>,<<Ld1>>,<<Ld2>>] loop:<<Loop>> outer_loop:none 98 /// CHECK-DAG: Add [<<I>>,<<Cons>>] loop:<<Loop>> outer_loop:none 99 private static int sadInt2IntAlt2(int[] x, int[] y) { 100 int min_length = Math.min(x.length, y.length); 101 int sad = 0; 102 for (int i = 0; i < min_length; i++) { 103 int s = x[i]; 104 int p = y[i]; 105 int m = s - p; 106 if (m < 0) m = -m; 107 sad += m; 108 } 109 return sad; 110 } 111 112 /// CHECK-START: long Main.sadInt2Long(int[], int[]) loop_optimization (before) 113 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 114 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 115 /// CHECK-DAG: <<ConsL:j\d+>> LongConstant 0 loop:none 116 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 117 /// CHECK-DAG: <<Phi2:j\d+>> Phi [<<ConsL>>,{{j\d+}}] loop:<<Loop>> outer_loop:none 118 /// CHECK-DAG: <<Get1:i\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 119 /// CHECK-DAG: <<Get2:i\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 120 /// CHECK-DAG: <<Cnv1:j\d+>> TypeConversion [<<Get1>>] loop:<<Loop>> outer_loop:none 121 /// CHECK-DAG: <<Cnv2:j\d+>> TypeConversion [<<Get2>>] loop:<<Loop>> outer_loop:none 122 /// CHECK-DAG: <<Sub:j\d+>> Sub [<<Cnv1>>,<<Cnv2>>] loop:<<Loop>> outer_loop:none 123 /// CHECK-DAG: <<Intrin:j\d+>> InvokeStaticOrDirect [<<Sub>>] intrinsic:MathAbsLong loop:<<Loop>> outer_loop:none 124 /// CHECK-DAG: Add [<<Phi2>>,<<Intrin>>] loop:<<Loop>> outer_loop:none 125 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 126 // 127 /// CHECK-START-{ARM64,MIPS64}: long Main.sadInt2Long(int[], int[]) loop_optimization (after) 128 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 129 /// CHECK-DAG: <<Cons4:i\d+>> IntConstant 4 loop:none 130 /// CHECK-DAG: <<ConsL:j\d+>> LongConstant 0 loop:none 131 /// CHECK-DAG: <<Set:d\d+>> VecSetScalars [<<ConsL>>] loop:none 132 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 133 /// CHECK-DAG: <<Phi2:d\d+>> Phi [<<Set>>,{{d\d+}}] loop:<<Loop>> outer_loop:none 134 /// CHECK-DAG: <<Load1:d\d+>> VecLoad [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 135 /// CHECK-DAG: <<Load2:d\d+>> VecLoad [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 136 /// CHECK-DAG: <<SAD:d\d+>> VecSADAccumulate [<<Phi2>>,<<Load1>>,<<Load2>>] loop:<<Loop>> outer_loop:none 137 /// CHECK-DAG: Add [<<Phi1>>,<<Cons4>>] loop:<<Loop>> outer_loop:none 138 private static long sadInt2Long(int[] x, int[] y) { 139 int min_length = Math.min(x.length, y.length); 140 long sad = 0; 141 for (int i = 0; i < min_length; i++) { 142 long s = x[i]; 143 long p = y[i]; 144 sad += Math.abs(s - p); 145 } 146 return sad; 147 } 148 149 /// CHECK-START: long Main.sadInt2LongAt1(int[], int[]) loop_optimization (before) 150 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 151 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 152 /// CHECK-DAG: <<ConsL:j\d+>> LongConstant 1 loop:none 153 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 154 /// CHECK-DAG: <<Phi2:j\d+>> Phi [<<ConsL>>,{{j\d+}}] loop:<<Loop>> outer_loop:none 155 /// CHECK-DAG: <<Get1:i\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 156 /// CHECK-DAG: <<Get2:i\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 157 /// CHECK-DAG: <<Cnv1:j\d+>> TypeConversion [<<Get1>>] loop:<<Loop>> outer_loop:none 158 /// CHECK-DAG: <<Cnv2:j\d+>> TypeConversion [<<Get2>>] loop:<<Loop>> outer_loop:none 159 /// CHECK-DAG: <<Sub:j\d+>> Sub [<<Cnv1>>,<<Cnv2>>] loop:<<Loop>> outer_loop:none 160 /// CHECK-DAG: <<Intrin:j\d+>> InvokeStaticOrDirect [<<Sub>>] intrinsic:MathAbsLong loop:<<Loop>> outer_loop:none 161 /// CHECK-DAG: Add [<<Phi2>>,<<Intrin>>] loop:<<Loop>> outer_loop:none 162 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 163 // 164 /// CHECK-START-{ARM64,MIPS64}: long Main.sadInt2LongAt1(int[], int[]) loop_optimization (after) 165 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 166 /// CHECK-DAG: <<Cons4:i\d+>> IntConstant 4 loop:none 167 /// CHECK-DAG: <<ConsL:j\d+>> LongConstant 1 loop:none 168 /// CHECK-DAG: <<Set:d\d+>> VecSetScalars [<<ConsL>>] loop:none 169 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 170 /// CHECK-DAG: <<Phi2:d\d+>> Phi [<<Set>>,{{d\d+}}] loop:<<Loop>> outer_loop:none 171 /// CHECK-DAG: <<Load1:d\d+>> VecLoad [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 172 /// CHECK-DAG: <<Load2:d\d+>> VecLoad [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 173 /// CHECK-DAG: <<SAD:d\d+>> VecSADAccumulate [<<Phi2>>,<<Load1>>,<<Load2>>] loop:<<Loop>> outer_loop:none 174 /// CHECK-DAG: Add [<<Phi1>>,<<Cons4>>] loop:<<Loop>> outer_loop:none 175 private static long sadInt2LongAt1(int[] x, int[] y) { 176 int min_length = Math.min(x.length, y.length); 177 long sad = 1; // starts at 1 178 for (int i = 0; i < min_length; i++) { 179 long s = x[i]; 180 long p = y[i]; 181 sad += Math.abs(s - p); 182 } 183 return sad; 184 } 185 186 public static void main(String[] args) { 187 // Cross-test the two most extreme values individually. 188 int[] x = { 0, Integer.MAX_VALUE, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; 189 int[] y = { 0, Integer.MIN_VALUE, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; 190 expectEquals(1, sadInt2Int(x, y)); 191 expectEquals(1, sadInt2Int(y, x)); 192 expectEquals(-1, sadInt2IntAlt(x, y)); 193 expectEquals(-1, sadInt2IntAlt(y, x)); 194 expectEquals(1, sadInt2IntAlt2(x, y)); 195 expectEquals(1, sadInt2IntAlt2(y, x)); 196 expectEquals(4294967295L, sadInt2Long(x, y)); 197 expectEquals(4294967295L, sadInt2Long(y, x)); 198 expectEquals(4294967296L, sadInt2LongAt1(x, y)); 199 expectEquals(4294967296L, sadInt2LongAt1(y, x)); 200 201 // Use cross-values for the interesting values. 202 int[] interesting = { 203 0x00000000, 0x00000001, 0x00007fff, 0x00008000, 0x00008001, 0x0000ffff, 204 0x00010000, 0x00010001, 0x00017fff, 0x00018000, 0x00018001, 0x0001ffff, 205 0x7fff0000, 0x7fff0001, 0x7fff7fff, 0x7fff8000, 0x7fff8001, 0x7fffffff, 206 0x80000000, 0x80000001, 0x80007fff, 0x80008000, 0x80008001, 0x8000ffff, 207 0x80010000, 0x80010001, 0x80017fff, 0x80018000, 0x80018001, 0x8001ffff, 208 0xffff0000, 0xffff0001, 0xffff7fff, 0xffff8000, 0xffff8001, 0xffffffff 209 }; 210 int n = interesting.length; 211 int m = n * n + 1; 212 x = new int[m]; 213 y = new int[m]; 214 int k = 0; 215 for (int i = 0; i < n; i++) { 216 for (int j = 0; j < n; j++) { 217 x[k] = interesting[i]; 218 y[k] = interesting[j]; 219 k++; 220 } 221 } 222 x[k] = 10; 223 y[k] = 2; 224 expectEquals(8, sadInt2Int(x, y)); 225 expectEquals(-13762600, sadInt2IntAlt(x, y)); 226 expectEquals(8, sadInt2IntAlt2(x, y)); 227 expectEquals(2010030931928L, sadInt2Long(x, y)); 228 expectEquals(2010030931929L, sadInt2LongAt1(x, y)); 229 230 System.out.println("passed"); 231 } 232 233 private static void expectEquals(int expected, int result) { 234 if (expected != result) { 235 throw new Error("Expected: " + expected + ", found: " + result); 236 } 237 } 238 239 private static void expectEquals(long expected, long result) { 240 if (expected != result) { 241 throw new Error("Expected: " + expected + ", found: " + result); 242 } 243 } 244 } 245
