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