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