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