Index: lib/Transforms/Scalar/SCCP.cpp =================================================================== --- lib/Transforms/Scalar/SCCP.cpp +++ lib/Transforms/Scalar/SCCP.cpp @@ -90,6 +90,9 @@ /// asserting. forcedconstant, + /// This Value is known to not have the specified value. + notconstant, + /// overdefined - This instruction is not known to be constant, and we know /// it has a value. overdefined @@ -97,7 +100,7 @@ /// Val: This stores the current lattice value along with the Constant* for /// the constant if this is a 'constant' or 'forcedconstant' value. - PointerIntPair Val; + PointerIntPair Val; LatticeValueTy getLatticeValue() const { return Val.getInt(); @@ -112,6 +115,8 @@ return getLatticeValue() == constant || getLatticeValue() == forcedconstant; } + bool isNotConstant() const { return getLatticeValue() == notconstant; } + bool isOverdefined() const { return getLatticeValue() == overdefined; } Constant *getConstant() const { @@ -153,6 +158,19 @@ return true; } + bool markNotConstant(Constant *V) { + assert(V && "Marking constant with NULL"); + if (isa(V)) + return false; + + assert((!isNotConstant() || getNotConstant() == V) && + "Marking !constant with different value"); + assert(isUnknown() || isNotConstant()); + Val.setPointer(V); + Val.setInt(notconstant); + return true; + } + /// getConstantInt - If this is a constant with a ConstantInt value, return it /// otherwise return null. ConstantInt *getConstantInt() const { @@ -161,6 +179,11 @@ return nullptr; } + Constant *getNotConstant() const { + assert(isNotConstant() && "Cannot get the constant of a non-notconstant!"); + return Val.getPointer(); + } + /// getBlockAddress - If this is a constant with a BlockAddress value, return /// it, otherwise return null. BlockAddress *getBlockAddress() const { @@ -180,6 +203,8 @@ return ValueLatticeElement::getOverdefined(); if (isConstant()) return ValueLatticeElement::get(getConstant()); + if (isNotConstant()) + return ValueLatticeElement::getNot(getNotConstant()); return ValueLatticeElement(); } }; @@ -443,6 +468,14 @@ pushToWorkList(IV, V); } + bool markNotConstant(LatticeVal &IV, Value *V, Constant *C) { + if (!IV.markNotConstant(C)) + return false; + LLVM_DEBUG(dbgs() << "markNotConstant: " << *C << ": " << *V << '\n'); + pushToWorkList(IV, V); + return true; + } + // markOverdefined - Make a value be marked as "overdefined". If the // value is not already overdefined, add it to the overdefined instruction // work list so that the users of the instruction are updated later. @@ -463,11 +496,29 @@ return false; // Noop. if (MergeWithV.isOverdefined()) return markOverdefined(IV, V); - if (IV.isUnknown()) - return markConstant(IV, V, MergeWithV.getConstant()); - if (IV.getConstant() != MergeWithV.getConstant()) + + if (IV.isUnknown()) { + if (MergeWithV.isNotConstant()) + return markNotConstant(IV, V, MergeWithV.getNotConstant()); + else { + assert(MergeWithV.isConstant() && "Unexpected lattice value type"); + return markConstant(IV, V, MergeWithV.getConstant()); + } + } + + if (IV.isNotConstant()) { + if (MergeWithV.isNotConstant() && + IV.getNotConstant() == MergeWithV.getNotConstant()) + return false; return markOverdefined(IV, V); - return false; + } + + if (IV.isConstant()) { + if (MergeWithV.isConstant() && + IV.getConstant() == MergeWithV.getConstant()) + return false; + return markOverdefined(IV, V); + } } bool mergeInValue(Value *V, LatticeVal MergeWithV) { @@ -788,6 +839,9 @@ if (IV.isOverdefined()) // PHI node becomes overdefined! return (void)markOverdefined(&PN); + if (IV.isNotConstant()) + return (void)markOverdefined(&PN); + if (!OperandVal) { // Grab the first value. OperandVal = IV.getConstant(); continue; @@ -851,7 +905,8 @@ void SCCPSolver::visitCastInst(CastInst &I) { LatticeVal OpSt = getValueState(I.getOperand(0)); - if (OpSt.isOverdefined()) // Inherit overdefinedness of operand + if (OpSt.isOverdefined() || + OpSt.isNotConstant()) // Inherit overdefinedness of operand markOverdefined(&I); else if (OpSt.isConstant()) { // Fold the constant as we build. @@ -960,6 +1015,10 @@ LatticeVal &IV = ValueState[&I]; if (IV.isOverdefined()) return; + // TODO: could do better than that in some cases. + if (V1State.isNotConstant() || V2State.isNotConstant()) + return (void)markOverdefined(&I); + if (V1State.isConstant() && V2State.isConstant()) { Constant *C = ConstantExpr::get(I.getOpcode(), V1State.getConstant(), V2State.getConstant()); @@ -988,9 +1047,9 @@ if (I.getOpcode() == Instruction::And || I.getOpcode() == Instruction::Mul || I.getOpcode() == Instruction::Or) { LatticeVal *NonOverdefVal = nullptr; - if (!V1State.isOverdefined()) + if (!V1State.isOverdefined() && !V1State.isNotConstant()) NonOverdefVal = &V1State; - else if (!V2State.isOverdefined()) + else if (!V2State.isOverdefined() && !V2State.isNotConstant()) NonOverdefVal = &V2State; if (NonOverdefVal) { @@ -1067,7 +1126,7 @@ if (State.isUnknown()) return; // Operands are not resolved yet. - if (State.isOverdefined()) + if (State.isOverdefined() || State.isNotConstant()) return (void)markOverdefined(&I); assert(State.isConstant() && "Unknown state!"); @@ -1194,21 +1253,41 @@ LatticeVal OriginalVal = getValueState(CopyOf); LatticeVal EqVal = getValueState(CmpOp1); LatticeVal &IV = ValueState[I]; - if (PBranch->TrueEdge && Cmp->getPredicate() == CmpInst::ICMP_EQ) { - addAdditionalUser(CmpOp1, I); - if (OriginalVal.isConstant()) - mergeInValue(IV, I, OriginalVal); - else - mergeInValue(IV, I, EqVal); + if (OriginalVal.isConstant()) { + mergeInValue(IV, I, OriginalVal); return; } - if (!PBranch->TrueEdge && Cmp->getPredicate() == CmpInst::ICMP_NE) { - addAdditionalUser(CmpOp1, I); - if (OriginalVal.isConstant()) - mergeInValue(IV, I, OriginalVal); - else + + if (Cmp->getPredicate() == CmpInst::ICMP_EQ) { + if (PBranch->TrueEdge) { + addAdditionalUser(CmpOp1, I); mergeInValue(IV, I, EqVal); - return; + return; + } else { + if (EqVal.isConstant() && + (IV.isUnknown() || + (IV.isNotConstant() && + IV.getNotConstant() == EqVal.getConstant()))) { + addAdditionalUser(CmpOp1, I); + markNotConstant(IV, I, EqVal.getConstant()); + return; + } + } + } else if (Cmp->getPredicate() == CmpInst::ICMP_NE) { + if (!PBranch->TrueEdge) { + addAdditionalUser(CmpOp1, I); + mergeInValue(IV, I, EqVal); + return; + } else { + if (EqVal.isConstant() && + (IV.isUnknown() || + (IV.isNotConstant() && + IV.getNotConstant() == EqVal.getConstant()))) { + addAdditionalUser(CmpOp1, I); + markNotConstant(IV, I, EqVal.getConstant()); + return; + } + } } return (void)mergeInValue(IV, I, getValueState(PBranch->OriginalOp)); @@ -1236,9 +1315,9 @@ if (State.isUnknown()) return; // Operands are not resolved yet. - if (State.isOverdefined()) + if (State.isOverdefined() || State.isNotConstant()) return (void)markOverdefined(I); - assert(State.isConstant() && "Unknown state!"); + assert(State.isConstant()); Operands.push_back(State.getConstant()); } @@ -1701,8 +1780,9 @@ Constant *Const = nullptr; if (V->getType()->isStructTy()) { std::vector IVs = Solver.getStructLatticeValueFor(V); - if (llvm::any_of(IVs, - [](const LatticeVal &LV) { return LV.isOverdefined(); })) + if (llvm::any_of(IVs, [](const LatticeVal &LV) { + return LV.isOverdefined() || LV.isNotConstant(); + })) return false; std::vector ConstVals; auto *ST = dyn_cast(V->getType()); @@ -1715,7 +1795,7 @@ Const = ConstantStruct::get(ST, ConstVals); } else { const LatticeVal &IV = Solver.getLatticeValueFor(V); - if (IV.isOverdefined()) + if (IV.isOverdefined() || IV.isNotConstant()) return false; Const = IV.isConstant() ? IV.getConstant() : UndefValue::get(V->getType()); @@ -2102,7 +2182,8 @@ const DenseMap &RV = Solver.getTrackedRetVals(); for (const auto &I : RV) { Function *F = I.first; - if (I.second.isOverdefined() || F->getReturnType()->isVoidTy()) + if (!(I.second.isUnknown() || I.second.isConstant()) || + F->getReturnType()->isVoidTy()) continue; findReturnsToZap(*F, ReturnsToZap, Solver); } Index: test/Transforms/SCCP/ipsccp-notnull.ll =================================================================== --- /dev/null +++ test/Transforms/SCCP/ipsccp-notnull.ll @@ -0,0 +1,64 @@ +; RUN: opt < %s -ipsccp -S | FileCheck %s + +; CHECK-LABEL: @test3 +; CHECK-LABEL: if.else: +; CHECK: ret i1 true +define internal i1 @test3(i32 %a, i32 %b) { +entry: + %cond = icmp eq i32 %a, %b + br i1 %cond, label %if.then, label %if.else + +if.then: ; preds = %entry + ret i1 %cond + +if.else: ; preds = %if.then, %entry + %s = select i1 undef, i32 undef, i32 %b + %c = icmp ne i32 %a, %s + ret i1 %c +} + +; CHECK-LABEL: @test5 +; CHECK-LABEL: if.else: +; CHECK: ret i1 true +define internal i1 @test5(i32 %a, i32 %b) { +entry: + %cond = icmp eq i32 %a, 4 + br i1 %cond, label %if.then, label %if.else + +if.then: ; preds = %entry + ret i1 %cond + +if.else: ; preds = %if.then, %entry + %r1 = add i32 %b, %b + %c = icmp ne i32 %a, %r1 + ret i1 %c +} + +define i1 @main(i32 %a) { + %v1 = call i1 @test3(i32 %a, i32 1) + %v2 = call i1 @test5(i32 %a, i32 2) + %v3 = and i1 %v1, %v2 + ret i1 %v3 +} + +; Make sure we do not zap return values marked as not-constant. +define i64 @caller_zap(i64 %n) { +entry: + %call = call i64 @callee_zap(i64 %n) + ret i64 %call +} + +; CHECK-LABEL: @callee_zap +; CHECK-LABEL: if.end: +; CHECK-NEXT: ret i64 %num +define internal i64 @callee_zap(i64 %num) { +entry: + %cond = icmp eq i64 %num, 16 + br i1 %cond, label %if.then, label %if.end + +if.then: ; preds = %entry + unreachable + +if.end: ; preds = %entry + ret i64 %num +}