1 //===- ScalarEvolutionsTest.cpp - ScalarEvolution 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/Analysis/ScalarEvolutionExpander.h"
11 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
12 #include "llvm/Analysis/AssumptionCache.h"
13 #include "llvm/Analysis/LoopInfo.h"
14 #include "llvm/Analysis/TargetLibraryInfo.h"
15 #include "llvm/ADT/SmallVector.h"
16 #include "llvm/Analysis/LoopInfo.h"
17 #include "llvm/AsmParser/Parser.h"
18 #include "llvm/IR/Constants.h"
19 #include "llvm/IR/Dominators.h"
20 #include "llvm/IR/GlobalVariable.h"
21 #include "llvm/IR/InstIterator.h"
22 #include "llvm/IR/LLVMContext.h"
23 #include "llvm/IR/Module.h"
24 #include "llvm/IR/LegacyPassManager.h"
25 #include "llvm/IR/Verifier.h"
26 #include "llvm/Support/SourceMgr.h"
27 #include "gtest/gtest.h"
28 
29 namespace llvm {
30 namespace {
31 
32 // We use this fixture to ensure that we clean up ScalarEvolution before
33 // deleting the PassManager.
34 class ScalarEvolutionsTest : public testing::Test {
35 protected:
36   LLVMContext Context;
37   Module M;
38   TargetLibraryInfoImpl TLII;
39   TargetLibraryInfo TLI;
40 
41   std::unique_ptr<AssumptionCache> AC;
42   std::unique_ptr<DominatorTree> DT;
43   std::unique_ptr<LoopInfo> LI;
44 
45   ScalarEvolutionsTest() : M("", Context), TLII(), TLI(TLII) {}
46 
47   ScalarEvolution buildSE(Function &F) {
48     AC.reset(new AssumptionCache(F));
49     DT.reset(new DominatorTree(F));
50     LI.reset(new LoopInfo(*DT));
51     return ScalarEvolution(F, TLI, *AC, *DT, *LI);
52   }
53 
54   void runWithFunctionAndSE(
55       Module &M, StringRef FuncName,
56       function_ref<void(Function &F, ScalarEvolution &SE)> Test) {
57     auto *F = M.getFunction(FuncName);
58     ASSERT_NE(F, nullptr) << "Could not find " << FuncName;
59     ScalarEvolution SE = buildSE(*F);
60     Test(*F, SE);
61   }
62 };
63 
64 TEST_F(ScalarEvolutionsTest, SCEVUnknownRAUW) {
65   FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context),
66                                               std::vector<Type *>(), false);
67   Function *F = cast<Function>(M.getOrInsertFunction("f", FTy));
68   BasicBlock *BB = BasicBlock::Create(Context, "entry", F);
69   ReturnInst::Create(Context, nullptr, BB);
70 
71   Type *Ty = Type::getInt1Ty(Context);
72   Constant *Init = Constant::getNullValue(Ty);
73   Value *V0 = new GlobalVariable(M, Ty, false, GlobalValue::ExternalLinkage, Init, "V0");
74   Value *V1 = new GlobalVariable(M, Ty, false, GlobalValue::ExternalLinkage, Init, "V1");
75   Value *V2 = new GlobalVariable(M, Ty, false, GlobalValue::ExternalLinkage, Init, "V2");
76 
77   ScalarEvolution SE = buildSE(*F);
78 
79   const SCEV *S0 = SE.getSCEV(V0);
80   const SCEV *S1 = SE.getSCEV(V1);
81   const SCEV *S2 = SE.getSCEV(V2);
82 
83   const SCEV *P0 = SE.getAddExpr(S0, S0);
84   const SCEV *P1 = SE.getAddExpr(S1, S1);
85   const SCEV *P2 = SE.getAddExpr(S2, S2);
86 
87   const SCEVMulExpr *M0 = cast<SCEVMulExpr>(P0);
88   const SCEVMulExpr *M1 = cast<SCEVMulExpr>(P1);
89   const SCEVMulExpr *M2 = cast<SCEVMulExpr>(P2);
90 
91   EXPECT_EQ(cast<SCEVConstant>(M0->getOperand(0))->getValue()->getZExtValue(),
92             2u);
93   EXPECT_EQ(cast<SCEVConstant>(M1->getOperand(0))->getValue()->getZExtValue(),
94             2u);
95   EXPECT_EQ(cast<SCEVConstant>(M2->getOperand(0))->getValue()->getZExtValue(),
96             2u);
97 
98   // Before the RAUWs, these are all pointing to separate values.
99   EXPECT_EQ(cast<SCEVUnknown>(M0->getOperand(1))->getValue(), V0);
100   EXPECT_EQ(cast<SCEVUnknown>(M1->getOperand(1))->getValue(), V1);
101   EXPECT_EQ(cast<SCEVUnknown>(M2->getOperand(1))->getValue(), V2);
102 
103   // Do some RAUWs.
104   V2->replaceAllUsesWith(V1);
105   V1->replaceAllUsesWith(V0);
106 
107   // After the RAUWs, these should all be pointing to V0.
108   EXPECT_EQ(cast<SCEVUnknown>(M0->getOperand(1))->getValue(), V0);
109   EXPECT_EQ(cast<SCEVUnknown>(M1->getOperand(1))->getValue(), V0);
110   EXPECT_EQ(cast<SCEVUnknown>(M2->getOperand(1))->getValue(), V0);
111 }
112 
113 TEST_F(ScalarEvolutionsTest, SCEVMultiplyAddRecs) {
114   Type *Ty = Type::getInt32Ty(Context);
115   SmallVector<Type *, 10> Types;
116   Types.append(10, Ty);
117   FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), Types, false);
118   Function *F = cast<Function>(M.getOrInsertFunction("f", FTy));
119   BasicBlock *BB = BasicBlock::Create(Context, "entry", F);
120   ReturnInst::Create(Context, nullptr, BB);
121 
122   ScalarEvolution SE = buildSE(*F);
123 
124   // It's possible to produce an empty loop through the default constructor,
125   // but you can't add any blocks to it without a LoopInfo pass.
126   Loop L;
127   const_cast<std::vector<BasicBlock*>&>(L.getBlocks()).push_back(BB);
128 
129   Function::arg_iterator AI = F->arg_begin();
130   SmallVector<const SCEV *, 5> A;
131   A.push_back(SE.getSCEV(&*AI++));
132   A.push_back(SE.getSCEV(&*AI++));
133   A.push_back(SE.getSCEV(&*AI++));
134   A.push_back(SE.getSCEV(&*AI++));
135   A.push_back(SE.getSCEV(&*AI++));
136   const SCEV *A_rec = SE.getAddRecExpr(A, &L, SCEV::FlagAnyWrap);
137 
138   SmallVector<const SCEV *, 5> B;
139   B.push_back(SE.getSCEV(&*AI++));
140   B.push_back(SE.getSCEV(&*AI++));
141   B.push_back(SE.getSCEV(&*AI++));
142   B.push_back(SE.getSCEV(&*AI++));
143   B.push_back(SE.getSCEV(&*AI++));
144   const SCEV *B_rec = SE.getAddRecExpr(B, &L, SCEV::FlagAnyWrap);
145 
146   /* Spot check that we perform this transformation:
147      {A0,+,A1,+,A2,+,A3,+,A4} * {B0,+,B1,+,B2,+,B3,+,B4} =
148      {A0*B0,+,
149       A1*B0 + A0*B1 + A1*B1,+,
150       A2*B0 + 2A1*B1 + A0*B2 + 2A2*B1 + 2A1*B2 + A2*B2,+,
151       A3*B0 + 3A2*B1 + 3A1*B2 + A0*B3 + 3A3*B1 + 6A2*B2 + 3A1*B3 + 3A3*B2 +
152         3A2*B3 + A3*B3,+,
153       A4*B0 + 4A3*B1 + 6A2*B2 + 4A1*B3 + A0*B4 + 4A4*B1 + 12A3*B2 + 12A2*B3 +
154         4A1*B4 + 6A4*B2 + 12A3*B3 + 6A2*B4 + 4A4*B3 + 4A3*B4 + A4*B4,+,
155       5A4*B1 + 10A3*B2 + 10A2*B3 + 5A1*B4 + 20A4*B2 + 30A3*B3 + 20A2*B4 +
156         30A4*B3 + 30A3*B4 + 20A4*B4,+,
157       15A4*B2 + 20A3*B3 + 15A2*B4 + 60A4*B3 + 60A3*B4 + 90A4*B4,+,
158       35A4*B3 + 35A3*B4 + 140A4*B4,+,
159       70A4*B4}
160   */
161 
162   const SCEVAddRecExpr *Product =
163       dyn_cast<SCEVAddRecExpr>(SE.getMulExpr(A_rec, B_rec));
164   ASSERT_TRUE(Product);
165   ASSERT_EQ(Product->getNumOperands(), 9u);
166 
167   SmallVector<const SCEV *, 16> Sum;
168   Sum.push_back(SE.getMulExpr(A[0], B[0]));
169   EXPECT_EQ(Product->getOperand(0), SE.getAddExpr(Sum));
170   Sum.clear();
171 
172   // SCEV produces different an equal but different expression for these.
173   // Re-enable when PR11052 is fixed.
174 #if 0
175   Sum.push_back(SE.getMulExpr(A[1], B[0]));
176   Sum.push_back(SE.getMulExpr(A[0], B[1]));
177   Sum.push_back(SE.getMulExpr(A[1], B[1]));
178   EXPECT_EQ(Product->getOperand(1), SE.getAddExpr(Sum));
179   Sum.clear();
180 
181   Sum.push_back(SE.getMulExpr(A[2], B[0]));
182   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 2), A[1], B[1]));
183   Sum.push_back(SE.getMulExpr(A[0], B[2]));
184   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 2), A[2], B[1]));
185   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 2), A[1], B[2]));
186   Sum.push_back(SE.getMulExpr(A[2], B[2]));
187   EXPECT_EQ(Product->getOperand(2), SE.getAddExpr(Sum));
188   Sum.clear();
189 
190   Sum.push_back(SE.getMulExpr(A[3], B[0]));
191   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 3), A[2], B[1]));
192   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 3), A[1], B[2]));
193   Sum.push_back(SE.getMulExpr(A[0], B[3]));
194   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 3), A[3], B[1]));
195   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 6), A[2], B[2]));
196   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 3), A[1], B[3]));
197   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 3), A[3], B[2]));
198   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 3), A[2], B[3]));
199   Sum.push_back(SE.getMulExpr(A[3], B[3]));
200   EXPECT_EQ(Product->getOperand(3), SE.getAddExpr(Sum));
201   Sum.clear();
202 
203   Sum.push_back(SE.getMulExpr(A[4], B[0]));
204   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 4), A[3], B[1]));
205   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 6), A[2], B[2]));
206   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 4), A[1], B[3]));
207   Sum.push_back(SE.getMulExpr(A[0], B[4]));
208   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 4), A[4], B[1]));
209   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 12), A[3], B[2]));
210   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 12), A[2], B[3]));
211   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 4), A[1], B[4]));
212   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 6), A[4], B[2]));
213   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 12), A[3], B[3]));
214   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 6), A[2], B[4]));
215   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 4), A[4], B[3]));
216   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 4), A[3], B[4]));
217   Sum.push_back(SE.getMulExpr(A[4], B[4]));
218   EXPECT_EQ(Product->getOperand(4), SE.getAddExpr(Sum));
219   Sum.clear();
220 
221   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 5), A[4], B[1]));
222   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 10), A[3], B[2]));
223   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 10), A[2], B[3]));
224   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 5), A[1], B[4]));
225   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 20), A[4], B[2]));
226   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 30), A[3], B[3]));
227   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 20), A[2], B[4]));
228   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 30), A[4], B[3]));
229   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 30), A[3], B[4]));
230   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 20), A[4], B[4]));
231   EXPECT_EQ(Product->getOperand(5), SE.getAddExpr(Sum));
232   Sum.clear();
233 
234   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 15), A[4], B[2]));
235   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 20), A[3], B[3]));
236   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 15), A[2], B[4]));
237   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 60), A[4], B[3]));
238   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 60), A[3], B[4]));
239   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 90), A[4], B[4]));
240   EXPECT_EQ(Product->getOperand(6), SE.getAddExpr(Sum));
241   Sum.clear();
242 
243   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 35), A[4], B[3]));
244   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 35), A[3], B[4]));
245   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 140), A[4], B[4]));
246   EXPECT_EQ(Product->getOperand(7), SE.getAddExpr(Sum));
247   Sum.clear();
248 #endif
249 
250   Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 70), A[4], B[4]));
251   EXPECT_EQ(Product->getOperand(8), SE.getAddExpr(Sum));
252 }
253 
254 TEST_F(ScalarEvolutionsTest, SimplifiedPHI) {
255   FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context),
256                                               std::vector<Type *>(), false);
257   Function *F = cast<Function>(M.getOrInsertFunction("f", FTy));
258   BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);
259   BasicBlock *LoopBB = BasicBlock::Create(Context, "loop", F);
260   BasicBlock *ExitBB = BasicBlock::Create(Context, "exit", F);
261   BranchInst::Create(LoopBB, EntryBB);
262   BranchInst::Create(LoopBB, ExitBB, UndefValue::get(Type::getInt1Ty(Context)),
263                      LoopBB);
264   ReturnInst::Create(Context, nullptr, ExitBB);
265   auto *Ty = Type::getInt32Ty(Context);
266   auto *PN = PHINode::Create(Ty, 2, "", &*LoopBB->begin());
267   PN->addIncoming(Constant::getNullValue(Ty), EntryBB);
268   PN->addIncoming(UndefValue::get(Ty), LoopBB);
269   ScalarEvolution SE = buildSE(*F);
270   auto *S1 = SE.getSCEV(PN);
271   auto *S2 = SE.getSCEV(PN);
272   auto *ZeroConst = SE.getConstant(Ty, 0);
273 
274   // At some point, only the first call to getSCEV returned the simplified
275   // SCEVConstant and later calls just returned a SCEVUnknown referencing the
276   // PHI node.
277   EXPECT_EQ(S1, ZeroConst);
278   EXPECT_EQ(S1, S2);
279 }
280 
281 TEST_F(ScalarEvolutionsTest, ExpandPtrTypeSCEV) {
282   // It is to test the fix for PR30213. It exercises the branch in scev
283   // expansion when the value in ValueOffsetPair is a ptr and the offset
284   // is not divisible by the elem type size of value.
285   auto *I8Ty = Type::getInt8Ty(Context);
286   auto *I8PtrTy = Type::getInt8PtrTy(Context);
287   auto *I32Ty = Type::getInt32Ty(Context);
288   auto *I32PtrTy = Type::getInt32PtrTy(Context);
289   FunctionType *FTy =
290       FunctionType::get(Type::getVoidTy(Context), std::vector<Type *>(), false);
291   Function *F = cast<Function>(M.getOrInsertFunction("f", FTy));
292   BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);
293   BasicBlock *LoopBB = BasicBlock::Create(Context, "loop", F);
294   BasicBlock *ExitBB = BasicBlock::Create(Context, "exit", F);
295   BranchInst::Create(LoopBB, EntryBB);
296   ReturnInst::Create(Context, nullptr, ExitBB);
297 
298   // loop:                            ; preds = %loop, %entry
299   //   %alloca = alloca i32
300   //   %gep0 = getelementptr i32, i32* %alloca, i32 1
301   //   %bitcast1 = bitcast i32* %gep0 to i8*
302   //   %gep1 = getelementptr i8, i8* %bitcast1, i32 1
303   //   %gep2 = getelementptr i8, i8* undef, i32 1
304   //   %cmp = icmp ult i8* undef, %bitcast1
305   //   %select = select i1 %cmp, i8* %gep1, i8* %gep2
306   //   %bitcast2 = bitcast i8* %select to i32*
307   //   br i1 undef, label %loop, label %exit
308 
309   BranchInst *Br = BranchInst::Create(
310       LoopBB, ExitBB, UndefValue::get(Type::getInt1Ty(Context)), LoopBB);
311   AllocaInst *Alloca = new AllocaInst(I32Ty, "alloca", Br);
312   ConstantInt *Ci32 = ConstantInt::get(Context, APInt(32, 1));
313   GetElementPtrInst *Gep0 =
314       GetElementPtrInst::Create(I32Ty, Alloca, Ci32, "gep0", Br);
315   CastInst *CastA =
316       CastInst::CreateBitOrPointerCast(Gep0, I8PtrTy, "bitcast1", Br);
317   GetElementPtrInst *Gep1 =
318       GetElementPtrInst::Create(I8Ty, CastA, Ci32, "gep1", Br);
319   GetElementPtrInst *Gep2 = GetElementPtrInst::Create(
320       I8Ty, UndefValue::get(I8PtrTy), Ci32, "gep2", Br);
321   CmpInst *Cmp = CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_ULT,
322                                  UndefValue::get(I8PtrTy), CastA, "cmp", Br);
323   SelectInst *Sel = SelectInst::Create(Cmp, Gep1, Gep2, "select", Br);
324   CastInst *CastB =
325       CastInst::CreateBitOrPointerCast(Sel, I32PtrTy, "bitcast2", Br);
326 
327   ScalarEvolution SE = buildSE(*F);
328   auto *S = SE.getSCEV(CastB);
329   SCEVExpander Exp(SE, M.getDataLayout(), "expander");
330   Value *V =
331       Exp.expandCodeFor(cast<SCEVAddExpr>(S)->getOperand(1), nullptr, Br);
332 
333   // Expect the expansion code contains:
334   //   %0 = bitcast i32* %bitcast2 to i8*
335   //   %uglygep = getelementptr i8, i8* %0, i64 -1
336   //   %1 = bitcast i8* %uglygep to i32*
337   EXPECT_TRUE(isa<BitCastInst>(V));
338   Instruction *Gep = cast<Instruction>(V)->getPrevNode();
339   EXPECT_TRUE(isa<GetElementPtrInst>(Gep));
340   EXPECT_TRUE(isa<ConstantInt>(Gep->getOperand(1)));
341   EXPECT_EQ(cast<ConstantInt>(Gep->getOperand(1))->getSExtValue(), -1);
342   EXPECT_TRUE(isa<BitCastInst>(Gep->getPrevNode()));
343 }
344 
345 static Instruction *getInstructionByName(Function &F, StringRef Name) {
346   for (auto &I : instructions(F))
347     if (I.getName() == Name)
348       return &I;
349   llvm_unreachable("Expected to find instruction!");
350 }
351 
352 TEST_F(ScalarEvolutionsTest, CommutativeExprOperandOrder) {
353   LLVMContext C;
354   SMDiagnostic Err;
355   std::unique_ptr<Module> M = parseAssemblyString(
356       "target datalayout = \"e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128\" "
357       " "
358       "@var_0 = external global i32, align 4"
359       "@var_1 = external global i32, align 4"
360       "@var_2 = external global i32, align 4"
361       " "
362       "declare i32 @unknown(i32, i32, i32)"
363       " "
364       "define void @f_1(i8* nocapture %arr, i32 %n, i32* %A, i32* %B) "
365       "    local_unnamed_addr { "
366       "entry: "
367       "  %entrycond = icmp sgt i32 %n, 0 "
368       "  br i1 %entrycond, label %loop.ph, label %for.end "
369       " "
370       "loop.ph: "
371       "  %a = load i32, i32* %A, align 4 "
372       "  %b = load i32, i32* %B, align 4 "
373       "  %mul = mul nsw i32 %b, %a "
374       "  %iv0.init = getelementptr inbounds i8, i8* %arr, i32 %mul "
375       "  br label %loop "
376       " "
377       "loop: "
378       "  %iv0 = phi i8* [ %iv0.inc, %loop ], [ %iv0.init, %loop.ph ] "
379       "  %iv1 = phi i32 [ %iv1.inc, %loop ], [ 0, %loop.ph ] "
380       "  %conv = trunc i32 %iv1 to i8 "
381       "  store i8 %conv, i8* %iv0, align 1 "
382       "  %iv0.inc = getelementptr inbounds i8, i8* %iv0, i32 %b "
383       "  %iv1.inc = add nuw nsw i32 %iv1, 1 "
384       "  %exitcond = icmp eq i32 %iv1.inc, %n "
385       "  br i1 %exitcond, label %for.end.loopexit, label %loop "
386       " "
387       "for.end.loopexit: "
388       "  br label %for.end "
389       " "
390       "for.end: "
391       "  ret void "
392       "} "
393       " "
394       "define void @f_2(i32* %X, i32* %Y, i32* %Z) { "
395       "  %x = load i32, i32* %X "
396       "  %y = load i32, i32* %Y "
397       "  %z = load i32, i32* %Z "
398       "  ret void "
399       "} "
400       " "
401       "define void @f_3() { "
402       "  %x = load i32, i32* @var_0"
403       "  %y = load i32, i32* @var_1"
404       "  %z = load i32, i32* @var_2"
405       "  ret void"
406       "} "
407       " "
408       "define void @f_4(i32 %a, i32 %b, i32 %c) { "
409       "  %x = call i32 @unknown(i32 %a, i32 %b, i32 %c)"
410       "  %y = call i32 @unknown(i32 %b, i32 %c, i32 %a)"
411       "  %z = call i32 @unknown(i32 %c, i32 %a, i32 %b)"
412       "  ret void"
413       "} "
414       ,
415       Err, C);
416 
417   assert(M && "Could not parse module?");
418   assert(!verifyModule(*M) && "Must have been well formed!");
419 
420   runWithFunctionAndSE(*M, "f_1", [&](Function &F, ScalarEvolution &SE) {
421     auto *IV0 = getInstructionByName(F, "iv0");
422     auto *IV0Inc = getInstructionByName(F, "iv0.inc");
423 
424     auto *FirstExprForIV0 = SE.getSCEV(IV0);
425     auto *FirstExprForIV0Inc = SE.getSCEV(IV0Inc);
426     auto *SecondExprForIV0 = SE.getSCEV(IV0);
427 
428     EXPECT_TRUE(isa<SCEVAddRecExpr>(FirstExprForIV0));
429     EXPECT_TRUE(isa<SCEVAddRecExpr>(FirstExprForIV0Inc));
430     EXPECT_TRUE(isa<SCEVAddRecExpr>(SecondExprForIV0));
431   });
432 
433   auto CheckCommutativeMulExprs = [&](ScalarEvolution &SE, const SCEV *A,
434                                       const SCEV *B, const SCEV *C) {
435     EXPECT_EQ(SE.getMulExpr(A, B), SE.getMulExpr(B, A));
436     EXPECT_EQ(SE.getMulExpr(B, C), SE.getMulExpr(C, B));
437     EXPECT_EQ(SE.getMulExpr(A, C), SE.getMulExpr(C, A));
438 
439     SmallVector<const SCEV *, 3> Ops0 = {A, B, C};
440     SmallVector<const SCEV *, 3> Ops1 = {A, C, B};
441     SmallVector<const SCEV *, 3> Ops2 = {B, A, C};
442     SmallVector<const SCEV *, 3> Ops3 = {B, C, A};
443     SmallVector<const SCEV *, 3> Ops4 = {C, B, A};
444     SmallVector<const SCEV *, 3> Ops5 = {C, A, B};
445 
446     auto *Mul0 = SE.getMulExpr(Ops0);
447     auto *Mul1 = SE.getMulExpr(Ops1);
448     auto *Mul2 = SE.getMulExpr(Ops2);
449     auto *Mul3 = SE.getMulExpr(Ops3);
450     auto *Mul4 = SE.getMulExpr(Ops4);
451     auto *Mul5 = SE.getMulExpr(Ops5);
452 
453     EXPECT_EQ(Mul0, Mul1) << "Expected " << *Mul0 << " == " << *Mul1;
454     EXPECT_EQ(Mul1, Mul2) << "Expected " << *Mul1 << " == " << *Mul2;
455     EXPECT_EQ(Mul2, Mul3) << "Expected " << *Mul2 << " == " << *Mul3;
456     EXPECT_EQ(Mul3, Mul4) << "Expected " << *Mul3 << " == " << *Mul4;
457     EXPECT_EQ(Mul4, Mul5) << "Expected " << *Mul4 << " == " << *Mul5;
458   };
459 
460   for (StringRef FuncName : {"f_2", "f_3", "f_4"})
461     runWithFunctionAndSE(*M, FuncName, [&](Function &F, ScalarEvolution &SE) {
462       CheckCommutativeMulExprs(SE, SE.getSCEV(getInstructionByName(F, "x")),
463                                SE.getSCEV(getInstructionByName(F, "y")),
464                                SE.getSCEV(getInstructionByName(F, "z")));
465     });
466 }
467 
468 TEST_F(ScalarEvolutionsTest, SCEVCompareComplexity) {
469   FunctionType *FTy =
470       FunctionType::get(Type::getVoidTy(Context), std::vector<Type *>(), false);
471   Function *F = cast<Function>(M.getOrInsertFunction("f", FTy));
472   BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", F);
473   BasicBlock *LoopBB = BasicBlock::Create(Context, "bb1", F);
474   BranchInst::Create(LoopBB, EntryBB);
475 
476   auto *Ty = Type::getInt32Ty(Context);
477   SmallVector<Instruction*, 8> Muls(8), Acc(8), NextAcc(8);
478 
479   Acc[0] = PHINode::Create(Ty, 2, "", LoopBB);
480   Acc[1] = PHINode::Create(Ty, 2, "", LoopBB);
481   Acc[2] = PHINode::Create(Ty, 2, "", LoopBB);
482   Acc[3] = PHINode::Create(Ty, 2, "", LoopBB);
483   Acc[4] = PHINode::Create(Ty, 2, "", LoopBB);
484   Acc[5] = PHINode::Create(Ty, 2, "", LoopBB);
485   Acc[6] = PHINode::Create(Ty, 2, "", LoopBB);
486   Acc[7] = PHINode::Create(Ty, 2, "", LoopBB);
487 
488   for (int i = 0; i < 20; i++) {
489     Muls[0] = BinaryOperator::CreateMul(Acc[0], Acc[0], "", LoopBB);
490     NextAcc[0] = BinaryOperator::CreateAdd(Muls[0], Acc[4], "", LoopBB);
491     Muls[1] = BinaryOperator::CreateMul(Acc[1], Acc[1], "", LoopBB);
492     NextAcc[1] = BinaryOperator::CreateAdd(Muls[1], Acc[5], "", LoopBB);
493     Muls[2] = BinaryOperator::CreateMul(Acc[2], Acc[2], "", LoopBB);
494     NextAcc[2] = BinaryOperator::CreateAdd(Muls[2], Acc[6], "", LoopBB);
495     Muls[3] = BinaryOperator::CreateMul(Acc[3], Acc[3], "", LoopBB);
496     NextAcc[3] = BinaryOperator::CreateAdd(Muls[3], Acc[7], "", LoopBB);
497 
498     Muls[4] = BinaryOperator::CreateMul(Acc[4], Acc[4], "", LoopBB);
499     NextAcc[4] = BinaryOperator::CreateAdd(Muls[4], Acc[0], "", LoopBB);
500     Muls[5] = BinaryOperator::CreateMul(Acc[5], Acc[5], "", LoopBB);
501     NextAcc[5] = BinaryOperator::CreateAdd(Muls[5], Acc[1], "", LoopBB);
502     Muls[6] = BinaryOperator::CreateMul(Acc[6], Acc[6], "", LoopBB);
503     NextAcc[6] = BinaryOperator::CreateAdd(Muls[6], Acc[2], "", LoopBB);
504     Muls[7] = BinaryOperator::CreateMul(Acc[7], Acc[7], "", LoopBB);
505     NextAcc[7] = BinaryOperator::CreateAdd(Muls[7], Acc[3], "", LoopBB);
506     Acc = NextAcc;
507   }
508 
509   auto II = LoopBB->begin();
510   for (int i = 0; i < 8; i++) {
511     PHINode *Phi = cast<PHINode>(&*II++);
512     Phi->addIncoming(Acc[i], LoopBB);
513     Phi->addIncoming(UndefValue::get(Ty), EntryBB);
514   }
515 
516   BasicBlock *ExitBB = BasicBlock::Create(Context, "bb2", F);
517   BranchInst::Create(LoopBB, ExitBB, UndefValue::get(Type::getInt1Ty(Context)),
518                      LoopBB);
519 
520   Acc[0] = BinaryOperator::CreateAdd(Acc[0], Acc[1], "", ExitBB);
521   Acc[1] = BinaryOperator::CreateAdd(Acc[2], Acc[3], "", ExitBB);
522   Acc[2] = BinaryOperator::CreateAdd(Acc[4], Acc[5], "", ExitBB);
523   Acc[3] = BinaryOperator::CreateAdd(Acc[6], Acc[7], "", ExitBB);
524   Acc[0] = BinaryOperator::CreateAdd(Acc[0], Acc[1], "", ExitBB);
525   Acc[1] = BinaryOperator::CreateAdd(Acc[2], Acc[3], "", ExitBB);
526   Acc[0] = BinaryOperator::CreateAdd(Acc[0], Acc[1], "", ExitBB);
527 
528   ReturnInst::Create(Context, nullptr, ExitBB);
529 
530   ScalarEvolution SE = buildSE(*F);
531 
532   EXPECT_NE(nullptr, SE.getSCEV(Acc[0]));
533 }
534 
535 }  // end anonymous namespace
536 }  // end namespace llvm
537