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