lib/Target/SparcV9/SparcV9InstrSelection.cpp

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