Skip to content

Commit 12b0c28

Browse files
author
Jingyue Wu
committedJun 15, 2015
[ValueTracking] do not overwrite analysis results already computed
Summary: ValueTracking used to overwrite the analysis results computed from assumes and dominating conditions. This patch fixes this issue. Test Plan: test/Analysis/ValueTracking/assume.ll Reviewers: hfinkel, majnemer Reviewed By: majnemer Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D10283 llvm-svn: 239718
1 parent f3770d3 commit 12b0c28

File tree

3 files changed

+192
-146
lines changed

3 files changed

+192
-146
lines changed
 

‎llvm/lib/Analysis/ValueTracking.cpp

+160-146
Original file line numberDiff line numberDiff line change
@@ -551,12 +551,17 @@ static void computeKnownBitsFromTrueCondition(Value *V, ICmpInst *Cmp,
551551
}
552552
break;
553553
case ICmpInst::ICMP_EQ:
554-
if (LHS == V)
555-
computeKnownBits(RHS, KnownZero, KnownOne, DL, Depth + 1, Q);
556-
else if (RHS == V)
557-
computeKnownBits(LHS, KnownZero, KnownOne, DL, Depth + 1, Q);
558-
else
559-
llvm_unreachable("missing use?");
554+
{
555+
APInt KnownZeroTemp(BitWidth, 0), KnownOneTemp(BitWidth, 0);
556+
if (LHS == V)
557+
computeKnownBits(RHS, KnownZeroTemp, KnownOneTemp, DL, Depth + 1, Q);
558+
else if (RHS == V)
559+
computeKnownBits(LHS, KnownZeroTemp, KnownOneTemp, DL, Depth + 1, Q);
560+
else
561+
llvm_unreachable("missing use?");
562+
KnownZero |= KnownZeroTemp;
563+
KnownOne |= KnownOneTemp;
564+
}
560565
break;
561566
case ICmpInst::ICMP_ULE:
562567
if (LHS == V) {
@@ -936,147 +941,11 @@ static void computeKnownBitsFromAssume(Value *V, APInt &KnownZero,
936941
}
937942
}
938943

