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 ChooseLoadInstruction(const Type *DestTy) {
 825   switch (DestTy->getPrimitiveID()) {
 826   case Type::BoolTyID:
 827   case Type::UByteTyID:   return LDUB;
 828   case Type::SByteTyID:   return LDSB;
 829   case Type::UShortTyID:  return LDUH;
 830   case Type::ShortTyID:   return LDSH;
 831   case Type::UIntTyID:    return LDUW;
 832   case Type::IntTyID:     return LDSW;
 833   case Type::PointerTyID:
 834   case Type::ULongTyID:
 835   case Type::LongTyID:    return LDX;
 836   case Type::FloatTyID:   return LD;
 837   case Type::DoubleTyID:  return LDD;
 838   default: assert(0 && "Invalid type for Load instruction");
 839   }
 840
 841   return 0;
 842 }
 843
 844
 845 static inline MachineOpCode ChooseStoreInstruction(const Type *DestTy) {
 846   switch (DestTy->getPrimitiveID()) {
 847   case Type::BoolTyID:
 848   case Type::UByteTyID:
 849   case Type::SByteTyID:   return STB;
 850   case Type::UShortTyID:
 851   case Type::ShortTyID:   return STH;
 852   case Type::UIntTyID:
 853   case Type::IntTyID:     return STW;
 854   case Type::PointerTyID:
 855   case Type::ULongTyID:
 856   case Type::LongTyID:    return STX;
 857   case Type::FloatTyID:   return ST;
 858   case Type::DoubleTyID:  return STD;
 859   default: assert(0 && "Invalid type for Store instruction");
 860   }
 861
 862   return 0;
 863 }
 864
 865
 866 //------------------------------------------------------------------------
 867 // Function SetOperandsForMemInstr
 868 //
 869 // Choose addressing mode for the given load or store instruction.
 870 // Use [reg+reg] if it is an indexed reference, and the index offset is
 871 //               not a constant or if it cannot fit in the offset field.
 872 // Use [reg+offset] in all other cases.
 873 //
 874 // This assumes that all array refs are "lowered" to one of these forms:
 875 //      %x = load (subarray*) ptr, constant     ; single constant offset
 876 //      %x = load (subarray*) ptr, offsetVal    ; single non-constant offset
 877 // Generally, this should happen via strength reduction + LICM.
 878 // Also, strength reduction should take care of using the same register for
 879 // the loop index variable and an array index, when that is profitable.
 880 //------------------------------------------------------------------------
 881
 882 static void
 883 SetOperandsForMemInstr(MachineInstr* minstr,
 884                        const InstructionNode* vmInstrNode,
 885                        const TargetMachine& target)
 886 {
 887   MemAccessInst* memInst = (MemAccessInst*) vmInstrNode->getInstruction();
 888
 889   // Variables to hold the index vector, ptr value, and offset value.
 890   // The major work here is to extract these for all 3 instruction types
 891   // and then call the common function SetMemOperands_Internal().
 892   //
 893   const vector<ConstPoolVal*>* idxVec = & memInst->getIndexVec();
 894   vector<ConstPoolVal*>* newIdxVec = NULL;
 895   Value* ptrVal;
 896   Value* arrayOffsetVal = NULL;
 897
 898   // Test if a GetElemPtr instruction is being folded into this mem instrn.
 899   // If so, it will be in the left child for Load and GetElemPtr,
 900   // and in the right child for Store instructions.
 901   //
 902   InstrTreeNode* ptrChild = (vmInstrNode->getOpLabel() == Instruction::Store
 903                              ? vmInstrNode->rightChild()
 904                              : vmInstrNode->leftChild());
 905
 906   if (ptrChild->getOpLabel() == Instruction::GetElementPtr ||
 907       ptrChild->getOpLabel() == GetElemPtrIdx)
 908     {
 909       // There is a GetElemPtr instruction and there may be a chain of
 910       // more than one.  Use the pointer value of the last one in the chain.
 911       // Fold the index vectors from the entire chain and from the mem
 912       // instruction into one single index vector.
 913       // Finally, we never fold for an array instruction so make that NULL.
 914
 915       newIdxVec = new vector<ConstPoolVal*>;
 916       ptrVal = FoldGetElemChain((InstructionNode*) ptrChild, *newIdxVec);
 917
 918       newIdxVec->insert(newIdxVec->end(), idxVec->begin(), idxVec->end());
 919       idxVec = newIdxVec;
 920
 921       assert(! ((PointerType*)ptrVal->getType())->getValueType()->isArrayType()
 922              && "GetElemPtr cannot be folded into array refs in selection");
 923     }
 924   else
 925     {
 926       // There is no GetElemPtr instruction.
 927       // Use the pointer value and the index vector from the Mem instruction.
 928       // If it is an array reference, get the array offset value.
 929       //
 930       ptrVal = memInst->getPtrOperand();
 931
 932       const Type* opType =
 933         ((const PointerType*) ptrVal->getType())->getValueType();
 934       if (opType->isArrayType())
 935         {
 936           assert((memInst->getNumOperands()
 937                   == (unsigned) 1 + memInst->getFirstOffsetIdx())
 938                  && "Array refs must be lowered before Instruction Selection");
 939
 940           arrayOffsetVal = memInst->getOperand(memInst->getFirstOffsetIdx());
 941         }
 942     }
 943
 944   SetMemOperands_Internal(minstr, vmInstrNode, ptrVal, arrayOffsetVal,
 945                           *idxVec, target);
 946
 947   if (newIdxVec != NULL)
 948     delete newIdxVec;
 949 }
 950
 951
 952 static void
 953 SetMemOperands_Internal(MachineInstr* minstr,
 954                         const InstructionNode* vmInstrNode,
 955                         Value* ptrVal,
 956                         Value* arrayOffsetVal,
 957                         const vector<ConstPoolVal*>& idxVec,
 958                         const TargetMachine& target)
 959 {
 960   MemAccessInst* memInst = (MemAccessInst*) vmInstrNode->getInstruction();
 961
 962   // Initialize so we default to storing the offset in a register.
 963   int64_t smallConstOffset;
 964   Value* valueForRegOffset = NULL;
 965   MachineOperand::MachineOperandType offsetOpType =MachineOperand::MO_VirtualRegister;
 966
 967   // Check if there is an index vector and if so, if it translates to
 968   // a small enough constant to fit in the immediate-offset field.
 969   //
 970   if (idxVec.size() > 0)
 971     {
 972       bool isConstantOffset = false;
 973       unsigned offset;
 974
 975       const PointerType* ptrType = (PointerType*) ptrVal->getType();
 976
 977       if (ptrType->getValueType()->isStructType())
 978         {
 979           // the offset is always constant for structs
 980           isConstantOffset = true;
 981
 982           // Compute the offset value using the index vector
 983           offset = target.DataLayout.getIndexedOffset(ptrType, idxVec);
 984         }
 985       else
 986         {
 987           // It must be an array ref.  Check if the offset is a constant,
 988           // and that the indexing has been lowered to a single offset.
 989           //
 990           assert(ptrType->getValueType()->isArrayType());
 991           assert(arrayOffsetVal != NULL
 992                  && "Expect to be given Value* for array offsets");
 993
 994           if (ConstPoolVal *CPV = arrayOffsetVal->castConstant())
 995             {
 996               isConstantOffset = true;  // always constant for structs
 997               assert(arrayOffsetVal->getType()->isIntegral());
 998               offset = (CPV->getType()->isSigned()
 999                         ? ((ConstPoolSInt*)CPV)->getValue()
1000                         : (int64_t) ((ConstPoolUInt*)CPV)->getValue());
1001             }
1002           else
1003             {
1004               valueForRegOffset = arrayOffsetVal;
1005             }
1006         }
1007
1008       if (isConstantOffset)
1009         {
1010           // create a virtual register for the constant
1011           valueForRegOffset = ConstPoolSInt::get(Type::IntTy, offset);
1012         }
1013     }
1014   else
1015     {
1016       offsetOpType = MachineOperand::MO_SignExtendedImmed;
1017       smallConstOffset = 0;
1018     }
1019
1020   // Operand 0 is value for STORE, ptr for LOAD or GET_ELEMENT_PTR
1021   // It is the left child in the instruction tree in all cases.
1022   Value* leftVal = vmInstrNode->leftChild()->getValue();
1023   minstr->SetMachineOperand(0, MachineOperand::MO_VirtualRegister, leftVal);
1024
1025   // Operand 1 is ptr for STORE, offset for LOAD or GET_ELEMENT_PTR
1026   // Operand 3 is offset for STORE, result reg for LOAD or GET_ELEMENT_PTR
1027   //
1028   unsigned offsetOpNum = (memInst->getOpcode() == Instruction::Store)? 2 : 1;
1029   if (offsetOpType == MachineOperand::MO_VirtualRegister)
1030     {
1031       assert(valueForRegOffset != NULL);
1032       minstr->SetMachineOperand(offsetOpNum, offsetOpType, valueForRegOffset);
1033     }
1034   else
1035     minstr->SetMachineOperand(offsetOpNum, offsetOpType, smallConstOffset);
1036
1037   if (memInst->getOpcode() == Instruction::Store)
1038     minstr->SetMachineOperand(1, MachineOperand::MO_VirtualRegister, ptrVal);
1039   else
1040     minstr->SetMachineOperand(2, MachineOperand::MO_VirtualRegister,
1041                                  vmInstrNode->getValue());
1042 }
1043
1044
1045 // Special handling for constant operands:
1046 // -- if the constant is 0, use the hardwired 0 register, if any;
1047 // -- if the constant is of float or double type but has an integer value,
1048 //    use int-to-float conversion instruction instead of generating a load;
1049 // -- if the constant fits in the IMMEDIATE field, use that field;
1050 // -- else insert instructions to put the constant into a register, either
1051 //    directly or by loading explicitly from the constant pool.
1052 //
1053 static unsigned
1054 FixConstantOperands(const InstructionNode* vmInstrNode,
1055                     MachineInstr** mvec,
1056                     unsigned numInstr,
1057                     TargetMachine& target)
1058 {
1059   static MachineInstr* loadConstVec[MAX_INSTR_PER_VMINSTR];
1060
1061   unsigned numNew = 0;
1062   Instruction* vmInstr = vmInstrNode->getInstruction();
1063
1064   for (unsigned i=0; i < numInstr; i++)
1065     {
1066       MachineInstr* minstr = mvec[i];
1067       const MachineInstrDescriptor& instrDesc =
1068         target.getInstrInfo().getDescriptor(minstr->getOpCode());
1069
1070       for (unsigned op=0; op < minstr->getNumOperands(); op++)
1071         {
1072           const MachineOperand& mop = minstr->getOperand(op);
1073
1074           // skip the result position (for efficiency below) and any other
1075           // positions already marked as not a virtual register
1076           if (instrDesc.resultPos == (int) op ||
1077               mop.getOperandType() != MachineOperand::MO_VirtualRegister ||
1078               mop.getVRegValue() == NULL)
1079             {
1080               break;
1081             }
1082
1083           Value* opValue = mop.getVRegValue();
1084
1085           if (opValue->isConstant())
1086             {
1087               unsigned int machineRegNum;
1088               int64_t immedValue;
1089               MachineOperand::MachineOperandType opType =
1090                 ChooseRegOrImmed(opValue, minstr->getOpCode(), target,
1091                                  /*canUseImmed*/ (op == 1),
1092                                  machineRegNum, immedValue);
1093
1094               if (opType == MachineOperand::MO_MachineRegister)
1095                 minstr->SetMachineOperand(op, machineRegNum);
1096               else if (opType == MachineOperand::MO_VirtualRegister)
1097                 {
1098                   // value is constant and must be loaded into a register
1099                   TmpInstruction* tmpReg;
1100                   MachineInstr* minstr2;
1101                   loadConstVec[numNew++] = MakeLoadConstInstr(vmInstr, opValue,
1102                                                               tmpReg, minstr2);
1103                   minstr->SetMachineOperand(op, opType, tmpReg);
1104                   if (minstr2 != NULL)
1105                     loadConstVec[numNew++] = minstr2;
1106                 }
1107               else
1108                 minstr->SetMachineOperand(op, opType, immedValue);
1109             }
1110         }
1111     }
1112
1113   if (numNew > 0)
1114     {
1115       // Insert the new instructions *before* the old ones by moving
1116       // the old ones over `numNew' positions (last-to-first, of course!).
1117       // We do check *after* returning that we did not exceed the vector mvec.
1118       for (int i=numInstr-1; i >= 0; i--)
1119         mvec[i+numNew] = mvec[i];
1120
1121       for (unsigned i=0; i < numNew; i++)
1122         mvec[i] = loadConstVec[i];
1123     }
1124
1125   return (numInstr + numNew);
1126 }
1127
1128
1129 static inline MachineInstr*
1130 MakeIntSetInstruction(int64_t C, bool isSigned, Value* dest)
1131 {
1132   MachineInstr* minstr;
1133   if (isSigned)
1134     {
1135       minstr = new MachineInstr(SETSW);
1136       minstr->SetMachineOperand(0, MachineOperand::MO_SignExtendedImmed, C);
1137     }
1138   else
1139     {
1140       minstr = new MachineInstr(SETUW);
1141       minstr->SetMachineOperand(0, MachineOperand::MO_UnextendedImmed, C);
1142     }
1143
1144   minstr->SetMachineOperand(1, MachineOperand::MO_VirtualRegister, dest);
1145
1146   return minstr;
1147 }
1148
1149
1150 static MachineInstr*
1151 MakeLoadConstInstr(Instruction* vmInstr,
1152                    Value* val,
1153                    TmpInstruction*& tmpReg,
1154                    MachineInstr*& getMinstr2)
1155 {
1156   assert(val->isConstant());
1157
1158   MachineInstr* minstr;
1159
1160   getMinstr2 = NULL;
1161
1162   // Create a TmpInstruction to mark the hidden register used for the constant
1163   tmpReg = new TmpInstruction(Instruction::UserOp1, val, NULL);
1164   vmInstr->getMachineInstrVec().addTempValue(tmpReg);
1165
1166   // Use a "set" instruction for known constants that can go in an integer reg.
1167   // Use a "set" instruction followed by a int-to-float conversion for known
1168   // constants that must go in a floating point reg but have an integer value.
1169   // Use a "load" instruction for all other constants, in particular,
1170   // floating point constants.
1171   //
1172   const Type* valType = val->getType();
1173
1174   if (valType->isIntegral() ||
1175       valType->isPointerType() ||
1176       valType == Type::BoolTy)
1177     {
1178       bool isValidConstant;
1179       int64_t C = GetConstantValueAsSignedInt(val, isValidConstant);
1180       assert(isValidConstant && "Unrecognized constant");
1181
1182       minstr = MakeIntSetInstruction(C, valType->isSigned(), tmpReg);
1183     }
1184   else
1185     {
1186       assert(valType == Type::FloatTy || valType == Type::DoubleTy);
1187       double dval = ((ConstPoolFP*) val)->getValue();
1188       if (dval == (int64_t) dval)
1189         {
1190           // The constant actually has an integer value, so use a
1191           // [set; int-to-float] sequence instead of a load instruction.
1192           //
1193           TmpInstruction* tmpReg2 = NULL;
1194           if (dval != 0.0)
1195             { // First, create an integer constant of the same value as dval
1196               ConstPoolSInt* ival = ConstPoolSInt::get(Type::IntTy,
1197                                                        (int64_t) dval);
1198               // Create another TmpInstruction for the hidden integer register
1199               TmpInstruction* tmpReg2 =
1200                 new TmpInstruction(Instruction::UserOp1, ival, NULL);
1201               vmInstr->getMachineInstrVec().addTempValue(tmpReg2);
1202
1203               // Create the `SET' instruction
1204               minstr = MakeIntSetInstruction((int64_t)dval, true, tmpReg2);
1205             }
1206
1207           // In which variable do we put the second instruction?
1208           MachineInstr*& instr2 = (minstr)? getMinstr2 : minstr;
1209
1210           // Create the int-to-float instruction
1211           instr2 = new MachineInstr(valType == Type::FloatTy? FITOS : FITOD);
1212
1213           if (dval == 0.0)
1214             instr2->SetMachineOperand(0, /*regNum %g0*/ (unsigned int) 0);
1215           else
1216             instr2->SetMachineOperand(0,MachineOperand::MO_VirtualRegister,
1217                                           tmpReg2);
1218
1219           instr2->SetMachineOperand(1, MachineOperand::MO_VirtualRegister,
1220                                            tmpReg);
1221         }
1222       else
1223         {
1224           // Make a Load instruction, and make `val' both the ptr value *and*
1225           // the result value, and set the offset field to 0.  Final code
1226           // generation will have to generate the base+offset for the constant.
1227           //
1228           int64_t zeroOffset = 0; // to avoid ambiguity with (Value*) 0
1229           minstr = new MachineInstr(ChooseLoadInstruction(val->getType()));
1230           minstr->SetMachineOperand(0, MachineOperand::MO_VirtualRegister,val);
1231           minstr->SetMachineOperand(1, MachineOperand::MO_SignExtendedImmed,
1232                                        zeroOffset);
1233           minstr->SetMachineOperand(2, MachineOperand::MO_VirtualRegister,
1234                                        tmpReg);
1235         }
1236     }
1237
1238   tmpReg->addMachineInstruction(minstr);
1239
1240   assert(minstr);
1241   return minstr;
1242 }
1243
1244 //
1245 // Substitute operand `operandNum' of the instruction in node `treeNode'
1246 // in place the use(s) of that instruction in node `parent'.
1247 //
1248 static void
1249 ForwardOperand(InstructionNode* treeNode,
1250                InstructionNode* parent,
1251                int operandNum)
1252 {
1253   Instruction* unusedOp = treeNode->getInstruction();
1254   Value* fwdOp = unusedOp->getOperand(operandNum);
1255   Instruction* userInstr = parent->getInstruction();
1256   MachineCodeForVMInstr& mvec = userInstr->getMachineInstrVec();
1257   for (unsigned i=0, N=mvec.size(); i < N; i++)
1258     {
1259       MachineInstr* minstr = mvec[i];
1260       for (unsigned i=0, numOps=minstr->getNumOperands(); i < numOps; i++)
1261         {
1262           const MachineOperand& mop = minstr->getOperand(i);
1263           if (mop.getOperandType() == MachineOperand::MO_VirtualRegister &&
1264               mop.getVRegValue() == unusedOp)
1265             {
1266               minstr->SetMachineOperand(i, MachineOperand::MO_VirtualRegister,
1267                                            fwdOp);
1268             }
1269         }
1270     }
1271 }
1272
1273
1274 // This function is currently unused and incomplete but will be
1275 // used if we have a linear layout of basic blocks in LLVM code.
1276 // It decides which branch should fall-through, and whether an
1277 // extra unconditional branch is needed (when neither falls through).
1278 //
1279 void
1280 ChooseBranchPattern(Instruction* vmInstr, BranchPattern& brPattern)
1281 {
1282   BranchInst* brInstr = (BranchInst*) vmInstr;
1283
1284   brPattern.flipCondition = false;
1285   brPattern.targetBB      = brInstr->getSuccessor(0);
1286   brPattern.extraBranch   = NULL;
1287
1288   assert(brInstr->getNumSuccessors() > 1 &&
1289          "Unnecessary analysis for unconditional branch");
1290
1291   assert(0 && "Fold branches in peephole optimization");
1292 }
1293
1294
1295 //******************* Externally Visible Functions *************************/
1296
1297
1298 //------------------------------------------------------------------------
1299 // External Function: GetInstructionsByRule
1300 //
1301 // Purpose:
1302 //   Choose machine instructions for the SPARC according to the
1303 //   patterns chosen by the BURG-generated parser.
1304 //------------------------------------------------------------------------
1305
1306 unsigned
1307 GetInstructionsByRule(InstructionNode* subtreeRoot,
1308                       int ruleForNode,
1309                       short* nts,
1310                       TargetMachine &target,
1311                       MachineInstr** mvec)
1312 {
1313   int numInstr = 1;                     // initialize for common case
1314   bool checkCast = false;               // initialize here to use fall-through
1315   Value *leftVal, *rightVal;
1316   const Type* opType;
1317   int nextRule;
1318   int forwardOperandNum = -1;
1319   BranchPattern brPattern;
1320   int64_t s0 = 0;                       // variables holding zero to avoid
1321   uint64_t u0 = 0;                      // overloading ambiguities below
1322
1323   mvec[0] = mvec[1] = mvec[2] = mvec[3] = NULL; // just for safety
1324
1325   switch(ruleForNode) {
1326   case 1:       // stmt:   Ret
1327   case 2:       // stmt:   RetValue(reg)
1328                 // NOTE: Prepass of register allocation is responsible
1329                 //       for moving return value to appropriate register.
1330                 // Mark the return-address register as a hidden virtual reg.
1331     {
1332     Instruction* returnReg = new TmpInstruction(Instruction::UserOp1,
1333                                         subtreeRoot->getInstruction(), NULL);
1334     subtreeRoot->getInstruction()->getMachineInstrVec().addTempValue(returnReg);
1335
1336     mvec[0] = new MachineInstr(RETURN);
1337     mvec[0]->SetMachineOperand(0,MachineOperand::MO_VirtualRegister,returnReg);
1338     mvec[0]->SetMachineOperand(1, MachineOperand::MO_SignExtendedImmed, s0);
1339
1340     returnReg->addMachineInstruction(mvec[0]);
1341
1342     mvec[numInstr++] = new MachineInstr(NOP); // delay slot
1343     break;
1344     }
1345
1346   case 3:       // stmt:   Store(reg,reg)
1347   case 4:       // stmt:   Store(reg,ptrreg)
1348     mvec[0] = new MachineInstr(ChooseStoreInstruction(subtreeRoot->leftChild()->getValue()->getType()));
1349     SetOperandsForMemInstr(mvec[0], subtreeRoot, target);
1350     break;
1351
1352   case 5:       // stmt:   BrUncond
1353     mvec[0] = new MachineInstr(BA);
1354     mvec[0]->SetMachineOperand(0, MachineOperand::MO_CCRegister, (Value*)NULL);
1355     mvec[0]->SetMachineOperand(1, MachineOperand::MO_PCRelativeDisp,
1356               ((BranchInst*) subtreeRoot->getInstruction())->getSuccessor(0));
1357
1358     // delay slot
1359     mvec[numInstr++] = new MachineInstr(NOP);
1360     break;
1361
1362   case 6:       // stmt:   BrCond(boolconst)
1363     // boolconst => boolean was computed with `%b = setCC type reg1 constant'
1364     // If the constant is ZERO, we can use the branch-on-integer-register
1365     // instructions and avoid the SUBcc instruction entirely.
1366     // Otherwise this is just the same as case 5, so just fall through.
1367     {
1368     InstrTreeNode* constNode = subtreeRoot->leftChild()->rightChild();
1369     assert(constNode && constNode->getNodeType() ==InstrTreeNode::NTConstNode);
1370     ConstPoolVal* constVal = (ConstPoolVal*) constNode->getValue();
1371     bool isValidConst;
1372
1373     if (constVal->getType()->isIntegral()
1374         && GetConstantValueAsSignedInt(constVal, isValidConst) == 0
1375         && isValidConst)
1376       {
1377         // That constant ia a zero after all...
1378         // Use the left child of the setCC instruction as the first argument!
1379         mvec[0] = new MachineInstr(ChooseBprInstruction(subtreeRoot));
1380         mvec[0]->SetMachineOperand(0, MachineOperand::MO_VirtualRegister,
1381                       subtreeRoot->leftChild()->leftChild()->getValue());
1382         mvec[0]->SetMachineOperand(1, MachineOperand::MO_PCRelativeDisp,
1383               ((BranchInst*) subtreeRoot->getInstruction())->getSuccessor(0));
1384
1385         // delay slot
1386         mvec[numInstr++] = new MachineInstr(NOP);
1387
1388         // false branch
1389         mvec[numInstr++] = new MachineInstr(BA);
1390         mvec[numInstr-1]->SetMachineOperand(0, MachineOperand::MO_CCRegister,
1391                                                 (Value*) NULL);
1392         mvec[numInstr-1]->SetMachineOperand(1, MachineOperand::MO_PCRelativeDisp, ((BranchInst*) subtreeRoot->getInstruction())->getSuccessor(1));
1393
1394         // delay slot
1395         mvec[numInstr++] = new MachineInstr(NOP);
1396
1397         break;
1398       }
1399     // ELSE FALL THROUGH
1400     }
1401
1402   case 7:       // stmt:   BrCond(bool)
1403     // bool => boolean was computed with `%b = setcc type reg1 reg2'
1404     // Need to check whether the type was a FP, signed int or unsigned int,
1405     // and check the branching condition in order to choose the branch to use.
1406     //
1407     {
1408     bool isFPBranch;
1409     mvec[0] = new MachineInstr(ChooseBccInstruction(subtreeRoot, isFPBranch));
1410     mvec[0]->SetMachineOperand(0, MachineOperand::MO_CCRegister,
1411                                   subtreeRoot->leftChild()->getValue());
1412     mvec[0]->SetMachineOperand(1, MachineOperand::MO_PCRelativeDisp,
1413               ((BranchInst*) subtreeRoot->getInstruction())->getSuccessor(0));
1414
1415     // delay slot
1416     mvec[numInstr++] = new MachineInstr(NOP);
1417
1418     // false branch
1419     mvec[numInstr++] = new MachineInstr(BA);
1420     mvec[numInstr-1]->SetMachineOperand(0, MachineOperand::MO_CCRegister,
1421                                            (Value*) NULL);
1422     mvec[numInstr-1]->SetMachineOperand(0, MachineOperand::MO_PCRelativeDisp,
1423               ((BranchInst*) subtreeRoot->getInstruction())->getSuccessor(1));
1424
1425     // delay slot
1426     mvec[numInstr++] = new MachineInstr(NOP);
1427     break;
1428     }
1429
1430   case 8:       // stmt:   BrCond(boolreg)
1431     // bool => boolean is stored in an existing register.
1432     // Just use the branch-on-integer-register instruction!
1433     //
1434     mvec[0] = new MachineInstr(BRNZ);
1435     mvec[0]->SetMachineOperand(0, MachineOperand::MO_VirtualRegister,
1436                                   subtreeRoot->leftChild()->getValue());
1437     mvec[0]->SetMachineOperand(1, MachineOperand::MO_PCRelativeDisp,
1438               ((BranchInst*) subtreeRoot->getInstruction())->getSuccessor(0));
1439
1440     // delay slot
1441     mvec[numInstr++] = new MachineInstr(NOP); // delay slot
1442
1443     // false branch
1444     mvec[numInstr++] = new MachineInstr(BA);
1445     mvec[numInstr-1]->SetMachineOperand(0, MachineOperand::MO_CCRegister,
1446                                            (Value*) NULL);
1447     mvec[numInstr-1]->SetMachineOperand(0, MachineOperand::MO_PCRelativeDisp,
1448               ((BranchInst*) subtreeRoot->getInstruction())->getSuccessor(1));
1449
1450     // delay slot
1451     mvec[numInstr++] = new MachineInstr(NOP);
1452     break;
1453
1454   case 9:       // stmt:   Switch(reg)
1455     assert(0 && "*** SWITCH instruction is not implemented yet.");
1456     numInstr = 0;
1457     break;
1458
1459   case 10:      // reg:   VRegList(reg, reg)
1460     assert(0 && "VRegList should never be the topmost non-chain rule");
1461     break;
1462
1463   case 21:      // reg:   Not(reg):     Implemented as reg = reg XOR-NOT 0
1464     mvec[0] = new MachineInstr(XNOR);
1465     mvec[0]->SetMachineOperand(0, MachineOperand::MO_VirtualRegister,
1466                                   subtreeRoot->leftChild()->getValue());
1467     mvec[0]->SetMachineOperand(1, /*regNum %g0*/ (unsigned int) 0);
1468     mvec[0]->SetMachineOperand(2, MachineOperand::MO_VirtualRegister,
1469                                  subtreeRoot->getValue());
1470     break;
1471
1472   case 22:      // reg:   ToBoolTy(reg):
1473     opType = subtreeRoot->leftChild()->getValue()->getType();
1474     assert(opType->isIntegral() || opType == Type::BoolTy);
1475     numInstr = 0;
1476     forwardOperandNum = 0;
1477     break;
1478
1479   case 23:      // reg:   ToUByteTy(reg)
1480   case 25:      // reg:   ToUShortTy(reg)
1481   case 27:      // reg:   ToUIntTy(reg)
1482   case 29:      // reg:   ToULongTy(reg)
1483     opType = subtreeRoot->leftChild()->getValue()->getType();
1484     assert(opType->isIntegral() ||
1485            opType->isPointerType() ||
1486            opType == Type::BoolTy && "Ignoring cast: illegal for other types");
1487     numInstr = 0;
1488     forwardOperandNum = 0;
1489     break;
1490
1491   case 24:      // reg:   ToSByteTy(reg)
1492   case 26:      // reg:   ToShortTy(reg)
1493   case 28:      // reg:   ToIntTy(reg)
1494   case 30:      // reg:   ToLongTy(reg)
1495     opType = subtreeRoot->leftChild()->getValue()->getType();
1496     if (opType->isIntegral() || opType == Type::BoolTy)
1497       {
1498         numInstr = 0;
1499         forwardOperandNum = 0;
1500       }
1501     else
1502       {
1503         mvec[0] =new MachineInstr(ChooseConvertToIntInstr(subtreeRoot,opType));
1504         Set2OperandsFromInstr(mvec[0], subtreeRoot, target);
1505       }
1506     break;
1507
1508   case 31:      // reg:   ToFloatTy(reg):
1509   case 32:      // reg:   ToDoubleTy(reg):
1510
1511     // If this instruction has a parent (a user) in the tree
1512     // and the user is translated as an FsMULd instruction,
1513     // then the cast is unnecessary.  So check that first.
1514     // In the future, we'll want to do the same for the FdMULq instruction,
1515     // so do the check here instead of only for ToFloatTy(reg).
1516     //
1517     if (subtreeRoot->parent() != NULL &&
1518         ((InstructionNode*) subtreeRoot->parent())->getInstruction()->getMachineInstrVec()[0]->getOpCode() == FSMULD)
1519       {
1520         numInstr = 0;
1521         forwardOperandNum = 0;
1522       }
1523     else
1524       {
1525         opType = subtreeRoot->leftChild()->getValue()->getType();
1526         MachineOpCode opCode = ChooseConvertToFloatInstr(subtreeRoot, opType);
1527         if (opCode == INVALID_OPCODE)   // no conversion needed
1528           {
1529             numInstr = 0;
1530             forwardOperandNum = 0;
1531           }
1532         else
1533           {
1534             mvec[0] = new MachineInstr(opCode);
1535             Set2OperandsFromInstr(mvec[0], subtreeRoot, target);
1536           }
1537       }
1538     break;
1539
1540   case 19:      // reg:   ToArrayTy(reg):
1541   case 20:      // reg:   ToPointerTy(reg):
1542     numInstr = 0;
1543     forwardOperandNum = 0;
1544     break;
1545
1546   case 233:     // reg:   Add(reg, Constant)
1547     mvec[0] = CreateAddConstInstruction(subtreeRoot);
1548     if (mvec[0] != NULL)
1549       break;
1550     // ELSE FALL THROUGH
1551
1552   case 33:      // reg:   Add(reg, reg)
1553     mvec[0] = new MachineInstr(ChooseAddInstruction(subtreeRoot));
1554     Set3OperandsFromInstr(mvec[0], subtreeRoot, target);
1555     break;
1556
1557   case 234:     // reg:   Sub(reg, Constant)
1558     mvec[0] = CreateSubConstInstruction(subtreeRoot);
1559     if (mvec[0] != NULL)
1560       break;
1561     // ELSE FALL THROUGH
1562
1563   case 34:      // reg:   Sub(reg, reg)
1564     mvec[0] = new MachineInstr(ChooseSubInstruction(subtreeRoot));
1565     Set3OperandsFromInstr(mvec[0], subtreeRoot, target);
1566     break;
1567
1568   case 135:     // reg:   Mul(todouble, todouble)
1569     checkCast = true;
1570     // FALL THROUGH
1571
1572   case 35:      // reg:   Mul(reg, reg)
1573     mvec[0] = new MachineInstr(ChooseMulInstruction(subtreeRoot, checkCast));
1574     Set3OperandsFromInstr(mvec[0], subtreeRoot, target);
1575     break;
1576
1577   case 335:     // reg:   Mul(todouble, todoubleConst)
1578     checkCast = true;
1579     // FALL THROUGH
1580
1581   case 235:     // reg:   Mul(reg, Constant)
1582     mvec[0] = CreateMulConstInstruction(subtreeRoot, mvec[1]);
1583     if (mvec[0] == NULL)
1584       {
1585         mvec[0]=new MachineInstr(ChooseMulInstruction(subtreeRoot, checkCast));
1586         Set3OperandsFromInstr(mvec[0], subtreeRoot, target);
1587       }
1588     else
1589       if (mvec[1] != NULL)
1590         ++numInstr;
1591     break;
1592
1593   case 236:     // reg:   Div(reg, Constant)
1594     mvec[0] = CreateDivConstInstruction(subtreeRoot, mvec[1]);
1595     if (mvec[0] != NULL)
1596       {
1597         if (mvec[1] != NULL)
1598           ++numInstr;
1599       }
1600     else
1601     // ELSE FALL THROUGH
1602
1603   case 36:      // reg:   Div(reg, reg)
1604     mvec[0] = new MachineInstr(ChooseDivInstruction(subtreeRoot));
1605     Set3OperandsFromInstr(mvec[0], subtreeRoot, target);
1606     break;
1607
1608   case  37:     // reg:   Rem(reg, reg)
1609   case 237:     // reg:   Rem(reg, Constant)
1610     assert(0 && "REM instruction unimplemented for the SPARC.");
1611     break;
1612
1613   case  38:     // reg:   And(reg, reg)
1614   case 238:     // reg:   And(reg, Constant)
1615     mvec[0] = new MachineInstr(AND);
1616     Set3OperandsFromInstr(mvec[0], subtreeRoot, target);
1617     break;
1618
1619   case 138:     // reg:   And(reg, not)
1620     mvec[0] = new MachineInstr(ANDN);
1621     Set3OperandsFromInstr(mvec[0], subtreeRoot, target);
1622     break;
1623
1624   case  39:     // reg:   Or(reg, reg)
1625   case 239:     // reg:   Or(reg, Constant)
1626     mvec[0] = new MachineInstr(ORN);
1627     Set3OperandsFromInstr(mvec[0], subtreeRoot, target);
1628     break;
1629
1630   case 139:     // reg:   Or(reg, not)
1631     mvec[0] = new MachineInstr(ORN);
1632     Set3OperandsFromInstr(mvec[0], subtreeRoot, target);
1633     break;
1634
1635   case  40:     // reg:   Xor(reg, reg)
1636   case 240:     // reg:   Xor(reg, Constant)
1637     mvec[0] = new MachineInstr(XOR);
1638     Set3OperandsFromInstr(mvec[0], subtreeRoot, target);
1639     break;
1640
1641   case 140:     // reg:   Xor(reg, not)
1642     mvec[0] = new MachineInstr(XNOR);
1643     Set3OperandsFromInstr(mvec[0], subtreeRoot, target);
1644     break;
1645
1646   case 41:      // boolconst:   SetCC(reg, Constant)
1647     // Check if this is an integer comparison, and
1648     // there is a parent, and the parent decided to use
1649     // a branch-on-integer-register instead of branch-on-condition-code.
1650     // If so, the SUBcc instruction is not required.
1651     // (However, we must still check for constants to be loaded from
1652     // the constant pool so that such a load can be associated with
1653     // this instruction.)
1654     //
1655     // Otherwise this is just the same as case 42, so just fall through.
1656     //
1657     if (subtreeRoot->leftChild()->getValue()->getType()->isIntegral() &&
1658         subtreeRoot->parent() != NULL)
1659       {
1660         InstructionNode* parentNode = (InstructionNode*) subtreeRoot->parent();
1661         assert(parentNode->getNodeType() == InstrTreeNode::NTInstructionNode);
1662         const vector<MachineInstr*>&
1663           minstrVec = parentNode->getInstruction()->getMachineInstrVec();
1664         MachineOpCode parentOpCode;
1665         if (parentNode->getInstruction()->getOpcode() == Instruction::Br &&
1666             (parentOpCode = minstrVec[0]->getOpCode()) >= BRZ &&
1667             parentOpCode <= BRGEZ)
1668           {
1669             numInstr = 0;               // don't forward the operand!
1670             break;
1671           }
1672       }
1673     // ELSE FALL THROUGH
1674
1675   case 42:      // bool:   SetCC(reg, reg):
1676   {
1677     // If result of the SetCC is only used for a branch, we can
1678     // discard the result. otherwise, it must go into an integer register.
1679     // Note that the user may or may not be in the same tree, so we have
1680     // to follow SSA def-use edges here, not BURG tree edges.
1681     //
1682     Instruction* result = subtreeRoot->getInstruction();
1683     Value* firstUse = result->use_empty() ? 0 : *result->use_begin();
1684     bool discardResult =
1685       (result->use_size() == 1
1686        && firstUse->isInstruction()
1687        && ((Instruction*) firstUse)->getOpcode() == Instruction::Br);
1688
1689     bool mustClearReg;
1690     int valueToMove;
1691     MachineOpCode movOpCode;
1692
1693     if (subtreeRoot->leftChild()->getValue()->getType()->isIntegral() ||
1694         subtreeRoot->leftChild()->getValue()->getType()->isPointerType())
1695       {
1696         // integer condition: destination should be %g0 or integer register
1697         // if result must be saved but condition is not SetEQ then we need
1698         // a separate instruction to compute the bool result, so discard
1699         // result of SUBcc instruction anyway.
1700         //
1701         mvec[0] = new MachineInstr(SUBcc);
1702         Set3OperandsFromInstr(mvec[0], subtreeRoot, target, discardResult);
1703
1704         // mark the 4th operand as being a CC register, and a "result"
1705         mvec[0]->SetMachineOperand(3, MachineOperand::MO_CCRegister,
1706                                       subtreeRoot->getValue(), /*def*/ true);
1707
1708         if (!discardResult)
1709           { // recompute bool if needed, using the integer condition codes
1710             if (result->getOpcode() == Instruction::SetNE)
1711               discardResult = true;
1712             else
1713               movOpCode =
1714                 ChooseMovpccAfterSub(subtreeRoot, mustClearReg, valueToMove);
1715           }
1716       }
1717     else
1718       {
1719         // FP condition: dest of FCMP should be some FCCn register
1720         mvec[0] = new MachineInstr(ChooseFcmpInstruction(subtreeRoot));
1721         mvec[0]->SetMachineOperand(0, MachineOperand::MO_CCRegister,
1722                                       subtreeRoot->getValue());
1723         mvec[0]->SetMachineOperand(1, MachineOperand::MO_VirtualRegister,
1724                                       subtreeRoot->leftChild()->getValue());
1725         mvec[0]->SetMachineOperand(2, MachineOperand::MO_VirtualRegister,
1726                                       subtreeRoot->rightChild()->getValue());
1727
1728         if (!discardResult)
1729           {// recompute bool using the FP condition codes
1730             mustClearReg = true;
1731             valueToMove = 1;
1732             movOpCode = ChooseMovFpccInstruction(subtreeRoot);
1733           }
1734       }
1735
1736     if (!discardResult)
1737       {
1738         if (mustClearReg)
1739           {// Unconditionally set register to 0
1740            int n = numInstr++;
1741            mvec[n] = new MachineInstr(SETHI);
1742            mvec[n]->SetMachineOperand(0,MachineOperand::MO_UnextendedImmed,s0);
1743            mvec[n]->SetMachineOperand(1, MachineOperand::MO_VirtualRegister,
1744                                          subtreeRoot->getValue());
1745           }
1746
1747         // Now conditionally move `valueToMove' (0 or 1) into the register
1748         int n = numInstr++;
1749         mvec[n] = new MachineInstr(movOpCode);
1750         mvec[n]->SetMachineOperand(0, MachineOperand::MO_CCRegister,
1751                                       subtreeRoot->getValue());
1752         mvec[n]->SetMachineOperand(1, MachineOperand::MO_UnextendedImmed,
1753                                       valueToMove);
1754         mvec[n]->SetMachineOperand(2, MachineOperand::MO_VirtualRegister,
1755                                       subtreeRoot->getValue());
1756       }
1757     break;
1758   }
1759
1760   case 43:      // boolreg: VReg
1761   case 44:      // boolreg: Constant
1762     numInstr = 0;
1763     break;
1764
1765   case 51:      // reg:   Load(reg)
1766   case 52:      // reg:   Load(ptrreg)
1767   case 53:      // reg:   LoadIdx(reg,reg)
1768   case 54:      // reg:   LoadIdx(ptrreg,reg)
1769     mvec[0] = new MachineInstr(ChooseLoadInstruction(subtreeRoot->getValue()->getType()));
1770     SetOperandsForMemInstr(mvec[0], subtreeRoot, target);
1771     break;
1772
1773   case 55:      // reg:   GetElemPtr(reg)
1774   case 56:      // reg:   GetElemPtrIdx(reg,reg)
1775     if (subtreeRoot->parent() != NULL)
1776       {
1777         // Check if the parent was an array access.
1778         // If so, we still need to generate this instruction.
1779         MemAccessInst* memInst =(MemAccessInst*) subtreeRoot->getInstruction();
1780         const PointerType* ptrType =
1781           (const PointerType*) memInst->getPtrOperand()->getType();
1782         if (! ptrType->getValueType()->isArrayType())
1783           {// we don't need a separate instr
1784             numInstr = 0;               // don't forward operand!
1785             break;
1786           }
1787       }
1788     // else in all other cases we need to a separate ADD instruction
1789     mvec[0] = new MachineInstr(ADD);
1790     SetOperandsForMemInstr(mvec[0], subtreeRoot, target);
1791     break;
1792
1793   case 57:      // reg:   Alloca: Implement as 2 instructions:
1794                 //      sub %sp, tmp -> %sp
1795     {           //      add %sp, 0   -> result
1796     Instruction* instr = subtreeRoot->getInstruction();
1797     const PointerType* instrType = (const PointerType*) instr->getType();
1798     assert(instrType->isPointerType());
1799     int tsize = (int) target.findOptimalStorageSize(instrType->getValueType());
1800     assert(tsize != 0 && "Just to check when this can happen");
1801     // if (tsize == 0)
1802     //   {
1803         // numInstr = 0;
1804         // break;
1805     // }
1806     //else go on to create the instructions needed...
1807
1808     // Create a temporary Value to hold the constant type-size
1809     ConstPoolSInt* valueForTSize = ConstPoolSInt::get(Type::IntTy, tsize);
1810
1811     // Instruction 1: sub %sp, tsize -> %sp
1812     // tsize is always constant, but it may have to be put into a
1813     // register if it doesn't fit in the immediate field.
1814     //
1815     mvec[0] = new MachineInstr(SUB);
1816     mvec[0]->SetMachineOperand(0, /*regNum %sp = o6 = r[14]*/(unsigned int)14);
1817     mvec[0]->SetMachineOperand(1, MachineOperand::MO_VirtualRegister, valueForTSize);
1818     mvec[0]->SetMachineOperand(2, /*regNum %sp = o6 = r[14]*/(unsigned int)14);
1819
1820     // Instruction 2: add %sp, 0 -> result
1821     numInstr++;
1822     mvec[1] = new MachineInstr(ADD);
1823     mvec[1]->SetMachineOperand(0, /*regNum %sp = o6 = r[14]*/(unsigned int)14);
1824     mvec[1]->SetMachineOperand(1, /*regNum %g0*/ (unsigned int) 0);
1825     mvec[1]->SetMachineOperand(2, MachineOperand::MO_VirtualRegister, instr);
1826     break;
1827     }
1828
1829   case 58:      // reg:   Alloca(reg): Implement as 3 instructions:
1830                 //      mul num, typeSz -> tmp
1831                 //      sub %sp, tmp    -> %sp
1832     {           //      add %sp, 0      -> result
1833     Instruction* instr = subtreeRoot->getInstruction();
1834     const PointerType* instrType = (const PointerType*) instr->getType();
1835     assert(instrType->isPointerType() &&
1836            instrType->getValueType()->isArrayType());
1837     const Type* eltType =
1838       ((ArrayType*) instrType->getValueType())->getElementType();
1839     int tsize = (int) target.findOptimalStorageSize(eltType);
1840
1841     assert(tsize != 0 && "Just to check when this can happen");
1842     // if (tsize == 0)
1843       // {
1844         // numInstr = 0;
1845         // break;
1846       // }
1847     //else go on to create the instructions needed...
1848
1849     // Create a temporary Value to hold the constant type-size
1850     ConstPoolSInt* valueForTSize = ConstPoolSInt::get(Type::IntTy, tsize);
1851
1852     // Create a temporary value to hold `tmp'
1853     Instruction* tmpInstr = new TmpInstruction(Instruction::UserOp1,
1854                                           subtreeRoot->leftChild()->getValue(),
1855                                           NULL /*could insert tsize here*/);
1856     subtreeRoot->getInstruction()->getMachineInstrVec().addTempValue(tmpInstr);
1857
1858     // Instruction 1: mul numElements, typeSize -> tmp
1859     mvec[0] = new MachineInstr(MULX);
1860     mvec[0]->SetMachineOperand(0, MachineOperand::MO_VirtualRegister,
1861                                 subtreeRoot->leftChild()->getValue());
1862     mvec[0]->SetMachineOperand(1, MachineOperand::MO_VirtualRegister, valueForTSize);
1863     mvec[0]->SetMachineOperand(2, MachineOperand::MO_VirtualRegister,tmpInstr);
1864
1865     tmpInstr->addMachineInstruction(mvec[0]);
1866
1867     // Instruction 2: sub %sp, tmp -> %sp
1868     numInstr++;
1869     mvec[1] = new MachineInstr(SUB);
1870     mvec[1]->SetMachineOperand(0, /*regNum %sp = o6 = r[14]*/(unsigned int)14);
1871     mvec[1]->SetMachineOperand(1, MachineOperand::MO_VirtualRegister,tmpInstr);
1872     mvec[1]->SetMachineOperand(2, /*regNum %sp = o6 = r[14]*/(unsigned int)14);
1873
1874     // Instruction 3: add %sp, 0 -> result
1875     numInstr++;
1876     mvec[2] = new MachineInstr(ADD);
1877     mvec[2]->SetMachineOperand(0, /*regNum %sp = o6 = r[14]*/(unsigned int)14);
1878     mvec[2]->SetMachineOperand(1, /*regNum %g0*/ (unsigned int) 0);
1879     mvec[2]->SetMachineOperand(2, MachineOperand::MO_VirtualRegister, instr);
1880     break;
1881     }
1882
1883   case 61:      // reg:   Call
1884                 // Generate a call-indirect (i.e., JMPL) for now to expose
1885                 // the potential need for registers.  If an absolute address
1886                 // is available, replace this with a CALL instruction.
1887                 // Mark both the indirection register and the return-address
1888     {           // register as hidden virtual registers.
1889
1890     Instruction* jmpAddrReg = new TmpInstruction(Instruction::UserOp1,
1891         ((CallInst*) subtreeRoot->getInstruction())->getCalledMethod(), NULL);
1892     Instruction* retAddrReg = new TmpInstruction(Instruction::UserOp1,
1893                                              subtreeRoot->getValue(), NULL);
1894     subtreeRoot->getInstruction()->getMachineInstrVec().addTempValue(jmpAddrReg);
1895     subtreeRoot->getInstruction()->getMachineInstrVec().addTempValue(retAddrReg);
1896
1897     mvec[0] = new MachineInstr(JMPL);
1898     mvec[0]->SetMachineOperand(0, MachineOperand::MO_VirtualRegister, jmpAddrReg);
1899     mvec[0]->SetMachineOperand(1, MachineOperand::MO_SignExtendedImmed,
1900                                   (int64_t) 0);
1901     mvec[0]->SetMachineOperand(2, MachineOperand::MO_VirtualRegister, retAddrReg);
1902
1903     // NOTE: jmpAddrReg will be loaded by a different instruction generated
1904     //       by the final code generator, so we just mark the CALL instruction
1905     //       as computing that value.
1906     //       The retAddrReg is actually computed by the CALL instruction.
1907     //
1908     jmpAddrReg->addMachineInstruction(mvec[0]);
1909     retAddrReg->addMachineInstruction(mvec[0]);
1910
1911     mvec[numInstr++] = new MachineInstr(NOP); // delay slot
1912     break;
1913     }
1914
1915   case 62:      // reg:   Shl(reg, reg)
1916     opType = subtreeRoot->leftChild()->getValue()->getType();
1917     assert(opType->isIntegral() || opType == Type::BoolTy);
1918     mvec[0] = new MachineInstr((opType == Type::LongTy)? SLLX : SLL);
1919     Set3OperandsFromInstr(mvec[0], subtreeRoot, target);
1920     break;
1921
1922   case 63:      // reg:   Shr(reg, reg)
1923     opType = subtreeRoot->leftChild()->getValue()->getType();
1924     assert(opType->isIntegral() || opType == Type::BoolTy);
1925     mvec[0] = new MachineInstr((opType->isSigned()
1926                                 ? ((opType == Type::LongTy)? SRAX : SRA)
1927                                 : ((opType == Type::LongTy)? SRLX : SRL)));
1928     Set3OperandsFromInstr(mvec[0], subtreeRoot, target);
1929     break;
1930
1931   case 64:      // reg:   Phi(reg,reg)
1932   {             // This instruction has variable #operands, so resultPos is 0.
1933     Instruction* phi = subtreeRoot->getInstruction();
1934     mvec[0] = new MachineInstr(PHI, 1 + phi->getNumOperands());
1935     mvec[0]->SetMachineOperand(0, MachineOperand::MO_VirtualRegister,
1936                                   subtreeRoot->getValue());
1937     for (unsigned i=0, N=phi->getNumOperands(); i < N; i++)
1938       mvec[0]->SetMachineOperand(i+1, MachineOperand::MO_VirtualRegister,
1939                                       phi->getOperand(i));
1940     break;
1941   }
1942   case 71:      // reg:     VReg
1943   case 72:      // reg:     Constant
1944     numInstr = 0;                       // don't forward the value
1945     break;
1946
1947   case 111:     // stmt:  reg
1948   case 112:     // stmt:  boolconst
1949   case 113:     // stmt:  bool
1950   case 121:
1951   case 122:
1952   case 123:
1953   case 124:
1954   case 125:
1955   case 126:
1956   case 127:
1957   case 128:
1958   case 129:
1959   case 130:
1960   case 131:
1961   case 132:
1962   case 153:
1963   case 155:
1964     //
1965     // These are all chain rules, which have a single nonterminal on the RHS.
1966     // Get the rule that matches the RHS non-terminal and use that instead.
1967     //
1968     assert(ThisIsAChainRule(ruleForNode));
1969     assert(nts[0] && ! nts[1]
1970            && "A chain rule should have only one RHS non-terminal!");
1971     nextRule = burm_rule(subtreeRoot->state, nts[0]);
1972     nts = burm_nts[nextRule];
1973     numInstr = GetInstructionsByRule(subtreeRoot, nextRule, nts,target,mvec);
1974     break;
1975
1976   default:
1977     assert(0 && "Unrecognized BURG rule");
1978     numInstr = 0;
1979     break;
1980   }
1981
1982   if (forwardOperandNum >= 0)
1983     { // We did not generate a machine instruction but need to use operand.
1984       // If user is in the same tree, replace Value in its machine operand.
1985       // If not, insert a copy instruction which should get coalesced away
1986       // by register allocation.
1987       if (subtreeRoot->parent() != NULL)
1988         ForwardOperand(subtreeRoot, (InstructionNode*) subtreeRoot->parent(),
1989                        forwardOperandNum);
1990       else
1991         {
1992           int n = numInstr++;
1993           mvec[n] = new MachineInstr(ADD);
1994           mvec[n]->SetMachineOperand(0, MachineOperand::MO_VirtualRegister,
1995                 subtreeRoot->getInstruction()->getOperand(forwardOperandNum));
1996           mvec[n]->SetMachineOperand(1, /*regNum %g0*/ (unsigned int) 0);
1997           mvec[n]->SetMachineOperand(2, MachineOperand::MO_VirtualRegister,
1998                                         subtreeRoot->getInstruction());
1999         }
2000     }
2001
2002   if (! ThisIsAChainRule(ruleForNode))
2003     numInstr = FixConstantOperands(subtreeRoot, mvec, numInstr, target);
2004
2005   return numInstr;
2006 }
2007
2008