Mercurial > hg > CbC > CbC_llvm

comparison llvm/unittests/Analysis/ScalarEvolutionTest.cpp @ 252:1f2b6ac9f198 llvm-original

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
LLVM16-1
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Fri, 18 Aug 2023 09:04:13 +0900
parents c4bab56944e8
children
comparison
equal deleted inserted replaced
237:c80f45b162ad 252:1f2b6ac9f198
56 ASSERT_NE(F, nullptr) << "Could not find " << FuncName; 56 ASSERT_NE(F, nullptr) << "Could not find " << FuncName;
57 ScalarEvolution SE = buildSE(*F); 57 ScalarEvolution SE = buildSE(*F);
58 Test(*F, *LI, SE); 58 Test(*F, *LI, SE);
59 } 59 }
60 60
61 static Optional<APInt> computeConstantDifference(ScalarEvolution &SE, 61 static std::optional<APInt> computeConstantDifference(ScalarEvolution &SE,
62 const SCEV *LHS, 62 const SCEV *LHS,
63 const SCEV *RHS) { 63 const SCEV *RHS) {
64 return SE.computeConstantDifference(LHS, RHS); 64 return SE.computeConstantDifference(LHS, RHS);
65 } 65 }
66 66
67 static bool matchURem(ScalarEvolution &SE, const SCEV *Expr, const SCEV *&LHS, 67 static bool matchURem(ScalarEvolution &SE, const SCEV *Expr, const SCEV *&LHS,
68 const SCEV *&RHS) { 68 const SCEV *&RHS) {
69 return SE.matchURem(Expr, LHS, RHS); 69 return SE.matchURem(Expr, LHS, RHS);
70 } 70 }
739 DataLayout += "-"; 739 DataLayout += "-";
740 DataLayout += "ni:10"; 740 DataLayout += "ni:10";
741 NIM.setDataLayout(DataLayout); 741 NIM.setDataLayout(DataLayout);
742 742
743 Type *T_int64 = Type::getInt64Ty(Context); 743 Type *T_int64 = Type::getInt64Ty(Context);
744 Type *T_pint64 = T_int64->getPointerTo(10); 744 Type *T_pint64 = PointerType::get(Context, 10);
745 745
746 FunctionType *FTy = 746 FunctionType *FTy =
747 FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false); 747 FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false);
748 Function *F = Function::Create(FTy, Function::ExternalLinkage, "foo", NIM); 748 Function *F = Function::Create(FTy, Function::ExternalLinkage, "foo", NIM);
749 749
837 DataLayout += "-"; 837 DataLayout += "-";
838 DataLayout += "ni:10"; 838 DataLayout += "ni:10";
839 NIM.setDataLayout(DataLayout); 839 NIM.setDataLayout(DataLayout);
840 840
841 Type *T_int64 = Type::getInt64Ty(Context); 841 Type *T_int64 = Type::getInt64Ty(Context);
842 Type *T_pint64 = T_int64->getPointerTo(10); 842 Type *T_pint64 = PointerType::get(Context, 10);
843 843
844 FunctionType *FTy = 844 FunctionType *FTy =
845 FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false); 845 FunctionType::get(Type::getVoidTy(Context), {T_pint64}, false);
846 Function *F = Function::Create(FTy, Function::ExternalLinkage, "foo", NIM); 846 Function *F = Function::Create(FTy, Function::ExternalLinkage, "foo", NIM);
847 847
1146 auto *ScevXA = SE.getSCEV(getInstructionByName(F, "xa")); // {%pp,+,1} 1146 auto *ScevXA = SE.getSCEV(getInstructionByName(F, "xa")); // {%pp,+,1}
1147 auto *ScevYY = SE.getSCEV(getInstructionByName(F, "yy")); // {(3 + %pp),+,1} 1147 auto *ScevYY = SE.getSCEV(getInstructionByName(F, "yy")); // {(3 + %pp),+,1}
1148 auto *ScevXB = SE.getSCEV(getInstructionByName(F, "xb")); // {%pp,+,1} 1148 auto *ScevXB = SE.getSCEV(getInstructionByName(F, "xb")); // {%pp,+,1}
1149 auto *ScevIVNext = SE.getSCEV(getInstructionByName(F, "iv.next")); // {1,+,1} 1149 auto *ScevIVNext = SE.getSCEV(getInstructionByName(F, "iv.next")); // {1,+,1}
1150 1150
1151 auto diff = [&SE](const SCEV *LHS, const SCEV *RHS) -> Optional<int> { 1151 auto diff = [&SE](const SCEV *LHS, const SCEV *RHS) -> std::optional<int> {
1152 auto ConstantDiffOrNone = computeConstantDifference(SE, LHS, RHS); 1152 auto ConstantDiffOrNone = computeConstantDifference(SE, LHS, RHS);
1153 if (!ConstantDiffOrNone) 1153 if (!ConstantDiffOrNone)
1154 return None; 1154 return std::nullopt;
1155 1155
1156 auto ExtDiff = ConstantDiffOrNone->getSExtValue(); 1156 auto ExtDiff = ConstantDiffOrNone->getSExtValue();
1157 int Diff = ExtDiff; 1157 int Diff = ExtDiff;
1158 assert(Diff == ExtDiff && "Integer overflow"); 1158 assert(Diff == ExtDiff && "Integer overflow");
1159 return Diff; 1159 return Diff;
1168 EXPECT_EQ(diff(ScevXA, ScevYY), -3); 1168 EXPECT_EQ(diff(ScevXA, ScevYY), -3);
1169 EXPECT_EQ(diff(ScevYY, ScevXB), 3); 1169 EXPECT_EQ(diff(ScevYY, ScevXB), 3);
1170 EXPECT_EQ(diff(ScevIV, ScevIVNext), -1); 1170 EXPECT_EQ(diff(ScevIV, ScevIVNext), -1);
1171 EXPECT_EQ(diff(ScevIVNext, ScevIV), 1); 1171 EXPECT_EQ(diff(ScevIVNext, ScevIV), 1);
1172 EXPECT_EQ(diff(ScevIVNext, ScevIVNext), 0); 1172 EXPECT_EQ(diff(ScevIVNext, ScevIVNext), 0);
1173 EXPECT_EQ(diff(ScevV0, ScevIV), None); 1173 EXPECT_EQ(diff(ScevV0, ScevIV), std::nullopt);
1174 EXPECT_EQ(diff(ScevIVNext, ScevV3), None); 1174 EXPECT_EQ(diff(ScevIVNext, ScevV3), std::nullopt);
1175 EXPECT_EQ(diff(ScevYY, ScevV3), None); 1175 EXPECT_EQ(diff(ScevYY, ScevV3), std::nullopt);
1176 }); 1176 });
1177 } 1177 }
1178 1178
1179 TEST_F(ScalarEvolutionsTest, SCEVrewriteUnknowns) { 1179 TEST_F(ScalarEvolutionsTest, SCEVrewriteUnknowns) {
1180 LLVMContext C; 1180 LLVMContext C;
1534 ASSERT_TRUE(CeilingS->getAPInt() == CeilingInt); 1534 ASSERT_TRUE(CeilingS->getAPInt() == CeilingInt);
1535 } 1535 }
1536 }); 1536 });
1537 } 1537 }
1538 1538
1539 TEST_F(ScalarEvolutionsTest, ComputeMaxTripCountFromArrayNormal) { 1539 TEST_F(ScalarEvolutionsTest, CheckGetPowerOfTwo) {
1540 Module M("CheckGetPowerOfTwo", Context);
1541 FunctionType *FTy = FunctionType::get(Type::getVoidTy(Context), {}, false);
1542 Function *F = Function::Create(FTy, Function::ExternalLinkage, "foo", M);
1543 BasicBlock *Entry = BasicBlock::Create(Context, "entry", F);
1544 IRBuilder<> Builder(Entry);
1545 Builder.CreateRetVoid();
1546 ScalarEvolution SE = buildSE(*F);
1547
1548 for (unsigned short i = 0; i < 64; ++i)
1549 EXPECT_TRUE(
1550 dyn_cast<SCEVConstant>(SE.getPowerOfTwo(Type::getInt64Ty(Context), i))
1551 ->getValue()
1552 ->equalsInt(1ULL << i));
1553 }
1554
1555 TEST_F(ScalarEvolutionsTest, ApplyLoopGuards) {
1540 LLVMContext C; 1556 LLVMContext C;
1541 SMDiagnostic Err; 1557 SMDiagnostic Err;
1542 std::unique_ptr<Module> M = parseAssemblyString( 1558 std::unique_ptr<Module> M = parseAssemblyString(
1543 "define void @foo(i32 signext %len) { " 1559 "declare void @llvm.assume(i1)\n"
1544 "entry: " 1560 "define void @test(i32 %num) {\n"
1545 " %a = alloca [7 x i32], align 4 " 1561 "entry:\n"
1546 " %cmp4 = icmp sgt i32 %len, 0 " 1562 " %u = urem i32 %num, 4\n"
1547 " br i1 %cmp4, label %for.body.preheader, label %for.cond.cleanup " 1563 " %cmp = icmp eq i32 %u, 0\n"
1548 "for.body.preheader: " 1564 " tail call void @llvm.assume(i1 %cmp)\n"
1549 " br label %for.body " 1565 " %cmp.1 = icmp ugt i32 %num, 0\n"
1550 "for.cond.cleanup.loopexit: " 1566 " tail call void @llvm.assume(i1 %cmp.1)\n"
1551 " br label %for.cond.cleanup " 1567 " br label %for.body\n"
1552 "for.cond.cleanup: " 1568 "for.body:\n"
1553 " ret void " 1569 " %i.010 = phi i32 [ 0, %entry ], [ %inc, %for.body ]\n"
1554 "for.body: " 1570 " %inc = add nuw nsw i32 %i.010, 1\n"
1555 " %iv = phi i32 [ %inc, %for.body ], [ 0, %for.body.preheader ] " 1571 " %cmp2 = icmp ult i32 %inc, %num\n"
1556 " %idxprom = zext i32 %iv to i64 " 1572 " br i1 %cmp2, label %for.body, label %exit\n"
1557 " %arrayidx = getelementptr inbounds [7 x i32], [7 x i32]* %a, i64 0, \ 1573 "exit:\n"
1558 i64 %idxprom " 1574 " ret void\n"
1559 " store i32 0, i32* %arrayidx, align 4 " 1575 "}\n",
1560 " %inc = add nuw nsw i32 %iv, 1 "
1561 " %cmp = icmp slt i32 %inc, %len "
1562 " br i1 %cmp, label %for.body, label %for.cond.cleanup.loopexit "
1563 "} ",
1564 Err, C); 1576 Err, C);
1565 1577
1566 ASSERT_TRUE(M && "Could not parse module?"); 1578 ASSERT_TRUE(M && "Could not parse module?");
1567 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!"); 1579 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");
1568 1580
1569 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) { 1581 runWithSE(*M, "test", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1570 auto *ScevIV = SE.getSCEV(getInstructionByName(F, "iv")); 1582 auto *TCScev = SE.getSCEV(getArgByName(F, "num"));
1571 const Loop *L = cast<SCEVAddRecExpr>(ScevIV)->getLoop(); 1583 auto *ApplyLoopGuardsTC = SE.applyLoopGuards(TCScev, *LI.begin());
1572 1584 // Assert that the new TC is (4 * ((4 umax %num) /u 4))
1573 const SCEV *ITC = SE.getConstantMaxTripCountFromArray(L); 1585 APInt Four(32, 4);
1574 EXPECT_FALSE(isa<SCEVCouldNotCompute>(ITC)); 1586 auto *Constant4 = SE.getConstant(Four);
1575 EXPECT_TRUE(isa<SCEVConstant>(ITC)); 1587 auto *Max = SE.getUMaxExpr(TCScev, Constant4);
1576 EXPECT_EQ(cast<SCEVConstant>(ITC)->getAPInt().getSExtValue(), 8); 1588 auto *Mul = SE.getMulExpr(SE.getUDivExpr(Max, Constant4), Constant4);
1589 ASSERT_TRUE(Mul == ApplyLoopGuardsTC);
1577 }); 1590 });
1578 } 1591 }
1579 1592
1580 TEST_F(ScalarEvolutionsTest, ComputeMaxTripCountFromZeroArray) {
1581 LLVMContext C;
1582 SMDiagnostic Err;
1583 std::unique_ptr<Module> M = parseAssemblyString(
1584 "define void @foo(i32 signext %len) { "
1585 "entry: "
1586 " %a = alloca [0 x i32], align 4 "
1587 " %cmp4 = icmp sgt i32 %len, 0 "
1588 " br i1 %cmp4, label %for.body.preheader, label %for.cond.cleanup "
1589 "for.body.preheader: "
1590 " br label %for.body "
1591 "for.cond.cleanup.loopexit: "
1592 " br label %for.cond.cleanup "
1593 "for.cond.cleanup: "
1594 " ret void "
1595 "for.body: "
1596 " %iv = phi i32 [ %inc, %for.body ], [ 0, %for.body.preheader ] "
1597 " %idxprom = zext i32 %iv to i64 "
1598 " %arrayidx = getelementptr inbounds [0 x i32], [0 x i32]* %a, i64 0, \
1599 i64 %idxprom "
1600 " store i32 0, i32* %arrayidx, align 4 "
1601 " %inc = add nuw nsw i32 %iv, 1 "
1602 " %cmp = icmp slt i32 %inc, %len "
1603 " br i1 %cmp, label %for.body, label %for.cond.cleanup.loopexit "
1604 "} ",
1605 Err, C);
1606
1607 ASSERT_TRUE(M && "Could not parse module?");
1608 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");
1609
1610 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1611 auto *ScevIV = SE.getSCEV(getInstructionByName(F, "iv"));
1612 const Loop *L = cast<SCEVAddRecExpr>(ScevIV)->getLoop();
1613
1614 const SCEV *ITC = SE.getConstantMaxTripCountFromArray(L);
1615 EXPECT_FALSE(isa<SCEVCouldNotCompute>(ITC));
1616 EXPECT_TRUE(isa<SCEVConstant>(ITC));
1617 EXPECT_EQ(cast<SCEVConstant>(ITC)->getAPInt().getSExtValue(), 1);
1618 });
1619 }
1620
1621 TEST_F(ScalarEvolutionsTest, ComputeMaxTripCountFromExtremArray) {
1622 LLVMContext C;
1623 SMDiagnostic Err;
1624 std::unique_ptr<Module> M = parseAssemblyString(
1625 "define void @foo(i32 signext %len) { "
1626 "entry: "
1627 " %a = alloca [4294967295 x i1], align 4 "
1628 " %cmp4 = icmp sgt i32 %len, 0 "
1629 " br i1 %cmp4, label %for.body.preheader, label %for.cond.cleanup "
1630 "for.body.preheader: "
1631 " br label %for.body "
1632 "for.cond.cleanup.loopexit: "
1633 " br label %for.cond.cleanup "
1634 "for.cond.cleanup: "
1635 " ret void "
1636 "for.body: "
1637 " %iv = phi i32 [ %inc, %for.body ], [ 0, %for.body.preheader ] "
1638 " %idxprom = zext i32 %iv to i64 "
1639 " %arrayidx = getelementptr inbounds [4294967295 x i1], \
1640 [4294967295 x i1]* %a, i64 0, i64 %idxprom "
1641 " store i1 0, i1* %arrayidx, align 4 "
1642 " %inc = add nuw nsw i32 %iv, 1 "
1643 " %cmp = icmp slt i32 %inc, %len "
1644 " br i1 %cmp, label %for.body, label %for.cond.cleanup.loopexit "
1645 "} ",
1646 Err, C);
1647
1648 ASSERT_TRUE(M && "Could not parse module?");
1649 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");
1650
1651 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1652 auto *ScevIV = SE.getSCEV(getInstructionByName(F, "iv"));
1653 const Loop *L = cast<SCEVAddRecExpr>(ScevIV)->getLoop();
1654
1655 const SCEV *ITC = SE.getConstantMaxTripCountFromArray(L);
1656 EXPECT_TRUE(isa<SCEVCouldNotCompute>(ITC));
1657 });
1658 }
1659
1660 TEST_F(ScalarEvolutionsTest, ComputeMaxTripCountFromArrayInBranch) {
1661 LLVMContext C;
1662 SMDiagnostic Err;
1663 std::unique_ptr<Module> M = parseAssemblyString(
1664 "define void @foo(i32 signext %len) { "
1665 "entry: "
1666 " %a = alloca [8 x i32], align 4 "
1667 " br label %for.cond "
1668 "for.cond: "
1669 " %iv = phi i32 [ %inc, %for.inc ], [ 0, %entry ] "
1670 " %cmp = icmp slt i32 %iv, %len "
1671 " br i1 %cmp, label %for.body, label %for.cond.cleanup "
1672 "for.cond.cleanup: "
1673 " br label %for.end "
1674 "for.body: "
1675 " %cmp1 = icmp slt i32 %iv, 8 "
1676 " br i1 %cmp1, label %if.then, label %if.end "
1677 "if.then: "
1678 " %idxprom = sext i32 %iv to i64 "
1679 " %arrayidx = getelementptr inbounds [8 x i32], [8 x i32]* %a, i64 0, \
1680 i64 %idxprom "
1681 " store i32 0, i32* %arrayidx, align 4 "
1682 " br label %if.end "
1683 "if.end: "
1684 " br label %for.inc "
1685 "for.inc: "
1686 " %inc = add nsw i32 %iv, 1 "
1687 " br label %for.cond "
1688 "for.end: "
1689 " ret void "
1690 "} ",
1691 Err, C);
1692
1693 ASSERT_TRUE(M && "Could not parse module?");
1694 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");
1695
1696 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1697 auto *ScevIV = SE.getSCEV(getInstructionByName(F, "iv"));
1698 const Loop *L = cast<SCEVAddRecExpr>(ScevIV)->getLoop();
1699
1700 const SCEV *ITC = SE.getConstantMaxTripCountFromArray(L);
1701 EXPECT_TRUE(isa<SCEVCouldNotCompute>(ITC));
1702 });
1703 }
1704
1705 TEST_F(ScalarEvolutionsTest, ComputeMaxTripCountFromMultiDemArray) {
1706 LLVMContext C;
1707 SMDiagnostic Err;
1708 std::unique_ptr<Module> M = parseAssemblyString(
1709 "define void @foo(i32 signext %len) { "
1710 "entry: "
1711 " %a = alloca [3 x [5 x i32]], align 4 "
1712 " br label %for.cond "
1713 "for.cond: "
1714 " %iv = phi i32 [ %inc, %for.inc ], [ 0, %entry ] "
1715 " %cmp = icmp slt i32 %iv, %len "
1716 " br i1 %cmp, label %for.body, label %for.cond.cleanup "
1717 "for.cond.cleanup: "
1718 " br label %for.end "
1719 "for.body: "
1720 " %arrayidx = getelementptr inbounds [3 x [5 x i32]], \
1721 [3 x [5 x i32]]* %a, i64 0, i64 3 "
1722 " %idxprom = sext i32 %iv to i64 "
1723 " %arrayidx1 = getelementptr inbounds [5 x i32], [5 x i32]* %arrayidx, \
1724 i64 0, i64 %idxprom "
1725 " store i32 0, i32* %arrayidx1, align 4"
1726 " br label %for.inc "
1727 "for.inc: "
1728 " %inc = add nsw i32 %iv, 1 "
1729 " br label %for.cond "
1730 "for.end: "
1731 " ret void "
1732 "} ",
1733 Err, C);
1734
1735 ASSERT_TRUE(M && "Could not parse module?");
1736 ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");
1737
1738 runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
1739 auto *ScevIV = SE.getSCEV(getInstructionByName(F, "iv"));
1740 const Loop *L = cast<SCEVAddRecExpr>(ScevIV)->getLoop();
1741
1742 const SCEV *ITC = SE.getConstantMaxTripCountFromArray(L);
1743 EXPECT_TRUE(isa<SCEVCouldNotCompute>(ITC));
1744 });
1745 }
1746
1747 } // end namespace llvm 1593 } // end namespace llvm