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