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 SimdSadInt { 21 22 /// CHECK-START: int SimdSadInt.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: <<Phi2:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 26 /// CHECK-DAG: <<Phi1: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+>> Abs [<<Sub>>] 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: int SimdSadInt.sadInt2Int(int[], int[]) loop_optimization (after) 35 /// CHECK-DAG: <<Cons:i\d+>> IntConstant 2 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 // 43 /// CHECK-START-ARM64: int SimdSadInt.sadInt2Int(int[], int[]) loop_optimization (after) 44 /// CHECK-IF: hasIsaFeature("sve") 45 // 46 // SAD idiom is not supported for SVE. 47 /// CHECK-NOT: VecSADAccumulate 48 // 49 /// CHECK-ELSE: 50 // 51 /// CHECK-DAG: <<Cons:i\d+>> IntConstant 4 loop:none 52 /// CHECK-DAG: <<Set:d\d+>> VecSetScalars [{{i\d+}}] loop:none 53 /// CHECK-DAG: <<Phi:d\d+>> Phi [<<Set>>,{{d\d+}}] loop:<<Loop:B\d+>> outer_loop:none 54 /// CHECK-DAG: <<Ld1:d\d+>> VecLoad [{{l\d+}},<<I:i\d+>>] loop:<<Loop>> outer_loop:none 55 /// CHECK-DAG: <<Ld2:d\d+>> VecLoad [{{l\d+}},<<I>>] loop:<<Loop>> outer_loop:none 56 /// CHECK-DAG: <<SAD:d\d+>> VecSADAccumulate [<<Phi>>,<<Ld1>>,<<Ld2>>] loop:<<Loop>> outer_loop:none 57 /// CHECK-DAG: Add [<<I>>,<<Cons>>] loop:<<Loop>> outer_loop:none 58 // 59 /// CHECK-FI: sadInt2Int(int[] x, int[] y)60 private static int sadInt2Int(int[] x, int[] y) { 61 int min_length = Math.min(x.length, y.length); 62 int sad = 0; 63 for (int i = 0; i < min_length; i++) { 64 sad += Math.abs(x[i] - y[i]); 65 } 66 return sad; 67 } 68 69 /// CHECK-START: int SimdSadInt.sadInt2IntAlt(int[], int[]) loop_optimization (before) 70 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 71 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 72 /// CHECK-DAG: <<Phi2:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 73 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 74 /// CHECK-DAG: <<Get1:i\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 75 /// CHECK-DAG: <<Get2:i\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 76 /// CHECK-DAG: <<Sub1:i\d+>> Sub [<<Get2>>,<<Get1>>] loop:<<Loop>> outer_loop:none 77 /// CHECK-DAG: <<Sub2:i\d+>> Sub [<<Get1>>,<<Get2>>] loop:<<Loop>> outer_loop:none 78 /// CHECK-DAG: <<Select:i\d+>> Select [<<Sub2>>,<<Sub1>>,{{z\d+}}] loop:<<Loop>> outer_loop:none 79 /// CHECK-DAG: Add [<<Phi2>>,<<Select>>] loop:<<Loop>> outer_loop:none 80 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 81 // 82 // No ABS? No SAD! 83 // 84 /// CHECK-START: int SimdSadInt.sadInt2IntAlt(int[], int[]) loop_optimization (after) 85 /// CHECK-NOT: VecSADAccumulate sadInt2IntAlt(int[] x, int[] y)86 private static int sadInt2IntAlt(int[] x, int[] y) { 87 int min_length = Math.min(x.length, y.length); 88 int sad = 0; 89 for (int i = 0; i < min_length; i++) { 90 int s = x[i]; 91 int p = y[i]; 92 sad += s >= p ? s - p : p - s; 93 } 94 return sad; 95 } 96 97 /// CHECK-START: int SimdSadInt.sadInt2IntAlt2(int[], int[]) loop_optimization (before) 98 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 99 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 100 /// CHECK-DAG: <<Phi2:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 101 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop>> outer_loop:none 102 /// CHECK-DAG: <<Get1:i\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 103 /// CHECK-DAG: <<Get2:i\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 104 /// CHECK-DAG: <<Sub:i\d+>> Sub [<<Get1>>,<<Get2>>] loop:<<Loop>> outer_loop:none 105 /// CHECK-DAG: <<Intrin:i\d+>> Abs [<<Sub>>] loop:<<Loop>> outer_loop:none 106 /// CHECK-DAG: Add [<<Phi2>>,<<Intrin>>] loop:<<Loop>> outer_loop:none 107 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 108 // 109 /// CHECK-START-ARM: int SimdSadInt.sadInt2IntAlt2(int[], int[]) loop_optimization (after) 110 /// CHECK-DAG: <<Cons:i\d+>> IntConstant 2 loop:none 111 /// CHECK-DAG: <<Set:d\d+>> VecSetScalars [{{i\d+}}] loop:none 112 /// CHECK-DAG: <<Phi:d\d+>> Phi [<<Set>>,{{d\d+}}] loop:<<Loop:B\d+>> outer_loop:none 113 /// CHECK-DAG: <<Ld1:d\d+>> VecLoad [{{l\d+}},<<I:i\d+>>] loop:<<Loop>> outer_loop:none 114 /// CHECK-DAG: <<Ld2:d\d+>> VecLoad [{{l\d+}},<<I>>] loop:<<Loop>> outer_loop:none 115 /// CHECK-DAG: <<SAD:d\d+>> VecSADAccumulate [<<Phi>>,<<Ld1>>,<<Ld2>>] loop:<<Loop>> outer_loop:none 116 /// CHECK-DAG: Add [<<I>>,<<Cons>>] loop:<<Loop>> outer_loop:none 117 // 118 /// CHECK-START-ARM64: int SimdSadInt.sadInt2IntAlt2(int[], int[]) loop_optimization (after) 119 /// CHECK-IF: hasIsaFeature("sve") 120 // 121 // SAD idiom is not supported for SVE. 122 /// CHECK-NOT: VecSADAccumulate 123 // 124 /// CHECK-ELSE: 125 // 126 /// CHECK-DAG: <<Cons:i\d+>> IntConstant 4 loop:none 127 /// CHECK-DAG: <<Set:d\d+>> VecSetScalars [{{i\d+}}] loop:none 128 /// CHECK-DAG: <<Phi:d\d+>> Phi [<<Set>>,{{d\d+}}] loop:<<Loop:B\d+>> outer_loop:none 129 /// CHECK-DAG: <<Ld1:d\d+>> VecLoad [{{l\d+}},<<I:i\d+>>] loop:<<Loop>> outer_loop:none 130 /// CHECK-DAG: <<Ld2:d\d+>> VecLoad [{{l\d+}},<<I>>] loop:<<Loop>> outer_loop:none 131 /// CHECK-DAG: <<SAD:d\d+>> VecSADAccumulate [<<Phi>>,<<Ld1>>,<<Ld2>>] loop:<<Loop>> outer_loop:none 132 /// CHECK-DAG: Add [<<I>>,<<Cons>>] loop:<<Loop>> outer_loop:none 133 // 134 /// CHECK-FI: sadInt2IntAlt2(int[] x, int[] y)135 private static int sadInt2IntAlt2(int[] x, int[] y) { 136 int min_length = Math.min(x.length, y.length); 137 int sad = 0; 138 for (int i = 0; i < min_length; i++) { 139 int s = x[i]; 140 int p = y[i]; 141 int m = s - p; 142 if (m < 0) m = -m; 143 sad += m; 144 } 145 return sad; 146 } 147 148 /// CHECK-START: long SimdSadInt.sadInt2Long(int[], int[]) loop_optimization (before) 149 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 150 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 151 /// CHECK-DAG: <<ConsL:j\d+>> LongConstant 0 loop:none 152 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 153 /// CHECK-DAG: <<Phi2:j\d+>> Phi [<<ConsL>>,{{j\d+}}] loop:<<Loop>> outer_loop:none 154 /// CHECK-DAG: <<Get1:i\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 155 /// CHECK-DAG: <<Get2:i\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 156 /// CHECK-DAG: <<Cnv1:j\d+>> TypeConversion [<<Get1>>] loop:<<Loop>> outer_loop:none 157 /// CHECK-DAG: <<Cnv2:j\d+>> TypeConversion [<<Get2>>] loop:<<Loop>> outer_loop:none 158 /// CHECK-DAG: <<Sub:j\d+>> Sub [<<Cnv1>>,<<Cnv2>>] loop:<<Loop>> outer_loop:none 159 /// CHECK-DAG: <<Intrin:j\d+>> Abs [<<Sub>>] loop:<<Loop>> outer_loop:none 160 /// CHECK-DAG: Add [<<Phi2>>,<<Intrin>>] loop:<<Loop>> outer_loop:none 161 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 162 // 163 /// CHECK-START-ARM64: long SimdSadInt.sadInt2Long(int[], int[]) loop_optimization (after) 164 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 165 /// CHECK-DAG: <<ConsL:j\d+>> LongConstant 0 loop:none 166 /// CHECK-IF: hasIsaFeature("sve") 167 // 168 // SAD idiom is not supported for SVE. 169 /// CHECK-NOT: VecSADAccumulate 170 // 171 /// CHECK-ELSE: 172 // 173 /// CHECK-DAG: <<Cons4:i\d+>> IntConstant 4 loop:none 174 /// CHECK-DAG: <<Set:d\d+>> VecSetScalars [<<ConsL>>] loop:none 175 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 176 /// CHECK-DAG: <<Phi2:d\d+>> Phi [<<Set>>,{{d\d+}}] loop:<<Loop>> outer_loop:none 177 /// CHECK-DAG: <<Load1:d\d+>> VecLoad [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 178 /// CHECK-DAG: <<Load2:d\d+>> VecLoad [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 179 /// CHECK-DAG: <<SAD:d\d+>> VecSADAccumulate [<<Phi2>>,<<Load1>>,<<Load2>>] loop:<<Loop>> outer_loop:none 180 /// CHECK-DAG: Add [<<Phi1>>,<<Cons4>>] loop:<<Loop>> outer_loop:none 181 // 182 /// CHECK-FI: sadInt2Long(int[] x, int[] y)183 private static long sadInt2Long(int[] x, int[] y) { 184 int min_length = Math.min(x.length, y.length); 185 long sad = 0; 186 for (int i = 0; i < min_length; i++) { 187 long s = x[i]; 188 long p = y[i]; 189 sad += Math.abs(s - p); 190 } 191 return sad; 192 } 193 194 /// CHECK-START: long SimdSadInt.sadInt2LongAt1(int[], int[]) loop_optimization (before) 195 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 196 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 197 /// CHECK-DAG: <<ConsL:j\d+>> LongConstant 1 loop:none 198 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 199 /// CHECK-DAG: <<Phi2:j\d+>> Phi [<<ConsL>>,{{j\d+}}] loop:<<Loop>> outer_loop:none 200 /// CHECK-DAG: <<Get1:i\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 201 /// CHECK-DAG: <<Get2:i\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 202 /// CHECK-DAG: <<Cnv1:j\d+>> TypeConversion [<<Get1>>] loop:<<Loop>> outer_loop:none 203 /// CHECK-DAG: <<Cnv2:j\d+>> TypeConversion [<<Get2>>] loop:<<Loop>> outer_loop:none 204 /// CHECK-DAG: <<Sub:j\d+>> Sub [<<Cnv1>>,<<Cnv2>>] loop:<<Loop>> outer_loop:none 205 /// CHECK-DAG: <<Intrin:j\d+>> Abs [<<Sub>>] loop:<<Loop>> outer_loop:none 206 /// CHECK-DAG: Add [<<Phi2>>,<<Intrin>>] loop:<<Loop>> outer_loop:none 207 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 208 // 209 /// CHECK-START-ARM64: long SimdSadInt.sadInt2LongAt1(int[], int[]) loop_optimization (after) 210 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 211 /// CHECK-DAG: <<ConsL:j\d+>> LongConstant 1 loop:none 212 /// CHECK-IF: hasIsaFeature("sve") 213 // 214 // SAD idiom is not supported for SVE. 215 /// CHECK-NOT: VecSADAccumulate 216 // 217 /// CHECK-ELSE: 218 // 219 /// CHECK-DAG: <<Cons4:i\d+>> IntConstant 4 loop:none 220 /// CHECK-DAG: <<Set:d\d+>> VecSetScalars [<<ConsL>>] loop:none 221 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 222 /// CHECK-DAG: <<Phi2:d\d+>> Phi [<<Set>>,{{d\d+}}] loop:<<Loop>> outer_loop:none 223 /// CHECK-DAG: <<Load1:d\d+>> VecLoad [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 224 /// CHECK-DAG: <<Load2:d\d+>> VecLoad [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 225 /// CHECK-DAG: <<SAD:d\d+>> VecSADAccumulate [<<Phi2>>,<<Load1>>,<<Load2>>] loop:<<Loop>> outer_loop:none 226 /// CHECK-DAG: Add [<<Phi1>>,<<Cons4>>] loop:<<Loop>> outer_loop:none 227 // 228 /// CHECK-FI: sadInt2LongAt1(int[] x, int[] y)229 private static long sadInt2LongAt1(int[] x, int[] y) { 230 int min_length = Math.min(x.length, y.length); 231 long sad = 1; // starts at 1 232 for (int i = 0; i < min_length; i++) { 233 long s = x[i]; 234 long p = y[i]; 235 sad += Math.abs(s - p); 236 } 237 return sad; 238 } 239 main()240 public static void main() { 241 // Cross-test the two most extreme values individually. 242 int[] x = { 0, Integer.MAX_VALUE, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; 243 int[] y = { 0, Integer.MIN_VALUE, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; 244 expectEquals(1, sadInt2Int(x, y)); 245 expectEquals(1, sadInt2Int(y, x)); 246 expectEquals(-1, sadInt2IntAlt(x, y)); 247 expectEquals(-1, sadInt2IntAlt(y, x)); 248 expectEquals(1, sadInt2IntAlt2(x, y)); 249 expectEquals(1, sadInt2IntAlt2(y, x)); 250 expectEquals(4294967295L, sadInt2Long(x, y)); 251 expectEquals(4294967295L, sadInt2Long(y, x)); 252 expectEquals(4294967296L, sadInt2LongAt1(x, y)); 253 expectEquals(4294967296L, sadInt2LongAt1(y, x)); 254 255 // Use cross-values for the interesting values. 256 int[] interesting = { 257 0x00000000, 0x00000001, 0x00007fff, 0x00008000, 0x00008001, 0x0000ffff, 258 0x00010000, 0x00010001, 0x00017fff, 0x00018000, 0x00018001, 0x0001ffff, 259 0x7fff0000, 0x7fff0001, 0x7fff7fff, 0x7fff8000, 0x7fff8001, 0x7fffffff, 260 0x80000000, 0x80000001, 0x80007fff, 0x80008000, 0x80008001, 0x8000ffff, 261 0x80010000, 0x80010001, 0x80017fff, 0x80018000, 0x80018001, 0x8001ffff, 262 0xffff0000, 0xffff0001, 0xffff7fff, 0xffff8000, 0xffff8001, 0xffffffff 263 }; 264 int n = interesting.length; 265 int m = n * n + 1; 266 x = new int[m]; 267 y = new int[m]; 268 int k = 0; 269 for (int i = 0; i < n; i++) { 270 for (int j = 0; j < n; j++) { 271 x[k] = interesting[i]; 272 y[k] = interesting[j]; 273 k++; 274 } 275 } 276 x[k] = 10; 277 y[k] = 2; 278 expectEquals(8, sadInt2Int(x, y)); 279 expectEquals(-13762600, sadInt2IntAlt(x, y)); 280 expectEquals(8, sadInt2IntAlt2(x, y)); 281 expectEquals(2010030931928L, sadInt2Long(x, y)); 282 expectEquals(2010030931929L, sadInt2LongAt1(x, y)); 283 284 System.out.println("SimdSadInt passed"); 285 } 286 expectEquals(int expected, int result)287 private static void expectEquals(int expected, int result) { 288 if (expected != result) { 289 throw new Error("Expected: " + expected + ", found: " + result); 290 } 291 } 292 expectEquals(long expected, long result)293 private static void expectEquals(long expected, long result) { 294 if (expected != result) { 295 throw new Error("Expected: " + expected + ", found: " + result); 296 } 297 } 298 } 299