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
28using namespace llvm;
29using namespace llvm::PatternMatch;
30
31namespace {
32
33struct 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
48TEST_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
68TEST_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
107TEST_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
146TEST_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
185TEST_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
224TEST_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