939-
/// Determine which bits of V are known to be either zero or one and return
940-
/// them in the KnownZero/KnownOne bit sets.
941-
///
942-
/// NOTE: we cannot consider 'undef' to be "IsZero" here. The problem is that
943-
/// we cannot optimize based on the assumption that it is zero without changing
944-
/// it to be an explicit zero. If we don't change it to zero, other code could
945-
/// optimized based on the contradictory assumption that it is non-zero.
946-
/// Because instcombine aggressively folds operations with undef args anyway,
947-
/// this won't lose us code quality.
948-
///
949-
/// This function is defined on values with integer type, values with pointer
950-
/// type, and vectors of integers. In the case
951-
/// where V is a vector, known zero, and known one values are the
952-
/// same width as the vector element, and the bit is set only if it is true
953-
/// for all of the elements in the vector.
954-
void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne,
955-
const DataLayout &DL, unsigned Depth, const Query &Q) {
956-
assert(V && "No Value?");
957-
assert(Depth <= MaxDepth && "Limit Search Depth");
944+
static void computeKnownBitsFromOperator(Operator *I, APInt &KnownZero,
945+
APInt &KnownOne, const DataLayout &DL,
946+
unsigned Depth, const Query &Q) {
958947
unsigned BitWidth = KnownZero.getBitWidth();
959948

960-
assert((V->getType()->isIntOrIntVectorTy() ||
961-
V->getType()->getScalarType()->isPointerTy()) &&
962-
"Not integer or pointer type!");
963-
assert((DL.getTypeSizeInBits(V->getType()->getScalarType()) == BitWidth) &&
964-
(!V->getType()->isIntOrIntVectorTy() ||
965-
V->getType()->getScalarSizeInBits() == BitWidth) &&
966-
KnownZero.getBitWidth() == BitWidth &&
967-
KnownOne.getBitWidth() == BitWidth &&
968-
"V, KnownOne and KnownZero should have same BitWidth");
969-
970-
if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
971-
// We know all of the bits for a constant!
972-
KnownOne = CI->getValue();
973-
KnownZero = ~KnownOne;
974-
return;
975-
}
976-
// Null and aggregate-zero are all-zeros.
977-
if (isa<ConstantPointerNull>(V) ||
978-
isa<ConstantAggregateZero>(V)) {
979-
KnownOne.clearAllBits();
980-
KnownZero = APInt::getAllOnesValue(BitWidth);
981-
return;
982-
}
983-
// Handle a constant vector by taking the intersection of the known bits of
984-
// each element. There is no real need to handle ConstantVector here, because
985-
// we don't handle undef in any particularly useful way.
986-
if (ConstantDataSequential *CDS = dyn_cast<ConstantDataSequential>(V)) {
987-
// We know that CDS must be a vector of integers. Take the intersection of
988-
// each element.
989-
KnownZero.setAllBits(); KnownOne.setAllBits();
990-
APInt Elt(KnownZero.getBitWidth(), 0);
991-
for (unsigned i = 0, e = CDS->getNumElements(); i != e; ++i) {
992-
Elt = CDS->getElementAsInteger(i);
993-
KnownZero &= ~Elt;
994-
KnownOne &= Elt;
995-
}
996-
return;
997-
}
998-
999-
// The address of an aligned GlobalValue has trailing zeros.
1000-
if (auto *GO = dyn_cast<GlobalObject>(V)) {
1001-
unsigned Align = GO->getAlignment();
1002-
if (Align == 0) {
1003-
if (auto *GVar = dyn_cast<GlobalVariable>(GO)) {
1004-
Type *ObjectType = GVar->getType()->getElementType();
1005-
if (ObjectType->isSized()) {
1006-
// If the object is defined in the current Module, we'll be giving
1007-
// it the preferred alignment. Otherwise, we have to assume that it
1008-
// may only have the minimum ABI alignment.
1009-
if (!GVar->isDeclaration() && !GVar->isWeakForLinker())
1010-
Align = DL.getPreferredAlignment(GVar);
1011-
else
1012-
Align = DL.getABITypeAlignment(ObjectType);
1013-
}
1014-
}
1015-
}
1016-
if (Align > 0)
1017-
KnownZero = APInt::getLowBitsSet(BitWidth,
1018-
countTrailingZeros(Align));
1019-
else
1020-
KnownZero.clearAllBits();
1021-
KnownOne.clearAllBits();
1022-
return;
1023-
}
1024-
1025-
if (Argument *A = dyn_cast<Argument>(V)) {
1026-
unsigned Align = A->getType()->isPointerTy() ? A->getParamAlignment() : 0;
1027-
1028-
if (!Align && A->hasStructRetAttr()) {
1029-
// An sret parameter has at least the ABI alignment of the return type.
1030-
Type *EltTy = cast<PointerType>(A->getType())->getElementType();
1031-
if (EltTy->isSized())
1032-
Align = DL.getABITypeAlignment(EltTy);
1033-
}
1034-
1035-
if (Align)
1036-
KnownZero = APInt::getLowBitsSet(BitWidth, countTrailingZeros(Align));
1037-
else
1038-
KnownZero.clearAllBits();
1039-
KnownOne.clearAllBits();
1040-
1041-
// Don't give up yet... there might be an assumption that provides more
1042-
// information...
1043-
computeKnownBitsFromAssume(V, KnownZero, KnownOne, DL, Depth, Q);
1044-
1045-
// Or a dominating condition for that matter
1046-
if (EnableDomConditions && Depth <= DomConditionsMaxDepth)
1047-
computeKnownBitsFromDominatingCondition(V, KnownZero, KnownOne, DL,
1048-
Depth, Q);
1049-
return;
1050-
}
1051-
1052-
// Start out not knowing anything.
1053-
KnownZero.clearAllBits(); KnownOne.clearAllBits();
1054-
1055-
// Limit search depth.
1056-
// All recursive calls that increase depth must come after this.
1057-
if (Depth == MaxDepth)
1058-
return;
1059-
1060-
// A weak GlobalAlias is totally unknown. A non-weak GlobalAlias has
1061-
// the bits of its aliasee.
1062-
if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
1063-
if (!GA->mayBeOverridden())
1064-
computeKnownBits(GA->getAliasee(), KnownZero, KnownOne, DL, Depth + 1, Q);
1065-
return;
1066-
}
1067-
1068-
// Check whether a nearby assume intrinsic can determine some known bits.
1069-
computeKnownBitsFromAssume(V, KnownZero, KnownOne, DL, Depth, Q);
1070-
1071-
// Check whether there's a dominating condition which implies something about
1072-
// this value at the given context.
1073-
if (EnableDomConditions && Depth <= DomConditionsMaxDepth)
1074-
computeKnownBitsFromDominatingCondition(V, KnownZero, KnownOne, DL, Depth,
1075-
Q);
1076-
1077-
Operator *I = dyn_cast<Operator>(V);
1078-
if (!I) return;
1079-
1080949
APInt KnownZero2(KnownZero), KnownOne2(KnownOne);
1081950
switch (I->getOpcode()) {
1082951
default: break;
@@ -1328,7 +1197,7 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne,
13281197
}
13291198

