aboutsummaryrefslogtreecommitdiffstats
path: root/unittests/Analysis
diff options
context:
space:
mode:
authorNick Lewycky <nicholas@mxc.ca>2011-10-04 06:51:26 +0000
committerNick Lewycky <nicholas@mxc.ca>2011-10-04 06:51:26 +0000
commite97728ecf8a0ee69562cc0e7880cfaa65200c624 (patch)
treeefec7199224c5861d0342b7b7bc827e30ce60947 /unittests/Analysis
parent6744a17dcfb941d9fdd869b9f06e20660e18ff88 (diff)
downloadexternal_llvm-e97728ecf8a0ee69562cc0e7880cfaa65200c624.zip
external_llvm-e97728ecf8a0ee69562cc0e7880cfaa65200c624.tar.gz
external_llvm-e97728ecf8a0ee69562cc0e7880cfaa65200c624.tar.bz2
The product of two chrec's can always be represented as a chrec.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141066 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'unittests/Analysis')
-rw-r--r--unittests/Analysis/ScalarEvolutionTest.cpp166
1 files changed, 159 insertions, 7 deletions
diff --git a/unittests/Analysis/ScalarEvolutionTest.cpp b/unittests/Analysis/ScalarEvolutionTest.cpp
index a09cb1c..ea5aeb3 100644
--- a/unittests/Analysis/ScalarEvolutionTest.cpp
+++ b/unittests/Analysis/ScalarEvolutionTest.cpp
@@ -8,20 +8,35 @@
//===----------------------------------------------------------------------===//
#include <llvm/Analysis/ScalarEvolutionExpressions.h>
+#include <llvm/Analysis/LoopInfo.h>
#include <llvm/GlobalVariable.h>
#include <llvm/Constants.h>
#include <llvm/LLVMContext.h>
#include <llvm/Module.h>
#include <llvm/PassManager.h>
+#include <llvm/ADT/SmallVector.h>
#include "gtest/gtest.h"
namespace llvm {
namespace {
-TEST(ScalarEvolutionsTest, SCEVUnknownRAUW) {
+// We use this fixture to ensure that we clean up ScalarEvolution before
+// deleting the PassManager.
+class ScalarEvolutionsTest : public testing::Test {
+protected:
+ ScalarEvolutionsTest() : M("", Context), SE(*new ScalarEvolution) {}
+ ~ScalarEvolutionsTest() {
+ // Manually clean up, since we allocated new SCEV objects after the
+ // pass was finished.
+ SE.releaseMemory();
+ }
LLVMContext Context;
- Module M("world", Context);
+ Module M;
+ PassManager PM;
+ ScalarEvolution &SE;
+};
+TEST_F(ScalarEvolutionsTest, SCEVUnknownRAUW) {
FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context),
std::vector<Type *>(), false);
Function *F = cast<Function>(M.getOrInsertFunction("f", FTy));
@@ -35,8 +50,6 @@ TEST(ScalarEvolutionsTest, SCEVUnknownRAUW) {
Value *V2 = new GlobalVariable(M, Ty, false, GlobalValue::ExternalLinkage, Init, "V2");
// Create a ScalarEvolution and "run" it so that it gets initialized.
- PassManager PM;
- ScalarEvolution &SE = *new ScalarEvolution();
PM.add(&SE);
PM.run(M);
@@ -72,10 +85,149 @@ TEST(ScalarEvolutionsTest, SCEVUnknownRAUW) {
EXPECT_EQ(cast<SCEVUnknown>(M0->getOperand(1))->getValue(), V0);
EXPECT_EQ(cast<SCEVUnknown>(M1->getOperand(1))->getValue(), V0);
EXPECT_EQ(cast<SCEVUnknown>(M2->getOperand(1))->getValue(), V0);
+}
+
+TEST_F(ScalarEvolutionsTest, SCEVMultiplyAddRecs) {
+ Type *Ty = Type::getInt32Ty(Context);
+ SmallVector<Type *, 10> Types;
+ Types.append(10, Ty);
+ FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), Types, false);
+ Function *F = cast<Function>(M.getOrInsertFunction("f", FTy));
+ BasicBlock *BB = BasicBlock::Create(Context, "entry", F);
+ ReturnInst::Create(Context, 0, BB);
+
+ // Create a ScalarEvolution and "run" it so that it gets initialized.
+ PM.add(&SE);
+ PM.run(M);
+
+ // It's possible to produce an empty loop through the default constructor,
+ // but you can't add any blocks to it without a LoopInfo pass.
+ Loop L;
+ const_cast<std::vector<BasicBlock*>&>(L.getBlocks()).push_back(BB);
+
+ Function::arg_iterator AI = F->arg_begin();
+ SmallVector<const SCEV *, 5> A;
+ A.push_back(SE.getSCEV(&*AI++));
+ A.push_back(SE.getSCEV(&*AI++));
+ A.push_back(SE.getSCEV(&*AI++));
+ A.push_back(SE.getSCEV(&*AI++));
+ A.push_back(SE.getSCEV(&*AI++));
+ const SCEV *A_rec = SE.getAddRecExpr(A, &L, SCEV::FlagAnyWrap);
+
+ SmallVector<const SCEV *, 5> B;
+ B.push_back(SE.getSCEV(&*AI++));
+ B.push_back(SE.getSCEV(&*AI++));
+ B.push_back(SE.getSCEV(&*AI++));
+ B.push_back(SE.getSCEV(&*AI++));
+ B.push_back(SE.getSCEV(&*AI++));
+ const SCEV *B_rec = SE.getAddRecExpr(B, &L, SCEV::FlagAnyWrap);
+
+ /* Spot check that we perform this transformation:
+ {A0,+,A1,+,A2,+,A3,+,A4} * {B0,+,B1,+,B2,+,B3,+,B4} =
+ {A0*B0,+,
+ A1*B0 + A0*B1 + A1*B1,+,
+ A2*B0 + 2A1*B1 + A0*B2 + 2A2*B1 + 2A1*B2 + A2*B2,+,
+ A3*B0 + 3A2*B1 + 3A1*B2 + A0*B3 + 3A3*B1 + 6A2*B2 + 3A1*B3 + 3A3*B2 +
+ 3A2*B3 + A3*B3,+,
+ A4*B0 + 4A3*B1 + 6A2*B2 + 4A1*B3 + A0*B4 + 4A4*B1 + 12A3*B2 + 12A2*B3 +
+ 4A1*B4 + 6A4*B2 + 12A3*B3 + 6A2*B4 + 4A4*B3 + 4A3*B4 + A4*B4,+,
+ 5A4*B1 + 10A3*B2 + 10A2*B3 + 5A1*B4 + 20A4*B2 + 30A3*B3 + 20A2*B4 +
+ 30A4*B3 + 30A3*B4 + 20A4*B4,+,
+ 15A4*B2 + 20A3*B3 + 15A2*B4 + 60A4*B3 + 60A3*B4 + 90A4*B4,+,
+ 35A4*B3 + 35A3*B4 + 140A4*B4,+,
+ 70A4*B4}
+ */
+
+ const SCEVAddRecExpr *Product =
+ dyn_cast<SCEVAddRecExpr>(SE.getMulExpr(A_rec, B_rec));
+ ASSERT_TRUE(Product);
+ ASSERT_EQ(Product->getNumOperands(), 9u);
+
+ SmallVector<const SCEV *, 16> Sum;
+ Sum.push_back(SE.getMulExpr(A[0], B[0]));
+ EXPECT_EQ(Product->getOperand(0), SE.getAddExpr(Sum));
+ Sum.clear();
+
+ // SCEV produces different an equal but different expression for these.
+ // Re-enable when PR11052 is fixed.
+#if 0
+ Sum.push_back(SE.getMulExpr(A[1], B[0]));
+ Sum.push_back(SE.getMulExpr(A[0], B[1]));
+ Sum.push_back(SE.getMulExpr(A[1], B[1]));
+ EXPECT_EQ(Product->getOperand(1), SE.getAddExpr(Sum));
+ Sum.clear();
+
+ Sum.push_back(SE.getMulExpr(A[2], B[0]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 2), A[1], B[1]));
+ Sum.push_back(SE.getMulExpr(A[0], B[2]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 2), A[2], B[1]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 2), A[1], B[2]));
+ Sum.push_back(SE.getMulExpr(A[2], B[2]));
+ EXPECT_EQ(Product->getOperand(2), SE.getAddExpr(Sum));
+ Sum.clear();
+
+ Sum.push_back(SE.getMulExpr(A[3], B[0]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 3), A[2], B[1]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 3), A[1], B[2]));
+ Sum.push_back(SE.getMulExpr(A[0], B[3]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 3), A[3], B[1]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 6), A[2], B[2]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 3), A[1], B[3]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 3), A[3], B[2]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 3), A[2], B[3]));
+ Sum.push_back(SE.getMulExpr(A[3], B[3]));
+ EXPECT_EQ(Product->getOperand(3), SE.getAddExpr(Sum));
+ Sum.clear();
+
+ Sum.push_back(SE.getMulExpr(A[4], B[0]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 4), A[3], B[1]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 6), A[2], B[2]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 4), A[1], B[3]));
+ Sum.push_back(SE.getMulExpr(A[0], B[4]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 4), A[4], B[1]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 12), A[3], B[2]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 12), A[2], B[3]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 4), A[1], B[4]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 6), A[4], B[2]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 12), A[3], B[3]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 6), A[2], B[4]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 4), A[4], B[3]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 4), A[3], B[4]));
+ Sum.push_back(SE.getMulExpr(A[4], B[4]));
+ EXPECT_EQ(Product->getOperand(4), SE.getAddExpr(Sum));
+ Sum.clear();
+
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 5), A[4], B[1]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 10), A[3], B[2]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 10), A[2], B[3]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 5), A[1], B[4]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 20), A[4], B[2]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 30), A[3], B[3]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 20), A[2], B[4]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 30), A[4], B[3]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 30), A[3], B[4]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 20), A[4], B[4]));
+ EXPECT_EQ(Product->getOperand(5), SE.getAddExpr(Sum));
+ Sum.clear();
+
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 15), A[4], B[2]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 20), A[3], B[3]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 15), A[2], B[4]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 60), A[4], B[3]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 60), A[3], B[4]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 90), A[4], B[4]));
+ EXPECT_EQ(Product->getOperand(6), SE.getAddExpr(Sum));
+ Sum.clear();
+
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 35), A[4], B[3]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 35), A[3], B[4]));
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 140), A[4], B[4]));
+ EXPECT_EQ(Product->getOperand(7), SE.getAddExpr(Sum));
+ Sum.clear();
+#endif
- // Manually clean up, since we allocated new SCEV objects after the
- // pass was finished.
- SE.releaseMemory();
+ Sum.push_back(SE.getMulExpr(SE.getConstant(Ty, 70), A[4], B[4]));
+ EXPECT_EQ(Product->getOperand(8), SE.getAddExpr(Sum));
}
} // end anonymous namespace