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