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 "Support/DataTypes.h"
  19 #include "Support/NonCopyable.h"
  20 #include "llvm/CodeGen/InstrForest.h"
  21 #include "llvm/Target/MachineInstrInfo.h"
  22 #include "llvm/Annotation.h"
  23 #include "llvm/Method.h"
  24 #include <iterator>
  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     isDef(false)
 190 {}
 191
 192 inline
 193 MachineOperand::MachineOperand(const MachineOperand& mo)
 194   : opType(mo.opType),
 195     isDef(false)
 196 {
 197   switch(opType) {
 198   case MO_VirtualRegister:
 199   case MO_CCRegister:           value = mo.value; break;
 200   case MO_MachineRegister:      regNum = mo.regNum; break;
 201   case MO_SignExtendedImmed:
 202   case MO_UnextendedImmed:
 203   case MO_PCRelativeDisp:       immedVal = mo.immedVal; break;
 204   default: assert(0);
 205   }
 206 }
 207
 208 inline void
 209 MachineOperand::Initialize(MachineOperandType operandType,
 210                            Value* _val)
 211 {
 212   opType = operandType;
 213   value = _val;
 214   regNum = -1;
 215 }
 216
 217 inline void
 218 MachineOperand::InitializeConst(MachineOperandType operandType,
 219                                 int64_t intValue)
 220 {
 221   opType = operandType;
 222   value = NULL;
 223   immedVal = intValue;
 224   regNum = -1;
 225 }
 226
 227 inline void
 228 MachineOperand::InitializeReg(int _regNum)
 229 {
 230   opType = MO_MachineRegister;
 231   value = NULL;
 232   regNum = (int) _regNum;
 233 }
 234
 235
 236 //---------------------------------------------------------------------------
 237 // class MachineInstr
 238 //
 239 // Purpose:
 240 //   Representation of each machine instruction.
 241 //
 242 //   MachineOpCode must be an enum, defined separately for each target.
 243 //   E.g., It is defined in SparcInstructionSelection.h for the SPARC.
 244 //
 245 //   opCodeMask is used to record variants of an instruction.
 246 //   E.g., each branch instruction on SPARC has 2 flags (i.e., 4 variants):
 247 //      ANNUL:             if 1: Annul delay slot instruction.
 248 //      PREDICT-NOT-TAKEN: if 1: predict branch not taken.
 249 //   Instead of creating 4 different opcodes for BNZ, we create a single
 250 //   opcode and set bits in opCodeMask for each of these flags.
 251 //
 252 //  There are 2 kinds of operands:
 253 //
 254 //  (1) Explicit operands of the machine instruction in vector operands[]
 255 //
 256 //  (2) "Implicit operands" are values implicitly used or defined by the
 257 //      machine instruction, such as arguments to a CALL, return value of
 258 //      a CALL (if any), and return value of a RETURN.
 259 //---------------------------------------------------------------------------
 260
 261 class MachineInstr : public NonCopyable {
 262 private:
 263   MachineOpCode         opCode;
 264   OpCodeMask            opCodeMask;     // extra bits for variants of an opcode
 265   vector<MachineOperand> operands;
 266   vector<Value*>        implicitRefs;   // values implicitly referenced by this
 267   vector<bool>          implicitIsDef;  // machine instruction (eg, call args)
 268
 269 public:
 270   typedef ValOpIterator<const MachineInstr, const Value> val_op_const_iterator;
 271   typedef ValOpIterator<const MachineInstr,       Value> val_op_iterator;
 272
 273 public:
 274   /*ctor*/              MachineInstr    (MachineOpCode _opCode,
 275                                          OpCodeMask    _opCodeMask = 0x0);
 276   /*ctor*/              MachineInstr    (MachineOpCode _opCode,
 277                                          unsigned       numOperands,
 278                                          OpCodeMask    _opCodeMask = 0x0);
 279   inline                ~MachineInstr   () {}
 280   const MachineOpCode   getOpCode       () const { return opCode; }
 281
 282   //
 283   // Information about explicit operands of the instruction
 284   //
 285   unsigned int          getNumOperands  () const { return operands.size(); }
 286
 287   bool                  operandIsDefined(unsigned int i) const;
 288
 289   const MachineOperand& getOperand      (unsigned int i) const;
 290         MachineOperand& getOperand      (unsigned int i);
 291
 292   //
 293   // Information about implicit operands of the instruction
 294   //
 295   unsigned int          getNumImplicitRefs() const{return implicitRefs.size();}
 296
 297   bool                  implicitRefIsDefined(unsigned int i) const;
 298
 299   const Value*          getImplicitRef  (unsigned int i) const;
 300         Value*          getImplicitRef  (unsigned int i);
 301
 302   //
 303   // Debugging support
 304   //
 305   void                  dump            (unsigned int indent = 0) const;
 306
 307
 308 public:
 309   friend ostream& operator<<(ostream& os, const MachineInstr& minstr);
 310   friend val_op_const_iterator;
 311   friend val_op_iterator;
 312
 313 public:
 314   // Access to set the operands when building the machine instruction
 315   void                  SetMachineOperand(unsigned int i,
 316                               MachineOperand::MachineOperandType operandType,
 317                               Value* _val, bool isDef=false);
 318   void                  SetMachineOperand(unsigned int i,
 319                               MachineOperand::MachineOperandType operandType,
 320                               int64_t intValue, bool isDef=false);
 321   void                  SetMachineOperand(unsigned int i,
 322                                           int regNum,
 323                                           bool isDef=false);
 324
 325   void                  addImplicitRef   (Value* val,
 326                                           bool isDef=false);
 327
 328   void                  setImplicitRef   (unsigned int i,
 329                                           Value* val,
 330                                           bool isDef=false);
 331 };
 332
 333
 334 inline MachineOperand&
 335 MachineInstr::getOperand(unsigned int i)
 336 {
 337   assert(i < operands.size() && "getOperand() out of range!");
 338   return operands[i];
 339 }
 340
 341 inline const MachineOperand&
 342 MachineInstr::getOperand(unsigned int i) const
 343 {
 344   assert(i < operands.size() && "getOperand() out of range!");
 345   return operands[i];
 346 }
 347
 348 inline bool
 349 MachineInstr::operandIsDefined(unsigned int i) const
 350 {
 351   return getOperand(i).opIsDef();
 352 }
 353
 354 inline bool
 355 MachineInstr::implicitRefIsDefined(unsigned int i) const
 356 {
 357   assert(i < implicitIsDef.size() && "operand out of range!");
 358   return implicitIsDef[i];
 359 }
 360
 361 inline const Value*
 362 MachineInstr::getImplicitRef(unsigned int i) const
 363 {
 364   assert(i < implicitRefs.size() && "getImplicitRef() out of range!");
 365   return implicitRefs[i];
 366 }
 367
 368 inline Value*
 369 MachineInstr::getImplicitRef(unsigned int i)
 370 {
 371   assert(i < implicitRefs.size() && "getImplicitRef() out of range!");
 372   return implicitRefs[i];
 373 }
 374
 375 inline void
 376 MachineInstr::addImplicitRef(Value* val,
 377                              bool isDef)
 378 {
 379   implicitRefs.push_back(val);
 380   implicitIsDef.push_back(isDef);
 381 }
 382
 383 inline void
 384 MachineInstr::setImplicitRef(unsigned int i,
 385                              Value* val,
 386                              bool isDef)
 387 {
 388   assert(i < implicitRefs.size() && "setImplicitRef() out of range!");
 389   implicitRefs[i] = val;
 390   implicitIsDef[i] = isDef;
 391 }
 392
 393
 394 template<class _MI, class _V>
 395 class ValOpIterator : public std::forward_iterator<_V, ptrdiff_t> {
 396 private:
 397   unsigned int i;
 398   int resultPos;
 399   _MI* minstr;
 400
 401   inline void   skipToNextVal() {
 402     while (i < minstr->getNumOperands() &&
 403            ! ((minstr->operands[i].opType == MachineOperand::MO_VirtualRegister
 404                || minstr->operands[i].opType == MachineOperand::MO_CCRegister)
 405               && minstr->operands[i].value != NULL))
 406       ++i;
 407   }
 408
 409 public:
 410   typedef ValOpIterator<_MI, _V> _Self;
 411
 412   inline ValOpIterator(_MI* _minstr) : i(0), minstr(_minstr) {
 413     resultPos = TargetInstrDescriptors[minstr->opCode].resultPos;
 414     skipToNextVal();
 415   };
 416
 417   inline _V*    operator*()  const { return minstr->getOperand(i).getVRegValue();}
 418
 419   const MachineOperand & getMachineOperand() const { return minstr->getOperand(i);  }
 420
 421   inline _V*    operator->() const { return operator*(); }
 422   //  inline bool       isDef   ()   const { return (((int) i) == resultPos); }
 423
 424   inline bool   isDef   ()   const { return minstr->getOperand(i).isDef; }
 425   inline bool   done    ()   const { return (i == minstr->getNumOperands()); }
 426
 427   inline _Self& operator++()       { i++; skipToNextVal(); return *this; }
 428   inline _Self  operator++(int)    { _Self tmp = *this; ++*this; return tmp; }
 429 };
 430
 431
 432 //---------------------------------------------------------------------------
 433 // class MachineCodeForVMInstr
 434 //
 435 // Purpose:
 436 //   Representation of the sequence of machine instructions created
 437 //   for a single VM instruction.  Additionally records information
 438 //   about hidden and implicit values used by the machine instructions:
 439 //   about hidden values used by the machine instructions:
 440 //
 441 //   "Temporary values" are intermediate values used in the machine
 442 //   instruction sequence, but not in the VM instruction
 443 //   Note that such values should be treated as pure SSA values with
 444 //   no interpretation of their operands (i.e., as a TmpInstruction
 445 //   object which actually represents such a value).
 446 //
 447 //   (2) "Implicit uses" are values used in the VM instruction but not in
 448 //       the machine instruction sequence
 449 //
 450 //---------------------------------------------------------------------------
 451
 452 class MachineCodeForVMInstr: public vector<MachineInstr*>
 453 {
 454 private:
 455   vector<Value*> tempVec;         // used by m/c instr but not VM instr
 456
 457 public:
 458   /*ctor*/      MachineCodeForVMInstr   ()      {}
 459   /*ctor*/      ~MachineCodeForVMInstr  ();
 460
 461   const vector<Value*>& getTempValues  () const { return tempVec; }
 462         vector<Value*>& getTempValues  ()       { return tempVec; }
 463
 464   void    addTempValue  (Value* val)            { tempVec.push_back(val); }
 465
 466   // dropAllReferences() - This function drops all references within
 467   // temporary (hidden) instructions created in implementing the original
 468   // VM intruction.  This ensures there are no remaining "uses" within
 469   // these hidden instructions, before the values of a method are freed.
 470   //
 471   // Make this inline because it has to be called from class Instruction
 472   // and inlining it avoids a serious circurality in link order.
 473   inline void dropAllReferences() {
 474     for (unsigned i=0, N=tempVec.size(); i < N; i++)
 475       if (Instruction *I = dyn_cast<Instruction>(tempVec[i]))
 476         I->dropAllReferences();
 477   }
 478 };
 479
 480 inline
 481 MachineCodeForVMInstr::~MachineCodeForVMInstr()
 482 {
 483   // Free the Value objects created to hold intermediate values
 484   for (unsigned i=0, N=tempVec.size(); i < N; i++)
 485     delete tempVec[i];
 486
 487   // Free the MachineInstr objects allocated, if any.
 488   for (unsigned i=0, N=this->size(); i < N; i++)
 489     delete (*this)[i];
 490 }
 491
 492
 493 //---------------------------------------------------------------------------
 494 // class MachineCodeForBasicBlock
 495 //
 496 // Purpose:
 497 //   Representation of the sequence of machine instructions created
 498 //   for a basic block.
 499 //---------------------------------------------------------------------------
 500
 501
 502 class MachineCodeForBasicBlock: public vector<MachineInstr*> {
 503 public:
 504   typedef vector<MachineInstr*>::iterator iterator;
 505   typedef vector<const MachineInstr*>::const_iterator const_iterator;
 506 };
 507
 508
 509 //---------------------------------------------------------------------------
 510 // class MachineCodeForMethod
 511 //
 512 // Purpose:
 513 //   Collect native machine code information for a method.
 514 //   This allows target-specific information about the generated code
 515 //   to be stored with each method.
 516 //---------------------------------------------------------------------------
 517
 518
 519
 520 class MachineCodeForMethod: public NonCopyable, private Annotation {
 521 private:
 522   static AnnotationID AID;
 523 private:
 524   const Method* method;
 525   bool          compiledAsLeaf;
 526   unsigned      staticStackSize;
 527   unsigned      automaticVarsSize;
 528   unsigned      regSpillsSize;
 529   unsigned      currentOptionalArgsSize;
 530   unsigned      maxOptionalArgsSize;
 531   unsigned      currentTmpValuesSize;
 532   hash_set<const ConstPoolVal*> constantsForConstPool;
 533   hash_map<const Value*, int> offsets;
 534   // hash_map<const Value*, int> offsetsFromSP;
 535
 536 public:
 537   /*ctor*/      MachineCodeForMethod(const Method* method,
 538                                      const TargetMachine& target);
 539
 540   // The next two methods are used to construct and to retrieve
 541   // the MachineCodeForMethod object for the given method.
 542   // construct() -- Allocates and initializes for a given method and target
 543   // get()       -- Returns a handle to the object.
 544   //                This should not be called before "construct()"
 545   //                for a given Method.
 546   //
 547   inline static MachineCodeForMethod& construct(const Method* method,
 548                                                 const TargetMachine& target)
 549   {
 550     assert(method->getAnnotation(MachineCodeForMethod::AID) == NULL &&
 551            "Object already exists for this method!");
 552     MachineCodeForMethod* mcInfo = new MachineCodeForMethod(method, target);
 553     method->addAnnotation(mcInfo);
 554     return *mcInfo;
 555   }
 556
 557   inline static MachineCodeForMethod& get(const Method* method)
 558   {
 559     MachineCodeForMethod* mc = (MachineCodeForMethod*)
 560       method->getAnnotation(MachineCodeForMethod::AID);
 561     assert(mc && "Call construct() method first to allocate the object");
 562     return *mc;
 563   }
 564
 565   //
 566   // Accessors for global information about generated code for a method.
 567   //
 568   inline bool     isCompiledAsLeafMethod() const { return compiledAsLeaf; }
 569   inline unsigned getStaticStackSize()     const { return staticStackSize; }
 570   inline unsigned getAutomaticVarsSize()   const { return automaticVarsSize; }
 571   inline unsigned getRegSpillsSize()       const { return regSpillsSize; }
 572   inline unsigned getMaxOptionalArgsSize() const { return maxOptionalArgsSize;}
 573   inline unsigned getCurrentOptionalArgsSize() const
 574                                              { return currentOptionalArgsSize;}
 575   inline const hash_set<const ConstPoolVal*>&
 576                   getConstantPoolValues() const {return constantsForConstPool;}
 577
 578   //
 579   // Modifiers used during code generation
 580   //
 581   void            initializeFrameLayout    (const TargetMachine& target);
 582
 583   void            addToConstantPool        (const ConstPoolVal* constVal)
 584                                     { constantsForConstPool.insert(constVal); }
 585
 586   inline void     markAsLeafMethod()              { compiledAsLeaf = true; }
 587
 588   int             allocateLocalVar         (const TargetMachine& target,
 589                                             const Value* local,
 590                                             unsigned int size = 0);
 591
 592   int             allocateSpilledValue     (const TargetMachine& target,
 593                                             const Type* type);
 594
 595   int             allocateOptionalArg      (const TargetMachine& target,
 596                                             const Type* type);
 597
 598   void            resetOptionalArgs        (const TargetMachine& target);
 599
 600   int             pushTempValue            (const TargetMachine& target,
 601                                             unsigned int size);
 602
 603   void            popAllTempValues         (const TargetMachine& target);
 604
 605   int             getOffset                (const Value* val) const;
 606
 607   // int          getOffsetFromFP       (const Value* val) const;
 608
 609   void            dump                     () const;
 610
 611 private:
 612   inline void     incrementAutomaticVarsSize(int incr) {
 613     automaticVarsSize+= incr;
 614     staticStackSize += incr;
 615   }
 616   inline void     incrementRegSpillsSize(int incr) {
 617     regSpillsSize+= incr;
 618     staticStackSize += incr;
 619   }
 620   inline void     incrementCurrentOptionalArgsSize(int incr) {
 621     currentOptionalArgsSize+= incr;     // stack size already includes this!
 622   }
 623 };
 624
 625
 626 //---------------------------------------------------------------------------
 627 // Debugging Support
 628 //---------------------------------------------------------------------------
 629
 630
 631 ostream& operator<<             (ostream& os, const MachineInstr& minstr);
 632
 633
 634 ostream& operator<<             (ostream& os, const MachineOperand& mop);
 635
 636
 637 void    PrintMachineInstructions(const Method *method);
 638
 639
 640 //**************************************************************************/
 641
 642 #endif