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/ScalarEvolutionExpressions.h" 11 #include "llvm/Analysis/AssumptionCache.h" 12 #include "llvm/Analysis/LoopInfo.h" 13 #include "llvm/Analysis/TargetLibraryInfo.h" 14 #include "llvm/ADT/SmallVector.h" 15 #include "llvm/Analysis/LoopInfo.h" 16 #include "llvm/IR/Constants.h" 17 #include "llvm/IR/Dominators.h" 18 #include "llvm/IR/GlobalVariable.h" 19 #include "llvm/IR/LLVMContext.h" 20 #include "llvm/IR/Module.h" 21 #include "llvm/IR/LegacyPassManager.h" 22 #include "gtest/gtest.h" 23 24 namespace llvm { 25 namespace { 26 27 // We use this fixture to ensure that we clean up ScalarEvolution before 28 // deleting the PassManager. 29 class ScalarEvolutionsTest : public testing::Test { 30 protected: 31 LLVMContext Context; 32 Module M; 33 TargetLibraryInfoImpl TLII; 34 TargetLibraryInfo TLI; 35 36 std::unique_ptr<AssumptionCache> AC; 37 std::unique_ptr<DominatorTree> DT; 38 std::unique_ptr<LoopInfo> LI; 39 40 ScalarEvolutionsTest() : M("", Context), TLII(), TLI(TLII) {} 41 42 ScalarEvolution buildSE(Function &F) { 43 AC.reset(new AssumptionCache(F)); 44 DT.reset(new DominatorTree(F)); 45 LI.reset(new LoopInfo(*DT)); 46 return ScalarEvolution(F, TLI, *AC, *DT, *LI); 47 } 48 }; 49 50 TEST_F(ScalarEvolutionsTest, SCEVUnknownRAUW) { 51 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), 52 std::vector<Type *>(), false); 53 Function *F = cast<Function>(M.getOrInsertFunction("f", FTy)); 54 BasicBlock *BB = BasicBlock::Create(Context, "entry", F); 55 ReturnInst::Create(Context, nullptr, BB); 56 57 Type *Ty = Type::getInt1Ty(Context); 58 Constant *Init = Constant::getNullValue(Ty); 59 Value *V0 = new GlobalVariable(M, Ty, false, GlobalValue::ExternalLinkage, Init, "V0"); 60 Value *V1 = new GlobalVariable(M, Ty, false, GlobalValue::ExternalLinkage, Init, "V1"); 61 Value *V2 = new GlobalVariable(M, Ty, false, GlobalValue::ExternalLinkage, Init, "V2"); 62 63 ScalarEvolution SE = buildSE(*F); 64 65 const SCEV *S0 = SE.getSCEV(V0); 66 const SCEV *S1 = SE.getSCEV(V1); 67 const SCEV *S2 = SE.getSCEV(V2); 68 69 const SCEV *P0 = SE.getAddExpr(S0, S0); 70 const SCEV *P1 = SE.getAddExpr(S1, S1); 71 const SCEV *P2 = SE.getAddExpr(S2, S2); 72 73 const SCEVMulExpr *M0 = cast<SCEVMulExpr>(P0); 74 const SCEVMulExpr *M1 = cast<SCEVMulExpr>(P1); 75 const SCEVMulExpr *M2 = cast<SCEVMulExpr>(P2); 76 77 EXPECT_EQ(cast<SCEVConstant>(M0->getOperand(0))->getValue()->getZExtValue(), 78 2u); 79 EXPECT_EQ(cast<SCEVConstant>(M1->getOperand(0))->getValue()->getZExtValue(), 80 2u); 81 EXPECT_EQ(cast<SCEVConstant>(M2->getOperand(0))->getValue()->getZExtValue(), 82 2u); 83 84 // Before the RAUWs, these are all pointing to separate values. 85 EXPECT_EQ(cast<SCEVUnknown>(M0->getOperand(1))->getValue(), V0); 86 EXPECT_EQ(cast<SCEVUnknown>(M1->getOperand(1))->getValue(), V1); 87 EXPECT_EQ(cast<SCEVUnknown>(M2->getOperand(1))->getValue(), V2); 88 89 // Do some RAUWs. 90 V2->replaceAllUsesWith(V1); 91 V1->replaceAllUsesWith(V0); 92 93 // After the RAUWs, these should all be pointing to V0. 94 EXPECT_EQ(cast<SCEVUnknown>(M0->getOperand(1))->getValue(), V0); 95 EXPECT_EQ(cast<SCEVUnknown>(M1->getOperand(1))->getValue(), V0); 96 EXPECT_EQ(cast<SCEVUnknown>(M2->getOperand(1))->getValue(), V0); 97 } 98 99 TEST_F(ScalarEvolutionsTest, SCEVMultiplyAddRecs) { 100 Type *Ty = Type::getInt32Ty(Context); 101 SmallVector<Type *, 10> Types; 102 Types.append(10, Ty); 103 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), Types, false); 104 Function *F = cast<Function>(M.getOrInsertFunction("f", FTy)); 105 BasicBlock *BB = BasicBlock::Create(Context, "entry", F); 106 ReturnInst::Create(Context, nullptr, BB); 107 108 ScalarEvolution SE = buildSE(*F); 109 110 // It's possible to produce an empty loop through the default constructor, 111 // but you can't add any blocks to it without a LoopInfo pass. 112 Loop L; 113 const_cast<std::vector<BasicBlock*>&>(L.getBlocks()).push_back(BB); 114 115 Function::arg_iterator AI = F->arg_begin(); 116 SmallVector<const SCEV *, 5> A; 117 A.push_back(SE.getSCEV(&*AI++)); 118 A.push_back(SE.getSCEV(&*AI++)); 119 A.push_back(SE.getSCEV(&*AI++)); 120 A.push_back(SE.getSCEV(&*AI++)); 121 A.push_back(SE.getSCEV(&*AI++)); 122 const SCEV *A_rec = SE.getAddRecExpr(A, &L, SCEV::FlagAnyWrap); 123 124 SmallVector<const SCEV *, 5> B; 125 B.push_back(SE.getSCEV(&*AI++)); 126 B.push_back(SE.getSCEV(&*AI++)); 127 B.push_back(SE.getSCEV(&*AI++)); 128 B.push_back(SE.getSCEV(&*AI++)); 129 B.push_back(SE.getSCEV(&*AI++)); 130 const SCEV *B_rec = SE.getAddRecExpr(B, &L, SCEV::FlagAnyWrap); 131 132 /* Spot check that we perform this transformation: 133 {A0,+,A1,+,A2,+,A3,+,A4} * {B0,+,B1,+,B2,+,B3,+,B4} = 134 {A0*B0,+, 135 A1*B0 + A0*B1 + A1*B1,+, 136 A2*B0 + 2A1*B1 + A0*B2 + 2A2*B1 + 2A1*B2 + A2*B2,+, 137 A3*B0 + 3A2*B1 + 3A1*B2 + A0*B3 + 3A3*B1 + 6A2*B2 + 3A1*B3 + 3A3*B2 + 138 3A2*B3 + A3*B3,+, 139 A4*B0 + 4A3*B1 + 6A2*B2 + 4A1*B3 + A0*B4 + 4A4*B1 + 12A3*B2 + 12A2*B3 + 140 4A1*B4 + 6A4*B2 + 12A3*B3 + 6A2*B4 + 4A4*B3 + 4A3*B4 + A4*B4,+, 141 5A4*B1 + 10A3*B2 + 10A2*B3 + 5A1*B4 + 20A4*B2 + 30A3*B3 + 20A2*B4 + 142 30A4*B3 + 30A3*B4 + 20A4*B4,+, 143 15A4*B2 + 20A3*B3 + 15A2*B4 + 60A4*B3 + 60A3*B4 + 90A4*B4,+, 144 35A4*B3 + 35A3*B4 + 140A4*B4,+, 145 70A4*B4} 146 */ 147 148 const SCEVAddRecExpr *Product = 149 dyn_cast<SCEVAddRecExpr>(SE.getMulExpr(A_rec, B_rec)); 150 ASSERT_TRUE(Product); 151 ASSERT_EQ(Product->getNumOperands(), 9u); 152 153 SmallVector<const SCEV *, 16> Sum; 154 Sum.push_back(SE.getMulExpr(A[0], B[0])); 155 EXPECT_EQ(Product->getOperand(0), SE.getAddExpr(Sum)); 156 Sum.clear(); 157 158 // SCEV produces different an equal but different expression for these. 159 // Re-enable when PR11052 is fixed. 160 #if 0 161 Sum.push_back(SE.getMulExpr(A[1], B[0])); 162 Sum.push_back(SE.getMulExpr(A[0], B[1])); 163 Sum.push_back(SE.getMulExpr(A[1], B[1])); 164 EXPECT_EQ(Product->getOperand(1), SE.getAddExpr(Sum)); 165 Sum.clear(); 166 167 Sum.push_back(SE.getMulExpr(A[2], B[0])); 168 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 2), A[1], B[1])); 169 Sum.push_back(SE.getMulExpr(A[0], B[2])); 170 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 2), A[2], B[1])); 171 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 2), A[1], B[2])); 172 Sum.push_back(SE.getMulExpr(A[2], B[2])); 173 EXPECT_EQ(Product->getOperand(2), SE.getAddExpr(Sum)); 174 Sum.clear(); 175 176 Sum.push_back(SE.getMulExpr(A[3], B[0])); 177 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 3), A[2], B[1])); 178 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 3), A[1], B[2])); 179 Sum.push_back(SE.getMulExpr(A[0], B[3])); 180 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 3), A[3], B[1])); 181 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 6), A[2], B[2])); 182 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 3), A[1], B[3])); 183 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 3), A[3], B[2])); 184 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 3), A[2], B[3])); 185 Sum.push_back(SE.getMulExpr(A[3], B[3])); 186 EXPECT_EQ(Product->getOperand(3), SE.getAddExpr(Sum)); 187 Sum.clear(); 188 189 Sum.push_back(SE.getMulExpr(A[4], B[0])); 190 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 4), A[3], B[1])); 191 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 6), A[2], B[2])); 192 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 4), A[1], B[3])); 193 Sum.push_back(SE.getMulExpr(A[0], B[4])); 194 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 4), A[4], B[1])); 195 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 12), A[3], B[2])); 196 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 12), A[2], B[3])); 197 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 4), A[1], B[4])); 198 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 6), A[4], B[2])); 199 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 12), A[3], B[3])); 200 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 6), A[2], B[4])); 201 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 4), A[4], B[3])); 202 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 4), A[3], B[4])); 203 Sum.push_back(SE.getMulExpr(A[4], B[4])); 204 EXPECT_EQ(Product->getOperand(4), SE.getAddExpr(Sum)); 205 Sum.clear(); 206 207 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 5), A[4], B[1])); 208 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 10), A[3], B[2])); 209 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 10), A[2], B[3])); 210 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 5), A[1], B[4])); 211 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 20), A[4], B[2])); 212 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 30), A[3], B[3])); 213 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 20), A[2], B[4])); 214 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 30), A[4], B[3])); 215 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 30), A[3], B[4])); 216 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 20), A[4], B[4])); 217 EXPECT_EQ(Product->getOperand(5), SE.getAddExpr(Sum)); 218 Sum.clear(); 219 220 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 15), A[4], B[2])); 221 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 20), A[3], B[3])); 222 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 15), A[2], B[4])); 223 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 60), A[4], B[3])); 224 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 60), A[3], B[4])); 225 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 90), A[4], B[4])); 226 EXPECT_EQ(Product->getOperand(6), SE.getAddExpr(Sum)); 227 Sum.clear(); 228 229 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 35), A[4], B[3])); 230 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 35), A[3], B[4])); 231 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 140), A[4], B[4])); 232 EXPECT_EQ(Product->getOperand(7), SE.getAddExpr(Sum)); 233 Sum.clear(); 234 #endif 235 236 Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 70), A[4], B[4])); 237 EXPECT_EQ(Product->getOperand(8), SE.getAddExpr(Sum)); 238 } 239 240 } // end anonymous namespace 241 } // end namespace llvm 242
