Index: llvm/lib/Bitcode/Reader/BitcodeReader.cpp =================================================================== --- llvm/lib/Bitcode/Reader/BitcodeReader.cpp +++ llvm/lib/Bitcode/Reader/BitcodeReader.cpp @@ -94,6 +94,10 @@ cl::desc( "Print the global id for each value when reading the module summary")); +static cl::opt ExpandConstantExprs( + "expand-constant-exprs", cl::init(false), cl::Hidden, + cl::desc("Expand constant expressions for testing purposes")); + namespace { enum { @@ -473,6 +477,90 @@ namespace { +/// This represents a constant expression or constant aggregate using a custom +/// structure internal to the bitcode reader. Later, this structure will be +/// expanded by materializeValue() either into a constant expression/aggregate, +/// or into an instruction sequence at the point of use. This allows us to +/// upgrade bitcode using constant expressions even if this kind of constant +/// expression is no longer supported. +class BitcodeConstant final : public Value, + TrailingObjects { + friend TrailingObjects; + + // Value subclass ID: Pick largest possible value to avoid any clashes. + static constexpr uint8_t SubclassID = 255; + +public: + // Opcodes used for non-expressions. This includes constant aggregates + // (struct, array, vector) that might need expansion, as well as non-leaf + // constants that don't need expansion (no_cfi, dso_local, blockaddress), + // but still go through BitcodeConstant to avoid different uselist orders + // between the two cases. + static constexpr uint8_t ConstantStructOpcode = 255; + static constexpr uint8_t ConstantArrayOpcode = 254; + static constexpr uint8_t ConstantVectorOpcode = 253; + static constexpr uint8_t NoCFIOpcode = 252; + static constexpr uint8_t DSOLocalEquivalentOpcode = 251; + static constexpr uint8_t BlockAddressOpcode = 250; + static constexpr uint8_t FirstSpecialOpcode = BlockAddressOpcode; + + // Separate struct to make passing different number of parameters to + // BitcodeConstant::create() more convenient. + struct ExtraInfo { + uint8_t Opcode; + uint8_t Flags; + unsigned Extra; + Type *SrcElemTy; + + ExtraInfo(uint8_t Opcode, uint8_t Flags = 0, unsigned Extra = 0, + Type *SrcElemTy = nullptr) + : Opcode(Opcode), Flags(Flags), Extra(Extra), SrcElemTy(SrcElemTy) {} + }; + + uint8_t Opcode; + uint8_t Flags; + unsigned NumOperands; + unsigned Extra; // GEP inrange index or blockaddress BB id. + Type *SrcElemTy; // GEP source element type. + +private: + BitcodeConstant(Type *Ty, const ExtraInfo &Info, ArrayRef OpIDs) + : Value(Ty, SubclassID), Opcode(Info.Opcode), Flags(Info.Flags), + NumOperands(OpIDs.size()), Extra(Info.Extra), + SrcElemTy(Info.SrcElemTy) { + std::uninitialized_copy(OpIDs.begin(), OpIDs.end(), + getTrailingObjects()); + } + + BitcodeConstant &operator=(const BitcodeConstant &) = delete; + +public: + static BitcodeConstant *create(BumpPtrAllocator &A, Type *Ty, + const ExtraInfo &Info, + ArrayRef OpIDs) { + void *Mem = A.Allocate(totalSizeToAlloc(OpIDs.size()), + alignof(BitcodeConstant)); + return new (Mem) BitcodeConstant(Ty, Info, OpIDs); + } + + static bool classof(const Value *V) { return V->getValueID() == SubclassID; } + + ArrayRef getOperandIDs() const { + return makeArrayRef(getTrailingObjects(), NumOperands); + } + + Optional getInRangeIndex() const { + assert(Opcode == Instruction::GetElementPtr); + if (Extra == (unsigned)-1) + return None; + return Extra; + } + + const char *getOpcodeName() const { + return Instruction::getOpcodeName(Opcode); + } +}; + class BitcodeReader : public BitcodeReaderBase, public GVMaterializer { LLVMContext &Context; Module *TheModule = nullptr; @@ -499,6 +587,10 @@ /// for the given pair of Type and contained type ID. DenseMap, unsigned> VirtualTypeIDs; DenseMap FunctionTypeIDs; + /// Allocator for BitcodeConstants. This should come before ValueList, + /// because the ValueList might hold ValueHandles to these constants, so + /// ValueList must be destroyed before Alloc. + BumpPtrAllocator Alloc; BitcodeReaderValueList ValueList; Optional MDLoader; std::vector ComdatList; @@ -618,10 +710,14 @@ unsigned getContainedTypeID(unsigned ID, unsigned Idx = 0); unsigned getVirtualTypeID(Type *Ty, ArrayRef ContainedTypeIDs = {}); - Value *getFnValueByID(unsigned ID, Type *Ty, unsigned TyID) { + Expected materializeValue(unsigned ValID, BasicBlock *InsertBB); + Expected getValueForInitializer(unsigned ID); + + Value *getFnValueByID(unsigned ID, Type *Ty, unsigned TyID, + BasicBlock *ConstExprInsertBB) { if (Ty && Ty->isMetadataTy()) return MetadataAsValue::get(Ty->getContext(), getFnMetadataByID(ID)); - return ValueList.getValueFwdRef(ID, Ty, TyID); + return ValueList.getValueFwdRef(ID, Ty, TyID, ConstExprInsertBB); } Metadata *getFnMetadataByID(unsigned ID) { @@ -643,7 +739,8 @@ /// Increment Slot past the number of slots used in the record. Return true on /// failure. bool getValueTypePair(const SmallVectorImpl &Record, unsigned &Slot, - unsigned InstNum, Value *&ResVal, unsigned &TypeID) { + unsigned InstNum, Value *&ResVal, unsigned &TypeID, + BasicBlock *ConstExprInsertBB) { if (Slot == Record.size()) return true; unsigned ValNo = (unsigned)Record[Slot++]; // Adjust the ValNo, if it was encoded relative to the InstNum. @@ -653,7 +750,7 @@ // If this is not a forward reference, just return the value we already // have. TypeID = ValueList.getTypeID(ValNo); - ResVal = getFnValueByID(ValNo, nullptr, TypeID); + ResVal = getFnValueByID(ValNo, nullptr, TypeID, ConstExprInsertBB); assert((!ResVal || ResVal->getType() == getTypeByID(TypeID)) && "Incorrect type ID stored for value"); return ResVal == nullptr; @@ -662,7 +759,8 @@ return true; TypeID = (unsigned)Record[Slot++]; - ResVal = getFnValueByID(ValNo, getTypeByID(TypeID), TypeID); + ResVal = getFnValueByID(ValNo, getTypeByID(TypeID), TypeID, + ConstExprInsertBB); return ResVal == nullptr; } @@ -670,8 +768,9 @@ /// past the number of slots used by the value in the record. Return true if /// there is an error. bool popValue(const SmallVectorImpl &Record, unsigned &Slot, - unsigned InstNum, Type *Ty, unsigned TyID, Value *&ResVal) { - if (getValue(Record, Slot, InstNum, Ty, TyID, ResVal)) + unsigned InstNum, Type *Ty, unsigned TyID, Value *&ResVal, + BasicBlock *ConstExprInsertBB) { + if (getValue(Record, Slot, InstNum, Ty, TyID, ResVal, ConstExprInsertBB)) return true; // All values currently take a single record slot. ++Slot; @@ -680,32 +779,35 @@ /// Like popValue, but does not increment the Slot number. bool getValue(const SmallVectorImpl &Record, unsigned Slot, - unsigned InstNum, Type *Ty, unsigned TyID, Value *&ResVal) { - ResVal = getValue(Record, Slot, InstNum, Ty, TyID); + unsigned InstNum, Type *Ty, unsigned TyID, Value *&ResVal, + BasicBlock *ConstExprInsertBB) { + ResVal = getValue(Record, Slot, InstNum, Ty, TyID, ConstExprInsertBB); return ResVal == nullptr; } /// Version of getValue that returns ResVal directly, or 0 if there is an /// error. Value *getValue(const SmallVectorImpl &Record, unsigned Slot, - unsigned InstNum, Type *Ty, unsigned TyID) { + unsigned InstNum, Type *Ty, unsigned TyID, + BasicBlock *ConstExprInsertBB) { if (Slot == Record.size()) return nullptr; unsigned ValNo = (unsigned)Record[Slot]; // Adjust the ValNo, if it was encoded relative to the InstNum. if (UseRelativeIDs) ValNo = InstNum - ValNo; - return getFnValueByID(ValNo, Ty, TyID); + return getFnValueByID(ValNo, Ty, TyID, ConstExprInsertBB); } /// Like getValue, but decodes signed VBRs. Value *getValueSigned(const SmallVectorImpl &Record, unsigned Slot, - unsigned InstNum, Type *Ty, unsigned TyID) { + unsigned InstNum, Type *Ty, unsigned TyID, + BasicBlock *ConstExprInsertBB) { if (Slot == Record.size()) return nullptr; unsigned ValNo = (unsigned)decodeSignRotatedValue(Record[Slot]); // Adjust the ValNo, if it was encoded relative to the InstNum. if (UseRelativeIDs) ValNo = InstNum - ValNo; - return getFnValueByID(ValNo, Ty, TyID); + return getFnValueByID(ValNo, Ty, TyID, ConstExprInsertBB); } /// Upgrades old-style typeless byval/sret/inalloca attributes by adding the @@ -856,7 +958,10 @@ StringRef ProducerIdentification, LLVMContext &Context) : BitcodeReaderBase(std::move(Stream), Strtab), Context(Context), - ValueList(Context, this->Stream.SizeInBytes()) { + ValueList(Context, this->Stream.SizeInBytes(), + [this](unsigned ValID, BasicBlock *InsertBB) { + return materializeValue(ValID, InsertBB); + }) { this->ProducerIdentification = std::string(ProducerIdentification); } @@ -1273,6 +1378,257 @@ return TypeID; } +static bool isConstExprSupported(uint8_t Opcode) { + // These are not real constant expressions, always consider them supported. + if (Opcode >= BitcodeConstant::FirstSpecialOpcode) + return true; + + return !ExpandConstantExprs; +} + +Expected BitcodeReader::materializeValue(unsigned StartValID, + BasicBlock *InsertBB) { + // Quickly handle the case where there is no BitcodeConstant to resolve. + if (StartValID < ValueList.size() && ValueList[StartValID] && + !isa(ValueList[StartValID])) + return ValueList[StartValID]; + + SmallDenseMap MaterializedValues; + SmallVector Worklist; + Worklist.push_back(StartValID); + while (!Worklist.empty()) { + unsigned ValID = Worklist.back(); + if (MaterializedValues.count(ValID)) { + // Duplicate expression that was already handled. + Worklist.pop_back(); + continue; + } + + if (ValID >= ValueList.size() || !ValueList[ValID]) + return error("Invalid value ID"); + + Value *V = ValueList[ValID]; + auto *BC = dyn_cast(V); + if (!BC) { + MaterializedValues.insert({ValID, V}); + Worklist.pop_back(); + continue; + } + + SmallVector Ops; + for (unsigned OpID : BC->getOperandIDs()) { + auto It = MaterializedValues.find(OpID); + if (It == MaterializedValues.end()) { + Worklist.push_back(OpID); + break; + } + Ops.push_back(It->second); + } + + // Some expressions have not been resolved yet, handle them first and then + // revisit this one. + if (Ops.size() != BC->getOperandIDs().size()) + continue; + + SmallVector ConstOps; + for (Value *Op : Ops) + if (auto *C = dyn_cast(Op)) + ConstOps.push_back(C); + + // Materialize as constant expression if possible. + if (isConstExprSupported(BC->Opcode) && ConstOps.size() == Ops.size()) { + Constant *C; + if (Instruction::isCast(BC->Opcode)) { + C = ConstantExpr::getCast(BC->Opcode, ConstOps[0], BC->getType()); + } else if (Instruction::isUnaryOp(BC->Opcode)) { + C = ConstantExpr::get(BC->Opcode, ConstOps[0], BC->Flags); + } else if (Instruction::isBinaryOp(BC->Opcode)) { + C = ConstantExpr::get(BC->Opcode, ConstOps[0], ConstOps[1], BC->Flags); + } else { + switch (BC->Opcode) { + case BitcodeConstant::NoCFIOpcode: { + auto *GV = dyn_cast(ConstOps[0]); + if (!GV) + return error("no_cfi operand must be GlobalValue"); + C = NoCFIValue::get(GV); + break; + } + case BitcodeConstant::DSOLocalEquivalentOpcode: { + auto *GV = dyn_cast(ConstOps[0]); + if (!GV) + return error("dso_local operand must be GlobalValue"); + C = DSOLocalEquivalent::get(GV); + break; + } + case BitcodeConstant::BlockAddressOpcode: { + Function *Fn = dyn_cast(ConstOps[0]); + if (!Fn) + return error("blockaddress operand must be a function"); + + // If the function is already parsed we can insert the block address + // right away. + BasicBlock *BB; + unsigned BBID = BC->Extra; + if (!BBID) + // Invalid reference to entry block. + return error("Invalid ID"); + if (!Fn->empty()) { + Function::iterator BBI = Fn->begin(), BBE = Fn->end(); + for (size_t I = 0, E = BBID; I != E; ++I) { + if (BBI == BBE) + return error("Invalid ID"); + ++BBI; + } + BB = &*BBI; + } else { + // Otherwise insert a placeholder and remember it so it can be + // inserted when the function is parsed. + auto &FwdBBs = BasicBlockFwdRefs[Fn]; + if (FwdBBs.empty()) + BasicBlockFwdRefQueue.push_back(Fn); + if (FwdBBs.size() < BBID + 1) + FwdBBs.resize(BBID + 1); + if (!FwdBBs[BBID]) + FwdBBs[BBID] = BasicBlock::Create(Context); + BB = FwdBBs[BBID]; + } + C = BlockAddress::get(Fn, BB); + break; + } + case BitcodeConstant::ConstantStructOpcode: + C = ConstantStruct::get(cast(BC->getType()), ConstOps); + break; + case BitcodeConstant::ConstantArrayOpcode: + C = ConstantArray::get(cast(BC->getType()), ConstOps); + break; + case BitcodeConstant::ConstantVectorOpcode: + C = ConstantVector::get(ConstOps); + break; + case Instruction::ICmp: + case Instruction::FCmp: + C = ConstantExpr::getCompare(BC->Flags, ConstOps[0], ConstOps[1]); + break; + case Instruction::GetElementPtr: + C = ConstantExpr::getGetElementPtr( + BC->SrcElemTy, ConstOps[0], makeArrayRef(ConstOps).drop_front(), + BC->Flags, BC->getInRangeIndex()); + break; + case Instruction::Select: + C = ConstantExpr::getSelect(ConstOps[0], ConstOps[1], ConstOps[2]); + break; + case Instruction::ExtractElement: + C = ConstantExpr::getExtractElement(ConstOps[0], ConstOps[1]); + break; + case Instruction::InsertElement: + C = ConstantExpr::getInsertElement(ConstOps[0], ConstOps[1], + ConstOps[2]); + break; + case Instruction::ShuffleVector: { + SmallVector Mask; + ShuffleVectorInst::getShuffleMask(ConstOps[2], Mask); + C = ConstantExpr::getShuffleVector(ConstOps[0], ConstOps[1], Mask); + break; + } + default: + llvm_unreachable("Unhandled bitcode constant"); + } + } + + // Cache resolved constant. + ValueList.replaceValueWithoutRAUW(ValID, C); + MaterializedValues.insert({ValID, C}); + Worklist.pop_back(); + continue; + } + + if (!InsertBB) + return error(Twine("Value referenced by initializer is an unsupported " + "constant expression of type ") + + BC->getOpcodeName()); + + // Materialize as instructions if necessary. + Instruction *I; + if (Instruction::isCast(BC->Opcode)) { + I = CastInst::Create((Instruction::CastOps)BC->Opcode, Ops[0], + BC->getType(), "constexpr", InsertBB); + } else if (Instruction::isUnaryOp(BC->Opcode)) { + I = UnaryOperator::Create((Instruction::UnaryOps)BC->Opcode, Ops[0], + "constexpr", InsertBB); + } else if (Instruction::isBinaryOp(BC->Opcode)) { + I = BinaryOperator::Create((Instruction::BinaryOps)BC->Opcode, Ops[0], + Ops[1], "constexpr", InsertBB); + if (isa(I)) { + if (BC->Flags & OverflowingBinaryOperator::NoSignedWrap) + I->setHasNoSignedWrap(); + if (BC->Flags & OverflowingBinaryOperator::NoUnsignedWrap) + I->setHasNoUnsignedWrap(); + } + if (isa(I) && + (BC->Flags & PossiblyExactOperator::IsExact)) + I->setIsExact(); + } else { + switch (BC->Opcode) { + case BitcodeConstant::ConstantStructOpcode: + case BitcodeConstant::ConstantArrayOpcode: + case BitcodeConstant::ConstantVectorOpcode: { + Type *IdxTy = Type::getInt32Ty(BC->getContext()); + Value *V = PoisonValue::get(BC->getType()); + for (auto Pair : enumerate(Ops)) { + Value *Idx = ConstantInt::get(IdxTy, Pair.index()); + V = InsertElementInst::Create(V, Pair.value(), Idx, "constexpr.ins", + InsertBB); + } + I = cast(V); + break; + } + case Instruction::ICmp: + case Instruction::FCmp: + I = CmpInst::Create((Instruction::OtherOps)BC->Opcode, + (CmpInst::Predicate)BC->Flags, Ops[0], Ops[1], + "constexpr", InsertBB); + break; + case Instruction::GetElementPtr: + I = GetElementPtrInst::Create(BC->SrcElemTy, Ops[0], + makeArrayRef(Ops).drop_front(), + "constexpr", InsertBB); + if (BC->Flags) + cast(I)->setIsInBounds(); + break; + case Instruction::Select: + I = SelectInst::Create(Ops[0], Ops[1], Ops[2], "constexpr", InsertBB); + break; + case Instruction::ExtractElement: + I = ExtractElementInst::Create(Ops[0], Ops[1], "constexpr", InsertBB); + break; + case Instruction::InsertElement: + I = InsertElementInst::Create(Ops[0], Ops[1], Ops[2], "constexpr", + InsertBB); + break; + case Instruction::ShuffleVector: + I = new ShuffleVectorInst(Ops[0], Ops[1], Ops[2], "constexpr", + InsertBB); + break; + default: + llvm_unreachable("Unhandled bitcode constant"); + } + } + + MaterializedValues.insert({ValID, I}); + Worklist.pop_back(); + } + + return MaterializedValues[StartValID]; +} + +Expected BitcodeReader::getValueForInitializer(unsigned ID) { + Expected MaybeV = materializeValue(ID, /* InsertBB */ nullptr); + if (!MaybeV) + return MaybeV.takeError(); + + // Result must be Constant if InsertBB is nullptr. + return cast(MaybeV.get()); +} + StructType *BitcodeReader::createIdentifiedStructType(LLVMContext &Context, StringRef Name) { auto *Ret = StructType::create(Context, Name); @@ -2386,10 +2742,10 @@ // Not ready to resolve this yet, it requires something later in the file. GlobalInits.push_back(GlobalInitWorklist.back()); } else { - if (Constant *C = dyn_cast_or_null(ValueList[ValID])) - GlobalInitWorklist.back().first->setInitializer(C); - else - return error("Expected a constant"); + Expected MaybeC = getValueForInitializer(ValID); + if (!MaybeC) + return MaybeC.takeError(); + GlobalInitWorklist.back().first->setInitializer(MaybeC.get()); } GlobalInitWorklist.pop_back(); } @@ -2399,9 +2755,10 @@ if (ValID >= ValueList.size()) { IndirectSymbolInits.push_back(IndirectSymbolInitWorklist.back()); } else { - Constant *C = dyn_cast_or_null(ValueList[ValID]); - if (!C) - return error("Expected a constant"); + Expected MaybeC = getValueForInitializer(ValID); + if (!MaybeC) + return MaybeC.takeError(); + Constant *C = MaybeC.get(); GlobalValue *GV = IndirectSymbolInitWorklist.back().first; if (auto *GA = dyn_cast(GV)) { if (C->getType() != GV->getType()) @@ -2425,30 +2782,30 @@ if (Info.PersonalityFn) { unsigned ValID = Info.PersonalityFn - 1; if (ValID < ValueList.size()) { - if (Constant *C = dyn_cast_or_null(ValueList[ValID])) - Info.F->setPersonalityFn(C); - else - return error("Expected a constant"); + Expected MaybeC = getValueForInitializer(ValID); + if (!MaybeC) + return MaybeC.takeError(); + Info.F->setPersonalityFn(MaybeC.get()); Info.PersonalityFn = 0; } } if (Info.Prefix) { unsigned ValID = Info.Prefix - 1; if (ValID < ValueList.size()) { - if (Constant *C = dyn_cast_or_null(ValueList[ValID])) - Info.F->setPrefixData(C); - else - return error("Expected a constant"); + Expected MaybeC = getValueForInitializer(ValID); + if (!MaybeC) + return MaybeC.takeError(); + Info.F->setPrefixData(MaybeC.get()); Info.Prefix = 0; } } if (Info.Prologue) { unsigned ValID = Info.Prologue - 1; if (ValID < ValueList.size()) { - if (Constant *C = dyn_cast_or_null(ValueList[ValID])) - Info.F->setPrologueData(C); - else - return error("Expected a constant"); + Expected MaybeC = getValueForInitializer(ValID); + if (!MaybeC) + return MaybeC.takeError(); + Info.F->setPrologueData(MaybeC.get()); Info.Prologue = 0; } } @@ -2481,26 +2838,6 @@ Type *CurElemTy = nullptr; unsigned NextCstNo = ValueList.size(); - struct DelayedShufTy { - VectorType *OpTy; - unsigned OpTyID; - VectorType *RTy; - uint64_t Op0Idx; - uint64_t Op1Idx; - uint64_t Op2Idx; - unsigned CstNo; - }; - std::vector DelayedShuffles; - struct DelayedSelTy { - Type *OpTy; - unsigned OpTyID; - uint64_t Op0Idx; - uint64_t Op1Idx; - uint64_t Op2Idx; - unsigned CstNo; - }; - std::vector DelayedSelectors; - while (true) { Expected MaybeEntry = Stream.advanceSkippingSubblocks(); if (!MaybeEntry) @@ -2512,68 +2849,8 @@ case BitstreamEntry::Error: return error("Malformed block"); case BitstreamEntry::EndBlock: - // Once all the constants have been read, go through and resolve forward - // references. - // - // We have to treat shuffles specially because they don't have three - // operands anymore. We need to convert the shuffle mask into an array, - // and we can't convert a forward reference. - for (auto &DelayedShuffle : DelayedShuffles) { - VectorType *OpTy = DelayedShuffle.OpTy; - unsigned OpTyID = DelayedShuffle.OpTyID; - VectorType *RTy = DelayedShuffle.RTy; - uint64_t Op0Idx = DelayedShuffle.Op0Idx; - uint64_t Op1Idx = DelayedShuffle.Op1Idx; - uint64_t Op2Idx = DelayedShuffle.Op2Idx; - uint64_t CstNo = DelayedShuffle.CstNo; - Constant *Op0 = ValueList.getConstantFwdRef(Op0Idx, OpTy, OpTyID); - Constant *Op1 = ValueList.getConstantFwdRef(Op1Idx, OpTy, OpTyID); - Type *ShufTy = - VectorType::get(Type::getInt32Ty(Context), RTy->getElementCount()); - Constant *Op2 = ValueList.getConstantFwdRef( - Op2Idx, ShufTy, getVirtualTypeID(ShufTy, Int32TyID)); - if (!ShuffleVectorInst::isValidOperands(Op0, Op1, Op2)) - return error("Invalid shufflevector operands"); - SmallVector Mask; - ShuffleVectorInst::getShuffleMask(Op2, Mask); - Value *V = ConstantExpr::getShuffleVector(Op0, Op1, Mask); - if (Error Err = ValueList.assignValue( - CstNo, V, - getVirtualTypeID(V->getType(), getContainedTypeID(OpTyID)))) - return Err; - } - for (auto &DelayedSelector : DelayedSelectors) { - Type *OpTy = DelayedSelector.OpTy; - unsigned OpTyID = DelayedSelector.OpTyID; - Type *SelectorTy = Type::getInt1Ty(Context); - unsigned SelectorTyID = getVirtualTypeID(SelectorTy); - uint64_t Op0Idx = DelayedSelector.Op0Idx; - uint64_t Op1Idx = DelayedSelector.Op1Idx; - uint64_t Op2Idx = DelayedSelector.Op2Idx; - uint64_t CstNo = DelayedSelector.CstNo; - Constant *Op1 = ValueList.getConstantFwdRef(Op1Idx, OpTy, OpTyID); - Constant *Op2 = ValueList.getConstantFwdRef(Op2Idx, OpTy, OpTyID); - // The selector might be an i1 or an - // Get the type from the ValueList before getting a forward ref. - if (VectorType *VTy = dyn_cast(OpTy)) { - Value *V = ValueList[Op0Idx]; - assert(V); - if (SelectorTy != V->getType()) { - SelectorTy = VectorType::get(SelectorTy, VTy->getElementCount()); - SelectorTyID = getVirtualTypeID(SelectorTy, SelectorTyID); - } - } - Constant *Op0 = - ValueList.getConstantFwdRef(Op0Idx, SelectorTy, SelectorTyID); - Value *V = ConstantExpr::getSelect(Op0, Op1, Op2); - if (Error Err = ValueList.assignValue(CstNo, V, OpTyID)) - return Err; - } - if (NextCstNo != ValueList.size()) return error("Invalid constant reference"); - - ValueList.resolveConstantForwardRefs(); return Error::success(); case BitstreamEntry::Record: // The interesting case. @@ -2664,28 +2941,19 @@ return error("Invalid aggregate record"); unsigned Size = Record.size(); - SmallVector Elts; - - if (StructType *STy = dyn_cast(CurTy)) { - for (unsigned i = 0; i != Size; ++i) - Elts.push_back(ValueList.getConstantFwdRef( - Record[i], STy->getElementType(i), - getContainedTypeID(CurTyID, i))); - V = ConstantStruct::get(STy, Elts); - } else if (ArrayType *ATy = dyn_cast(CurTy)) { - Type *EltTy = ATy->getElementType(); - unsigned EltTyID = getContainedTypeID(CurTyID); - for (unsigned i = 0; i != Size; ++i) - Elts.push_back(ValueList.getConstantFwdRef(Record[i], EltTy, - EltTyID)); - V = ConstantArray::get(ATy, Elts); - } else if (VectorType *VTy = dyn_cast(CurTy)) { - Type *EltTy = VTy->getElementType(); - unsigned EltTyID = getContainedTypeID(CurTyID); - for (unsigned i = 0; i != Size; ++i) - Elts.push_back(ValueList.getConstantFwdRef(Record[i], EltTy, - EltTyID)); - V = ConstantVector::get(Elts); + SmallVector Elts; + for (unsigned i = 0; i != Size; ++i) + Elts.push_back(Record[i]); + + if (isa(CurTy)) { + V = BitcodeConstant::create( + Alloc, CurTy, BitcodeConstant::ConstantStructOpcode, Elts); + } else if (isa(CurTy)) { + V = BitcodeConstant::create(Alloc, CurTy, + BitcodeConstant::ConstantArrayOpcode, Elts); + } else if (isa(CurTy)) { + V = BitcodeConstant::create( + Alloc, CurTy, BitcodeConstant::ConstantVectorOpcode, Elts); } else { V = UndefValue::get(CurTy); } @@ -2770,9 +3038,7 @@ if (Opc < 0) { V = UndefValue::get(CurTy); // Unknown unop. } else { - Constant *LHS = ValueList.getConstantFwdRef(Record[1], CurTy, CurTyID); - unsigned Flags = 0; - V = ConstantExpr::get(Opc, LHS, Flags); + V = BitcodeConstant::create(Alloc, CurTy, Opc, (unsigned)Record[1]); } break; } @@ -2783,9 +3049,7 @@ if (Opc < 0) { V = UndefValue::get(CurTy); // Unknown binop. } else { - Constant *LHS = ValueList.getConstantFwdRef(Record[1], CurTy, CurTyID); - Constant *RHS = ValueList.getConstantFwdRef(Record[2], CurTy, CurTyID); - unsigned Flags = 0; + uint8_t Flags = 0; if (Record.size() >= 4) { if (Opc == Instruction::Add || Opc == Instruction::Sub || @@ -2803,7 +3067,8 @@ Flags |= SDivOperator::IsExact; } } - V = ConstantExpr::get(Opc, LHS, RHS, Flags); + V = BitcodeConstant::create(Alloc, CurTy, {(uint8_t)Opc, Flags}, + {(unsigned)Record[1], (unsigned)Record[2]}); } break; } @@ -2818,9 +3083,7 @@ Type *OpTy = getTypeByID(OpTyID); if (!OpTy) return error("Invalid cast constexpr record"); - Constant *Op = ValueList.getConstantFwdRef(Record[2], OpTy, OpTyID); - V = UpgradeBitCastExpr(Opc, Op, CurTy); - if (!V) V = ConstantExpr::getCast(Opc, Op, CurTy); + V = BitcodeConstant::create(Alloc, CurTy, Opc, (unsigned)Record[2]); } break; } @@ -2845,15 +3108,14 @@ } else if (BitCode == bitc::CST_CODE_CE_INBOUNDS_GEP) InBounds = true; - SmallVector Elts; + SmallVector Elts; unsigned BaseTypeID = Record[OpNum]; while (OpNum != Record.size()) { unsigned ElTyID = Record[OpNum++]; Type *ElTy = getTypeByID(ElTyID); if (!ElTy) return error("Invalid getelementptr constexpr record"); - Elts.push_back(ValueList.getConstantFwdRef(Record[OpNum++], ElTy, - ElTyID)); + Elts.push_back(Record[OpNum++]); } if (Elts.size() < 1) @@ -2877,20 +3139,21 @@ return error("Explicit gep operator type does not match pointee type " "of pointer operand"); - ArrayRef Indices(Elts.begin() + 1, Elts.end()); - V = ConstantExpr::getGetElementPtr(PointeeType, Elts[0], Indices, - InBounds, InRangeIndex); + V = BitcodeConstant::create( + Alloc, CurTy, + {Instruction::GetElementPtr, InBounds, InRangeIndex.getValueOr(-1), + PointeeType}, + Elts); break; } case bitc::CST_CODE_CE_SELECT: { // CE_SELECT: [opval#, opval#, opval#] if (Record.size() < 3) return error("Invalid select constexpr record"); - DelayedSelectors.push_back( - {CurTy, CurTyID, Record[0], Record[1], Record[2], NextCstNo}); - (void)ValueList.getConstantFwdRef(NextCstNo, CurTy, CurTyID); - ++NextCstNo; - continue; + V = BitcodeConstant::create( + Alloc, CurTy, Instruction::Select, + {(unsigned)Record[0], (unsigned)Record[1], (unsigned)Record[2]}); + break; } case bitc::CST_CODE_CE_EXTRACTELT : { // CE_EXTRACTELT: [opty, opval, opty, opval] @@ -2901,22 +3164,19 @@ dyn_cast_or_null(getTypeByID(OpTyID)); if (!OpTy) return error("Invalid extractelement constexpr record"); - Constant *Op0 = ValueList.getConstantFwdRef(Record[1], OpTy, OpTyID); - Constant *Op1 = nullptr; + unsigned IdxRecord; if (Record.size() == 4) { unsigned IdxTyID = Record[2]; Type *IdxTy = getTypeByID(IdxTyID); if (!IdxTy) return error("Invalid extractelement constexpr record"); - Op1 = ValueList.getConstantFwdRef(Record[3], IdxTy, IdxTyID); + IdxRecord = Record[3]; } else { // Deprecated, but still needed to read old bitcode files. - Op1 = ValueList.getConstantFwdRef(Record[2], Type::getInt32Ty(Context), - Int32TyID); + IdxRecord = Record[2]; } - if (!Op1) - return error("Invalid extractelement constexpr record"); - V = ConstantExpr::getExtractElement(Op0, Op1); + V = BitcodeConstant::create(Alloc, CurTy, Instruction::ExtractElement, + {(unsigned)Record[1], IdxRecord}); break; } case bitc::CST_CODE_CE_INSERTELT @@ -2924,35 +3184,30 @@ VectorType *OpTy = dyn_cast(CurTy); if (Record.size() < 3 || !OpTy) return error("Invalid insertelement constexpr record"); - Constant *Op0 = ValueList.getConstantFwdRef(Record[0], OpTy, CurTyID); - Constant *Op1 = ValueList.getConstantFwdRef(Record[1], - OpTy->getElementType(), - getContainedTypeID(CurTyID)); - Constant *Op2 = nullptr; + unsigned IdxRecord; if (Record.size() == 4) { unsigned IdxTyID = Record[2]; Type *IdxTy = getTypeByID(IdxTyID); if (!IdxTy) return error("Invalid insertelement constexpr record"); - Op2 = ValueList.getConstantFwdRef(Record[3], IdxTy, IdxTyID); + IdxRecord = Record[3]; } else { // Deprecated, but still needed to read old bitcode files. - Op2 = ValueList.getConstantFwdRef(Record[2], Type::getInt32Ty(Context), - Int32TyID); + IdxRecord = Record[2]; } - if (!Op2) - return error("Invalid insertelement constexpr record"); - V = ConstantExpr::getInsertElement(Op0, Op1, Op2); + V = BitcodeConstant::create( + Alloc, CurTy, Instruction::InsertElement, + {(unsigned)Record[0], (unsigned)Record[1], IdxRecord}); break; } case bitc::CST_CODE_CE_SHUFFLEVEC: { // CE_SHUFFLEVEC: [opval, opval, opval] VectorType *OpTy = dyn_cast(CurTy); if (Record.size() < 3 || !OpTy) return error("Invalid shufflevector constexpr record"); - DelayedShuffles.push_back( - {OpTy, CurTyID, OpTy, Record[0], Record[1], Record[2], NextCstNo}); - ++NextCstNo; - continue; + V = BitcodeConstant::create( + Alloc, CurTy, Instruction::ShuffleVector, + {(unsigned)Record[0], (unsigned)Record[1], (unsigned)Record[2]}); + break; } case bitc::CST_CODE_CE_SHUFVEC_EX: { // [opty, opval, opval, opval] VectorType *RTy = dyn_cast(CurTy); @@ -2960,10 +3215,10 @@ dyn_cast_or_null(getTypeByID(Record[0])); if (Record.size() < 4 || !RTy || !OpTy) return error("Invalid shufflevector constexpr record"); - DelayedShuffles.push_back( - {OpTy, CurTyID, RTy, Record[1], Record[2], Record[3], NextCstNo}); - ++NextCstNo; - continue; + V = BitcodeConstant::create( + Alloc, CurTy, Instruction::ShuffleVector, + {(unsigned)Record[1], (unsigned)Record[2], (unsigned)Record[3]}); + break; } case bitc::CST_CODE_CE_CMP: { // CE_CMP: [opty, opval, opval, pred] if (Record.size() < 4) @@ -2972,13 +3227,11 @@ Type *OpTy = getTypeByID(OpTyID); if (!OpTy) return error("Invalid cmp constexpr record"); - Constant *Op0 = ValueList.getConstantFwdRef(Record[1], OpTy, OpTyID); - Constant *Op1 = ValueList.getConstantFwdRef(Record[2], OpTy, OpTyID); - - if (OpTy->isFPOrFPVectorTy()) - V = ConstantExpr::getFCmp(Record[3], Op0, Op1); - else - V = ConstantExpr::getICmp(Record[3], Op0, Op1); + V = BitcodeConstant::create( + Alloc, CurTy, + {OpTy->isFPOrFPVectorTy() ? Instruction::FCmp : Instruction::ICmp, + (uint8_t)Record[3]}, + {(unsigned)Record[1], (unsigned)Record[2]}); break; } // This maintains backward compatibility, pre-asm dialect keywords. @@ -3107,39 +3360,10 @@ Type *FnTy = getTypeByID(FnTyID); if (!FnTy) return error("Invalid blockaddress record"); - Function *Fn = dyn_cast_or_null( - ValueList.getConstantFwdRef(Record[1], FnTy, FnTyID)); - if (!Fn) - return error("Invalid blockaddress record"); - - // If the function is already parsed we can insert the block address right - // away. - BasicBlock *BB; - unsigned BBID = Record[2]; - if (!BBID) - // Invalid reference to entry block. - return error("Invalid ID"); - if (!Fn->empty()) { - Function::iterator BBI = Fn->begin(), BBE = Fn->end(); - for (size_t I = 0, E = BBID; I != E; ++I) { - if (BBI == BBE) - return error("Invalid ID"); - ++BBI; - } - BB = &*BBI; - } else { - // Otherwise insert a placeholder and remember it so it can be inserted - // when the function is parsed. - auto &FwdBBs = BasicBlockFwdRefs[Fn]; - if (FwdBBs.empty()) - BasicBlockFwdRefQueue.push_back(Fn); - if (FwdBBs.size() < BBID + 1) - FwdBBs.resize(BBID + 1); - if (!FwdBBs[BBID]) - FwdBBs[BBID] = BasicBlock::Create(Context); - BB = FwdBBs[BBID]; - } - V = BlockAddress::get(Fn, BB); + V = BitcodeConstant::create( + Alloc, CurTy, + {BitcodeConstant::BlockAddressOpcode, 0, (unsigned)Record[2]}, + Record[1]); break; } case bitc::CST_CODE_DSO_LOCAL_EQUIVALENT: { @@ -3149,12 +3373,8 @@ Type *GVTy = getTypeByID(GVTyID); if (!GVTy) return error("Invalid dso_local record"); - GlobalValue *GV = dyn_cast_or_null( - ValueList.getConstantFwdRef(Record[1], GVTy, GVTyID)); - if (!GV) - return error("Invalid dso_local record"); - - V = DSOLocalEquivalent::get(GV); + V = BitcodeConstant::create( + Alloc, CurTy, BitcodeConstant::DSOLocalEquivalentOpcode, Record[1]); break; } case bitc::CST_CODE_NO_CFI_VALUE: { @@ -3164,11 +3384,8 @@ Type *GVTy = getTypeByID(GVTyID); if (!GVTy) return error("Invalid no_cfi record"); - GlobalValue *GV = dyn_cast_or_null( - ValueList.getConstantFwdRef(Record[1], GVTy, GVTyID)); - if (!GV) - return error("Invalid no_cfi record"); - V = NoCFIValue::get(GV); + V = BitcodeConstant::create(Alloc, CurTy, BitcodeConstant::NoCFIOpcode, + Record[1]); break; } } @@ -4248,6 +4465,15 @@ unsigned NextValueNo = ValueList.size(); BasicBlock *CurBB = nullptr; unsigned CurBBNo = 0; + // Block into which constant expressions from phi nodes are materialized. + BasicBlock *PhiConstExprBB = nullptr; + // Information about constant expressions materialized into edges. + struct EdgeConstExprInfo { + BasicBlock *From; + BasicBlock *To; + BasicBlock *EdgeBB; + }; + SmallVector EdgeConstExprs; DebugLoc LastLoc; auto getLastInstruction = [&]() -> Instruction * { @@ -4426,7 +4652,7 @@ unsigned OpNum = 0; Value *LHS; unsigned TypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, LHS, TypeID) || + if (getValueTypePair(Record, OpNum, NextValueNo, LHS, TypeID, CurBB) || OpNum+1 > Record.size()) return error("Invalid record"); @@ -4449,8 +4675,9 @@ unsigned OpNum = 0; Value *LHS, *RHS; unsigned TypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, LHS, TypeID) || - popValue(Record, OpNum, NextValueNo, LHS->getType(), TypeID, RHS) || + if (getValueTypePair(Record, OpNum, NextValueNo, LHS, TypeID, CurBB) || + popValue(Record, OpNum, NextValueNo, LHS->getType(), TypeID, RHS, + CurBB) || OpNum+1 > Record.size()) return error("Invalid record"); @@ -4488,7 +4715,7 @@ unsigned OpNum = 0; Value *Op; unsigned OpTypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID) || + if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID, CurBB) || OpNum+2 != Record.size()) return error("Invalid record"); @@ -4534,7 +4761,8 @@ Value *BasePtr; unsigned BasePtrTypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, BasePtr, BasePtrTypeID)) + if (getValueTypePair(Record, OpNum, NextValueNo, BasePtr, BasePtrTypeID, + CurBB)) return error("Invalid record"); if (!Ty) { @@ -4552,7 +4780,7 @@ while (OpNum != Record.size()) { Value *Op; unsigned OpTypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID)) + if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID, CurBB)) return error("Invalid record"); GEPIdx.push_back(Op); } @@ -4593,7 +4821,7 @@ unsigned OpNum = 0; Value *Agg; unsigned AggTypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, Agg, AggTypeID)) + if (getValueTypePair(Record, OpNum, NextValueNo, Agg, AggTypeID, CurBB)) return error("Invalid record"); Type *Ty = Agg->getType(); @@ -4637,11 +4865,11 @@ unsigned OpNum = 0; Value *Agg; unsigned AggTypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, Agg, AggTypeID)) + if (getValueTypePair(Record, OpNum, NextValueNo, Agg, AggTypeID, CurBB)) return error("Invalid record"); Value *Val; unsigned ValTypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, Val, ValTypeID)) + if (getValueTypePair(Record, OpNum, NextValueNo, Val, ValTypeID, CurBB)) return error("Invalid record"); unsigned RecSize = Record.size(); @@ -4687,11 +4915,12 @@ Value *TrueVal, *FalseVal, *Cond; unsigned TypeID; Type *CondType = Type::getInt1Ty(Context); - if (getValueTypePair(Record, OpNum, NextValueNo, TrueVal, TypeID) || + if (getValueTypePair(Record, OpNum, NextValueNo, TrueVal, TypeID, + CurBB) || popValue(Record, OpNum, NextValueNo, TrueVal->getType(), TypeID, - FalseVal) || + FalseVal, CurBB) || popValue(Record, OpNum, NextValueNo, CondType, - getVirtualTypeID(CondType), Cond)) + getVirtualTypeID(CondType), Cond, CurBB)) return error("Invalid record"); I = SelectInst::Create(Cond, TrueVal, FalseVal); @@ -4706,10 +4935,11 @@ unsigned OpNum = 0; Value *TrueVal, *FalseVal, *Cond; unsigned ValTypeID, CondTypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, TrueVal, ValTypeID) || + if (getValueTypePair(Record, OpNum, NextValueNo, TrueVal, ValTypeID, + CurBB) || popValue(Record, OpNum, NextValueNo, TrueVal->getType(), ValTypeID, - FalseVal) || - getValueTypePair(Record, OpNum, NextValueNo, Cond, CondTypeID)) + FalseVal, CurBB) || + getValueTypePair(Record, OpNum, NextValueNo, Cond, CondTypeID, CurBB)) return error("Invalid record"); // select condition can be either i1 or [N x i1] @@ -4739,8 +4969,8 @@ unsigned OpNum = 0; Value *Vec, *Idx; unsigned VecTypeID, IdxTypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, Vec, VecTypeID) || - getValueTypePair(Record, OpNum, NextValueNo, Idx, IdxTypeID)) + if (getValueTypePair(Record, OpNum, NextValueNo, Vec, VecTypeID, CurBB) || + getValueTypePair(Record, OpNum, NextValueNo, Idx, IdxTypeID, CurBB)) return error("Invalid record"); if (!Vec->getType()->isVectorTy()) return error("Invalid type for value"); @@ -4754,14 +4984,14 @@ unsigned OpNum = 0; Value *Vec, *Elt, *Idx; unsigned VecTypeID, IdxTypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, Vec, VecTypeID)) + if (getValueTypePair(Record, OpNum, NextValueNo, Vec, VecTypeID, CurBB)) return error("Invalid record"); if (!Vec->getType()->isVectorTy()) return error("Invalid type for value"); if (popValue(Record, OpNum, NextValueNo, cast(Vec->getType())->getElementType(), - getContainedTypeID(VecTypeID), Elt) || - getValueTypePair(Record, OpNum, NextValueNo, Idx, IdxTypeID)) + getContainedTypeID(VecTypeID), Elt, CurBB) || + getValueTypePair(Record, OpNum, NextValueNo, Idx, IdxTypeID, CurBB)) return error("Invalid record"); I = InsertElementInst::Create(Vec, Elt, Idx); ResTypeID = VecTypeID; @@ -4773,13 +5003,14 @@ unsigned OpNum = 0; Value *Vec1, *Vec2, *Mask; unsigned Vec1TypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, Vec1, Vec1TypeID) || + if (getValueTypePair(Record, OpNum, NextValueNo, Vec1, Vec1TypeID, + CurBB) || popValue(Record, OpNum, NextValueNo, Vec1->getType(), Vec1TypeID, - Vec2)) + Vec2, CurBB)) return error("Invalid record"); unsigned MaskTypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, Mask, MaskTypeID)) + if (getValueTypePair(Record, OpNum, NextValueNo, Mask, MaskTypeID, CurBB)) return error("Invalid record"); if (!Vec1->getType()->isVectorTy() || !Vec2->getType()->isVectorTy()) return error("Invalid type for value"); @@ -4801,8 +5032,9 @@ unsigned OpNum = 0; Value *LHS, *RHS; unsigned LHSTypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, LHS, LHSTypeID) || - popValue(Record, OpNum, NextValueNo, LHS->getType(), LHSTypeID, RHS)) + if (getValueTypePair(Record, OpNum, NextValueNo, LHS, LHSTypeID, CurBB) || + popValue(Record, OpNum, NextValueNo, LHS->getType(), LHSTypeID, RHS, + CurBB)) return error("Invalid record"); if (OpNum >= Record.size()) @@ -4845,7 +5077,7 @@ unsigned OpNum = 0; Value *Op = nullptr; unsigned OpTypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID)) + if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID, CurBB)) return error("Invalid record"); if (OpNum != Record.size()) return error("Invalid record"); @@ -4869,7 +5101,7 @@ BasicBlock *FalseDest = getBasicBlock(Record[1]); Type *CondType = Type::getInt1Ty(Context); Value *Cond = getValue(Record, 2, NextValueNo, CondType, - getVirtualTypeID(CondType)); + getVirtualTypeID(CondType), CurBB); if (!FalseDest || !Cond) return error("Invalid record"); I = BranchInst::Create(TrueDest, FalseDest, Cond); @@ -4883,7 +5115,7 @@ unsigned Idx = 0; Type *TokenTy = Type::getTokenTy(Context); Value *CleanupPad = getValue(Record, Idx++, NextValueNo, TokenTy, - getVirtualTypeID(TokenTy)); + getVirtualTypeID(TokenTy), CurBB); if (!CleanupPad) return error("Invalid record"); BasicBlock *UnwindDest = nullptr; @@ -4903,7 +5135,7 @@ unsigned Idx = 0; Type *TokenTy = Type::getTokenTy(Context); Value *CatchPad = getValue(Record, Idx++, NextValueNo, TokenTy, - getVirtualTypeID(TokenTy)); + getVirtualTypeID(TokenTy), CurBB); if (!CatchPad) return error("Invalid record"); BasicBlock *BB = getBasicBlock(Record[Idx++]); @@ -4923,7 +5155,7 @@ Type *TokenTy = Type::getTokenTy(Context); Value *ParentPad = getValue(Record, Idx++, NextValueNo, TokenTy, - getVirtualTypeID(TokenTy)); + getVirtualTypeID(TokenTy), CurBB); unsigned NumHandlers = Record[Idx++]; @@ -4964,7 +5196,7 @@ Type *TokenTy = Type::getTokenTy(Context); Value *ParentPad = getValue(Record, Idx++, NextValueNo, TokenTy, - getVirtualTypeID(TokenTy)); + getVirtualTypeID(TokenTy), CurBB); unsigned NumArgOperands = Record[Idx++]; @@ -4972,7 +5204,7 @@ for (unsigned Op = 0; Op != NumArgOperands; ++Op) { Value *Val; unsigned ValTypeID; - if (getValueTypePair(Record, Idx, NextValueNo, Val, ValTypeID)) + if (getValueTypePair(Record, Idx, NextValueNo, Val, ValTypeID, nullptr)) return error("Invalid record"); Args.push_back(Val); } @@ -5000,7 +5232,7 @@ Type *OpTy = getTypeByID(OpTyID); unsigned ValueBitWidth = cast(OpTy)->getBitWidth(); - Value *Cond = getValue(Record, 2, NextValueNo, OpTy, OpTyID); + Value *Cond = getValue(Record, 2, NextValueNo, OpTy, OpTyID, CurBB); BasicBlock *Default = getBasicBlock(Record[3]); if (!OpTy || !Cond || !Default) return error("Invalid record"); @@ -5056,7 +5288,7 @@ return error("Invalid record"); unsigned OpTyID = Record[0]; Type *OpTy = getTypeByID(OpTyID); - Value *Cond = getValue(Record, 1, NextValueNo, OpTy, OpTyID); + Value *Cond = getValue(Record, 1, NextValueNo, OpTy, OpTyID, CurBB); BasicBlock *Default = getBasicBlock(Record[2]); if (!OpTy || !Cond || !Default) return error("Invalid record"); @@ -5065,7 +5297,7 @@ InstructionList.push_back(SI); for (unsigned i = 0, e = NumCases; i != e; ++i) { ConstantInt *CaseVal = dyn_cast_or_null( - getFnValueByID(Record[3+i*2], OpTy, OpTyID)); + getFnValueByID(Record[3+i*2], OpTy, OpTyID, nullptr)); BasicBlock *DestBB = getBasicBlock(Record[1+3+i*2]); if (!CaseVal || !DestBB) { delete SI; @@ -5081,7 +5313,7 @@ return error("Invalid record"); unsigned OpTyID = Record[0]; Type *OpTy = getTypeByID(OpTyID); - Value *Address = getValue(Record, 1, NextValueNo, OpTy, OpTyID); + Value *Address = getValue(Record, 1, NextValueNo, OpTy, OpTyID, CurBB); if (!OpTy || !Address) return error("Invalid record"); unsigned NumDests = Record.size()-2; @@ -5120,7 +5352,8 @@ Value *Callee; unsigned CalleeTypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, Callee, CalleeTypeID)) + if (getValueTypePair(Record, OpNum, NextValueNo, Callee, CalleeTypeID, + CurBB)) return error("Invalid record"); PointerType *CalleeTy = dyn_cast(Callee->getType()); @@ -5142,7 +5375,7 @@ for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i, ++OpNum) { unsigned ArgTyID = getContainedTypeID(FTyID, i + 1); Ops.push_back(getValue(Record, OpNum, NextValueNo, FTy->getParamType(i), - ArgTyID)); + ArgTyID, CurBB)); ArgTyIDs.push_back(ArgTyID); if (!Ops.back()) return error("Invalid record"); @@ -5156,7 +5389,7 @@ while (OpNum != Record.size()) { Value *Op; unsigned OpTypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID)) + if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID, CurBB)) return error("Invalid record"); Ops.push_back(Op); ArgTyIDs.push_back(OpTypeID); @@ -5186,7 +5419,7 @@ unsigned Idx = 0; Value *Val = nullptr; unsigned ValTypeID; - if (getValueTypePair(Record, Idx, NextValueNo, Val, ValTypeID)) + if (getValueTypePair(Record, Idx, NextValueNo, Val, ValTypeID, CurBB)) return error("Invalid record"); I = ResumeInst::Create(Val); InstructionList.push_back(I); @@ -5215,7 +5448,8 @@ Value *Callee; unsigned CalleeTypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, Callee, CalleeTypeID)) + if (getValueTypePair(Record, OpNum, NextValueNo, Callee, CalleeTypeID, + CurBB)) return error("Invalid record"); PointerType *OpTy = dyn_cast(Callee->getType()); @@ -5242,7 +5476,7 @@ Arg = getBasicBlock(Record[OpNum]); else Arg = getValue(Record, OpNum, NextValueNo, FTy->getParamType(i), - ArgTyID); + ArgTyID, CurBB); if (!Arg) return error("Invalid record"); Args.push_back(Arg); @@ -5257,7 +5491,7 @@ while (OpNum != Record.size()) { Value *Op; unsigned OpTypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID)) + if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID, CurBB)) return error("Invalid record"); Args.push_back(Op); ArgTyIDs.push_back(OpTypeID); @@ -5306,21 +5540,46 @@ } InstructionList.push_back(PN); + SmallDenseMap Args; for (unsigned i = 0; i != NumArgs; i++) { - Value *V; + BasicBlock *BB = getBasicBlock(Record[i * 2 + 2]); + if (!BB) { + PN->deleteValue(); + return error("Invalid phi BB"); + } + + if (!PhiConstExprBB) + PhiConstExprBB = BasicBlock::Create(Context, "phi.constexpr", F); + // With the new function encoding, it is possible that operands have // negative IDs (for forward references). Use a signed VBR // representation to keep the encoding small. + Value *V; if (UseRelativeIDs) - V = getValueSigned(Record, i * 2 + 1, NextValueNo, Ty, TyID); + V = getValueSigned(Record, i * 2 + 1, NextValueNo, Ty, TyID, + PhiConstExprBB); else - V = getValue(Record, i * 2 + 1, NextValueNo, Ty, TyID); - BasicBlock *BB = getBasicBlock(Record[i * 2 + 2]); - if (!V || !BB) { + V = getValue(Record, i * 2 + 1, NextValueNo, Ty, TyID, + PhiConstExprBB); + if (!V) { PN->deleteValue(); + PhiConstExprBB->eraseFromParent(); return error("Invalid phi record"); } + if (!PhiConstExprBB->empty()) { + auto It = Args.find(BB); + if (It != Args.end()) { + // If this phi argument has already been expanded, reuse the + // previous value instead of materializing a new one. + V = It->second; + PhiConstExprBB->eraseFromParent(); + } else { + EdgeConstExprs.push_back({BB, CurBB, PhiConstExprBB}); + } + PhiConstExprBB = nullptr; + } PN->addIncoming(V, BB); + Args.insert({BB, V}); } I = PN; ResTypeID = TyID; @@ -5355,7 +5614,8 @@ if (BitCode == bitc::FUNC_CODE_INST_LANDINGPAD_OLD) { Value *PersFn = nullptr; unsigned PersFnTypeID; - if (getValueTypePair(Record, Idx, NextValueNo, PersFn, PersFnTypeID)) + if (getValueTypePair(Record, Idx, NextValueNo, PersFn, PersFnTypeID, + nullptr)) return error("Invalid record"); if (!F->hasPersonalityFn()) @@ -5374,7 +5634,8 @@ Value *Val; unsigned ValTypeID; - if (getValueTypePair(Record, Idx, NextValueNo, Val, ValTypeID)) { + if (getValueTypePair(Record, Idx, NextValueNo, Val, ValTypeID, + nullptr)) { delete LP; return error("Invalid record"); } @@ -5410,7 +5671,7 @@ } unsigned OpTyID = Record[1]; Type *OpTy = getTypeByID(OpTyID); - Value *Size = getFnValueByID(Record[2], OpTy, OpTyID); + Value *Size = getFnValueByID(Record[2], OpTy, OpTyID, CurBB); MaybeAlign Align; uint64_t AlignExp = Bitfield::get(Rec) | @@ -5442,7 +5703,7 @@ unsigned OpNum = 0; Value *Op; unsigned OpTypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID) || + if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID, CurBB) || (OpNum + 2 != Record.size() && OpNum + 3 != Record.size())) return error("Invalid record"); @@ -5480,7 +5741,7 @@ unsigned OpNum = 0; Value *Op; unsigned OpTypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID) || + if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID, CurBB) || (OpNum + 4 != Record.size() && OpNum + 5 != Record.size())) return error("Invalid record"); @@ -5524,16 +5785,16 @@ unsigned OpNum = 0; Value *Val, *Ptr; unsigned PtrTypeID, ValTypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, Ptr, PtrTypeID)) + if (getValueTypePair(Record, OpNum, NextValueNo, Ptr, PtrTypeID, CurBB)) return error("Invalid record"); if (BitCode == bitc::FUNC_CODE_INST_STORE) { - if (getValueTypePair(Record, OpNum, NextValueNo, Val, ValTypeID)) + if (getValueTypePair(Record, OpNum, NextValueNo, Val, ValTypeID, CurBB)) return error("Invalid record"); } else { ValTypeID = getContainedTypeID(PtrTypeID); if (popValue(Record, OpNum, NextValueNo, getTypeByID(ValTypeID), - ValTypeID, Val)) + ValTypeID, Val, CurBB)) return error("Invalid record"); } @@ -5560,16 +5821,16 @@ unsigned OpNum = 0; Value *Val, *Ptr; unsigned PtrTypeID, ValTypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, Ptr, PtrTypeID) || + if (getValueTypePair(Record, OpNum, NextValueNo, Ptr, PtrTypeID, CurBB) || !isa(Ptr->getType())) return error("Invalid record"); if (BitCode == bitc::FUNC_CODE_INST_STOREATOMIC) { - if (getValueTypePair(Record, OpNum, NextValueNo, Val, ValTypeID)) + if (getValueTypePair(Record, OpNum, NextValueNo, Val, ValTypeID, CurBB)) return error("Invalid record"); } else { ValTypeID = getContainedTypeID(PtrTypeID); if (popValue(Record, OpNum, NextValueNo, getTypeByID(ValTypeID), - ValTypeID, Val)) + ValTypeID, Val, CurBB)) return error("Invalid record"); } @@ -5603,7 +5864,7 @@ unsigned OpNum = 0; Value *Ptr = nullptr; unsigned PtrTypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, Ptr, PtrTypeID)) + if (getValueTypePair(Record, OpNum, NextValueNo, Ptr, PtrTypeID, CurBB)) return error("Invalid record"); if (!isa(Ptr->getType())) @@ -5612,12 +5873,12 @@ Value *Cmp = nullptr; unsigned CmpTypeID = getContainedTypeID(PtrTypeID); if (popValue(Record, OpNum, NextValueNo, getTypeByID(CmpTypeID), - CmpTypeID, Cmp)) + CmpTypeID, Cmp, CurBB)) return error("Invalid record"); Value *New = nullptr; if (popValue(Record, OpNum, NextValueNo, Cmp->getType(), CmpTypeID, - New) || + New, CurBB) || NumRecords < OpNum + 3 || NumRecords > OpNum + 5) return error("Invalid record"); @@ -5671,7 +5932,7 @@ unsigned OpNum = 0; Value *Ptr = nullptr; unsigned PtrTypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, Ptr, PtrTypeID)) + if (getValueTypePair(Record, OpNum, NextValueNo, Ptr, PtrTypeID, CurBB)) return error("Invalid record"); if (!isa(Ptr->getType())) @@ -5679,11 +5940,12 @@ Value *Cmp = nullptr; unsigned CmpTypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, Cmp, CmpTypeID)) + if (getValueTypePair(Record, OpNum, NextValueNo, Cmp, CmpTypeID, CurBB)) return error("Invalid record"); Value *Val = nullptr; - if (popValue(Record, OpNum, NextValueNo, Cmp->getType(), CmpTypeID, Val)) + if (popValue(Record, OpNum, NextValueNo, Cmp->getType(), CmpTypeID, Val, + CurBB)) return error("Invalid record"); if (NumRecords < OpNum + 3 || NumRecords > OpNum + 6) @@ -5738,7 +6000,7 @@ Value *Ptr = nullptr; unsigned PtrTypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, Ptr, PtrTypeID)) + if (getValueTypePair(Record, OpNum, NextValueNo, Ptr, PtrTypeID, CurBB)) return error("Invalid record"); if (!isa(Ptr->getType())) @@ -5749,10 +6011,10 @@ if (BitCode == bitc::FUNC_CODE_INST_ATOMICRMW_OLD) { ValTypeID = getContainedTypeID(PtrTypeID); if (popValue(Record, OpNum, NextValueNo, - getTypeByID(ValTypeID), ValTypeID, Val)) + getTypeByID(ValTypeID), ValTypeID, Val, CurBB)) return error("Invalid record"); } else { - if (getValueTypePair(Record, OpNum, NextValueNo, Val, ValTypeID)) + if (getValueTypePair(Record, OpNum, NextValueNo, Val, ValTypeID, CurBB)) return error("Invalid record"); } @@ -5832,7 +6094,8 @@ Value *Callee; unsigned CalleeTypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, Callee, CalleeTypeID)) + if (getValueTypePair(Record, OpNum, NextValueNo, Callee, CalleeTypeID, + CurBB)) return error("Invalid record"); PointerType *OpTy = dyn_cast(Callee->getType()); @@ -5858,7 +6121,7 @@ Args.push_back(getBasicBlock(Record[OpNum])); else Args.push_back(getValue(Record, OpNum, NextValueNo, - FTy->getParamType(i), ArgTyID)); + FTy->getParamType(i), ArgTyID, CurBB)); ArgTyIDs.push_back(ArgTyID); if (!Args.back()) return error("Invalid record"); @@ -5872,7 +6135,7 @@ while (OpNum != Record.size()) { Value *Op; unsigned OpTypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID)) + if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID, CurBB)) return error("Invalid record"); Args.push_back(Op); ArgTyIDs.push_back(OpTypeID); @@ -5915,7 +6178,7 @@ return error("Invalid record"); unsigned OpTyID = Record[0]; Type *OpTy = getTypeByID(OpTyID); - Value *Op = getValue(Record, 1, NextValueNo, OpTy, OpTyID); + Value *Op = getValue(Record, 1, NextValueNo, OpTy, OpTyID, CurBB); ResTypeID = Record[2]; Type *ResTy = getTypeByID(ResTypeID); if (!OpTy || !Op || !ResTy) @@ -5939,7 +6202,7 @@ while (OpNum != Record.size()) { Value *Op; unsigned OpTypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID)) + if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID, CurBB)) return error("Invalid record"); Inputs.push_back(Op); } @@ -5952,7 +6215,7 @@ unsigned OpNum = 0; Value *Op = nullptr; unsigned OpTypeID; - if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID)) + if (getValueTypePair(Record, OpNum, NextValueNo, Op, OpTypeID, CurBB)) return error("Invalid record"); if (OpNum != Record.size()) return error("Invalid record"); @@ -6014,6 +6277,16 @@ if (MDLoader->hasFwdRefs()) return error("Invalid function metadata: outgoing forward refs"); + if (PhiConstExprBB) + PhiConstExprBB->eraseFromParent(); + + for (const EdgeConstExprInfo &Info : EdgeConstExprs) { + BranchInst::Create(Info.To, Info.EdgeBB); + Info.From->getTerminator()->replaceSuccessorWith(Info.To, Info.EdgeBB); + Info.To->replacePhiUsesWith(Info.From, Info.EdgeBB); + Info.EdgeBB->moveBefore(Info.To); + } + // Trim the value list down to the size it was before we parsed this function. ValueList.shrinkTo(ModuleValueListSize); MDLoader->shrinkTo(ModuleMDLoaderSize); Index: llvm/lib/Bitcode/Reader/MetadataLoader.cpp =================================================================== --- llvm/lib/Bitcode/Reader/MetadataLoader.cpp +++ llvm/lib/Bitcode/Reader/MetadataLoader.cpp @@ -1227,7 +1227,8 @@ } MetadataList.assignValue( - LocalAsMetadata::get(ValueList.getValueFwdRef(Record[1], Ty, TyID)), + LocalAsMetadata::get(ValueList.getValueFwdRef( + Record[1], Ty, TyID, /*ConstExprInsertBB*/ nullptr)), NextMetadataNo); NextMetadataNo++; break; @@ -1247,8 +1248,8 @@ if (Ty->isMetadataTy()) Elts.push_back(getMD(Record[i + 1])); else if (!Ty->isVoidTy()) { - auto *MD = ValueAsMetadata::get( - ValueList.getValueFwdRef(Record[i + 1], Ty, TyID)); + auto *MD = ValueAsMetadata::get(ValueList.getValueFwdRef( + Record[i + 1], Ty, TyID, /*ConstExprInsertBB*/ nullptr)); assert(isa(MD) && "Expected non-function-local metadata"); Elts.push_back(MD); @@ -1269,7 +1270,8 @@ return error("Invalid record"); MetadataList.assignValue( - ValueAsMetadata::get(ValueList.getValueFwdRef(Record[1], Ty, TyID)), + ValueAsMetadata::get(ValueList.getValueFwdRef( + Record[1], Ty, TyID, /*ConstExprInsertBB*/ nullptr)), NextMetadataNo); NextMetadataNo++; break; Index: llvm/lib/Bitcode/Reader/ValueList.h =================================================================== --- llvm/lib/Bitcode/Reader/ValueList.h +++ llvm/lib/Bitcode/Reader/ValueList.h @@ -22,6 +22,7 @@ class Constant; class Error; +template class Expected; class LLVMContext; class Type; class Value; @@ -30,30 +31,23 @@ /// Maps Value ID to pair of Value* and Type ID. std::vector> ValuePtrs; - /// As we resolve forward-referenced constants, we add information about them - /// to this vector. This allows us to resolve them in bulk instead of - /// resolving each reference at a time. See the code in - /// ResolveConstantForwardRefs for more information about this. - /// - /// The key of this vector is the placeholder constant, the value is the slot - /// number that holds the resolved value. - using ResolveConstantsTy = std::vector>; - ResolveConstantsTy ResolveConstants; LLVMContext &Context; /// Maximum number of valid references. Forward references exceeding the /// maximum must be invalid. unsigned RefsUpperBound; + using MaterializeValueFnTy = + std::function(unsigned, BasicBlock *)>; + MaterializeValueFnTy MaterializeValueFn; + public: - BitcodeReaderValueList(LLVMContext &C, size_t RefsUpperBound) + BitcodeReaderValueList(LLVMContext &C, size_t RefsUpperBound, + MaterializeValueFnTy MaterializeValueFn) : Context(C), RefsUpperBound(std::min((size_t)std::numeric_limits::max(), - RefsUpperBound)) {} - - ~BitcodeReaderValueList() { - assert(ResolveConstants.empty() && "Constants not resolved?"); - } + RefsUpperBound)), + MaterializeValueFn(MaterializeValueFn) {} // vector compatibility methods unsigned size() const { return ValuePtrs.size(); } @@ -65,7 +59,6 @@ } void clear() { - assert(ResolveConstants.empty() && "Constants not resolved?"); ValuePtrs.clear(); } @@ -90,14 +83,15 @@ ValuePtrs.resize(N); } - Constant *getConstantFwdRef(unsigned Idx, Type *Ty, unsigned TyID); - Value *getValueFwdRef(unsigned Idx, Type *Ty, unsigned TyID); + void replaceValueWithoutRAUW(unsigned ValNo, Value *NewV) { + assert(ValNo < ValuePtrs.size()); + ValuePtrs[ValNo].first = NewV; + } - Error assignValue(unsigned Idx, Value *V, unsigned TypeID); + Value *getValueFwdRef(unsigned Idx, Type *Ty, unsigned TyID, + BasicBlock *ConstExprInsertBB); - /// Once all constants are read, this method bulk resolves any forward - /// references. - void resolveConstantForwardRefs(); + Error assignValue(unsigned Idx, Value *V, unsigned TypeID); }; } // end namespace llvm Index: llvm/lib/Bitcode/Reader/ValueList.cpp =================================================================== --- llvm/lib/Bitcode/Reader/ValueList.cpp +++ llvm/lib/Bitcode/Reader/ValueList.cpp @@ -23,44 +23,6 @@ using namespace llvm; -namespace llvm { - -namespace { - -/// A class for maintaining the slot number definition -/// as a placeholder for the actual definition for forward constants defs. -class ConstantPlaceHolder : public ConstantExpr { -public: - explicit ConstantPlaceHolder(Type *Ty, LLVMContext &Context) - : ConstantExpr(Ty, Instruction::UserOp1, &Op<0>(), 1) { - Op<0>() = UndefValue::get(Type::getInt32Ty(Context)); - } - - ConstantPlaceHolder &operator=(const ConstantPlaceHolder &) = delete; - - // allocate space for exactly one operand - void *operator new(size_t s) { return User::operator new(s, 1); } - - /// Methods to support type inquiry through isa, cast, and dyn_cast. - static bool classof(const Value *V) { - return isa(V) && - cast(V)->getOpcode() == Instruction::UserOp1; - } - - /// Provide fast operand accessors - DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Value); -}; - -} // end anonymous namespace - -// FIXME: can we inherit this from ConstantExpr? -template <> -struct OperandTraits - : public FixedNumOperandTraits {}; -DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ConstantPlaceHolder, Value) - -} // end namespace llvm - Error BitcodeReaderValueList::assignValue(unsigned Idx, Value *V, unsigned TypeID) { if (Idx == size()) { @@ -78,48 +40,21 @@ return Error::success(); } - // Handle constants and non-constants (e.g. instrs) differently for - // efficiency. - if (Constant *PHC = dyn_cast(&*Old.first)) { - ResolveConstants.push_back(std::make_pair(PHC, Idx)); - Old.first = V; - Old.second = TypeID; - } else { - // If there was a forward reference to this value, replace it. - Value *PrevVal = Old.first; - if (PrevVal->getType() != V->getType()) - return createStringError( - std::errc::illegal_byte_sequence, - "Assigned value does not match type of forward declaration"); - Old.first->replaceAllUsesWith(V); - PrevVal->deleteValue(); - } + assert(!isa(&*Old.first) && "Shouldn't update constant"); + // If there was a forward reference to this value, replace it. + Value *PrevVal = Old.first; + if (PrevVal->getType() != V->getType()) + return createStringError( + std::errc::illegal_byte_sequence, + "Assigned value does not match type of forward declaration"); + Old.first->replaceAllUsesWith(V); + PrevVal->deleteValue(); return Error::success(); } -Constant *BitcodeReaderValueList::getConstantFwdRef(unsigned Idx, Type *Ty, - unsigned TyID) { - // Bail out for a clearly invalid value. - if (Idx >= RefsUpperBound) - return nullptr; - - if (Idx >= size()) - resize(Idx + 1); - - if (Value *V = ValuePtrs[Idx].first) { - if (Ty != V->getType()) - report_fatal_error("Type mismatch in constant table!"); - return cast(V); - } - - // Create and return a placeholder, which will later be RAUW'd. - Constant *C = new ConstantPlaceHolder(Ty, Context); - ValuePtrs[Idx] = {C, TyID}; - return C; -} - Value *BitcodeReaderValueList::getValueFwdRef(unsigned Idx, Type *Ty, - unsigned TyID) { + unsigned TyID, + BasicBlock *ConstExprInsertBB) { // Bail out for a clearly invalid value. if (Idx >= RefsUpperBound) return nullptr; @@ -131,7 +66,14 @@ // If the types don't match, it's invalid. if (Ty && Ty != V->getType()) return nullptr; - return V; + + Expected MaybeV = MaterializeValueFn(Idx, ConstExprInsertBB); + if (!MaybeV) { + // TODO: We might want to propagate the precise error message here. + consumeError(MaybeV.takeError()); + return nullptr; + } + return MaybeV.get(); } // No type specified, must be invalid reference. @@ -143,83 +85,3 @@ ValuePtrs[Idx] = {V, TyID}; return V; } - -/// Once all constants are read, this method bulk resolves any forward -/// references. The idea behind this is that we sometimes get constants (such -/// as large arrays) which reference *many* forward ref constants. Replacing -/// each of these causes a lot of thrashing when building/reuniquing the -/// constant. Instead of doing this, we look at all the uses and rewrite all -/// the place holders at once for any constant that uses a placeholder. -void BitcodeReaderValueList::resolveConstantForwardRefs() { - // Sort the values by-pointer so that they are efficient to look up with a - // binary search. - llvm::sort(ResolveConstants); - - SmallVector NewOps; - - while (!ResolveConstants.empty()) { - Value *RealVal = operator[](ResolveConstants.back().second); - Constant *Placeholder = ResolveConstants.back().first; - ResolveConstants.pop_back(); - - // Loop over all users of the placeholder, updating them to reference the - // new value. If they reference more than one placeholder, update them all - // at once. - while (!Placeholder->use_empty()) { - auto UI = Placeholder->user_begin(); - User *U = *UI; - - // If the using object isn't uniqued, just update the operands. This - // handles instructions and initializers for global variables. - if (!isa(U) || isa(U)) { - UI.getUse().set(RealVal); - continue; - } - - // Otherwise, we have a constant that uses the placeholder. Replace that - // constant with a new constant that has *all* placeholder uses updated. - Constant *UserC = cast(U); - for (User::op_iterator I = UserC->op_begin(), E = UserC->op_end(); I != E; - ++I) { - Value *NewOp; - if (!isa(*I)) { - // Not a placeholder reference. - NewOp = *I; - } else if (*I == Placeholder) { - // Common case is that it just references this one placeholder. - NewOp = RealVal; - } else { - // Otherwise, look up the placeholder in ResolveConstants. - ResolveConstantsTy::iterator It = llvm::lower_bound( - ResolveConstants, - std::pair(cast(*I), 0)); - assert(It != ResolveConstants.end() && It->first == *I); - NewOp = operator[](It->second); - } - - NewOps.push_back(cast(NewOp)); - } - - // Make the new constant. - Constant *NewC; - if (ConstantArray *UserCA = dyn_cast(UserC)) { - NewC = ConstantArray::get(UserCA->getType(), NewOps); - } else if (ConstantStruct *UserCS = dyn_cast(UserC)) { - NewC = ConstantStruct::get(UserCS->getType(), NewOps); - } else if (isa(UserC)) { - NewC = ConstantVector::get(NewOps); - } else { - assert(isa(UserC) && "Must be a ConstantExpr."); - NewC = cast(UserC)->getWithOperands(NewOps); - } - - UserC->replaceAllUsesWith(NewC); - UserC->destroyConstant(); - NewOps.clear(); - } - - // Update all ValueHandles, they should be the only users at this point. - Placeholder->replaceAllUsesWith(RealVal); - delete cast(Placeholder); - } -} Index: llvm/lib/Bitcode/Writer/ValueEnumerator.cpp =================================================================== --- llvm/lib/Bitcode/Writer/ValueEnumerator.cpp +++ llvm/lib/Bitcode/Writer/ValueEnumerator.cpp @@ -50,17 +50,12 @@ struct OrderMap { DenseMap> IDs; - unsigned LastGlobalConstantID = 0; unsigned LastGlobalValueID = 0; OrderMap() = default; - bool isGlobalConstant(unsigned ID) const { - return ID <= LastGlobalConstantID; - } - bool isGlobalValue(unsigned ID) const { - return ID <= LastGlobalValueID && !isGlobalConstant(ID); + return ID <= LastGlobalValueID; } unsigned size() const { return IDs.size(); } @@ -84,7 +79,7 @@ return; if (const Constant *C = dyn_cast(V)) { - if (C->getNumOperands() && !isa(C)) { + if (C->getNumOperands()) { for (const Value *Op : C->operands()) if (!isa(Op) && !isa(Op)) orderValue(Op, OM); @@ -104,39 +99,40 @@ // and ValueEnumerator::incorporateFunction(). OrderMap OM; - // In the reader, initializers of GlobalValues are set *after* all the - // globals have been read. Rather than awkwardly modeling this behaviour - // directly in predictValueUseListOrderImpl(), just assign IDs to - // initializers of GlobalValues before GlobalValues themselves to model this - // implicitly. - for (const GlobalVariable &G : M.globals()) - if (G.hasInitializer()) - if (!isa(G.getInitializer())) - orderValue(G.getInitializer(), OM); - for (const GlobalAlias &A : M.aliases()) - if (!isa(A.getAliasee())) - orderValue(A.getAliasee(), OM); - for (const GlobalIFunc &I : M.ifuncs()) - if (!isa(I.getResolver())) - orderValue(I.getResolver(), OM); - for (const Function &F : M) { - for (const Use &U : F.operands()) - if (!isa(U.get())) - orderValue(U.get(), OM); - } + // Initializers of GlobalValues are processed in + // BitcodeReader::ResolveGlobalAndAliasInits(). Match the order there rather + // than ValueEnumerator, and match the code in predictValueUseListOrderImpl() + // by giving IDs in reverse order. + // + // Since GlobalValues never reference each other directly (just through + // initializers), their relative IDs only matter for determining order of + // uses in their initializers. + for (const GlobalVariable &G : reverse(M.globals())) + orderValue(&G, OM); + for (const GlobalAlias &A : reverse(M.aliases())) + orderValue(&A, OM); + for (const GlobalIFunc &I : reverse(M.ifuncs())) + orderValue(&I, OM); + for (const Function &F : reverse(M)) + orderValue(&F, OM); + OM.LastGlobalValueID = OM.size(); - // As constants used in metadata operands are emitted as module-level - // constants, we must order them before other operands. Also, we must order - // these before global values, as these will be read before setting the - // global values' initializers. The latter matters for constants which have - // uses towards other constants that are used as initializers. auto orderConstantValue = [&OM](const Value *V) { - if ((isa(V) && !isa(V)) || isa(V)) + if (isa(V) || isa(V)) orderValue(V, OM); }; + for (const Function &F : M) { if (F.isDeclaration()) continue; + // Here we need to match the union of ValueEnumerator::incorporateFunction() + // and WriteFunction(). Basic blocks are implicitly declared before + // anything else (by declaring their size). + for (const BasicBlock &BB : F) + orderValue(&BB, OM); + + // Metadata used by instructions is decoded before the actual instructions, + // so visit any constants used by it beforehand. for (const BasicBlock &BB : F) for (const Instruction &I : BB) for (const Value *V : I.operands()) { @@ -151,49 +147,17 @@ } } } - } - OM.LastGlobalConstantID = OM.size(); - // Initializers of GlobalValues are processed in - // BitcodeReader::ResolveGlobalAndAliasInits(). Match the order there rather - // than ValueEnumerator, and match the code in predictValueUseListOrderImpl() - // by giving IDs in reverse order. - // - // Since GlobalValues never reference each other directly (just through - // initializers), their relative IDs only matter for determining order of - // uses in their initializers. - for (const Function &F : M) - orderValue(&F, OM); - for (const GlobalAlias &A : M.aliases()) - orderValue(&A, OM); - for (const GlobalIFunc &I : M.ifuncs()) - orderValue(&I, OM); - for (const GlobalVariable &G : M.globals()) - orderValue(&G, OM); - OM.LastGlobalValueID = OM.size(); - - for (const Function &F : M) { - if (F.isDeclaration()) - continue; - // Here we need to match the union of ValueEnumerator::incorporateFunction() - // and WriteFunction(). Basic blocks are implicitly declared before - // anything else (by declaring their size). - for (const BasicBlock &BB : F) - orderValue(&BB, OM); for (const Argument &A : F.args()) orderValue(&A, OM); for (const BasicBlock &BB : F) for (const Instruction &I : BB) { for (const Value *Op : I.operands()) - if ((isa(*Op) && !isa(*Op)) || - isa(*Op)) - orderValue(Op, OM); + orderConstantValue(Op); if (auto *SVI = dyn_cast(&I)) orderValue(SVI->getShuffleMaskForBitcode(), OM); - } - for (const BasicBlock &BB : F) - for (const Instruction &I : BB) orderValue(&I, OM); + } } return OM; } @@ -223,18 +187,6 @@ auto LID = OM.lookup(LU->getUser()).first; auto RID = OM.lookup(RU->getUser()).first; - // Global values are processed in reverse order. - // - // Moreover, initializers of GlobalValues are set *after* all the globals - // have been read (despite having earlier IDs). Rather than awkwardly - // modeling this behaviour here, orderModule() has assigned IDs to - // initializers of GlobalValues before GlobalValues themselves. - if (OM.isGlobalValue(LID) && OM.isGlobalValue(RID)) { - if (LID == RID) - return LU->getOperandNo() > RU->getOperandNo(); - return LID < RID; - } - // If ID is 4, then expect: 7 6 5 1 2 3. if (LID < RID) { if (RID <= ID) @@ -317,16 +269,25 @@ predictValueUseListOrder(&A, &F, OM, Stack); for (const BasicBlock &BB : F) for (const Instruction &I : BB) { - for (const Value *Op : I.operands()) + for (const Value *Op : I.operands()) { if (isa(*Op) || isa(*Op)) // Visit GlobalValues. predictValueUseListOrder(Op, &F, OM, Stack); + if (const auto *MAV = dyn_cast(Op)) { + if (const auto *VAM = + dyn_cast(MAV->getMetadata())) { + predictValueUseListOrder(VAM->getValue(), &F, OM, Stack); + } else if (const auto *AL = + dyn_cast(MAV->getMetadata())) { + for (const auto *VAM : AL->getArgs()) + predictValueUseListOrder(VAM->getValue(), &F, OM, Stack); + } + } + } if (auto *SVI = dyn_cast(&I)) predictValueUseListOrder(SVI->getShuffleMaskForBitcode(), &F, OM, Stack); - } - for (const BasicBlock &BB : F) - for (const Instruction &I : BB) predictValueUseListOrder(&I, &F, OM, Stack); + } } // Visit globals last, since the module-level use-list block will be seen Index: llvm/test/Bitcode/constexpr-to-instr.ll =================================================================== --- /dev/null +++ llvm/test/Bitcode/constexpr-to-instr.ll @@ -0,0 +1,187 @@ +; RUN: llvm-as < %s | llvm-dis -expand-constant-exprs | FileCheck %s + +@g = extern_weak global i32 + +define i64 @test_cast() { +; CHECK-LABEL: define i64 @test_cast() { +; CHECK-NEXT: %constexpr = ptrtoint ptr @g to i64 +; CHECK-NEXT: ret i64 %constexpr + ret i64 ptrtoint (ptr @g to i64) +} + +define i1 @test_icmp() { +; CHECK-LABEL: define i1 @test_icmp() { +; CHECK-NEXT: %constexpr = ptrtoint ptr @g to i64 +; CHECK-NEXT: %constexpr1 = icmp ne i64 %constexpr, 0 +; CHECK-NEXT: ret i1 %constexpr1 + ret i1 icmp ne (i64 ptrtoint (ptr @g to i64), i64 0) +} + +define i32 @test_select() { +; CHECK-LABEL: define i32 @test_select() { +; CHECK-NEXT: %constexpr = ptrtoint ptr @g to i64 +; CHECK-NEXT: %constexpr1 = icmp ne i64 %constexpr, 0 +; CHECK-NEXT: %constexpr2 = select i1 %constexpr1, i32 1, i32 2 +; CHECK-NEXT: ret i32 %constexpr2 + ret i32 select (i1 icmp ne (i64 ptrtoint (ptr @g to i64), i64 0), i32 1, i32 2) +} + +define i8 @test_extractelement() { +; CHECK-LABEL: define i8 @test_extractelement() { +; CHECK-NEXT: %constexpr = ptrtoint ptr @g to i64 +; CHECK-NEXT: %constexpr1 = icmp ne i64 %constexpr, 0 +; CHECK-NEXT: %constexpr2 = select i1 %constexpr1, <2 x i8> zeroinitializer, <2 x i8> +; CHECK-NEXT: %constexpr3 = extractelement <2 x i8> %constexpr2, i32 0 +; CHECK-NEXT: ret i8 %constexpr3 + ret i8 extractelement (<2 x i8> select (i1 icmp ne (i64 ptrtoint (ptr @g to i64), i64 0), <2 x i8> zeroinitializer, <2 x i8> ), i32 0) +} + +define <2 x i8> @test_insertelement() { +; CHECK-LABEL: define <2 x i8> @test_insertelement() { +; CHECK-NEXT: %constexpr = ptrtoint ptr @g to i32 +; CHECK-NEXT: %constexpr1 = insertelement <2 x i8> poison, i8 42, i32 %constexpr +; CHECK-NEXT: ret <2 x i8> %constexpr1 + ret <2 x i8> insertelement (<2 x i8> poison, i8 42, i32 ptrtoint (ptr @g to i32)) +} + +define double @test_fneg() { +; CHECK-LABEL: define double @test_fneg() { +; CHECK-NEXT: %constexpr = ptrtoint ptr @g to i64 +; CHECK-NEXT: %constexpr1 = bitcast i64 %constexpr to double +; CHECK-NEXT: %constexpr2 = fneg double %constexpr1 + ret double fneg (double bitcast (i64 ptrtoint (ptr @g to i64) to double)) +} + +define i64 @test_flags() { +; CHECK-LABEL: define i64 @test_flags() { +; CHECK-NEXT: %constexpr = ptrtoint ptr @g to i64 +; CHECK-NEXT: %constexpr1 = add nuw i64 %constexpr, 1 +; CHECK-NEXT: ret i64 %constexpr1 + ret i64 add nuw (i64 ptrtoint (ptr @g to i64), i64 1) +} + +define <3 x i64> @test_vector() { +; CHECK-LABEL: define <3 x i64> @test_vector() { +; CHECK-NEXT: %constexpr = ptrtoint ptr @g to i64 +; CHECK-NEXT: %constexpr.ins = insertelement <3 x i64> poison, i64 5, i32 0 +; CHECK-NEXT: %constexpr.ins1 = insertelement <3 x i64> %constexpr.ins, i64 %constexpr, i32 1 +; CHECK-NEXT: %constexpr.ins2 = insertelement <3 x i64> %constexpr.ins1, i64 7, i32 2 + ret <3 x i64> +} + +define i64 @test_reused_expr() { +; CHECK-LABEL: define i64 @test_reused_expr() { +; CHECK-NEXT: %constexpr = ptrtoint ptr @g to i64 +; CHECK-NEXT: %constexpr1 = add i64 %constexpr, %constexpr +; CHECK-NEXT: ret i64 %constexpr1 + ret i64 add (i64 ptrtoint (ptr @g to i64), i64 ptrtoint (ptr @g to i64)) +} + +define i64 @test_mid_block(i64 %arg) { +; CHECK-LABEL: define i64 @test_mid_block(i64 %arg) { +; CHECK-NEXT: %x = mul i64 %arg, 3 +; CHECK-NEXT: %constexpr = ptrtoint ptr @g to i64 +; CHECK-NEXT: %add = add i64 %x, %constexpr +; CHECK-NEXT: ret i64 %add + %x = mul i64 %arg, 3 + %add = add i64 %x, ptrtoint (ptr @g to i64) + ret i64 %add +} + +define i64 @test_phi1(i1 %c) { +; CHECK-LABEL: define i64 @test_phi1(i1 %c) { +; CHECK: entry: +; CHECK-NEXT: br i1 %c, label %if, label %join +; CHECK: if: +; CHECK-NEXT: br label %phi.constexpr +; CHECK: phi.constexpr: +; CHECK-NEXT: %constexpr = ptrtoint ptr @g to i64 +; CHECK-NEXT: br label %join +; CHECK: join: +; CHECK-NEXT: %phi = phi i64 [ 0, %entry ], [ %constexpr, %phi.constexpr ] +; CHECK-NEXT: ret i64 %phi +entry: + br i1 %c, label %if, label %join + +if: + br label %join + +join: + %phi = phi i64 [ 0, %entry ], [ ptrtoint (ptr @g to i64), %if ] + ret i64 %phi +} + +define i64 @test_phi2(i1 %c) { +; CHECK-LABEL: define i64 @test_phi2(i1 %c) { +; CHECK: entry: +; CHECK-NEXT: br i1 %c, label %if, label %join +; CHECK: phi.constexpr: +; CHECK-NEXT: %constexpr = ptrtoint ptr @g to i64 +; CHECK-NEXT: br label %join +; CHECK: join: +; CHECK-NEXT: %phi = phi i64 [ 0, %entry ], [ %constexpr, %phi.constexpr ] +; CHECK-NEXT: ret i64 %phi +; CHECK: if: +; CHECK-NEXT: br label %phi.constexpr +entry: + br i1 %c, label %if, label %join + +join: + %phi = phi i64 [ 0, %entry ], [ ptrtoint (ptr @g to i64), %if ] + ret i64 %phi + +if: + br label %join +} + +define i64 @test_phi3(i1 %c) { +; CHECK-LABEL: define i64 @test_phi3(i1 %c) { +; CHECK: entry: +; CHECK-NEXT: br i1 %c, label %if, label %phi.constexpr +; CHECK: if: +; CHECK-NEXT: br label %join +; CHECK: phi.constexpr: +; CHECK-NEXT: %constexpr = ptrtoint ptr @g to i64 +; CHECK-NEXT: br label %join +; CHECK: join: +; CHECK-NEXT: %phi = phi i64 [ %constexpr, %phi.constexpr ], [ 0, %if ] +; CHECK-NEXT: ret i64 %phi +entry: + br i1 %c, label %if, label %join + +if: + br label %join + +join: + %phi = phi i64 [ ptrtoint (ptr @g to i64), %entry ], [ 0, %if ] + ret i64 %phi +} + +define i64 @test_phi4(i32 %x) { +; CHECK-LABEL: define i64 @test_phi4(i32 %x) { +; CHECK: entry: +; CHECK-NEXT: switch i32 %x, label %default [ +; CHECK-NEXT: i32 0, label %phi.constexpr +; CHECK-NEXT: i32 1, label %phi.constexpr +; CHECK-NEXT: ] +; CHECK: default: +; CHECK-NEXT: br label %join +; CHECK: phi.constexpr: +; CHECK-NEXT: %constexpr = ptrtoint ptr @g to i64 +; CHECK-NEXT: br label %join +; CHECK: join: +; CHECK-NEXT: %phi = phi i64 [ %constexpr, %phi.constexpr ], [ %constexpr, %phi.constexpr ], [ 0, %default ] +; CHECK-NEXT: ret i64 %phi +entry: + switch i32 %x, label %default [ + i32 0, label %join + i32 1, label %join + ] + +default: + br label %join + +join: + %phi = phi i64 [ ptrtoint (ptr @g to i64), %entry ], [ ptrtoint (ptr @g to i64), %entry ], [ 0, %default ] + ret i64 %phi +}