lib/Bytecode/Writer/InstructionWriter.cpp

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