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/DerivedTypes.h"
  15 #include "llvm/Instructions.h"
  16 #include "Support/Statistic.h"
  17 #include <algorithm>
  18
  19 static Statistic<>
  20 NumInstrs("bytecodewriter", "Number of instructions");
  21
  22 typedef unsigned char uchar;
  23
  24 // outputInstructionFormat0 - Output those wierd instructions that have a large
  25 // number of operands or have large operands themselves...
  26 //
  27 // Format: [opcode] [type] [numargs] [arg0] [arg1] ... [arg<numargs-1>]
  28 //
  29 static void outputInstructionFormat0(const Instruction *I, unsigned Opcode,
  30                                      const SlotCalculator &Table,
  31                                      unsigned Type, std::deque<uchar> &Out) {
  32   // Opcode must have top two bits clear...
  33   output_vbr(Opcode << 2, Out);                  // Instruction Opcode ID
  34   output_vbr(Type, Out);                         // Result type
  35
  36   unsigned NumArgs = I->getNumOperands();
  37   output_vbr(NumArgs + (isa<CastInst>(I) || isa<VarArgInst>(I)), Out);
  38
  39   for (unsigned i = 0; i < NumArgs; ++i) {
  40     int Slot = Table.getValSlot(I->getOperand(i));
  41     assert(Slot >= 0 && "No slot number for value!?!?");
  42     output_vbr((unsigned)Slot, Out);
  43   }
  44
  45   if (isa<CastInst>(I) || isa<VarArgInst>(I)) {
  46     int Slot = Table.getValSlot(I->getType());
  47     assert(Slot != -1 && "Cast/VarArg return type unknown?");
  48     output_vbr((unsigned)Slot, Out);
  49   }
  50
  51   align32(Out);    // We must maintain correct alignment!
  52 }
  53
  54
  55 // outputInstrVarArgsCall - Output the absurdly annoying varargs function calls.
  56 // This are more annoying than most because the signature of the call does not
  57 // tell us anything about the types of the arguments in the varargs portion.
  58 // Because of this, we encode (as type 0) all of the argument types explicitly
  59 // before the argument value.  This really sucks, but you shouldn't be using
  60 // varargs functions in your code! *death to printf*!
  61 //
  62 // Format: [opcode] [type] [numargs] [arg0] [arg1] ... [arg<numargs-1>]
  63 //
  64 static void outputInstrVarArgsCall(const Instruction *I, unsigned Opcode,
  65                                    const SlotCalculator &Table, unsigned Type,
  66                                    std::deque<uchar> &Out) {
  67   assert(isa<CallInst>(I) || isa<InvokeInst>(I));
  68   // Opcode must have top two bits clear...
  69   output_vbr(Opcode << 2, Out);                  // Instruction Opcode ID
  70   output_vbr(Type, Out);                         // Result type (varargs type)
  71
  72   unsigned NumArgs = I->getNumOperands();
  73   output_vbr(NumArgs*2, Out);
  74   // TODO: Don't need to emit types for the fixed types of the varargs function
  75   // prototype...
  76
  77   // The type for the function has already been emitted in the type field of the
  78   // instruction.  Just emit the slot # now.
  79   int Slot = Table.getValSlot(I->getOperand(0));
  80   assert(Slot >= 0 && "No slot number for value!?!?");
  81   output_vbr((unsigned)Slot, Out);
  82
  83   // Output a dummy field to fill Arg#2 in the reader that is currently unused
  84   // for varargs calls.  This is a gross hack to make the code simpler, but we
  85   // aren't really doing very small bytecode for varargs calls anyways.
  86   // FIXME in the future: Smaller bytecode for varargs calls
  87   output_vbr(0, Out);
  88
  89   for (unsigned i = 1; i < NumArgs; ++i) {
  90     // Output Arg Type ID
  91     Slot = Table.getValSlot(I->getOperand(i)->getType());
  92     assert(Slot >= 0 && "No slot number for value!?!?");
  93     output_vbr((unsigned)Slot, Out);
  94
  95     // Output arg ID itself
  96     Slot = Table.getValSlot(I->getOperand(i));
  97     assert(Slot >= 0 && "No slot number for value!?!?");
  98     output_vbr((unsigned)Slot, Out);
  99   }
 100   align32(Out);    // We must maintain correct alignment!
 101 }
 102
 103
 104 // outputInstructionFormat1 - Output one operand instructions, knowing that no
 105 // operand index is >= 2^12.
 106 //
 107 static void outputInstructionFormat1(const Instruction *I, unsigned Opcode,
 108                                      const SlotCalculator &Table, int *Slots,
 109                                      unsigned Type, std::deque<uchar> &Out) {
 110   // bits   Instruction format:
 111   // --------------------------
 112   // 01-00: Opcode type, fixed to 1.
 113   // 07-02: Opcode
 114   // 19-08: Resulting type plane
 115   // 31-20: Operand #1 (if set to (2^12-1), then zero operands)
 116   //
 117   unsigned Bits = 1 | (Opcode << 2) | (Type << 8) | (Slots[0] << 20);
 118   //  cerr << "1 " << IType << " " << Type << " " << Slots[0] << endl;
 119   output(Bits, Out);
 120 }
 121
 122
 123 // outputInstructionFormat2 - Output two operand instructions, knowing that no
 124 // operand index is >= 2^8.
 125 //
 126 static void outputInstructionFormat2(const Instruction *I, unsigned Opcode,
 127                                      const SlotCalculator &Table, int *Slots,
 128                                      unsigned Type, std::deque<uchar> &Out) {
 129   // bits   Instruction format:
 130   // --------------------------
 131   // 01-00: Opcode type, fixed to 2.
 132   // 07-02: Opcode
 133   // 15-08: Resulting type plane
 134   // 23-16: Operand #1
 135   // 31-24: Operand #2
 136   //
 137   unsigned Bits = 2 | (Opcode << 2) | (Type << 8) |
 138                     (Slots[0] << 16) | (Slots[1] << 24);
 139   //  cerr << "2 " << IType << " " << Type << " " << Slots[0] << " "
 140   //       << Slots[1] << endl;
 141   output(Bits, Out);
 142 }
 143
 144
 145 // outputInstructionFormat3 - Output three operand instructions, knowing that no
 146 // operand index is >= 2^6.
 147 //
 148 static void outputInstructionFormat3(const Instruction *I, unsigned Opcode,
 149                                      const SlotCalculator &Table, int *Slots,
 150                                      unsigned Type, std::deque<uchar> &Out) {
 151   // bits   Instruction format:
 152   // --------------------------
 153   // 01-00: Opcode type, fixed to 3.
 154   // 07-02: Opcode
 155   // 13-08: Resulting type plane
 156   // 19-14: Operand #1
 157   // 25-20: Operand #2
 158   // 31-26: Operand #3
 159   //
 160   unsigned Bits = 3 | (Opcode << 2) | (Type << 8) |
 161           (Slots[0] << 14) | (Slots[1] << 20) | (Slots[2] << 26);
 162   //cerr << "3 " << IType << " " << Type << " " << Slots[0] << " "
 163   //     << Slots[1] << " " << Slots[2] << endl;
 164   output(Bits, Out);
 165 }
 166
 167 void BytecodeWriter::processInstruction(const Instruction &I) {
 168   assert(I.getOpcode() < 62 && "Opcode too big???");
 169   unsigned Opcode = I.getOpcode();
 170
 171   // Encode 'volatile load' as 62 and 'volatile store' as 63.
 172   if (isa<LoadInst>(I) && cast<LoadInst>(I).isVolatile())
 173     Opcode = 62;
 174   if (isa<StoreInst>(I) && cast<StoreInst>(I).isVolatile())
 175     Opcode = 63;
 176
 177   unsigned NumOperands = I.getNumOperands();
 178   int MaxOpSlot = 0;
 179   int Slots[3]; Slots[0] = (1 << 12)-1;   // Marker to signify 0 operands
 180
 181   for (unsigned i = 0; i < NumOperands; ++i) {
 182     const Value *Def = I.getOperand(i);
 183     int slot = Table.getValSlot(Def);
 184     assert(slot != -1 && "Broken bytecode!");
 185     if (slot > MaxOpSlot) MaxOpSlot = slot;
 186     if (i < 3) Slots[i] = slot;
 187   }
 188
 189   // Figure out which type to encode with the instruction.  Typically we want
 190   // the type of the first parameter, as opposed to the type of the instruction
 191   // (for example, with setcc, we always know it returns bool, but the type of
 192   // the first param is actually interesting).  But if we have no arguments
 193   // we take the type of the instruction itself.
 194   //
 195   const Type *Ty;
 196   switch (I.getOpcode()) {
 197   case Instruction::Malloc:
 198   case Instruction::Alloca:
 199     Ty = I.getType();  // Malloc & Alloca ALWAYS want to encode the return type
 200     break;
 201   case Instruction::Store:
 202     Ty = I.getOperand(1)->getType();  // Encode the pointer type...
 203     assert(isa<PointerType>(Ty) && "Store to nonpointer type!?!?");
 204     break;
 205   default:              // Otherwise use the default behavior...
 206     Ty = NumOperands ? I.getOperand(0)->getType() : I.getType();
 207     break;
 208   }
 209
 210   unsigned Type;
 211   int Slot = Table.getValSlot(Ty);
 212   assert(Slot != -1 && "Type not available!!?!");
 213   Type = (unsigned)Slot;
 214
 215   // Make sure that we take the type number into consideration.  We don't want
 216   // to overflow the field size for the instruction format we select.
 217   //
 218   if (Slot > MaxOpSlot) MaxOpSlot = Slot;
 219
 220   // Handle the special case for cast...
 221   if (isa<CastInst>(I) || isa<VarArgInst>(I)) {
 222     // Cast has to encode the destination type as the second argument in the
 223     // packet, or else we won't know what type to cast to!
 224     Slots[1] = Table.getValSlot(I.getType());
 225     assert(Slots[1] != -1 && "Cast return type unknown?");
 226     if (Slots[1] > MaxOpSlot) MaxOpSlot = Slots[1];
 227     NumOperands++;
 228   } else if (const CallInst *CI = dyn_cast<CallInst>(&I)){// Handle VarArg calls
 229     const PointerType *Ty = cast<PointerType>(CI->getCalledValue()->getType());
 230     if (cast<FunctionType>(Ty->getElementType())->isVarArg()) {
 231       outputInstrVarArgsCall(CI, Opcode, Table, Type, Out);
 232       return;
 233     }
 234   } else if (const InvokeInst *II = dyn_cast<InvokeInst>(&I)) {// ...  & Invokes
 235     const PointerType *Ty = cast<PointerType>(II->getCalledValue()->getType());
 236     if (cast<FunctionType>(Ty->getElementType())->isVarArg()) {
 237       outputInstrVarArgsCall(II, Opcode, Table, Type, Out);
 238       return;
 239     }
 240   }
 241
 242   ++NumInstrs;
 243
 244   // Decide which instruction encoding to use.  This is determined primarily by
 245   // the number of operands, and secondarily by whether or not the max operand
 246   // will fit into the instruction encoding.  More operands == fewer bits per
 247   // operand.
 248   //
 249   switch (NumOperands) {
 250   case 0:
 251   case 1:
 252     if (MaxOpSlot < (1 << 12)-1) { // -1 because we use 4095 to indicate 0 ops
 253       outputInstructionFormat1(&I, Opcode, Table, Slots, Type, Out);
 254       return;
 255     }
 256     break;
 257
 258   case 2:
 259     if (MaxOpSlot < (1 << 8)) {
 260       outputInstructionFormat2(&I, Opcode, Table, Slots, Type, Out);
 261       return;
 262     }
 263     break;
 264
 265   case 3:
 266     if (MaxOpSlot < (1 << 6)) {
 267       outputInstructionFormat3(&I, Opcode, Table, Slots, Type, Out);
 268       return;
 269     }
 270     break;
 271   }
 272
 273   // If we weren't handled before here, we either have a large number of
 274   // operands or a large operand index that we are referring to.
 275   outputInstructionFormat0(&I, Opcode, Table, Type, Out);
 276 }