1 //===- IntegerDivision.cpp - Unit tests for the integer division code -----===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "llvm/Transforms/Utils/IntegerDivision.h"
10 #include "llvm/IR/BasicBlock.h"
11 #include "llvm/IR/Function.h"
12 #include "llvm/IR/GlobalValue.h"
13 #include "llvm/IR/IRBuilder.h"
14 #include "llvm/IR/Module.h"
15 #include "gtest/gtest.h"
16 
17 using namespace llvm;
18 
19 namespace {
20 
21 
22 TEST(IntegerDivision, SDiv) {
23   LLVMContext C;
24   Module M("test division", C);
25   IRBuilder<> Builder(C);
26 
27   SmallVector<Type*, 2> ArgTys(2, Builder.getInt32Ty());
28   Function *F = Function::Create(FunctionType::get(Builder.getInt32Ty(),
29                                                    ArgTys, false),
30                                  GlobalValue::ExternalLinkage, "F", &M);
31   assert(F->arg_size() == 2);
32 
33   BasicBlock *BB = BasicBlock::Create(C, "", F);
34   Builder.SetInsertPoint(BB);
35 
36   Function::arg_iterator AI = F->arg_begin();
37   Value *A = &*AI++;
38   Value *B = &*AI++;
39 
40   Value *Div = Builder.CreateSDiv(A, B);
41   EXPECT_TRUE(BB->front().getOpcode() == Instruction::SDiv);
42 
43   Value *Ret = Builder.CreateRet(Div);
44 
45   expandDivision(cast<BinaryOperator>(Div));
46   EXPECT_TRUE(BB->front().getOpcode() == Instruction::AShr);
47 
48   Instruction* Quotient = dyn_cast<Instruction>(cast<User>(Ret)->getOperand(0));
49   EXPECT_TRUE(Quotient && Quotient->getOpcode() == Instruction::Sub);
50 }
51 
52 TEST(IntegerDivision, UDiv) {
53   LLVMContext C;
54   Module M("test division", C);
55   IRBuilder<> Builder(C);
56 
57   SmallVector<Type*, 2> ArgTys(2, Builder.getInt32Ty());
58   Function *F = Function::Create(FunctionType::get(Builder.getInt32Ty(),
59                                                    ArgTys, false),
60                                  GlobalValue::ExternalLinkage, "F", &M);
61   assert(F->arg_size() == 2);
62 
63   BasicBlock *BB = BasicBlock::Create(C, "", F);
64   Builder.SetInsertPoint(BB);
65 
66   Function::arg_iterator AI = F->arg_begin();
67   Value *A = &*AI++;
68   Value *B = &*AI++;
69 
70   Value *Div = Builder.CreateUDiv(A, B);
71   EXPECT_TRUE(BB->front().getOpcode() == Instruction::UDiv);
72 
73   Value *Ret = Builder.CreateRet(Div);
74 
75   expandDivision(cast<BinaryOperator>(Div));
76   EXPECT_TRUE(BB->front().getOpcode() == Instruction::ICmp);
77 
78   Instruction* Quotient = dyn_cast<Instruction>(cast<User>(Ret)->getOperand(0));
79   EXPECT_TRUE(Quotient && Quotient->getOpcode() == Instruction::PHI);
80 }
81 
82 TEST(IntegerDivision, SRem) {
83   LLVMContext C;
84   Module M("test remainder", C);
85   IRBuilder<> Builder(C);
86 
87   SmallVector<Type*, 2> ArgTys(2, Builder.getInt32Ty());
88   Function *F = Function::Create(FunctionType::get(Builder.getInt32Ty(),
89                                                    ArgTys, false),
90                                  GlobalValue::ExternalLinkage, "F", &M);
91   assert(F->arg_size() == 2);
92 
93   BasicBlock *BB = BasicBlock::Create(C, "", F);
94   Builder.SetInsertPoint(BB);
95 
96   Function::arg_iterator AI = F->arg_begin();
97   Value *A = &*AI++;
98   Value *B = &*AI++;
99 
100   Value *Rem = Builder.CreateSRem(A, B);
101   EXPECT_TRUE(BB->front().getOpcode() == Instruction::SRem);
102 
103   Value *Ret = Builder.CreateRet(Rem);
104 
105   expandRemainder(cast<BinaryOperator>(Rem));
106   EXPECT_TRUE(BB->front().getOpcode() == Instruction::AShr);
107 
108   Instruction* Remainder = dyn_cast<Instruction>(cast<User>(Ret)->getOperand(0));
109   EXPECT_TRUE(Remainder && Remainder->getOpcode() == Instruction::Sub);
110 }
111 
112 TEST(IntegerDivision, URem) {
113   LLVMContext C;
114   Module M("test remainder", C);
115   IRBuilder<> Builder(C);
116 
117   SmallVector<Type*, 2> ArgTys(2, Builder.getInt32Ty());
118   Function *F = Function::Create(FunctionType::get(Builder.getInt32Ty(),
119                                                    ArgTys, false),
120                                  GlobalValue::ExternalLinkage, "F", &M);
121   assert(F->arg_size() == 2);
122 
123   BasicBlock *BB = BasicBlock::Create(C, "", F);
124   Builder.SetInsertPoint(BB);
125 
126   Function::arg_iterator AI = F->arg_begin();
127   Value *A = &*AI++;
128   Value *B = &*AI++;
129 
130   Value *Rem = Builder.CreateURem(A, B);
131   EXPECT_TRUE(BB->front().getOpcode() == Instruction::URem);
132 
133   Value *Ret = Builder.CreateRet(Rem);
134 
135   expandRemainder(cast<BinaryOperator>(Rem));
136   EXPECT_TRUE(BB->front().getOpcode() == Instruction::ICmp);
137 
138   Instruction* Remainder = dyn_cast<Instruction>(cast<User>(Ret)->getOperand(0));
139   EXPECT_TRUE(Remainder && Remainder->getOpcode() == Instruction::Sub);
140 }
141 
142 
143 TEST(IntegerDivision, SDiv64) {
144   LLVMContext C;
145   Module M("test division", C);
146   IRBuilder<> Builder(C);
147 
148   SmallVector<Type*, 2> ArgTys(2, Builder.getInt64Ty());
149   Function *F = Function::Create(FunctionType::get(Builder.getInt64Ty(),
150                                                    ArgTys, false),
151                                  GlobalValue::ExternalLinkage, "F", &M);
152   assert(F->arg_size() == 2);
153 
154   BasicBlock *BB = BasicBlock::Create(C, "", F);
155   Builder.SetInsertPoint(BB);
156 
157   Function::arg_iterator AI = F->arg_begin();
158   Value *A = &*AI++;
159   Value *B = &*AI++;
160 
161   Value *Div = Builder.CreateSDiv(A, B);
162   EXPECT_TRUE(BB->front().getOpcode() == Instruction::SDiv);
163 
164   Value *Ret = Builder.CreateRet(Div);
165 
166   expandDivision(cast<BinaryOperator>(Div));
167   EXPECT_TRUE(BB->front().getOpcode() == Instruction::AShr);
168 
169   Instruction* Quotient = dyn_cast<Instruction>(cast<User>(Ret)->getOperand(0));
170   EXPECT_TRUE(Quotient && Quotient->getOpcode() == Instruction::Sub);
171 }
172 
173 TEST(IntegerDivision, UDiv64) {
174   LLVMContext C;
175   Module M("test division", C);
176   IRBuilder<> Builder(C);
177 
178   SmallVector<Type*, 2> ArgTys(2, Builder.getInt64Ty());
179   Function *F = Function::Create(FunctionType::get(Builder.getInt64Ty(),
180                                                    ArgTys, false),
181                                  GlobalValue::ExternalLinkage, "F", &M);
182   assert(F->arg_size() == 2);
183 
184   BasicBlock *BB = BasicBlock::Create(C, "", F);
185   Builder.SetInsertPoint(BB);
186 
187   Function::arg_iterator AI = F->arg_begin();
188   Value *A = &*AI++;
189   Value *B = &*AI++;
190 
191   Value *Div = Builder.CreateUDiv(A, B);
192   EXPECT_TRUE(BB->front().getOpcode() == Instruction::UDiv);
193 
194   Value *Ret = Builder.CreateRet(Div);
195 
196   expandDivision(cast<BinaryOperator>(Div));
197   EXPECT_TRUE(BB->front().getOpcode() == Instruction::ICmp);
198 
199   Instruction* Quotient = dyn_cast<Instruction>(cast<User>(Ret)->getOperand(0));
200   EXPECT_TRUE(Quotient && Quotient->getOpcode() == Instruction::PHI);
201 }
202 
203 TEST(IntegerDivision, SRem64) {
204   LLVMContext C;
205   Module M("test remainder", C);
206   IRBuilder<> Builder(C);
207 
208   SmallVector<Type*, 2> ArgTys(2, Builder.getInt64Ty());
209   Function *F = Function::Create(FunctionType::get(Builder.getInt64Ty(),
210                                                    ArgTys, false),
211                                  GlobalValue::ExternalLinkage, "F", &M);
212   assert(F->arg_size() == 2);
213 
214   BasicBlock *BB = BasicBlock::Create(C, "", F);
215   Builder.SetInsertPoint(BB);
216 
217   Function::arg_iterator AI = F->arg_begin();
218   Value *A = &*AI++;
219   Value *B = &*AI++;
220 
221   Value *Rem = Builder.CreateSRem(A, B);
222   EXPECT_TRUE(BB->front().getOpcode() == Instruction::SRem);
223 
224   Value *Ret = Builder.CreateRet(Rem);
225 
226   expandRemainder(cast<BinaryOperator>(Rem));
227   EXPECT_TRUE(BB->front().getOpcode() == Instruction::AShr);
228 
229   Instruction* Remainder = dyn_cast<Instruction>(cast<User>(Ret)->getOperand(0));
230   EXPECT_TRUE(Remainder && Remainder->getOpcode() == Instruction::Sub);
231 }
232 
233 TEST(IntegerDivision, URem64) {
234   LLVMContext C;
235   Module M("test remainder", C);
236   IRBuilder<> Builder(C);
237 
238   SmallVector<Type*, 2> ArgTys(2, Builder.getInt64Ty());
239   Function *F = Function::Create(FunctionType::get(Builder.getInt64Ty(),
240                                                    ArgTys, false),
241                                  GlobalValue::ExternalLinkage, "F", &M);
242   assert(F->arg_size() == 2);
243 
244   BasicBlock *BB = BasicBlock::Create(C, "", F);
245   Builder.SetInsertPoint(BB);
246 
247   Function::arg_iterator AI = F->arg_begin();
248   Value *A = &*AI++;
249   Value *B = &*AI++;
250 
251   Value *Rem = Builder.CreateURem(A, B);
252   EXPECT_TRUE(BB->front().getOpcode() == Instruction::URem);
253 
254   Value *Ret = Builder.CreateRet(Rem);
255 
256   expandRemainder(cast<BinaryOperator>(Rem));
257   EXPECT_TRUE(BB->front().getOpcode() == Instruction::ICmp);
258 
259   Instruction* Remainder = dyn_cast<Instruction>(cast<User>(Ret)->getOperand(0));
260   EXPECT_TRUE(Remainder && Remainder->getOpcode() == Instruction::Sub);
261 }
262 
263 }
264