lib/Bytecode/Writer/InstructionWriter.cpp

   1 //===-- WriteInst.cpp - Functions for writing instructions -------*- C++ -*--=//
   2 //
   3 // This file implements the routines for encoding instruction opcodes to a
   4 // bytecode stream.
   5 //
   6 // Note that the performance of this library is not terribly important, because
   7 // it shouldn't be used by JIT type applications... so it is not a huge focus
   8 // at least.  :)
   9 //
  10 //===----------------------------------------------------------------------===//
  11
  12 #include "WriterInternals.h"
  13 #include "llvm/Module.h"
  14 #include "llvm/Method.h"
  15 #include "llvm/BasicBlock.h"
  16 #include "llvm/Instruction.h"
  17 #include "llvm/DerivedTypes.h"
  18 #include <algorithm>
  19
  20 typedef unsigned char uchar;
  21
  22 // outputInstructionFormat0 - Output those wierd instructions that have a large
  23 // number of operands or have large operands themselves...
  24 //
  25 // Format: [opcode] [type] [numargs] [arg0] [arg1] ... [arg<numargs-1>]
  26 //
  27 static void outputInstructionFormat0(const Instruction *I,
  28                                      const SlotCalculator &Table,
  29                                      unsigned Type, deque<uchar> &Out) {
  30   // Opcode must have top two bits clear...
  31   output_vbr(I->getOpcode(), Out);               // Instruction Opcode ID
  32   output_vbr(Type, Out);                         // Result type
  33
  34   unsigned NumArgs = I->getNumOperands();
  35   output_vbr(NumArgs, Out);
  36
  37   for (unsigned i = 0; i < NumArgs; ++i) {
  38     int Slot = Table.getValSlot(I->getOperand(i));
  39     assert(Slot >= 0 && "No slot number for value!?!?");
  40     output_vbr((unsigned)Slot, Out);
  41   }
  42   align32(Out);    // We must maintain correct alignment!
  43 }
  44
  45
  46 // outputInstrVarArgsCall - Output the obsurdly annoying varargs method calls.
  47 // This are more annoying than most because the signature of the call does not
  48 // tell us anything about the types of the arguments in the varargs portion.
  49 // Because of this, we encode (as type 0) all of the argument types explicitly
  50 // before the argument value.  This really sucks, but you shouldn't be using
  51 // varargs functions in your code! *death to printf*!
  52 //
  53 // Format: [opcode] [type] [numargs] [arg0] [arg1] ... [arg<numargs-1>]
  54 //
  55 static void outputInstrVarArgsCall(const Instruction *I,
  56                                    const SlotCalculator &Table, unsigned Type,
  57                                    deque<uchar> &Out) {
  58   assert(I->getOpcode() == Instruction::Call /*||
  59          I->getOpcode() == Instruction::ICall */);
  60   // Opcode must have top two bits clear...
  61   output_vbr(I->getOpcode(), Out);               // Instruction Opcode ID
  62   output_vbr(Type, Out);                         // Result type (varargs type)
  63
  64   unsigned NumArgs = I->getNumOperands();
  65   output_vbr((NumArgs-2)*2+2, Out); // Don't duplicate method & Arg1 types
  66
  67   // Output the method type without an extra type argument.
  68   int Slot = Table.getValSlot(I->getOperand(0));
  69   assert(Slot >= 0 && "No slot number for value!?!?");
  70   output_vbr((unsigned)Slot, Out);
  71
  72   // VarArgs methods must have at least one specified operand
  73   Slot = Table.getValSlot(I->getOperand(1));
  74   assert(Slot >= 0 && "No slot number for value!?!?");
  75   output_vbr((unsigned)Slot, Out);
  76
  77   for (unsigned i = 2; i < NumArgs; ++i) {
  78     // Output Arg Type ID
  79     Slot = Table.getValSlot(I->getOperand(i)->getType());
  80     assert(Slot >= 0 && "No slot number for value!?!?");
  81     output_vbr((unsigned)Slot, Out);
  82
  83     // Output arg ID itself
  84     Slot = Table.getValSlot(I->getOperand(i));
  85     assert(Slot >= 0 && "No slot number for value!?!?");
  86     output_vbr((unsigned)Slot, Out);
  87   }
  88   align32(Out);    // We must maintain correct alignment!
  89 }
  90
  91
  92 // outputInstructionFormat1 - Output one operand instructions, knowing that no
  93 // operand index is >= 2^12.
  94 //
  95 static void outputInstructionFormat1(const Instruction *I,
  96                                      const SlotCalculator &Table, int *Slots,
  97                                      unsigned Type, deque<uchar> &Out) {
  98   unsigned IType = I->getOpcode();      // Instruction Opcode ID
  99
 100   // bits   Instruction format:
 101   // --------------------------
 102   // 31-30: Opcode type, fixed to 1.
 103   // 29-24: Opcode
 104   // 23-12: Resulting type plane
 105   // 11- 0: Operand #1 (if set to (2^12-1), then zero operands)
 106   //
 107   unsigned Opcode = (1 << 30) | (IType << 24) | (Type << 12) | Slots[0];
 108   //  cerr << "1 " << IType << " " << Type << " " << Slots[0] << endl;
 109   output(Opcode, Out);
 110 }
 111
 112
 113 // outputInstructionFormat2 - Output two operand instructions, knowing that no
 114 // operand index is >= 2^8.
 115 //
 116 static void outputInstructionFormat2(const Instruction *I,
 117                                      const SlotCalculator &Table, int *Slots,
 118                                      unsigned Type, deque<uchar> &Out) {
 119   unsigned IType = I->getOpcode();      // Instruction Opcode ID
 120
 121   // bits   Instruction format:
 122   // --------------------------
 123   // 31-30: Opcode type, fixed to 2.
 124   // 29-24: Opcode
 125   // 23-16: Resulting type plane
 126   // 15- 8: Operand #1
 127   //  7- 0: Operand #2
 128   //
 129   unsigned Opcode = (2 << 30) | (IType << 24) | (Type << 16) |
 130                     (Slots[0] << 8) | (Slots[1] << 0);
 131   //  cerr << "2 " << IType << " " << Type << " " << Slots[0] << " "
 132   //       << Slots[1] << endl;
 133   output(Opcode, Out);
 134 }
 135
 136
 137 // outputInstructionFormat3 - Output three operand instructions, knowing that no
 138 // operand index is >= 2^6.
 139 //
 140 static void outputInstructionFormat3(const Instruction *I,
 141                                      const SlotCalculator &Table, int *Slots,
 142                                      unsigned Type, deque<uchar> &Out) {
 143   unsigned IType = I->getOpcode();      // Instruction Opcode ID
 144
 145   // bits   Instruction format:
 146   // --------------------------
 147   // 31-30: Opcode type, fixed to 3
 148   // 29-24: Opcode
 149   // 23-18: Resulting type plane
 150   // 17-12: Operand #1
 151   // 11- 6: Operand #2
 152   //  5- 0: Operand #3
 153   //
 154   unsigned Opcode = (3 << 30) | (IType << 24) | (Type << 18) |
 155                     (Slots[0] << 12) | (Slots[1] << 6) | (Slots[2] << 0);
 156   //cerr << "3 " << IType << " " << Type << " " << Slots[0] << " "
 157   //     << Slots[1] << " " << Slots[2] << endl;
 158   output(Opcode, Out);
 159 }
 160
 161 #include "llvm/Assembly/Writer.h"
 162
 163 void BytecodeWriter::processInstruction(const Instruction *I) {
 164   assert(I->getOpcode() < 64 && "Opcode too big???");
 165
 166   unsigned NumOperands = I->getNumOperands();
 167   int MaxOpSlot = 0;
 168   int Slots[3]; Slots[0] = (1 << 12)-1;   // Marker to signify 0 operands
 169
 170   for (unsigned i = 0; i < NumOperands; ++i) {
 171     const Value *Def = I->getOperand(i);
 172     int slot = Table.getValSlot(Def);
 173     assert(slot != -1 && "Broken bytecode!");
 174     if (slot > MaxOpSlot) MaxOpSlot = slot;
 175     if (i < 3) Slots[i] = slot;
 176   }
 177
 178   // Figure out which type to encode with the instruction.  Typically we want
 179   // the type of the first parameter, as opposed to the type of the instruction
 180   // (for example, with setcc, we always know it returns bool, but the type of
 181   // the first param is actually interesting).  But if we have no arguments
 182   // we take the type of the instruction itself.
 183   //
 184   const Type *Ty;
 185   switch (I->getOpcode()) {
 186   case Instruction::Malloc:
 187   case Instruction::Alloca:
 188     Ty = I->getType();  // Malloc & Alloca ALWAYS want to encode the return type
 189     break;
 190   case Instruction::Store:
 191     Ty = I->getOperand(1)->getType();  // Encode the pointer type...
 192     assert(Ty->isPointerType() && "Store to nonpointer type!?!?");
 193     break;
 194   default:              // Otherwise use the default behavior...
 195     Ty = NumOperands ? I->getOperand(0)->getType() : I->getType();
 196     break;
 197   }
 198
 199   unsigned Type;
 200   int Slot = Table.getValSlot(Ty);
 201   assert(Slot != -1 && "Type not available!!?!");
 202   Type = (unsigned)Slot;
 203
 204   // Make sure that we take the type number into consideration.  We don't want
 205   // to overflow the field size for the instruction format we select.
 206   //
 207   if (Slot > MaxOpSlot) MaxOpSlot = Slot;
 208
 209   // Handle the special case for cast...
 210   if (I->getOpcode() == Instruction::Cast) {
 211     // Cast has to encode the destination type as the second argument in the
 212     // packet, or else we won't know what type to cast to!
 213     Slots[1] = Table.getValSlot(I->getType());
 214     assert(Slots[1] != -1 && "Cast return type unknown?");
 215     if (Slots[1] > MaxOpSlot) MaxOpSlot = Slots[1];
 216     NumOperands++;
 217   } else if (I->getOpcode() == Instruction::Call &&  // Handle VarArg calls
 218              cast<MethodType>(I->getOperand(0)->getType())->isVarArg()) {
 219     outputInstrVarArgsCall(I, Table, Type, Out);
 220     return;
 221   }
 222
 223   // Decide which instruction encoding to use.  This is determined primarily by
 224   // the number of operands, and secondarily by whether or not the max operand
 225   // will fit into the instruction encoding.  More operands == fewer bits per
 226   // operand.
 227   //
 228   switch (NumOperands) {
 229   case 0:
 230   case 1:
 231     if (MaxOpSlot < (1 << 12)-1) { // -1 because we use 4095 to indicate 0 ops
 232       outputInstructionFormat1(I, Table, Slots, Type, Out);
 233       return;
 234     }
 235     break;
 236
 237   case 2:
 238     if (MaxOpSlot < (1 << 8)) {
 239       outputInstructionFormat2(I, Table, Slots, Type, Out);
 240       return;
 241     }
 242     break;
 243
 244   case 3:
 245     if (MaxOpSlot < (1 << 6)) {
 246       outputInstructionFormat3(I, Table, Slots, Type, Out);
 247       return;
 248     }
 249     break;
 250   }
 251
 252   // If we weren't handled before here, we either have a large number of
 253   // operands or a large operand index that we are refering to.
 254   outputInstructionFormat0(I, Table, Type, Out);
 255 }