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