blob: 57012c9df93d4a310a681a27daa6af0147e0f94d [file] [log] [blame]
Chris Lattner44d2c352003-10-13 03:32:08 +00001//===-- InstructionWriter.cpp - Functions for writing instructions --------===//
Chris Lattner2f7c9632001-06-06 20:29:01 +00002//
3// This file implements the routines for encoding instruction opcodes to a
4// bytecode stream.
5//
Chris Lattner2f7c9632001-06-06 20:29:01 +00006//===----------------------------------------------------------------------===//
7
8#include "WriterInternals.h"
9#include "llvm/Module.h"
Chris Lattner2f7c9632001-06-06 20:29:01 +000010#include "llvm/DerivedTypes.h"
Chris Lattner8e8593a2003-09-08 17:58:37 +000011#include "llvm/Instructions.h"
Chris Lattnerbf3a0992002-10-01 22:38:41 +000012#include "Support/Statistic.h"
Chris Lattner2f7c9632001-06-06 20:29:01 +000013#include <algorithm>
14
Chris Lattner64eea742002-07-26 18:40:14 +000015static Statistic<>
Chris Lattner5d965972003-01-21 20:13:49 +000016NumInstrs("bytecodewriter", "Number of instructions");
Chris Lattner64eea742002-07-26 18:40:14 +000017
Chris Lattner2f7c9632001-06-06 20:29:01 +000018typedef unsigned char uchar;
19
20// outputInstructionFormat0 - Output those wierd instructions that have a large
21// number of operands or have large operands themselves...
22//
23// Format: [opcode] [type] [numargs] [arg0] [arg1] ... [arg<numargs-1>]
24//
Chris Lattner8e8593a2003-09-08 17:58:37 +000025static void outputInstructionFormat0(const Instruction *I, unsigned Opcode,
Chris Lattner2f7c9632001-06-06 20:29:01 +000026 const SlotCalculator &Table,
Chris Lattner7f74a562002-01-20 22:54:45 +000027 unsigned Type, std::deque<uchar> &Out) {
Chris Lattner2f7c9632001-06-06 20:29:01 +000028 // Opcode must have top two bits clear...
Chris Lattner8e8593a2003-09-08 17:58:37 +000029 output_vbr(Opcode << 2, Out); // Instruction Opcode ID
Chris Lattner2f7c9632001-06-06 20:29:01 +000030 output_vbr(Type, Out); // Result type
31
Chris Lattnera073acb2001-07-07 08:36:50 +000032 unsigned NumArgs = I->getNumOperands();
Chris Lattner9d573472003-10-18 05:54:48 +000033 output_vbr(NumArgs + (isa<CastInst>(I) || isa<VANextInst>(I) ||
34 isa<VAArgInst>(I)), Out);
Chris Lattner2f7c9632001-06-06 20:29:01 +000035
Chris Lattnera073acb2001-07-07 08:36:50 +000036 for (unsigned i = 0; i < NumArgs; ++i) {
Alkis Evlogimenos8faf8d92003-10-17 02:02:40 +000037 int Slot = Table.getSlot(I->getOperand(i));
Chris Lattner90e0d462001-07-25 22:47:55 +000038 assert(Slot >= 0 && "No slot number for value!?!?");
39 output_vbr((unsigned)Slot, Out);
40 }
Chris Lattner18e81932001-10-21 00:14:44 +000041
Chris Lattner9d573472003-10-18 05:54:48 +000042 if (isa<CastInst>(I) || isa<VAArgInst>(I)) {
Alkis Evlogimenos8faf8d92003-10-17 02:02:40 +000043 int Slot = Table.getSlot(I->getType());
Chris Lattner9d573472003-10-18 05:54:48 +000044 assert(Slot != -1 && "Cast return type unknown?");
45 output_vbr((unsigned)Slot, Out);
46 } else if (const VANextInst *VAI = dyn_cast<VANextInst>(I)) {
47 int Slot = Table.getSlot(VAI->getArgType());
48 assert(Slot != -1 && "VarArg argument type unknown?");
Chris Lattner18e81932001-10-21 00:14:44 +000049 output_vbr((unsigned)Slot, Out);
50 }
51
Chris Lattner90e0d462001-07-25 22:47:55 +000052 align32(Out); // We must maintain correct alignment!
53}
54
55
Misha Brukmanacda7df2003-09-11 22:34:13 +000056// outputInstrVarArgsCall - Output the absurdly annoying varargs function calls.
Chris Lattner90e0d462001-07-25 22:47:55 +000057// This are more annoying than most because the signature of the call does not
58// tell us anything about the types of the arguments in the varargs portion.
59// Because of this, we encode (as type 0) all of the argument types explicitly
60// before the argument value. This really sucks, but you shouldn't be using
61// varargs functions in your code! *death to printf*!
62//
63// Format: [opcode] [type] [numargs] [arg0] [arg1] ... [arg<numargs-1>]
64//
Chris Lattner8e8593a2003-09-08 17:58:37 +000065static void outputInstrVarArgsCall(const Instruction *I, unsigned Opcode,
Chris Lattner90e0d462001-07-25 22:47:55 +000066 const SlotCalculator &Table, unsigned Type,
Chris Lattner7f74a562002-01-20 22:54:45 +000067 std::deque<uchar> &Out) {
Chris Lattner81125b62001-10-13 06:48:38 +000068 assert(isa<CallInst>(I) || isa<InvokeInst>(I));
Chris Lattner90e0d462001-07-25 22:47:55 +000069 // Opcode must have top two bits clear...
Chris Lattner8e8593a2003-09-08 17:58:37 +000070 output_vbr(Opcode << 2, Out); // Instruction Opcode ID
Chris Lattner90e0d462001-07-25 22:47:55 +000071 output_vbr(Type, Out); // Result type (varargs type)
72
Chris Lattner9d573472003-10-18 05:54:48 +000073 const PointerType *PTy = cast<PointerType>(I->getOperand(0)->getType());
74 const FunctionType *FTy = cast<FunctionType>(PTy->getElementType());
75 unsigned NumParams = FTy->getNumParams();
76
77 unsigned NumFixedOperands;
78 if (isa<CallInst>(I)) {
79 // Output an operand for the callee and each fixed argument, then two for
80 // each variable argument.
81 NumFixedOperands = 1+NumParams;
82 } else {
83 assert(isa<InvokeInst>(I) && "Not call or invoke??");
84 // Output an operand for the callee and destinations, then two for each
85 // variable argument.
86 NumFixedOperands = 3+NumParams;
87 }
88 output_vbr(2 * I->getNumOperands()-NumFixedOperands, Out);
Chris Lattner90e0d462001-07-25 22:47:55 +000089
Chris Lattner62b7fd12002-04-07 20:49:59 +000090 // The type for the function has already been emitted in the type field of the
Chris Lattner81125b62001-10-13 06:48:38 +000091 // instruction. Just emit the slot # now.
Chris Lattner9d573472003-10-18 05:54:48 +000092 for (unsigned i = 0; i != NumFixedOperands; ++i) {
93 int Slot = Table.getSlot(I->getOperand(i));
Chris Lattner90e0d462001-07-25 22:47:55 +000094 assert(Slot >= 0 && "No slot number for value!?!?");
95 output_vbr((unsigned)Slot, Out);
Chris Lattner9d573472003-10-18 05:54:48 +000096 }
Chris Lattner90e0d462001-07-25 22:47:55 +000097
Chris Lattner9d573472003-10-18 05:54:48 +000098 for (unsigned i = NumFixedOperands, e = I->getNumOperands(); i != e; ++i) {
99 // Output Arg Type ID
100 int Slot = Table.getSlot(I->getOperand(i)->getType());
101 assert(Slot >= 0 && "No slot number for value!?!?");
102 output_vbr((unsigned)Slot, Out);
103
Chris Lattner90e0d462001-07-25 22:47:55 +0000104 // Output arg ID itself
Alkis Evlogimenos8faf8d92003-10-17 02:02:40 +0000105 Slot = Table.getSlot(I->getOperand(i));
Chris Lattnera073acb2001-07-07 08:36:50 +0000106 assert(Slot >= 0 && "No slot number for value!?!?");
Chris Lattner2f7c9632001-06-06 20:29:01 +0000107 output_vbr((unsigned)Slot, Out);
108 }
109 align32(Out); // We must maintain correct alignment!
110}
111
112
113// outputInstructionFormat1 - Output one operand instructions, knowing that no
114// operand index is >= 2^12.
115//
Chris Lattner8e8593a2003-09-08 17:58:37 +0000116static void outputInstructionFormat1(const Instruction *I, unsigned Opcode,
Chris Lattner2f7c9632001-06-06 20:29:01 +0000117 const SlotCalculator &Table, int *Slots,
Chris Lattner7f74a562002-01-20 22:54:45 +0000118 unsigned Type, std::deque<uchar> &Out) {
Chris Lattner2f7c9632001-06-06 20:29:01 +0000119 // bits Instruction format:
120 // --------------------------
Chris Lattnerb5498ab2001-10-23 03:21:10 +0000121 // 01-00: Opcode type, fixed to 1.
122 // 07-02: Opcode
123 // 19-08: Resulting type plane
124 // 31-20: Operand #1 (if set to (2^12-1), then zero operands)
Chris Lattner2f7c9632001-06-06 20:29:01 +0000125 //
Chris Lattnerb5498ab2001-10-23 03:21:10 +0000126 unsigned Bits = 1 | (Opcode << 2) | (Type << 8) | (Slots[0] << 20);
Chris Lattner2f7c9632001-06-06 20:29:01 +0000127 // cerr << "1 " << IType << " " << Type << " " << Slots[0] << endl;
Chris Lattnerb5498ab2001-10-23 03:21:10 +0000128 output(Bits, Out);
Chris Lattner2f7c9632001-06-06 20:29:01 +0000129}
130
131
132// outputInstructionFormat2 - Output two operand instructions, knowing that no
133// operand index is >= 2^8.
134//
Chris Lattner8e8593a2003-09-08 17:58:37 +0000135static void outputInstructionFormat2(const Instruction *I, unsigned Opcode,
Chris Lattner2f7c9632001-06-06 20:29:01 +0000136 const SlotCalculator &Table, int *Slots,
Chris Lattner7f74a562002-01-20 22:54:45 +0000137 unsigned Type, std::deque<uchar> &Out) {
Chris Lattner2f7c9632001-06-06 20:29:01 +0000138 // bits Instruction format:
139 // --------------------------
Chris Lattnerb5498ab2001-10-23 03:21:10 +0000140 // 01-00: Opcode type, fixed to 2.
141 // 07-02: Opcode
142 // 15-08: Resulting type plane
143 // 23-16: Operand #1
144 // 31-24: Operand #2
Chris Lattner2f7c9632001-06-06 20:29:01 +0000145 //
Chris Lattnerb5498ab2001-10-23 03:21:10 +0000146 unsigned Bits = 2 | (Opcode << 2) | (Type << 8) |
147 (Slots[0] << 16) | (Slots[1] << 24);
Chris Lattner2f7c9632001-06-06 20:29:01 +0000148 // cerr << "2 " << IType << " " << Type << " " << Slots[0] << " "
149 // << Slots[1] << endl;
Chris Lattnerb5498ab2001-10-23 03:21:10 +0000150 output(Bits, Out);
Chris Lattner2f7c9632001-06-06 20:29:01 +0000151}
152
153
154// outputInstructionFormat3 - Output three operand instructions, knowing that no
155// operand index is >= 2^6.
156//
Chris Lattner8e8593a2003-09-08 17:58:37 +0000157static void outputInstructionFormat3(const Instruction *I, unsigned Opcode,
Chris Lattner2f7c9632001-06-06 20:29:01 +0000158 const SlotCalculator &Table, int *Slots,
Chris Lattner7f74a562002-01-20 22:54:45 +0000159 unsigned Type, std::deque<uchar> &Out) {
Chris Lattner2f7c9632001-06-06 20:29:01 +0000160 // bits Instruction format:
161 // --------------------------
Chris Lattnerb5498ab2001-10-23 03:21:10 +0000162 // 01-00: Opcode type, fixed to 3.
163 // 07-02: Opcode
164 // 13-08: Resulting type plane
165 // 19-14: Operand #1
166 // 25-20: Operand #2
167 // 31-26: Operand #3
Chris Lattner2f7c9632001-06-06 20:29:01 +0000168 //
Chris Lattnerb5498ab2001-10-23 03:21:10 +0000169 unsigned Bits = 3 | (Opcode << 2) | (Type << 8) |
170 (Slots[0] << 14) | (Slots[1] << 20) | (Slots[2] << 26);
Chris Lattnera073acb2001-07-07 08:36:50 +0000171 //cerr << "3 " << IType << " " << Type << " " << Slots[0] << " "
172 // << Slots[1] << " " << Slots[2] << endl;
Chris Lattnerb5498ab2001-10-23 03:21:10 +0000173 output(Bits, Out);
Chris Lattner2f7c9632001-06-06 20:29:01 +0000174}
175
Chris Lattner7076ff22002-06-25 16:13:21 +0000176void BytecodeWriter::processInstruction(const Instruction &I) {
Chris Lattner8e8593a2003-09-08 17:58:37 +0000177 assert(I.getOpcode() < 62 && "Opcode too big???");
178 unsigned Opcode = I.getOpcode();
179
180 // Encode 'volatile load' as 62 and 'volatile store' as 63.
181 if (isa<LoadInst>(I) && cast<LoadInst>(I).isVolatile())
182 Opcode = 62;
183 if (isa<StoreInst>(I) && cast<StoreInst>(I).isVolatile())
184 Opcode = 63;
Chris Lattner2f7c9632001-06-06 20:29:01 +0000185
Chris Lattner7076ff22002-06-25 16:13:21 +0000186 unsigned NumOperands = I.getNumOperands();
Chris Lattner2f7c9632001-06-06 20:29:01 +0000187 int MaxOpSlot = 0;
Chris Lattnera073acb2001-07-07 08:36:50 +0000188 int Slots[3]; Slots[0] = (1 << 12)-1; // Marker to signify 0 operands
Chris Lattner2f7c9632001-06-06 20:29:01 +0000189
Chris Lattnera073acb2001-07-07 08:36:50 +0000190 for (unsigned i = 0; i < NumOperands; ++i) {
Chris Lattner7076ff22002-06-25 16:13:21 +0000191 const Value *Def = I.getOperand(i);
Alkis Evlogimenos8faf8d92003-10-17 02:02:40 +0000192 int slot = Table.getSlot(Def);
Chris Lattner2f7c9632001-06-06 20:29:01 +0000193 assert(slot != -1 && "Broken bytecode!");
194 if (slot > MaxOpSlot) MaxOpSlot = slot;
Chris Lattnera073acb2001-07-07 08:36:50 +0000195 if (i < 3) Slots[i] = slot;
Chris Lattner2f7c9632001-06-06 20:29:01 +0000196 }
197
198 // Figure out which type to encode with the instruction. Typically we want
199 // the type of the first parameter, as opposed to the type of the instruction
200 // (for example, with setcc, we always know it returns bool, but the type of
201 // the first param is actually interesting). But if we have no arguments
202 // we take the type of the instruction itself.
203 //
Chris Lattner62ecb4a2001-07-08 23:22:50 +0000204 const Type *Ty;
Chris Lattner7076ff22002-06-25 16:13:21 +0000205 switch (I.getOpcode()) {
Chris Lattner62ecb4a2001-07-08 23:22:50 +0000206 case Instruction::Malloc:
207 case Instruction::Alloca:
Chris Lattner7076ff22002-06-25 16:13:21 +0000208 Ty = I.getType(); // Malloc & Alloca ALWAYS want to encode the return type
Chris Lattner62ecb4a2001-07-08 23:22:50 +0000209 break;
210 case Instruction::Store:
Chris Lattner7076ff22002-06-25 16:13:21 +0000211 Ty = I.getOperand(1)->getType(); // Encode the pointer type...
Chris Lattner181cc322002-05-06 16:15:30 +0000212 assert(isa<PointerType>(Ty) && "Store to nonpointer type!?!?");
Chris Lattner62ecb4a2001-07-08 23:22:50 +0000213 break;
214 default: // Otherwise use the default behavior...
Chris Lattner7076ff22002-06-25 16:13:21 +0000215 Ty = NumOperands ? I.getOperand(0)->getType() : I.getType();
Chris Lattner62ecb4a2001-07-08 23:22:50 +0000216 break;
217 }
Chris Lattner2f7c9632001-06-06 20:29:01 +0000218
219 unsigned Type;
Alkis Evlogimenos8faf8d92003-10-17 02:02:40 +0000220 int Slot = Table.getSlot(Ty);
Chris Lattner2f7c9632001-06-06 20:29:01 +0000221 assert(Slot != -1 && "Type not available!!?!");
222 Type = (unsigned)Slot;
223
Chris Lattnerf324dc82001-07-28 17:51:21 +0000224 // Make sure that we take the type number into consideration. We don't want
225 // to overflow the field size for the instruction format we select.
226 //
227 if (Slot > MaxOpSlot) MaxOpSlot = Slot;
228
Chris Lattnera6821822001-07-08 04:57:15 +0000229 // Handle the special case for cast...
Chris Lattner9d573472003-10-18 05:54:48 +0000230 if (isa<CastInst>(I) || isa<VAArgInst>(I)) {
Chris Lattnera6821822001-07-08 04:57:15 +0000231 // Cast has to encode the destination type as the second argument in the
232 // packet, or else we won't know what type to cast to!
Alkis Evlogimenos8faf8d92003-10-17 02:02:40 +0000233 Slots[1] = Table.getSlot(I.getType());
Chris Lattnera6821822001-07-08 04:57:15 +0000234 assert(Slots[1] != -1 && "Cast return type unknown?");
235 if (Slots[1] > MaxOpSlot) MaxOpSlot = Slots[1];
236 NumOperands++;
Chris Lattner9d573472003-10-18 05:54:48 +0000237 } else if (const VANextInst *VANI = dyn_cast<VANextInst>(&I)) {
238 Slots[1] = Table.getSlot(VANI->getArgType());
239 assert(Slots[1] != -1 && "va_next return type unknown?");
240 if (Slots[1] > MaxOpSlot) MaxOpSlot = Slots[1];
241 NumOperands++;
Chris Lattner7076ff22002-06-25 16:13:21 +0000242 } else if (const CallInst *CI = dyn_cast<CallInst>(&I)){// Handle VarArg calls
Chris Lattner64802e42002-06-05 17:49:40 +0000243 const PointerType *Ty = cast<PointerType>(CI->getCalledValue()->getType());
Chris Lattnere2f2f542002-04-04 22:19:18 +0000244 if (cast<FunctionType>(Ty->getElementType())->isVarArg()) {
Chris Lattner8e8593a2003-09-08 17:58:37 +0000245 outputInstrVarArgsCall(CI, Opcode, Table, Type, Out);
Chris Lattner81125b62001-10-13 06:48:38 +0000246 return;
247 }
Chris Lattner7076ff22002-06-25 16:13:21 +0000248 } else if (const InvokeInst *II = dyn_cast<InvokeInst>(&I)) {// ... & Invokes
Chris Lattner64802e42002-06-05 17:49:40 +0000249 const PointerType *Ty = cast<PointerType>(II->getCalledValue()->getType());
Chris Lattnere2f2f542002-04-04 22:19:18 +0000250 if (cast<FunctionType>(Ty->getElementType())->isVarArg()) {
Chris Lattner8e8593a2003-09-08 17:58:37 +0000251 outputInstrVarArgsCall(II, Opcode, Table, Type, Out);
Chris Lattner7fac0702001-10-03 14:53:21 +0000252 return;
253 }
Chris Lattnera6821822001-07-08 04:57:15 +0000254 }
Chris Lattner2f7c9632001-06-06 20:29:01 +0000255
Chris Lattner5d965972003-01-21 20:13:49 +0000256 ++NumInstrs;
257
Chris Lattner2f7c9632001-06-06 20:29:01 +0000258 // Decide which instruction encoding to use. This is determined primarily by
259 // the number of operands, and secondarily by whether or not the max operand
260 // will fit into the instruction encoding. More operands == fewer bits per
261 // operand.
262 //
263 switch (NumOperands) {
264 case 0:
265 case 1:
266 if (MaxOpSlot < (1 << 12)-1) { // -1 because we use 4095 to indicate 0 ops
Chris Lattner8e8593a2003-09-08 17:58:37 +0000267 outputInstructionFormat1(&I, Opcode, Table, Slots, Type, Out);
Chris Lattnerb97ef9f2001-09-07 16:39:41 +0000268 return;
Chris Lattner2f7c9632001-06-06 20:29:01 +0000269 }
270 break;
271
272 case 2:
273 if (MaxOpSlot < (1 << 8)) {
Chris Lattner8e8593a2003-09-08 17:58:37 +0000274 outputInstructionFormat2(&I, Opcode, Table, Slots, Type, Out);
Chris Lattnerb97ef9f2001-09-07 16:39:41 +0000275 return;
Chris Lattner2f7c9632001-06-06 20:29:01 +0000276 }
277 break;
278
279 case 3:
280 if (MaxOpSlot < (1 << 6)) {
Chris Lattner8e8593a2003-09-08 17:58:37 +0000281 outputInstructionFormat3(&I, Opcode, Table, Slots, Type, Out);
Chris Lattnerb97ef9f2001-09-07 16:39:41 +0000282 return;
Chris Lattner2f7c9632001-06-06 20:29:01 +0000283 }
284 break;
285 }
286
Chris Lattner62ecb4a2001-07-08 23:22:50 +0000287 // If we weren't handled before here, we either have a large number of
Misha Brukmanacda7df2003-09-11 22:34:13 +0000288 // operands or a large operand index that we are referring to.
Chris Lattner8e8593a2003-09-08 17:58:37 +0000289 outputInstructionFormat0(&I, Opcode, Table, Type, Out);
Chris Lattner2f7c9632001-06-06 20:29:01 +0000290}