lib/Target/SparcV9/SparcV9InstrSelection.cpp

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