lib/Target/SparcV9/SparcV9InstrSelection.cpp

   1 //***************************************************************************
   2 // File:
   3 //      SparcInstrSelection.cpp
   4 //
   5 // Purpose:
   6 //
   7 // History:
   8 //      7/02/01  -  Vikram Adve  -  Created
   9 //**************************************************************************/
  10
  11 #include "SparcInternals.h"
  12 #include "llvm/CodeGen/MachineInstr.h"
  13 #include "llvm/CodeGen/InstrForest.h"
  14 #include "llvm/CodeGen/InstrSelection.h"
  15 #include "llvm/Support/MathExtras.h"
  16 #include "llvm/DerivedTypes.h"
  17 #include "llvm/iTerminators.h"
  18 #include "llvm/iMemory.h"
  19 #include "llvm/iOther.h"
  20 #include "llvm/BasicBlock.h"
  21 #include "llvm/Method.h"
  22 #include "llvm/ConstPoolVals.h"
  23
  24
  25 //******************** Internal Data Declarations ************************/
  26
  27 // to be used later
  28 struct BranchPattern {
  29   bool          flipCondition; // should the sense of the test be reversed
  30   BasicBlock*   targetBB;      // which basic block to branch to
  31   MachineInstr* extraBranch;   // if neither branch is fall-through, then this
  32                                // BA must be inserted after the cond'l one
  33 };
  34
  35 //************************* Forward Declarations ***************************/
  36
  37
  38 static MachineOpCode ChooseBprInstruction   (const InstructionNode* instrNode);
  39
  40 static MachineOpCode ChooseBccInstruction   (const InstructionNode* instrNode,
  41                                              bool& isFPBranch);
  42
  43 static MachineOpCode ChooseBpccInstruction  (const InstructionNode* instrNode,
  44                                              const BinaryOperator* setCCInst);
  45
  46 static MachineOpCode ChooseBFpccInstruction (const InstructionNode* instrNode,
  47                                              const BinaryOperator* setCCInst);
  48
  49 static MachineOpCode ChooseMovFpccInstruction(const InstructionNode*);
  50
  51 static MachineOpCode ChooseMovpccAfterSub   (const InstructionNode* instrNode,
  52                                              bool& mustClearReg,
  53                                              int& valueToMove);
  54
  55 static MachineOpCode ChooseConvertToFloatInstr(const InstructionNode*,
  56                                                const Type* opType);
  57
  58 static MachineOpCode ChooseConvertToIntInstr(const InstructionNode* instrNode,
  59                                              const Type* opType);
  60
  61 static MachineOpCode ChooseAddInstruction   (const InstructionNode* instrNode);
  62
  63 static MachineOpCode ChooseSubInstruction   (const InstructionNode* instrNode);
  64
  65 static MachineOpCode ChooseFcmpInstruction  (const InstructionNode* instrNode);
  66
  67 static MachineOpCode ChooseMulInstruction   (const InstructionNode* instrNode,
  68                                              bool checkCasts);
  69
  70 static MachineOpCode ChooseDivInstruction   (const InstructionNode* instrNode);
  71
  72 static MachineOpCode ChooseLoadInstruction  (const Type* resultType);
  73
  74 static MachineOpCode ChooseStoreInstruction (const Type* valueType);
  75
  76 static void             SetOperandsForMemInstr(MachineInstr* minstr,
  77                                          const InstructionNode* vmInstrNode,
  78                                          const TargetMachine& target);
  79
  80 static void             SetMemOperands_Internal (MachineInstr* minstr,
  81                                          const InstructionNode* vmInstrNode,
  82                                          Value* ptrVal,
  83                                          Value* arrayOffsetVal,
  84                                          const vector<ConstPoolVal*>& idxVec,
  85                                          const TargetMachine& target);
  86
  87 static unsigned         FixConstantOperands(const InstructionNode* vmInstrNode,
  88                                             MachineInstr** mvec,
  89                                             unsigned numInstr,
  90                                             TargetMachine& target);
  91
  92 static MachineInstr*    MakeLoadConstInstr(Instruction* vmInstr,
  93                                            Value* val,
  94                                            TmpInstruction*& tmpReg,
  95                                            MachineInstr*& getMinstr2);
  96
  97 static void             ForwardOperand  (InstructionNode* treeNode,
  98                                          InstructionNode* parent,
  99                                          int operandNum);
 100
 101
 102 //************************ Internal Functions ******************************/
 103
 104 // Convenience function to get the value of an integer constant, for an
 105 // appropriate integer or non-integer type that can be held in an integer.
 106 // The type of the argument must be the following:
 107 //   GetConstantValueAsSignedInt: any of the above, but the value
 108 //                                must fit into a int64_t.
 109 //
 110 // isValidConstant is set to true if a valid constant was found.
 111 //
 112
 113 static int64_t GetConstantValueAsSignedInt(const Value *V,
 114                                            bool &isValidConstant) {
 115   if (!V->isConstant()) { isValidConstant = false; return 0; }
 116   isValidConstant = true;
 117
 118   if (V->getType() == Type::BoolTy)
 119     return ((ConstPoolBool*)V)->getValue();
 120   if (V->getType()->isIntegral()) {
 121     if (V->getType()->isSigned())
 122       return ((ConstPoolSInt*)V)->getValue();
 123
 124     assert(V->getType()->isUnsigned());
 125     uint64_t Val = ((ConstPoolUInt*)V)->getValue();
 126
 127     if (Val < INT64_MAX)     // then safe to cast to signed
 128       return (int64_t)Val;
 129   }
 130
 131   isValidConstant = false;
 132   return 0;
 133 }
 134
 135
 136
 137 //------------------------------------------------------------------------
 138 // External Function: ThisIsAChainRule
 139 //
 140 // Purpose:
 141 //   Check if a given BURG rule is a chain rule.
 142 //------------------------------------------------------------------------
 143
 144 extern bool
 145 ThisIsAChainRule(int eruleno)
 146 {
 147   switch(eruleno)
 148     {
 149     case 111:   // stmt:  reg
 150     case 112:   // stmt:  boolconst
 151     case 113:   // stmt:  bool
 152     case 121:
 153     case 122:
 154     case 123:
 155     case 124:
 156     case 125:
 157     case 126:
 158     case 127:
 159     case 128:
 160     case 129:
 161     case 130:
 162     case 131:
 163     case 132:
 164     case 153:
 165     case 155: return true; break;
 166
 167     default: return false; break;
 168     }
 169 }
 170
 171
 172 static inline MachineOpCode
 173 ChooseBprInstruction(const InstructionNode* instrNode)
 174 {
 175   MachineOpCode opCode;
 176
 177   Instruction* setCCInstr =
 178     ((InstructionNode*) instrNode->leftChild())->getInstruction();
 179
 180   switch(setCCInstr->getOpcode())
 181     {
 182     case Instruction::SetEQ: opCode = BRZ;   break;
 183     case Instruction::SetNE: opCode = BRNZ;  break;
 184     case Instruction::SetLE: opCode = BRLEZ; break;
 185     case Instruction::SetGE: opCode = BRGEZ; break;
 186     case Instruction::SetLT: opCode = BRLZ;  break;
 187     case Instruction::SetGT: opCode = BRGZ;  break;
 188     default:
 189       assert(0 && "Unrecognized VM instruction!");
 190       opCode = INVALID_OPCODE;
 191       break;
 192     }
 193
 194   return opCode;
 195 }
 196
 197
 198 static inline MachineOpCode
 199 ChooseBccInstruction(const InstructionNode* instrNode,
 200                      bool& isFPBranch)
 201 {
 202   InstructionNode* setCCNode = (InstructionNode*) instrNode->leftChild();
 203   BinaryOperator* setCCInstr = (BinaryOperator*) setCCNode->getInstruction();
 204   const Type* setCCType = setCCInstr->getOperand(0)->getType();
 205
 206   isFPBranch = (setCCType == Type::FloatTy || setCCType == Type::DoubleTy);
 207
 208   if (isFPBranch)
 209     return ChooseBFpccInstruction(instrNode, setCCInstr);
 210   else
 211     return ChooseBpccInstruction(instrNode, setCCInstr);
 212 }
 213
 214
 215 static inline MachineOpCode
 216 ChooseBpccInstruction(const InstructionNode* instrNode,
 217                       const BinaryOperator* setCCInstr)
 218 {
 219   MachineOpCode opCode = INVALID_OPCODE;
 220
 221   bool isSigned = setCCInstr->getOperand(0)->getType()->isSigned();
 222
 223   if (isSigned)
 224     {
 225       switch(setCCInstr->getOpcode())
 226         {
 227         case Instruction::SetEQ: opCode = BE;  break;
 228         case Instruction::SetNE: opCode = BNE; break;
 229         case Instruction::SetLE: opCode = BLE; break;
 230         case Instruction::SetGE: opCode = BGE; break;
 231         case Instruction::SetLT: opCode = BL;  break;
 232         case Instruction::SetGT: opCode = BG;  break;
 233         default:
 234           assert(0 && "Unrecognized VM instruction!");
 235           break;
 236         }
 237     }
 238   else
 239     {
 240       switch(setCCInstr->getOpcode())
 241         {
 242         case Instruction::SetEQ: opCode = BE;   break;
 243         case Instruction::SetNE: opCode = BNE;  break;
 244         case Instruction::SetLE: opCode = BLEU; break;
 245         case Instruction::SetGE: opCode = BCC;  break;
 246         case Instruction::SetLT: opCode = BCS;  break;
 247         case Instruction::SetGT: opCode = BGU;  break;
 248         default:
 249           assert(0 && "Unrecognized VM instruction!");
 250           break;
 251         }
 252     }
 253
 254   return opCode;
 255 }
 256
 257 static inline MachineOpCode
 258 ChooseBFpccInstruction(const InstructionNode* instrNode,
 259                        const BinaryOperator* setCCInstr)
 260 {
 261   MachineOpCode opCode = INVALID_OPCODE;
 262
 263   switch(setCCInstr->getOpcode())
 264     {
 265     case Instruction::SetEQ: opCode = FBE;  break;
 266     case Instruction::SetNE: opCode = FBNE; break;
 267     case Instruction::SetLE: opCode = FBLE; break;
 268     case Instruction::SetGE: opCode = FBGE; break;
 269     case Instruction::SetLT: opCode = FBL;  break;
 270     case Instruction::SetGT: opCode = FBG;  break;
 271     default:
 272       assert(0 && "Unrecognized VM instruction!");
 273       break;
 274     }
 275
 276   return opCode;
 277 }
 278
 279
 280 static inline MachineOpCode
 281 ChooseMovFpccInstruction(const InstructionNode* instrNode)
 282 {
 283   MachineOpCode opCode = INVALID_OPCODE;
 284
 285   switch(instrNode->getInstruction()->getOpcode())
 286     {
 287     case Instruction::SetEQ: opCode = MOVFE;  break;
 288     case Instruction::SetNE: opCode = MOVFNE; break;
 289     case Instruction::SetLE: opCode = MOVFLE; break;
 290     case Instruction::SetGE: opCode = MOVFGE; break;
 291     case Instruction::SetLT: opCode = MOVFL;  break;
 292     case Instruction::SetGT: opCode = MOVFG;  break;
 293     default:
 294       assert(0 && "Unrecognized VM instruction!");
 295       break;
 296     }
 297
 298   return opCode;
 299 }
 300
 301
 302 // Assumes that SUBcc v1, v2 -> v3 has been executed.
 303 // In most cases, we want to clear v3 and then follow it by instruction
 304 // MOVcc 1 -> v3.
 305 // Set mustClearReg=false if v3 need not be cleared before conditional move.
 306 // Set valueToMove=0 if we want to conditionally move 0 instead of 1
 307 //                      (i.e., we want to test inverse of a condition)
 308 //
 309 //
 310 static MachineOpCode
 311 ChooseMovpccAfterSub(const InstructionNode* instrNode,
 312                      bool& mustClearReg,
 313                      int& valueToMove)
 314 {
 315   MachineOpCode opCode = INVALID_OPCODE;
 316   mustClearReg = true;
 317   valueToMove = 1;
 318
 319   switch(instrNode->getInstruction()->getOpcode())
 320     {
 321     case Instruction::SetEQ: opCode = MOVNE; mustClearReg = false;
 322                                              valueToMove = 0; break;
 323     case Instruction::SetLE: opCode = MOVLE; break;
 324     case Instruction::SetGE: opCode = MOVGE; break;
 325     case Instruction::SetLT: opCode = MOVL;  break;
 326     case Instruction::SetGT: opCode = MOVG;  break;
 327
 328     case Instruction::SetNE: assert(0 && "No move required!");
 329
 330     default:
 331       assert(0 && "Unrecognized VM instruction!");
 332       break;
 333     }
 334
 335   return opCode;
 336 }
 337
 338
 339 static inline MachineOpCode
 340 ChooseConvertToFloatInstr(const InstructionNode* instrNode,
 341                           const Type* opType)
 342 {
 343   MachineOpCode opCode = INVALID_OPCODE;
 344
 345   switch(instrNode->getOpLabel())
 346     {
 347     case ToFloatTy:
 348       if (opType == Type::SByteTy || opType == Type::ShortTy || opType == Type::IntTy)
 349         opCode = FITOS;
 350       else if (opType == Type::LongTy)
 351         opCode = FXTOS;
 352       else if (opType == Type::DoubleTy)
 353         opCode = FDTOS;
 354       else if (opType == Type::FloatTy)
 355         ;
 356       else
 357         assert(0 && "Cannot convert this type to FLOAT on SPARC");
 358       break;
 359
 360     case ToDoubleTy:
 361       if (opType == Type::SByteTy || opType == Type::ShortTy || opType == Type::IntTy)
 362         opCode = FITOD;
 363       else if (opType == Type::LongTy)
 364         opCode = FXTOD;
 365       else if (opType == Type::FloatTy)
 366         opCode = FSTOD;
 367       else if (opType == Type::DoubleTy)
 368         ;
 369       else
 370         assert(0 && "Cannot convert this type to DOUBLE on SPARC");
 371       break;
 372
 373     default:
 374       break;
 375     }
 376
 377   return opCode;
 378 }
 379
 380 static inline MachineOpCode
 381 ChooseConvertToIntInstr(const InstructionNode* instrNode,
 382                         const Type* opType)
 383 {
 384   MachineOpCode opCode = INVALID_OPCODE;;
 385
 386   int instrType = (int) instrNode->getOpLabel();
 387
 388   if (instrType == ToSByteTy || instrType == ToShortTy || instrType == ToIntTy)
 389     {
 390       switch (opType->getPrimitiveID())
 391         {
 392         case Type::FloatTyID:   opCode = FSTOI; break;
 393         case Type::DoubleTyID:  opCode = FDTOI; break;
 394         default:
 395           assert(0 && "Non-numeric non-bool type cannot be converted to Int");
 396           break;
 397         }
 398     }
 399   else if (instrType == ToLongTy)
 400     {
 401       switch (opType->getPrimitiveID())
 402         {
 403         case Type::FloatTyID:   opCode = FSTOX; break;
 404         case Type::DoubleTyID:  opCode = FDTOX; break;
 405         default:
 406           assert(0 && "Non-numeric non-bool type cannot be converted to Long");
 407           break;
 408         }
 409     }
 410   else
 411       assert(0 && "Should not get here, Mo!");
 412
 413   return opCode;
 414 }
 415
 416
 417 static inline MachineOpCode
 418 ChooseAddInstruction(const InstructionNode* instrNode)
 419 {
 420   MachineOpCode opCode = INVALID_OPCODE;
 421
 422   const Type* resultType = instrNode->getInstruction()->getType();
 423
 424   if (resultType->isIntegral() ||
 425       resultType->isPointerType() ||
 426       resultType->isMethodType() ||
 427       resultType->isLabelType())
 428     {
 429       opCode = ADD;
 430     }
 431   else
 432     {
 433       Value* operand = ((InstrTreeNode*) instrNode->leftChild())->getValue();
 434       switch(operand->getType()->getPrimitiveID())
 435         {
 436         case Type::FloatTyID:  opCode = FADDS; break;
 437         case Type::DoubleTyID: opCode = FADDD; break;
 438         default: assert(0 && "Invalid type for ADD instruction"); break;
 439         }
 440     }
 441
 442   return opCode;
 443 }
 444
 445
 446 static inline MachineInstr*
 447 CreateMovFloatInstruction(const InstructionNode* instrNode,
 448                           const Type* resultType)
 449 {
 450   MachineInstr* minstr = new MachineInstr((resultType == Type::FloatTy)
 451                                           ? FMOVS : FMOVD);
 452   minstr->SetMachineOperand(0, MachineOperand::MO_VirtualRegister,
 453                             instrNode->leftChild()->getValue());
 454   minstr->SetMachineOperand(1, MachineOperand::MO_VirtualRegister,
 455                             instrNode->getValue());
 456   return minstr;
 457 }
 458
 459 static inline MachineInstr*
 460 CreateAddConstInstruction(const InstructionNode* instrNode)
 461 {
 462   MachineInstr* minstr = NULL;
 463
 464   Value* constOp = ((InstrTreeNode*) instrNode->rightChild())->getValue();
 465   assert(constOp->isConstant());
 466
 467   // Cases worth optimizing are:
 468   // (1) Add with 0 for float or double: use an FMOV of appropriate type,
 469   //     instead of an FADD (1 vs 3 cycles).  There is no integer MOV.
 470   //
 471   const Type* resultType = instrNode->getInstruction()->getType();
 472
 473   if (resultType == Type::FloatTy || resultType == Type::DoubleTy) {
 474     double dval = ((ConstPoolFP*) constOp)->getValue();
 475     if (dval == 0.0)
 476       minstr = CreateMovFloatInstruction(instrNode, resultType);
 477   }
 478
 479   return minstr;
 480 }
 481
 482
 483 static inline MachineOpCode
 484 ChooseSubInstruction(const InstructionNode* instrNode)
 485 {
 486   MachineOpCode opCode = INVALID_OPCODE;
 487
 488   const Type* resultType = instrNode->getInstruction()->getType();
 489
 490   if (resultType->isIntegral() ||
 491       resultType->isPointerType())
 492     {
 493       opCode = SUB;
 494     }
 495   else
 496     {
 497       Value* operand = ((InstrTreeNode*) instrNode->leftChild())->getValue();
 498       switch(operand->getType()->getPrimitiveID())
 499         {
 500         case Type::FloatTyID:  opCode = FSUBS; break;
 501         case Type::DoubleTyID: opCode = FSUBD; break;
 502         default: assert(0 && "Invalid type for SUB instruction"); break;
 503         }
 504     }
 505
 506   return opCode;
 507 }
 508
 509
 510 static inline MachineInstr*
 511 CreateSubConstInstruction(const InstructionNode* instrNode)
 512 {
 513   MachineInstr* minstr = NULL;
 514
 515   Value* constOp = ((InstrTreeNode*) instrNode->rightChild())->getValue();
 516   assert(constOp->isConstant());
 517
 518   // Cases worth optimizing are:
 519   // (1) Sub with 0 for float or double: use an FMOV of appropriate type,
 520   //     instead of an FSUB (1 vs 3 cycles).  There is no integer MOV.
 521   //
 522   const Type* resultType = instrNode->getInstruction()->getType();
 523
 524   if (resultType == Type::FloatTy ||
 525       resultType == Type::DoubleTy)
 526     {
 527       double dval = ((ConstPoolFP*) constOp)->getValue();
 528       if (dval == 0.0)
 529         minstr = CreateMovFloatInstruction(instrNode, resultType);
 530     }
 531
 532   return minstr;
 533 }
 534
 535
 536 static inline MachineOpCode
 537 ChooseFcmpInstruction(const InstructionNode* instrNode)
 538 {
 539   MachineOpCode opCode = INVALID_OPCODE;
 540
 541   Value* operand = ((InstrTreeNode*) instrNode->leftChild())->getValue();
 542   switch(operand->getType()->getPrimitiveID()) {
 543   case Type::FloatTyID:  opCode = FCMPS; break;
 544   case Type::DoubleTyID: opCode = FCMPD; break;
 545   default: assert(0 && "Invalid type for FCMP instruction"); break;
 546   }
 547
 548   return opCode;
 549 }
 550
 551
 552 // Assumes that leftArg and rightArg are both cast instructions.
 553 //
 554 static inline bool
 555 BothFloatToDouble(const InstructionNode* instrNode)
 556 {
 557   InstrTreeNode* leftArg = instrNode->leftChild();
 558   InstrTreeNode* rightArg = instrNode->rightChild();
 559   InstrTreeNode* leftArgArg = leftArg->leftChild();
 560   InstrTreeNode* rightArgArg = rightArg->leftChild();
 561   assert(leftArg->getValue()->getType() == rightArg->getValue()->getType());
 562
 563   // Check if both arguments are floats cast to double
 564   return (leftArg->getValue()->getType() == Type::DoubleTy &&
 565           leftArgArg->getValue()->getType() == Type::FloatTy &&
 566           rightArgArg->getValue()->getType() == Type::FloatTy);
 567 }
 568
 569
 570 static inline MachineOpCode
 571 ChooseMulInstruction(const InstructionNode* instrNode,
 572                      bool checkCasts)
 573 {
 574   MachineOpCode opCode = INVALID_OPCODE;
 575
 576   if (checkCasts && BothFloatToDouble(instrNode))
 577     {
 578       return opCode = FSMULD;
 579     }
 580   // else fall through and use the regular multiply instructions
 581
 582   const Type* resultType = instrNode->getInstruction()->getType();
 583
 584   if (resultType->isIntegral())
 585     {
 586       opCode = MULX;
 587     }
 588   else
 589     {
 590       switch(instrNode->leftChild()->getValue()->getType()->getPrimitiveID())
 591         {
 592         case Type::FloatTyID:  opCode = FMULS; break;
 593         case Type::DoubleTyID: opCode = FMULD; break;
 594         default: assert(0 && "Invalid type for MUL instruction"); break;
 595         }
 596     }
 597
 598   return opCode;
 599 }
 600
 601
 602 static inline MachineInstr*
 603 CreateIntNegInstruction(Value* vreg)
 604 {
 605   MachineInstr* minstr = new MachineInstr(SUB);
 606   minstr->SetMachineOperand(0, /*regNum %g0*/(unsigned int) 0);
 607   minstr->SetMachineOperand(1, MachineOperand::MO_VirtualRegister, vreg);
 608   minstr->SetMachineOperand(2, MachineOperand::MO_VirtualRegister, vreg);
 609   return minstr;
 610 }
 611
 612
 613 static inline MachineInstr*
 614 CreateMulConstInstruction(const InstructionNode* instrNode,
 615                           MachineInstr*& getMinstr2)
 616 {
 617   MachineInstr* minstr = NULL;
 618   getMinstr2 = NULL;
 619   bool needNeg = false;
 620
 621   Value* constOp = ((InstrTreeNode*) instrNode->rightChild())->getValue();
 622   assert(constOp->isConstant());
 623
 624   // Cases worth optimizing are:
 625   // (1) Multiply by 0 or 1 for any type: replace with copy (ADD or FMOV)
 626   // (2) Multiply by 2^x for integer types: replace with Shift
 627   //
 628   const Type* resultType = instrNode->getInstruction()->getType();
 629
 630   if (resultType->isIntegral())
 631     {
 632       unsigned pow;
 633       bool isValidConst;
 634       int64_t C = GetConstantValueAsSignedInt(constOp, isValidConst);
 635       if (isValidConst)
 636         {
 637           bool needNeg = false;
 638           if (C < 0)
 639             {
 640               needNeg = true;
 641               C = -C;
 642             }
 643
 644           if (C == 0 || C == 1)
 645             {
 646               minstr = new MachineInstr(ADD);
 647
 648               if (C == 0)
 649                 minstr->SetMachineOperand(0, /*regNum %g0*/ (unsigned int) 0);
 650               else
 651                 minstr->SetMachineOperand(0,MachineOperand::MO_VirtualRegister,
 652                                           instrNode->leftChild()->getValue());
 653               minstr->SetMachineOperand(1, /*regNum %g0*/ (unsigned int) 0);
 654             }
 655           else if (IsPowerOf2(C, pow))
 656             {
 657               minstr = new MachineInstr((resultType == Type::LongTy)
 658                                         ? SLLX : SLL);
 659               minstr->SetMachineOperand(0, MachineOperand::MO_VirtualRegister,
 660                                            instrNode->leftChild()->getValue());
 661               minstr->SetMachineOperand(1, MachineOperand::MO_UnextendedImmed,
 662                                            pow);
 663             }
 664
 665           if (minstr && needNeg)
 666             { // insert <reg = SUB 0, reg> after the instr to flip the sign
 667               getMinstr2 = CreateIntNegInstruction(instrNode->getValue());
 668             }
 669         }
 670     }
 671   else
 672     {
 673       if (resultType == Type::FloatTy ||
 674           resultType == Type::DoubleTy)
 675         {
 676           bool isValidConst;
 677           double dval = ((ConstPoolFP*) constOp)->getValue();
 678
 679           if (isValidConst)
 680             {
 681               if (dval == 0)
 682                 {
 683                   minstr = new MachineInstr((resultType == Type::FloatTy)
 684                                             ? FITOS : FITOD);
 685                   minstr->SetMachineOperand(0, /*regNum %g0*/(unsigned int) 0);
 686                 }
 687               else if (fabs(dval) == 1)
 688                 {
 689                   bool needNeg = (dval < 0);
 690
 691                   MachineOpCode opCode = needNeg
 692                     ? (resultType == Type::FloatTy? FNEGS : FNEGD)
 693                     : (resultType == Type::FloatTy? FMOVS : FMOVD);
 694
 695                   minstr = new MachineInstr(opCode);
 696                   minstr->SetMachineOperand(0,
 697                                            MachineOperand::MO_VirtualRegister,
 698                                            instrNode->leftChild()->getValue());
 699                 }
 700             }
 701         }
 702     }
 703
 704   if (minstr != NULL)
 705     minstr->SetMachineOperand(2, MachineOperand::MO_VirtualRegister,
 706                               instrNode->getValue());
 707
 708   return minstr;
 709 }
 710
 711
 712 static inline MachineOpCode
 713 ChooseDivInstruction(const InstructionNode* instrNode)
 714 {
 715   MachineOpCode opCode = INVALID_OPCODE;
 716
 717   const Type* resultType = instrNode->getInstruction()->getType();
 718
 719   if (resultType->isIntegral())
 720     {
 721       opCode = resultType->isSigned()? SDIVX : UDIVX;
 722     }
 723   else
 724     {
 725       Value* operand = ((InstrTreeNode*) instrNode->leftChild())->getValue();
 726       switch(operand->getType()->getPrimitiveID())
 727         {
 728         case Type::FloatTyID:  opCode = FDIVS; break;
 729         case Type::DoubleTyID: opCode = FDIVD; break;
 730         default: assert(0 && "Invalid type for DIV instruction"); break;
 731         }
 732     }
 733
 734   return opCode;
 735 }
 736
 737
 738 static inline MachineInstr*
 739 CreateDivConstInstruction(const InstructionNode* instrNode,
 740                           MachineInstr*& getMinstr2)
 741 {
 742   MachineInstr* minstr = NULL;
 743   getMinstr2 = NULL;
 744
 745   Value* constOp = ((InstrTreeNode*) instrNode->rightChild())->getValue();
 746   assert(constOp->isConstant());
 747
 748   // Cases worth optimizing are:
 749   // (1) Divide by 1 for any type: replace with copy (ADD or FMOV)
 750   // (2) Divide by 2^x for integer types: replace with SR[L or A]{X}
 751   //
 752   const Type* resultType = instrNode->getInstruction()->getType();
 753
 754   if (resultType->isIntegral())
 755     {
 756       unsigned pow;
 757       bool isValidConst;
 758       int64_t C = GetConstantValueAsSignedInt(constOp, isValidConst);
 759       if (isValidConst)
 760         {
 761           bool needNeg = false;
 762           if (C < 0)
 763             {
 764               needNeg = true;
 765               C = -C;
 766             }
 767
 768           if (C == 1)
 769             {
 770               minstr = new MachineInstr(ADD);
 771               minstr->SetMachineOperand(0,MachineOperand::MO_VirtualRegister,
 772                                           instrNode->leftChild()->getValue());
 773               minstr->SetMachineOperand(1, /*regNum %g0*/ (unsigned int) 0);
 774             }
 775           else if (IsPowerOf2(C, pow))
 776             {
 777               MachineOpCode opCode= ((resultType->isSigned())
 778                                      ? (resultType==Type::LongTy)? SRAX : SRA
 779                                      : (resultType==Type::LongTy)? SRLX : SRL);
 780               minstr = new MachineInstr(opCode);
 781               minstr->SetMachineOperand(0, MachineOperand::MO_VirtualRegister,
 782                                            instrNode->leftChild()->getValue());
 783               minstr->SetMachineOperand(1, MachineOperand::MO_UnextendedImmed,
 784                                            pow);
 785             }
 786
 787           if (minstr && needNeg)
 788             { // insert <reg = SUB 0, reg> after the instr to flip the sign
 789               getMinstr2 = CreateIntNegInstruction(instrNode->getValue());
 790             }
 791         }
 792     }
 793   else
 794     {
 795       if (resultType == Type::FloatTy ||
 796           resultType == Type::DoubleTy)
 797         {
 798           bool isValidConst;
 799           double dval = ((ConstPoolFP*) constOp)->getValue();
 800
 801           if (isValidConst && fabs(dval) == 1)
 802             {
 803               bool needNeg = (dval < 0);
 804
 805               MachineOpCode opCode = needNeg
 806                 ? (resultType == Type::FloatTy? FNEGS : FNEGD)
 807                 : (resultType == Type::FloatTy? FMOVS : FMOVD);
 808
 809               minstr = new MachineInstr(opCode);
 810               minstr->SetMachineOperand(0, MachineOperand::MO_VirtualRegister,
 811                                            instrNode->leftChild()->getValue());
 812             }
 813         }
 814     }
 815
 816   if (minstr != NULL)
 817     minstr->SetMachineOperand(2, MachineOperand::MO_VirtualRegister,
 818                               instrNode->getValue());
 819
 820   return minstr;
 821 }
 822
 823
 824 static inline MachineOpCode
 825 ChooseLoadInstruction(const Type* resultType)
 826 {
 827   MachineOpCode opCode = INVALID_OPCODE;
 828
 829   switch (resultType->getPrimitiveID())
 830     {
 831     case Type::BoolTyID:        opCode = LDUB; break;
 832     case Type::UByteTyID:       opCode = LDUB; break;
 833     case Type::SByteTyID:       opCode = LDSB; break;
 834     case Type::UShortTyID:      opCode = LDUH; break;
 835     case Type::ShortTyID:       opCode = LDSH; break;
 836     case Type::UIntTyID:        opCode = LDUW; break;
 837     case Type::IntTyID:         opCode = LDSW; break;
 838     case Type::ULongTyID:
 839     case Type::LongTyID:        opCode = LDX;  break;
 840     case Type::FloatTyID:       opCode = LD;   break;
 841     case Type::DoubleTyID:      opCode = LDD;  break;
 842     default: assert(0 && "Invalid type for Load instruction"); break;
 843     }
 844
 845   return opCode;
 846 }
 847
 848
 849 static inline MachineOpCode
 850 ChooseStoreInstruction(const Type* valueType)
 851 {
 852   MachineOpCode opCode = INVALID_OPCODE;
 853
 854   switch (valueType->getPrimitiveID())
 855     {
 856     case Type::BoolTyID:
 857     case Type::UByteTyID:
 858     case Type::SByteTyID:       opCode = STB; break;
 859     case Type::UShortTyID:
 860     case Type::ShortTyID:       opCode = STH; break;
 861     case Type::UIntTyID:
 862     case Type::IntTyID:         opCode = STW; break;
 863     case Type::ULongTyID:
 864     case Type::LongTyID:        opCode = STX;  break;
 865     case Type::FloatTyID:       opCode = ST;   break;
 866     case Type::DoubleTyID:      opCode = STD;  break;
 867     default: assert(0 && "Invalid type for Store instruction"); break;
 868     }
 869
 870   return opCode;
 871 }
 872
 873
 874 //------------------------------------------------------------------------
 875 // Function SetOperandsForMemInstr
 876 //
 877 // Choose addressing mode for the given load or store instruction.
 878 // Use [reg+reg] if it is an indexed reference, and the index offset is
 879 //               not a constant or if it cannot fit in the offset field.
 880 // Use [reg+offset] in all other cases.
 881 //
 882 // This assumes that all array refs are "lowered" to one of these forms:
 883 //      %x = load (subarray*) ptr, constant     ; single constant offset
 884 //      %x = load (subarray*) ptr, offsetVal    ; single non-constant offset
 885 // Generally, this should happen via strength reduction + LICM.
 886 // Also, strength reduction should take care of using the same register for
 887 // the loop index variable and an array index, when that is profitable.
 888 //------------------------------------------------------------------------
 889
 890 static void
 891 SetOperandsForMemInstr(MachineInstr* minstr,
 892                        const InstructionNode* vmInstrNode,
 893                        const TargetMachine& target)
 894 {
 895   MemAccessInst* memInst = (MemAccessInst*) vmInstrNode->getInstruction();
 896
 897   // Variables to hold the index vector, ptr value, and offset value.
 898   // The major work here is to extract these for all 3 instruction types
 899   // and then call the common function SetMemOperands_Internal().
 900   //
 901   const vector<ConstPoolVal*>* idxVec = & memInst->getIndexVec();
 902   vector<ConstPoolVal*>* newIdxVec = NULL;
 903   Value* ptrVal;
 904   Value* arrayOffsetVal = NULL;
 905
 906   // Test if a GetElemPtr instruction is being folded into this mem instrn.
 907   // If so, it will be in the left child for Load and GetElemPtr,
 908   // and in the right child for Store instructions.
 909   //
 910   InstrTreeNode* ptrChild = (vmInstrNode->getOpLabel() == Instruction::Store
 911                              ? vmInstrNode->rightChild()
 912                              : vmInstrNode->leftChild());
 913
 914   if (ptrChild->getOpLabel() == Instruction::GetElementPtr ||
 915       ptrChild->getOpLabel() == GetElemPtrIdx)
 916     {
 917       // There is a GetElemPtr instruction and there may be a chain of
 918       // more than one.  Use the pointer value of the last one in the chain.
 919       // Fold the index vectors from the entire chain and from the mem
 920       // instruction into one single index vector.
 921       // Finally, we never fold for an array instruction so make that NULL.
 922
 923       newIdxVec = new vector<ConstPoolVal*>;
 924       ptrVal = FoldGetElemChain((InstructionNode*) ptrChild, *newIdxVec);
 925
 926       newIdxVec->insert(newIdxVec->end(), idxVec->begin(), idxVec->end());
 927       idxVec = newIdxVec;
 928
 929       assert(! ((PointerType*)ptrVal->getType())->getValueType()->isArrayType()
 930              && "GetElemPtr cannot be folded into array refs in selection");
 931     }
 932   else
 933     {
 934       // There is no GetElemPtr instruction.
 935       // Use the pointer value and the index vector from the Mem instruction.
 936       // If it is an array reference, get the array offset value.
 937       //
 938       ptrVal = memInst->getPtrOperand();
 939
 940       const Type* opType =
 941         ((const PointerType*) ptrVal->getType())->getValueType();
 942       if (opType->isArrayType())
 943         {
 944           assert((memInst->getNumOperands()
 945                   == (unsigned) 1 + memInst->getFirstOffsetIdx())
 946                  && "Array refs must be lowered before Instruction Selection");
 947
 948           arrayOffsetVal = memInst->getOperand(memInst->getFirstOffsetIdx());
 949         }
 950     }
 951
 952   SetMemOperands_Internal(minstr, vmInstrNode, ptrVal, arrayOffsetVal,
 953                           *idxVec, target);
 954
 955   if (newIdxVec != NULL)
 956     delete newIdxVec;
 957 }
 958
 959
 960 static void
 961 SetMemOperands_Internal(MachineInstr* minstr,
 962                         const InstructionNode* vmInstrNode,
 963                         Value* ptrVal,
 964                         Value* arrayOffsetVal,
 965                         const vector<ConstPoolVal*>& idxVec,
 966                         const TargetMachine& target)
 967 {
 968   MemAccessInst* memInst = (MemAccessInst*) vmInstrNode->getInstruction();
 969
 970   // Initialize so we default to storing the offset in a register.
 971   int64_t smallConstOffset;
 972   Value* valueForRegOffset = NULL;
 973   MachineOperand::MachineOperandType offsetOpType =MachineOperand::MO_VirtualRegister;
 974
 975   // Check if there is an index vector and if so, if it translates to
 976   // a small enough constant to fit in the immediate-offset field.
 977   //
 978   if (idxVec.size() > 0)
 979     {
 980       bool isConstantOffset = false;
 981       unsigned offset;
 982
 983       const PointerType* ptrType = (PointerType*) ptrVal->getType();
 984
 985       if (ptrType->getValueType()->isStructType())
 986         {
 987           // the offset is always constant for structs
 988           isConstantOffset = true;
 989
 990           // Compute the offset value using the index vector
 991           offset = target.DataLayout.getIndexedOffset(ptrType, idxVec);
 992         }
 993       else
 994         {
 995           // It must be an array ref.  Check if the offset is a constant,
 996           // and that the indexing has been lowered to a single offset.
 997           //
 998           assert(ptrType->getValueType()->isArrayType());
 999           assert(arrayOffsetVal != NULL
1000                  && "Expect to be given Value* for array offsets");
1001
1002           if (ConstPoolVal *CPV = arrayOffsetVal->castConstant())
1003             {
1004               isConstantOffset = true;  // always constant for structs
1005               assert(arrayOffsetVal->getType()->isIntegral());
1006               offset = (CPV->getType()->isSigned()
1007                         ? ((ConstPoolSInt*)CPV)->getValue()
1008                         : (int64_t) ((ConstPoolUInt*)CPV)->getValue());
1009             }
1010           else
1011             {
1012               valueForRegOffset = arrayOffsetVal;
1013             }
1014         }
1015
1016       if (isConstantOffset)
1017         {
1018           // create a virtual register for the constant
1019           valueForRegOffset = ConstPoolSInt::get(Type::IntTy, offset);
1020         }
1021     }
1022   else
1023     {
1024       offsetOpType = MachineOperand::MO_SignExtendedImmed;
1025       smallConstOffset = 0;
1026     }
1027
1028   // Operand 0 is value for STORE, ptr for LOAD or GET_ELEMENT_PTR
1029   // It is the left child in the instruction tree in all cases.
1030   Value* leftVal = vmInstrNode->leftChild()->getValue();
1031   minstr->SetMachineOperand(0, MachineOperand::MO_VirtualRegister, leftVal);
1032
1033   // Operand 1 is ptr for STORE, offset for LOAD or GET_ELEMENT_PTR
1034   // Operand 3 is offset for STORE, result reg for LOAD or GET_ELEMENT_PTR
1035   //
1036   unsigned offsetOpNum = (memInst->getOpcode() == Instruction::Store)? 2 : 1;
1037   if (offsetOpType == MachineOperand::MO_VirtualRegister)
1038     {
1039       assert(valueForRegOffset != NULL);
1040       minstr->SetMachineOperand(offsetOpNum, offsetOpType, valueForRegOffset);
1041     }
1042   else
1043     minstr->SetMachineOperand(offsetOpNum, offsetOpType, smallConstOffset);
1044
1045   if (memInst->getOpcode() == Instruction::Store)
1046     minstr->SetMachineOperand(1, MachineOperand::MO_VirtualRegister, ptrVal);
1047   else
1048     minstr->SetMachineOperand(2, MachineOperand::MO_VirtualRegister,
1049                                  vmInstrNode->getValue());
1050 }
1051
1052
1053 // Special handling for constant operands:
1054 // -- if the constant is 0, use the hardwired 0 register, if any;
1055 // -- if the constant is of float or double type but has an integer value,
1056 //    use int-to-float conversion instruction instead of generating a load;
1057 // -- if the constant fits in the IMMEDIATE field, use that field;
1058 // -- else insert instructions to put the constant into a register, either
1059 //    directly or by loading explicitly from the constant pool.
1060 //
1061 static unsigned
1062 FixConstantOperands(const InstructionNode* vmInstrNode,
1063                     MachineInstr** mvec,
1064                     unsigned numInstr,
1065                     TargetMachine& target)
1066 {
1067   static MachineInstr* loadConstVec[MAX_INSTR_PER_VMINSTR];
1068
1069   unsigned numNew = 0;
1070   Instruction* vmInstr = vmInstrNode->getInstruction();
1071
1072   for (unsigned i=0; i < numInstr; i++)
1073     {
1074       MachineInstr* minstr = mvec[i];
1075       const MachineInstrDescriptor& instrDesc =
1076         target.getInstrInfo().getDescriptor(minstr->getOpCode());
1077
1078       for (unsigned op=0; op < minstr->getNumOperands(); op++)
1079         {
1080           const MachineOperand& mop = minstr->getOperand(op);
1081
1082           // skip the result position (for efficiency below) and any other
1083           // positions already marked as not a virtual register
1084           if (instrDesc.resultPos == (int) op ||
1085               mop.getOperandType() != MachineOperand::MO_VirtualRegister ||
1086               mop.getVRegValue() == NULL)
1087             {
1088               break;
1089             }
1090
1091           Value* opValue = mop.getVRegValue();
1092
1093           if (opValue->isConstant())
1094             {
1095               unsigned int machineRegNum;
1096               int64_t immedValue;
1097               MachineOperand::MachineOperandType opType =
1098                 ChooseRegOrImmed(opValue, minstr->getOpCode(), target,
1099                                  /*canUseImmed*/ (op == 1),
1100                                  machineRegNum, immedValue);
1101
1102               if (opType == MachineOperand::MO_MachineRegister)
1103                 minstr->SetMachineOperand(op, machineRegNum);
1104               else if (opType == MachineOperand::MO_VirtualRegister)
1105                 {
1106                   // value is constant and must be loaded into a register
1107                   TmpInstruction* tmpReg;
1108                   MachineInstr* minstr2;
1109                   loadConstVec[numNew++] = MakeLoadConstInstr(vmInstr, opValue,
1110                                                               tmpReg, minstr2);
1111                   minstr->SetMachineOperand(op, opType, tmpReg);
1112                   if (minstr2 != NULL)
1113                     loadConstVec[numNew++] = minstr2;
1114                 }
1115               else
1116                 minstr->SetMachineOperand(op, opType, immedValue);
1117             }
1118         }
1119     }
1120
1121   if (numNew > 0)
1122     {
1123       // Insert the new instructions *before* the old ones by moving
1124       // the old ones over `numNew' positions (last-to-first, of course!).
1125       // We do check *after* returning that we did not exceed the vector mvec.
1126       for (int i=numInstr-1; i >= 0; i--)
1127         mvec[i+numNew] = mvec[i];
1128
1129       for (unsigned i=0; i < numNew; i++)
1130         mvec[i] = loadConstVec[i];
1131     }
1132
1133   return (numInstr + numNew);
1134 }
1135
1136
1137 static inline MachineInstr*
1138 MakeIntSetInstruction(int64_t C, bool isSigned, Value* dest)
1139 {
1140   MachineInstr* minstr;
1141   if (isSigned)
1142     {
1143       minstr = new MachineInstr(SETSW);
1144       minstr->SetMachineOperand(0, MachineOperand::MO_SignExtendedImmed, C);
1145     }
1146   else
1147     {
1148       minstr = new MachineInstr(SETUW);
1149       minstr->SetMachineOperand(0, MachineOperand::MO_UnextendedImmed, C);
1150     }
1151
1152   minstr->SetMachineOperand(1, MachineOperand::MO_VirtualRegister, dest);
1153
1154   return minstr;
1155 }
1156
1157
1158 static MachineInstr*
1159 MakeLoadConstInstr(Instruction* vmInstr,
1160                    Value* val,
1161                    TmpInstruction*& tmpReg,
1162                    MachineInstr*& getMinstr2)
1163 {
1164   assert(val->isConstant());
1165
1166   MachineInstr* minstr;
1167
1168   getMinstr2 = NULL;
1169
1170   // Create a TmpInstruction to mark the hidden register used for the constant
1171   tmpReg = new TmpInstruction(Instruction::UserOp1, val, NULL);
1172   vmInstr->getMachineInstrVec().addTempValue(tmpReg);
1173
1174   // Use a "set" instruction for known constants that can go in an integer reg.
1175   // Use a "set" instruction followed by a int-to-float conversion for known
1176   // constants that must go in a floating point reg but have an integer value.
1177   // Use a "load" instruction for all other constants, in particular,
1178   // floating point constants.
1179   //
1180   const Type* valType = val->getType();
1181
1182   if (valType->isIntegral() ||
1183       valType->isPointerType() ||
1184       valType == Type::BoolTy)
1185     {
1186       bool isValidConstant;
1187       int64_t C = GetConstantValueAsSignedInt(val, isValidConstant);
1188       assert(isValidConstant && "Unrecognized constant");
1189
1190       minstr = MakeIntSetInstruction(C, valType->isSigned(), tmpReg);
1191     }
1192   else
1193     {
1194       assert(valType == Type::FloatTy || valType == Type::DoubleTy);
1195       double dval = ((ConstPoolFP*) val)->getValue();
1196       if (dval == (int64_t) dval)
1197         {
1198           // The constant actually has an integer value, so use a
1199           // [set; int-to-float] sequence instead of a load instruction.
1200           //
1201           TmpInstruction* tmpReg2 = NULL;
1202           if (dval != 0.0)
1203             { // First, create an integer constant of the same value as dval
1204               ConstPoolSInt* ival = ConstPoolSInt::get(Type::IntTy,
1205                                                        (int64_t) dval);
1206               // Create another TmpInstruction for the hidden integer register
1207               TmpInstruction* tmpReg2 =
1208                 new TmpInstruction(Instruction::UserOp1, ival, NULL);
1209               vmInstr->getMachineInstrVec().addTempValue(tmpReg2);
1210
1211               // Create the `SET' instruction
1212               minstr = MakeIntSetInstruction((int64_t)dval, true, tmpReg2);
1213             }
1214
1215           // In which variable do we put the second instruction?
1216           MachineInstr*& instr2 = (minstr)? getMinstr2 : minstr;
1217
1218           // Create the int-to-float instruction
1219           instr2 = new MachineInstr(valType == Type::FloatTy? FITOS : FITOD);
1220
1221           if (dval == 0.0)
1222             instr2->SetMachineOperand(0, /*regNum %g0*/ (unsigned int) 0);
1223           else
1224             instr2->SetMachineOperand(0,MachineOperand::MO_VirtualRegister,
1225                                           tmpReg2);
1226
1227           instr2->SetMachineOperand(1, MachineOperand::MO_VirtualRegister,
1228                                            tmpReg);
1229         }
1230       else
1231         {
1232           // Make a Load instruction, and make `val' both the ptr value *and*
1233           // the result value, and set the offset field to 0.  Final code
1234           // generation will have to generate the base+offset for the constant.
1235           //
1236           int64_t zeroOffset = 0; // to avoid ambiguity with (Value*) 0
1237           minstr = new MachineInstr(ChooseLoadInstruction(val->getType()));
1238           minstr->SetMachineOperand(0, MachineOperand::MO_VirtualRegister,val);
1239           minstr->SetMachineOperand(1, MachineOperand::MO_SignExtendedImmed,
1240                                        zeroOffset);
1241           minstr->SetMachineOperand(2, MachineOperand::MO_VirtualRegister,
1242                                        tmpReg);
1243         }
1244     }
1245
1246   tmpReg->addMachineInstruction(minstr);
1247
1248   assert(minstr);
1249   return minstr;
1250 }
1251
1252 //
1253 // Substitute operand `operandNum' of the instruction in node `treeNode'
1254 // in place the use(s) of that instruction in node `parent'.
1255 //
1256 static void
1257 ForwardOperand(InstructionNode* treeNode,
1258                InstructionNode* parent,
1259                int operandNum)
1260 {
1261   Instruction* unusedOp = treeNode->getInstruction();
1262   Value* fwdOp = unusedOp->getOperand(operandNum);
1263   Instruction* userInstr = parent->getInstruction();
1264   MachineCodeForVMInstr& mvec = userInstr->getMachineInstrVec();
1265   for (unsigned i=0, N=mvec.size(); i < N; i++)
1266     {
1267       MachineInstr* minstr = mvec[i];
1268       for (unsigned i=0, numOps=minstr->getNumOperands(); i < numOps; i++)
1269         {
1270           const MachineOperand& mop = minstr->getOperand(i);
1271           if (mop.getOperandType() == MachineOperand::MO_VirtualRegister &&
1272               mop.getVRegValue() == unusedOp)
1273             {
1274               minstr->SetMachineOperand(i, MachineOperand::MO_VirtualRegister,
1275                                            fwdOp);
1276             }
1277         }
1278     }
1279 }
1280
1281
1282 // This function is currently unused and incomplete but will be
1283 // used if we have a linear layout of basic blocks in LLVM code.
1284 // It decides which branch should fall-through, and whether an
1285 // extra unconditional branch is needed (when neither falls through).
1286 //
1287 void
1288 ChooseBranchPattern(Instruction* vmInstr, BranchPattern& brPattern)
1289 {
1290   BranchInst* brInstr = (BranchInst*) vmInstr;
1291
1292   brPattern.flipCondition = false;
1293   brPattern.targetBB      = brInstr->getSuccessor(0);
1294   brPattern.extraBranch   = NULL;
1295
1296   assert(brInstr->getNumSuccessors() > 1 &&
1297          "Unnecessary analysis for unconditional branch");
1298
1299   assert(0 && "Fold branches in peephole optimization");
1300 }
1301
1302
1303 //******************* Externally Visible Functions *************************/
1304
1305
1306 //------------------------------------------------------------------------
1307 // External Function: GetInstructionsByRule
1308 //
1309 // Purpose:
1310 //   Choose machine instructions for the SPARC according to the
1311 //   patterns chosen by the BURG-generated parser.
1312 //------------------------------------------------------------------------
1313
1314 unsigned
1315 GetInstructionsByRule(InstructionNode* subtreeRoot,
1316                       int ruleForNode,
1317                       short* nts,
1318                       TargetMachine &target,
1319                       MachineInstr** mvec)
1320 {
1321   int numInstr = 1;                     // initialize for common case
1322   bool checkCast = false;               // initialize here to use fall-through
1323   Value *leftVal, *rightVal;
1324   const Type* opType;
1325   int nextRule;
1326   int forwardOperandNum = -1;
1327   BranchPattern brPattern;
1328   int64_t s0 = 0;                       // variables holding zero to avoid
1329   uint64_t u0 = 0;                      // overloading ambiguities below
1330
1331   mvec[0] = mvec[1] = mvec[2] = mvec[3] = NULL; // just for safety
1332
1333   switch(ruleForNode) {
1334   case 1:       // stmt:   Ret
1335   case 2:       // stmt:   RetValue(reg)
1336                 // NOTE: Prepass of register allocation is responsible
1337                 //       for moving return value to appropriate register.
1338                 // Mark the return-address register as a hidden virtual reg.
1339     {
1340     Instruction* returnReg = new TmpInstruction(Instruction::UserOp1,
1341                                         subtreeRoot->getInstruction(), NULL);
1342     subtreeRoot->getInstruction()->getMachineInstrVec().addTempValue(returnReg);
1343
1344     mvec[0] = new MachineInstr(RETURN);
1345     mvec[0]->SetMachineOperand(0,MachineOperand::MO_VirtualRegister,returnReg);
1346     mvec[0]->SetMachineOperand(1, MachineOperand::MO_SignExtendedImmed, s0);
1347
1348     returnReg->addMachineInstruction(mvec[0]);
1349
1350     mvec[numInstr++] = new MachineInstr(NOP); // delay slot
1351     break;
1352     }
1353
1354   case 3:       // stmt:   Store(reg,reg)
1355   case 4:       // stmt:   Store(reg,ptrreg)
1356     mvec[0] = new MachineInstr(ChooseStoreInstruction(subtreeRoot->leftChild()->getValue()->getType()));
1357     SetOperandsForMemInstr(mvec[0], subtreeRoot, target);
1358     break;
1359
1360   case 5:       // stmt:   BrUncond
1361     mvec[0] = new MachineInstr(BA);
1362     mvec[0]->SetMachineOperand(0, MachineOperand::MO_CCRegister, (Value*)NULL);
1363     mvec[0]->SetMachineOperand(1, MachineOperand::MO_PCRelativeDisp,
1364               ((BranchInst*) subtreeRoot->getInstruction())->getSuccessor(0));
1365
1366     // delay slot
1367     mvec[numInstr++] = new MachineInstr(NOP);
1368     break;
1369
1370   case 6:       // stmt:   BrCond(boolconst)
1371     // boolconst => boolean was computed with `%b = setCC type reg1 constant'
1372     // If the constant is ZERO, we can use the branch-on-integer-register
1373     // instructions and avoid the SUBcc instruction entirely.
1374     // Otherwise this is just the same as case 5, so just fall through.
1375     {
1376     InstrTreeNode* constNode = subtreeRoot->leftChild()->rightChild();
1377     assert(constNode && constNode->getNodeType() ==InstrTreeNode::NTConstNode);
1378     ConstPoolVal* constVal = (ConstPoolVal*) constNode->getValue();
1379     bool isValidConst;
1380
1381     if (constVal->getType()->isIntegral()
1382         && GetConstantValueAsSignedInt(constVal, isValidConst) == 0
1383         && isValidConst)
1384       {
1385         // That constant ia a zero after all...
1386         // Use the left child of the setCC instruction as the first argument!
1387         mvec[0] = new MachineInstr(ChooseBprInstruction(subtreeRoot));
1388         mvec[0]->SetMachineOperand(0, MachineOperand::MO_VirtualRegister,
1389                       subtreeRoot->leftChild()->leftChild()->getValue());
1390         mvec[0]->SetMachineOperand(1, MachineOperand::MO_PCRelativeDisp,
1391               ((BranchInst*) subtreeRoot->getInstruction())->getSuccessor(0));
1392
1393         // delay slot
1394         mvec[numInstr++] = new MachineInstr(NOP);
1395
1396         // false branch
1397         mvec[numInstr++] = new MachineInstr(BA);
1398         mvec[numInstr-1]->SetMachineOperand(0, MachineOperand::MO_CCRegister,
1399                                                 (Value*) NULL);
1400         mvec[numInstr-1]->SetMachineOperand(1, MachineOperand::MO_PCRelativeDisp, ((BranchInst*) subtreeRoot->getInstruction())->getSuccessor(1));
1401
1402         // delay slot
1403         mvec[numInstr++] = new MachineInstr(NOP);
1404
1405         break;
1406       }
1407     // ELSE FALL THROUGH
1408     }
1409
1410   case 7:       // stmt:   BrCond(bool)
1411     // bool => boolean was computed with `%b = setcc type reg1 reg2'
1412     // Need to check whether the type was a FP, signed int or unsigned int,
1413     // and check the branching condition in order to choose the branch to use.
1414     //
1415     {
1416     bool isFPBranch;
1417     mvec[0] = new MachineInstr(ChooseBccInstruction(subtreeRoot, isFPBranch));
1418     mvec[0]->SetMachineOperand(0, MachineOperand::MO_CCRegister,
1419                                   subtreeRoot->leftChild()->getValue());
1420     mvec[0]->SetMachineOperand(1, MachineOperand::MO_PCRelativeDisp,
1421               ((BranchInst*) subtreeRoot->getInstruction())->getSuccessor(0));
1422
1423     // delay slot
1424     mvec[numInstr++] = new MachineInstr(NOP);
1425
1426     // false branch
1427     mvec[numInstr++] = new MachineInstr(BA);
1428     mvec[numInstr-1]->SetMachineOperand(0, MachineOperand::MO_CCRegister,
1429                                            (Value*) NULL);
1430     mvec[numInstr-1]->SetMachineOperand(0, MachineOperand::MO_PCRelativeDisp,
1431               ((BranchInst*) subtreeRoot->getInstruction())->getSuccessor(1));
1432
1433     // delay slot
1434     mvec[numInstr++] = new MachineInstr(NOP);
1435     break;
1436     }
1437
1438   case 8:       // stmt:   BrCond(boolreg)
1439     // bool => boolean is stored in an existing register.
1440     // Just use the branch-on-integer-register instruction!
1441     //
1442     mvec[0] = new MachineInstr(BRNZ);
1443     mvec[0]->SetMachineOperand(0, MachineOperand::MO_VirtualRegister,
1444                                   subtreeRoot->leftChild()->getValue());
1445     mvec[0]->SetMachineOperand(1, MachineOperand::MO_PCRelativeDisp,
1446               ((BranchInst*) subtreeRoot->getInstruction())->getSuccessor(0));
1447
1448     // delay slot
1449     mvec[numInstr++] = new MachineInstr(NOP); // delay slot
1450
1451     // false branch
1452     mvec[numInstr++] = new MachineInstr(BA);
1453     mvec[numInstr-1]->SetMachineOperand(0, MachineOperand::MO_CCRegister,
1454                                            (Value*) NULL);
1455     mvec[numInstr-1]->SetMachineOperand(0, MachineOperand::MO_PCRelativeDisp,
1456               ((BranchInst*) subtreeRoot->getInstruction())->getSuccessor(1));
1457
1458     // delay slot
1459     mvec[numInstr++] = new MachineInstr(NOP);
1460     break;
1461
1462   case 9:       // stmt:   Switch(reg)
1463     assert(0 && "*** SWITCH instruction is not implemented yet.");
1464     numInstr = 0;
1465     break;
1466
1467   case 10:      // reg:   VRegList(reg, reg)
1468     assert(0 && "VRegList should never be the topmost non-chain rule");
1469     break;
1470
1471   case 21:      // reg:   Not(reg):     Implemented as reg = reg XOR-NOT 0
1472     mvec[0] = new MachineInstr(XNOR);
1473     mvec[0]->SetMachineOperand(0, MachineOperand::MO_VirtualRegister,
1474                                   subtreeRoot->leftChild()->getValue());
1475     mvec[0]->SetMachineOperand(1, /*regNum %g0*/ (unsigned int) 0);
1476     mvec[0]->SetMachineOperand(2, MachineOperand::MO_VirtualRegister,
1477                                  subtreeRoot->getValue());
1478     break;
1479
1480   case 22:      // reg:   ToBoolTy(reg):
1481     opType = subtreeRoot->leftChild()->getValue()->getType();
1482     assert(opType->isIntegral() || opType == Type::BoolTy);
1483     numInstr = 0;
1484     forwardOperandNum = 0;
1485     break;
1486
1487   case 23:      // reg:   ToUByteTy(reg)
1488   case 25:      // reg:   ToUShortTy(reg)
1489   case 27:      // reg:   ToUIntTy(reg)
1490   case 29:      // reg:   ToULongTy(reg)
1491     opType = subtreeRoot->leftChild()->getValue()->getType();
1492     assert(opType->isIntegral() ||
1493            opType->isPointerType() ||
1494            opType == Type::BoolTy && "Ignoring cast: illegal for other types");
1495     numInstr = 0;
1496     forwardOperandNum = 0;
1497     break;
1498
1499   case 24:      // reg:   ToSByteTy(reg)
1500   case 26:      // reg:   ToShortTy(reg)
1501   case 28:      // reg:   ToIntTy(reg)
1502   case 30:      // reg:   ToLongTy(reg)
1503     opType = subtreeRoot->leftChild()->getValue()->getType();
1504     if (opType->isIntegral() || opType == Type::BoolTy)
1505       {
1506         numInstr = 0;
1507         forwardOperandNum = 0;
1508       }
1509     else
1510       {
1511         mvec[0] =new MachineInstr(ChooseConvertToIntInstr(subtreeRoot,opType));
1512         Set2OperandsFromInstr(mvec[0], subtreeRoot, target);
1513       }
1514     break;
1515
1516   case 31:      // reg:   ToFloatTy(reg):
1517   case 32:      // reg:   ToDoubleTy(reg):
1518
1519     // If this instruction has a parent (a user) in the tree
1520     // and the user is translated as an FsMULd instruction,
1521     // then the cast is unnecessary.  So check that first.
1522     // In the future, we'll want to do the same for the FdMULq instruction,
1523     // so do the check here instead of only for ToFloatTy(reg).
1524     //
1525     if (subtreeRoot->parent() != NULL &&
1526         ((InstructionNode*) subtreeRoot->parent())->getInstruction()->getMachineInstrVec()[0]->getOpCode() == FSMULD)
1527       {
1528         numInstr = 0;
1529         forwardOperandNum = 0;
1530       }
1531     else
1532       {
1533         opType = subtreeRoot->leftChild()->getValue()->getType();
1534         MachineOpCode opCode = ChooseConvertToFloatInstr(subtreeRoot, opType);
1535         if (opCode == INVALID_OPCODE)   // no conversion needed
1536           {
1537             numInstr = 0;
1538             forwardOperandNum = 0;
1539           }
1540         else
1541           {
1542             mvec[0] = new MachineInstr(opCode);
1543             Set2OperandsFromInstr(mvec[0], subtreeRoot, target);
1544           }
1545       }
1546     break;
1547
1548   case 19:      // reg:   ToArrayTy(reg):
1549   case 20:      // reg:   ToPointerTy(reg):
1550     numInstr = 0;
1551     forwardOperandNum = 0;
1552     break;
1553
1554   case 233:     // reg:   Add(reg, Constant)
1555     mvec[0] = CreateAddConstInstruction(subtreeRoot);
1556     if (mvec[0] != NULL)
1557       break;
1558     // ELSE FALL THROUGH
1559
1560   case 33:      // reg:   Add(reg, reg)
1561     mvec[0] = new MachineInstr(ChooseAddInstruction(subtreeRoot));
1562     Set3OperandsFromInstr(mvec[0], subtreeRoot, target);
1563     break;
1564
1565   case 234:     // reg:   Sub(reg, Constant)
1566     mvec[0] = CreateSubConstInstruction(subtreeRoot);
1567     if (mvec[0] != NULL)
1568       break;
1569     // ELSE FALL THROUGH
1570
1571   case 34:      // reg:   Sub(reg, reg)
1572     mvec[0] = new MachineInstr(ChooseSubInstruction(subtreeRoot));
1573     Set3OperandsFromInstr(mvec[0], subtreeRoot, target);
1574     break;
1575
1576   case 135:     // reg:   Mul(todouble, todouble)
1577     checkCast = true;
1578     // FALL THROUGH
1579
1580   case 35:      // reg:   Mul(reg, reg)
1581     mvec[0] = new MachineInstr(ChooseMulInstruction(subtreeRoot, checkCast));
1582     Set3OperandsFromInstr(mvec[0], subtreeRoot, target);
1583     break;
1584
1585   case 335:     // reg:   Mul(todouble, todoubleConst)
1586     checkCast = true;
1587     // FALL THROUGH
1588
1589   case 235:     // reg:   Mul(reg, Constant)
1590     mvec[0] = CreateMulConstInstruction(subtreeRoot, mvec[1]);
1591     if (mvec[0] == NULL)
1592       {
1593         mvec[0]=new MachineInstr(ChooseMulInstruction(subtreeRoot, checkCast));
1594         Set3OperandsFromInstr(mvec[0], subtreeRoot, target);
1595       }
1596     else
1597       if (mvec[1] != NULL)
1598         ++numInstr;
1599     break;
1600
1601   case 236:     // reg:   Div(reg, Constant)
1602     mvec[0] = CreateDivConstInstruction(subtreeRoot, mvec[1]);
1603     if (mvec[0] != NULL)
1604       {
1605         if (mvec[1] != NULL)
1606           ++numInstr;
1607       }
1608     else
1609     // ELSE FALL THROUGH
1610
1611   case 36:      // reg:   Div(reg, reg)
1612     mvec[0] = new MachineInstr(ChooseDivInstruction(subtreeRoot));
1613     Set3OperandsFromInstr(mvec[0], subtreeRoot, target);
1614     break;
1615
1616   case  37:     // reg:   Rem(reg, reg)
1617   case 237:     // reg:   Rem(reg, Constant)
1618     assert(0 && "REM instruction unimplemented for the SPARC.");
1619     break;
1620
1621   case  38:     // reg:   And(reg, reg)
1622   case 238:     // reg:   And(reg, Constant)
1623     mvec[0] = new MachineInstr(AND);
1624     Set3OperandsFromInstr(mvec[0], subtreeRoot, target);
1625     break;
1626
1627   case 138:     // reg:   And(reg, not)
1628     mvec[0] = new MachineInstr(ANDN);
1629     Set3OperandsFromInstr(mvec[0], subtreeRoot, target);
1630     break;
1631
1632   case  39:     // reg:   Or(reg, reg)
1633   case 239:     // reg:   Or(reg, Constant)
1634     mvec[0] = new MachineInstr(ORN);
1635     Set3OperandsFromInstr(mvec[0], subtreeRoot, target);
1636     break;
1637
1638   case 139:     // reg:   Or(reg, not)
1639     mvec[0] = new MachineInstr(ORN);
1640     Set3OperandsFromInstr(mvec[0], subtreeRoot, target);
1641     break;
1642
1643   case  40:     // reg:   Xor(reg, reg)
1644   case 240:     // reg:   Xor(reg, Constant)
1645     mvec[0] = new MachineInstr(XOR);
1646     Set3OperandsFromInstr(mvec[0], subtreeRoot, target);
1647     break;
1648
1649   case 140:     // reg:   Xor(reg, not)
1650     mvec[0] = new MachineInstr(XNOR);
1651     Set3OperandsFromInstr(mvec[0], subtreeRoot, target);
1652     break;
1653
1654   case 41:      // boolconst:   SetCC(reg, Constant)
1655     // Check if this is an integer comparison, and
1656     // there is a parent, and the parent decided to use
1657     // a branch-on-integer-register instead of branch-on-condition-code.
1658     // If so, the SUBcc instruction is not required.
1659     // (However, we must still check for constants to be loaded from
1660     // the constant pool so that such a load can be associated with
1661     // this instruction.)
1662     //
1663     // Otherwise this is just the same as case 42, so just fall through.
1664     //
1665     if (subtreeRoot->leftChild()->getValue()->getType()->isIntegral() &&
1666         subtreeRoot->parent() != NULL)
1667       {
1668         InstructionNode* parentNode = (InstructionNode*) subtreeRoot->parent();
1669         assert(parentNode->getNodeType() == InstrTreeNode::NTInstructionNode);
1670         const vector<MachineInstr*>&
1671           minstrVec = parentNode->getInstruction()->getMachineInstrVec();
1672         MachineOpCode parentOpCode;
1673         if (parentNode->getInstruction()->getOpcode() == Instruction::Br &&
1674             (parentOpCode = minstrVec[0]->getOpCode()) >= BRZ &&
1675             parentOpCode <= BRGEZ)
1676           {
1677             numInstr = 0;               // don't forward the operand!
1678             break;
1679           }
1680       }
1681     // ELSE FALL THROUGH
1682
1683   case 42:      // bool:   SetCC(reg, reg):
1684   {
1685     // If result of the SetCC is only used for a branch, we can
1686     // discard the result. otherwise, it must go into an integer register.
1687     // Note that the user may or may not be in the same tree, so we have
1688     // to follow SSA def-use edges here, not BURG tree edges.
1689     //
1690     Instruction* result = subtreeRoot->getInstruction();
1691     Value* firstUse = result->use_empty() ? 0 : *result->use_begin();
1692     bool discardResult =
1693       (result->use_size() == 1
1694        && firstUse->isInstruction()
1695        && ((Instruction*) firstUse)->getOpcode() == Instruction::Br);
1696
1697     bool mustClearReg;
1698     int valueToMove;
1699     MachineOpCode movOpCode;
1700
1701     if (subtreeRoot->leftChild()->getValue()->getType()->isIntegral() ||
1702         subtreeRoot->leftChild()->getValue()->getType()->isPointerType())
1703       {
1704         // integer condition: destination should be %g0 or integer register
1705         // if result must be saved but condition is not SetEQ then we need
1706         // a separate instruction to compute the bool result, so discard
1707         // result of SUBcc instruction anyway.
1708         //
1709         mvec[0] = new MachineInstr(SUBcc);
1710         Set3OperandsFromInstr(mvec[0], subtreeRoot, target, discardResult);
1711
1712         // mark the 4th operand as being a CC register, and a "result"
1713         mvec[0]->SetMachineOperand(3, MachineOperand::MO_CCRegister,
1714                                       subtreeRoot->getValue(), /*def*/ true);
1715
1716         if (!discardResult)
1717           { // recompute bool if needed, using the integer condition codes
1718             if (result->getOpcode() == Instruction::SetNE)
1719               discardResult = true;
1720             else
1721               movOpCode =
1722                 ChooseMovpccAfterSub(subtreeRoot, mustClearReg, valueToMove);
1723           }
1724       }
1725     else
1726       {
1727         // FP condition: dest of FCMP should be some FCCn register
1728         mvec[0] = new MachineInstr(ChooseFcmpInstruction(subtreeRoot));
1729         mvec[0]->SetMachineOperand(0, MachineOperand::MO_CCRegister,
1730                                       subtreeRoot->getValue());
1731         mvec[0]->SetMachineOperand(1, MachineOperand::MO_VirtualRegister,
1732                                       subtreeRoot->leftChild()->getValue());
1733         mvec[0]->SetMachineOperand(2, MachineOperand::MO_VirtualRegister,
1734                                       subtreeRoot->rightChild()->getValue());
1735
1736         if (!discardResult)
1737           {// recompute bool using the FP condition codes
1738             mustClearReg = true;
1739             valueToMove = 1;
1740             movOpCode = ChooseMovFpccInstruction(subtreeRoot);
1741           }
1742       }
1743
1744     if (!discardResult)
1745       {
1746         if (mustClearReg)
1747           {// Unconditionally set register to 0
1748            int n = numInstr++;
1749            mvec[n] = new MachineInstr(SETHI);
1750            mvec[n]->SetMachineOperand(0,MachineOperand::MO_UnextendedImmed,s0);
1751            mvec[n]->SetMachineOperand(1, MachineOperand::MO_VirtualRegister,
1752                                          subtreeRoot->getValue());
1753           }
1754
1755         // Now conditionally move `valueToMove' (0 or 1) into the register
1756         int n = numInstr++;
1757         mvec[n] = new MachineInstr(movOpCode);
1758         mvec[n]->SetMachineOperand(0, MachineOperand::MO_CCRegister,
1759                                       subtreeRoot->getValue());
1760         mvec[n]->SetMachineOperand(1, MachineOperand::MO_UnextendedImmed,
1761                                       valueToMove);
1762         mvec[n]->SetMachineOperand(2, MachineOperand::MO_VirtualRegister,
1763                                       subtreeRoot->getValue());
1764       }
1765     break;
1766   }
1767
1768   case 43:      // boolreg: VReg
1769   case 44:      // boolreg: Constant
1770     numInstr = 0;
1771     break;
1772
1773   case 51:      // reg:   Load(reg)
1774   case 52:      // reg:   Load(ptrreg)
1775   case 53:      // reg:   LoadIdx(reg,reg)
1776   case 54:      // reg:   LoadIdx(ptrreg,reg)
1777     mvec[0] = new MachineInstr(ChooseLoadInstruction(subtreeRoot->getValue()->getType()));
1778     SetOperandsForMemInstr(mvec[0], subtreeRoot, target);
1779     break;
1780
1781   case 55:      // reg:   GetElemPtr(reg)
1782   case 56:      // reg:   GetElemPtrIdx(reg,reg)
1783     if (subtreeRoot->parent() != NULL)
1784       {
1785         // Check if the parent was an array access.
1786         // If so, we still need to generate this instruction.
1787         MemAccessInst* memInst =(MemAccessInst*) subtreeRoot->getInstruction();
1788         const PointerType* ptrType =
1789           (const PointerType*) memInst->getPtrOperand()->getType();
1790         if (! ptrType->getValueType()->isArrayType())
1791           {// we don't need a separate instr
1792             numInstr = 0;               // don't forward operand!
1793             break;
1794           }
1795       }
1796     // else in all other cases we need to a separate ADD instruction
1797     mvec[0] = new MachineInstr(ADD);
1798     SetOperandsForMemInstr(mvec[0], subtreeRoot, target);
1799     break;
1800
1801   case 57:      // reg:   Alloca: Implement as 2 instructions:
1802                 //      sub %sp, tmp -> %sp
1803     {           //      add %sp, 0   -> result
1804     Instruction* instr = subtreeRoot->getInstruction();
1805     const PointerType* instrType = (const PointerType*) instr->getType();
1806     assert(instrType->isPointerType());
1807     int tsize = (int) target.findOptimalStorageSize(instrType->getValueType());
1808     assert(tsize != 0 && "Just to check when this can happen");
1809     // if (tsize == 0)
1810     //   {
1811         // numInstr = 0;
1812         // break;
1813     // }
1814     //else go on to create the instructions needed...
1815
1816     // Create a temporary Value to hold the constant type-size
1817     ConstPoolSInt* valueForTSize = ConstPoolSInt::get(Type::IntTy, tsize);
1818
1819     // Instruction 1: sub %sp, tsize -> %sp
1820     // tsize is always constant, but it may have to be put into a
1821     // register if it doesn't fit in the immediate field.
1822     //
1823     mvec[0] = new MachineInstr(SUB);
1824     mvec[0]->SetMachineOperand(0, /*regNum %sp = o6 = r[14]*/(unsigned int)14);
1825     mvec[0]->SetMachineOperand(1, MachineOperand::MO_VirtualRegister, valueForTSize);
1826     mvec[0]->SetMachineOperand(2, /*regNum %sp = o6 = r[14]*/(unsigned int)14);
1827
1828     // Instruction 2: add %sp, 0 -> result
1829     numInstr++;
1830     mvec[1] = new MachineInstr(ADD);
1831     mvec[1]->SetMachineOperand(0, /*regNum %sp = o6 = r[14]*/(unsigned int)14);
1832     mvec[1]->SetMachineOperand(1, /*regNum %g0*/ (unsigned int) 0);
1833     mvec[1]->SetMachineOperand(2, MachineOperand::MO_VirtualRegister, instr);
1834     break;
1835     }
1836
1837   case 58:      // reg:   Alloca(reg): Implement as 3 instructions:
1838                 //      mul num, typeSz -> tmp
1839                 //      sub %sp, tmp    -> %sp
1840     {           //      add %sp, 0      -> result
1841     Instruction* instr = subtreeRoot->getInstruction();
1842     const PointerType* instrType = (const PointerType*) instr->getType();
1843     assert(instrType->isPointerType() &&
1844            instrType->getValueType()->isArrayType());
1845     const Type* eltType =
1846       ((ArrayType*) instrType->getValueType())->getElementType();
1847     int tsize = (int) target.findOptimalStorageSize(eltType);
1848
1849     assert(tsize != 0 && "Just to check when this can happen");
1850     // if (tsize == 0)
1851       // {
1852         // numInstr = 0;
1853         // break;
1854       // }
1855     //else go on to create the instructions needed...
1856
1857     // Create a temporary Value to hold the constant type-size
1858     ConstPoolSInt* valueForTSize = ConstPoolSInt::get(Type::IntTy, tsize);
1859
1860     // Create a temporary value to hold `tmp'
1861     Instruction* tmpInstr = new TmpInstruction(Instruction::UserOp1,
1862                                           subtreeRoot->leftChild()->getValue(),
1863                                           NULL /*could insert tsize here*/);
1864     subtreeRoot->getInstruction()->getMachineInstrVec().addTempValue(tmpInstr);
1865
1866     // Instruction 1: mul numElements, typeSize -> tmp
1867     mvec[0] = new MachineInstr(MULX);
1868     mvec[0]->SetMachineOperand(0, MachineOperand::MO_VirtualRegister,
1869                                 subtreeRoot->leftChild()->getValue());
1870     mvec[0]->SetMachineOperand(1, MachineOperand::MO_VirtualRegister, valueForTSize);
1871     mvec[0]->SetMachineOperand(2, MachineOperand::MO_VirtualRegister,tmpInstr);
1872
1873     tmpInstr->addMachineInstruction(mvec[0]);
1874
1875     // Instruction 2: sub %sp, tmp -> %sp
1876     numInstr++;
1877     mvec[1] = new MachineInstr(SUB);
1878     mvec[1]->SetMachineOperand(0, /*regNum %sp = o6 = r[14]*/(unsigned int)14);
1879     mvec[1]->SetMachineOperand(1, MachineOperand::MO_VirtualRegister,tmpInstr);
1880     mvec[1]->SetMachineOperand(2, /*regNum %sp = o6 = r[14]*/(unsigned int)14);
1881
1882     // Instruction 3: add %sp, 0 -> result
1883     numInstr++;
1884     mvec[2] = new MachineInstr(ADD);
1885     mvec[2]->SetMachineOperand(0, /*regNum %sp = o6 = r[14]*/(unsigned int)14);
1886     mvec[2]->SetMachineOperand(1, /*regNum %g0*/ (unsigned int) 0);
1887     mvec[2]->SetMachineOperand(2, MachineOperand::MO_VirtualRegister, instr);
1888     break;
1889     }
1890
1891   case 61:      // reg:   Call
1892                 // Generate a call-indirect (i.e., JMPL) for now to expose
1893                 // the potential need for registers.  If an absolute address
1894                 // is available, replace this with a CALL instruction.
1895                 // Mark both the indirection register and the return-address
1896     {           // register as hidden virtual registers.
1897
1898     Instruction* jmpAddrReg = new TmpInstruction(Instruction::UserOp1,
1899         ((CallInst*) subtreeRoot->getInstruction())->getCalledMethod(), NULL);
1900     Instruction* retAddrReg = new TmpInstruction(Instruction::UserOp1,
1901                                              subtreeRoot->getValue(), NULL);
1902     subtreeRoot->getInstruction()->getMachineInstrVec().addTempValue(jmpAddrReg);
1903     subtreeRoot->getInstruction()->getMachineInstrVec().addTempValue(retAddrReg);
1904
1905     mvec[0] = new MachineInstr(JMPL);
1906     mvec[0]->SetMachineOperand(0, MachineOperand::MO_VirtualRegister, jmpAddrReg);
1907     mvec[0]->SetMachineOperand(1, MachineOperand::MO_SignExtendedImmed,
1908                                   (int64_t) 0);
1909     mvec[0]->SetMachineOperand(2, MachineOperand::MO_VirtualRegister, retAddrReg);
1910
1911     // NOTE: jmpAddrReg will be loaded by a different instruction generated
1912     //       by the final code generator, so we just mark the CALL instruction
1913     //       as computing that value.
1914     //       The retAddrReg is actually computed by the CALL instruction.
1915     //
1916     jmpAddrReg->addMachineInstruction(mvec[0]);
1917     retAddrReg->addMachineInstruction(mvec[0]);
1918
1919     mvec[numInstr++] = new MachineInstr(NOP); // delay slot
1920     break;
1921     }
1922
1923   case 62:      // reg:   Shl(reg, reg)
1924     opType = subtreeRoot->leftChild()->getValue()->getType();
1925     assert(opType->isIntegral() || opType == Type::BoolTy);
1926     mvec[0] = new MachineInstr((opType == Type::LongTy)? SLLX : SLL);
1927     Set3OperandsFromInstr(mvec[0], subtreeRoot, target);
1928     break;
1929
1930   case 63:      // reg:   Shr(reg, reg)
1931     opType = subtreeRoot->leftChild()->getValue()->getType();
1932     assert(opType->isIntegral() || opType == Type::BoolTy);
1933     mvec[0] = new MachineInstr((opType->isSigned()
1934                                 ? ((opType == Type::LongTy)? SRAX : SRA)
1935                                 : ((opType == Type::LongTy)? SRLX : SRL)));
1936     Set3OperandsFromInstr(mvec[0], subtreeRoot, target);
1937     break;
1938
1939   case 64:      // reg:   Phi(reg,reg)
1940   {             // This instruction has variable #operands, so resultPos is 0.
1941     Instruction* phi = subtreeRoot->getInstruction();
1942     mvec[0] = new MachineInstr(PHI, 1 + phi->getNumOperands());
1943     mvec[0]->SetMachineOperand(0, MachineOperand::MO_VirtualRegister,
1944                                   subtreeRoot->getValue());
1945     for (unsigned i=0, N=phi->getNumOperands(); i < N; i++)
1946       mvec[0]->SetMachineOperand(i+1, MachineOperand::MO_VirtualRegister,
1947                                       phi->getOperand(i));
1948     break;
1949   }
1950   case 71:      // reg:     VReg
1951   case 72:      // reg:     Constant
1952     numInstr = 0;                       // don't forward the value
1953     break;
1954
1955   case 111:     // stmt:  reg
1956   case 112:     // stmt:  boolconst
1957   case 113:     // stmt:  bool
1958   case 121:
1959   case 122:
1960   case 123:
1961   case 124:
1962   case 125:
1963   case 126:
1964   case 127:
1965   case 128:
1966   case 129:
1967   case 130:
1968   case 131:
1969   case 132:
1970   case 153:
1971   case 155:
1972     //
1973     // These are all chain rules, which have a single nonterminal on the RHS.
1974     // Get the rule that matches the RHS non-terminal and use that instead.
1975     //
1976     assert(ThisIsAChainRule(ruleForNode));
1977     assert(nts[0] && ! nts[1]
1978            && "A chain rule should have only one RHS non-terminal!");
1979     nextRule = burm_rule(subtreeRoot->state, nts[0]);
1980     nts = burm_nts[nextRule];
1981     numInstr = GetInstructionsByRule(subtreeRoot, nextRule, nts,target,mvec);
1982     break;
1983
1984   default:
1985     assert(0 && "Unrecognized BURG rule");
1986     numInstr = 0;
1987     break;
1988   }
1989
1990   if (forwardOperandNum >= 0)
1991     { // We did not generate a machine instruction but need to use operand.
1992       // If user is in the same tree, replace Value in its machine operand.
1993       // If not, insert a copy instruction which should get coalesced away
1994       // by register allocation.
1995       if (subtreeRoot->parent() != NULL)
1996         ForwardOperand(subtreeRoot, (InstructionNode*) subtreeRoot->parent(),
1997                        forwardOperandNum);
1998       else
1999         {
2000           int n = numInstr++;
2001           mvec[n] = new MachineInstr(ADD);
2002           mvec[n]->SetMachineOperand(0, MachineOperand::MO_VirtualRegister,
2003                 subtreeRoot->getInstruction()->getOperand(forwardOperandNum));
2004           mvec[n]->SetMachineOperand(1, /*regNum %g0*/ (unsigned int) 0);
2005           mvec[n]->SetMachineOperand(2, MachineOperand::MO_VirtualRegister,
2006                                         subtreeRoot->getInstruction());
2007         }
2008     }
2009
2010   if (! ThisIsAChainRule(ruleForNode))
2011     numInstr = FixConstantOperands(subtreeRoot, mvec, numInstr, target);
2012
2013   return numInstr;
2014 }
2015
2016