Index: docs/LangRef.rst =================================================================== --- docs/LangRef.rst +++ docs/LangRef.rst @@ -3025,6 +3025,24 @@ the same as those for the corresponding instruction (e.g. no bitwise operations on floating point values are allowed). +.. _unreachableconstants: + +Unreachable Constants +--------------------- + +Unreachable constants are used to indicate that the evaluation of a constant +expression would trap. An instruction that produces an unreachable constant +has no defined semantics. + +Ordinarily an instruction produces unreachable if it has an unreachable +operand, but there are some exceptions. A select instruction whose condition +does not select an unreachable does not produce an unreachable, similarly a PHI +node that does not select an unreachable. A load instruction may have no +unreachable constant operands, but still produce an unreachable constant either +by being a provably invalid load, or by loading a global holding an unreachable +constant itself. An unreachable constant may be a single member in an aggregate +value without making the whole value unreachable. + Other Values ============ Index: include/llvm/Bitcode/LLVMBitCodes.h =================================================================== --- include/llvm/Bitcode/LLVMBitCodes.h +++ include/llvm/Bitcode/LLVMBitCodes.h @@ -276,8 +276,9 @@ CST_CODE_CE_INBOUNDS_GEP = 20, // INBOUNDS_GEP: [n x operands] CST_CODE_BLOCKADDRESS = 21, // CST_CODE_BLOCKADDRESS [fnty, fnval, bb#] CST_CODE_DATA = 22, // DATA: [n x elements] - CST_CODE_INLINEASM = 23 // INLINEASM: [sideeffect|alignstack| + CST_CODE_INLINEASM = 23, // INLINEASM: [sideeffect|alignstack| // asmdialect,asmstr,conststr] + CST_CODE_UNREACHABLE = 24 // UNREACHABLE }; /// CastOpcodes - These are values used in the bitcode files to encode which Index: include/llvm/IR/Constants.h =================================================================== --- include/llvm/IR/Constants.h +++ include/llvm/IR/Constants.h @@ -32,10 +32,10 @@ class ArrayType; class IntegerType; +class SequentialType; class StructType; class PointerType; class VectorType; -class SequentialType; struct ConstantExprKeyType; template struct ConstantAggrKeyType; @@ -1223,11 +1223,11 @@ /// Static factory methods - Return an 'undef' object of the specified type. static UndefValue *get(Type *T); - /// If this Undef has array or vector type, return a undef with the right + /// If this Undef has array or vector type, return an undef with the right /// element type. UndefValue *getSequentialElement() const; - /// If this undef has struct type, return a undef with the right element type + /// If this undef has struct type, return an undef with the right element type /// for the specified element. UndefValue *getStructElement(unsigned Elt) const; @@ -1246,6 +1246,54 @@ } }; +//===----------------------------------------------------------------------===// +/// 'unreachable' values are placeholders for computations that not only have +/// no result, but are guaranteed never execute in any run of the program. +/// These are used for a variety of purposes, including global variable +/// initializers and operands to instructions. 'unreachable' values can occur +/// with any first-class type. +/// +/// Unreachable values aren't exactly constants, they represent a property of +/// the control flow graph, but can be used in algorithms that operate strictly +/// as data flow problems. See LangRef.html#unreachablevalues for details. +/// +class UnreachableValue : public ConstantData { + UnreachableValue(const UnreachableValue &) = delete; + + friend class Constant; + void destroyConstantImpl(); + +protected: + explicit UnreachableValue(Type *T) : ConstantData(T, UnreachableValueVal) {} + +public: + /// Static factory methods - Return an 'unreachable' object of the specified + /// type. + static UnreachableValue *get(Type *T); + + /// If this Unreachable has array or vector type, return an unreachable with + /// the right element type. + UnreachableValue *getSequentialElement() const; + + /// If this unreachable has struct type, return an unreachable with the right + /// element type for the specified element. + UnreachableValue *getStructElement(unsigned Elt) const; + + /// Return an unreachable of the right value for the specified GEP index. + UnreachableValue *getElementValue(Constant *C) const; + + /// Return an unreachable of the right value for the specified GEP index. + UnreachableValue *getElementValue(unsigned Idx) const; + + /// Return the number of elements in the array, vector, or struct. + unsigned getNumElements() const; + + /// Methods for support type inquiry through isa, cast, and dyn_cast: + static bool classof(const Value *V) { + return V->getValueID() == UnreachableValueVal; + } +}; + } // End llvm namespace #endif Index: include/llvm/IR/PatternMatch.h =================================================================== --- include/llvm/IR/PatternMatch.h +++ include/llvm/IR/PatternMatch.h @@ -76,6 +76,9 @@ return class_match(); } +/// \brief Match an arbitrary unreachable constant. +inline class_match m_Unreachable() { return class_match(); } + /// \brief Match an arbitrary undef constant. inline class_match m_Undef() { return class_match(); } Index: include/llvm/IR/Value.def =================================================================== --- include/llvm/IR/Value.def +++ include/llvm/IR/Value.def @@ -76,6 +76,7 @@ HANDLE_CONSTANT(ConstantFP) HANDLE_CONSTANT(ConstantPointerNull) HANDLE_CONSTANT(ConstantTokenNone) +HANDLE_CONSTANT(UnreachableValue) HANDLE_METADATA_VALUE(MetadataAsValue) HANDLE_INLINE_ASM_VALUE(InlineAsm) @@ -85,9 +86,9 @@ // don't add new values here! HANDLE_CONSTANT_MARKER(ConstantFirstVal, Function) -HANDLE_CONSTANT_MARKER(ConstantLastVal, ConstantTokenNone) +HANDLE_CONSTANT_MARKER(ConstantLastVal, UnreachableValue) HANDLE_CONSTANT_MARKER(ConstantDataFirstVal, UndefValue) -HANDLE_CONSTANT_MARKER(ConstantDataLastVal, ConstantTokenNone) +HANDLE_CONSTANT_MARKER(ConstantDataLastVal, UnreachableValue) #undef HANDLE_GLOBAL_VALUE #undef HANDLE_CONSTANT Index: lib/Analysis/InstructionSimplify.cpp =================================================================== --- lib/Analysis/InstructionSimplify.cpp +++ lib/Analysis/InstructionSimplify.cpp @@ -325,9 +325,9 @@ return TV; // If one branch simplified to undef, return the other one. - if (TV && isa(TV)) + if (TV && (isa(TV) || isa(TV))) return FV; - if (FV && isa(FV)) + if (FV && (isa(FV) || isa(FV))) return TV; // If applying the operation did not change the true and false select values, @@ -535,6 +535,10 @@ std::swap(Op0, Op1); } + // X + unreachable -> unreachable + if (match(Op1, m_Unreachable())) + return Op1; + // X + undef -> undef if (match(Op1, m_Undef())) return Op1; @@ -660,6 +664,11 @@ if (Constant *CRHS = dyn_cast(Op1)) return ConstantFoldBinaryOpOperands(Instruction::Sub, CLHS, CRHS, Q.DL); + // X - unreachable -> unreachable + // unreachable - X -> unreachable + if (match(Op0, m_Unreachable()) || match(Op1, m_Unreachable())) + return UnreachableValue::get(Op0->getType()); + // X - undef -> undef // undef - X -> undef if (match(Op0, m_Undef()) || match(Op1, m_Undef())) @@ -886,6 +895,10 @@ std::swap(Op0, Op1); } + // X * unreachable -> unreachable + if (match(Op1, m_Unreachable())) + return UnreachableValue::get(Op0->getType()); + // X * undef -> 0 if (match(Op1, m_Undef())) return Constant::getNullValue(Op0->getType()); @@ -981,13 +994,16 @@ bool isSigned = Opcode == Instruction::SDiv; - // X / undef -> undef - if (match(Op1, m_Undef())) - return Op1; - - // X / 0 -> undef, we don't need to preserve faults! - if (match(Op1, m_Zero())) - return UndefValue::get(Op1->getType()); + // X / unreachable -> unreachable + // X / undef -> unreachable + // X / 0 -> unreachable + if (match(Op1, m_Unreachable()) || match(Op1, m_Undef()) || + match(Op1, m_Zero())) + return UnreachableValue::get(Op1->getType()); + + // unreachable / X -> unreachable + if (match(Op0, m_Unreachable())) + return UnreachableValue::get(Op1->getType()); // undef / X -> 0 if (match(Op0, m_Undef())) @@ -1092,6 +1108,11 @@ static Value *SimplifyFDivInst(Value *Op0, Value *Op1, FastMathFlags FMF, const Query &Q, unsigned) { + // unreachable / X -> unreachable + // X / unreachable -> unreachable + if (match(Op0, m_Unreachable()) || match(Op1, m_Unreachable())) + return UnreachableValue::get(Op0->getType()); + // undef / X -> undef (the undef could be a snan). if (match(Op0, m_Undef())) return Op0; @@ -1141,9 +1162,14 @@ if (Constant *C1 = dyn_cast(Op1)) return ConstantFoldBinaryOpOperands(Opcode, C0, C1, Q.DL); - // X % undef -> undef - if (match(Op1, m_Undef())) - return Op1; + // X % unreachable -> unreachable + // X % undef -> unreachable + if (match(Op1, m_Undef()) || match(Op1, m_Unreachable())) + return UnreachableValue::get(Op0->getType()); + + // unreachable % X -> unreachable + if (match(Op0, m_Undef())) + return UnreachableValue::get(Op0->getType()); // undef % X -> 0 if (match(Op0, m_Undef())) @@ -1153,9 +1179,9 @@ if (match(Op0, m_Zero())) return Op0; - // X % 0 -> undef, we don't need to preserve faults! + // X % 0 -> unreachable if (match(Op1, m_Zero())) - return UndefValue::get(Op0->getType()); + return UnreachableValue::get(Op0->getType()); // X % 1 -> 0 if (match(Op1, m_One())) @@ -1539,6 +1565,11 @@ std::swap(Op0, Op1); } + // unreachable & X -> unreachable + // X & unreachable -> unreachable + if (match(Op0, m_Unreachable()) || match(Op1, m_Unreachable())) + return UnreachableValue::get(Op0->getType()); + // X & undef -> 0 if (match(Op1, m_Undef())) return Constant::getNullValue(Op0->getType()); @@ -1695,6 +1726,11 @@ std::swap(Op0, Op1); } + // X | unreachable -> unreachable + // unreachable | X -> unreachable + if (match(Op0, m_Unreachable()) || match(Op1, m_Unreachable())) + return UnreachableValue::get(Op0->getType()); + // X | undef -> -1 if (match(Op1, m_Undef())) return Constant::getAllOnesValue(Op0->getType()); @@ -1828,6 +1864,11 @@ std::swap(Op0, Op1); } + // A ^ unreachable -> unreachable + // unreachable ^ A -> unreachable + if (match(Op0, m_Unreachable()) || match(Op1, m_Unreachable())) + return UnreachableValue::get(Op0->getType()); + // A ^ undef -> undef if (match(Op1, m_Undef())) return Op1; @@ -2106,6 +2147,10 @@ Type *ITy = GetCompareTy(LHS); // The return type. Type *OpTy = LHS->getType(); // The operand type. + // icmp X, unreachable -> unreachable + if (isa(RHS)) + return UnreachableValue::get(ITy); + // icmp X, X -> true/false // X icmp undef -> true/false. For example, icmp ugt %X, undef -> false // because X could be 0. @@ -3285,6 +3330,10 @@ return FalseVal; } + // select unreachable, X, Y, -> unreachable + if (isa(CondVal)) + return UnreachableValue::get(TrueVal->getType()); + // select C, X, X -> X if (TrueVal == FalseVal) return TrueVal; @@ -3294,9 +3343,13 @@ return TrueVal; return FalseVal; } - if (isa(TrueVal)) // select C, undef, X -> X + // select C, undef, X -> X + // select C, unreachable, X -> X + if (isa(TrueVal) || isa(TrueVal)) return FalseVal; - if (isa(FalseVal)) // select C, X, undef -> X + // select C, X, undef -> X + // select C, X, unreachable -> X + if (isa(FalseVal) || isa(TrueVal)) return TrueVal; if (const auto *ICI = dyn_cast(CondVal)) { @@ -3427,6 +3480,9 @@ if (VectorType *VT = dyn_cast(Ops[0]->getType())) GEPTy = VectorType::get(GEPTy, VT->getNumElements()); + if (isa(Ops[0])) + return UnreachableValue::get(GEPTy); + if (isa(Ops[0])) return UndefValue::get(GEPTy); @@ -3511,6 +3567,10 @@ if (Constant *CVal = dyn_cast(Val)) return ConstantFoldInsertValueInstruction(CAgg, CVal, Idxs); + // insertvalue unreachable, x, n -> unreachable + if (match(Agg, m_Unreachable())) + return Agg; + // insertvalue x, undef, n -> x if (match(Val, m_Undef())) return Agg; @@ -3588,6 +3648,9 @@ if (isa(Vec)) return UndefValue::get(Vec->getType()->getVectorElementType()); + + if (isa(Vec)) + return UnreachableValue::get(Vec->getType()->getVectorElementType()); } // If extracting a specified index from the vector, see if we can recursively Index: lib/AsmParser/LLLexer.cpp =================================================================== --- lib/AsmParser/LLLexer.cpp +++ lib/AsmParser/LLLexer.cpp @@ -522,6 +522,7 @@ KEYWORD(localexec); KEYWORD(zeroinitializer); KEYWORD(undef); + KEYWORD(unreachable); KEYWORD(null); KEYWORD(none); KEYWORD(to); Index: lib/AsmParser/LLParser.h =================================================================== --- lib/AsmParser/LLParser.h +++ lib/AsmParser/LLParser.h @@ -49,7 +49,7 @@ t_LocalID, t_GlobalID, // ID in UIntVal. t_LocalName, t_GlobalName, // Name in StrVal. t_APSInt, t_APFloat, // Value in APSIntVal/APFloatVal. - t_Null, t_Undef, t_Zero, t_None, // No value. + t_Null, t_Unreachable, t_Undef, t_Zero, t_None, // No value. t_EmptyArray, // No value: [] t_Constant, // Value in ConstantVal. t_InlineAsm, // Value in FTy/StrVal/StrVal2/UIntVal. Index: lib/AsmParser/LLParser.cpp =================================================================== --- lib/AsmParser/LLParser.cpp +++ lib/AsmParser/LLParser.cpp @@ -2597,6 +2597,7 @@ break; case lltok::kw_null: ID.Kind = ValID::t_Null; break; case lltok::kw_undef: ID.Kind = ValID::t_Undef; break; + case lltok::kw_unreachable: ID.Kind = ValID::t_Unreachable; break; case lltok::kw_zeroinitializer: ID.Kind = ValID::t_Zero; break; case lltok::kw_none: ID.Kind = ValID::t_None; break; @@ -4291,6 +4292,12 @@ return Error(ID.Loc, "invalid type for undef constant"); V = UndefValue::get(Ty); return false; + case ValID::t_Unreachable: + // FIXME: LabelTy should not be a first-class type. + if (!Ty->isFirstClassType() || Ty->isLabelTy()) + return Error(ID.Loc, "invalid type for unreachable constant"); + V = UnreachableValue::get(Ty); + return false; case ValID::t_EmptyArray: if (!Ty->isArrayTy() || cast(Ty)->getNumElements() != 0) return Error(ID.Loc, "invalid empty array initializer"); @@ -4347,6 +4354,7 @@ case ValID::t_APSInt: case ValID::t_APFloat: case ValID::t_Undef: + case ValID::t_Unreachable: case ValID::t_Constant: case ValID::t_ConstantStruct: case ValID::t_PackedConstantStruct: { Index: lib/Bitcode/Reader/BitcodeReader.cpp =================================================================== --- lib/Bitcode/Reader/BitcodeReader.cpp +++ lib/Bitcode/Reader/BitcodeReader.cpp @@ -3021,6 +3021,9 @@ V = BlockAddress::get(Fn, BB); break; } + case bitc::CST_CODE_UNREACHABLE: + V = UnreachableValue::get(CurTy); + break; } ValueList.assignValue(V, NextCstNo); Index: lib/Bitcode/Writer/BitcodeWriter.cpp =================================================================== --- lib/Bitcode/Writer/BitcodeWriter.cpp +++ lib/Bitcode/Writer/BitcodeWriter.cpp @@ -1629,6 +1629,8 @@ Code = bitc::CST_CODE_NULL; } else if (isa(C)) { Code = bitc::CST_CODE_UNDEF; + } else if (isa(C)) { + Code = bitc::CST_CODE_UNREACHABLE; } else if (const ConstantInt *IV = dyn_cast(C)) { if (IV->getBitWidth() <= 64) { uint64_t V = IV->getSExtValue(); Index: lib/IR/AsmWriter.cpp =================================================================== --- lib/IR/AsmWriter.cpp +++ lib/IR/AsmWriter.cpp @@ -1303,6 +1303,11 @@ return; } + if (isa(CV)) { + Out << "unreachable"; + return; + } + if (const ConstantExpr *CE = dyn_cast(CV)) { Out << CE->getOpcodeName(); WriteOptimizationInfo(Out, CE); Index: lib/IR/ConstantFold.cpp =================================================================== --- lib/IR/ConstantFold.cpp +++ lib/IR/ConstantFold.cpp @@ -523,6 +523,9 @@ Constant *llvm::ConstantFoldCastInstruction(unsigned opc, Constant *V, Type *DestTy) { + if (isa(V)) + return UnreachableValue::get(DestTy); + if (isa(V)) { // zext(undef) = 0, because the top bits will be zero. // sext(undef) = 0, because the top bits will all be the same. @@ -744,6 +747,8 @@ V = V1Element; } else if (isa(Cond)) { V = isa(V1Element) ? V1Element : V2Element; + } else if (isa(Cond)) { + return UnreachableValue::get(V1->getType()); } else { if (!isa(Cond)) break; V = Cond->isNullValue() ? V2Element : V1Element; @@ -756,12 +761,16 @@ return ConstantVector::get(Result); } + if (isa(Cond)) { + return UnreachableValue::get(V1->getType()); + } if (isa(Cond)) { - if (isa(V1)) return V1; + if (isa(V2)) return V2; + if (isa(V1) || isa(V1)) return V1; return V2; } - if (isa(V1)) return V2; - if (isa(V2)) return V1; + if (isa(V1) || isa(V1)) return V2; + if (isa(V2) || isa(V2)) return V1; if (V1 == V2) return V1; if (ConstantExpr *TrueVal = dyn_cast(V1)) { @@ -780,6 +789,10 @@ Constant *llvm::ConstantFoldExtractElementInstruction(Constant *Val, Constant *Idx) { + // ee(unreachable, x) -> unreachable + // ee({w,x,y,z}, unreachable) -> unreachable + if (isa(Val) || isa(Idx)) + return UnreachableValue::get(Val->getType()->getVectorElementType()); if (isa(Val)) // ee(undef, x) -> undef return UndefValue::get(Val->getType()->getVectorElementType()); if (Val->isNullValue()) // ee(zero, x) -> zero @@ -800,6 +813,10 @@ Constant *llvm::ConstantFoldInsertElementInstruction(Constant *Val, Constant *Elt, Constant *Idx) { + if (isa(Val) || isa(Elt) || + isa(Idx)) + return UnreachableValue::get(Val->getType()); + if (isa(Idx)) return UndefValue::get(Val->getType()); @@ -837,6 +854,10 @@ if (isa(Mask)) return UndefValue::get(VectorType::get(EltTy, MaskNumElts)); + // Unreachable shuffle mask -> unreachable value. + if (isa(Mask)) + return UnreachableValue::get(VectorType::get(EltTy, MaskNumElts)); + // Don't break the bitcode reader hack. if (isa(Mask)) return nullptr; @@ -858,9 +879,13 @@ InElt = ConstantExpr::getExtractElement(V2, ConstantInt::get(Ty, Elt - SrcNumElts)); + if (isa(InElt)) + return UnreachableValue::get(VectorType::get(EltTy, MaskNumElts)); } else { Type *Ty = IntegerType::get(V1->getContext(), 32); InElt = ConstantExpr::getExtractElement(V1, ConstantInt::get(Ty, Elt)); + if (isa(InElt)) + return UnreachableValue::get(VectorType::get(EltTy, MaskNumElts)); } Result.push_back(InElt); } @@ -918,6 +943,12 @@ Constant *C1, Constant *C2) { assert(Instruction::isBinaryOp(Opcode) && "Non-binary instruction detected"); + // Handle UnreachableValue now to make the rest of the function easier. + if (isa(C1)) + return C1; + if (isa(C2)) + return C2; + // Handle UndefValue up front. if (isa(C1) || isa(C2)) { switch (static_cast(Opcode)) { @@ -949,23 +980,21 @@ } case Instruction::SDiv: case Instruction::UDiv: - // X / undef -> undef - if (isa(C2)) - return C2; - // undef / 0 -> undef + // X / undef -> unreachable + // undef / 0 -> unreachable + if (isa(C2) || match(C2, m_Zero())) + return UnreachableValue::get(C1->getType()); // undef / 1 -> undef - if (match(C2, m_Zero()) || match(C2, m_One())) + if (match(C2, m_One())) return C1; // undef / X -> 0 otherwise return Constant::getNullValue(C1->getType()); case Instruction::URem: case Instruction::SRem: - // X % undef -> undef + // X % undef -> unreachable + // undef % 0 -> unreachable if (match(C2, m_Undef())) - return C2; - // undef % 0 -> undef - if (match(C2, m_Zero())) - return C1; + return UnreachableValue::get(C1->getType()); // undef % X -> 0 otherwise return Constant::getNullValue(C1->getType()); case Instruction::Or: // X | undef -> -1 @@ -1033,16 +1062,16 @@ case Instruction::UDiv: case Instruction::SDiv: if (CI2->equalsInt(1)) - return C1; // X / 1 == X + return C1; // X / 1 == X if (CI2->equalsInt(0)) - return UndefValue::get(CI2->getType()); // X / 0 == undef + return UnreachableValue::get(CI2->getType()); // X / 0 == unreachable break; case Instruction::URem: case Instruction::SRem: if (CI2->equalsInt(1)) - return Constant::getNullValue(CI2->getType()); // X % 1 == 0 + return Constant::getNullValue(CI2->getType()); // X % 1 == 0 if (CI2->equalsInt(0)) - return UndefValue::get(CI2->getType()); // X % 0 == undef + return UnreachableValue::get(CI2->getType()); // X % 0 == unreachable break; case Instruction::And: if (CI2->isZero()) return C2; // X & 0 == 0 @@ -1117,6 +1146,8 @@ return ConstantExpr::get(Opcode, C2, C1); } + // At this point we know neither constant is an UndefValue or an + // UnreachableValue. if (ConstantInt *CI1 = dyn_cast(C1)) { if (ConstantInt *CI2 = dyn_cast(C2)) { const APInt &C1V = CI1->getValue(); @@ -1135,16 +1166,18 @@ return ConstantInt::get(CI1->getContext(), C1V.udiv(C2V)); case Instruction::SDiv: assert(!CI2->isNullValue() && "Div by zero handled above"); + // MIN_INT / -1 -> unreachable if (C2V.isAllOnesValue() && C1V.isMinSignedValue()) - return UndefValue::get(CI1->getType()); // MIN_INT / -1 -> undef + return UnreachableValue::get(CI1->getType()); return ConstantInt::get(CI1->getContext(), C1V.sdiv(C2V)); case Instruction::URem: assert(!CI2->isNullValue() && "Div by zero handled above"); return ConstantInt::get(CI1->getContext(), C1V.urem(C2V)); case Instruction::SRem: assert(!CI2->isNullValue() && "Div by zero handled above"); + // MIN_INT % -1 -> undef if (C2V.isAllOnesValue() && C1V.isMinSignedValue()) - return UndefValue::get(CI1->getType()); // MIN_INT % -1 -> undef + return UnreachableValue::get(CI1->getType()); return ConstantInt::get(CI1->getContext(), C1V.srem(C2V)); case Instruction::And: return ConstantInt::get(CI1->getContext(), C1V & C2V); @@ -1687,6 +1720,9 @@ return Constant::getAllOnesValue(ResultTy); // Handle some degenerate cases first + if (isa(C1) || isa(C2)) + return UnreachableValue::get(ResultTy); + if (isa(C1) || isa(C2)) { CmpInst::Predicate Predicate = CmpInst::Predicate(pred); bool isIntegerPredicate = ICmpInst::isIntPredicate(Predicate); @@ -2053,13 +2089,15 @@ if ((Idxs.size() == 1 && Idx0->isNullValue())) return C; - if (isa(C)) { + if (isa(C) || isa(C)) { PointerType *PtrTy = cast(C->getType()->getScalarType()); Type *Ty = GetElementPtrInst::getIndexedType(PointeeTy, Idxs); assert(Ty && "Invalid indices for GEP!"); Type *GEPTy = PointerType::get(Ty, PtrTy->getAddressSpace()); if (VectorType *VT = dyn_cast(C->getType())) GEPTy = VectorType::get(GEPTy, VT->getNumElements()); + if (isa(C)) + return UnreachableValue::get(GEPTy); return UndefValue::get(GEPTy); } Index: lib/IR/Constants.cpp =================================================================== --- lib/IR/Constants.cpp +++ lib/IR/Constants.cpp @@ -285,6 +285,9 @@ if (const UndefValue *UV = dyn_cast(this)) return Elt < UV->getNumElements() ? UV->getElementValue(Elt) : nullptr; + if (const UnreachableValue *UV = dyn_cast(this)) + return Elt < UV->getNumElements() ? UV->getElementValue(Elt) : nullptr; + if (const ConstantDataSequential *CDS =dyn_cast(this)) return Elt < CDS->getNumElements() ? CDS->getElementAsConstant(Elt) : nullptr; @@ -848,6 +851,47 @@ } //===----------------------------------------------------------------------===// +// UnreachableValue Implementation +//===----------------------------------------------------------------------===// + +/// getSequentialElement - If this unreachable has array or vector type, +/// return an unreachable with the right element type. +UnreachableValue *UnreachableValue::getSequentialElement() const { + return UnreachableValue::get(getType()->getSequentialElementType()); +} + +/// getStructElement - If this unreachable has struct type, return a zero with +/// the right element type for the specified element. +UnreachableValue *UnreachableValue::getStructElement(unsigned Elt) const { + return UnreachableValue::get(getType()->getStructElementType(Elt)); +} + +/// getElementValue - Return an unreachable of the right value for the specified +/// GEP index if we can, otherwise return null (e.g. if C is a ConstantExpr). +UnreachableValue *UnreachableValue::getElementValue(Constant *C) const { + if (isa(getType())) + return getSequentialElement(); + return getStructElement(cast(C)->getZExtValue()); +} + +/// getElementValue - Return an unreachable of the right value for the specified +/// GEP index. +UnreachableValue *UnreachableValue::getElementValue(unsigned Idx) const { + if (isa(getType())) + return getSequentialElement(); + return getStructElement(Idx); +} + +unsigned UnreachableValue::getNumElements() const { + Type *Ty = getType(); + if (auto *AT = dyn_cast(Ty)) + return AT->getNumElements(); + if (auto *VT = dyn_cast(Ty)) + return VT->getNumElements(); + return Ty->getStructNumElements(); +} + +//===----------------------------------------------------------------------===// // ConstantXXX Classes //===----------------------------------------------------------------------===// @@ -941,9 +985,12 @@ } // If this is an all-zero array, return a ConstantAggregateZero object. If - // all undef, return an UndefValue, if "all simple", then return a - // ConstantDataArray. + // all unreachable, return an UnreachableValue, if all undef, return an + // UndefValue. If "all simple", then return a ConstantDataArray. Constant *C = V[0]; + if (isa(C) && rangeOnlyContains(V.begin(), V.end(), C)) + return UnreachableValue::get(Ty); + if (isa(C) && rangeOnlyContains(V.begin(), V.end(), C)) return UndefValue::get(Ty); @@ -1001,8 +1048,10 @@ // Create a ConstantAggregateZero value if all elements are zeros. bool isZero = true; bool isUndef = false; + bool isUnreachable = false; if (!V.empty()) { + isUnreachable = isa(V[0]); isUndef = isa(V[0]); isZero = V[0]->isNullValue(); if (isUndef || isZero) { @@ -1011,6 +1060,8 @@ isZero = false; if (!isa(V[i])) isUndef = false; + if (!isa(V[i])) + isUnreachable = false; } } } @@ -1018,6 +1069,8 @@ return ConstantAggregateZero::get(ST); if (isUndef) return UndefValue::get(ST); + if (isUnreachable) + return UnreachableValue::get(ST); return ST->getContext().pImpl->StructConstants.getOrCreate(ST, V); } @@ -1054,16 +1107,17 @@ assert(!V.empty() && "Vectors can't be empty"); VectorType *T = VectorType::get(V.front()->getType(), V.size()); - // If this is an all-undef or all-zero vector, return a - // ConstantAggregateZero or UndefValue. + // If this is an all-unreachable, all-undef or all-zero vector, return a + // UnreachableValue, UndefValue or ConstantAggregateZero. Constant *C = V[0]; bool isZero = C->isNullValue(); bool isUndef = isa(C); + bool isUnreachable = isa(C); - if (isZero || isUndef) { + if (isZero || isUndef || isUnreachable) { for (unsigned i = 1, e = V.size(); i != e; ++i) if (V[i] != C) { - isZero = isUndef = false; + isZero = isUndef = isUnreachable = false; break; } } @@ -1072,6 +1126,8 @@ return ConstantAggregateZero::get(T); if (isUndef) return UndefValue::get(T); + if (isUnreachable) + return UnreachableValue::get(T); // Check to see if all of the elements are ConstantFP or ConstantInt and if // the element type is compatible with ConstantDataVector. If so, use it. @@ -1422,6 +1478,24 @@ getContext().pImpl->UVConstants.erase(getType()); } +//---- UnreachableValue::get() implementation. +// + +UnreachableValue *UnreachableValue::get(Type *Ty) { + UnreachableValue *&Entry = Ty->getContext().pImpl->URVConstants[Ty]; + if (!Entry) + Entry = new UnreachableValue(Ty); + + return Entry; +} + +// destroyConstant - Remove the constant from the constant table. +// +void UnreachableValue::destroyConstantImpl() { + // Free the constant and any dangling references to it. + getContext().pImpl->URVConstants.erase(getType()); +} + //---- BlockAddress::get() implementation. // @@ -2850,6 +2924,9 @@ if (AllSame && isa(ToC)) return UndefValue::get(getType()); + if (AllSame && isa(ToC)) + return UnreachableValue::get(getType()); + // Check for any other type of constant-folding. if (Constant *C = getImpl(getType(), Values)) return C; @@ -2890,6 +2967,9 @@ if (AllSame && isa(ToC)) return UndefValue::get(getType()); + if (AllSame && isa(ToC)) + return UnreachableValue::get(getType()); + // Update to the new value. return getContext().pImpl->StructConstants.replaceOperandsInPlace( Values, this, From, ToC, NumUpdated, OperandNo); Index: lib/IR/LLVMContextImpl.h =================================================================== --- lib/IR/LLVMContextImpl.h +++ lib/IR/LLVMContextImpl.h @@ -961,6 +961,8 @@ DenseMap CPNConstants; DenseMap UVConstants; + + DenseMap URVConstants; StringMap CDSConstants; Index: lib/IR/LLVMContextImpl.cpp =================================================================== --- lib/IR/LLVMContextImpl.cpp +++ lib/IR/LLVMContextImpl.cpp @@ -114,6 +114,7 @@ DeleteContainerSeconds(CAZConstants); DeleteContainerSeconds(CPNConstants); DeleteContainerSeconds(UVConstants); + DeleteContainerSeconds(URVConstants); InlineAsms.freeConstants(); DeleteContainerSeconds(IntConstants); DeleteContainerSeconds(FPConstants); Index: lib/Transforms/Scalar/SCCP.cpp =================================================================== --- lib/Transforms/Scalar/SCCP.cpp +++ lib/Transforms/Scalar/SCCP.cpp @@ -69,7 +69,7 @@ /// asserting. forcedconstant, - /// overdefined - This instruction is not known to be constant, and we know + /// overdefined - This LLVM Value is not known to be constant, and we know /// it has a value. overdefined }; @@ -828,6 +828,9 @@ if (I.getType()->isStructTy()) return markAnythingOverdefined(&I); + LatticeVal &IV = ValueState[&I]; + if (IV.isOverdefined()) return; + LatticeVal CondValue = getValueState(I.getCondition()); if (CondValue.isUndefined()) return; @@ -838,6 +841,9 @@ return; } + if (CondValue.isConstant() && isa(CondValue.getConstant())) + return markConstant(&I, UnreachableValue::get(I.getType())); + // Otherwise, the condition is overdefined or a constant we can't evaluate. // See if we can produce something better than overdefined based on the T/F // value. @@ -1397,14 +1403,14 @@ case Instruction::UDiv: case Instruction::SRem: case Instruction::URem: - // X / undef -> undef. No change. - // X % undef -> undef. No change. - if (Op1LV.isUndefined()) break; - - // X / 0 -> undef. No change. - // X % 0 -> undef. No change. - if (Op1LV.isConstant() && Op1LV.getConstant()->isZeroValue()) - break; + // X / undef -> unreachable. + // X % undef -> unreachable. + // X / 0 -> unreachable. + // X % 0 -> unreachable. + if (Op1LV.isUndefined() || (Op1LV.isConstant() && Op1LV.getConstant()->isZeroValue())) { + markForcedConstant(&I, UnreachableValue::get(ITy)); + return true; + } // undef / X -> 0. X could be maxint. // undef % X -> 0. X could be 1. Index: lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- lib/Transforms/Utils/SimplifyCFG.cpp +++ lib/Transforms/Utils/SimplifyCFG.cpp @@ -549,19 +549,21 @@ } -static void EraseTerminatorInstAndDCECond(TerminatorInst *TI) { - Instruction *Cond = nullptr; +static void EraseTerminatorInstAndDCE(TerminatorInst *TI) { + Instruction *Op = nullptr; if (SwitchInst *SI = dyn_cast(TI)) { - Cond = dyn_cast(SI->getCondition()); + Op = dyn_cast(SI->getCondition()); } else if (BranchInst *BI = dyn_cast(TI)) { if (BI->isConditional()) - Cond = dyn_cast(BI->getCondition()); + Op = dyn_cast(BI->getCondition()); } else if (IndirectBrInst *IBI = dyn_cast(TI)) { - Cond = dyn_cast(IBI->getAddress()); + Op = dyn_cast(IBI->getAddress()); + } else if (ReturnInst *RI = dyn_cast(TI)) { + Op = dyn_cast_or_null(RI->getReturnValue()); } TI->eraseFromParent(); - if (Cond) RecursivelyDeleteTriviallyDeadInstructions(Cond); + if (Op) RecursivelyDeleteTriviallyDeadInstructions(Op); } /// Return true if the specified terminator checks @@ -710,7 +712,7 @@ DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"); - EraseTerminatorInstAndDCECond(TI); + EraseTerminatorInstAndDCE(TI); return true; } @@ -792,7 +794,7 @@ DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"); - EraseTerminatorInstAndDCECond(TI); + EraseTerminatorInstAndDCE(TI); return true; } @@ -1044,7 +1046,7 @@ createBranchWeights(MDWeights)); } - EraseTerminatorInstAndDCECond(PTI); + EraseTerminatorInstAndDCE(PTI); // Okay, last check. If BB is still a successor of PSI, then we must // have an infinite loop case. If so, add an infinitely looping block @@ -1232,7 +1234,7 @@ for (BasicBlock *Succ : successors(BB1)) AddPredecessorToBlock(Succ, BIParent, BB1); - EraseTerminatorInstAndDCECond(BI); + EraseTerminatorInstAndDCE(BI); return true; } @@ -1981,7 +1983,7 @@ TrueSucc->removePredecessor(BI->getParent()); FalseSucc->removePredecessor(BI->getParent()); Builder.CreateRetVoid(); - EraseTerminatorInstAndDCECond(BI); + EraseTerminatorInstAndDCE(BI); return true; } @@ -2037,7 +2039,7 @@ << "\n " << *BI << "NewRet = " << *RI << "TRUEBLOCK: " << *TrueSucc << "FALSEBLOCK: "<< *FalseSucc); - EraseTerminatorInstAndDCECond(BI); + EraseTerminatorInstAndDCE(BI); return true; } @@ -2360,7 +2362,7 @@ } // Change PBI from Conditional to Unconditional. BranchInst *New_PBI = BranchInst::Create(TrueDest, PBI); - EraseTerminatorInstAndDCECond(PBI); + EraseTerminatorInstAndDCE(PBI); PBI = New_PBI; } @@ -2963,7 +2965,7 @@ Builder.CreateBr(FalseBB); } - EraseTerminatorInstAndDCECond(OldTerm); + EraseTerminatorInstAndDCE(OldTerm); return true; } @@ -3248,7 +3250,7 @@ } // Erase the old branch instruction. - EraseTerminatorInstAndDCECond(BI); + EraseTerminatorInstAndDCE(BI); DEBUG(dbgs() << " ** 'icmp' chain result is:\n" << *BB << '\n'); return true; @@ -3538,6 +3540,13 @@ bool SimplifyCFGOpt::SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder) { BasicBlock *BB = RI->getParent(); + + if (RI->getReturnValue() && isa(RI->getReturnValue())) { + new UnreachableInst(RI->getContext(), BB); + EraseTerminatorInstAndDCE(RI); + return true; + } + if (!BB->getFirstNonPHIOrDbg()->isTerminator()) return false; // Find predecessors that end with branches. @@ -3659,10 +3668,10 @@ } else { if (BI->getSuccessor(0) == BB) { Builder.CreateBr(BI->getSuccessor(1)); - EraseTerminatorInstAndDCECond(BI); + EraseTerminatorInstAndDCE(BI); } else if (BI->getSuccessor(1) == BB) { Builder.CreateBr(BI->getSuccessor(0)); - EraseTerminatorInstAndDCECond(BI); + EraseTerminatorInstAndDCE(BI); Changed = true; } } @@ -3892,7 +3901,7 @@ SplitBlock(&*NewDefault, &NewDefault->front()); auto *OldTI = NewDefault->getTerminator(); new UnreachableInst(SI->getContext(), OldTI); - EraseTerminatorInstAndDCECond(OldTI); + EraseTerminatorInstAndDCE(OldTI); return true; } @@ -4968,14 +4977,14 @@ if (IBI->getNumDestinations() == 0) { // If the indirectbr has no successors, change it to unreachable. new UnreachableInst(IBI->getContext(), IBI); - EraseTerminatorInstAndDCECond(IBI); + EraseTerminatorInstAndDCE(IBI); return true; } if (IBI->getNumDestinations() == 1) { // If the indirectbr has one successor, change it to a direct branch. BranchInst::Create(IBI->getDestination(0), IBI); - EraseTerminatorInstAndDCECond(IBI); + EraseTerminatorInstAndDCE(IBI); return true; } @@ -5223,10 +5232,10 @@ if (I->use_empty()) return false; - if (C->isNullValue()) { - // Only look at the first use, avoid hurting compile time with long uselists - User *Use = *I->user_begin(); + // Only look at the first use, avoid hurting compile time with long uselists + User *Use = *I->user_begin(); + if (C->isNullValue()) { // Now make sure that there are no instructions in between that can alter // control flow (eg. calls) for (BasicBlock::iterator i = ++BasicBlock::iterator(I); &*i != Use; ++i) @@ -5252,6 +5261,12 @@ if (!SI->isVolatile()) return SI->getPointerAddressSpace() == 0 && SI->getPointerOperand() == I; } + + if (isa(C)) { + return isa(Use) || isa(Use) || + isa(Use) || isa(Use) || isa(Use); + } + return false; } Index: test/Feature/unreachable-cst.ll =================================================================== --- test/Feature/unreachable-cst.ll +++ test/Feature/unreachable-cst.ll @@ -0,0 +1,15 @@ +; RUN: llvm-as < %s | llvm-dis > %t1.ll +; RUN: llvm-as %t1.ll -o - | llvm-dis > %t2.ll +; RUN: diff %t1.ll %t2.ll + +@X = global i32 unreachable ; [#uses=0] + +define i32 @test() { + ret i32 unreachable +} + +define i32 @test2() { + %X = add i32 unreachable, 1 ; [#uses=1] + ret i32 %X +} + Index: test/Transforms/IPConstantProp/PR16052.ll =================================================================== --- test/Transforms/IPConstantProp/PR16052.ll +++ test/Transforms/IPConstantProp/PR16052.ll @@ -12,7 +12,7 @@ } ; CHECK-DAG: define i64 @fn2( -; CHECK: %[[CALL:.*]] = call i64 @fn1(i64 undef) +; CHECK: %[[CALL:.*]] = call i64 @fn1(i64 unreachable) define internal i64 @fn1(i64 %p1) { entry: @@ -22,5 +22,5 @@ } ; CHECK-DAG: define internal i64 @fn1( -; CHECK: %[[SEL:.*]] = select i1 undef, i64 undef, i64 undef +; CHECK: %[[SEL:.*]] = select i1 unreachable, i64 unreachable, i64 unreachable ; CHECK: ret i64 %[[SEL]] Index: test/Transforms/InstCombine/rem.ll =================================================================== --- test/Transforms/InstCombine/rem.ll +++ test/Transforms/InstCombine/rem.ll @@ -59,8 +59,8 @@ define i32 @test6(i32 %A) { ; CHECK-LABEL: @test6( -; CHECK-NEXT: ret i32 undef - %B = srem i32 %A, 0 ;; undef +; CHECK-NEXT: ret i32 unreachable + %B = srem i32 %A, 0 ret i32 %B } Index: test/Transforms/InstSimplify/undef.ll =================================================================== --- test/Transforms/InstSimplify/undef.ll +++ test/Transforms/InstSimplify/undef.ll @@ -188,7 +188,7 @@ define i32 @test20(i32 %a) { ; CHECK-LABEL: @test20( -; CHECK: ret i32 undef +; CHECK: ret i32 unreachable ; %b = udiv i32 %a, 0 ret i32 %b @@ -196,7 +196,7 @@ define i32 @test21(i32 %a) { ; CHECK-LABEL: @test21( -; CHECK: ret i32 undef +; CHECK: ret i32 unreachable ; %b = sdiv i32 %a, 0 ret i32 %b @@ -220,7 +220,7 @@ define i32 @test24() { ; CHECK-LABEL: @test24( -; CHECK: ret i32 undef +; CHECK: ret i32 unreachable ; %b = udiv i32 undef, 0 ret i32 %b @@ -324,7 +324,7 @@ define i32 @test37() { ; CHECK-LABEL: @test37( -; CHECK: ret i32 undef +; CHECK: ret i32 unreachable ; %b = udiv i32 undef, undef ret i32 %b @@ -332,7 +332,7 @@ define i32 @test38(i32 %a) { ; CHECK-LABEL: @test38( -; CHECK: ret i32 undef +; CHECK: ret i32 unreachable ; %b = udiv i32 %a, undef ret i32 %b @@ -340,7 +340,7 @@ define i32 @test39() { ; CHECK-LABEL: @test39( -; CHECK: ret i32 undef +; CHECK: ret i32 unreachable ; %b = udiv i32 0, undef ret i32 %b