diff --git a/llvm/include/llvm/Analysis/ValueLattice.h b/llvm/include/llvm/Analysis/ValueLattice.h --- a/llvm/include/llvm/Analysis/ValueLattice.h +++ b/llvm/include/llvm/Analysis/ValueLattice.h @@ -29,7 +29,12 @@ /// producing instruction is dead. Caution: We use this as the starting /// state in our local meet rules. In this usage, it's taken to mean /// "nothing known yet". - undefined, + unknown, + + /// This Value is an UndefValue constant or produces undef. Undefined values + /// can be merged with constants (or single element constant ranges), + /// assuming all uses of the result will be replaced. + undef, /// This Value has a specific constant value. (For constant integers, /// constantrange is used instead. Integer typed constantexprs can appear @@ -60,14 +65,15 @@ public: // Const and Range are initialized on-demand. - ValueLatticeElement() : Tag(undefined) {} + ValueLatticeElement() : Tag(unknown) {} /// Custom destructor to ensure Range is properly destroyed, when the object /// is deallocated. ~ValueLatticeElement() { switch (Tag) { case overdefined: - case undefined: + case unknown: + case undef: case constant: case notconstant: break; @@ -79,7 +85,7 @@ /// Custom copy constructor, to ensure Range gets initialized when /// copying a constant range lattice element. - ValueLatticeElement(const ValueLatticeElement &Other) : Tag(undefined) { + ValueLatticeElement(const ValueLatticeElement &Other) : Tag(unknown) { *this = Other; } @@ -109,7 +115,8 @@ ConstVal = Other.ConstVal; break; case overdefined: - case undefined: + case unknown: + case undef: break; } Tag = Other.Tag; @@ -118,14 +125,16 @@ static ValueLatticeElement get(Constant *C) { ValueLatticeElement Res; - if (!isa(C)) + if (isa(C)) + Res.markUndef(); + else Res.markConstant(C); return Res; } static ValueLatticeElement getNot(Constant *C) { ValueLatticeElement Res; - if (!isa(C)) - Res.markNotConstant(C); + assert(!isa(C) && "!= undef is not supported"); + Res.markNotConstant(C); return Res; } static ValueLatticeElement getRange(ConstantRange CR) { @@ -139,8 +148,9 @@ return Res; } - bool isUndefined() const { return Tag == undefined; } - bool isUnknown() const { return Tag == undefined; } + bool isUndef() const { return Tag == undef; } + bool isUnknown() const { return Tag == unknown; } + bool isUnknownOrUndef() const { return Tag == unknown || Tag == undef; } bool isConstant() const { return Tag == constant; } bool isNotConstant() const { return Tag == notconstant; } bool isConstantRange() const { return Tag == constantrange; } @@ -182,9 +192,18 @@ return true; } + bool markUndef() { + if (isUndef()) + return false; + + assert(isUnknown()); + Tag = undef; + return true; + } + bool markConstant(Constant *V) { if (isa(V)) - return false; + return markUndef(); if (isConstant()) { assert(getConstant() == V && "Marking constant with different value"); @@ -194,7 +213,7 @@ if (ConstantInt *CI = dyn_cast(V)) return markConstantRange(ConstantRange(CI->getValue())); - assert(isUndefined()); + assert(isUnknown() || isUndef()); Tag = constant; ConstVal = V; return true; @@ -214,7 +233,7 @@ return false; } - assert(isUndefined()); + assert(isUnknown()); Tag = notconstant; ConstVal = V; return true; @@ -223,7 +242,7 @@ /// Mark the object as constant range with \p NewR. If the object is already a /// constant range, nothing changes if the existing range is equal to \p /// NewR. Otherwise \p NewR must be a superset of the existing range or the - /// object must be undefined. + /// object must be undef. bool markConstantRange(ConstantRange NewR) { if (isConstantRange()) { if (getConstantRange() == NewR) @@ -238,7 +257,7 @@ return true; } - assert(isUndefined()); + assert(isUnknown() || isUndef()); if (NewR.isEmptySet()) return markOverdefined(); @@ -250,21 +269,35 @@ /// Updates this object to approximate both this object and RHS. Returns /// true if this object has been changed. bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL) { - if (RHS.isUndefined() || isOverdefined()) + if (RHS.isUnknown() || isOverdefined()) return false; if (RHS.isOverdefined()) { markOverdefined(); return true; } - if (isUndefined()) { + if (isUndef()) { + assert(!RHS.isUnknown()); + if (RHS.isUndef()) + return false; + if (RHS.isConstant()) + return markConstant(RHS.getConstant()); + if (RHS.isConstantRange() && RHS.getConstantRange().isSingleElement()) + return markConstantRange(RHS.getConstantRange()); + return markOverdefined(); + } + + if (isUnknown()) { + assert(!RHS.isUnknown() && "Unknow RHS should be handled earlier"); *this = RHS; - return !RHS.isUndefined(); + return true; } if (isConstant()) { if (RHS.isConstant() && getConstant() == RHS.getConstant()) return false; + if (RHS.isUndef()) + return false; markOverdefined(); return true; } @@ -277,6 +310,9 @@ } assert(isConstantRange() && "New ValueLattice type?"); + if (RHS.isUndef() && getConstantRange().isSingleElement()) + return false; + if (!RHS.isConstantRange()) { // We can get here if we've encountered a constantexpr of integer type // and merge it with a constantrange. @@ -292,12 +328,12 @@ return markConstantRange(std::move(NewR)); } - /// Compares this symbolic value with Other using Pred and returns either + // Compares this symbolic value with Other using Pred and returns either /// true, false or undef constants, or nullptr if the comparison cannot be /// evaluated. Constant *getCompare(CmpInst::Predicate Pred, Type *Ty, const ValueLatticeElement &Other) const { - if (isUndefined() || Other.isUndefined()) + if (isUnknownOrUndef() || Other.isUnknownOrUndef()) return UndefValue::get(Ty); if (isConstant() && Other.isConstant()) diff --git a/llvm/lib/Analysis/LazyValueInfo.cpp b/llvm/lib/Analysis/LazyValueInfo.cpp --- a/llvm/lib/Analysis/LazyValueInfo.cpp +++ b/llvm/lib/Analysis/LazyValueInfo.cpp @@ -96,9 +96,9 @@ const ValueLatticeElement &B) { // Undefined is the strongest state. It means the value is known to be along // an unreachable path. - if (A.isUndefined()) + if (A.isUnknown()) return A; - if (B.isUndefined()) + if (B.isUnknown()) return B; // If we gave up for one, but got a useable fact from the other, use it. @@ -1203,7 +1203,7 @@ // false SETNE. if (isTrueDest == (Predicate == ICmpInst::ICMP_EQ)) return ValueLatticeElement::get(cast(RHS)); - else + else if (!isa(RHS)) return ValueLatticeElement::getNot(cast(RHS)); } } @@ -1722,7 +1722,7 @@ const DataLayout &DL = BB->getModule()->getDataLayout(); ValueLatticeElement Result = getImpl(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI); - if (Result.isUndefined()) + if (Result.isUnknown()) return ConstantRange::getEmpty(Width); if (Result.isConstantRange()) return Result.getConstantRange(); @@ -1761,7 +1761,7 @@ ValueLatticeElement Result = getImpl(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI); - if (Result.isUndefined()) + if (Result.isUnknown()) return ConstantRange::getEmpty(Width); if (Result.isConstantRange()) return Result.getConstantRange(); @@ -1991,7 +1991,7 @@ for (auto &Arg : F->args()) { ValueLatticeElement Result = LVIImpl->getValueInBlock( const_cast(&Arg), const_cast(BB)); - if (Result.isUndefined()) + if (Result.isUnknown()) continue; OS << "; LatticeVal for: '" << Arg << "' is: " << Result << "\n"; } diff --git a/llvm/lib/Analysis/ValueLattice.cpp b/llvm/lib/Analysis/ValueLattice.cpp --- a/llvm/lib/Analysis/ValueLattice.cpp +++ b/llvm/lib/Analysis/ValueLattice.cpp @@ -10,8 +10,10 @@ namespace llvm { raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val) { - if (Val.isUndefined()) - return OS << "undefined"; + if (Val.isUnknown()) + return OS << "unknown"; + if (Val.isUndef()) + return OS << "undef"; if (Val.isOverdefined()) return OS << "overdefined"; diff --git a/llvm/lib/Transforms/Scalar/SCCP.cpp b/llvm/lib/Transforms/Scalar/SCCP.cpp --- a/llvm/lib/Transforms/Scalar/SCCP.cpp +++ b/llvm/lib/Transforms/Scalar/SCCP.cpp @@ -434,19 +434,16 @@ if (!I.second) return LV; // Common case, already in the map. - if (auto *C = dyn_cast(V)) { - // Undef values remain unknown. - if (!isa(V)) - LV.markConstant(C); // Constants are constant - } + if (auto *C = dyn_cast(V)) + LV.markConstant(C); // Constants are constant - // All others are underdefined by default. + // All others are unknown by default. return LV; } LatticeVal toLatticeVal(const ValueLatticeElement &V, Type *T) { LatticeVal Res; - if (V.isUndefined()) + if (V.isUnknownOrUndef()) return Res; if (V.isConstant()) { @@ -621,7 +618,7 @@ if (!CI) { // Overdefined condition variables, and branches on unfoldable constant // conditions, mean the branch could go either way. - if (!BCValue.isUnknown()) + if (!BCValue.isUnknownOrUndef()) Succs[0] = Succs[1] = true; return; } @@ -647,7 +644,7 @@ if (!CI) { // Overdefined or unknown condition? // All destinations are executable! - if (!SCValue.isUnknown()) + if (!SCValue.isUnknownOrUndef()) Succs.assign(TI.getNumSuccessors(), true); return; } @@ -664,7 +661,7 @@ BlockAddress *Addr = dyn_cast_or_null(getConstant(IBRValue)); if (!Addr) { // Overdefined or unknown condition? // All destinations are executable! - if (!IBRValue.isUnknown()) + if (!IBRValue.isUnknownOrUndef()) Succs.assign(TI.getNumSuccessors(), true); return; } @@ -745,7 +742,7 @@ Constant *OperandVal = nullptr; for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) { LatticeVal IV = getValueState(PN.getIncomingValue(i)); - if (IV.isUnknown()) continue; // Doesn't influence PHI node. + if (IV.isUnknownOrUndef()) continue; // Doesn't influence PHI node. if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent())) continue; @@ -833,7 +830,7 @@ return; // Propagate constant value markConstant(&I, C); - } else if (!OpSt.isUnknown()) + } else if (!OpSt.isUnknownOrUndef()) markOverdefined(&I); } @@ -913,7 +910,7 @@ return; LatticeVal CondValue = getValueState(I.getCondition()); - if (CondValue.isUnknown()) + if (CondValue.isUnknownOrUndef()) return; if (ConstantInt *CondCB = getConstantInt(CondValue)) { @@ -933,9 +930,9 @@ getConstant(TVal) == getConstant(FVal)) return (void)markConstant(&I, getConstant(FVal)); - if (TVal.isUnknown()) // select ?, undef, X -> X. + if (TVal.isUnknownOrUndef()) // select ?, undef, X -> X. return (void)mergeInValue(&I, FVal); - if (FVal.isUnknown()) // select ?, X, undef -> X. + if (FVal.isUnknownOrUndef()) // select ?, X, undef -> X. return (void)mergeInValue(&I, TVal); markOverdefined(&I); } @@ -986,7 +983,7 @@ } // If something is undef, wait for it to resolve. - if (V1State.isUnknown() || V2State.isUnknown()) + if (V1State.isUnknownOrUndef() || V2State.isUnknownOrUndef()) return; // Otherwise, one of our operands is overdefined. Try to produce something @@ -1010,7 +1007,7 @@ else if (!isOverdefined(V2State)) NonOverdefVal = &V2State; if (NonOverdefVal) { - if (NonOverdefVal->isUnknown()) + if (!isConstant(*NonOverdefVal)) return; if (I.getOpcode() == Instruction::And || @@ -1059,7 +1056,7 @@ } // If operands are still unknown, wait for it to resolve. - if ((V1State.isUnknown() || V2State.isUnknown()) && + if ((V1State.isUnknownOrUndef() || V2State.isUnknownOrUndef()) && !isConstant(ValueState[&I])) return; @@ -1076,7 +1073,7 @@ for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { LatticeVal State = getValueState(I.getOperand(i)); - if (State.isUnknown()) + if (State.isUnknownOrUndef()) return; // Operands are not resolved yet. if (isOverdefined(State)) @@ -1136,7 +1133,8 @@ return; LatticeVal PtrVal = getValueState(I.getOperand(0)); - if (PtrVal.isUnknown()) return; // The pointer is not resolved yet! + if (PtrVal.isUnknownOrUndef()) + return; // The pointer is not resolved yet! LatticeVal &IV = ValueState[&I]; @@ -1260,7 +1258,7 @@ return markOverdefined(I); // Can't handle struct args. LatticeVal State = getValueState(*AI); - if (State.isUnknown()) + if (State.isUnknownOrUndef()) return; // Operands are not resolved yet. if (isOverdefined(State)) return (void)markOverdefined(I); @@ -1427,14 +1425,14 @@ // more precise than this but it isn't worth bothering. for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { LatticeVal &LV = getStructValueState(&I, i); - if (LV.isUnknown()) + if (LV.isUnknownOrUndef()) markOverdefined(LV, &I); } continue; } LatticeVal &LV = getValueState(&I); - if (!LV.isUnknown()) + if (!LV.isUnknownOrUndef()) continue; // There are two reasons a call can have an undef result @@ -1464,7 +1462,7 @@ Instruction *TI = BB.getTerminator(); if (auto *BI = dyn_cast(TI)) { if (!BI->isConditional()) continue; - if (!getValueState(BI->getCondition()).isUnknown()) + if (!getValueState(BI->getCondition()).isUnknownOrUndef()) continue; // If the input to SCCP is actually branch on undef, fix the undef to @@ -1492,7 +1490,7 @@ if (IBR->getNumSuccessors() < 1) continue; - if (!getValueState(IBR->getAddress()).isUnknown()) + if (!getValueState(IBR->getAddress()).isUnknownOrUndef()) continue; // If the input to SCCP is actually branch on undef, fix the undef to @@ -1516,7 +1514,8 @@ } if (auto *SI = dyn_cast(TI)) { - if (!SI->getNumCases() || !getValueState(SI->getCondition()).isUnknown()) + if (!SI->getNumCases() || + !getValueState(SI->getCondition()).isUnknownOrUndef()) continue; // If the input to SCCP is actually switch on undef, fix the undef to diff --git a/llvm/test/Transforms/CorrelatedValuePropagation/merge-range-and-undef.ll b/llvm/test/Transforms/CorrelatedValuePropagation/merge-range-and-undef.ll --- a/llvm/test/Transforms/CorrelatedValuePropagation/merge-range-and-undef.ll +++ b/llvm/test/Transforms/CorrelatedValuePropagation/merge-range-and-undef.ll @@ -47,7 +47,8 @@ ; CHECK-NEXT: br label [[BB3]] ; CHECK: bb3: ; CHECK-NEXT: [[P:%.*]] = phi i64 [ undef, [[BB1]] ], [ [[R]], [[BB2]] ] -; CHECK-NEXT: ret i64 [[P]] +; CHECK-NEXT: [[RES:%.*]] = and i64 [[P]], 255 +; CHECK-NEXT: ret i64 [[RES]] ; entry: br i1 %cond, label %bb1, label %bb2 @@ -70,7 +71,7 @@ ; CHECK-NEXT: entry: ; CHECK-NEXT: br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]] ; CHECK: bb1: -; CHECK-NEXT: [[V1:%.*]] = add nuw nsw i64 undef, undef +; CHECK-NEXT: [[V1:%.*]] = add i64 undef, undef ; CHECK-NEXT: br label [[BB3:%.*]] ; CHECK: bb2: ; CHECK-NEXT: [[V2:%.*]] = and i64 [[A:%.*]], 255 @@ -161,7 +162,8 @@ ; CHECK-NEXT: br label [[BB4]] ; CHECK: bb4: ; CHECK-NEXT: [[P:%.*]] = phi i64 [ [[R]], [[BB1]] ], [ 10, [[BB2]] ], [ undef, [[BB3]] ] -; CHECK-NEXT: ret i64 [[P]] +; CHECK-NEXT: [[RES:%.*]] = and i64 [[P]], 255 +; CHECK-NEXT: ret i64 [[RES]] ; entry: br i1 %c1, label %bb1, label %bb2 @@ -233,7 +235,8 @@ ; CHECK-NEXT: br label [[BB4]] ; CHECK: bb4: ; CHECK-NEXT: [[P:%.*]] = phi i64 [ [[R]], [[BB1]] ], [ undef, [[BB2]] ], [ 10, [[BB3]] ] -; CHECK-NEXT: ret i64 [[P]] +; CHECK-NEXT: [[RES:%.*]] = and i64 [[P]], 255 +; CHECK-NEXT: ret i64 [[RES]] ; entry: br i1 %c1, label %bb1, label %bb2 diff --git a/llvm/test/Transforms/JumpThreading/ne-undef.ll b/llvm/test/Transforms/JumpThreading/ne-undef.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/JumpThreading/ne-undef.ll @@ -0,0 +1,61 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -jump-threading -S %s | FileCheck %s + +declare i1 @cond() + +define hidden void @hoge(i1 %c1, i32 %x) { +; CHECK-LABEL: @hoge( +; CHECK-NEXT: bb: +; CHECK-NEXT: br label [[BB13:%.*]] +; CHECK: bb4: +; CHECK-NEXT: [[TMP3:%.*]] = icmp ne i32 [[TMP7:%.*]], undef +; CHECK-NEXT: br i1 [[TMP3]], label [[BB5:%.*]], label [[BB13]] +; CHECK: bb5: +; CHECK-NEXT: br label [[BB6:%.*]] +; CHECK: bb6: +; CHECK-NEXT: [[TMP7]] = phi i32 [ [[TMP7]], [[BB5]] ], [ [[X:%.*]], [[BB8:%.*]] ] +; CHECK-NEXT: [[C:%.*]] = call i1 @cond() +; CHECK-NEXT: br i1 [[C]], label [[BB4:%.*]], label [[BB8]] +; CHECK: bb8: +; CHECK-NEXT: br label [[BB6]] +; CHECK: bb13: +; CHECK-NEXT: ret void +; +bb: + br i1 false, label %bb1, label %bb13 + +bb1: ; preds = %bb + br label %bb2 + +bb2: ; preds = %bb12, %bb1 + %tmp = phi i32 [ 10, %bb1 ], [ %tmp7, %bb12 ] + %tmp3 = icmp ne i32 %tmp, undef + br label %bb4 + +bb4: ; preds = %bb2 + br i1 %tmp3, label %bb5, label %bb13 + +bb5: ; preds = %bb4 + br label %bb6 + +bb6: ; preds = %bb8, %bb5 + %tmp7 = phi i32 [ %tmp, %bb5 ], [ %x, %bb8 ] + %c = call i1 @cond() + br i1 %c, label %bb9, label %bb8 + +bb8: ; preds = %bb6 + br label %bb6 + +bb9: ; preds = %bb6 + br label %bb10 + +bb10: ; preds = %bb9 + br label %bb12 + +bb12: ; preds = %bb10 + br label %bb2 + +bb13: ; preds = %bb4 + ret void + +} diff --git a/llvm/test/Transforms/SCCP/float-phis.ll b/llvm/test/Transforms/SCCP/float-phis.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/SCCP/float-phis.ll @@ -0,0 +1,26 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -sccp -S | FileCheck %s + +declare void @use(i1) + +define void @test(i1 %c) { +; CHECK-LABEL: @test( +; CHECK-NEXT: br label [[DO_BODY:%.*]] +; CHECK: do.body: +; CHECK-NEXT: br i1 [[C:%.*]], label [[DO_BODY]], label [[FOR_COND41:%.*]] +; CHECK: for.cond41: +; CHECK-NEXT: call void @use(i1 true) +; CHECK-NEXT: br label [[FOR_COND41]] +; + br label %do.body + +do.body: ; preds = %do.body, %entry + br i1 %c, label %do.body, label %for.cond41 + +for.cond41: ; preds = %for.cond41, %do.body + %mid.0 = phi float [ 0.000000e+00, %for.cond41 ], [ undef, %do.body ] + %fc = fcmp oeq float %mid.0, 0.000000e+00 + call void @use(i1 %fc) + + br label %for.cond41 +} diff --git a/llvm/test/Transforms/SCCP/int-phis.ll b/llvm/test/Transforms/SCCP/int-phis.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/SCCP/int-phis.ll @@ -0,0 +1,61 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -sccp -S | FileCheck %s + +declare void @use(i1) + +define void @read_dmatrix() #0 { +; CHECK-LABEL: @read_dmatrix( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[HEIGHT:%.*]] = alloca i32, align 4 +; CHECK-NEXT: br label [[FOR_COND:%.*]] +; CHECK: for.cond: +; CHECK-NEXT: [[TMP0:%.*]] = load i32, i32* [[HEIGHT]], align 4 +; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 0, [[TMP0]] +; CHECK-NEXT: br i1 [[CMP]], label [[FOR_COND6:%.*]], label [[FOR_END16:%.*]] +; CHECK: for.cond6: +; CHECK-NEXT: br label [[FOR_COND]] +; CHECK: for.end16: +; CHECK-NEXT: ret void +; +entry: + %height = alloca i32, align 4 + br label %for.cond + +for.cond: ; preds = %for.cond6, %entry + %j.0 = phi i32 [ undef, %entry ], [ 0, %for.cond6 ] + %0 = load i32, i32* %height, align 4 + %cmp = icmp slt i32 0, %0 + br i1 %cmp, label %for.cond6, label %for.end16 + +for.cond6: ; preds = %for.cond + br label %for.cond + +for.end16: ; preds = %for.cond + %sub21 = sub nsw i32 %j.0, 1 + ret void +} + +declare i1 @cond() + +define void @emptyTT() #0 { +; CHECK-LABEL: @emptyTT( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[FOR_COND:%.*]] +; CHECK: for.cond: +; CHECK-NEXT: [[C:%.*]] = call i1 @cond() +; CHECK-NEXT: br i1 [[C]], label [[FOR_COND]], label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + br label %for.cond + +for.cond: ; preds = %for.cond, %entry + %.compoundliteral.sroa.0.0 = phi i64 [ undef, %entry ], [ 0, %for.cond ] + %bf.clear = and i64 %.compoundliteral.sroa.0.0, -67108864 + %c = call i1 @cond() + br i1 %c, label %for.cond, label %exit + +exit: + ret void +}