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