1 //===---- llvm/unittest/IR/PatternMatch.cpp - PatternMatch unit 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/ADT/STLExtras.h" 11 #include "llvm/Analysis/ValueTracking.h" 12 #include "llvm/IR/BasicBlock.h" 13 #include "llvm/IR/Constants.h" 14 #include "llvm/IR/DataLayout.h" 15 #include "llvm/IR/DerivedTypes.h" 16 #include "llvm/IR/Function.h" 17 #include "llvm/IR/IRBuilder.h" 18 #include "llvm/IR/Instructions.h" 19 #include "llvm/IR/LLVMContext.h" 20 #include "llvm/IR/MDBuilder.h" 21 #include "llvm/IR/Module.h" 22 #include "llvm/IR/NoFolder.h" 23 #include "llvm/IR/Operator.h" 24 #include "llvm/IR/PatternMatch.h" 25 #include "llvm/IR/Type.h" 26 #include "gtest/gtest.h" 27 28 using namespace llvm; 29 using namespace llvm::PatternMatch; 30 31 namespace { 32 33 struct PatternMatchTest : ::testing::Test { 34 LLVMContext Ctx; 35 std::unique_ptr<Module> M; 36 Function *F; 37 BasicBlock *BB; 38 IRBuilder<true, NoFolder> IRB; 39 40 PatternMatchTest() 41 : M(new Module("PatternMatchTestModule", Ctx)), 42 F(Function::Create( 43 FunctionType::get(Type::getVoidTy(Ctx), /* IsVarArg */ false), 44 Function::ExternalLinkage, "f", M.get())), 45 BB(BasicBlock::Create(Ctx, "entry", F)), IRB(BB) {} 46 }; 47 48 TEST_F(PatternMatchTest, OneUse) { 49 // Build up a little tree of values: 50 // 51 // One = (1 + 2) + 42 52 // Two = One + 42 53 // Leaf = (Two + 8) + (Two + 13) 54 Value *One = IRB.CreateAdd(IRB.CreateAdd(IRB.getInt32(1), IRB.getInt32(2)), 55 IRB.getInt32(42)); 56 Value *Two = IRB.CreateAdd(One, IRB.getInt32(42)); 57 Value *Leaf = IRB.CreateAdd(IRB.CreateAdd(Two, IRB.getInt32(8)), 58 IRB.CreateAdd(Two, IRB.getInt32(13))); 59 Value *V; 60 61 EXPECT_TRUE(m_OneUse(m_Value(V)).match(One)); 62 EXPECT_EQ(One, V); 63 64 EXPECT_FALSE(m_OneUse(m_Value()).match(Two)); 65 EXPECT_FALSE(m_OneUse(m_Value()).match(Leaf)); 66 } 67 68 TEST_F(PatternMatchTest, FloatingPointOrderedMin) { 69 Type *FltTy = IRB.getFloatTy(); 70 Value *L = ConstantFP::get(FltTy, 1.0); 71 Value *R = ConstantFP::get(FltTy, 2.0); 72 Value *MatchL, *MatchR; 73 74 // Test OLT. 75 EXPECT_TRUE(m_OrdFMin(m_Value(MatchL), m_Value(MatchR)) 76 .match(IRB.CreateSelect(IRB.CreateFCmpOLT(L, R), L, R))); 77 EXPECT_EQ(L, MatchL); 78 EXPECT_EQ(R, MatchR); 79 80 // Test OLE. 81 EXPECT_TRUE(m_OrdFMin(m_Value(MatchL), m_Value(MatchR)) 82 .match(IRB.CreateSelect(IRB.CreateFCmpOLE(L, R), L, R))); 83 EXPECT_EQ(L, MatchL); 84 EXPECT_EQ(R, MatchR); 85 86 // Test no match on OGE. 87 EXPECT_FALSE(m_OrdFMin(m_Value(MatchL), m_Value(MatchR)) 88 .match(IRB.CreateSelect(IRB.CreateFCmpOGE(L, R), L, R))); 89 90 // Test no match on OGT. 91 EXPECT_FALSE(m_OrdFMin(m_Value(MatchL), m_Value(MatchR)) 92 .match(IRB.CreateSelect(IRB.CreateFCmpOGT(L, R), L, R))); 93 94 // Test match on OGE with inverted select. 95 EXPECT_TRUE(m_OrdFMin(m_Value(MatchL), m_Value(MatchR)) 96 .match(IRB.CreateSelect(IRB.CreateFCmpOGE(L, R), R, L))); 97 EXPECT_EQ(L, MatchL); 98 EXPECT_EQ(R, MatchR); 99 100 // Test match on OGT with inverted select. 101 EXPECT_TRUE(m_OrdFMin(m_Value(MatchL), m_Value(MatchR)) 102 .match(IRB.CreateSelect(IRB.CreateFCmpOGT(L, R), R, L))); 103 EXPECT_EQ(L, MatchL); 104 EXPECT_EQ(R, MatchR); 105 } 106 107 TEST_F(PatternMatchTest, FloatingPointOrderedMax) { 108 Type *FltTy = IRB.getFloatTy(); 109 Value *L = ConstantFP::get(FltTy, 1.0); 110 Value *R = ConstantFP::get(FltTy, 2.0); 111 Value *MatchL, *MatchR; 112 113 // Test OGT. 114 EXPECT_TRUE(m_OrdFMax(m_Value(MatchL), m_Value(MatchR)) 115 .match(IRB.CreateSelect(IRB.CreateFCmpOGT(L, R), L, R))); 116 EXPECT_EQ(L, MatchL); 117 EXPECT_EQ(R, MatchR); 118 119 // Test OGE. 120 EXPECT_TRUE(m_OrdFMax(m_Value(MatchL), m_Value(MatchR)) 121 .match(IRB.CreateSelect(IRB.CreateFCmpOGE(L, R), L, R))); 122 EXPECT_EQ(L, MatchL); 123 EXPECT_EQ(R, MatchR); 124 125 // Test no match on OLE. 126 EXPECT_FALSE(m_OrdFMax(m_Value(MatchL), m_Value(MatchR)) 127 .match(IRB.CreateSelect(IRB.CreateFCmpOLE(L, R), L, R))); 128 129 // Test no match on OLT. 130 EXPECT_FALSE(m_OrdFMax(m_Value(MatchL), m_Value(MatchR)) 131 .match(IRB.CreateSelect(IRB.CreateFCmpOLT(L, R), L, R))); 132 133 // Test match on OLE with inverted select. 134 EXPECT_TRUE(m_OrdFMax(m_Value(MatchL), m_Value(MatchR)) 135 .match(IRB.CreateSelect(IRB.CreateFCmpOLE(L, R), R, L))); 136 EXPECT_EQ(L, MatchL); 137 EXPECT_EQ(R, MatchR); 138 139 // Test match on OLT with inverted select. 140 EXPECT_TRUE(m_OrdFMax(m_Value(MatchL), m_Value(MatchR)) 141 .match(IRB.CreateSelect(IRB.CreateFCmpOLT(L, R), R, L))); 142 EXPECT_EQ(L, MatchL); 143 EXPECT_EQ(R, MatchR); 144 } 145 146 TEST_F(PatternMatchTest, FloatingPointUnorderedMin) { 147 Type *FltTy = IRB.getFloatTy(); 148 Value *L = ConstantFP::get(FltTy, 1.0); 149 Value *R = ConstantFP::get(FltTy, 2.0); 150 Value *MatchL, *MatchR; 151 152 // Test ULT. 153 EXPECT_TRUE(m_UnordFMin(m_Value(MatchL), m_Value(MatchR)) 154 .match(IRB.CreateSelect(IRB.CreateFCmpULT(L, R), L, R))); 155 EXPECT_EQ(L, MatchL); 156 EXPECT_EQ(R, MatchR); 157 158 // Test ULE. 159 EXPECT_TRUE(m_UnordFMin(m_Value(MatchL), m_Value(MatchR)) 160 .match(IRB.CreateSelect(IRB.CreateFCmpULE(L, R), L, R))); 161 EXPECT_EQ(L, MatchL); 162 EXPECT_EQ(R, MatchR); 163 164 // Test no match on UGE. 165 EXPECT_FALSE(m_UnordFMin(m_Value(MatchL), m_Value(MatchR)) 166 .match(IRB.CreateSelect(IRB.CreateFCmpUGE(L, R), L, R))); 167 168 // Test no match on UGT. 169 EXPECT_FALSE(m_UnordFMin(m_Value(MatchL), m_Value(MatchR)) 170 .match(IRB.CreateSelect(IRB.CreateFCmpUGT(L, R), L, R))); 171 172 // Test match on UGE with inverted select. 173 EXPECT_TRUE(m_UnordFMin(m_Value(MatchL), m_Value(MatchR)) 174 .match(IRB.CreateSelect(IRB.CreateFCmpUGE(L, R), R, L))); 175 EXPECT_EQ(L, MatchL); 176 EXPECT_EQ(R, MatchR); 177 178 // Test match on UGT with inverted select. 179 EXPECT_TRUE(m_UnordFMin(m_Value(MatchL), m_Value(MatchR)) 180 .match(IRB.CreateSelect(IRB.CreateFCmpUGT(L, R), R, L))); 181 EXPECT_EQ(L, MatchL); 182 EXPECT_EQ(R, MatchR); 183 } 184 185 TEST_F(PatternMatchTest, FloatingPointUnorderedMax) { 186 Type *FltTy = IRB.getFloatTy(); 187 Value *L = ConstantFP::get(FltTy, 1.0); 188 Value *R = ConstantFP::get(FltTy, 2.0); 189 Value *MatchL, *MatchR; 190 191 // Test UGT. 192 EXPECT_TRUE(m_UnordFMax(m_Value(MatchL), m_Value(MatchR)) 193 .match(IRB.CreateSelect(IRB.CreateFCmpUGT(L, R), L, R))); 194 EXPECT_EQ(L, MatchL); 195 EXPECT_EQ(R, MatchR); 196 197 // Test UGE. 198 EXPECT_TRUE(m_UnordFMax(m_Value(MatchL), m_Value(MatchR)) 199 .match(IRB.CreateSelect(IRB.CreateFCmpUGE(L, R), L, R))); 200 EXPECT_EQ(L, MatchL); 201 EXPECT_EQ(R, MatchR); 202 203 // Test no match on ULE. 204 EXPECT_FALSE(m_UnordFMax(m_Value(MatchL), m_Value(MatchR)) 205 .match(IRB.CreateSelect(IRB.CreateFCmpULE(L, R), L, R))); 206 207 // Test no match on ULT. 208 EXPECT_FALSE(m_UnordFMax(m_Value(MatchL), m_Value(MatchR)) 209 .match(IRB.CreateSelect(IRB.CreateFCmpULT(L, R), L, R))); 210 211 // Test match on ULE with inverted select. 212 EXPECT_TRUE(m_UnordFMax(m_Value(MatchL), m_Value(MatchR)) 213 .match(IRB.CreateSelect(IRB.CreateFCmpULE(L, R), R, L))); 214 EXPECT_EQ(L, MatchL); 215 EXPECT_EQ(R, MatchR); 216 217 // Test match on ULT with inverted select. 218 EXPECT_TRUE(m_UnordFMax(m_Value(MatchL), m_Value(MatchR)) 219 .match(IRB.CreateSelect(IRB.CreateFCmpULT(L, R), R, L))); 220 EXPECT_EQ(L, MatchL); 221 EXPECT_EQ(R, MatchR); 222 } 223 224 TEST_F(PatternMatchTest, OverflowingBinOps) { 225 Value *L = IRB.getInt32(1); 226 Value *R = IRB.getInt32(2); 227 Value *MatchL, *MatchR; 228 229 EXPECT_TRUE( 230 m_NSWAdd(m_Value(MatchL), m_Value(MatchR)).match(IRB.CreateNSWAdd(L, R))); 231 EXPECT_EQ(L, MatchL); 232 EXPECT_EQ(R, MatchR); 233 MatchL = MatchR = nullptr; 234 EXPECT_TRUE( 235 m_NSWSub(m_Value(MatchL), m_Value(MatchR)).match(IRB.CreateNSWSub(L, R))); 236 EXPECT_EQ(L, MatchL); 237 EXPECT_EQ(R, MatchR); 238 MatchL = MatchR = nullptr; 239 EXPECT_TRUE( 240 m_NSWMul(m_Value(MatchL), m_Value(MatchR)).match(IRB.CreateNSWMul(L, R))); 241 EXPECT_EQ(L, MatchL); 242 EXPECT_EQ(R, MatchR); 243 MatchL = MatchR = nullptr; 244 EXPECT_TRUE(m_NSWShl(m_Value(MatchL), m_Value(MatchR)).match( 245 IRB.CreateShl(L, R, "", /* NUW */ false, /* NSW */ true))); 246 EXPECT_EQ(L, MatchL); 247 EXPECT_EQ(R, MatchR); 248 249 EXPECT_TRUE( 250 m_NUWAdd(m_Value(MatchL), m_Value(MatchR)).match(IRB.CreateNUWAdd(L, R))); 251 EXPECT_EQ(L, MatchL); 252 EXPECT_EQ(R, MatchR); 253 MatchL = MatchR = nullptr; 254 EXPECT_TRUE( 255 m_NUWSub(m_Value(MatchL), m_Value(MatchR)).match(IRB.CreateNUWSub(L, R))); 256 EXPECT_EQ(L, MatchL); 257 EXPECT_EQ(R, MatchR); 258 MatchL = MatchR = nullptr; 259 EXPECT_TRUE( 260 m_NUWMul(m_Value(MatchL), m_Value(MatchR)).match(IRB.CreateNUWMul(L, R))); 261 EXPECT_EQ(L, MatchL); 262 EXPECT_EQ(R, MatchR); 263 MatchL = MatchR = nullptr; 264 EXPECT_TRUE(m_NUWShl(m_Value(MatchL), m_Value(MatchR)).match( 265 IRB.CreateShl(L, R, "", /* NUW */ true, /* NSW */ false))); 266 EXPECT_EQ(L, MatchL); 267 EXPECT_EQ(R, MatchR); 268 269 EXPECT_FALSE(m_NSWAdd(m_Value(), m_Value()).match(IRB.CreateAdd(L, R))); 270 EXPECT_FALSE(m_NSWAdd(m_Value(), m_Value()).match(IRB.CreateNUWAdd(L, R))); 271 EXPECT_FALSE(m_NSWAdd(m_Value(), m_Value()).match(IRB.CreateNSWSub(L, R))); 272 EXPECT_FALSE(m_NSWSub(m_Value(), m_Value()).match(IRB.CreateSub(L, R))); 273 EXPECT_FALSE(m_NSWSub(m_Value(), m_Value()).match(IRB.CreateNUWSub(L, R))); 274 EXPECT_FALSE(m_NSWSub(m_Value(), m_Value()).match(IRB.CreateNSWAdd(L, R))); 275 EXPECT_FALSE(m_NSWMul(m_Value(), m_Value()).match(IRB.CreateMul(L, R))); 276 EXPECT_FALSE(m_NSWMul(m_Value(), m_Value()).match(IRB.CreateNUWMul(L, R))); 277 EXPECT_FALSE(m_NSWMul(m_Value(), m_Value()).match(IRB.CreateNSWAdd(L, R))); 278 EXPECT_FALSE(m_NSWShl(m_Value(), m_Value()).match(IRB.CreateShl(L, R))); 279 EXPECT_FALSE(m_NSWShl(m_Value(), m_Value()).match( 280 IRB.CreateShl(L, R, "", /* NUW */ true, /* NSW */ false))); 281 EXPECT_FALSE(m_NSWShl(m_Value(), m_Value()).match(IRB.CreateNSWAdd(L, R))); 282 283 EXPECT_FALSE(m_NUWAdd(m_Value(), m_Value()).match(IRB.CreateAdd(L, R))); 284 EXPECT_FALSE(m_NUWAdd(m_Value(), m_Value()).match(IRB.CreateNSWAdd(L, R))); 285 EXPECT_FALSE(m_NUWAdd(m_Value(), m_Value()).match(IRB.CreateNUWSub(L, R))); 286 EXPECT_FALSE(m_NUWSub(m_Value(), m_Value()).match(IRB.CreateSub(L, R))); 287 EXPECT_FALSE(m_NUWSub(m_Value(), m_Value()).match(IRB.CreateNSWSub(L, R))); 288 EXPECT_FALSE(m_NUWSub(m_Value(), m_Value()).match(IRB.CreateNUWAdd(L, R))); 289 EXPECT_FALSE(m_NUWMul(m_Value(), m_Value()).match(IRB.CreateMul(L, R))); 290 EXPECT_FALSE(m_NUWMul(m_Value(), m_Value()).match(IRB.CreateNSWMul(L, R))); 291 EXPECT_FALSE(m_NUWMul(m_Value(), m_Value()).match(IRB.CreateNUWAdd(L, R))); 292 EXPECT_FALSE(m_NUWShl(m_Value(), m_Value()).match(IRB.CreateShl(L, R))); 293 EXPECT_FALSE(m_NUWShl(m_Value(), m_Value()).match( 294 IRB.CreateShl(L, R, "", /* NUW */ false, /* NSW */ true))); 295 EXPECT_FALSE(m_NUWShl(m_Value(), m_Value()).match(IRB.CreateNUWAdd(L, R))); 296 } 297 298 } // anonymous namespace. 299
