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