lib/Target/SparcV9/SparcV9InstrSelection.cpp

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