1 //===- KnownBitsTest.cpp -------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "GISelMITest.h" 10 #include "llvm/CodeGen/GlobalISel/GISelKnownBits.h" 11 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h" 12 13 TEST_F(AArch64GISelMITest, TestKnownBitsCst) { 14 StringRef MIRString = " %3:_(s8) = G_CONSTANT i8 1\n" 15 " %4:_(s8) = COPY %3\n"; 16 setUp(MIRString); 17 if (!TM) 18 return; 19 unsigned CopyReg = Copies[Copies.size() - 1]; 20 MachineInstr *FinalCopy = MRI->getVRegDef(CopyReg); 21 unsigned SrcReg = FinalCopy->getOperand(1).getReg(); 22 unsigned DstReg = FinalCopy->getOperand(0).getReg(); 23 GISelKnownBits Info(*MF); 24 KnownBits Res = Info.getKnownBits(SrcReg); 25 EXPECT_EQ((uint64_t)1, Res.One.getZExtValue()); 26 EXPECT_EQ((uint64_t)0xfe, Res.Zero.getZExtValue()); 27 28 KnownBits Res2 = Info.getKnownBits(DstReg); 29 EXPECT_EQ(Res.One.getZExtValue(), Res2.One.getZExtValue()); 30 EXPECT_EQ(Res.Zero.getZExtValue(), Res2.Zero.getZExtValue()); 31 } 32 33 TEST_F(AArch64GISelMITest, TestKnownBitsCstWithClass) { 34 StringRef MIRString = " %10:gpr32 = MOVi32imm 1\n" 35 " %4:_(s32) = COPY %10\n"; 36 setUp(MIRString); 37 if (!TM) 38 return; 39 unsigned CopyReg = Copies[Copies.size() - 1]; 40 MachineInstr *FinalCopy = MRI->getVRegDef(CopyReg); 41 unsigned SrcReg = FinalCopy->getOperand(1).getReg(); 42 unsigned DstReg = FinalCopy->getOperand(0).getReg(); 43 GISelKnownBits Info(*MF); 44 KnownBits Res = Info.getKnownBits(SrcReg); 45 // We can't analyze %3 due to the register class constraint. We will get a 46 // default-constructed KnownBits back. 47 EXPECT_EQ((uint64_t)1, Res.getBitWidth()); 48 EXPECT_EQ((uint64_t)0, Res.One.getZExtValue()); 49 EXPECT_EQ((uint64_t)0, Res.Zero.getZExtValue()); 50 51 KnownBits Res2 = Info.getKnownBits(DstReg); 52 // We still don't know the values due to the register class constraint but %4 53 // did reveal the size of %3. 54 EXPECT_EQ((uint64_t)32, Res2.getBitWidth()); 55 EXPECT_EQ(Res.One.getZExtValue(), Res2.One.getZExtValue()); 56 EXPECT_EQ(Res.Zero.getZExtValue(), Res2.Zero.getZExtValue()); 57 } 58 59 // Check that we are able to track bits through PHIs 60 // and get the intersections of everything we know on each operand. 61 TEST_F(AArch64GISelMITest, TestKnownBitsCstPHI) { 62 StringRef MIRString = " bb.10:\n" 63 " %10:_(s8) = G_CONSTANT i8 3\n" 64 " %11:_(s1) = G_IMPLICIT_DEF\n" 65 " G_BRCOND %11(s1), %bb.11\n" 66 " G_BR %bb.12\n" 67 "\n" 68 " bb.11:\n" 69 " %12:_(s8) = G_CONSTANT i8 2\n" 70 " G_BR %bb.12\n" 71 "\n" 72 " bb.12:\n" 73 " %13:_(s8) = PHI %10(s8), %bb.10, %12(s8), %bb.11\n" 74 " %14:_(s8) = COPY %13\n"; 75 setUp(MIRString); 76 if (!TM) 77 return; 78 Register CopyReg = Copies[Copies.size() - 1]; 79 MachineInstr *FinalCopy = MRI->getVRegDef(CopyReg); 80 Register SrcReg = FinalCopy->getOperand(1).getReg(); 81 Register DstReg = FinalCopy->getOperand(0).getReg(); 82 GISelKnownBits Info(*MF); 83 KnownBits Res = Info.getKnownBits(SrcReg); 84 EXPECT_EQ((uint64_t)2, Res.One.getZExtValue()); 85 EXPECT_EQ((uint64_t)0xfc, Res.Zero.getZExtValue()); 86 87 KnownBits Res2 = Info.getKnownBits(DstReg); 88 EXPECT_EQ(Res.One.getZExtValue(), Res2.One.getZExtValue()); 89 EXPECT_EQ(Res.Zero.getZExtValue(), Res2.Zero.getZExtValue()); 90 } 91 92 // Check that we report we know nothing when we hit a 93 // non-generic register. 94 // Note: this could be improved though! 95 TEST_F(AArch64GISelMITest, TestKnownBitsCstPHIToNonGenericReg) { 96 StringRef MIRString = " bb.10:\n" 97 " %10:gpr32 = MOVi32imm 3\n" 98 " %11:_(s1) = G_IMPLICIT_DEF\n" 99 " G_BRCOND %11(s1), %bb.11\n" 100 " G_BR %bb.12\n" 101 "\n" 102 " bb.11:\n" 103 " %12:_(s8) = G_CONSTANT i8 2\n" 104 " G_BR %bb.12\n" 105 "\n" 106 " bb.12:\n" 107 " %13:_(s8) = PHI %10, %bb.10, %12(s8), %bb.11\n" 108 " %14:_(s8) = COPY %13\n"; 109 setUp(MIRString); 110 if (!TM) 111 return; 112 Register CopyReg = Copies[Copies.size() - 1]; 113 MachineInstr *FinalCopy = MRI->getVRegDef(CopyReg); 114 Register SrcReg = FinalCopy->getOperand(1).getReg(); 115 Register DstReg = FinalCopy->getOperand(0).getReg(); 116 GISelKnownBits Info(*MF); 117 KnownBits Res = Info.getKnownBits(SrcReg); 118 EXPECT_EQ((uint64_t)0, Res.One.getZExtValue()); 119 EXPECT_EQ((uint64_t)0, Res.Zero.getZExtValue()); 120 121 KnownBits Res2 = Info.getKnownBits(DstReg); 122 EXPECT_EQ(Res.One.getZExtValue(), Res2.One.getZExtValue()); 123 EXPECT_EQ(Res.Zero.getZExtValue(), Res2.Zero.getZExtValue()); 124 } 125 126 // Check that we know nothing when at least one value of a PHI 127 // comes from something we cannot analysis. 128 // This test is not particularly interesting, it is just 129 // here to cover the code that stops the analysis of PHIs 130 // earlier. In that case, we would not even look at the 131 // second incoming value. 132 TEST_F(AArch64GISelMITest, TestKnownBitsUnknownPHI) { 133 StringRef MIRString = 134 " bb.10:\n" 135 " %10:_(s64) = COPY %0\n" 136 " %11:_(s1) = G_IMPLICIT_DEF\n" 137 " G_BRCOND %11(s1), %bb.11\n" 138 " G_BR %bb.12\n" 139 "\n" 140 " bb.11:\n" 141 " %12:_(s64) = G_CONSTANT i64 2\n" 142 " G_BR %bb.12\n" 143 "\n" 144 " bb.12:\n" 145 " %13:_(s64) = PHI %10(s64), %bb.10, %12(s64), %bb.11\n" 146 " %14:_(s64) = COPY %13\n"; 147 setUp(MIRString); 148 if (!TM) 149 return; 150 Register CopyReg = Copies[Copies.size() - 1]; 151 MachineInstr *FinalCopy = MRI->getVRegDef(CopyReg); 152 Register SrcReg = FinalCopy->getOperand(1).getReg(); 153 Register DstReg = FinalCopy->getOperand(0).getReg(); 154 GISelKnownBits Info(*MF); 155 KnownBits Res = Info.getKnownBits(SrcReg); 156 EXPECT_EQ((uint64_t)0, Res.One.getZExtValue()); 157 EXPECT_EQ((uint64_t)0, Res.Zero.getZExtValue()); 158 159 KnownBits Res2 = Info.getKnownBits(DstReg); 160 EXPECT_EQ(Res.One.getZExtValue(), Res2.One.getZExtValue()); 161 EXPECT_EQ(Res.Zero.getZExtValue(), Res2.Zero.getZExtValue()); 162 } 163 164 // Check that we manage to process PHIs that loop on themselves. 165 // For now, the analysis just stops and assumes it knows nothing, 166 // eventually we could teach it how to properly track phis that 167 // loop back. 168 TEST_F(AArch64GISelMITest, TestKnownBitsCstPHIWithLoop) { 169 StringRef MIRString = 170 " bb.10:\n" 171 " %10:_(s8) = G_CONSTANT i8 3\n" 172 " %11:_(s1) = G_IMPLICIT_DEF\n" 173 " G_BRCOND %11(s1), %bb.11\n" 174 " G_BR %bb.12\n" 175 "\n" 176 " bb.11:\n" 177 " %12:_(s8) = G_CONSTANT i8 2\n" 178 " G_BR %bb.12\n" 179 "\n" 180 " bb.12:\n" 181 " %13:_(s8) = PHI %10(s8), %bb.10, %12(s8), %bb.11, %14(s8), %bb.12\n" 182 " %14:_(s8) = COPY %13\n" 183 " G_BR %bb.12\n"; 184 setUp(MIRString); 185 if (!TM) 186 return; 187 Register CopyReg = Copies[Copies.size() - 1]; 188 MachineInstr *FinalCopy = MRI->getVRegDef(CopyReg); 189 Register SrcReg = FinalCopy->getOperand(1).getReg(); 190 Register DstReg = FinalCopy->getOperand(0).getReg(); 191 GISelKnownBits Info(*MF); 192 KnownBits Res = Info.getKnownBits(SrcReg); 193 EXPECT_EQ((uint64_t)0, Res.One.getZExtValue()); 194 EXPECT_EQ((uint64_t)0, Res.Zero.getZExtValue()); 195 196 KnownBits Res2 = Info.getKnownBits(DstReg); 197 EXPECT_EQ(Res.One.getZExtValue(), Res2.One.getZExtValue()); 198 EXPECT_EQ(Res.Zero.getZExtValue(), Res2.Zero.getZExtValue()); 199 } 200 201 // Check that we don't try to analysis PHIs progression. 202 // Setting a deep enough max depth would allow to effectively simulate 203 // what happens in the loop. 204 // Thus, with a deep enough depth, we could actually figure out 205 // that %14's zero known bits are actually at least what we know 206 // for %10, right shifted by one. 207 // However, this process is super expensive compile-time wise and 208 // we don't want to reach that conclusion while playing with max depth. 209 // For now, the analysis just stops and assumes it knows nothing 210 // on PHIs, but eventually we could teach it how to properly track 211 // phis that loop back without relying on the luck effect of max 212 // depth. 213 TEST_F(AArch64GISelMITest, TestKnownBitsDecreasingCstPHIWithLoop) { 214 StringRef MIRString = " bb.10:\n" 215 " %10:_(s8) = G_CONSTANT i8 5\n" 216 " %11:_(s8) = G_CONSTANT i8 1\n" 217 "\n" 218 " bb.12:\n" 219 " %13:_(s8) = PHI %10(s8), %bb.10, %14(s8), %bb.12\n" 220 " %14:_(s8) = G_LSHR %13, %11\n" 221 " %15:_(s8) = COPY %14\n" 222 " G_BR %bb.12\n"; 223 setUp(MIRString); 224 if (!TM) 225 return; 226 Register CopyReg = Copies[Copies.size() - 1]; 227 MachineInstr *FinalCopy = MRI->getVRegDef(CopyReg); 228 Register SrcReg = FinalCopy->getOperand(1).getReg(); 229 Register DstReg = FinalCopy->getOperand(0).getReg(); 230 GISelKnownBits Info(*MF, /*MaxDepth=*/24); 231 KnownBits Res = Info.getKnownBits(SrcReg); 232 EXPECT_EQ((uint64_t)0, Res.One.getZExtValue()); 233 // A single iteration on the PHI (%13) gives: 234 // %10 has known zero of 0xFA 235 // %12 has known zero of 0x80 (we shift right by one so high bit is zero) 236 // Therefore, %14's known zero are 0x80 shifted by one 0xC0. 237 // If we had simulated the loop we could have more zero bits, basically 238 // up to 0xFC (count leading zero of 5, + 1). 239 EXPECT_EQ((uint64_t)0xC0, Res.Zero.getZExtValue()); 240 241 KnownBits Res2 = Info.getKnownBits(DstReg); 242 EXPECT_EQ(Res.One.getZExtValue(), Res2.One.getZExtValue()); 243 EXPECT_EQ(Res.Zero.getZExtValue(), Res2.Zero.getZExtValue()); 244 } 245 246 TEST_F(AArch64GISelMITest, TestKnownBitsPtrToIntViceVersa) { 247 StringRef MIRString = " %3:_(s16) = G_CONSTANT i16 256\n" 248 " %4:_(p0) = G_INTTOPTR %3\n" 249 " %5:_(s32) = G_PTRTOINT %4\n" 250 " %6:_(s32) = COPY %5\n"; 251 setUp(MIRString); 252 if (!TM) 253 return; 254 unsigned CopyReg = Copies[Copies.size() - 1]; 255 MachineInstr *FinalCopy = MRI->getVRegDef(CopyReg); 256 unsigned SrcReg = FinalCopy->getOperand(1).getReg(); 257 GISelKnownBits Info(*MF); 258 KnownBits Res = Info.getKnownBits(SrcReg); 259 EXPECT_EQ(256u, Res.One.getZExtValue()); 260 EXPECT_EQ(0xfffffeffu, Res.Zero.getZExtValue()); 261 } 262 TEST_F(AArch64GISelMITest, TestKnownBitsXOR) { 263 StringRef MIRString = " %3:_(s8) = G_CONSTANT i8 4\n" 264 " %4:_(s8) = G_CONSTANT i8 7\n" 265 " %5:_(s8) = G_XOR %3, %4\n" 266 " %6:_(s8) = COPY %5\n"; 267 setUp(MIRString); 268 if (!TM) 269 return; 270 unsigned CopyReg = Copies[Copies.size() - 1]; 271 MachineInstr *FinalCopy = MRI->getVRegDef(CopyReg); 272 unsigned SrcReg = FinalCopy->getOperand(1).getReg(); 273 GISelKnownBits Info(*MF); 274 KnownBits Res = Info.getKnownBits(SrcReg); 275 EXPECT_EQ(3u, Res.One.getZExtValue()); 276 EXPECT_EQ(252u, Res.Zero.getZExtValue()); 277 } 278 279 TEST_F(AArch64GISelMITest, TestKnownBits) { 280 281 StringRef MIR = " %3:_(s32) = G_TRUNC %0\n" 282 " %4:_(s32) = G_TRUNC %1\n" 283 " %5:_(s32) = G_CONSTANT i32 5\n" 284 " %6:_(s32) = G_CONSTANT i32 24\n" 285 " %7:_(s32) = G_CONSTANT i32 28\n" 286 " %14:_(p0) = G_INTTOPTR %7\n" 287 " %16:_(s32) = G_PTRTOINT %14\n" 288 " %8:_(s32) = G_SHL %3, %5\n" 289 " %9:_(s32) = G_SHL %4, %5\n" 290 " %10:_(s32) = G_OR %8, %6\n" 291 " %11:_(s32) = G_OR %9, %16\n" 292 " %12:_(s32) = G_MUL %10, %11\n" 293 " %13:_(s32) = COPY %12\n"; 294 setUp(MIR); 295 if (!TM) 296 return; 297 unsigned CopyReg = Copies[Copies.size() - 1]; 298 MachineInstr *FinalCopy = MRI->getVRegDef(CopyReg); 299 unsigned SrcReg = FinalCopy->getOperand(1).getReg(); 300 GISelKnownBits Info(*MF); 301 KnownBits Known = Info.getKnownBits(SrcReg); 302 EXPECT_FALSE(Known.hasConflict()); 303 EXPECT_EQ(0u, Known.One.getZExtValue()); 304 EXPECT_EQ(31u, Known.Zero.getZExtValue()); 305 APInt Zeroes = Info.getKnownZeroes(SrcReg); 306 EXPECT_EQ(Known.Zero, Zeroes); 307 } 308 309 TEST_F(AArch64GISelMITest, TestSignBitIsZero) { 310 setUp(); 311 if (!TM) 312 return; 313 314 const LLT S32 = LLT::scalar(32); 315 auto SignBit = B.buildConstant(S32, 0x80000000); 316 auto Zero = B.buildConstant(S32, 0); 317 318 GISelKnownBits KnownBits(*MF); 319 320 EXPECT_TRUE(KnownBits.signBitIsZero(Zero.getReg(0))); 321 EXPECT_FALSE(KnownBits.signBitIsZero(SignBit.getReg(0))); 322 } 323 324 TEST_F(AArch64GISelMITest, TestNumSignBitsConstant) { 325 StringRef MIRString = " %3:_(s8) = G_CONSTANT i8 1\n" 326 " %4:_(s8) = COPY %3\n" 327 328 " %5:_(s8) = G_CONSTANT i8 -1\n" 329 " %6:_(s8) = COPY %5\n" 330 331 " %7:_(s8) = G_CONSTANT i8 127\n" 332 " %8:_(s8) = COPY %7\n" 333 334 " %9:_(s8) = G_CONSTANT i8 32\n" 335 " %10:_(s8) = COPY %9\n" 336 337 " %11:_(s8) = G_CONSTANT i8 -32\n" 338 " %12:_(s8) = COPY %11\n"; 339 setUp(MIRString); 340 if (!TM) 341 return; 342 Register CopyReg1 = Copies[Copies.size() - 5]; 343 Register CopyRegNeg1 = Copies[Copies.size() - 4]; 344 Register CopyReg127 = Copies[Copies.size() - 3]; 345 Register CopyReg32 = Copies[Copies.size() - 2]; 346 Register CopyRegNeg32 = Copies[Copies.size() - 1]; 347 348 GISelKnownBits Info(*MF); 349 EXPECT_EQ(7u, Info.computeNumSignBits(CopyReg1)); 350 EXPECT_EQ(8u, Info.computeNumSignBits(CopyRegNeg1)); 351 EXPECT_EQ(1u, Info.computeNumSignBits(CopyReg127)); 352 EXPECT_EQ(2u, Info.computeNumSignBits(CopyReg32)); 353 EXPECT_EQ(3u, Info.computeNumSignBits(CopyRegNeg32)); 354 } 355 356 TEST_F(AArch64GISelMITest, TestNumSignBitsSext) { 357 StringRef MIRString = " %3:_(p0) = G_IMPLICIT_DEF\n" 358 " %4:_(s8) = G_LOAD %3 :: (load 1)\n" 359 " %5:_(s32) = G_SEXT %4\n" 360 " %6:_(s32) = COPY %5\n" 361 362 " %7:_(s8) = G_CONSTANT i8 -1\n" 363 " %8:_(s32) = G_SEXT %7\n" 364 " %9:_(s32) = COPY %8\n"; 365 setUp(MIRString); 366 if (!TM) 367 return; 368 Register CopySextLoad = Copies[Copies.size() - 2]; 369 Register CopySextNeg1 = Copies[Copies.size() - 1]; 370 371 GISelKnownBits Info(*MF); 372 EXPECT_EQ(25u, Info.computeNumSignBits(CopySextLoad)); 373 EXPECT_EQ(32u, Info.computeNumSignBits(CopySextNeg1)); 374 } 375 376 TEST_F(AArch64GISelMITest, TestNumSignBitsTrunc) { 377 StringRef MIRString = " %3:_(p0) = G_IMPLICIT_DEF\n" 378 " %4:_(s32) = G_LOAD %3 :: (load 4)\n" 379 " %5:_(s8) = G_TRUNC %4\n" 380 " %6:_(s8) = COPY %5\n" 381 382 " %7:_(s32) = G_CONSTANT i32 -1\n" 383 " %8:_(s8) = G_TRUNC %7\n" 384 " %9:_(s8) = COPY %8\n" 385 386 " %10:_(s32) = G_CONSTANT i32 7\n" 387 " %11:_(s8) = G_TRUNC %10\n" 388 " %12:_(s8) = COPY %11\n"; 389 setUp(MIRString); 390 if (!TM) 391 return; 392 Register CopyTruncLoad = Copies[Copies.size() - 3]; 393 Register CopyTruncNeg1 = Copies[Copies.size() - 2]; 394 Register CopyTrunc7 = Copies[Copies.size() - 1]; 395 396 GISelKnownBits Info(*MF); 397 EXPECT_EQ(1u, Info.computeNumSignBits(CopyTruncLoad)); 398 EXPECT_EQ(8u, Info.computeNumSignBits(CopyTruncNeg1)); 399 EXPECT_EQ(5u, Info.computeNumSignBits(CopyTrunc7)); 400 } 401 402 TEST_F(AMDGPUGISelMITest, TestNumSignBitsTrunc) { 403 StringRef MIRString = 404 " %3:_(<4 x s32>) = G_IMPLICIT_DEF\n" 405 " %4:_(s32) = G_IMPLICIT_DEF\n" 406 " %5:_(s32) = G_AMDGPU_BUFFER_LOAD_UBYTE %3, %4, %4, %4, 0, 0, 0 :: (load 1)\n" 407 " %6:_(s32) = COPY %5\n" 408 409 " %7:_(s32) = G_AMDGPU_BUFFER_LOAD_SBYTE %3, %4, %4, %4, 0, 0, 0 :: (load 1)\n" 410 " %8:_(s32) = COPY %7\n" 411 412 " %9:_(s32) = G_AMDGPU_BUFFER_LOAD_USHORT %3, %4, %4, %4, 0, 0, 0 :: (load 2)\n" 413 " %10:_(s32) = COPY %9\n" 414 415 " %11:_(s32) = G_AMDGPU_BUFFER_LOAD_SSHORT %3, %4, %4, %4, 0, 0, 0 :: (load 2)\n" 416 " %12:_(s32) = COPY %11\n"; 417 418 setUp(MIRString); 419 if (!TM) 420 return; 421 422 Register CopyLoadUByte = Copies[Copies.size() - 4]; 423 Register CopyLoadSByte = Copies[Copies.size() - 3]; 424 Register CopyLoadUShort = Copies[Copies.size() - 2]; 425 Register CopyLoadSShort = Copies[Copies.size() - 1]; 426 427 GISelKnownBits Info(*MF); 428 429 EXPECT_EQ(24u, Info.computeNumSignBits(CopyLoadUByte)); 430 EXPECT_EQ(25u, Info.computeNumSignBits(CopyLoadSByte)); 431 EXPECT_EQ(16u, Info.computeNumSignBits(CopyLoadUShort)); 432 EXPECT_EQ(17u, Info.computeNumSignBits(CopyLoadSShort)); 433 } 434