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