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