From d9a3bad4487dee0b9ed1a0f5555dffe605826158 Mon Sep 17 00:00:00 2001 From: Jan Wen Voung Date: Thu, 11 Oct 2012 20:20:40 +0000 Subject: [PATCH] Change encoding of instruction operands in bitcode binaries to be relative to the instruction position. The old encoding would give an absolute ID which counts up within a function, and only resets at the next function. I.e., Instead of having: ... = icmp eq i32 n-1, n-2 br i1 ..., label %bb1, label %bb2 it will now be roughly: ... = icmp eq i32 1, 2 br i1 1, label %bb1, label %bb2 This makes it so that ids remain relatively small and can be encoded in fewer bits. With this encoding, forward reference operands will be given negative-valued IDs. Use signed VBRs for the most common case of forward references, which is phi instructions. To retain backward compatibility we bump the bitcode version from 0 to 1 to distinguish between the different encodings. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165739 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Bitcode/BitstreamReader.h | 2 +- lib/Bitcode/Reader/BitcodeReader.cpp | 86 ++++++------ lib/Bitcode/Reader/BitcodeReader.h | 67 ++++++++-- lib/Bitcode/Writer/BitcodeWriter.cpp | 123 +++++++++++------- .../Bitcode/function-encoding-rel-operands.ll | 49 +++++++ 5 files changed, 236 insertions(+), 91 deletions(-) create mode 100644 test/Bitcode/function-encoding-rel-operands.ll diff --git a/include/llvm/Bitcode/BitstreamReader.h b/include/llvm/Bitcode/BitstreamReader.h index 3daef789d61..840f57e7526 100644 --- a/include/llvm/Bitcode/BitstreamReader.h +++ b/include/llvm/Bitcode/BitstreamReader.h @@ -409,7 +409,7 @@ public: } /// EnterSubBlock - Having read the ENTER_SUBBLOCK abbrevid, enter - /// the block, and return true if the block is valid. + /// the block, and return true if the block has an error. bool EnterSubBlock(unsigned BlockID, unsigned *NumWordsP = 0) { // Save the current block's state on BlockScope. BlockScope.push_back(Block(CurCodeSize)); diff --git a/lib/Bitcode/Reader/BitcodeReader.cpp b/lib/Bitcode/Reader/BitcodeReader.cpp index 8860ef065c6..1a3a7b0f3f5 100644 --- a/lib/Bitcode/Reader/BitcodeReader.cpp +++ b/lib/Bitcode/Reader/BitcodeReader.cpp @@ -891,9 +891,9 @@ bool BitcodeReader::ParseMetadata() { } } -/// DecodeSignRotatedValue - Decode a signed value stored with the sign bit in +/// decodeSignRotatedValue - Decode a signed value stored with the sign bit in /// the LSB for dense VBR encoding. -static uint64_t DecodeSignRotatedValue(uint64_t V) { +uint64_t BitcodeReader::decodeSignRotatedValue(uint64_t V) { if ((V & 1) == 0) return V >> 1; if (V != 1) @@ -943,7 +943,7 @@ bool BitcodeReader::ResolveGlobalAndAliasInits() { static APInt ReadWideAPInt(ArrayRef Vals, unsigned TypeBits) { SmallVector Words(Vals.size()); std::transform(Vals.begin(), Vals.end(), Words.begin(), - DecodeSignRotatedValue); + BitcodeReader::decodeSignRotatedValue); return APInt(TypeBits, Words); } @@ -997,7 +997,7 @@ bool BitcodeReader::ParseConstants() { case bitc::CST_CODE_INTEGER: // INTEGER: [intval] if (!CurTy->isIntegerTy() || Record.empty()) return Error("Invalid CST_INTEGER record"); - V = ConstantInt::get(CurTy, DecodeSignRotatedValue(Record[0])); + V = ConstantInt::get(CurTy, decodeSignRotatedValue(Record[0])); break; case bitc::CST_CODE_WIDE_INTEGER: {// WIDE_INTEGER: [n x intval] if (!CurTy->isIntegerTy() || Record.empty()) @@ -1524,13 +1524,22 @@ bool BitcodeReader::ParseModule(bool Resume) { // Read a record. switch (Stream.ReadRecord(Code, Record)) { default: break; // Default behavior, ignore unknown content. - case bitc::MODULE_CODE_VERSION: // VERSION: [version#] + case bitc::MODULE_CODE_VERSION: { // VERSION: [version#] if (Record.size() < 1) return Error("Malformed MODULE_CODE_VERSION"); - // Only version #0 is supported so far. - if (Record[0] != 0) - return Error("Unknown bitstream version!"); + // Only version #0 and #1 are supported so far. + unsigned module_version = Record[0]; + switch (module_version) { + default: return Error("Unknown bitstream version!"); + case 0: + UseRelativeIDs = false; + break; + case 1: + UseRelativeIDs = true; + break; + } break; + } case bitc::MODULE_CODE_TRIPLE: { // TRIPLE: [strchr x N] std::string S; if (ConvertToString(Record, 0, S)) @@ -1797,13 +1806,6 @@ bool BitcodeReader::ParseModuleTriple(std::string &Triple) { // Read a record. switch (Stream.ReadRecord(Code, Record)) { default: break; // Default behavior, ignore unknown content. - case bitc::MODULE_CODE_VERSION: // VERSION: [version#] - if (Record.size() < 1) - return Error("Malformed MODULE_CODE_VERSION"); - // Only version #0 is supported so far. - if (Record[0] != 0) - return Error("Unknown bitstream version!"); - break; case bitc::MODULE_CODE_TRIPLE: { // TRIPLE: [strchr x N] std::string S; if (ConvertToString(Record, 0, S)) @@ -2016,7 +2018,7 @@ bool BitcodeReader::ParseFunctionBody(Function *F) { unsigned OpNum = 0; Value *LHS, *RHS; if (getValueTypePair(Record, OpNum, NextValueNo, LHS) || - getValue(Record, OpNum, LHS->getType(), RHS) || + popValue(Record, OpNum, NextValueNo, LHS->getType(), RHS) || OpNum+1 > Record.size()) return Error("Invalid BINOP record"); @@ -2131,8 +2133,8 @@ bool BitcodeReader::ParseFunctionBody(Function *F) { unsigned OpNum = 0; Value *TrueVal, *FalseVal, *Cond; if (getValueTypePair(Record, OpNum, NextValueNo, TrueVal) || - getValue(Record, OpNum, TrueVal->getType(), FalseVal) || - getValue(Record, OpNum, Type::getInt1Ty(Context), Cond)) + popValue(Record, OpNum, NextValueNo, TrueVal->getType(), FalseVal) || + popValue(Record, OpNum, NextValueNo, Type::getInt1Ty(Context), Cond)) return Error("Invalid SELECT record"); I = SelectInst::Create(Cond, TrueVal, FalseVal); @@ -2146,7 +2148,7 @@ bool BitcodeReader::ParseFunctionBody(Function *F) { unsigned OpNum = 0; Value *TrueVal, *FalseVal, *Cond; if (getValueTypePair(Record, OpNum, NextValueNo, TrueVal) || - getValue(Record, OpNum, TrueVal->getType(), FalseVal) || + popValue(Record, OpNum, NextValueNo, TrueVal->getType(), FalseVal) || getValueTypePair(Record, OpNum, NextValueNo, Cond)) return Error("Invalid SELECT record"); @@ -2171,7 +2173,7 @@ bool BitcodeReader::ParseFunctionBody(Function *F) { unsigned OpNum = 0; Value *Vec, *Idx; if (getValueTypePair(Record, OpNum, NextValueNo, Vec) || - getValue(Record, OpNum, Type::getInt32Ty(Context), Idx)) + popValue(Record, OpNum, NextValueNo, Type::getInt32Ty(Context), Idx)) return Error("Invalid EXTRACTELT record"); I = ExtractElementInst::Create(Vec, Idx); InstructionList.push_back(I); @@ -2182,9 +2184,9 @@ bool BitcodeReader::ParseFunctionBody(Function *F) { unsigned OpNum = 0; Value *Vec, *Elt, *Idx; if (getValueTypePair(Record, OpNum, NextValueNo, Vec) || - getValue(Record, OpNum, + popValue(Record, OpNum, NextValueNo, cast(Vec->getType())->getElementType(), Elt) || - getValue(Record, OpNum, Type::getInt32Ty(Context), Idx)) + popValue(Record, OpNum, NextValueNo, Type::getInt32Ty(Context), Idx)) return Error("Invalid INSERTELT record"); I = InsertElementInst::Create(Vec, Elt, Idx); InstructionList.push_back(I); @@ -2195,7 +2197,7 @@ bool BitcodeReader::ParseFunctionBody(Function *F) { unsigned OpNum = 0; Value *Vec1, *Vec2, *Mask; if (getValueTypePair(Record, OpNum, NextValueNo, Vec1) || - getValue(Record, OpNum, Vec1->getType(), Vec2)) + popValue(Record, OpNum, NextValueNo, Vec1->getType(), Vec2)) return Error("Invalid SHUFFLEVEC record"); if (getValueTypePair(Record, OpNum, NextValueNo, Mask)) @@ -2215,7 +2217,7 @@ bool BitcodeReader::ParseFunctionBody(Function *F) { unsigned OpNum = 0; Value *LHS, *RHS; if (getValueTypePair(Record, OpNum, NextValueNo, LHS) || - getValue(Record, OpNum, LHS->getType(), RHS) || + popValue(Record, OpNum, NextValueNo, LHS->getType(), RHS) || OpNum+1 != Record.size()) return Error("Invalid CMP record"); @@ -2260,7 +2262,8 @@ bool BitcodeReader::ParseFunctionBody(Function *F) { } else { BasicBlock *FalseDest = getBasicBlock(Record[1]); - Value *Cond = getFnValueByID(Record[2], Type::getInt1Ty(Context)); + Value *Cond = getValue(Record, 2, NextValueNo, + Type::getInt1Ty(Context)); if (FalseDest == 0 || Cond == 0) return Error("Invalid BR record"); I = BranchInst::Create(TrueDest, FalseDest, Cond); @@ -2276,7 +2279,7 @@ bool BitcodeReader::ParseFunctionBody(Function *F) { Type *OpTy = getTypeByID(Record[1]); unsigned ValueBitWidth = cast(OpTy)->getBitWidth(); - Value *Cond = getFnValueByID(Record[2], OpTy); + Value *Cond = getValue(Record, 2, NextValueNo, OpTy); BasicBlock *Default = getBasicBlock(Record[3]); if (OpTy == 0 || Cond == 0 || Default == 0) return Error("Invalid SWITCH record"); @@ -2331,7 +2334,7 @@ bool BitcodeReader::ParseFunctionBody(Function *F) { if (Record.size() < 3 || (Record.size() & 1) == 0) return Error("Invalid SWITCH record"); Type *OpTy = getTypeByID(Record[0]); - Value *Cond = getFnValueByID(Record[1], OpTy); + Value *Cond = getValue(Record, 1, NextValueNo, OpTy); BasicBlock *Default = getBasicBlock(Record[2]); if (OpTy == 0 || Cond == 0 || Default == 0) return Error("Invalid SWITCH record"); @@ -2355,7 +2358,7 @@ bool BitcodeReader::ParseFunctionBody(Function *F) { if (Record.size() < 2) return Error("Invalid INDIRECTBR record"); Type *OpTy = getTypeByID(Record[0]); - Value *Address = getFnValueByID(Record[1], OpTy); + Value *Address = getValue(Record, 1, NextValueNo, OpTy); if (OpTy == 0 || Address == 0) return Error("Invalid INDIRECTBR record"); unsigned NumDests = Record.size()-2; @@ -2397,7 +2400,8 @@ bool BitcodeReader::ParseFunctionBody(Function *F) { SmallVector Ops; for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i, ++OpNum) { - Ops.push_back(getFnValueByID(Record[OpNum], FTy->getParamType(i))); + Ops.push_back(getValue(Record, OpNum, NextValueNo, + FTy->getParamType(i))); if (Ops.back() == 0) return Error("Invalid INVOKE record"); } @@ -2444,7 +2448,14 @@ bool BitcodeReader::ParseFunctionBody(Function *F) { InstructionList.push_back(PN); for (unsigned i = 0, e = Record.size()-1; i != e; i += 2) { - Value *V = getFnValueByID(Record[1+i], Ty); + Value *V; + // 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. + if (UseRelativeIDs) + V = getValueSigned(Record, 1+i, NextValueNo, Ty); + else + V = getValue(Record, 1+i, NextValueNo, Ty); BasicBlock *BB = getBasicBlock(Record[2+i]); if (!V || !BB) return Error("Invalid PHI record"); PN->addIncoming(V, BB); @@ -2542,7 +2553,7 @@ bool BitcodeReader::ParseFunctionBody(Function *F) { unsigned OpNum = 0; Value *Val, *Ptr; if (getValueTypePair(Record, OpNum, NextValueNo, Ptr) || - getValue(Record, OpNum, + popValue(Record, OpNum, NextValueNo, cast(Ptr->getType())->getElementType(), Val) || OpNum+2 != Record.size()) return Error("Invalid STORE record"); @@ -2556,7 +2567,7 @@ bool BitcodeReader::ParseFunctionBody(Function *F) { unsigned OpNum = 0; Value *Val, *Ptr; if (getValueTypePair(Record, OpNum, NextValueNo, Ptr) || - getValue(Record, OpNum, + popValue(Record, OpNum, NextValueNo, cast(Ptr->getType())->getElementType(), Val) || OpNum+4 != Record.size()) return Error("Invalid STOREATOMIC record"); @@ -2579,9 +2590,9 @@ bool BitcodeReader::ParseFunctionBody(Function *F) { unsigned OpNum = 0; Value *Ptr, *Cmp, *New; if (getValueTypePair(Record, OpNum, NextValueNo, Ptr) || - getValue(Record, OpNum, + popValue(Record, OpNum, NextValueNo, cast(Ptr->getType())->getElementType(), Cmp) || - getValue(Record, OpNum, + popValue(Record, OpNum, NextValueNo, cast(Ptr->getType())->getElementType(), New) || OpNum+3 != Record.size()) return Error("Invalid CMPXCHG record"); @@ -2599,7 +2610,7 @@ bool BitcodeReader::ParseFunctionBody(Function *F) { unsigned OpNum = 0; Value *Ptr, *Val; if (getValueTypePair(Record, OpNum, NextValueNo, Ptr) || - getValue(Record, OpNum, + popValue(Record, OpNum, NextValueNo, cast(Ptr->getType())->getElementType(), Val) || OpNum+4 != Record.size()) return Error("Invalid ATOMICRMW record"); @@ -2653,7 +2664,8 @@ bool BitcodeReader::ParseFunctionBody(Function *F) { if (FTy->getParamType(i)->isLabelTy()) Args.push_back(getBasicBlock(Record[OpNum])); else - Args.push_back(getFnValueByID(Record[OpNum], FTy->getParamType(i))); + Args.push_back(getValue(Record, OpNum, NextValueNo, + FTy->getParamType(i))); if (Args.back() == 0) return Error("Invalid CALL record"); } @@ -2682,7 +2694,7 @@ bool BitcodeReader::ParseFunctionBody(Function *F) { if (Record.size() < 3) return Error("Invalid VAARG record"); Type *OpTy = getTypeByID(Record[0]); - Value *Op = getFnValueByID(Record[1], OpTy); + Value *Op = getValue(Record, 1, NextValueNo, OpTy); Type *ResTy = getTypeByID(Record[2]); if (!OpTy || !Op || !ResTy) return Error("Invalid VAARG record"); diff --git a/lib/Bitcode/Reader/BitcodeReader.h b/lib/Bitcode/Reader/BitcodeReader.h index e7c4e94f785..c5e97991b92 100644 --- a/lib/Bitcode/Reader/BitcodeReader.h +++ b/lib/Bitcode/Reader/BitcodeReader.h @@ -179,18 +179,27 @@ class BitcodeReader : public GVMaterializer { typedef std::pair BlockAddrRefTy; DenseMap > BlockAddrFwdRefs; + /// UseRelativeIDs - Indicates that we are using a new encoding for + /// instrunction operands where most operands in the current + /// FUNCTION_BLOCK are encoded relative to the instruction number, + /// for a more compact encoding. Some instruction operands are not + /// relative to the instruction ID: basic block numbers, and types. + /// Once the old style function blocks have been phased out, we would + /// not need this flag. + bool UseRelativeIDs; + public: explicit BitcodeReader(MemoryBuffer *buffer, LLVMContext &C) : Context(C), TheModule(0), Buffer(buffer), BufferOwned(false), LazyStreamer(0), NextUnreadBit(0), SeenValueSymbolTable(false), ErrorString(0), ValueList(C), MDValueList(C), - SeenFirstFunctionBody(false) { + SeenFirstFunctionBody(false), UseRelativeIDs(false) { } explicit BitcodeReader(DataStreamer *streamer, LLVMContext &C) : Context(C), TheModule(0), Buffer(0), BufferOwned(false), LazyStreamer(streamer), NextUnreadBit(0), SeenValueSymbolTable(false), ErrorString(0), ValueList(C), MDValueList(C), - SeenFirstFunctionBody(false) { + SeenFirstFunctionBody(false), UseRelativeIDs(false) { } ~BitcodeReader() { FreeState(); @@ -223,6 +232,9 @@ public: /// @brief Cheap mechanism to just extract module triple /// @returns true if an error occurred. bool ParseTriple(std::string &Triple); + + static uint64_t decodeSignRotatedValue(uint64_t V); + private: Type *getTypeByID(unsigned ID); Value *getFnValueByID(unsigned ID, Type *Ty) { @@ -247,6 +259,9 @@ private: unsigned InstNum, Value *&ResVal) { if (Slot == Record.size()) return true; unsigned ValNo = (unsigned)Record[Slot++]; + // Adjust the ValNo, if it was encoded relative to the InstNum. + if (UseRelativeIDs) + ValNo = InstNum - ValNo; if (ValNo < InstNum) { // If this is not a forward reference, just return the value we already // have. @@ -255,20 +270,54 @@ private: } else if (Slot == Record.size()) { return true; } - + unsigned TypeNo = (unsigned)Record[Slot++]; ResVal = getFnValueByID(ValNo, getTypeByID(TypeNo)); return ResVal == 0; } - bool getValue(SmallVector &Record, unsigned &Slot, - Type *Ty, Value *&ResVal) { - if (Slot == Record.size()) return true; - unsigned ValNo = (unsigned)Record[Slot++]; - ResVal = getFnValueByID(ValNo, Ty); + + /// popValue - Read a value out of the specified record from slot 'Slot'. + /// Increment Slot past the number of slots used by the value in the record. + /// Return true if there is an error. + bool popValue(SmallVector &Record, unsigned &Slot, + unsigned InstNum, Type *Ty, Value *&ResVal) { + if (getValue(Record, Slot, InstNum, Ty, ResVal)) + return true; + // All values currently take a single record slot. + ++Slot; + return false; + } + + /// getValue -- Like popValue, but does not increment the Slot number. + bool getValue(SmallVector &Record, unsigned Slot, + unsigned InstNum, Type *Ty, Value *&ResVal) { + ResVal = getValue(Record, Slot, InstNum, Ty); return ResVal == 0; } - + /// getValue -- Version of getValue that returns ResVal directly, + /// or 0 if there is an error. + Value *getValue(SmallVector &Record, unsigned Slot, + unsigned InstNum, Type *Ty) { + if (Slot == Record.size()) return 0; + 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); + } + + /// getValueSigned -- Like getValue, but decodes signed VBRs. + Value *getValueSigned(SmallVector &Record, unsigned Slot, + unsigned InstNum, Type *Ty) { + if (Slot == Record.size()) return 0; + 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); + } + bool ParseModule(bool Resume); bool ParseAttributeBlock(); bool ParseTypeTable(); diff --git a/lib/Bitcode/Writer/BitcodeWriter.cpp b/lib/Bitcode/Writer/BitcodeWriter.cpp index b3f1bb13a9f..efa60b8e076 100644 --- a/lib/Bitcode/Writer/BitcodeWriter.cpp +++ b/lib/Bitcode/Writer/BitcodeWriter.cpp @@ -41,8 +41,6 @@ EnablePreserveUseListOrdering("enable-bc-uselist-preserve", /// These are manifest constants used by the bitcode writer. They do not need to /// be kept in sync with the reader, but need to be consistent within this file. enum { - CurVersion = 0, - // VALUE_SYMTAB_BLOCK abbrev id's. VST_ENTRY_8_ABBREV = bitc::FIRST_APPLICATION_ABBREV, VST_ENTRY_7_ABBREV, @@ -722,16 +720,20 @@ static void WriteModuleMetadataStore(const Module *M, BitstreamWriter &Stream) { Stream.ExitBlock(); } +static void emitSignedInt64(SmallVectorImpl &Vals, uint64_t V) { + if ((int64_t)V >= 0) + Vals.push_back(V << 1); + else + Vals.push_back((-V << 1) | 1); +} + static void EmitAPInt(SmallVectorImpl &Vals, unsigned &Code, unsigned &AbbrevToUse, const APInt &Val, bool EmitSizeForWideNumbers = false ) { if (Val.getBitWidth() <= 64) { uint64_t V = Val.getSExtValue(); - if ((int64_t)V >= 0) - Vals.push_back(V << 1); - else - Vals.push_back((-V << 1) | 1); + emitSignedInt64(Vals, V); Code = bitc::CST_CODE_INTEGER; AbbrevToUse = CONSTANTS_INTEGER_ABBREV; } else { @@ -747,11 +749,7 @@ static void EmitAPInt(SmallVectorImpl &Vals, const uint64_t *RawWords = Val.getRawData(); for (unsigned i = 0; i != NWords; ++i) { - int64_t V = RawWords[i]; - if (V >= 0) - Vals.push_back(V << 1); - else - Vals.push_back((-V << 1) | 1); + emitSignedInt64(Vals, RawWords[i]); } Code = bitc::CST_CODE_WIDE_INTEGER; } @@ -1025,12 +1023,13 @@ static void WriteModuleConstants(const ValueEnumerator &VE, /// /// This function adds V's value ID to Vals. If the value ID is higher than the /// instruction ID, then it is a forward reference, and it also includes the -/// type ID. +/// type ID. The value ID that is written is encoded relative to the InstID. static bool PushValueAndType(const Value *V, unsigned InstID, SmallVector &Vals, ValueEnumerator &VE) { unsigned ValID = VE.getValueID(V); - Vals.push_back(ValID); + // Make encoding relative to the InstID. + Vals.push_back(InstID - ValID); if (ValID >= InstID) { Vals.push_back(VE.getTypeID(V->getType())); return true; @@ -1038,6 +1037,30 @@ static bool PushValueAndType(const Value *V, unsigned InstID, return false; } +/// pushValue - Like PushValueAndType, but where the type of the value is +/// omitted (perhaps it was already encoded in an earlier operand). +static void pushValue(const Value *V, unsigned InstID, + SmallVector &Vals, + ValueEnumerator &VE) { + unsigned ValID = VE.getValueID(V); + Vals.push_back(InstID - ValID); +} + +static void pushValue64(const Value *V, unsigned InstID, + SmallVector &Vals, + ValueEnumerator &VE) { + uint64_t ValID = VE.getValueID(V); + Vals.push_back(InstID - ValID); +} + +static void pushValueSigned(const Value *V, unsigned InstID, + SmallVector &Vals, + ValueEnumerator &VE) { + unsigned ValID = VE.getValueID(V); + int64_t diff = ((int32_t)InstID - (int32_t)ValID); + emitSignedInt64(Vals, diff); +} + /// WriteInstruction - Emit an instruction to the specified stream. static void WriteInstruction(const Instruction &I, unsigned InstID, ValueEnumerator &VE, BitstreamWriter &Stream, @@ -1058,7 +1081,7 @@ static void WriteInstruction(const Instruction &I, unsigned InstID, Code = bitc::FUNC_CODE_INST_BINOP; if (!PushValueAndType(I.getOperand(0), InstID, Vals, VE)) AbbrevToUse = FUNCTION_INST_BINOP_ABBREV; - Vals.push_back(VE.getValueID(I.getOperand(1))); + pushValue(I.getOperand(1), InstID, Vals, VE); Vals.push_back(GetEncodedBinaryOpcode(I.getOpcode())); uint64_t Flags = GetOptimizationFlags(&I); if (Flags != 0) { @@ -1096,32 +1119,32 @@ static void WriteInstruction(const Instruction &I, unsigned InstID, case Instruction::Select: Code = bitc::FUNC_CODE_INST_VSELECT; PushValueAndType(I.getOperand(1), InstID, Vals, VE); - Vals.push_back(VE.getValueID(I.getOperand(2))); + pushValue(I.getOperand(2), InstID, Vals, VE); PushValueAndType(I.getOperand(0), InstID, Vals, VE); break; case Instruction::ExtractElement: Code = bitc::FUNC_CODE_INST_EXTRACTELT; PushValueAndType(I.getOperand(0), InstID, Vals, VE); - Vals.push_back(VE.getValueID(I.getOperand(1))); + pushValue(I.getOperand(1), InstID, Vals, VE); break; case Instruction::InsertElement: Code = bitc::FUNC_CODE_INST_INSERTELT; PushValueAndType(I.getOperand(0), InstID, Vals, VE); - Vals.push_back(VE.getValueID(I.getOperand(1))); - Vals.push_back(VE.getValueID(I.getOperand(2))); + pushValue(I.getOperand(1), InstID, Vals, VE); + pushValue(I.getOperand(2), InstID, Vals, VE); break; case Instruction::ShuffleVector: Code = bitc::FUNC_CODE_INST_SHUFFLEVEC; PushValueAndType(I.getOperand(0), InstID, Vals, VE); - Vals.push_back(VE.getValueID(I.getOperand(1))); - Vals.push_back(VE.getValueID(I.getOperand(2))); + pushValue(I.getOperand(1), InstID, Vals, VE); + pushValue(I.getOperand(2), InstID, Vals, VE); break; case Instruction::ICmp: case Instruction::FCmp: // compare returning Int1Ty or vector of Int1Ty Code = bitc::FUNC_CODE_INST_CMP2; PushValueAndType(I.getOperand(0), InstID, Vals, VE); - Vals.push_back(VE.getValueID(I.getOperand(1))); + pushValue(I.getOperand(1), InstID, Vals, VE); Vals.push_back(cast(I).getPredicate()); break; @@ -1147,7 +1170,7 @@ static void WriteInstruction(const Instruction &I, unsigned InstID, Vals.push_back(VE.getValueID(II.getSuccessor(0))); if (II.isConditional()) { Vals.push_back(VE.getValueID(II.getSuccessor(1))); - Vals.push_back(VE.getValueID(II.getCondition())); + pushValue(II.getCondition(), InstID, Vals, VE); } } break; @@ -1164,7 +1187,7 @@ static void WriteInstruction(const Instruction &I, unsigned InstID, Vals64.push_back(SwitchRecordHeader); Vals64.push_back(VE.getTypeID(SI.getCondition()->getType())); - Vals64.push_back(VE.getValueID(SI.getCondition())); + pushValue64(SI.getCondition(), InstID, Vals64, VE); Vals64.push_back(VE.getValueID(SI.getDefaultDest())); Vals64.push_back(SI.getNumCases()); for (SwitchInst::CaseIt i = SI.case_begin(), e = SI.case_end(); @@ -1215,7 +1238,9 @@ static void WriteInstruction(const Instruction &I, unsigned InstID, case Instruction::IndirectBr: Code = bitc::FUNC_CODE_INST_INDIRECTBR; Vals.push_back(VE.getTypeID(I.getOperand(0)->getType())); - for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) + // Encode the address operand as relative, but not the basic blocks. + pushValue(I.getOperand(0), InstID, Vals, VE); + for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i) Vals.push_back(VE.getValueID(I.getOperand(i))); break; @@ -1234,7 +1259,7 @@ static void WriteInstruction(const Instruction &I, unsigned InstID, // Emit value #'s for the fixed parameters. for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i) - Vals.push_back(VE.getValueID(I.getOperand(i))); // fixed param. + pushValue(I.getOperand(i), InstID, Vals, VE); // fixed param. // Emit type/value pairs for varargs params. if (FTy->isVarArg()) { @@ -1256,12 +1281,19 @@ static void WriteInstruction(const Instruction &I, unsigned InstID, case Instruction::PHI: { const PHINode &PN = cast(I); Code = bitc::FUNC_CODE_INST_PHI; - Vals.push_back(VE.getTypeID(PN.getType())); + // With the newer instruction encoding, forward references could give + // negative valued IDs. This is most common for PHIs, so we use + // signed VBRs. + SmallVector Vals64; + Vals64.push_back(VE.getTypeID(PN.getType())); for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) { - Vals.push_back(VE.getValueID(PN.getIncomingValue(i))); - Vals.push_back(VE.getValueID(PN.getIncomingBlock(i))); + pushValueSigned(PN.getIncomingValue(i), InstID, Vals64, VE); + Vals64.push_back(VE.getValueID(PN.getIncomingBlock(i))); } - break; + // Emit a Vals64 vector and exit. + Stream.EmitRecord(Code, Vals64, AbbrevToUse); + Vals64.clear(); + return; } case Instruction::LandingPad: { @@ -1311,7 +1343,7 @@ static void WriteInstruction(const Instruction &I, unsigned InstID, else Code = bitc::FUNC_CODE_INST_STORE; PushValueAndType(I.getOperand(1), InstID, Vals, VE); // ptrty + ptr - Vals.push_back(VE.getValueID(I.getOperand(0))); // val. + pushValue(I.getOperand(0), InstID, Vals, VE); // val. Vals.push_back(Log2_32(cast(I).getAlignment())+1); Vals.push_back(cast(I).isVolatile()); if (cast(I).isAtomic()) { @@ -1322,8 +1354,8 @@ static void WriteInstruction(const Instruction &I, unsigned InstID, case Instruction::AtomicCmpXchg: Code = bitc::FUNC_CODE_INST_CMPXCHG; PushValueAndType(I.getOperand(0), InstID, Vals, VE); // ptrty + ptr - Vals.push_back(VE.getValueID(I.getOperand(1))); // cmp. - Vals.push_back(VE.getValueID(I.getOperand(2))); // newval. + pushValue(I.getOperand(1), InstID, Vals, VE); // cmp. + pushValue(I.getOperand(2), InstID, Vals, VE); // newval. Vals.push_back(cast(I).isVolatile()); Vals.push_back(GetEncodedOrdering( cast(I).getOrdering())); @@ -1333,7 +1365,7 @@ static void WriteInstruction(const Instruction &I, unsigned InstID, case Instruction::AtomicRMW: Code = bitc::FUNC_CODE_INST_ATOMICRMW; PushValueAndType(I.getOperand(0), InstID, Vals, VE); // ptrty + ptr - Vals.push_back(VE.getValueID(I.getOperand(1))); // val. + pushValue(I.getOperand(1), InstID, Vals, VE); // val. Vals.push_back(GetEncodedRMWOperation( cast(I).getOperation())); Vals.push_back(cast(I).isVolatile()); @@ -1358,8 +1390,13 @@ static void WriteInstruction(const Instruction &I, unsigned InstID, PushValueAndType(CI.getCalledValue(), InstID, Vals, VE); // Callee // Emit value #'s for the fixed parameters. - for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i) - Vals.push_back(VE.getValueID(CI.getArgOperand(i))); // fixed param. + for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i) { + // Check for labels (can happen with asm labels). + if (FTy->getParamType(i)->isLabelTy()) + Vals.push_back(VE.getValueID(CI.getArgOperand(i))); + else + pushValue(CI.getArgOperand(i), InstID, Vals, VE); // fixed param. + } // Emit type/value pairs for varargs params. if (FTy->isVarArg()) { @@ -1372,7 +1409,7 @@ static void WriteInstruction(const Instruction &I, unsigned InstID, case Instruction::VAArg: Code = bitc::FUNC_CODE_INST_VAARG; Vals.push_back(VE.getTypeID(I.getOperand(0)->getType())); // valistty - Vals.push_back(VE.getValueID(I.getOperand(0))); // valist. + pushValue(I.getOperand(0), InstID, Vals, VE); // valist. Vals.push_back(VE.getTypeID(I.getType())); // restype. break; } @@ -1514,8 +1551,8 @@ static void WriteFunction(const Function &F, ValueEnumerator &VE, // Emit blockinfo, which defines the standard abbreviations etc. static void WriteBlockInfo(const ValueEnumerator &VE, BitstreamWriter &Stream) { // We only want to emit block info records for blocks that have multiple - // instances: CONSTANTS_BLOCK, FUNCTION_BLOCK and VALUE_SYMTAB_BLOCK. Other - // blocks can defined their abbrevs inline. + // instances: CONSTANTS_BLOCK, FUNCTION_BLOCK and VALUE_SYMTAB_BLOCK. + // Other blocks can defined their abbrevs inline. Stream.EnterBlockInfoBlock(2); { // 8-bit fixed-width VST_ENTRY/VST_BBENTRY strings. @@ -1773,12 +1810,10 @@ static void WriteModuleUseLists(const Module *M, ValueEnumerator &VE, static void WriteModule(const Module *M, BitstreamWriter &Stream) { Stream.EnterSubblock(bitc::MODULE_BLOCK_ID, 3); - // Emit the version number if it is non-zero. - if (CurVersion) { - SmallVector Vals; - Vals.push_back(CurVersion); - Stream.EmitRecord(bitc::MODULE_CODE_VERSION, Vals); - } + SmallVector Vals; + unsigned CurVersion = 1; + Vals.push_back(CurVersion); + Stream.EmitRecord(bitc::MODULE_CODE_VERSION, Vals); // Analyze the module, enumerating globals, functions, etc. ValueEnumerator VE(M); diff --git a/test/Bitcode/function-encoding-rel-operands.ll b/test/Bitcode/function-encoding-rel-operands.ll new file mode 100644 index 00000000000..aedb0c32676 --- /dev/null +++ b/test/Bitcode/function-encoding-rel-operands.ll @@ -0,0 +1,49 @@ +; Basic sanity test to check that instruction operands are encoded with +; relative IDs. +; RUN: llvm-as < %s | llvm-bcanalyzer -dump | FileCheck %s + +; CHECK: FUNCTION_BLOCK +; CHECK: INST_BINOP {{.*}}op0=1 op1=1 +; CHECK: INST_BINOP {{.*}}op0=1 op1=1 +; CHECK: INST_BINOP {{.*}}op0=1 op1=1 +; CHECK: INST_RET {{.*}}op0=1 +define i32 @test_int_binops(i32 %a) nounwind { +entry: + %0 = add i32 %a, %a + %1 = sub i32 %0, %0 + %2 = mul i32 %1, %1 + ret i32 %2 +} + + +; CHECK: FUNCTION_BLOCK +; CHECK: INST_CAST {{.*}}op0=1 +; CHECK: INST_BINOP {{.*}}op0=1 op1=1 +; CHECK: INST_BINOP {{.*}}op0=1 op1=1 +; CHECK: INST_BINOP {{.*}}op0=1 op1=1 +; CHECK: INST_BINOP {{.*}}op0=1 op1=1 +; CHECK: INST_RET {{.*}}op0=1 +define double @test_float_binops(i32 %a) nounwind { + %1 = sitofp i32 %a to double + %2 = fadd double %1, %1 + %3 = fsub double %2, %2 + %4 = fmul double %3, %3 + %5 = fdiv double %4, %4 + ret double %5 +} + + +; CHECK: FUNCTION_BLOCK +; skip checking operands of INST_INBOUNDS_GEP since that depends on ordering +; between literals and the formal parameters. +; CHECK: INST_INBOUNDS_GEP {{.*}} +; CHECK: INST_LOAD {{.*}}op0=1 {{.*}} +; CHECK: INST_CMP2 op0=1 {{.*}} +; CHECK: INST_RET {{.*}}op0=1 +define i1 @test_load(i32 %a, {i32, i32}* %ptr) nounwind { +entry: + %0 = getelementptr inbounds {i32, i32}* %ptr, i32 %a, i32 0 + %1 = load i32* %0 + %2 = icmp eq i32 %1, %a + ret i1 %2 +} -- 2.34.1