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<NoFolder> IRB;
39
PatternMatchTest__anon63dab90c0111::PatternMatchTest40 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
TEST_F(PatternMatchTest,OneUse)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
TEST_F(PatternMatchTest,FloatingPointOrderedMin)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
TEST_F(PatternMatchTest,FloatingPointOrderedMax)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
TEST_F(PatternMatchTest,FloatingPointUnorderedMin)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
TEST_F(PatternMatchTest,FloatingPointUnorderedMax)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
TEST_F(PatternMatchTest,OverflowingBinOps)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