1 //===-- Writer.cpp - Library for writing LLVM bytecode files --------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This library implements the functionality defined in llvm/Bytecode/Writer.h
12 // Note that this file uses an unusual technique of outputting all the bytecode
13 // to a vector of unsigned char, then copies the vector to an ostream. The
14 // reason for this is that we must do "seeking" in the stream to do back-
15 // patching, and some very important ostreams that we want to support (like
16 // pipes) do not support seeking. :( :( :(
18 //===----------------------------------------------------------------------===//
20 #include "WriterInternals.h"
21 #include "llvm/Bytecode/WriteBytecodePass.h"
22 #include "llvm/CallingConv.h"
23 #include "llvm/Constants.h"
24 #include "llvm/DerivedTypes.h"
25 #include "llvm/Instructions.h"
26 #include "llvm/Module.h"
27 #include "llvm/SymbolTable.h"
28 #include "llvm/Support/GetElementPtrTypeIterator.h"
29 #include "llvm/Support/Compressor.h"
30 #include "llvm/Support/MathExtras.h"
31 #include "llvm/ADT/STLExtras.h"
32 #include "llvm/ADT/Statistic.h"
37 /// This value needs to be incremented every time the bytecode format changes
38 /// so that the reader can distinguish which format of the bytecode file has
40 /// @brief The bytecode version number
41 const unsigned BCVersionNum = 5;
43 static RegisterPass<WriteBytecodePass> X("emitbytecode", "Bytecode Writer");
46 BytesWritten("bytecodewriter", "Number of bytecode bytes written");
48 //===----------------------------------------------------------------------===//
49 //=== Output Primitives ===//
50 //===----------------------------------------------------------------------===//
52 // output - If a position is specified, it must be in the valid portion of the
53 // string... note that this should be inlined always so only the relevant IF
54 // body should be included.
55 inline void BytecodeWriter::output(unsigned i, int pos) {
56 if (pos == -1) { // Be endian clean, little endian is our friend
57 Out.push_back((unsigned char)i);
58 Out.push_back((unsigned char)(i >> 8));
59 Out.push_back((unsigned char)(i >> 16));
60 Out.push_back((unsigned char)(i >> 24));
62 Out[pos ] = (unsigned char)i;
63 Out[pos+1] = (unsigned char)(i >> 8);
64 Out[pos+2] = (unsigned char)(i >> 16);
65 Out[pos+3] = (unsigned char)(i >> 24);
69 inline void BytecodeWriter::output(int i) {
73 /// output_vbr - Output an unsigned value, by using the least number of bytes
74 /// possible. This is useful because many of our "infinite" values are really
75 /// very small most of the time; but can be large a few times.
76 /// Data format used: If you read a byte with the high bit set, use the low
77 /// seven bits as data and then read another byte.
78 inline void BytecodeWriter::output_vbr(uint64_t i) {
80 if (i < 0x80) { // done?
81 Out.push_back((unsigned char)i); // We know the high bit is clear...
85 // Nope, we are bigger than a character, output the next 7 bits and set the
86 // high bit to say that there is more coming...
87 Out.push_back(0x80 | ((unsigned char)i & 0x7F));
88 i >>= 7; // Shift out 7 bits now...
92 inline void BytecodeWriter::output_vbr(unsigned i) {
94 if (i < 0x80) { // done?
95 Out.push_back((unsigned char)i); // We know the high bit is clear...
99 // Nope, we are bigger than a character, output the next 7 bits and set the
100 // high bit to say that there is more coming...
101 Out.push_back(0x80 | ((unsigned char)i & 0x7F));
102 i >>= 7; // Shift out 7 bits now...
106 inline void BytecodeWriter::output_typeid(unsigned i) {
110 this->output_vbr(0x00FFFFFF);
115 inline void BytecodeWriter::output_vbr(int64_t i) {
117 output_vbr(((uint64_t)(-i) << 1) | 1); // Set low order sign bit...
119 output_vbr((uint64_t)i << 1); // Low order bit is clear.
123 inline void BytecodeWriter::output_vbr(int i) {
125 output_vbr(((unsigned)(-i) << 1) | 1); // Set low order sign bit...
127 output_vbr((unsigned)i << 1); // Low order bit is clear.
130 inline void BytecodeWriter::output(const std::string &s) {
131 unsigned Len = s.length();
132 output_vbr(Len ); // Strings may have an arbitrary length...
133 Out.insert(Out.end(), s.begin(), s.end());
136 inline void BytecodeWriter::output_data(const void *Ptr, const void *End) {
137 Out.insert(Out.end(), (const unsigned char*)Ptr, (const unsigned char*)End);
140 inline void BytecodeWriter::output_float(float& FloatVal) {
141 /// FIXME: This isn't optimal, it has size problems on some platforms
142 /// where FP is not IEEE.
143 uint32_t i = FloatToBits(FloatVal);
144 Out.push_back( static_cast<unsigned char>( (i & 0xFF )));
145 Out.push_back( static_cast<unsigned char>( (i >> 8) & 0xFF));
146 Out.push_back( static_cast<unsigned char>( (i >> 16) & 0xFF));
147 Out.push_back( static_cast<unsigned char>( (i >> 24) & 0xFF));
150 inline void BytecodeWriter::output_double(double& DoubleVal) {
151 /// FIXME: This isn't optimal, it has size problems on some platforms
152 /// where FP is not IEEE.
153 uint64_t i = DoubleToBits(DoubleVal);
154 Out.push_back( static_cast<unsigned char>( (i & 0xFF )));
155 Out.push_back( static_cast<unsigned char>( (i >> 8) & 0xFF));
156 Out.push_back( static_cast<unsigned char>( (i >> 16) & 0xFF));
157 Out.push_back( static_cast<unsigned char>( (i >> 24) & 0xFF));
158 Out.push_back( static_cast<unsigned char>( (i >> 32) & 0xFF));
159 Out.push_back( static_cast<unsigned char>( (i >> 40) & 0xFF));
160 Out.push_back( static_cast<unsigned char>( (i >> 48) & 0xFF));
161 Out.push_back( static_cast<unsigned char>( (i >> 56) & 0xFF));
164 inline BytecodeBlock::BytecodeBlock(unsigned ID, BytecodeWriter& w,
165 bool elideIfEmpty, bool hasLongFormat )
166 : Id(ID), Writer(w), ElideIfEmpty(elideIfEmpty), HasLongFormat(hasLongFormat){
170 w.output(0U); // For length in long format
172 w.output(0U); /// Place holder for ID and length for this block
177 inline BytecodeBlock::~BytecodeBlock() { // Do backpatch when block goes out
179 if (Loc == Writer.size() && ElideIfEmpty) {
180 // If the block is empty, and we are allowed to, do not emit the block at
182 Writer.resize(Writer.size()-(HasLongFormat?8:4));
187 Writer.output(unsigned(Writer.size()-Loc), int(Loc-4));
189 Writer.output(unsigned(Writer.size()-Loc) << 5 | (Id & 0x1F), int(Loc-4));
192 //===----------------------------------------------------------------------===//
193 //=== Constant Output ===//
194 //===----------------------------------------------------------------------===//
196 void BytecodeWriter::outputType(const Type *T) {
197 output_vbr((unsigned)T->getTypeID());
199 // That's all there is to handling primitive types...
200 if (T->isPrimitiveType()) {
201 return; // We might do this if we alias a prim type: %x = type int
204 switch (T->getTypeID()) { // Handle derived types now.
205 case Type::FunctionTyID: {
206 const FunctionType *MT = cast<FunctionType>(T);
207 int Slot = Table.getSlot(MT->getReturnType());
208 assert(Slot != -1 && "Type used but not available!!");
209 output_typeid((unsigned)Slot);
211 // Output the number of arguments to function (+1 if varargs):
212 output_vbr((unsigned)MT->getNumParams()+MT->isVarArg());
214 // Output all of the arguments...
215 FunctionType::param_iterator I = MT->param_begin();
216 for (; I != MT->param_end(); ++I) {
217 Slot = Table.getSlot(*I);
218 assert(Slot != -1 && "Type used but not available!!");
219 output_typeid((unsigned)Slot);
222 // Terminate list with VoidTy if we are a varargs function...
224 output_typeid((unsigned)Type::VoidTyID);
228 case Type::ArrayTyID: {
229 const ArrayType *AT = cast<ArrayType>(T);
230 int Slot = Table.getSlot(AT->getElementType());
231 assert(Slot != -1 && "Type used but not available!!");
232 output_typeid((unsigned)Slot);
233 output_vbr(AT->getNumElements());
237 case Type::PackedTyID: {
238 const PackedType *PT = cast<PackedType>(T);
239 int Slot = Table.getSlot(PT->getElementType());
240 assert(Slot != -1 && "Type used but not available!!");
241 output_typeid((unsigned)Slot);
242 output_vbr(PT->getNumElements());
247 case Type::StructTyID: {
248 const StructType *ST = cast<StructType>(T);
250 // Output all of the element types...
251 for (StructType::element_iterator I = ST->element_begin(),
252 E = ST->element_end(); I != E; ++I) {
253 int Slot = Table.getSlot(*I);
254 assert(Slot != -1 && "Type used but not available!!");
255 output_typeid((unsigned)Slot);
258 // Terminate list with VoidTy
259 output_typeid((unsigned)Type::VoidTyID);
263 case Type::PointerTyID: {
264 const PointerType *PT = cast<PointerType>(T);
265 int Slot = Table.getSlot(PT->getElementType());
266 assert(Slot != -1 && "Type used but not available!!");
267 output_typeid((unsigned)Slot);
271 case Type::OpaqueTyID:
272 // No need to emit anything, just the count of opaque types is enough.
276 std::cerr << __FILE__ << ":" << __LINE__ << ": Don't know how to serialize"
277 << " Type '" << T->getDescription() << "'\n";
282 void BytecodeWriter::outputConstant(const Constant *CPV) {
283 assert((CPV->getType()->isPrimitiveType() || !CPV->isNullValue()) &&
284 "Shouldn't output null constants!");
286 // We must check for a ConstantExpr before switching by type because
287 // a ConstantExpr can be of any type, and has no explicit value.
289 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(CPV)) {
290 // FIXME: Encoding of constant exprs could be much more compact!
291 assert(CE->getNumOperands() > 0 && "ConstantExpr with 0 operands");
292 assert(CE->getNumOperands() != 1 || CE->getOpcode() == Instruction::Cast);
293 output_vbr(1+CE->getNumOperands()); // flags as an expr
294 output_vbr(CE->getOpcode()); // flags as an expr
296 for (User::const_op_iterator OI = CE->op_begin(); OI != CE->op_end(); ++OI){
297 int Slot = Table.getSlot(*OI);
298 assert(Slot != -1 && "Unknown constant used in ConstantExpr!!");
299 output_vbr((unsigned)Slot);
300 Slot = Table.getSlot((*OI)->getType());
301 output_typeid((unsigned)Slot);
304 } else if (isa<UndefValue>(CPV)) {
305 output_vbr(1U); // 1 -> UndefValue constant.
308 output_vbr(0U); // flag as not a ConstantExpr
311 switch (CPV->getType()->getTypeID()) {
312 case Type::BoolTyID: // Boolean Types
313 if (cast<ConstantBool>(CPV)->getValue())
319 case Type::UByteTyID: // Unsigned integer types...
320 case Type::UShortTyID:
322 case Type::ULongTyID:
323 output_vbr(cast<ConstantUInt>(CPV)->getValue());
326 case Type::SByteTyID: // Signed integer types...
327 case Type::ShortTyID:
330 output_vbr(cast<ConstantSInt>(CPV)->getValue());
333 case Type::ArrayTyID: {
334 const ConstantArray *CPA = cast<ConstantArray>(CPV);
335 assert(!CPA->isString() && "Constant strings should be handled specially!");
337 for (unsigned i = 0, e = CPA->getNumOperands(); i != e; ++i) {
338 int Slot = Table.getSlot(CPA->getOperand(i));
339 assert(Slot != -1 && "Constant used but not available!!");
340 output_vbr((unsigned)Slot);
345 case Type::PackedTyID: {
346 const ConstantPacked *CP = cast<ConstantPacked>(CPV);
348 for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i) {
349 int Slot = Table.getSlot(CP->getOperand(i));
350 assert(Slot != -1 && "Constant used but not available!!");
351 output_vbr((unsigned)Slot);
356 case Type::StructTyID: {
357 const ConstantStruct *CPS = cast<ConstantStruct>(CPV);
359 for (unsigned i = 0, e = CPS->getNumOperands(); i != e; ++i) {
360 int Slot = Table.getSlot(CPS->getOperand(i));
361 assert(Slot != -1 && "Constant used but not available!!");
362 output_vbr((unsigned)Slot);
367 case Type::PointerTyID:
368 assert(0 && "No non-null, non-constant-expr constants allowed!");
371 case Type::FloatTyID: { // Floating point types...
372 float Tmp = (float)cast<ConstantFP>(CPV)->getValue();
376 case Type::DoubleTyID: {
377 double Tmp = cast<ConstantFP>(CPV)->getValue();
383 case Type::LabelTyID:
385 std::cerr << __FILE__ << ":" << __LINE__ << ": Don't know how to serialize"
386 << " type '" << *CPV->getType() << "'\n";
392 void BytecodeWriter::outputConstantStrings() {
393 SlotCalculator::string_iterator I = Table.string_begin();
394 SlotCalculator::string_iterator E = Table.string_end();
395 if (I == E) return; // No strings to emit
397 // If we have != 0 strings to emit, output them now. Strings are emitted into
398 // the 'void' type plane.
399 output_vbr(unsigned(E-I));
400 output_typeid(Type::VoidTyID);
402 // Emit all of the strings.
403 for (I = Table.string_begin(); I != E; ++I) {
404 const ConstantArray *Str = *I;
405 int Slot = Table.getSlot(Str->getType());
406 assert(Slot != -1 && "Constant string of unknown type?");
407 output_typeid((unsigned)Slot);
409 // Now that we emitted the type (which indicates the size of the string),
410 // emit all of the characters.
411 std::string Val = Str->getAsString();
412 output_data(Val.c_str(), Val.c_str()+Val.size());
416 //===----------------------------------------------------------------------===//
417 //=== Instruction Output ===//
418 //===----------------------------------------------------------------------===//
420 // outputInstructionFormat0 - Output those weird instructions that have a large
421 // number of operands or have large operands themselves.
423 // Format: [opcode] [type] [numargs] [arg0] [arg1] ... [arg<numargs-1>]
425 void BytecodeWriter::outputInstructionFormat0(const Instruction *I,
427 const SlotCalculator &Table,
429 // Opcode must have top two bits clear...
430 output_vbr(Opcode << 2); // Instruction Opcode ID
431 output_typeid(Type); // Result type
433 unsigned NumArgs = I->getNumOperands();
434 output_vbr(NumArgs + (isa<CastInst>(I) ||
435 isa<VAArgInst>(I) || Opcode == 56 || Opcode == 58));
437 if (!isa<GetElementPtrInst>(&I)) {
438 for (unsigned i = 0; i < NumArgs; ++i) {
439 int Slot = Table.getSlot(I->getOperand(i));
440 assert(Slot >= 0 && "No slot number for value!?!?");
441 output_vbr((unsigned)Slot);
444 if (isa<CastInst>(I) || isa<VAArgInst>(I)) {
445 int Slot = Table.getSlot(I->getType());
446 assert(Slot != -1 && "Cast return type unknown?");
447 output_typeid((unsigned)Slot);
448 } else if (Opcode == 56) { // Invoke escape sequence
449 output_vbr(cast<InvokeInst>(I)->getCallingConv());
450 } else if (Opcode == 58) { // Call escape sequence
451 output_vbr((cast<CallInst>(I)->getCallingConv() << 1) |
452 unsigned(cast<CallInst>(I)->isTailCall()));
455 int Slot = Table.getSlot(I->getOperand(0));
456 assert(Slot >= 0 && "No slot number for value!?!?");
457 output_vbr(unsigned(Slot));
459 // We need to encode the type of sequential type indices into their slot #
461 for (gep_type_iterator TI = gep_type_begin(I), E = gep_type_end(I);
462 Idx != NumArgs; ++TI, ++Idx) {
463 Slot = Table.getSlot(I->getOperand(Idx));
464 assert(Slot >= 0 && "No slot number for value!?!?");
466 if (isa<SequentialType>(*TI)) {
468 switch (I->getOperand(Idx)->getType()->getTypeID()) {
469 default: assert(0 && "Unknown index type!");
470 case Type::UIntTyID: IdxId = 0; break;
471 case Type::IntTyID: IdxId = 1; break;
472 case Type::ULongTyID: IdxId = 2; break;
473 case Type::LongTyID: IdxId = 3; break;
475 Slot = (Slot << 2) | IdxId;
477 output_vbr(unsigned(Slot));
483 // outputInstrVarArgsCall - Output the absurdly annoying varargs function calls.
484 // This are more annoying than most because the signature of the call does not
485 // tell us anything about the types of the arguments in the varargs portion.
486 // Because of this, we encode (as type 0) all of the argument types explicitly
487 // before the argument value. This really sucks, but you shouldn't be using
488 // varargs functions in your code! *death to printf*!
490 // Format: [opcode] [type] [numargs] [arg0] [arg1] ... [arg<numargs-1>]
492 void BytecodeWriter::outputInstrVarArgsCall(const Instruction *I,
494 const SlotCalculator &Table,
496 assert(isa<CallInst>(I) || isa<InvokeInst>(I));
497 // Opcode must have top two bits clear...
498 output_vbr(Opcode << 2); // Instruction Opcode ID
499 output_typeid(Type); // Result type (varargs type)
501 const PointerType *PTy = cast<PointerType>(I->getOperand(0)->getType());
502 const FunctionType *FTy = cast<FunctionType>(PTy->getElementType());
503 unsigned NumParams = FTy->getNumParams();
505 unsigned NumFixedOperands;
506 if (isa<CallInst>(I)) {
507 // Output an operand for the callee and each fixed argument, then two for
508 // each variable argument.
509 NumFixedOperands = 1+NumParams;
511 assert(isa<InvokeInst>(I) && "Not call or invoke??");
512 // Output an operand for the callee and destinations, then two for each
513 // variable argument.
514 NumFixedOperands = 3+NumParams;
516 output_vbr(2 * I->getNumOperands()-NumFixedOperands);
518 // The type for the function has already been emitted in the type field of the
519 // instruction. Just emit the slot # now.
520 for (unsigned i = 0; i != NumFixedOperands; ++i) {
521 int Slot = Table.getSlot(I->getOperand(i));
522 assert(Slot >= 0 && "No slot number for value!?!?");
523 output_vbr((unsigned)Slot);
526 for (unsigned i = NumFixedOperands, e = I->getNumOperands(); i != e; ++i) {
527 // Output Arg Type ID
528 int Slot = Table.getSlot(I->getOperand(i)->getType());
529 assert(Slot >= 0 && "No slot number for value!?!?");
530 output_typeid((unsigned)Slot);
532 // Output arg ID itself
533 Slot = Table.getSlot(I->getOperand(i));
534 assert(Slot >= 0 && "No slot number for value!?!?");
535 output_vbr((unsigned)Slot);
540 // outputInstructionFormat1 - Output one operand instructions, knowing that no
541 // operand index is >= 2^12.
543 inline void BytecodeWriter::outputInstructionFormat1(const Instruction *I,
547 // bits Instruction format:
548 // --------------------------
549 // 01-00: Opcode type, fixed to 1.
551 // 19-08: Resulting type plane
552 // 31-20: Operand #1 (if set to (2^12-1), then zero operands)
554 output(1 | (Opcode << 2) | (Type << 8) | (Slots[0] << 20));
558 // outputInstructionFormat2 - Output two operand instructions, knowing that no
559 // operand index is >= 2^8.
561 inline void BytecodeWriter::outputInstructionFormat2(const Instruction *I,
565 // bits Instruction format:
566 // --------------------------
567 // 01-00: Opcode type, fixed to 2.
569 // 15-08: Resulting type plane
573 output(2 | (Opcode << 2) | (Type << 8) | (Slots[0] << 16) | (Slots[1] << 24));
577 // outputInstructionFormat3 - Output three operand instructions, knowing that no
578 // operand index is >= 2^6.
580 inline void BytecodeWriter::outputInstructionFormat3(const Instruction *I,
584 // bits Instruction format:
585 // --------------------------
586 // 01-00: Opcode type, fixed to 3.
588 // 13-08: Resulting type plane
593 output(3 | (Opcode << 2) | (Type << 8) |
594 (Slots[0] << 14) | (Slots[1] << 20) | (Slots[2] << 26));
597 void BytecodeWriter::outputInstruction(const Instruction &I) {
598 assert(I.getOpcode() < 56 && "Opcode too big???");
599 unsigned Opcode = I.getOpcode();
600 unsigned NumOperands = I.getNumOperands();
602 // Encode 'tail call' as 61, 'volatile load' as 62, and 'volatile store' as
604 if (const CallInst *CI = dyn_cast<CallInst>(&I)) {
605 if (CI->getCallingConv() == CallingConv::C) {
606 if (CI->isTailCall())
607 Opcode = 61; // CCC + Tail Call
609 ; // Opcode = Instruction::Call
610 } else if (CI->getCallingConv() == CallingConv::Fast) {
611 if (CI->isTailCall())
612 Opcode = 59; // FastCC + TailCall
614 Opcode = 60; // FastCC + Not Tail Call
616 Opcode = 58; // Call escape sequence.
618 } else if (const InvokeInst *II = dyn_cast<InvokeInst>(&I)) {
619 if (II->getCallingConv() == CallingConv::Fast)
620 Opcode = 57; // FastCC invoke.
621 else if (II->getCallingConv() != CallingConv::C)
622 Opcode = 56; // Invoke escape sequence.
624 } else if (isa<LoadInst>(I) && cast<LoadInst>(I).isVolatile()) {
626 } else if (isa<StoreInst>(I) && cast<StoreInst>(I).isVolatile()) {
630 // Figure out which type to encode with the instruction. Typically we want
631 // the type of the first parameter, as opposed to the type of the instruction
632 // (for example, with setcc, we always know it returns bool, but the type of
633 // the first param is actually interesting). But if we have no arguments
634 // we take the type of the instruction itself.
637 switch (I.getOpcode()) {
638 case Instruction::Select:
639 case Instruction::Malloc:
640 case Instruction::Alloca:
641 Ty = I.getType(); // These ALWAYS want to encode the return type
643 case Instruction::Store:
644 Ty = I.getOperand(1)->getType(); // Encode the pointer type...
645 assert(isa<PointerType>(Ty) && "Store to nonpointer type!?!?");
647 default: // Otherwise use the default behavior...
648 Ty = NumOperands ? I.getOperand(0)->getType() : I.getType();
653 int Slot = Table.getSlot(Ty);
654 assert(Slot != -1 && "Type not available!!?!");
655 Type = (unsigned)Slot;
657 // Varargs calls and invokes are encoded entirely different from any other
659 if (const CallInst *CI = dyn_cast<CallInst>(&I)){
660 const PointerType *Ty =cast<PointerType>(CI->getCalledValue()->getType());
661 if (cast<FunctionType>(Ty->getElementType())->isVarArg()) {
662 outputInstrVarArgsCall(CI, Opcode, Table, Type);
665 } else if (const InvokeInst *II = dyn_cast<InvokeInst>(&I)) {
666 const PointerType *Ty =cast<PointerType>(II->getCalledValue()->getType());
667 if (cast<FunctionType>(Ty->getElementType())->isVarArg()) {
668 outputInstrVarArgsCall(II, Opcode, Table, Type);
673 if (NumOperands <= 3) {
674 // Make sure that we take the type number into consideration. We don't want
675 // to overflow the field size for the instruction format we select.
677 unsigned MaxOpSlot = Type;
678 unsigned Slots[3]; Slots[0] = (1 << 12)-1; // Marker to signify 0 operands
680 for (unsigned i = 0; i != NumOperands; ++i) {
681 int slot = Table.getSlot(I.getOperand(i));
682 assert(slot != -1 && "Broken bytecode!");
683 if (unsigned(slot) > MaxOpSlot) MaxOpSlot = unsigned(slot);
684 Slots[i] = unsigned(slot);
687 // Handle the special cases for various instructions...
688 if (isa<CastInst>(I) || isa<VAArgInst>(I)) {
689 // Cast has to encode the destination type as the second argument in the
690 // packet, or else we won't know what type to cast to!
691 Slots[1] = Table.getSlot(I.getType());
692 assert(Slots[1] != ~0U && "Cast return type unknown?");
693 if (Slots[1] > MaxOpSlot) MaxOpSlot = Slots[1];
695 } else if (const AllocationInst *AI = dyn_cast<AllocationInst>(&I)) {
696 assert(NumOperands == 1 && "Bogus allocation!");
697 if (AI->getAlignment()) {
698 Slots[1] = Log2_32(AI->getAlignment())+1;
699 if (Slots[1] > MaxOpSlot) MaxOpSlot = Slots[1];
702 } else if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&I)) {
703 // We need to encode the type of sequential type indices into their slot #
705 for (gep_type_iterator I = gep_type_begin(GEP), E = gep_type_end(GEP);
707 if (isa<SequentialType>(*I)) {
709 switch (GEP->getOperand(Idx)->getType()->getTypeID()) {
710 default: assert(0 && "Unknown index type!");
711 case Type::UIntTyID: IdxId = 0; break;
712 case Type::IntTyID: IdxId = 1; break;
713 case Type::ULongTyID: IdxId = 2; break;
714 case Type::LongTyID: IdxId = 3; break;
716 Slots[Idx] = (Slots[Idx] << 2) | IdxId;
717 if (Slots[Idx] > MaxOpSlot) MaxOpSlot = Slots[Idx];
719 } else if (Opcode == 58) {
720 // If this is the escape sequence for call, emit the tailcall/cc info.
721 const CallInst &CI = cast<CallInst>(I);
723 if (NumOperands < 3) {
724 Slots[NumOperands-1] = (CI.getCallingConv() << 1)|unsigned(CI.isTailCall());
725 if (Slots[NumOperands-1] > MaxOpSlot)
726 MaxOpSlot = Slots[NumOperands-1];
728 } else if (Opcode == 56) {
729 // Invoke escape seq has at least 4 operands to encode.
733 // Decide which instruction encoding to use. This is determined primarily
734 // by the number of operands, and secondarily by whether or not the max
735 // operand will fit into the instruction encoding. More operands == fewer
738 switch (NumOperands) {
741 if (MaxOpSlot < (1 << 12)-1) { // -1 because we use 4095 to indicate 0 ops
742 outputInstructionFormat1(&I, Opcode, Slots, Type);
748 if (MaxOpSlot < (1 << 8)) {
749 outputInstructionFormat2(&I, Opcode, Slots, Type);
755 if (MaxOpSlot < (1 << 6)) {
756 outputInstructionFormat3(&I, Opcode, Slots, Type);
765 // If we weren't handled before here, we either have a large number of
766 // operands or a large operand index that we are referring to.
767 outputInstructionFormat0(&I, Opcode, Table, Type);
770 //===----------------------------------------------------------------------===//
771 //=== Block Output ===//
772 //===----------------------------------------------------------------------===//
774 BytecodeWriter::BytecodeWriter(std::vector<unsigned char> &o, const Module *M)
777 // Emit the signature...
778 static const unsigned char *Sig = (const unsigned char*)"llvm";
779 output_data(Sig, Sig+4);
781 // Emit the top level CLASS block.
782 BytecodeBlock ModuleBlock(BytecodeFormat::ModuleBlockID, *this, false, true);
784 bool isBigEndian = M->getEndianness() == Module::BigEndian;
785 bool hasLongPointers = M->getPointerSize() == Module::Pointer64;
786 bool hasNoEndianness = M->getEndianness() == Module::AnyEndianness;
787 bool hasNoPointerSize = M->getPointerSize() == Module::AnyPointerSize;
789 // Output the version identifier and other information.
790 unsigned Version = (BCVersionNum << 4) |
791 (unsigned)isBigEndian | (hasLongPointers << 1) |
792 (hasNoEndianness << 2) |
793 (hasNoPointerSize << 3);
796 // The Global type plane comes first
798 BytecodeBlock CPool(BytecodeFormat::GlobalTypePlaneBlockID, *this );
799 outputTypes(Type::FirstDerivedTyID);
802 // The ModuleInfoBlock follows directly after the type information
803 outputModuleInfoBlock(M);
805 // Output module level constants, used for global variable initializers
806 outputConstants(false);
808 // Do the whole module now! Process each function at a time...
809 for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I)
812 // If needed, output the symbol table for the module...
813 outputSymbolTable(M->getSymbolTable());
816 void BytecodeWriter::outputTypes(unsigned TypeNum) {
817 // Write the type plane for types first because earlier planes (e.g. for a
818 // primitive type like float) may have constants constructed using types
819 // coming later (e.g., via getelementptr from a pointer type). The type
820 // plane is needed before types can be fwd or bkwd referenced.
821 const std::vector<const Type*>& Types = Table.getTypes();
822 assert(!Types.empty() && "No types at all?");
823 assert(TypeNum <= Types.size() && "Invalid TypeNo index");
825 unsigned NumEntries = Types.size() - TypeNum;
827 // Output type header: [num entries]
828 output_vbr(NumEntries);
830 for (unsigned i = TypeNum; i < TypeNum+NumEntries; ++i)
831 outputType(Types[i]);
834 // Helper function for outputConstants().
835 // Writes out all the constants in the plane Plane starting at entry StartNo.
837 void BytecodeWriter::outputConstantsInPlane(const std::vector<const Value*>
838 &Plane, unsigned StartNo) {
839 unsigned ValNo = StartNo;
841 // Scan through and ignore function arguments, global values, and constant
843 for (; ValNo < Plane.size() &&
844 (isa<Argument>(Plane[ValNo]) || isa<GlobalValue>(Plane[ValNo]) ||
845 (isa<ConstantArray>(Plane[ValNo]) &&
846 cast<ConstantArray>(Plane[ValNo])->isString())); ValNo++)
849 unsigned NC = ValNo; // Number of constants
850 for (; NC < Plane.size() && (isa<Constant>(Plane[NC])); NC++)
852 NC -= ValNo; // Convert from index into count
853 if (NC == 0) return; // Skip empty type planes...
855 // FIXME: Most slabs only have 1 or 2 entries! We should encode this much
858 // Output type header: [num entries][type id number]
862 // Output the Type ID Number...
863 int Slot = Table.getSlot(Plane.front()->getType());
864 assert (Slot != -1 && "Type in constant pool but not in function!!");
865 output_typeid((unsigned)Slot);
867 for (unsigned i = ValNo; i < ValNo+NC; ++i) {
868 const Value *V = Plane[i];
869 if (const Constant *C = dyn_cast<Constant>(V)) {
875 static inline bool hasNullValue(const Type *Ty) {
876 return Ty != Type::LabelTy && Ty != Type::VoidTy && !isa<OpaqueType>(Ty);
879 void BytecodeWriter::outputConstants(bool isFunction) {
880 BytecodeBlock CPool(BytecodeFormat::ConstantPoolBlockID, *this,
881 true /* Elide block if empty */);
883 unsigned NumPlanes = Table.getNumPlanes();
886 // Output the type plane before any constants!
887 outputTypes(Table.getModuleTypeLevel());
889 // Output module-level string constants before any other constants.
890 outputConstantStrings();
892 for (unsigned pno = 0; pno != NumPlanes; pno++) {
893 const std::vector<const Value*> &Plane = Table.getPlane(pno);
894 if (!Plane.empty()) { // Skip empty type planes...
896 if (isFunction) // Don't re-emit module constants
897 ValNo += Table.getModuleLevel(pno);
899 if (hasNullValue(Plane[0]->getType())) {
900 // Skip zero initializer
905 // Write out constants in the plane
906 outputConstantsInPlane(Plane, ValNo);
911 static unsigned getEncodedLinkage(const GlobalValue *GV) {
912 switch (GV->getLinkage()) {
913 default: assert(0 && "Invalid linkage!");
914 case GlobalValue::ExternalLinkage: return 0;
915 case GlobalValue::WeakLinkage: return 1;
916 case GlobalValue::AppendingLinkage: return 2;
917 case GlobalValue::InternalLinkage: return 3;
918 case GlobalValue::LinkOnceLinkage: return 4;
922 void BytecodeWriter::outputModuleInfoBlock(const Module *M) {
923 BytecodeBlock ModuleInfoBlock(BytecodeFormat::ModuleGlobalInfoBlockID, *this);
925 // Output the types for the global variables in the module...
926 for (Module::const_global_iterator I = M->global_begin(),
927 End = M->global_end(); I != End; ++I) {
928 int Slot = Table.getSlot(I->getType());
929 assert(Slot != -1 && "Module global vars is broken!");
931 assert((I->hasInitializer() || !I->hasInternalLinkage()) &&
932 "Global must have an initializer or have external linkage!");
934 // Fields: bit0 = isConstant, bit1 = hasInitializer, bit2-4=Linkage,
935 // bit5+ = Slot # for type.
936 bool HasExtensionWord = I->getAlignment() != 0;
938 // If we need to use the extension byte, set linkage=3(internal) and
939 // initializer = 0 (impossible!).
940 if (!HasExtensionWord) {
941 unsigned oSlot = ((unsigned)Slot << 5) | (getEncodedLinkage(I) << 2) |
942 (I->hasInitializer() << 1) | (unsigned)I->isConstant();
945 unsigned oSlot = ((unsigned)Slot << 5) | (3 << 2) |
946 (0 << 1) | (unsigned)I->isConstant();
949 // The extension word has this format: bit 0 = has initializer, bit 1-3 =
950 // linkage, bit 4-8 = alignment (log2), bits 10+ = future use.
951 unsigned ExtWord = I->hasInitializer() | (getEncodedLinkage(I) << 1) |
952 ((Log2_32(I->getAlignment())+1) << 4);
956 // If we have an initializer, output it now.
957 if (I->hasInitializer()) {
958 Slot = Table.getSlot((Value*)I->getInitializer());
959 assert(Slot != -1 && "No slot for global var initializer!");
960 output_vbr((unsigned)Slot);
963 output_typeid((unsigned)Table.getSlot(Type::VoidTy));
965 // Output the types of the functions in this module.
966 for (Module::const_iterator I = M->begin(), End = M->end(); I != End; ++I) {
967 int Slot = Table.getSlot(I->getType());
968 assert(Slot != -1 && "Module slot calculator is broken!");
969 assert(Slot >= Type::FirstDerivedTyID && "Derived type not in range!");
970 assert(((Slot << 6) >> 6) == Slot && "Slot # too big!");
971 unsigned ID = (Slot << 5) | (I->getCallingConv() & 15);
973 if (I->isExternal()) // If external, we don't have an FunctionInfo block.
976 if (I->getAlignment() || I->getCallingConv() & ~15)
977 ID |= 1 << 31; // Do we need an extension word?
981 if (ID & (1 << 31)) {
982 // Extension byte: bits 0-4 = alignment, bits 5-9 = top nibble of calling
984 ID = (Log2_32(I->getAlignment())+1) | ((I->getCallingConv() >> 4) << 5);
988 output_vbr((unsigned)Table.getSlot(Type::VoidTy) << 5);
990 // Emit the list of dependent libraries for the Module.
991 Module::lib_iterator LI = M->lib_begin();
992 Module::lib_iterator LE = M->lib_end();
993 output_vbr(unsigned(LE - LI)); // Emit the number of dependent libraries.
994 for (; LI != LE; ++LI)
997 // Output the target triple from the module
998 output(M->getTargetTriple());
1001 void BytecodeWriter::outputInstructions(const Function *F) {
1002 BytecodeBlock ILBlock(BytecodeFormat::InstructionListBlockID, *this);
1003 for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
1004 for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I)
1005 outputInstruction(*I);
1008 void BytecodeWriter::outputFunction(const Function *F) {
1009 // If this is an external function, there is nothing else to emit!
1010 if (F->isExternal()) return;
1012 BytecodeBlock FunctionBlock(BytecodeFormat::FunctionBlockID, *this);
1013 output_vbr(getEncodedLinkage(F));
1015 // Get slot information about the function...
1016 Table.incorporateFunction(F);
1018 if (Table.getCompactionTable().empty()) {
1019 // Output information about the constants in the function if the compaction
1020 // table is not being used.
1021 outputConstants(true);
1023 // Otherwise, emit the compaction table.
1024 outputCompactionTable();
1027 // Output all of the instructions in the body of the function
1028 outputInstructions(F);
1030 // If needed, output the symbol table for the function...
1031 outputSymbolTable(F->getSymbolTable());
1033 Table.purgeFunction();
1036 void BytecodeWriter::outputCompactionTablePlane(unsigned PlaneNo,
1037 const std::vector<const Value*> &Plane,
1039 unsigned End = Table.getModuleLevel(PlaneNo);
1040 if (Plane.empty() || StartNo == End || End == 0) return; // Nothing to emit
1041 assert(StartNo < End && "Cannot emit negative range!");
1042 assert(StartNo < Plane.size() && End <= Plane.size());
1044 // Do not emit the null initializer!
1047 // Figure out which encoding to use. By far the most common case we have is
1048 // to emit 0-2 entries in a compaction table plane.
1049 switch (End-StartNo) {
1050 case 0: // Avoid emitting two vbr's if possible.
1053 output_vbr((PlaneNo << 2) | End-StartNo);
1056 // Output the number of things.
1057 output_vbr((unsigned(End-StartNo) << 2) | 3);
1058 output_typeid(PlaneNo); // Emit the type plane this is
1062 for (unsigned i = StartNo; i != End; ++i)
1063 output_vbr(Table.getGlobalSlot(Plane[i]));
1066 void BytecodeWriter::outputCompactionTypes(unsigned StartNo) {
1067 // Get the compaction type table from the slot calculator
1068 const std::vector<const Type*> &CTypes = Table.getCompactionTypes();
1070 // The compaction types may have been uncompactified back to the
1071 // global types. If so, we just write an empty table
1072 if (CTypes.size() == 0 ) {
1077 assert(CTypes.size() >= StartNo && "Invalid compaction types start index");
1079 // Determine how many types to write
1080 unsigned NumTypes = CTypes.size() - StartNo;
1082 // Output the number of types.
1083 output_vbr(NumTypes);
1085 for (unsigned i = StartNo; i < StartNo+NumTypes; ++i)
1086 output_typeid(Table.getGlobalSlot(CTypes[i]));
1089 void BytecodeWriter::outputCompactionTable() {
1090 // Avoid writing the compaction table at all if there is no content.
1091 if (Table.getCompactionTypes().size() >= Type::FirstDerivedTyID ||
1092 (!Table.CompactionTableIsEmpty())) {
1093 BytecodeBlock CTB(BytecodeFormat::CompactionTableBlockID, *this,
1094 true/*ElideIfEmpty*/);
1095 const std::vector<std::vector<const Value*> > &CT =
1096 Table.getCompactionTable();
1098 // First things first, emit the type compaction table if there is one.
1099 outputCompactionTypes(Type::FirstDerivedTyID);
1101 for (unsigned i = 0, e = CT.size(); i != e; ++i)
1102 outputCompactionTablePlane(i, CT[i], 0);
1106 void BytecodeWriter::outputSymbolTable(const SymbolTable &MST) {
1107 // Do not output the Bytecode block for an empty symbol table, it just wastes
1109 if (MST.isEmpty()) return;
1111 BytecodeBlock SymTabBlock(BytecodeFormat::SymbolTableBlockID, *this,
1112 true/*ElideIfEmpty*/);
1114 // Write the number of types
1115 output_vbr(MST.num_types());
1117 // Write each of the types
1118 for (SymbolTable::type_const_iterator TI = MST.type_begin(),
1119 TE = MST.type_end(); TI != TE; ++TI ) {
1120 // Symtab entry:[def slot #][name]
1121 output_typeid((unsigned)Table.getSlot(TI->second));
1125 // Now do each of the type planes in order.
1126 for (SymbolTable::plane_const_iterator PI = MST.plane_begin(),
1127 PE = MST.plane_end(); PI != PE; ++PI) {
1128 SymbolTable::value_const_iterator I = MST.value_begin(PI->first);
1129 SymbolTable::value_const_iterator End = MST.value_end(PI->first);
1132 if (I == End) continue; // Don't mess with an absent type...
1134 // Write the number of values in this plane
1135 output_vbr((unsigned)PI->second.size());
1137 // Write the slot number of the type for this plane
1138 Slot = Table.getSlot(PI->first);
1139 assert(Slot != -1 && "Type in symtab, but not in table!");
1140 output_typeid((unsigned)Slot);
1142 // Write each of the values in this plane
1143 for (; I != End; ++I) {
1144 // Symtab entry: [def slot #][name]
1145 Slot = Table.getSlot(I->second);
1146 assert(Slot != -1 && "Value in symtab but has no slot number!!");
1147 output_vbr((unsigned)Slot);
1153 void llvm::WriteBytecodeToFile(const Module *M, std::ostream &Out,
1155 assert(M && "You can't write a null module!!");
1157 // Create a vector of unsigned char for the bytecode output. We
1158 // reserve 256KBytes of space in the vector so that we avoid doing
1159 // lots of little allocations. 256KBytes is sufficient for a large
1160 // proportion of the bytecode files we will encounter. Larger files
1161 // will be automatically doubled in size as needed (std::vector
1163 std::vector<unsigned char> Buffer;
1164 Buffer.reserve(256 * 1024);
1166 // The BytecodeWriter populates Buffer for us.
1167 BytecodeWriter BCW(Buffer, M);
1169 // Keep track of how much we've written
1170 BytesWritten += Buffer.size();
1172 // Determine start and end points of the Buffer
1173 const unsigned char *FirstByte = &Buffer.front();
1175 // If we're supposed to compress this mess ...
1178 // We signal compression by using an alternate magic number for the
1179 // file. The compressed bytecode file's magic number is "llvc" instead
1181 char compressed_magic[4];
1182 compressed_magic[0] = 'l';
1183 compressed_magic[1] = 'l';
1184 compressed_magic[2] = 'v';
1185 compressed_magic[3] = 'c';
1187 Out.write(compressed_magic,4);
1189 // Compress everything after the magic number (which we altered)
1190 uint64_t zipSize = Compressor::compressToStream(
1191 (char*)(FirstByte+4), // Skip the magic number
1192 Buffer.size()-4, // Skip the magic number
1193 Out // Where to write compressed data
1198 // We're not compressing, so just write the entire block.
1199 Out.write((char*)FirstByte, Buffer.size());
1202 // make sure it hits disk now