1 //===- ValueTrackingTest.cpp - ValueTracking tests ------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 #include "llvm/Analysis/ValueTracking.h" 11 #include "llvm/AsmParser/Parser.h" 12 #include "llvm/IR/Function.h" 13 #include "llvm/IR/InstIterator.h" 14 #include "llvm/IR/LLVMContext.h" 15 #include "llvm/IR/Module.h" 16 #include "llvm/Support/ErrorHandling.h" 17 #include "llvm/Support/SourceMgr.h" 18 #include "llvm/Support/KnownBits.h" 19 #include "gtest/gtest.h" 20 21 using namespace llvm; 22 23 namespace { 24 25 class MatchSelectPatternTest : public testing::Test { 26 protected: 27 void parseAssembly(const char *Assembly) { 28 SMDiagnostic Error; 29 M = parseAssemblyString(Assembly, Error, Context); 30 31 std::string errMsg; 32 raw_string_ostream os(errMsg); 33 Error.print("", os); 34 35 // A failure here means that the test itself is buggy. 36 if (!M) 37 report_fatal_error(os.str()); 38 39 Function *F = M->getFunction("test"); 40 if (F == nullptr) 41 report_fatal_error("Test must have a function named @test"); 42 43 A = nullptr; 44 for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) { 45 if (I->hasName()) { 46 if (I->getName() == "A") 47 A = &*I; 48 } 49 } 50 if (A == nullptr) 51 report_fatal_error("@test must have an instruction %A"); 52 } 53 54 void expectPattern(const SelectPatternResult &P) { 55 Value *LHS, *RHS; 56 Instruction::CastOps CastOp; 57 SelectPatternResult R = matchSelectPattern(A, LHS, RHS, &CastOp); 58 EXPECT_EQ(P.Flavor, R.Flavor); 59 EXPECT_EQ(P.NaNBehavior, R.NaNBehavior); 60 EXPECT_EQ(P.Ordered, R.Ordered); 61 } 62 63 LLVMContext Context; 64 std::unique_ptr<Module> M; 65 Instruction *A, *B; 66 }; 67 68 } 69 70 TEST_F(MatchSelectPatternTest, SimpleFMin) { 71 parseAssembly( 72 "define float @test(float %a) {\n" 73 " %1 = fcmp ult float %a, 5.0\n" 74 " %A = select i1 %1, float %a, float 5.0\n" 75 " ret float %A\n" 76 "}\n"); 77 expectPattern({SPF_FMINNUM, SPNB_RETURNS_NAN, false}); 78 } 79 80 TEST_F(MatchSelectPatternTest, SimpleFMax) { 81 parseAssembly( 82 "define float @test(float %a) {\n" 83 " %1 = fcmp ogt float %a, 5.0\n" 84 " %A = select i1 %1, float %a, float 5.0\n" 85 " ret float %A\n" 86 "}\n"); 87 expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, true}); 88 } 89 90 TEST_F(MatchSelectPatternTest, SwappedFMax) { 91 parseAssembly( 92 "define float @test(float %a) {\n" 93 " %1 = fcmp olt float 5.0, %a\n" 94 " %A = select i1 %1, float %a, float 5.0\n" 95 " ret float %A\n" 96 "}\n"); 97 expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, false}); 98 } 99 100 TEST_F(MatchSelectPatternTest, SwappedFMax2) { 101 parseAssembly( 102 "define float @test(float %a) {\n" 103 " %1 = fcmp olt float %a, 5.0\n" 104 " %A = select i1 %1, float 5.0, float %a\n" 105 " ret float %A\n" 106 "}\n"); 107 expectPattern({SPF_FMAXNUM, SPNB_RETURNS_NAN, false}); 108 } 109 110 TEST_F(MatchSelectPatternTest, SwappedFMax3) { 111 parseAssembly( 112 "define float @test(float %a) {\n" 113 " %1 = fcmp ult float %a, 5.0\n" 114 " %A = select i1 %1, float 5.0, float %a\n" 115 " ret float %A\n" 116 "}\n"); 117 expectPattern({SPF_FMAXNUM, SPNB_RETURNS_OTHER, true}); 118 } 119 120 TEST_F(MatchSelectPatternTest, FastFMin) { 121 parseAssembly( 122 "define float @test(float %a) {\n" 123 " %1 = fcmp nnan olt float %a, 5.0\n" 124 " %A = select i1 %1, float %a, float 5.0\n" 125 " ret float %A\n" 126 "}\n"); 127 expectPattern({SPF_FMINNUM, SPNB_RETURNS_ANY, false}); 128 } 129 130 TEST_F(MatchSelectPatternTest, FMinConstantZero) { 131 parseAssembly( 132 "define float @test(float %a) {\n" 133 " %1 = fcmp ole float %a, 0.0\n" 134 " %A = select i1 %1, float %a, float 0.0\n" 135 " ret float %A\n" 136 "}\n"); 137 // This shouldn't be matched, as %a could be -0.0. 138 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 139 } 140 141 TEST_F(MatchSelectPatternTest, FMinConstantZeroNsz) { 142 parseAssembly( 143 "define float @test(float %a) {\n" 144 " %1 = fcmp nsz ole float %a, 0.0\n" 145 " %A = select i1 %1, float %a, float 0.0\n" 146 " ret float %A\n" 147 "}\n"); 148 // But this should be, because we've ignored signed zeroes. 149 expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, true}); 150 } 151 152 TEST_F(MatchSelectPatternTest, VectorFMinNaN) { 153 parseAssembly( 154 "define <4 x float> @test(<4 x float> %a) {\n" 155 " %1 = fcmp ule <4 x float> %a, \n" 156 " <float 5.0, float 5.0, float 5.0, float 5.0>\n" 157 " %A = select <4 x i1> %1, <4 x float> %a,\n" 158 " <4 x float> <float 5.0, float 5.0, float 5.0, float 5.0>\n" 159 " ret <4 x float> %A\n" 160 "}\n"); 161 // Check that pattern matching works on vectors where each lane has the same 162 // unordered pattern. 163 expectPattern({SPF_FMINNUM, SPNB_RETURNS_NAN, false}); 164 } 165 166 TEST_F(MatchSelectPatternTest, VectorFMinOtherOrdered) { 167 parseAssembly( 168 "define <4 x float> @test(<4 x float> %a) {\n" 169 " %1 = fcmp ole <4 x float> %a, \n" 170 " <float 5.0, float 5.0, float 5.0, float 5.0>\n" 171 " %A = select <4 x i1> %1, <4 x float> %a,\n" 172 " <4 x float> <float 5.0, float 5.0, float 5.0, float 5.0>\n" 173 " ret <4 x float> %A\n" 174 "}\n"); 175 // Check that pattern matching works on vectors where each lane has the same 176 // ordered pattern. 177 expectPattern({SPF_FMINNUM, SPNB_RETURNS_OTHER, true}); 178 } 179 180 TEST_F(MatchSelectPatternTest, VectorNotFMinNaN) { 181 parseAssembly( 182 "define <4 x float> @test(<4 x float> %a) {\n" 183 " %1 = fcmp ule <4 x float> %a, \n" 184 " <float 5.0, float 0x7ff8000000000000, float 5.0, float 5.0>\n" 185 " %A = select <4 x i1> %1, <4 x float> %a,\n" 186 " <4 x float> <float 5.0, float 0x7ff8000000000000, float 5.0, float " 187 "5.0>\n" 188 " ret <4 x float> %A\n" 189 "}\n"); 190 // The lane that contains a NaN (0x7ff80...) behaves like a 191 // non-NaN-propagating min and the other lines behave like a NaN-propagating 192 // min, so check that neither is returned. 193 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 194 } 195 196 TEST_F(MatchSelectPatternTest, VectorNotFMinZero) { 197 parseAssembly( 198 "define <4 x float> @test(<4 x float> %a) {\n" 199 " %1 = fcmp ule <4 x float> %a, \n" 200 " <float 5.0, float -0.0, float 5.0, float 5.0>\n" 201 " %A = select <4 x i1> %1, <4 x float> %a,\n" 202 " <4 x float> <float 5.0, float 0.0, float 5.0, float 5.0>\n" 203 " ret <4 x float> %A\n" 204 "}\n"); 205 // Always selects the second lane of %a if it is positive or negative zero, so 206 // this is stricter than a min. 207 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 208 } 209 210 TEST_F(MatchSelectPatternTest, DoubleCastU) { 211 parseAssembly( 212 "define i32 @test(i8 %a, i8 %b) {\n" 213 " %1 = icmp ult i8 %a, %b\n" 214 " %2 = zext i8 %a to i32\n" 215 " %3 = zext i8 %b to i32\n" 216 " %A = select i1 %1, i32 %2, i32 %3\n" 217 " ret i32 %A\n" 218 "}\n"); 219 // We should be able to look through the situation where we cast both operands 220 // to the select. 221 expectPattern({SPF_UMIN, SPNB_NA, false}); 222 } 223 224 TEST_F(MatchSelectPatternTest, DoubleCastS) { 225 parseAssembly( 226 "define i32 @test(i8 %a, i8 %b) {\n" 227 " %1 = icmp slt i8 %a, %b\n" 228 " %2 = sext i8 %a to i32\n" 229 " %3 = sext i8 %b to i32\n" 230 " %A = select i1 %1, i32 %2, i32 %3\n" 231 " ret i32 %A\n" 232 "}\n"); 233 // We should be able to look through the situation where we cast both operands 234 // to the select. 235 expectPattern({SPF_SMIN, SPNB_NA, false}); 236 } 237 238 TEST_F(MatchSelectPatternTest, DoubleCastBad) { 239 parseAssembly( 240 "define i32 @test(i8 %a, i8 %b) {\n" 241 " %1 = icmp ult i8 %a, %b\n" 242 " %2 = zext i8 %a to i32\n" 243 " %3 = sext i8 %b to i32\n" 244 " %A = select i1 %1, i32 %2, i32 %3\n" 245 " ret i32 %A\n" 246 "}\n"); 247 // The cast types here aren't the same, so we cannot match an UMIN. 248 expectPattern({SPF_UNKNOWN, SPNB_NA, false}); 249 } 250 251 TEST(ValueTracking, GuaranteedToTransferExecutionToSuccessor) { 252 StringRef Assembly = 253 "declare void @nounwind_readonly(i32*) nounwind readonly " 254 "declare void @nounwind_argmemonly(i32*) nounwind argmemonly " 255 "declare void @throws_but_readonly(i32*) readonly " 256 "declare void @throws_but_argmemonly(i32*) argmemonly " 257 " " 258 "declare void @unknown(i32*) " 259 " " 260 "define void @f(i32* %p) { " 261 " call void @nounwind_readonly(i32* %p) " 262 " call void @nounwind_argmemonly(i32* %p) " 263 " call void @throws_but_readonly(i32* %p) " 264 " call void @throws_but_argmemonly(i32* %p) " 265 " call void @unknown(i32* %p) nounwind readonly " 266 " call void @unknown(i32* %p) nounwind argmemonly " 267 " call void @unknown(i32* %p) readonly " 268 " call void @unknown(i32* %p) argmemonly " 269 " ret void " 270 "} "; 271 272 LLVMContext Context; 273 SMDiagnostic Error; 274 auto M = parseAssemblyString(Assembly, Error, Context); 275 assert(M && "Bad assembly?"); 276 277 auto *F = M->getFunction("f"); 278 assert(F && "Bad assembly?"); 279 280 auto &BB = F->getEntryBlock(); 281 bool ExpectedAnswers[] = { 282 true, // call void @nounwind_readonly(i32* %p) 283 true, // call void @nounwind_argmemonly(i32* %p) 284 false, // call void @throws_but_readonly(i32* %p) 285 false, // call void @throws_but_argmemonly(i32* %p) 286 true, // call void @unknown(i32* %p) nounwind readonly 287 true, // call void @unknown(i32* %p) nounwind argmemonly 288 false, // call void @unknown(i32* %p) readonly 289 false, // call void @unknown(i32* %p) argmemonly 290 false, // ret void 291 }; 292 293 int Index = 0; 294 for (auto &I : BB) { 295 EXPECT_EQ(isGuaranteedToTransferExecutionToSuccessor(&I), 296 ExpectedAnswers[Index]) 297 << "Incorrect answer at instruction " << Index << " = " << I; 298 Index++; 299 } 300 } 301 302 TEST(ValueTracking, ComputeNumSignBits_PR32045) { 303 StringRef Assembly = "define i32 @f(i32 %a) { " 304 " %val = ashr i32 %a, -1 " 305 " ret i32 %val " 306 "} "; 307 308 LLVMContext Context; 309 SMDiagnostic Error; 310 auto M = parseAssemblyString(Assembly, Error, Context); 311 assert(M && "Bad assembly?"); 312 313 auto *F = M->getFunction("f"); 314 assert(F && "Bad assembly?"); 315 316 auto *RVal = 317 cast<ReturnInst>(F->getEntryBlock().getTerminator())->getOperand(0); 318 EXPECT_EQ(ComputeNumSignBits(RVal, M->getDataLayout()), 1u); 319 } 320 321 TEST(ValueTracking, ComputeKnownBits) { 322 StringRef Assembly = "define i32 @f(i32 %a, i32 %b) { " 323 " %ash = mul i32 %a, 8 " 324 " %aad = add i32 %ash, 7 " 325 " %aan = and i32 %aad, 4095 " 326 " %bsh = shl i32 %b, 4 " 327 " %bad = or i32 %bsh, 6 " 328 " %ban = and i32 %bad, 4095 " 329 " %mul = mul i32 %aan, %ban " 330 " ret i32 %mul " 331 "} "; 332 333 LLVMContext Context; 334 SMDiagnostic Error; 335 auto M = parseAssemblyString(Assembly, Error, Context); 336 assert(M && "Bad assembly?"); 337 338 auto *F = M->getFunction("f"); 339 assert(F && "Bad assembly?"); 340 341 auto *RVal = 342 cast<ReturnInst>(F->getEntryBlock().getTerminator())->getOperand(0); 343 auto Known = computeKnownBits(RVal, M->getDataLayout()); 344 ASSERT_FALSE(Known.hasConflict()); 345 EXPECT_EQ(Known.One.getZExtValue(), 10u); 346 EXPECT_EQ(Known.Zero.getZExtValue(), 4278190085u); 347 } 348 349 TEST(ValueTracking, ComputeKnownMulBits) { 350 StringRef Assembly = "define i32 @f(i32 %a, i32 %b) { " 351 " %aa = shl i32 %a, 5 " 352 " %bb = shl i32 %b, 5 " 353 " %aaa = or i32 %aa, 24 " 354 " %bbb = or i32 %bb, 28 " 355 " %mul = mul i32 %aaa, %bbb " 356 " ret i32 %mul " 357 "} "; 358 359 LLVMContext Context; 360 SMDiagnostic Error; 361 auto M = parseAssemblyString(Assembly, Error, Context); 362 assert(M && "Bad assembly?"); 363 364 auto *F = M->getFunction("f"); 365 assert(F && "Bad assembly?"); 366 367 auto *RVal = 368 cast<ReturnInst>(F->getEntryBlock().getTerminator())->getOperand(0); 369 auto Known = computeKnownBits(RVal, M->getDataLayout()); 370 ASSERT_FALSE(Known.hasConflict()); 371 EXPECT_EQ(Known.One.getZExtValue(), 32u); 372 EXPECT_EQ(Known.Zero.getZExtValue(), 95u); 373 } 374