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