lib/Bytecode/Writer/InstructionWriter.cpp

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