unittests/Analysis/ValueTrackingTest.cpp

   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 }