include/llvm/CodeGen/MachineInstr.h

   1 // $Id$ -*-c++-*-
   2 //***************************************************************************
   3 // File:
   4 //      MachineInstr.h
   5 //
   6 // Purpose:
   7 //
   8 //
   9 // Strategy:
  10 //
  11 // History:
  12 //      7/2/01   -  Vikram Adve  -  Created
  13 //**************************************************************************/
  14
  15 #ifndef LLVM_CODEGEN_MACHINEINSTR_H
  16 #define LLVM_CODEGEN_MACHINEINSTR_H
  17
  18 #include <iterator>
  19 #include "llvm/CodeGen/InstrForest.h"
  20 #include "llvm/Support/DataTypes.h"
  21 #include "llvm/Support/NonCopyable.h"
  22 #include "llvm/Target/MachineInstrInfo.h"
  23 #include "llvm/Annotation.h"
  24 #include "llvm/Method.h"
  25 #include <hash_map>
  26 #include <hash_set>
  27 #include <values.h>
  28
  29 template<class _MI, class _V> class ValOpIterator;
  30
  31
  32 //************************** External Constants ****************************/
  33
  34 const int INVALID_FRAME_OFFSET = MAXINT;
  35
  36
  37 //*************************** External Classes *****************************/
  38
  39
  40 //---------------------------------------------------------------------------
  41 // class MachineOperand
  42 //
  43 // Purpose:
  44 //   Representation of each machine instruction operand.
  45 //   This class is designed so that you can allocate a vector of operands
  46 //   first and initialize each one later.
  47 //
  48 //   E.g, for this VM instruction:
  49 //              ptr = alloca type, numElements
  50 //   we generate 2 machine instructions on the SPARC:
  51 //
  52 //              mul Constant, Numelements -> Reg
  53 //              add %sp, Reg -> Ptr
  54 //
  55 //   Each instruction has 3 operands, listed above.  Of those:
  56 //   -  Reg, NumElements, and Ptr are of operand type MO_Register.
  57 //   -  Constant is of operand type MO_SignExtendedImmed on the SPARC.
  58 //
  59 //   For the register operands, the virtual register type is as follows:
  60 //
  61 //   -  Reg will be of virtual register type MO_MInstrVirtualReg.  The field
  62 //      MachineInstr* minstr will point to the instruction that computes reg.
  63 //
  64 //   -  %sp will be of virtual register type MO_MachineReg.
  65 //      The field regNum identifies the machine register.
  66 //
  67 //   -  NumElements will be of virtual register type MO_VirtualReg.
  68 //      The field Value* value identifies the value.
  69 //
  70 //   -  Ptr will also be of virtual register type MO_VirtualReg.
  71 //      Again, the field Value* value identifies the value.
  72 //
  73 //---------------------------------------------------------------------------
  74
  75
  76 class MachineOperand {
  77 public:
  78   enum MachineOperandType {
  79     MO_VirtualRegister,         // virtual register for *value
  80     MO_MachineRegister,         // pre-assigned machine register `regNum'
  81     MO_CCRegister,
  82     MO_SignExtendedImmed,
  83     MO_UnextendedImmed,
  84     MO_PCRelativeDisp,
  85   };
  86
  87 private:
  88   MachineOperandType opType;
  89
  90   union {
  91     Value*      value;          // BasicBlockVal for a label operand.
  92                                 // ConstantVal for a non-address immediate.
  93                                 // Virtual register for an SSA operand,
  94                                 // including hidden operands required for
  95                                 // the generated machine code.
  96     int64_t immedVal;           // constant value for an explicit constant
  97   };
  98
  99   int regNum;                   // register number for an explicit register
 100                                 // will be set for a value after reg allocation
 101   bool isDef;                   // is this a defition for the value
 102
 103 public:
 104   /*ctor*/              MachineOperand  ();
 105   /*ctor*/              MachineOperand  (MachineOperandType operandType,
 106                                          Value* _val);
 107   /*copy ctor*/         MachineOperand  (const MachineOperand&);
 108   /*dtor*/              ~MachineOperand () {}
 109
 110   // Accessor methods.  Caller is responsible for checking the
 111   // operand type before invoking the corresponding accessor.
 112   //
 113   inline MachineOperandType getOperandType      () const {
 114     return opType;
 115   }
 116   inline Value*         getVRegValue    () const {
 117     assert(opType == MO_VirtualRegister || opType == MO_CCRegister ||
 118            opType == MO_PCRelativeDisp);
 119     return value;
 120   }
 121   inline int            getMachineRegNum() const {
 122     assert(opType == MO_MachineRegister);
 123     return regNum;
 124   }
 125   inline int64_t        getImmedValue   () const {
 126     assert(opType == MO_SignExtendedImmed || opType == MO_UnextendedImmed);
 127     return immedVal;
 128   }
 129   inline bool           opIsDef         () const {
 130     return isDef;
 131   }
 132
 133 public:
 134   friend ostream& operator<<(ostream& os, const MachineOperand& mop);
 135
 136
 137 private:
 138   // These functions are provided so that a vector of operands can be
 139   // statically allocated and individual ones can be initialized later.
 140   // Give class MachineInstr gets access to these functions.
 141   //
 142   void                  Initialize      (MachineOperandType operandType,
 143                                          Value* _val);
 144   void                  InitializeConst (MachineOperandType operandType,
 145                                          int64_t intValue);
 146   void                  InitializeReg   (int regNum);
 147
 148   friend class MachineInstr;
 149   friend class ValOpIterator<const MachineInstr, const Value>;
 150   friend class ValOpIterator<      MachineInstr,       Value>;
 151
 152
 153 public:
 154
 155   // replaces the Value with its corresponding physical register after
 156   // register allocation is complete
 157   void setRegForValue(int reg) {
 158     assert(opType == MO_VirtualRegister || opType == MO_CCRegister ||
 159            opType == MO_MachineRegister);
 160     regNum = reg;
 161   }
 162
 163   // used to get the reg number if when one is allocted (must be
 164   // called only after reg alloc)
 165   inline int  getAllocatedRegNum() const {
 166     assert(opType == MO_VirtualRegister || opType == MO_CCRegister ||
 167            opType == MO_MachineRegister);
 168     return regNum;
 169   }
 170
 171
 172 };
 173
 174
 175 inline
 176 MachineOperand::MachineOperand()
 177   : opType(MO_VirtualRegister),
 178     immedVal(0),
 179     regNum(-1),
 180     isDef(false)
 181 {}
 182
 183 inline
 184 MachineOperand::MachineOperand(MachineOperandType operandType,
 185                                Value* _val)
 186   : opType(operandType),
 187     immedVal(0),
 188     regNum(-1),
 189     value(_val),
 190     isDef(false)
 191 {}
 192
 193 inline
 194 MachineOperand::MachineOperand(const MachineOperand& mo)
 195   : opType(mo.opType),
 196     isDef(false)
 197 {
 198   switch(opType) {
 199   case MO_VirtualRegister:
 200   case MO_CCRegister:           value = mo.value; break;
 201   case MO_MachineRegister:      regNum = mo.regNum; break;
 202   case MO_SignExtendedImmed:
 203   case MO_UnextendedImmed:
 204   case MO_PCRelativeDisp:       immedVal = mo.immedVal; break;
 205   default: assert(0);
 206   }
 207 }
 208
 209 inline void
 210 MachineOperand::Initialize(MachineOperandType operandType,
 211                            Value* _val)
 212 {
 213   opType = operandType;
 214   value = _val;
 215   regNum = -1;
 216 }
 217
 218 inline void
 219 MachineOperand::InitializeConst(MachineOperandType operandType,
 220                                 int64_t intValue)
 221 {
 222   opType = operandType;
 223   value = NULL;
 224   immedVal = intValue;
 225   regNum = -1;
 226 }
 227
 228 inline void
 229 MachineOperand::InitializeReg(int _regNum)
 230 {
 231   opType = MO_MachineRegister;
 232   value = NULL;
 233   regNum = (int) _regNum;
 234 }
 235
 236
 237 //---------------------------------------------------------------------------
 238 // class MachineInstr
 239 //
 240 // Purpose:
 241 //   Representation of each machine instruction.
 242 //
 243 //   MachineOpCode must be an enum, defined separately for each target.
 244 //   E.g., It is defined in SparcInstructionSelection.h for the SPARC.
 245 //
 246 //   opCodeMask is used to record variants of an instruction.
 247 //   E.g., each branch instruction on SPARC has 2 flags (i.e., 4 variants):
 248 //      ANNUL:             if 1: Annul delay slot instruction.
 249 //      PREDICT-NOT-TAKEN: if 1: predict branch not taken.
 250 //   Instead of creating 4 different opcodes for BNZ, we create a single
 251 //   opcode and set bits in opCodeMask for each of these flags.
 252 //
 253 //  There are 2 kinds of operands:
 254 //
 255 //  (1) Explicit operands of the machine instruction in vector operands[]
 256 //
 257 //  (2) "Implicit operands" are values implicitly used or defined by the
 258 //      machine instruction, such as arguments to a CALL, return value of
 259 //      a CALL (if any), and return value of a RETURN.
 260 //---------------------------------------------------------------------------
 261
 262 class MachineInstr : public NonCopyable {
 263 private:
 264   MachineOpCode         opCode;
 265   OpCodeMask            opCodeMask;     // extra bits for variants of an opcode
 266   vector<MachineOperand> operands;
 267   vector<Value*>        implicitRefs;   // values implicitly referenced by this
 268   vector<bool>          implicitIsDef;  // machine instruction (eg, call args)
 269
 270 public:
 271   typedef ValOpIterator<const MachineInstr, const Value> val_op_const_iterator;
 272   typedef ValOpIterator<const MachineInstr,       Value> val_op_iterator;
 273
 274 public:
 275   /*ctor*/              MachineInstr    (MachineOpCode _opCode,
 276                                          OpCodeMask    _opCodeMask = 0x0);
 277   /*ctor*/              MachineInstr    (MachineOpCode _opCode,
 278                                          unsigned       numOperands,
 279                                          OpCodeMask    _opCodeMask = 0x0);
 280   inline                ~MachineInstr   () {}
 281   const MachineOpCode   getOpCode       () const { return opCode; }
 282
 283   //
 284   // Information about explicit operands of the instruction
 285   //
 286   unsigned int          getNumOperands  () const { return operands.size(); }
 287
 288   bool                  operandIsDefined(unsigned int i) const;
 289
 290   const MachineOperand& getOperand      (unsigned int i) const;
 291         MachineOperand& getOperand      (unsigned int i);
 292
 293   //
 294   // Information about implicit operands of the instruction
 295   //
 296   unsigned int          getNumImplicitRefs() const{return implicitRefs.size();}
 297
 298   bool                  implicitRefIsDefined(unsigned int i) const;
 299
 300   const Value*          getImplicitRef  (unsigned int i) const;
 301         Value*          getImplicitRef  (unsigned int i);
 302
 303   //
 304   // Debugging support
 305   //
 306   void                  dump            (unsigned int indent = 0) const;
 307
 308
 309 public:
 310   friend ostream& operator<<(ostream& os, const MachineInstr& minstr);
 311   friend val_op_const_iterator;
 312   friend val_op_iterator;
 313
 314 public:
 315   // Access to set the operands when building the machine instruction
 316   void                  SetMachineOperand(unsigned int i,
 317                               MachineOperand::MachineOperandType operandType,
 318                               Value* _val, bool isDef=false);
 319   void                  SetMachineOperand(unsigned int i,
 320                               MachineOperand::MachineOperandType operandType,
 321                               int64_t intValue, bool isDef=false);
 322   void                  SetMachineOperand(unsigned int i,
 323                                           int regNum,
 324                                           bool isDef=false);
 325
 326   void                  addImplicitRef   (Value* val,
 327                                           bool isDef=false);
 328
 329   void                  setImplicitRef   (unsigned int i,
 330                                           Value* val,
 331                                           bool isDef=false);
 332 };
 333
 334
 335 inline MachineOperand&
 336 MachineInstr::getOperand(unsigned int i)
 337 {
 338   assert(i < operands.size() && "getOperand() out of range!");
 339   return operands[i];
 340 }
 341
 342 inline const MachineOperand&
 343 MachineInstr::getOperand(unsigned int i) const
 344 {
 345   assert(i < operands.size() && "getOperand() out of range!");
 346   return operands[i];
 347 }
 348
 349 inline bool
 350 MachineInstr::operandIsDefined(unsigned int i) const
 351 {
 352   return getOperand(i).opIsDef();
 353 }
 354
 355 inline bool
 356 MachineInstr::implicitRefIsDefined(unsigned int i) const
 357 {
 358   assert(i < implicitIsDef.size() && "operand out of range!");
 359   return implicitIsDef[i];
 360 }
 361
 362 inline const Value*
 363 MachineInstr::getImplicitRef(unsigned int i) const
 364 {
 365   assert(i < implicitRefs.size() && "getImplicitRef() out of range!");
 366   return implicitRefs[i];
 367 }
 368
 369 inline Value*
 370 MachineInstr::getImplicitRef(unsigned int i)
 371 {
 372   assert(i < implicitRefs.size() && "getImplicitRef() out of range!");
 373   return implicitRefs[i];
 374 }
 375
 376 inline void
 377 MachineInstr::addImplicitRef(Value* val,
 378                              bool isDef)
 379 {
 380   implicitRefs.push_back(val);
 381   implicitIsDef.push_back(isDef);
 382 }
 383
 384 inline void
 385 MachineInstr::setImplicitRef(unsigned int i,
 386                              Value* val,
 387                              bool isDef)
 388 {
 389   assert(i < implicitRefs.size() && "setImplicitRef() out of range!");
 390   implicitRefs[i] = val;
 391   implicitIsDef[i] = isDef;
 392 }
 393
 394
 395 template<class _MI, class _V>
 396 class ValOpIterator : public std::forward_iterator<_V, ptrdiff_t> {
 397 private:
 398   unsigned int i;
 399   int resultPos;
 400   _MI* minstr;
 401
 402   inline void   skipToNextVal() {
 403     while (i < minstr->getNumOperands() &&
 404            ! ((minstr->operands[i].opType == MachineOperand::MO_VirtualRegister
 405                || minstr->operands[i].opType == MachineOperand::MO_CCRegister)
 406               && minstr->operands[i].value != NULL))
 407       ++i;
 408   }
 409
 410 public:
 411   typedef ValOpIterator<_MI, _V> _Self;
 412
 413   inline ValOpIterator(_MI* _minstr) : i(0), minstr(_minstr) {
 414     resultPos = TargetInstrDescriptors[minstr->opCode].resultPos;
 415     skipToNextVal();
 416   };
 417
 418   inline _V*    operator*()  const { return minstr->getOperand(i).getVRegValue();}
 419
 420   const MachineOperand & getMachineOperand() const { return minstr->getOperand(i);  }
 421
 422   inline _V*    operator->() const { return operator*(); }
 423   //  inline bool       isDef   ()   const { return (((int) i) == resultPos); }
 424
 425   inline bool   isDef   ()   const { return minstr->getOperand(i).isDef; }
 426   inline bool   done    ()   const { return (i == minstr->getNumOperands()); }
 427
 428   inline _Self& operator++()       { i++; skipToNextVal(); return *this; }
 429   inline _Self  operator++(int)    { _Self tmp = *this; ++*this; return tmp; }
 430 };
 431
 432
 433 //---------------------------------------------------------------------------
 434 // class MachineCodeForVMInstr
 435 //
 436 // Purpose:
 437 //   Representation of the sequence of machine instructions created
 438 //   for a single VM instruction.  Additionally records information
 439 //   about hidden and implicit values used by the machine instructions:
 440 //   about hidden values used by the machine instructions:
 441 //
 442 //   "Temporary values" are intermediate values used in the machine
 443 //   instruction sequence, but not in the VM instruction
 444 //   Note that such values should be treated as pure SSA values with
 445 //   no interpretation of their operands (i.e., as a TmpInstruction
 446 //   object which actually represents such a value).
 447 //
 448 //   (2) "Implicit uses" are values used in the VM instruction but not in
 449 //       the machine instruction sequence
 450 //
 451 //---------------------------------------------------------------------------
 452
 453 class MachineCodeForVMInstr: public vector<MachineInstr*>
 454 {
 455 private:
 456   vector<Value*> tempVec;         // used by m/c instr but not VM instr
 457
 458 public:
 459   /*ctor*/      MachineCodeForVMInstr   ()      {}
 460   /*ctor*/      ~MachineCodeForVMInstr  ();
 461
 462   const vector<Value*>& getTempValues  () const { return tempVec; }
 463         vector<Value*>& getTempValues  ()       { return tempVec; }
 464
 465   void    addTempValue  (Value* val)            { tempVec.push_back(val); }
 466
 467   // dropAllReferences() - This function drops all references within
 468   // temporary (hidden) instructions created in implementing the original
 469   // VM intruction.  This ensures there are no remaining "uses" within
 470   // these hidden instructions, before the values of a method are freed.
 471   //
 472   // Make this inline because it has to be called from class Instruction
 473   // and inlining it avoids a serious circurality in link order.
 474   inline void dropAllReferences() {
 475     for (unsigned i=0, N=tempVec.size(); i < N; i++)
 476       if (Instruction *I = dyn_cast<Instruction>(tempVec[i]))
 477         I->dropAllReferences();
 478   }
 479 };
 480
 481 inline
 482 MachineCodeForVMInstr::~MachineCodeForVMInstr()
 483 {
 484   // Free the Value objects created to hold intermediate values
 485   for (unsigned i=0, N=tempVec.size(); i < N; i++)
 486     delete tempVec[i];
 487
 488   // Free the MachineInstr objects allocated, if any.
 489   for (unsigned i=0, N=this->size(); i < N; i++)
 490     delete (*this)[i];
 491 }
 492
 493
 494 //---------------------------------------------------------------------------
 495 // class MachineCodeForBasicBlock
 496 //
 497 // Purpose:
 498 //   Representation of the sequence of machine instructions created
 499 //   for a basic block.
 500 //---------------------------------------------------------------------------
 501
 502
 503 class MachineCodeForBasicBlock: public vector<MachineInstr*> {
 504 public:
 505   typedef vector<MachineInstr*>::iterator iterator;
 506   typedef vector<const MachineInstr*>::const_iterator const_iterator;
 507 };
 508
 509
 510 //---------------------------------------------------------------------------
 511 // class MachineCodeForMethod
 512 //
 513 // Purpose:
 514 //   Collect native machine code information for a method.
 515 //   This allows target-specific information about the generated code
 516 //   to be stored with each method.
 517 //---------------------------------------------------------------------------
 518
 519
 520
 521 class MachineCodeForMethod: public NonCopyable, private Annotation {
 522 private:
 523   static AnnotationID AID;
 524 private:
 525   const Method* method;
 526   bool          compiledAsLeaf;
 527   unsigned      staticStackSize;
 528   unsigned      automaticVarsSize;
 529   unsigned      regSpillsSize;
 530   unsigned      currentOptionalArgsSize;
 531   unsigned      maxOptionalArgsSize;
 532   unsigned      currentTmpValuesSize;
 533   hash_set<const ConstPoolVal*> constantsForConstPool;
 534   hash_map<const Value*, int> offsets;
 535   // hash_map<const Value*, int> offsetsFromSP;
 536
 537 public:
 538   /*ctor*/      MachineCodeForMethod(const Method* method,
 539                                      const TargetMachine& target);
 540
 541   // The next two methods are used to construct and to retrieve
 542   // the MachineCodeForMethod object for the given method.
 543   // construct() -- Allocates and initializes for a given method and target
 544   // get()       -- Returns a handle to the object.
 545   //                This should not be called before "construct()"
 546   //                for a given Method.
 547   //
 548   inline static MachineCodeForMethod& construct(const Method* method,
 549                                                 const TargetMachine& target)
 550   {
 551     assert(method->getAnnotation(MachineCodeForMethod::AID) == NULL &&
 552            "Object already exists for this method!");
 553     MachineCodeForMethod* mcInfo = new MachineCodeForMethod(method, target);
 554     method->addAnnotation(mcInfo);
 555     return *mcInfo;
 556   }
 557
 558   inline static MachineCodeForMethod& get(const Method* method)
 559   {
 560     MachineCodeForMethod* mc = (MachineCodeForMethod*)
 561       method->getAnnotation(MachineCodeForMethod::AID);
 562     assert(mc && "Call construct() method first to allocate the object");
 563     return *mc;
 564   }
 565
 566   //
 567   // Accessors for global information about generated code for a method.
 568   //
 569   inline bool     isCompiledAsLeafMethod() const { return compiledAsLeaf; }
 570   inline unsigned getStaticStackSize()     const { return staticStackSize; }
 571   inline unsigned getAutomaticVarsSize()   const { return automaticVarsSize; }
 572   inline unsigned getRegSpillsSize()       const { return regSpillsSize; }
 573   inline unsigned getMaxOptionalArgsSize() const { return maxOptionalArgsSize;}
 574   inline unsigned getCurrentOptionalArgsSize() const
 575                                              { return currentOptionalArgsSize;}
 576   inline const hash_set<const ConstPoolVal*>&
 577                   getConstantPoolValues() const {return constantsForConstPool;}
 578
 579   //
 580   // Modifiers used during code generation
 581   //
 582   void            initializeFrameLayout    (const TargetMachine& target);
 583
 584   void            addToConstantPool        (const ConstPoolVal* constVal)
 585                                     { constantsForConstPool.insert(constVal); }
 586
 587   inline void     markAsLeafMethod()              { compiledAsLeaf = true; }
 588
 589   int             allocateLocalVar         (const TargetMachine& target,
 590                                             const Value* local,
 591                                             unsigned int size = 0);
 592
 593   int             allocateSpilledValue     (const TargetMachine& target,
 594                                             const Type* type);
 595
 596   int             allocateOptionalArg      (const TargetMachine& target,
 597                                             const Type* type);
 598
 599   void            resetOptionalArgs        (const TargetMachine& target);
 600
 601   int             pushTempValue            (const TargetMachine& target,
 602                                             unsigned int size);
 603
 604   void            popAllTempValues         (const TargetMachine& target);
 605
 606   int             getOffset                (const Value* val) const;
 607
 608   // int          getOffsetFromFP       (const Value* val) const;
 609
 610   void            dump                     () const;
 611
 612 private:
 613   inline void     incrementAutomaticVarsSize(int incr) {
 614     automaticVarsSize+= incr;
 615     staticStackSize += incr;
 616   }
 617   inline void     incrementRegSpillsSize(int incr) {
 618     regSpillsSize+= incr;
 619     staticStackSize += incr;
 620   }
 621   inline void     incrementCurrentOptionalArgsSize(int incr) {
 622     currentOptionalArgsSize+= incr;     // stack size already includes this!
 623   }
 624 };
 625
 626
 627 //---------------------------------------------------------------------------
 628 // Debugging Support
 629 //---------------------------------------------------------------------------
 630
 631
 632 ostream& operator<<             (ostream& os, const MachineInstr& minstr);
 633
 634
 635 ostream& operator<<             (ostream& os, const MachineOperand& mop);
 636
 637
 638 void    PrintMachineInstructions(const Method *method);
 639
 640
 641 //**************************************************************************/
 642
 643 #endif