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