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 SimdSadLong { 21 22 /// CHECK-START: long SimdSadLong.sadLong2Long(long[], long[]) 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: <<ConsL:j\d+>> LongConstant 0 loop:none 26 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 27 /// CHECK-DAG: <<Phi2:j\d+>> Phi [<<ConsL>>,{{j\d+}}] loop:<<Loop>> outer_loop:none 28 /// CHECK-DAG: <<Get1:j\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 29 /// CHECK-DAG: <<Get2:j\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 30 /// CHECK-DAG: <<Sub:j\d+>> Sub [<<Get1>>,<<Get2>>] loop:<<Loop>> outer_loop:none 31 /// CHECK-DAG: <<Intrin:j\d+>> Abs [<<Sub>>] loop:<<Loop>> outer_loop:none 32 /// CHECK-DAG: Add [<<Phi2>>,<<Intrin>>] loop:<<Loop>> outer_loop:none 33 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 34 // 35 /// CHECK-START-ARM64: long SimdSadLong.sadLong2Long(long[], long[]) loop_optimization (after) 36 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 37 /// CHECK-DAG: <<ConsL:j\d+>> LongConstant 0 loop:none 38 /// CHECK-IF: hasIsaFeature("sve") 39 // 40 // SAD idiom is not supported for SVE. 41 /// CHECK-NOT: VecSADAccumulate 42 // 43 /// CHECK-ELSE: 44 // 45 /// CHECK-DAG: <<Cons2:i\d+>> IntConstant 2 loop:none 46 /// CHECK-DAG: <<Set:d\d+>> VecSetScalars [<<ConsL>>] loop:none 47 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 48 /// CHECK-DAG: <<Phi2:d\d+>> Phi [<<Set>>,{{d\d+}}] loop:<<Loop>> outer_loop:none 49 /// CHECK-DAG: <<Load1:d\d+>> VecLoad [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 50 /// CHECK-DAG: <<Load2:d\d+>> VecLoad [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 51 /// CHECK-DAG: <<SAD:d\d+>> VecSADAccumulate [<<Phi2>>,<<Load1>>,<<Load2>>] loop:<<Loop>> outer_loop:none 52 /// CHECK-DAG: Add [<<Phi1>>,<<Cons2>>] loop:<<Loop>> outer_loop:none 53 // 54 /// CHECK-FI: sadLong2Long(long[] x, long[] y)55 private static long sadLong2Long(long[] x, long[] y) { 56 int min_length = Math.min(x.length, y.length); 57 long sad = 0; 58 for (int i = 0; i < min_length; i++) { 59 sad += Math.abs(x[i] - y[i]); 60 } 61 return sad; 62 } 63 64 /// CHECK-START: long SimdSadLong.sadLong2LongAlt(long[], long[]) loop_optimization (before) 65 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 66 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 67 /// CHECK-DAG: <<ConsL:j\d+>> LongConstant 0 loop:none 68 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 69 /// CHECK-DAG: <<Phi2:j\d+>> Phi [<<ConsL>>,{{j\d+}}] loop:<<Loop>> outer_loop:none 70 /// CHECK-DAG: <<Get1:j\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 71 /// CHECK-DAG: <<Get2:j\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 72 /// CHECK-DAG: <<Sub1:j\d+>> Sub [<<Get2>>,<<Get1>>] loop:<<Loop>> outer_loop:none 73 /// CHECK-DAG: <<Sub2:j\d+>> Sub [<<Get1>>,<<Get2>>] loop:<<Loop>> outer_loop:none 74 /// CHECK-DAG: <<Select:j\d+>> Select [<<Sub2>>,<<Sub1>>,{{z\d+}}] loop:<<Loop>> outer_loop:none 75 /// CHECK-DAG: Add [<<Phi2>>,<<Select>>] loop:<<Loop>> outer_loop:none 76 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 77 // 78 // No ABS? No SAD! 79 // 80 /// CHECK-START: long SimdSadLong.sadLong2LongAlt(long[], long[]) loop_optimization (after) 81 /// CHECK-NOT: VecSADAccumulate sadLong2LongAlt(long[] x, long[] y)82 private static long sadLong2LongAlt(long[] x, long[] y) { 83 int min_length = Math.min(x.length, y.length); 84 long sad = 0; 85 for (int i = 0; i < min_length; i++) { 86 long s = x[i]; 87 long p = y[i]; 88 sad += s >= p ? s - p : p - s; 89 } 90 return sad; 91 } 92 93 /// CHECK-START: long SimdSadLong.sadLong2LongAlt2(long[], long[]) loop_optimization (before) 94 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 95 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 96 /// CHECK-DAG: <<ConsL:j\d+>> LongConstant 0 loop:none 97 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 98 /// CHECK-DAG: <<Phi2:j\d+>> Phi [<<ConsL>>,{{j\d+}}] loop:<<Loop>> outer_loop:none 99 /// CHECK-DAG: <<Get1:j\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 100 /// CHECK-DAG: <<Get2:j\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 101 /// CHECK-DAG: <<Sub:j\d+>> Sub [<<Get1>>,<<Get2>>] loop:<<Loop>> outer_loop:none 102 /// CHECK-DAG: <<Intrin:j\d+>> Abs [<<Sub>>] loop:<<Loop>> outer_loop:none 103 /// CHECK-DAG: Add [<<Phi2>>,<<Intrin>>] loop:<<Loop>> outer_loop:none 104 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 105 // 106 /// CHECK-START-ARM64: long SimdSadLong.sadLong2LongAlt2(long[], long[]) loop_optimization (after) 107 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 108 /// CHECK-DAG: <<ConsL:j\d+>> LongConstant 0 loop:none 109 /// CHECK-IF: hasIsaFeature("sve") 110 // 111 // SAD idiom is not supported for SVE. 112 /// CHECK-NOT: VecSADAccumulate 113 // 114 /// CHECK-ELSE: 115 // 116 /// CHECK-DAG: <<Cons2:i\d+>> IntConstant 2 loop:none 117 /// CHECK-DAG: <<Set:d\d+>> VecSetScalars [<<ConsL>>] loop:none 118 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 119 /// CHECK-DAG: <<Phi2:d\d+>> Phi [<<Set>>,{{d\d+}}] loop:<<Loop>> outer_loop:none 120 /// CHECK-DAG: <<Load1:d\d+>> VecLoad [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 121 /// CHECK-DAG: <<Load2:d\d+>> VecLoad [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 122 /// CHECK-DAG: <<SAD:d\d+>> VecSADAccumulate [<<Phi2>>,<<Load1>>,<<Load2>>] loop:<<Loop>> outer_loop:none 123 /// CHECK-DAG: Add [<<Phi1>>,<<Cons2>>] loop:<<Loop>> outer_loop:none 124 // 125 /// CHECK-FI: sadLong2LongAlt2(long[] x, long[] y)126 private static long sadLong2LongAlt2(long[] x, long[] y) { 127 int min_length = Math.min(x.length, y.length); 128 long sad = 0; 129 for (int i = 0; i < min_length; i++) { 130 long s = x[i]; 131 long p = y[i]; 132 long m = s - p; 133 if (m < 0) m = -m; 134 sad += m; 135 } 136 return sad; 137 } 138 139 /// CHECK-START: long SimdSadLong.sadLong2LongAt1(long[], long[]) loop_optimization (before) 140 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 141 /// CHECK-DAG: <<Cons1:i\d+>> IntConstant 1 loop:none 142 /// CHECK-DAG: <<ConsL:j\d+>> LongConstant 1 loop:none 143 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 144 /// CHECK-DAG: <<Phi2:j\d+>> Phi [<<ConsL>>,{{j\d+}}] loop:<<Loop>> outer_loop:none 145 /// CHECK-DAG: <<Get1:j\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 146 /// CHECK-DAG: <<Get2:j\d+>> ArrayGet [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 147 /// CHECK-DAG: <<Sub:j\d+>> Sub [<<Get1>>,<<Get2>>] loop:<<Loop>> outer_loop:none 148 /// CHECK-DAG: <<Intrin:j\d+>> Abs [<<Sub>>] loop:<<Loop>> outer_loop:none 149 /// CHECK-DAG: Add [<<Phi2>>,<<Intrin>>] loop:<<Loop>> outer_loop:none 150 /// CHECK-DAG: Add [<<Phi1>>,<<Cons1>>] loop:<<Loop>> outer_loop:none 151 // 152 /// CHECK-START-ARM64: long SimdSadLong.sadLong2LongAt1(long[], long[]) loop_optimization (after) 153 /// CHECK-DAG: <<Cons0:i\d+>> IntConstant 0 loop:none 154 /// CHECK-DAG: <<ConsL:j\d+>> LongConstant 1 loop:none 155 /// CHECK-IF: hasIsaFeature("sve") 156 // 157 // SAD idiom is not supported for SVE. 158 /// CHECK-NOT: VecSADAccumulate 159 // 160 /// CHECK-ELSE: 161 // 162 /// CHECK-DAG: <<Cons2:i\d+>> IntConstant 2 loop:none 163 /// CHECK-DAG: <<Set:d\d+>> VecSetScalars [<<ConsL>>] loop:none 164 /// CHECK-DAG: <<Phi1:i\d+>> Phi [<<Cons0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none 165 /// CHECK-DAG: <<Phi2:d\d+>> Phi [<<Set>>,{{d\d+}}] loop:<<Loop>> outer_loop:none 166 /// CHECK-DAG: <<Load1:d\d+>> VecLoad [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 167 /// CHECK-DAG: <<Load2:d\d+>> VecLoad [{{l\d+}},<<Phi1>>] loop:<<Loop>> outer_loop:none 168 /// CHECK-DAG: <<SAD:d\d+>> VecSADAccumulate [<<Phi2>>,<<Load1>>,<<Load2>>] loop:<<Loop>> outer_loop:none 169 /// CHECK-DAG: Add [<<Phi1>>,<<Cons2>>] loop:<<Loop>> outer_loop:none 170 // 171 /// CHECK-FI: sadLong2LongAt1(long[] x, long[] y)172 private static long sadLong2LongAt1(long[] x, long[] y) { 173 int min_length = Math.min(x.length, y.length); 174 long sad = 1; // starts at 1 175 for (int i = 0; i < min_length; i++) { 176 sad += Math.abs(x[i] - y[i]); 177 } 178 return sad; 179 } 180 main()181 public static void main() { 182 // Cross-test the two most extreme values individually. 183 long[] x = { 0, Long.MIN_VALUE, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; 184 long[] y = { 0, Long.MAX_VALUE, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; 185 expectEquals(1L, sadLong2Long(x, y)); 186 expectEquals(1L, sadLong2Long(y, x)); 187 expectEquals(-1L, sadLong2LongAlt(x, y)); 188 expectEquals(-1L, sadLong2LongAlt(y, x)); 189 expectEquals(1L, sadLong2LongAlt2(x, y)); 190 expectEquals(1L, sadLong2LongAlt2(y, x)); 191 expectEquals(2L, sadLong2LongAt1(x, y)); 192 expectEquals(2L, sadLong2LongAt1(y, x)); 193 194 // Use cross-values for the interesting values. 195 long[] interesting = { 196 0x0000000000000000L, 0x0000000000000001L, 0x000000007fffffffL, 197 0x0000000080000000L, 0x0000000080000001L, 0x00000000ffffffffL, 198 0x0000000100000000L, 0x0000000100000001L, 0x000000017fffffffL, 199 0x0000000180000000L, 0x0000000180000001L, 0x00000001ffffffffL, 200 0x7fffffff00000000L, 0x7fffffff00000001L, 0x7fffffff7fffffffL, 201 0x7fffffff80000000L, 0x7fffffff80000001L, 0x7fffffffffffffffL, 202 0x8000000000000000L, 0x8000000000000001L, 0x800000007fffffffL, 203 0x8000000080000000L, 0x8000000080000001L, 0x80000000ffffffffL, 204 0x8000000100000000L, 0x8000000100000001L, 0x800000017fffffffL, 205 0x8000000180000000L, 0x8000000180000001L, 0x80000001ffffffffL, 206 0xffffffff00000000L, 0xffffffff00000001L, 0xffffffff7fffffffL, 207 0xffffffff80000000L, 0xffffffff80000001L, 0xffffffffffffffffL 208 }; 209 int n = interesting.length; 210 int m = n * n + 1; 211 x = new long[m]; 212 y = new long[m]; 213 int k = 0; 214 for (int i = 0; i < n; i++) { 215 for (int j = 0; j < n; j++) { 216 x[k] = interesting[i]; 217 y[k] = interesting[j]; 218 k++; 219 } 220 } 221 x[k] = 10; 222 y[k] = 2; 223 expectEquals(8L, sadLong2Long(x, y)); 224 expectEquals(-901943132200L, sadLong2LongAlt(x, y)); 225 expectEquals(8L, sadLong2LongAlt2(x, y)); 226 expectEquals(9L, sadLong2LongAt1(x, y)); 227 228 System.out.println("SimdSadLong passed"); 229 } 230 expectEquals(long expected, long result)231 private static void expectEquals(long expected, long result) { 232 if (expected != result) { 233 throw new Error("Expected: " + expected + ", found: " + result); 234 } 235 } 236 } 237