13301199
case Instruction::Alloca: {
1331-
AllocaInst *AI = cast<AllocaInst>(V);
1200+
AllocaInst *AI = cast<AllocaInst>(I);
13321201
unsigned Align = AI->getAlignment();
13331202
if (Align == 0)
13341203
Align = DL.getABITypeAlignment(AI->getType()->getElementType());
@@ -1523,6 +1392,151 @@ void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne,
15231392
}
15241393
}
15251394
}
1395+
}
1396+
1397+
/// Determine which bits of V are known to be either zero or one and return
1398+
/// them in the KnownZero/KnownOne bit sets.
1399+
///
1400+
/// NOTE: we cannot consider 'undef' to be "IsZero" here. The problem is that
1401+
/// we cannot optimize based on the assumption that it is zero without changing
1402+
/// it to be an explicit zero. If we don't change it to zero, other code could
1403+
/// optimized based on the contradictory assumption that it is non-zero.
1404+
/// Because instcombine aggressively folds operations with undef args anyway,
1405+
/// this won't lose us code quality.
1406+
///
1407+
/// This function is defined on values with integer type, values with pointer
1408+
/// type, and vectors of integers. In the case
1409+
/// where V is a vector, known zero, and known one values are the
1410+
/// same width as the vector element, and the bit is set only if it is true
1411+
/// for all of the elements in the vector.
1412+
void computeKnownBits(Value *V, APInt &KnownZero, APInt &KnownOne,
1413+
const DataLayout &DL, unsigned Depth, const Query &Q) {
1414+
assert(V && "No Value?");
1415+
assert(Depth <= MaxDepth && "Limit Search Depth");
1416+
unsigned BitWidth = KnownZero.getBitWidth();
1417+
1418+
assert((V->getType()->isIntOrIntVectorTy() ||
1419+
V->getType()->getScalarType()->isPointerTy()) &&
1420+
"Not integer or pointer type!");
1421+
assert((DL.getTypeSizeInBits(V->getType()->getScalarType()) == BitWidth) &&
1422+
(!V->getType()->isIntOrIntVectorTy() ||
1423+
V->getType()->getScalarSizeInBits() == BitWidth) &&
1424+
KnownZero.getBitWidth() == BitWidth &&
1425+
KnownOne.getBitWidth() == BitWidth &&
1426+
"V, KnownOne and KnownZero should have same BitWidth");
1427+
1428+
if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
1429+
// We know all of the bits for a constant!
1430+
KnownOne = CI->getValue();
1431+
KnownZero = ~KnownOne;
1432+
return;
1433+
}
1434+
// Null and aggregate-zero are all-zeros.
1435+
if (isa<ConstantPointerNull>(V) ||
1436+
isa<ConstantAggregateZero>(V)) {
1437+
KnownOne.clearAllBits();
1438+
KnownZero = APInt::getAllOnesValue(BitWidth);
1439+
return;
1440+
}
1441+
// Handle a constant vector by taking the intersection of the known bits of
1442+
// each element. There is no real need to handle ConstantVector here, because
1443+
// we don't handle undef in any particularly useful way.
1444+
if (ConstantDataSequential *CDS = dyn_cast<ConstantDataSequential>(V)) {
1445+
// We know that CDS must be a vector of integers. Take the intersection of
1446+
// each element.
1447+
KnownZero.setAllBits(); KnownOne.setAllBits();
1448+
APInt Elt(KnownZero.getBitWidth(), 0);
1449+
for (unsigned i = 0, e = CDS->getNumElements(); i != e; ++i) {
1450+
Elt = CDS->getElementAsInteger(i);
1451+
KnownZero &= ~Elt;
1452+
KnownOne &= Elt;
1453+
}
1454+
return;
1455+
}
1456+
1457+
// The address of an aligned GlobalValue has trailing zeros.
1458+
if (auto *GO = dyn_cast<GlobalObject>(V)) {
1459+
unsigned Align = GO->getAlignment();
1460+
if (Align == 0) {
1461+
if (auto *GVar = dyn_cast<GlobalVariable>(GO)) {
1462+
Type *ObjectType = GVar->getType()->getElementType();
1463+
if (ObjectType->isSized()) {
1464+
// If the object is defined in the current Module, we'll be giving
1465+
// it the preferred alignment. Otherwise, we have to assume that it
1466+
// may only have the minimum ABI alignment.
1467+
if (!GVar->isDeclaration() && !GVar->isWeakForLinker())
1468+
Align = DL.getPreferredAlignment(GVar);
1469+
else
1470+
Align = DL.getABITypeAlignment(ObjectType);
1471+
}
1472+
}
1473+
}
1474+
if (Align > 0)
1475+
KnownZero = APInt::getLowBitsSet(BitWidth,
1476+
countTrailingZeros(Align));
1477+
else
1478+
KnownZero.clearAllBits();
1479+
KnownOne.clearAllBits();
1480+
return;
1481+
}
1482+
1483+
if (Argument *A = dyn_cast<Argument>(V)) {
1484+
unsigned Align = A->getType()->isPointerTy() ? A->getParamAlignment() : 0;
1485+
1486+
if (!Align && A->hasStructRetAttr()) {
1487+
// An sret parameter has at least the ABI alignment of the return type.
1488+
Type *EltTy = cast<PointerType>(A->getType())->getElementType();
1489+
if (EltTy->isSized())
1490+
Align = DL.getABITypeAlignment(EltTy);
1491+
}
1492+
1493+
if (Align)
1494+
KnownZero = APInt::getLowBitsSet(BitWidth, countTrailingZeros(Align));
1495+
else
1496+
KnownZero.clearAllBits();
1497+
KnownOne.clearAllBits();
1498+
1499+
// Don't give up yet... there might be an assumption that provides more
1500+
// information...
1501+
computeKnownBitsFromAssume(V, KnownZero, KnownOne, DL, Depth, Q);
1502+
1503+
// Or a dominating condition for that matter
1504+
if (EnableDomConditions && Depth <= DomConditionsMaxDepth)
1505+
computeKnownBitsFromDominatingCondition(V, KnownZero, KnownOne, DL,
1506+
Depth, Q);
1507+
return;
1508+
}
1509+
1510+
// Start out not knowing anything.
1511+
KnownZero.clearAllBits(); KnownOne.clearAllBits();
1512+
1513+
// Limit search depth.
1514+
// All recursive calls that increase depth must come after this.
1515+
if (Depth == MaxDepth)
1516+
return;
1517+
1518+
// A weak GlobalAlias is totally unknown. A non-weak GlobalAlias has
1519+
// the bits of its aliasee.
1520+
if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
1521+
if (!GA->mayBeOverridden())
1522+
computeKnownBits(GA->getAliasee(), KnownZero, KnownOne, DL, Depth + 1, Q);
1523+
return;
1524+
}
1525+
1526+
if (Operator *I = dyn_cast<Operator>(V))
1527+
computeKnownBitsFromOperator(I, KnownZero, KnownOne, DL, Depth, Q);
1528+
// computeKnownBitsFromAssume and computeKnownBitsFromDominatingCondition
1529+
// strictly refines KnownZero and KnownOne. Therefore, we run them after
1530+
// computeKnownBitsFromOperator.
1531+
1532+
// Check whether a nearby assume intrinsic can determine some known bits.
1533+
computeKnownBitsFromAssume(V, KnownZero, KnownOne, DL, Depth, Q);
1534+
1535+
// Check whether there's a dominating condition which implies something about
1536+
// this value at the given context.
1537+
if (EnableDomConditions && Depth <= DomConditionsMaxDepth)
1538+
computeKnownBitsFromDominatingCondition(V, KnownZero, KnownOne, DL, Depth,
1539+
Q);
15261540

