1 //===---- llvm/unittest/IR/PatternMatch.cpp - PatternMatch unit tests ----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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"
29 using namespace llvm::PatternMatch;
33 struct PatternMatchTest : ::testing::Test {
35 std::unique_ptr<Module> M;
38 IRBuilder<true, NoFolder> IRB;
41 : M(new Module("PatternMatchTestModule", Ctx)),
43 FunctionType::get(Type::getVoidTy(Ctx), /* IsVarArg */ false),
44 Function::ExternalLinkage, "f", M.get())),
45 BB(BasicBlock::Create(Ctx, "entry", F)), IRB(BB) {}
48 TEST_F(PatternMatchTest, OneUse) {
49 // Build up a little tree of values:
53 // Leaf = (Two + 8) + (Two + 13)
54 Value *One = IRB.CreateAdd(IRB.CreateAdd(IRB.getInt32(1), IRB.getInt32(2)),
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)));
61 EXPECT_TRUE(m_OneUse(m_Value(V)).match(One));
64 EXPECT_FALSE(m_OneUse(m_Value()).match(Two));
65 EXPECT_FALSE(m_OneUse(m_Value()).match(Leaf));
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;
75 EXPECT_TRUE(m_OrdFMin(m_Value(MatchL), m_Value(MatchR))
76 .match(IRB.CreateSelect(IRB.CreateFCmpOLT(L, R), L, R)));
81 EXPECT_TRUE(m_OrdFMin(m_Value(MatchL), m_Value(MatchR))
82 .match(IRB.CreateSelect(IRB.CreateFCmpOLE(L, R), L, R)));
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)));
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)));
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)));
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);
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;
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);
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);
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)));
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)));
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);
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);
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;
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);
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);
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)));
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)));
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);
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);
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;
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);
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);
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)));
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)));
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);
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);
224 TEST_F(PatternMatchTest, OverflowingBinOps) {
225 Value *L = IRB.getInt32(1);
226 Value *R = IRB.getInt32(2);
227 Value *MatchL, *MatchR;
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;
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;
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);
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;
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;
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);
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)));
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)));
298 } // anonymous namespace.