15271541
assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
15281542
}

‎llvm/test/Analysis/ValueTracking/assume.ll

+14
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
; RUN: opt < %s -instcombine -S | FileCheck %s
2+
3+
define i32 @assume_add(i32 %a, i32 %b) {
4+
; CHECK-LABEL: @assume_add(
5+
%1 = add i32 %a, %b
6+
%last_two_digits = and i32 %1, 3
7+
%2 = icmp eq i32 %last_two_digits, 0
8+
call void @llvm.assume(i1 %2)
9+
%3 = add i32 %1, 3
10+
; CHECK: %3 = or i32 %1, 3
11+
ret i32 %3
12+
}
13+
14+
declare void @llvm.assume(i1)

‎llvm/test/Analysis/ValueTracking/dom-cond.ll

+18
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
; RUN: opt < %s -instcombine -value-tracking-dom-conditions -S | FileCheck %s
2+
3+
define i32 @dom_cond(i32 %a, i32 %b) {
4+
; CHECK-LABEL: @dom_cond(
5+
entry:
6+
%v = add i32 %a, %b
7+
%cond = icmp ule i32 %v, 7
8+
br i1 %cond, label %then, label %exit
9+
10+
then:
11+
%v2 = add i32 %v, 8
12+
; CHECK: or i32 %v, 8
13+
br label %exit
14+
15+
exit:
16+
%v3 = phi i32 [ %v, %entry ], [ %v2, %then ]
17+
ret i32 %v3
18+
}

0 commit comments

Comments
 (0)
Please sign in to comment.