lib/Target/SparcV9/SparcV9InstrSelection.cpp

   1 //===-- SparcInstrSelection.cpp -------------------------------------------===//
   2 //
   3 //  BURS instruction selection for SPARC V9 architecture.
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #include "SparcInternals.h"
   8 #include "SparcInstrSelectionSupport.h"
   9 #include "SparcRegClassInfo.h"
  10 #include "llvm/CodeGen/InstrSelectionSupport.h"
  11 #include "llvm/CodeGen/MachineInstrBuilder.h"
  12 #include "llvm/CodeGen/MachineInstrAnnot.h"
  13 #include "llvm/CodeGen/InstrForest.h"
  14 #include "llvm/CodeGen/InstrSelection.h"
  15 #include "llvm/CodeGen/MachineFunction.h"
  16 #include "llvm/CodeGen/MachineFunctionInfo.h"
  17 #include "llvm/CodeGen/MachineCodeForInstruction.h"
  18 #include "llvm/DerivedTypes.h"
  19 #include "llvm/iTerminators.h"
  20 #include "llvm/iMemory.h"
  21 #include "llvm/iOther.h"
  22 #include "llvm/Function.h"
  23 #include "llvm/Constants.h"
  24 #include "llvm/ConstantHandling.h"
  25 #include "Support/MathExtras.h"
  26 #include <math.h>
  27 using std::vector;
  28
  29 static inline void Add3OperandInstr(unsigned Opcode, InstructionNode* Node,
  30                                     vector<MachineInstr*>& mvec) {
  31   mvec.push_back(BuildMI(Opcode, 3).addReg(Node->leftChild()->getValue())
  32                                    .addReg(Node->rightChild()->getValue())
  33                                    .addRegDef(Node->getValue()));
  34 }
  35
  36
  37
  38
  39 //************************ Internal Functions ******************************/
  40
  41
  42 static inline MachineOpCode
  43 ChooseBprInstruction(const InstructionNode* instrNode)
  44 {
  45   MachineOpCode opCode;
  46
  47   Instruction* setCCInstr =
  48     ((InstructionNode*) instrNode->leftChild())->getInstruction();
  49
  50   switch(setCCInstr->getOpcode())
  51     {
  52     case Instruction::SetEQ: opCode = BRZ;   break;
  53     case Instruction::SetNE: opCode = BRNZ;  break;
  54     case Instruction::SetLE: opCode = BRLEZ; break;
  55     case Instruction::SetGE: opCode = BRGEZ; break;
  56     case Instruction::SetLT: opCode = BRLZ;  break;
  57     case Instruction::SetGT: opCode = BRGZ;  break;
  58     default:
  59       assert(0 && "Unrecognized VM instruction!");
  60       opCode = INVALID_OPCODE;
  61       break;
  62     }
  63
  64   return opCode;
  65 }
  66
  67
  68 static inline MachineOpCode
  69 ChooseBpccInstruction(const InstructionNode* instrNode,
  70                       const BinaryOperator* setCCInstr)
  71 {
  72   MachineOpCode opCode = INVALID_OPCODE;
  73
  74   bool isSigned = setCCInstr->getOperand(0)->getType()->isSigned();
  75
  76   if (isSigned)
  77     {
  78       switch(setCCInstr->getOpcode())
  79         {
  80         case Instruction::SetEQ: opCode = BE;  break;
  81         case Instruction::SetNE: opCode = BNE; break;
  82         case Instruction::SetLE: opCode = BLE; break;
  83         case Instruction::SetGE: opCode = BGE; break;
  84         case Instruction::SetLT: opCode = BL;  break;
  85         case Instruction::SetGT: opCode = BG;  break;
  86         default:
  87           assert(0 && "Unrecognized VM instruction!");
  88           break;
  89         }
  90     }
  91   else
  92     {
  93       switch(setCCInstr->getOpcode())
  94         {
  95         case Instruction::SetEQ: opCode = BE;   break;
  96         case Instruction::SetNE: opCode = BNE;  break;
  97         case Instruction::SetLE: opCode = BLEU; break;
  98         case Instruction::SetGE: opCode = BCC;  break;
  99         case Instruction::SetLT: opCode = BCS;  break;
 100         case Instruction::SetGT: opCode = BGU;  break;
 101         default:
 102           assert(0 && "Unrecognized VM instruction!");
 103           break;
 104         }
 105     }
 106
 107   return opCode;
 108 }
 109
 110 static inline MachineOpCode
 111 ChooseBFpccInstruction(const InstructionNode* instrNode,
 112                        const BinaryOperator* setCCInstr)
 113 {
 114   MachineOpCode opCode = INVALID_OPCODE;
 115
 116   switch(setCCInstr->getOpcode())
 117     {
 118     case Instruction::SetEQ: opCode = FBE;  break;
 119     case Instruction::SetNE: opCode = FBNE; break;
 120     case Instruction::SetLE: opCode = FBLE; break;
 121     case Instruction::SetGE: opCode = FBGE; break;
 122     case Instruction::SetLT: opCode = FBL;  break;
 123     case Instruction::SetGT: opCode = FBG;  break;
 124     default:
 125       assert(0 && "Unrecognized VM instruction!");
 126       break;
 127     }
 128
 129   return opCode;
 130 }
 131
 132
 133 // Create a unique TmpInstruction for a boolean value,
 134 // representing the CC register used by a branch on that value.
 135 // For now, hack this using a little static cache of TmpInstructions.
 136 // Eventually the entire BURG instruction selection should be put
 137 // into a separate class that can hold such information.
 138 // The static cache is not too bad because the memory for these
 139 // TmpInstructions will be freed along with the rest of the Function anyway.
 140 //
 141 static TmpInstruction*
 142 GetTmpForCC(Value* boolVal, const Function *F, const Type* ccType)
 143 {
 144   typedef hash_map<const Value*, TmpInstruction*> BoolTmpCache;
 145   static BoolTmpCache boolToTmpCache;     // Map boolVal -> TmpInstruction*
 146   static const Function *lastFunction = 0;// Use to flush cache between funcs
 147
 148   assert(boolVal->getType() == Type::BoolTy && "Weird but ok! Delete assert");
 149
 150   if (lastFunction != F)
 151     {
 152       lastFunction = F;
 153       boolToTmpCache.clear();
 154     }
 155
 156   // Look for tmpI and create a new one otherwise.  The new value is
 157   // directly written to map using the ref returned by operator[].
 158   TmpInstruction*& tmpI = boolToTmpCache[boolVal];
 159   if (tmpI == NULL)
 160     tmpI = new TmpInstruction(ccType, boolVal);
 161
 162   return tmpI;
 163 }
 164
 165
 166 static inline MachineOpCode
 167 ChooseBccInstruction(const InstructionNode* instrNode,
 168                      bool& isFPBranch)
 169 {
 170   InstructionNode* setCCNode = (InstructionNode*) instrNode->leftChild();
 171   assert(setCCNode->getOpLabel() == SetCCOp);
 172   BinaryOperator* setCCInstr =cast<BinaryOperator>(setCCNode->getInstruction());
 173   const Type* setCCType = setCCInstr->getOperand(0)->getType();
 174
 175   isFPBranch = setCCType->isFloatingPoint(); // Return value: don't delete!
 176
 177   if (isFPBranch)
 178     return ChooseBFpccInstruction(instrNode, setCCInstr);
 179   else
 180     return ChooseBpccInstruction(instrNode, setCCInstr);
 181 }
 182
 183
 184 static inline MachineOpCode
 185 ChooseMovFpccInstruction(const InstructionNode* instrNode)
 186 {
 187   MachineOpCode opCode = INVALID_OPCODE;
 188
 189   switch(instrNode->getInstruction()->getOpcode())
 190     {
 191     case Instruction::SetEQ: opCode = MOVFE;  break;
 192     case Instruction::SetNE: opCode = MOVFNE; break;
 193     case Instruction::SetLE: opCode = MOVFLE; break;
 194     case Instruction::SetGE: opCode = MOVFGE; break;
 195     case Instruction::SetLT: opCode = MOVFL;  break;
 196     case Instruction::SetGT: opCode = MOVFG;  break;
 197     default:
 198       assert(0 && "Unrecognized VM instruction!");
 199       break;
 200     }
 201
 202   return opCode;
 203 }
 204
 205
 206 // Assumes that SUBcc v1, v2 -> v3 has been executed.
 207 // In most cases, we want to clear v3 and then follow it by instruction
 208 // MOVcc 1 -> v3.
 209 // Set mustClearReg=false if v3 need not be cleared before conditional move.
 210 // Set valueToMove=0 if we want to conditionally move 0 instead of 1
 211 //                      (i.e., we want to test inverse of a condition)
 212 // (The latter two cases do not seem to arise because SetNE needs nothing.)
 213 //
 214 static MachineOpCode
 215 ChooseMovpccAfterSub(const InstructionNode* instrNode,
 216                      bool& mustClearReg,
 217                      int& valueToMove)
 218 {
 219   MachineOpCode opCode = INVALID_OPCODE;
 220   mustClearReg = true;
 221   valueToMove = 1;
 222
 223   switch(instrNode->getInstruction()->getOpcode())
 224     {
 225     case Instruction::SetEQ: opCode = MOVE;  break;
 226     case Instruction::SetLE: opCode = MOVLE; break;
 227     case Instruction::SetGE: opCode = MOVGE; break;
 228     case Instruction::SetLT: opCode = MOVL;  break;
 229     case Instruction::SetGT: opCode = MOVG;  break;
 230     case Instruction::SetNE: assert(0 && "No move required!"); break;
 231     default:                 assert(0 && "Unrecognized VM instr!"); break;
 232     }
 233
 234   return opCode;
 235 }
 236
 237 static inline MachineOpCode
 238 ChooseConvertToFloatInstr(OpLabel vopCode, const Type* opType)
 239 {
 240   MachineOpCode opCode = INVALID_OPCODE;
 241
 242   switch(vopCode)
 243     {
 244     case ToFloatTy:
 245       if (opType == Type::SByteTy || opType == Type::ShortTy || opType == Type::IntTy)
 246         opCode = FITOS;
 247       else if (opType == Type::LongTy)
 248         opCode = FXTOS;
 249       else if (opType == Type::DoubleTy)
 250         opCode = FDTOS;
 251       else if (opType == Type::FloatTy)
 252         ;
 253       else
 254         assert(0 && "Cannot convert this type to FLOAT on SPARC");
 255       break;
 256
 257     case ToDoubleTy:
 258       // This is usually used in conjunction with CreateCodeToCopyIntToFloat().
 259       // Both functions should treat the integer as a 32-bit value for types
 260       // of 4 bytes or less, and as a 64-bit value otherwise.
 261       if (opType == Type::SByteTy || opType == Type::UByteTy ||
 262           opType == Type::ShortTy || opType == Type::UShortTy ||
 263           opType == Type::IntTy   || opType == Type::UIntTy)
 264         opCode = FITOD;
 265       else if (opType == Type::LongTy || opType == Type::ULongTy)
 266         opCode = FXTOD;
 267       else if (opType == Type::FloatTy)
 268         opCode = FSTOD;
 269       else if (opType == Type::DoubleTy)
 270         ;
 271       else
 272         assert(0 && "Cannot convert this type to DOUBLE on SPARC");
 273       break;
 274
 275     default:
 276       break;
 277     }
 278
 279   return opCode;
 280 }
 281
 282 static inline MachineOpCode
 283 ChooseConvertFPToIntInstr(Type::PrimitiveID tid, const Type* opType)
 284 {
 285   MachineOpCode opCode = INVALID_OPCODE;;
 286
 287   assert((opType == Type::FloatTy || opType == Type::DoubleTy)
 288          && "This function should only be called for FLOAT or DOUBLE");
 289
 290   if (tid==Type::UIntTyID)
 291     {
 292       assert(tid != Type::UIntTyID && "FP-to-uint conversions must be expanded"
 293              " into FP->long->uint for SPARC v9:  SO RUN PRESELECTION PASS!");
 294     }
 295   else if (tid==Type::SByteTyID || tid==Type::ShortTyID || tid==Type::IntTyID ||
 296            tid==Type::UByteTyID || tid==Type::UShortTyID)
 297     {
 298       opCode = (opType == Type::FloatTy)? FSTOI : FDTOI;
 299     }
 300   else if (tid==Type::LongTyID || tid==Type::ULongTyID)
 301     {
 302       opCode = (opType == Type::FloatTy)? FSTOX : FDTOX;
 303     }
 304   else
 305       assert(0 && "Should not get here, Mo!");
 306
 307   return opCode;
 308 }
 309
 310 MachineInstr*
 311 CreateConvertFPToIntInstr(Type::PrimitiveID destTID,
 312                           Value* srcVal, Value* destVal)
 313 {
 314   MachineOpCode opCode = ChooseConvertFPToIntInstr(destTID, srcVal->getType());
 315   assert(opCode != INVALID_OPCODE && "Expected to need conversion!");
 316   return BuildMI(opCode, 2).addReg(srcVal).addRegDef(destVal);
 317 }
 318
 319 // CreateCodeToConvertFloatToInt: Convert FP value to signed or unsigned integer
 320 // The FP value must be converted to the dest type in an FP register,
 321 // and the result is then copied from FP to int register via memory.
 322 //
 323 // Since fdtoi converts to signed integers, any FP value V between MAXINT+1
 324 // and MAXUNSIGNED (i.e., 2^31 <= V <= 2^32-1) would be converted incorrectly
 325 // *only* when converting to an unsigned.  (Unsigned byte, short or long
 326 // don't have this problem.)
 327 // For unsigned int, we therefore have to generate the code sequence:
 328 //
 329 //      if (V > (float) MAXINT) {
 330 //        unsigned result = (unsigned) (V  - (float) MAXINT);
 331 //        result = result + (unsigned) MAXINT;
 332 //      }
 333 //      else
 334 //        result = (unsigned) V;
 335 //
 336 static void
 337 CreateCodeToConvertFloatToInt(const TargetMachine& target,
 338                               Value* opVal,
 339                               Instruction* destI,
 340                               std::vector<MachineInstr*>& mvec,
 341                               MachineCodeForInstruction& mcfi)
 342 {
 343   // Create a temporary to represent the FP register into which the
 344   // int value will placed after conversion.  The type of this temporary
 345   // depends on the type of FP register to use: single-prec for a 32-bit
 346   // int or smaller; double-prec for a 64-bit int.
 347   //
 348   size_t destSize = target.getTargetData().getTypeSize(destI->getType());
 349   const Type* destTypeToUse = (destSize > 4)? Type::DoubleTy : Type::FloatTy;
 350   TmpInstruction* destForCast = new TmpInstruction(destTypeToUse, opVal);
 351   mcfi.addTemp(destForCast);
 352
 353   // Create the fp-to-int conversion code
 354   MachineInstr* M =CreateConvertFPToIntInstr(destI->getType()->getPrimitiveID(),
 355                                              opVal, destForCast);
 356   mvec.push_back(M);
 357
 358   // Create the fpreg-to-intreg copy code
 359   target.getInstrInfo().
 360     CreateCodeToCopyFloatToInt(target, destI->getParent()->getParent(),
 361                                destForCast, destI, mvec, mcfi);
 362 }
 363
 364
 365 static inline MachineOpCode
 366 ChooseAddInstruction(const InstructionNode* instrNode)
 367 {
 368   return ChooseAddInstructionByType(instrNode->getInstruction()->getType());
 369 }
 370
 371
 372 static inline MachineInstr*
 373 CreateMovFloatInstruction(const InstructionNode* instrNode,
 374                           const Type* resultType)
 375 {
 376   return BuildMI((resultType == Type::FloatTy) ? FMOVS : FMOVD, 2)
 377                    .addReg(instrNode->leftChild()->getValue())
 378                    .addRegDef(instrNode->getValue());
 379 }
 380
 381 static inline MachineInstr*
 382 CreateAddConstInstruction(const InstructionNode* instrNode)
 383 {
 384   MachineInstr* minstr = NULL;
 385
 386   Value* constOp = ((InstrTreeNode*) instrNode->rightChild())->getValue();
 387   assert(isa<Constant>(constOp));
 388
 389   // Cases worth optimizing are:
 390   // (1) Add with 0 for float or double: use an FMOV of appropriate type,
 391   //     instead of an FADD (1 vs 3 cycles).  There is no integer MOV.
 392   //
 393   if (ConstantFP *FPC = dyn_cast<ConstantFP>(constOp)) {
 394       double dval = FPC->getValue();
 395       if (dval == 0.0)
 396         minstr = CreateMovFloatInstruction(instrNode,
 397                                    instrNode->getInstruction()->getType());
 398     }
 399
 400   return minstr;
 401 }
 402
 403
 404 static inline MachineOpCode
 405 ChooseSubInstructionByType(const Type* resultType)
 406 {
 407   MachineOpCode opCode = INVALID_OPCODE;
 408
 409   if (resultType->isInteger() || isa<PointerType>(resultType))
 410     {
 411       opCode = SUB;
 412     }
 413   else
 414     switch(resultType->getPrimitiveID())
 415       {
 416       case Type::FloatTyID:  opCode = FSUBS; break;
 417       case Type::DoubleTyID: opCode = FSUBD; break;
 418       default: assert(0 && "Invalid type for SUB instruction"); break;
 419       }
 420
 421   return opCode;
 422 }
 423
 424
 425 static inline MachineInstr*
 426 CreateSubConstInstruction(const InstructionNode* instrNode)
 427 {
 428   MachineInstr* minstr = NULL;
 429
 430   Value* constOp = ((InstrTreeNode*) instrNode->rightChild())->getValue();
 431   assert(isa<Constant>(constOp));
 432
 433   // Cases worth optimizing are:
 434   // (1) Sub with 0 for float or double: use an FMOV of appropriate type,
 435   //     instead of an FSUB (1 vs 3 cycles).  There is no integer MOV.
 436   //
 437   if (ConstantFP *FPC = dyn_cast<ConstantFP>(constOp)) {
 438     double dval = FPC->getValue();
 439     if (dval == 0.0)
 440       minstr = CreateMovFloatInstruction(instrNode,
 441                                         instrNode->getInstruction()->getType());
 442   }
 443
 444   return minstr;
 445 }
 446
 447
 448 static inline MachineOpCode
 449 ChooseFcmpInstruction(const InstructionNode* instrNode)
 450 {
 451   MachineOpCode opCode = INVALID_OPCODE;
 452
 453   Value* operand = ((InstrTreeNode*) instrNode->leftChild())->getValue();
 454   switch(operand->getType()->getPrimitiveID()) {
 455   case Type::FloatTyID:  opCode = FCMPS; break;
 456   case Type::DoubleTyID: opCode = FCMPD; break;
 457   default: assert(0 && "Invalid type for FCMP instruction"); break;
 458   }
 459
 460   return opCode;
 461 }
 462
 463
 464 // Assumes that leftArg and rightArg are both cast instructions.
 465 //
 466 static inline bool
 467 BothFloatToDouble(const InstructionNode* instrNode)
 468 {
 469   InstrTreeNode* leftArg = instrNode->leftChild();
 470   InstrTreeNode* rightArg = instrNode->rightChild();
 471   InstrTreeNode* leftArgArg = leftArg->leftChild();
 472   InstrTreeNode* rightArgArg = rightArg->leftChild();
 473   assert(leftArg->getValue()->getType() == rightArg->getValue()->getType());
 474
 475   // Check if both arguments are floats cast to double
 476   return (leftArg->getValue()->getType() == Type::DoubleTy &&
 477           leftArgArg->getValue()->getType() == Type::FloatTy &&
 478           rightArgArg->getValue()->getType() == Type::FloatTy);
 479 }
 480
 481
 482 static inline MachineOpCode
 483 ChooseMulInstructionByType(const Type* resultType)
 484 {
 485   MachineOpCode opCode = INVALID_OPCODE;
 486
 487   if (resultType->isInteger())
 488     opCode = MULX;
 489   else
 490     switch(resultType->getPrimitiveID())
 491       {
 492       case Type::FloatTyID:  opCode = FMULS; break;
 493       case Type::DoubleTyID: opCode = FMULD; break;
 494       default: assert(0 && "Invalid type for MUL instruction"); break;
 495       }
 496
 497   return opCode;
 498 }
 499
 500
 501
 502 static inline MachineInstr*
 503 CreateIntNegInstruction(const TargetMachine& target,
 504                         Value* vreg)
 505 {
 506   return BuildMI(SUB, 3).addMReg(target.getRegInfo().getZeroRegNum())
 507                         .addReg(vreg).addRegDef(vreg);
 508 }
 509
 510
 511 // Create instruction sequence for any shift operation.
 512 // SLL or SLLX on an operand smaller than the integer reg. size (64bits)
 513 // requires a second instruction for explicit sign-extension.
 514 // Note that we only have to worry about a sign-bit appearing in the
 515 // most significant bit of the operand after shifting (e.g., bit 32 of
 516 // Int or bit 16 of Short), so we do not have to worry about results
 517 // that are as large as a normal integer register.
 518 //
 519 static inline void
 520 CreateShiftInstructions(const TargetMachine& target,
 521                         Function* F,
 522                         MachineOpCode shiftOpCode,
 523                         Value* argVal1,
 524                         Value* optArgVal2, /* Use optArgVal2 if not NULL */
 525                         unsigned optShiftNum, /* else use optShiftNum */
 526                         Instruction* destVal,
 527                         vector<MachineInstr*>& mvec,
 528                         MachineCodeForInstruction& mcfi)
 529 {
 530   assert((optArgVal2 != NULL || optShiftNum <= 64) &&
 531          "Large shift sizes unexpected, but can be handled below: "
 532          "You need to check whether or not it fits in immed field below");
 533
 534   // If this is a logical left shift of a type smaller than the standard
 535   // integer reg. size, we have to extend the sign-bit into upper bits
 536   // of dest, so we need to put the result of the SLL into a temporary.
 537   //
 538   Value* shiftDest = destVal;
 539   unsigned opSize = target.getTargetData().getTypeSize(argVal1->getType());
 540   if ((shiftOpCode == SLL || shiftOpCode == SLLX)
 541       && opSize < target.getTargetData().getIntegerRegize())
 542     { // put SLL result into a temporary
 543       shiftDest = new TmpInstruction(argVal1, optArgVal2, "sllTmp");
 544       mcfi.addTemp(shiftDest);
 545     }
 546
 547   MachineInstr* M = (optArgVal2 != NULL)
 548     ? BuildMI(shiftOpCode, 3).addReg(argVal1).addReg(optArgVal2)
 549                              .addReg(shiftDest, MOTy::Def)
 550     : BuildMI(shiftOpCode, 3).addReg(argVal1).addZImm(optShiftNum)
 551                              .addReg(shiftDest, MOTy::Def);
 552   mvec.push_back(M);
 553
 554   if (shiftDest != destVal)
 555     { // extend the sign-bit of the result into all upper bits of dest
 556       assert(8*opSize <= 32 && "Unexpected type size > 4 and < IntRegSize?");
 557       target.getInstrInfo().
 558         CreateSignExtensionInstructions(target, F, shiftDest, destVal,
 559                                         8*opSize, mvec, mcfi);
 560     }
 561 }
 562
 563
 564 // Does not create any instructions if we cannot exploit constant to
 565 // create a cheaper instruction.
 566 // This returns the approximate cost of the instructions generated,
 567 // which is used to pick the cheapest when both operands are constant.
 568 static inline unsigned
 569 CreateMulConstInstruction(const TargetMachine &target, Function* F,
 570                           Value* lval, Value* rval, Instruction* destVal,
 571                           vector<MachineInstr*>& mvec,
 572                           MachineCodeForInstruction& mcfi)
 573 {
 574   /* Use max. multiply cost, viz., cost of MULX */
 575   unsigned cost = target.getInstrInfo().minLatency(MULX);
 576   unsigned firstNewInstr = mvec.size();
 577
 578   Value* constOp = rval;
 579   if (! isa<Constant>(constOp))
 580     return cost;
 581
 582   // Cases worth optimizing are:
 583   // (1) Multiply by 0 or 1 for any type: replace with copy (ADD or FMOV)
 584   // (2) Multiply by 2^x for integer types: replace with Shift
 585   //
 586   const Type* resultType = destVal->getType();
 587
 588   if (resultType->isInteger() || isa<PointerType>(resultType))
 589     {
 590       bool isValidConst;
 591       int64_t C = GetConstantValueAsSignedInt(constOp, isValidConst);
 592       if (isValidConst)
 593         {
 594           unsigned pow;
 595           bool needNeg = false;
 596           if (C < 0)
 597             {
 598               needNeg = true;
 599               C = -C;
 600             }
 601
 602           if (C == 0 || C == 1) {
 603             cost = target.getInstrInfo().minLatency(ADD);
 604             unsigned Zero = target.getRegInfo().getZeroRegNum();
 605             MachineInstr* M;
 606             if (C == 0)
 607               M = BuildMI(ADD,3).addMReg(Zero).addMReg(Zero).addRegDef(destVal);
 608             else
 609               M = BuildMI(ADD,3).addReg(lval).addMReg(Zero).addRegDef(destVal);
 610             mvec.push_back(M);
 611           }
 612           else if (isPowerOf2(C, pow))
 613             {
 614               unsigned opSize = target.getTargetData().getTypeSize(resultType);
 615               MachineOpCode opCode = (opSize <= 32)? SLL : SLLX;
 616               CreateShiftInstructions(target, F, opCode, lval, NULL, pow,
 617                                       destVal, mvec, mcfi);
 618             }
 619
 620           if (mvec.size() > 0 && needNeg)
 621             { // insert <reg = SUB 0, reg> after the instr to flip the sign
 622               MachineInstr* M = CreateIntNegInstruction(target, destVal);
 623               mvec.push_back(M);
 624             }
 625         }
 626     }
 627   else
 628     {
 629       if (ConstantFP *FPC = dyn_cast<ConstantFP>(constOp))
 630         {
 631           double dval = FPC->getValue();
 632           if (fabs(dval) == 1)
 633             {
 634               MachineOpCode opCode =  (dval < 0)
 635                 ? (resultType == Type::FloatTy? FNEGS : FNEGD)
 636                 : (resultType == Type::FloatTy? FMOVS : FMOVD);
 637               mvec.push_back(BuildMI(opCode,2).addReg(lval).addRegDef(destVal));
 638             }
 639         }
 640     }
 641
 642   if (firstNewInstr < mvec.size())
 643     {
 644       cost = 0;
 645       for (unsigned i=firstNewInstr; i < mvec.size(); ++i)
 646         cost += target.getInstrInfo().minLatency(mvec[i]->getOpCode());
 647     }
 648
 649   return cost;
 650 }
 651
 652
 653 // Does not create any instructions if we cannot exploit constant to
 654 // create a cheaper instruction.
 655 //
 656 static inline void
 657 CreateCheapestMulConstInstruction(const TargetMachine &target,
 658                                   Function* F,
 659                                   Value* lval, Value* rval,
 660                                   Instruction* destVal,
 661                                   vector<MachineInstr*>& mvec,
 662                                   MachineCodeForInstruction& mcfi)
 663 {
 664   Value* constOp;
 665   if (isa<Constant>(lval) && isa<Constant>(rval))
 666     { // both operands are constant: evaluate and "set" in dest
 667       Constant* P = ConstantFoldBinaryInstruction(Instruction::Mul,
 668                                   cast<Constant>(lval), cast<Constant>(rval));
 669       target.getInstrInfo().CreateCodeToLoadConst(target,F,P,destVal,mvec,mcfi);
 670     }
 671   else if (isa<Constant>(rval))         // rval is constant, but not lval
 672     CreateMulConstInstruction(target, F, lval, rval, destVal, mvec, mcfi);
 673   else if (isa<Constant>(lval))         // lval is constant, but not rval
 674     CreateMulConstInstruction(target, F, lval, rval, destVal, mvec, mcfi);
 675
 676   // else neither is constant
 677   return;
 678 }
 679
 680 // Return NULL if we cannot exploit constant to create a cheaper instruction
 681 static inline void
 682 CreateMulInstruction(const TargetMachine &target, Function* F,
 683                      Value* lval, Value* rval, Instruction* destVal,
 684                      vector<MachineInstr*>& mvec,
 685                      MachineCodeForInstruction& mcfi,
 686                      MachineOpCode forceMulOp = INVALID_MACHINE_OPCODE)
 687 {
 688   unsigned L = mvec.size();
 689   CreateCheapestMulConstInstruction(target,F, lval, rval, destVal, mvec, mcfi);
 690   if (mvec.size() == L)
 691     { // no instructions were added so create MUL reg, reg, reg.
 692       // Use FSMULD if both operands are actually floats cast to doubles.
 693       // Otherwise, use the default opcode for the appropriate type.
 694       MachineOpCode mulOp = ((forceMulOp != INVALID_MACHINE_OPCODE)
 695                              ? forceMulOp
 696                              : ChooseMulInstructionByType(destVal->getType()));
 697       mvec.push_back(BuildMI(mulOp, 3).addReg(lval).addReg(rval)
 698                                       .addRegDef(destVal));
 699     }
 700 }
 701
 702
 703 // Generate a divide instruction for Div or Rem.
 704 // For Rem, this assumes that the operand type will be signed if the result
 705 // type is signed.  This is correct because they must have the same sign.
 706 //
 707 static inline MachineOpCode
 708 ChooseDivInstruction(TargetMachine &target,
 709                      const InstructionNode* instrNode)
 710 {
 711   MachineOpCode opCode = INVALID_OPCODE;
 712
 713   const Type* resultType = instrNode->getInstruction()->getType();
 714
 715   if (resultType->isInteger())
 716     opCode = resultType->isSigned()? SDIVX : UDIVX;
 717   else
 718     switch(resultType->getPrimitiveID())
 719       {
 720       case Type::FloatTyID:  opCode = FDIVS; break;
 721       case Type::DoubleTyID: opCode = FDIVD; break;
 722       default: assert(0 && "Invalid type for DIV instruction"); break;
 723       }
 724
 725   return opCode;
 726 }
 727
 728
 729 // Return if we cannot exploit constant to create a cheaper instruction
 730 static inline void
 731 CreateDivConstInstruction(TargetMachine &target,
 732                           const InstructionNode* instrNode,
 733                           vector<MachineInstr*>& mvec)
 734 {
 735   Value* LHS  = instrNode->leftChild()->getValue();
 736   Value* constOp = ((InstrTreeNode*) instrNode->rightChild())->getValue();
 737   if (!isa<Constant>(constOp))
 738     return;
 739
 740   Value* DestVal = instrNode->getValue();
 741   unsigned ZeroReg = target.getRegInfo().getZeroRegNum();
 742
 743   // Cases worth optimizing are:
 744   // (1) Divide by 1 for any type: replace with copy (ADD or FMOV)
 745   // (2) Divide by 2^x for integer types: replace with SR[L or A]{X}
 746   //
 747   const Type* resultType = instrNode->getInstruction()->getType();
 748
 749   if (resultType->isInteger())
 750     {
 751       unsigned pow;
 752       bool isValidConst;
 753       int64_t C = GetConstantValueAsSignedInt(constOp, isValidConst);
 754       if (isValidConst)
 755         {
 756           bool needNeg = false;
 757           if (C < 0) {
 758             needNeg = true;
 759             C = -C;
 760           }
 761
 762           if (C == 1) {
 763             mvec.push_back(BuildMI(ADD, 3).addReg(LHS).addMReg(ZeroReg)
 764                                           .addRegDef(DestVal));
 765           } else if (isPowerOf2(C, pow)) {
 766             unsigned opCode= ((resultType->isSigned())
 767                               ? (resultType==Type::LongTy) ? SRAX : SRA
 768                               : (resultType==Type::LongTy) ? SRLX : SRL);
 769             mvec.push_back(BuildMI(opCode, 3).addReg(LHS).addZImm(pow)
 770                                              .addRegDef(DestVal));
 771           }
 772
 773           if (needNeg && (C == 1 || isPowerOf2(C, pow)))
 774             { // insert <reg = SUB 0, reg> after the instr to flip the sign
 775               mvec.push_back(CreateIntNegInstruction(target, DestVal));
 776             }
 777         }
 778     }
 779   else
 780     {
 781       if (ConstantFP *FPC = dyn_cast<ConstantFP>(constOp))
 782         {
 783           double dval = FPC->getValue();
 784           if (fabs(dval) == 1)
 785             {
 786               unsigned opCode =
 787                 (dval < 0) ? (resultType == Type::FloatTy? FNEGS : FNEGD)
 788                            : (resultType == Type::FloatTy? FMOVS : FMOVD);
 789
 790               mvec.push_back(BuildMI(opCode, 2).addReg(LHS).addRegDef(DestVal));
 791             }
 792         }
 793     }
 794 }
 795
 796
 797 static void
 798 CreateCodeForVariableSizeAlloca(const TargetMachine& target,
 799                                 Instruction* result,
 800                                 unsigned tsize,
 801                                 Value* numElementsVal,
 802                                 vector<MachineInstr*>& getMvec)
 803 {
 804   Value* totalSizeVal;
 805   MachineInstr* M;
 806   MachineCodeForInstruction& mcfi = MachineCodeForInstruction::get(result);
 807   Function *F = result->getParent()->getParent();
 808
 809   // Enforce the alignment constraints on the stack pointer at
 810   // compile time if the total size is a known constant.
 811   if (isa<Constant>(numElementsVal))
 812     {
 813       bool isValid;
 814       int64_t numElem = GetConstantValueAsSignedInt(numElementsVal, isValid);
 815       assert(isValid && "Unexpectedly large array dimension in alloca!");
 816       int64_t total = numElem * tsize;
 817       if (int extra= total % target.getFrameInfo().getStackFrameSizeAlignment())
 818         total += target.getFrameInfo().getStackFrameSizeAlignment() - extra;
 819       totalSizeVal = ConstantSInt::get(Type::IntTy, total);
 820     }
 821   else
 822     {
 823       // The size is not a constant.  Generate code to compute it and
 824       // code to pad the size for stack alignment.
 825       // Create a Value to hold the (constant) element size
 826       Value* tsizeVal = ConstantSInt::get(Type::IntTy, tsize);
 827
 828       // Create temporary values to hold the result of MUL, SLL, SRL
 829       // THIS CASE IS INCOMPLETE AND WILL BE FIXED SHORTLY.
 830       TmpInstruction* tmpProd = new TmpInstruction(numElementsVal, tsizeVal);
 831       TmpInstruction* tmpSLL  = new TmpInstruction(numElementsVal, tmpProd);
 832       TmpInstruction* tmpSRL  = new TmpInstruction(numElementsVal, tmpSLL);
 833       mcfi.addTemp(tmpProd);
 834       mcfi.addTemp(tmpSLL);
 835       mcfi.addTemp(tmpSRL);
 836
 837       // Instruction 1: mul numElements, typeSize -> tmpProd
 838       // This will optimize the MUL as far as possible.
 839       CreateMulInstruction(target, F, numElementsVal, tsizeVal, tmpProd,getMvec,
 840                            mcfi, INVALID_MACHINE_OPCODE);
 841
 842       assert(0 && "Need to insert padding instructions here!");
 843
 844       totalSizeVal = tmpProd;
 845     }
 846
 847   // Get the constant offset from SP for dynamically allocated storage
 848   // and create a temporary Value to hold it.
 849   MachineFunction& mcInfo = MachineFunction::get(F);
 850   bool growUp;
 851   ConstantSInt* dynamicAreaOffset =
 852     ConstantSInt::get(Type::IntTy,
 853                      target.getFrameInfo().getDynamicAreaOffset(mcInfo,growUp));
 854   assert(! growUp && "Has SPARC v9 stack frame convention changed?");
 855
 856   unsigned SPReg = target.getRegInfo().getStackPointer();
 857
 858   // Instruction 2: sub %sp, totalSizeVal -> %sp
 859   getMvec.push_back(BuildMI(SUB, 3).addMReg(SPReg).addReg(totalSizeVal)
 860                                    .addMReg(SPReg,MOTy::Def));
 861
 862   // Instruction 3: add %sp, frameSizeBelowDynamicArea -> result
 863   getMvec.push_back(BuildMI(ADD, 3).addMReg(SPReg).addReg(dynamicAreaOffset)
 864                                    .addRegDef(result));
 865 }
 866
 867
 868 static void
 869 CreateCodeForFixedSizeAlloca(const TargetMachine& target,
 870                              Instruction* result,
 871                              unsigned tsize,
 872                              unsigned numElements,
 873                              vector<MachineInstr*>& getMvec)
 874 {
 875   assert(tsize > 0 && "Illegal (zero) type size for alloca");
 876   assert(result && result->getParent() &&
 877          "Result value is not part of a function?");
 878   Function *F = result->getParent()->getParent();
 879   MachineFunction &mcInfo = MachineFunction::get(F);
 880
 881   // Check if the offset would small enough to use as an immediate in
 882   // load/stores (check LDX because all load/stores have the same-size immediate
 883   // field).  If not, put the variable in the dynamically sized area of the
 884   // frame.
 885   unsigned paddedSizeIgnored;
 886   int offsetFromFP = mcInfo.getInfo()->computeOffsetforLocalVar(result,
 887                                                      paddedSizeIgnored,
 888                                                      tsize * numElements);
 889   if (! target.getInstrInfo().constantFitsInImmedField(LDX, offsetFromFP)) {
 890     CreateCodeForVariableSizeAlloca(target, result, tsize,
 891                                     ConstantSInt::get(Type::IntTy,numElements),
 892                                     getMvec);
 893     return;
 894   }
 895
 896   // else offset fits in immediate field so go ahead and allocate it.
 897   offsetFromFP = mcInfo.getInfo()->allocateLocalVar(result, tsize *numElements);
 898
 899   // Create a temporary Value to hold the constant offset.
 900   // This is needed because it may not fit in the immediate field.
 901   ConstantSInt* offsetVal = ConstantSInt::get(Type::IntTy, offsetFromFP);
 902
 903   // Instruction 1: add %fp, offsetFromFP -> result
 904   unsigned FPReg = target.getRegInfo().getFramePointer();
 905   getMvec.push_back(BuildMI(ADD, 3).addMReg(FPReg).addReg(offsetVal)
 906                                    .addRegDef(result));
 907 }
 908
 909
 910 //------------------------------------------------------------------------
 911 // Function SetOperandsForMemInstr
 912 //
 913 // Choose addressing mode for the given load or store instruction.
 914 // Use [reg+reg] if it is an indexed reference, and the index offset is
 915 //               not a constant or if it cannot fit in the offset field.
 916 // Use [reg+offset] in all other cases.
 917 //
 918 // This assumes that all array refs are "lowered" to one of these forms:
 919 //      %x = load (subarray*) ptr, constant     ; single constant offset
 920 //      %x = load (subarray*) ptr, offsetVal    ; single non-constant offset
 921 // Generally, this should happen via strength reduction + LICM.
 922 // Also, strength reduction should take care of using the same register for
 923 // the loop index variable and an array index, when that is profitable.
 924 //------------------------------------------------------------------------
 925
 926 static void
 927 SetOperandsForMemInstr(unsigned Opcode,
 928                        vector<MachineInstr*>& mvec,
 929                        InstructionNode* vmInstrNode,
 930                        const TargetMachine& target)
 931 {
 932   Instruction* memInst = vmInstrNode->getInstruction();
 933   // Index vector, ptr value, and flag if all indices are const.
 934   vector<Value*> idxVec;
 935   bool allConstantIndices;
 936   Value* ptrVal = GetMemInstArgs(vmInstrNode, idxVec, allConstantIndices);
 937
 938   // Now create the appropriate operands for the machine instruction.
 939   // First, initialize so we default to storing the offset in a register.
 940   int64_t smallConstOffset = 0;
 941   Value* valueForRegOffset = NULL;
 942   MachineOperand::MachineOperandType offsetOpType =
 943     MachineOperand::MO_VirtualRegister;
 944
 945   // Check if there is an index vector and if so, compute the
 946   // right offset for structures and for arrays
 947   //
 948   if (!idxVec.empty())
 949     {
 950       const PointerType* ptrType = cast<PointerType>(ptrVal->getType());
 951
 952       // If all indices are constant, compute the combined offset directly.
 953       if (allConstantIndices)
 954         {
 955           // Compute the offset value using the index vector. Create a
 956           // virtual reg. for it since it may not fit in the immed field.
 957           uint64_t offset = target.getTargetData().getIndexedOffset(ptrType,idxVec);
 958           valueForRegOffset = ConstantSInt::get(Type::LongTy, offset);
 959         }
 960       else
 961         {
 962           // There is at least one non-constant offset.  Therefore, this must
 963           // be an array ref, and must have been lowered to a single non-zero
 964           // offset.  (An extra leading zero offset, if any, can be ignored.)
 965           // Generate code sequence to compute address from index.
 966           //
 967           bool firstIdxIsZero =
 968             (idxVec[0] == Constant::getNullValue(idxVec[0]->getType()));
 969           assert(idxVec.size() == 1U + firstIdxIsZero
 970                  && "Array refs must be lowered before Instruction Selection");
 971
 972           Value* idxVal = idxVec[firstIdxIsZero];
 973
 974           vector<MachineInstr*> mulVec;
 975           Instruction* addr = new TmpInstruction(Type::ULongTy, memInst);
 976           MachineCodeForInstruction::get(memInst).addTemp(addr);
 977
 978           // Get the array type indexed by idxVal, and compute its element size.
 979           // The call to getTypeSize() will fail if size is not constant.
 980           const Type* vecType = (firstIdxIsZero
 981                                  ? GetElementPtrInst::getIndexedType(ptrType,
 982                                            std::vector<Value*>(1U, idxVec[0]),
 983                                            /*AllowCompositeLeaf*/ true)
 984                                  : ptrType);
 985           const Type* eltType = cast<SequentialType>(vecType)->getElementType();
 986           ConstantUInt* eltSizeVal = ConstantUInt::get(Type::ULongTy,
 987                                        target.getTargetData().getTypeSize(eltType));
 988
 989           // CreateMulInstruction() folds constants intelligently enough.
 990           CreateMulInstruction(target, memInst->getParent()->getParent(),
 991                                idxVal,         /* lval, not likely to be const*/
 992                                eltSizeVal,     /* rval, likely to be constant */
 993                                addr,           /* result */
 994                                mulVec, MachineCodeForInstruction::get(memInst),
 995                                INVALID_MACHINE_OPCODE);
 996
 997           assert(mulVec.size() > 0 && "No multiply code created?");
 998           mvec.insert(mvec.end(), mulVec.begin(), mulVec.end());
 999
1000           valueForRegOffset = addr;
1001         }
1002     }
1003   else
1004     {
1005       offsetOpType = MachineOperand::MO_SignExtendedImmed;
1006       smallConstOffset = 0;
1007     }
1008
1009   // For STORE:
1010   //   Operand 0 is value, operand 1 is ptr, operand 2 is offset
1011   // For LOAD or GET_ELEMENT_PTR,
1012   //   Operand 0 is ptr, operand 1 is offset, operand 2 is result.
1013   //
1014   unsigned offsetOpNum, ptrOpNum;
1015   MachineInstr *MI;
1016   if (memInst->getOpcode() == Instruction::Store) {
1017     if (offsetOpType == MachineOperand::MO_VirtualRegister)
1018       MI = BuildMI(Opcode, 3).addReg(vmInstrNode->leftChild()->getValue())
1019                              .addReg(ptrVal).addReg(valueForRegOffset);
1020     else
1021       MI = BuildMI(Opcode, 3).addReg(vmInstrNode->leftChild()->getValue())
1022                              .addReg(ptrVal).addSImm(smallConstOffset);
1023   } else {
1024     if (offsetOpType == MachineOperand::MO_VirtualRegister)
1025       MI = BuildMI(Opcode, 3).addReg(ptrVal).addReg(valueForRegOffset)
1026                              .addRegDef(memInst);
1027     else
1028       MI = BuildMI(Opcode, 3).addReg(ptrVal).addSImm(smallConstOffset)
1029                              .addRegDef(memInst);
1030   }
1031   mvec.push_back(MI);
1032 }
1033
1034
1035 //
1036 // Substitute operand `operandNum' of the instruction in node `treeNode'
1037 // in place of the use(s) of that instruction in node `parent'.
1038 // Check both explicit and implicit operands!
1039 // Also make sure to skip over a parent who:
1040 // (1) is a list node in the Burg tree, or
1041 // (2) itself had its results forwarded to its parent
1042 //
1043 static void
1044 ForwardOperand(InstructionNode* treeNode,
1045                InstrTreeNode*   parent,
1046                int operandNum)
1047 {
1048   assert(treeNode && parent && "Invalid invocation of ForwardOperand");
1049
1050   Instruction* unusedOp = treeNode->getInstruction();
1051   Value* fwdOp = unusedOp->getOperand(operandNum);
1052
1053   // The parent itself may be a list node, so find the real parent instruction
1054   while (parent->getNodeType() != InstrTreeNode::NTInstructionNode)
1055     {
1056       parent = parent->parent();
1057       assert(parent && "ERROR: Non-instruction node has no parent in tree.");
1058     }
1059   InstructionNode* parentInstrNode = (InstructionNode*) parent;
1060
1061   Instruction* userInstr = parentInstrNode->getInstruction();
1062   MachineCodeForInstruction &mvec = MachineCodeForInstruction::get(userInstr);
1063
1064   // The parent's mvec would be empty if it was itself forwarded.
1065   // Recursively call ForwardOperand in that case...
1066   //
1067   if (mvec.size() == 0)
1068     {
1069       assert(parent->parent() != NULL &&
1070              "Parent could not have been forwarded, yet has no instructions?");
1071       ForwardOperand(treeNode, parent->parent(), operandNum);
1072     }
1073   else
1074     {
1075       for (unsigned i=0, N=mvec.size(); i < N; i++)
1076         {
1077           MachineInstr* minstr = mvec[i];
1078           for (unsigned i=0, numOps=minstr->getNumOperands(); i < numOps; ++i)
1079             {
1080               const MachineOperand& mop = minstr->getOperand(i);
1081               if (mop.getType() == MachineOperand::MO_VirtualRegister &&
1082                   mop.getVRegValue() == unusedOp)
1083                 minstr->SetMachineOperandVal(i,
1084                                 MachineOperand::MO_VirtualRegister, fwdOp);
1085             }
1086
1087           for (unsigned i=0,numOps=minstr->getNumImplicitRefs(); i<numOps; ++i)
1088             if (minstr->getImplicitRef(i) == unusedOp)
1089               minstr->setImplicitRef(i, fwdOp,
1090                                      minstr->implicitRefIsDefined(i),
1091                                      minstr->implicitRefIsDefinedAndUsed(i));
1092         }
1093     }
1094 }
1095
1096
1097 inline bool
1098 AllUsesAreBranches(const Instruction* setccI)
1099 {
1100   for (Value::use_const_iterator UI=setccI->use_begin(), UE=setccI->use_end();
1101        UI != UE; ++UI)
1102     if (! isa<TmpInstruction>(*UI)     // ignore tmp instructions here
1103         && cast<Instruction>(*UI)->getOpcode() != Instruction::Br)
1104       return false;
1105   return true;
1106 }
1107
1108 //******************* Externally Visible Functions *************************/
1109
1110 //------------------------------------------------------------------------
1111 // External Function: ThisIsAChainRule
1112 //
1113 // Purpose:
1114 //   Check if a given BURG rule is a chain rule.
1115 //------------------------------------------------------------------------
1116
1117 extern bool
1118 ThisIsAChainRule(int eruleno)
1119 {
1120   switch(eruleno)
1121     {
1122     case 111:   // stmt:  reg
1123     case 123:
1124     case 124:
1125     case 125:
1126     case 126:
1127     case 127:
1128     case 128:
1129     case 129:
1130     case 130:
1131     case 131:
1132     case 132:
1133     case 133:
1134     case 155:
1135     case 221:
1136     case 222:
1137     case 241:
1138     case 242:
1139     case 243:
1140     case 244:
1141     case 245:
1142     case 321:
1143       return true; break;
1144
1145     default:
1146       return false; break;
1147     }
1148 }
1149
1150
1151 //------------------------------------------------------------------------
1152 // External Function: GetInstructionsByRule
1153 //
1154 // Purpose:
1155 //   Choose machine instructions for the SPARC according to the
1156 //   patterns chosen by the BURG-generated parser.
1157 //------------------------------------------------------------------------
1158
1159 void
1160 GetInstructionsByRule(InstructionNode* subtreeRoot,
1161                       int ruleForNode,
1162                       short* nts,
1163                       TargetMachine &target,
1164                       vector<MachineInstr*>& mvec)
1165 {
1166   bool checkCast = false;               // initialize here to use fall-through
1167   bool maskUnsignedResult = false;
1168   int nextRule;
1169   int forwardOperandNum = -1;
1170   unsigned allocaSize = 0;
1171   MachineInstr* M, *M2;
1172   unsigned L;
1173
1174   mvec.clear();
1175
1176   // If the code for this instruction was folded into the parent (user),
1177   // then do nothing!
1178   if (subtreeRoot->isFoldedIntoParent())
1179     return;
1180
1181   //
1182   // Let's check for chain rules outside the switch so that we don't have
1183   // to duplicate the list of chain rule production numbers here again
1184   //
1185   if (ThisIsAChainRule(ruleForNode))
1186     {
1187       // Chain rules have a single nonterminal on the RHS.
1188       // Get the rule that matches the RHS non-terminal and use that instead.
1189       //
1190       assert(nts[0] && ! nts[1]
1191              && "A chain rule should have only one RHS non-terminal!");
1192       nextRule = burm_rule(subtreeRoot->state, nts[0]);
1193       nts = burm_nts[nextRule];
1194       GetInstructionsByRule(subtreeRoot, nextRule, nts, target, mvec);
1195     }
1196   else
1197     {
1198       switch(ruleForNode) {
1199       case 1:   // stmt:   Ret
1200       case 2:   // stmt:   RetValue(reg)
1201       {         // NOTE: Prepass of register allocation is responsible
1202                 //       for moving return value to appropriate register.
1203                 // Mark the return-address register as a hidden virtual reg.
1204                 // Mark the return value   register as an implicit ref of
1205                 // the machine instruction.
1206                 // Finally put a NOP in the delay slot.
1207         ReturnInst *returnInstr =
1208           cast<ReturnInst>(subtreeRoot->getInstruction());
1209         assert(returnInstr->getOpcode() == Instruction::Ret);
1210
1211         Instruction* returnReg = new TmpInstruction(returnInstr);
1212         MachineCodeForInstruction::get(returnInstr).addTemp(returnReg);
1213
1214         M = BuildMI(JMPLRET, 3).addReg(returnReg).addSImm(8)
1215                        .addMReg(target.getRegInfo().getZeroRegNum(), MOTy::Def);
1216
1217         if (returnInstr->getReturnValue() != NULL)
1218           M->addImplicitRef(returnInstr->getReturnValue());
1219
1220         mvec.push_back(M);
1221         mvec.push_back(BuildMI(NOP, 0));
1222
1223         break;
1224       }
1225
1226       case 3:   // stmt:   Store(reg,reg)
1227       case 4:   // stmt:   Store(reg,ptrreg)
1228         SetOperandsForMemInstr(ChooseStoreInstruction(
1229                         subtreeRoot->leftChild()->getValue()->getType()),
1230                                mvec, subtreeRoot, target);
1231         break;
1232
1233       case 5:   // stmt:   BrUncond
1234         {
1235           BranchInst *BI = cast<BranchInst>(subtreeRoot->getInstruction());
1236           mvec.push_back(BuildMI(BA, 1).addPCDisp(BI->getSuccessor(0)));
1237
1238           // delay slot
1239           mvec.push_back(BuildMI(NOP, 0));
1240           break;
1241         }
1242
1243       case 206: // stmt:   BrCond(setCCconst)
1244       { // setCCconst => boolean was computed with `%b = setCC type reg1 const'
1245         // If the constant is ZERO, we can use the branch-on-integer-register
1246         // instructions and avoid the SUBcc instruction entirely.
1247         // Otherwise this is just the same as case 5, so just fall through.
1248         //
1249         InstrTreeNode* constNode = subtreeRoot->leftChild()->rightChild();
1250         assert(constNode &&
1251                constNode->getNodeType() ==InstrTreeNode::NTConstNode);
1252         Constant *constVal = cast<Constant>(constNode->getValue());
1253         bool isValidConst;
1254
1255         if ((constVal->getType()->isInteger()
1256              || isa<PointerType>(constVal->getType()))
1257             && GetConstantValueAsSignedInt(constVal, isValidConst) == 0
1258             && isValidConst)
1259           {
1260             // That constant is a zero after all...
1261             // Use the left child of setCC as the first argument!
1262             // Mark the setCC node so that no code is generated for it.
1263             InstructionNode* setCCNode = (InstructionNode*)
1264                                          subtreeRoot->leftChild();
1265             assert(setCCNode->getOpLabel() == SetCCOp);
1266             setCCNode->markFoldedIntoParent();
1267
1268             BranchInst* brInst=cast<BranchInst>(subtreeRoot->getInstruction());
1269
1270             M = BuildMI(ChooseBprInstruction(subtreeRoot), 2)
1271                                 .addReg(setCCNode->leftChild()->getValue())
1272                                 .addPCDisp(brInst->getSuccessor(0));
1273             mvec.push_back(M);
1274
1275             // delay slot
1276             mvec.push_back(BuildMI(NOP, 0));
1277
1278             // false branch
1279             mvec.push_back(BuildMI(BA, 1).addPCDisp(brInst->getSuccessor(1)));
1280
1281             // delay slot
1282             mvec.push_back(BuildMI(NOP, 0));
1283             break;
1284           }
1285         // ELSE FALL THROUGH
1286       }
1287
1288       case 6:   // stmt:   BrCond(setCC)
1289       { // bool => boolean was computed with SetCC.
1290         // The branch to use depends on whether it is FP, signed, or unsigned.
1291         // If it is an integer CC, we also need to find the unique
1292         // TmpInstruction representing that CC.
1293         //
1294         BranchInst* brInst = cast<BranchInst>(subtreeRoot->getInstruction());
1295         bool isFPBranch;
1296         unsigned Opcode = ChooseBccInstruction(subtreeRoot, isFPBranch);
1297         Value* ccValue = GetTmpForCC(subtreeRoot->leftChild()->getValue(),
1298                                      brInst->getParent()->getParent(),
1299                                      isFPBranch? Type::FloatTy : Type::IntTy);
1300         M = BuildMI(Opcode, 2).addCCReg(ccValue)
1301                               .addPCDisp(brInst->getSuccessor(0));
1302         mvec.push_back(M);
1303
1304         // delay slot
1305         mvec.push_back(BuildMI(NOP, 0));
1306
1307         // false branch
1308         mvec.push_back(BuildMI(BA, 1).addPCDisp(brInst->getSuccessor(1)));
1309
1310         // delay slot
1311         mvec.push_back(BuildMI(NOP, 0));
1312         break;
1313       }
1314
1315       case 208: // stmt:   BrCond(boolconst)
1316       {
1317         // boolconst => boolean is a constant; use BA to first or second label
1318         Constant* constVal =
1319           cast<Constant>(subtreeRoot->leftChild()->getValue());
1320         unsigned dest = cast<ConstantBool>(constVal)->getValue()? 0 : 1;
1321
1322         M = BuildMI(BA, 1).addPCDisp(
1323           cast<BranchInst>(subtreeRoot->getInstruction())->getSuccessor(dest));
1324         mvec.push_back(M);
1325
1326         // delay slot
1327         mvec.push_back(BuildMI(NOP, 0));
1328         break;
1329       }
1330
1331       case   8: // stmt:   BrCond(boolreg)
1332       { // boolreg   => boolean is stored in an existing register.
1333         // Just use the branch-on-integer-register instruction!
1334         //
1335         BranchInst *BI = cast<BranchInst>(subtreeRoot->getInstruction());
1336         M = BuildMI(BRNZ, 2).addReg(subtreeRoot->leftChild()->getValue())
1337           .addPCDisp(BI->getSuccessor(0));
1338         mvec.push_back(M);
1339
1340         // delay slot
1341         mvec.push_back(BuildMI(NOP, 0));
1342
1343         // false branch
1344         mvec.push_back(BuildMI(BA, 1).addPCDisp(BI->getSuccessor(1)));
1345
1346         // delay slot
1347         mvec.push_back(BuildMI(NOP, 0));
1348         break;
1349       }
1350
1351       case 9:   // stmt:   Switch(reg)
1352         assert(0 && "*** SWITCH instruction is not implemented yet.");
1353         break;
1354
1355       case 10:  // reg:   VRegList(reg, reg)
1356         assert(0 && "VRegList should never be the topmost non-chain rule");
1357         break;
1358
1359       case 21:  // bool:  Not(bool,reg): Both these are implemented as:
1360       case 421: // reg:   BNot(reg,reg):        reg = reg XOR-NOT 0
1361       { // First find the unary operand. It may be left or right, usually right.
1362         Value* notArg = BinaryOperator::getNotArgument(
1363                            cast<BinaryOperator>(subtreeRoot->getInstruction()));
1364         unsigned ZeroReg = target.getRegInfo().getZeroRegNum();
1365         mvec.push_back(BuildMI(XNOR, 3).addReg(notArg).addMReg(ZeroReg)
1366                                        .addRegDef(subtreeRoot->getValue()));
1367         break;
1368       }
1369
1370       case 22:  // reg:   ToBoolTy(reg):
1371       {
1372         const Type* opType = subtreeRoot->leftChild()->getValue()->getType();
1373         assert(opType->isIntegral() || isa<PointerType>(opType));
1374         forwardOperandNum = 0;          // forward first operand to user
1375         break;
1376       }
1377
1378       case 23:  // reg:   ToUByteTy(reg)
1379       case 24:  // reg:   ToSByteTy(reg)
1380       case 25:  // reg:   ToUShortTy(reg)
1381       case 26:  // reg:   ToShortTy(reg)
1382       case 27:  // reg:   ToUIntTy(reg)
1383       case 28:  // reg:   ToIntTy(reg)
1384       {
1385         //======================================================================
1386         // Rules for integer conversions:
1387         //
1388         //--------
1389         // From ISO 1998 C++ Standard, Sec. 4.7:
1390         //
1391         // 2. If the destination type is unsigned, the resulting value is
1392         // the least unsigned integer congruent to the source integer
1393         // (modulo 2n where n is the number of bits used to represent the
1394         // unsigned type). [Note: In a two s complement representation,
1395         // this conversion is conceptual and there is no change in the
1396         // bit pattern (if there is no truncation). ]
1397         //
1398         // 3. If the destination type is signed, the value is unchanged if
1399         // it can be represented in the destination type (and bitfield width);
1400         // otherwise, the value is implementation-defined.
1401         //--------
1402         //
1403         // Since we assume 2s complement representations, this implies:
1404         //
1405         // -- if operand is smaller than destination, zero-extend or sign-extend
1406         //    according to the signedness of the *operand*: source decides.
1407         //    ==> we have to do nothing here!
1408         //
1409         // -- if operand is same size as or larger than destination, and the
1410         //    destination is *unsigned*, zero-extend the operand: dest. decides
1411         //
1412         // -- if operand is same size as or larger than destination, and the
1413         //    destination is *signed*, the choice is implementation defined:
1414         //    we sign-extend the operand: i.e., again dest. decides.
1415         //    Note: this matches both Sun's cc and gcc3.2.
1416         //======================================================================
1417
1418         Instruction* destI =  subtreeRoot->getInstruction();
1419         Value* opVal = subtreeRoot->leftChild()->getValue();
1420         const Type* opType = opVal->getType();
1421         if (opType->isIntegral() || isa<PointerType>(opType))
1422           {
1423             unsigned opSize = target.getTargetData().getTypeSize(opType);
1424             unsigned destSize = target.getTargetData().getTypeSize(destI->getType());
1425             if (opSize >= destSize)
1426               { // Operand is same size as or larger than dest:
1427                 // zero- or sign-extend, according to the signeddness of
1428                 // the destination (see above).
1429                 if (destI->getType()->isSigned())
1430                   target.getInstrInfo().CreateSignExtensionInstructions(target,
1431                     destI->getParent()->getParent(), opVal, destI, 8*destSize,
1432                     mvec, MachineCodeForInstruction::get(destI));
1433                 else
1434                   target.getInstrInfo().CreateZeroExtensionInstructions(target,
1435                     destI->getParent()->getParent(), opVal, destI, 8*destSize,
1436                     mvec, MachineCodeForInstruction::get(destI));
1437               }
1438             else
1439               forwardOperandNum = 0;          // forward first operand to user
1440           }
1441         else if (opType->isFloatingPoint())
1442           {
1443             CreateCodeToConvertFloatToInt(target, opVal, destI, mvec,
1444                                          MachineCodeForInstruction::get(destI));
1445             if (destI->getType()->isUnsigned())
1446               maskUnsignedResult = true; // not handled by fp->int code
1447           }
1448         else
1449           assert(0 && "Unrecognized operand type for convert-to-unsigned");
1450
1451         break;
1452       }
1453
1454       case 29:  // reg:   ToULongTy(reg)
1455       case 30:  // reg:   ToLongTy(reg)
1456       {
1457         Value* opVal = subtreeRoot->leftChild()->getValue();
1458         const Type* opType = opVal->getType();
1459         if (opType->isIntegral() || isa<PointerType>(opType))
1460           forwardOperandNum = 0;          // forward first operand to user
1461         else if (opType->isFloatingPoint())
1462           {
1463             Instruction* destI =  subtreeRoot->getInstruction();
1464             CreateCodeToConvertFloatToInt(target, opVal, destI, mvec,
1465                                          MachineCodeForInstruction::get(destI));
1466           }
1467         else
1468           assert(0 && "Unrecognized operand type for convert-to-signed");
1469         break;
1470       }
1471
1472       case  31: // reg:   ToFloatTy(reg):
1473       case  32: // reg:   ToDoubleTy(reg):
1474       case 232: // reg:   ToDoubleTy(Constant):
1475
1476         // If this instruction has a parent (a user) in the tree
1477         // and the user is translated as an FsMULd instruction,
1478         // then the cast is unnecessary.  So check that first.
1479         // In the future, we'll want to do the same for the FdMULq instruction,
1480         // so do the check here instead of only for ToFloatTy(reg).
1481         //
1482         if (subtreeRoot->parent() != NULL)
1483           {
1484             const MachineCodeForInstruction& mcfi =
1485               MachineCodeForInstruction::get(
1486                 cast<InstructionNode>(subtreeRoot->parent())->getInstruction());
1487             if (mcfi.size() == 0 || mcfi.front()->getOpCode() == FSMULD)
1488               forwardOperandNum = 0;    // forward first operand to user
1489           }
1490
1491         if (forwardOperandNum != 0)     // we do need the cast
1492           {
1493             Value* leftVal = subtreeRoot->leftChild()->getValue();
1494             const Type* opType = leftVal->getType();
1495             MachineOpCode opCode=ChooseConvertToFloatInstr(
1496                                        subtreeRoot->getOpLabel(), opType);
1497             if (opCode == INVALID_OPCODE)       // no conversion needed
1498               {
1499                 forwardOperandNum = 0;      // forward first operand to user
1500               }
1501             else
1502               {
1503                 // If the source operand is a non-FP type it must be
1504                 // first copied from int to float register via memory!
1505                 Instruction *dest = subtreeRoot->getInstruction();
1506                 Value* srcForCast;
1507                 int n = 0;
1508                 if (! opType->isFloatingPoint())
1509                   {
1510                     // Create a temporary to represent the FP register
1511                     // into which the integer will be copied via memory.
1512                     // The type of this temporary will determine the FP
1513                     // register used: single-prec for a 32-bit int or smaller,
1514                     // double-prec for a 64-bit int.
1515                     //
1516                     uint64_t srcSize =
1517                       target.getTargetData().getTypeSize(leftVal->getType());
1518                     Type* tmpTypeToUse =
1519                       (srcSize <= 4)? Type::FloatTy : Type::DoubleTy;
1520                     srcForCast = new TmpInstruction(tmpTypeToUse, dest);
1521                     MachineCodeForInstruction &destMCFI =
1522                       MachineCodeForInstruction::get(dest);
1523                     destMCFI.addTemp(srcForCast);
1524
1525                     target.getInstrInfo().CreateCodeToCopyIntToFloat(target,
1526                          dest->getParent()->getParent(),
1527                          leftVal, cast<Instruction>(srcForCast),
1528                          mvec, destMCFI);
1529                   }
1530                 else
1531                   srcForCast = leftVal;
1532
1533                 M = BuildMI(opCode, 2).addReg(srcForCast).addRegDef(dest);
1534                 mvec.push_back(M);
1535               }
1536           }
1537         break;
1538
1539       case 19:  // reg:   ToArrayTy(reg):
1540       case 20:  // reg:   ToPointerTy(reg):
1541         forwardOperandNum = 0;          // forward first operand to user
1542         break;
1543
1544       case 233: // reg:   Add(reg, Constant)
1545         maskUnsignedResult = true;
1546         M = CreateAddConstInstruction(subtreeRoot);
1547         if (M != NULL)
1548           {
1549             mvec.push_back(M);
1550             break;
1551           }
1552         // ELSE FALL THROUGH
1553
1554       case 33:  // reg:   Add(reg, reg)
1555         maskUnsignedResult = true;
1556         Add3OperandInstr(ChooseAddInstruction(subtreeRoot), subtreeRoot, mvec);
1557         break;
1558
1559       case 234: // reg:   Sub(reg, Constant)
1560         maskUnsignedResult = true;
1561         M = CreateSubConstInstruction(subtreeRoot);
1562         if (M != NULL)
1563           {
1564             mvec.push_back(M);
1565             break;
1566           }
1567         // ELSE FALL THROUGH
1568
1569       case 34:  // reg:   Sub(reg, reg)
1570         maskUnsignedResult = true;
1571         Add3OperandInstr(ChooseSubInstructionByType(
1572                                    subtreeRoot->getInstruction()->getType()),
1573                          subtreeRoot, mvec);
1574         break;
1575
1576       case 135: // reg:   Mul(todouble, todouble)
1577         checkCast = true;
1578         // FALL THROUGH
1579
1580       case 35:  // reg:   Mul(reg, reg)
1581       {
1582         maskUnsignedResult = true;
1583         MachineOpCode forceOp = ((checkCast && BothFloatToDouble(subtreeRoot))
1584                                  ? FSMULD
1585                                  : INVALID_MACHINE_OPCODE);
1586         Instruction* mulInstr = subtreeRoot->getInstruction();
1587         CreateMulInstruction(target, mulInstr->getParent()->getParent(),
1588                              subtreeRoot->leftChild()->getValue(),
1589                              subtreeRoot->rightChild()->getValue(),
1590                              mulInstr, mvec,
1591                              MachineCodeForInstruction::get(mulInstr),forceOp);
1592         break;
1593       }
1594       case 335: // reg:   Mul(todouble, todoubleConst)
1595         checkCast = true;
1596         // FALL THROUGH
1597
1598       case 235: // reg:   Mul(reg, Constant)
1599       {
1600         maskUnsignedResult = true;
1601         MachineOpCode forceOp = ((checkCast && BothFloatToDouble(subtreeRoot))
1602                                  ? FSMULD
1603                                  : INVALID_MACHINE_OPCODE);
1604         Instruction* mulInstr = subtreeRoot->getInstruction();
1605         CreateMulInstruction(target, mulInstr->getParent()->getParent(),
1606                              subtreeRoot->leftChild()->getValue(),
1607                              subtreeRoot->rightChild()->getValue(),
1608                              mulInstr, mvec,
1609                              MachineCodeForInstruction::get(mulInstr),
1610                              forceOp);
1611         break;
1612       }
1613       case 236: // reg:   Div(reg, Constant)
1614         maskUnsignedResult = true;
1615         L = mvec.size();
1616         CreateDivConstInstruction(target, subtreeRoot, mvec);
1617         if (mvec.size() > L)
1618           break;
1619         // ELSE FALL THROUGH
1620
1621       case 36:  // reg:   Div(reg, reg)
1622         maskUnsignedResult = true;
1623         Add3OperandInstr(ChooseDivInstruction(target, subtreeRoot),
1624                          subtreeRoot, mvec);
1625         break;
1626
1627       case  37: // reg:   Rem(reg, reg)
1628       case 237: // reg:   Rem(reg, Constant)
1629       {
1630         maskUnsignedResult = true;
1631         Instruction* remInstr = subtreeRoot->getInstruction();
1632
1633         TmpInstruction* quot = new TmpInstruction(
1634                                         subtreeRoot->leftChild()->getValue(),
1635                                         subtreeRoot->rightChild()->getValue());
1636         TmpInstruction* prod = new TmpInstruction(
1637                                         quot,
1638                                         subtreeRoot->rightChild()->getValue());
1639         MachineCodeForInstruction::get(remInstr).addTemp(quot).addTemp(prod);
1640
1641         M = BuildMI(ChooseDivInstruction(target, subtreeRoot), 3)
1642                              .addReg(subtreeRoot->leftChild()->getValue())
1643                              .addReg(subtreeRoot->rightChild()->getValue())
1644                              .addRegDef(quot);
1645         mvec.push_back(M);
1646
1647         unsigned MulOpcode =
1648           ChooseMulInstructionByType(subtreeRoot->getInstruction()->getType());
1649         Value *MulRHS = subtreeRoot->rightChild()->getValue();
1650         M = BuildMI(MulOpcode, 3).addReg(quot).addReg(MulRHS).addReg(prod,
1651                                                                      MOTy::Def);
1652         mvec.push_back(M);
1653
1654         unsigned Opcode = ChooseSubInstructionByType(
1655                                    subtreeRoot->getInstruction()->getType());
1656         M = BuildMI(Opcode, 3).addReg(subtreeRoot->leftChild()->getValue())
1657                               .addReg(prod).addRegDef(subtreeRoot->getValue());
1658         mvec.push_back(M);
1659         break;
1660       }
1661
1662       case  38: // bool:   And(bool, bool)
1663       case 238: // bool:   And(bool, boolconst)
1664       case 338: // reg :   BAnd(reg, reg)
1665       case 538: // reg :   BAnd(reg, Constant)
1666         Add3OperandInstr(AND, subtreeRoot, mvec);
1667         break;
1668
1669       case 138: // bool:   And(bool, not)
1670       case 438: // bool:   BAnd(bool, bnot)
1671       { // Use the argument of NOT as the second argument!
1672         // Mark the NOT node so that no code is generated for it.
1673         InstructionNode* notNode = (InstructionNode*) subtreeRoot->rightChild();
1674         Value* notArg = BinaryOperator::getNotArgument(
1675                            cast<BinaryOperator>(notNode->getInstruction()));
1676         notNode->markFoldedIntoParent();
1677         Value *LHS = subtreeRoot->leftChild()->getValue();
1678         Value *Dest = subtreeRoot->getValue();
1679         mvec.push_back(BuildMI(ANDN, 3).addReg(LHS).addReg(notArg)
1680                                        .addReg(Dest, MOTy::Def));
1681         break;
1682       }
1683
1684       case  39: // bool:   Or(bool, bool)
1685       case 239: // bool:   Or(bool, boolconst)
1686       case 339: // reg :   BOr(reg, reg)
1687       case 539: // reg :   BOr(reg, Constant)
1688         Add3OperandInstr(OR, subtreeRoot, mvec);
1689         break;
1690
1691       case 139: // bool:   Or(bool, not)
1692       case 439: // bool:   BOr(bool, bnot)
1693       { // Use the argument of NOT as the second argument!
1694         // Mark the NOT node so that no code is generated for it.
1695         InstructionNode* notNode = (InstructionNode*) subtreeRoot->rightChild();
1696         Value* notArg = BinaryOperator::getNotArgument(
1697                            cast<BinaryOperator>(notNode->getInstruction()));
1698         notNode->markFoldedIntoParent();
1699         Value *LHS = subtreeRoot->leftChild()->getValue();
1700         Value *Dest = subtreeRoot->getValue();
1701         mvec.push_back(BuildMI(ORN, 3).addReg(LHS).addReg(notArg)
1702                                       .addReg(Dest, MOTy::Def));
1703         break;
1704       }
1705
1706       case  40: // bool:   Xor(bool, bool)
1707       case 240: // bool:   Xor(bool, boolconst)
1708       case 340: // reg :   BXor(reg, reg)
1709       case 540: // reg :   BXor(reg, Constant)
1710         Add3OperandInstr(XOR, subtreeRoot, mvec);
1711         break;
1712
1713       case 140: // bool:   Xor(bool, not)
1714       case 440: // bool:   BXor(bool, bnot)
1715       { // Use the argument of NOT as the second argument!
1716         // Mark the NOT node so that no code is generated for it.
1717         InstructionNode* notNode = (InstructionNode*) subtreeRoot->rightChild();
1718         Value* notArg = BinaryOperator::getNotArgument(
1719                            cast<BinaryOperator>(notNode->getInstruction()));
1720         notNode->markFoldedIntoParent();
1721         Value *LHS = subtreeRoot->leftChild()->getValue();
1722         Value *Dest = subtreeRoot->getValue();
1723         mvec.push_back(BuildMI(XNOR, 3).addReg(LHS).addReg(notArg)
1724                                        .addReg(Dest, MOTy::Def));
1725         break;
1726       }
1727
1728       case 41:  // boolconst:   SetCC(reg, Constant)
1729         //
1730         // If the SetCC was folded into the user (parent), it will be
1731         // caught above.  All other cases are the same as case 42,
1732         // so just fall through.
1733         //
1734       case 42:  // bool:   SetCC(reg, reg):
1735       {
1736         // This generates a SUBCC instruction, putting the difference in
1737         // a result register, and setting a condition code.
1738         //
1739         // If the boolean result of the SetCC is used by anything other
1740         // than a branch instruction, or if it is used outside the current
1741         // basic block, the boolean must be
1742         // computed and stored in the result register.  Otherwise, discard
1743         // the difference (by using %g0) and keep only the condition code.
1744         //
1745         // To compute the boolean result in a register we use a conditional
1746         // move, unless the result of the SUBCC instruction can be used as
1747         // the bool!  This assumes that zero is FALSE and any non-zero
1748         // integer is TRUE.
1749         //
1750         InstructionNode* parentNode = (InstructionNode*) subtreeRoot->parent();
1751         Instruction* setCCInstr = subtreeRoot->getInstruction();
1752
1753         bool keepBoolVal = parentNode == NULL ||
1754                            ! AllUsesAreBranches(setCCInstr);
1755         bool subValIsBoolVal = setCCInstr->getOpcode() == Instruction::SetNE;
1756         bool keepSubVal = keepBoolVal && subValIsBoolVal;
1757         bool computeBoolVal = keepBoolVal && ! subValIsBoolVal;
1758
1759         bool mustClearReg;
1760         int valueToMove;
1761         MachineOpCode movOpCode = 0;
1762
1763         // Mark the 4th operand as being a CC register, and as a def
1764         // A TmpInstruction is created to represent the CC "result".
1765         // Unlike other instances of TmpInstruction, this one is used
1766         // by machine code of multiple LLVM instructions, viz.,
1767         // the SetCC and the branch.  Make sure to get the same one!
1768         // Note that we do this even for FP CC registers even though they
1769         // are explicit operands, because the type of the operand
1770         // needs to be a floating point condition code, not an integer
1771         // condition code.  Think of this as casting the bool result to
1772         // a FP condition code register.
1773         //
1774         Value* leftVal = subtreeRoot->leftChild()->getValue();
1775         bool isFPCompare = leftVal->getType()->isFloatingPoint();
1776
1777         TmpInstruction* tmpForCC = GetTmpForCC(setCCInstr,
1778                                      setCCInstr->getParent()->getParent(),
1779                                      isFPCompare ? Type::FloatTy : Type::IntTy);
1780         MachineCodeForInstruction::get(setCCInstr).addTemp(tmpForCC);
1781
1782         if (! isFPCompare)
1783           {
1784             // Integer condition: dest. should be %g0 or an integer register.
1785             // If result must be saved but condition is not SetEQ then we need
1786             // a separate instruction to compute the bool result, so discard
1787             // result of SUBcc instruction anyway.
1788             //
1789             if (keepSubVal) {
1790               M = BuildMI(SUBcc, 4).addReg(subtreeRoot->leftChild()->getValue())
1791                                   .addReg(subtreeRoot->rightChild()->getValue())
1792                                   .addRegDef(subtreeRoot->getValue())
1793                                   .addCCReg(tmpForCC, MOTy::Def);
1794             } else {
1795               M = BuildMI(SUBcc, 4).addReg(subtreeRoot->leftChild()->getValue())
1796                                   .addReg(subtreeRoot->rightChild()->getValue())
1797                         .addMReg(target.getRegInfo().getZeroRegNum(), MOTy::Def)
1798                                   .addCCReg(tmpForCC, MOTy::Def);
1799             }
1800             mvec.push_back(M);
1801
1802             if (computeBoolVal)
1803               { // recompute bool using the integer condition codes
1804                 movOpCode =
1805                   ChooseMovpccAfterSub(subtreeRoot,mustClearReg,valueToMove);
1806               }
1807           }
1808         else
1809           {
1810             // FP condition: dest of FCMP should be some FCCn register
1811             M = BuildMI(ChooseFcmpInstruction(subtreeRoot), 3)
1812                          .addCCReg(tmpForCC, MOTy::Def)
1813                          .addReg(subtreeRoot->leftChild()->getValue())
1814                          .addRegDef(subtreeRoot->rightChild()->getValue());
1815             mvec.push_back(M);
1816
1817             if (computeBoolVal)
1818               {// recompute bool using the FP condition codes
1819                 mustClearReg = true;
1820                 valueToMove = 1;
1821                 movOpCode = ChooseMovFpccInstruction(subtreeRoot);
1822               }
1823           }
1824
1825         if (computeBoolVal)
1826           {
1827             if (mustClearReg)
1828               {// Unconditionally set register to 0
1829                 M = BuildMI(SETHI, 2).addZImm(0).addRegDef(setCCInstr);
1830                 mvec.push_back(M);
1831               }
1832
1833             // Now conditionally move `valueToMove' (0 or 1) into the register
1834             // Mark the register as a use (as well as a def) because the old
1835             // value should be retained if the condition is false.
1836             M = BuildMI(movOpCode, 3).addCCReg(tmpForCC).addZImm(valueToMove)
1837                                      .addReg(setCCInstr, MOTy::UseAndDef);
1838             mvec.push_back(M);
1839           }
1840         break;
1841       }
1842
1843       case 51:  // reg:   Load(reg)
1844       case 52:  // reg:   Load(ptrreg)
1845         SetOperandsForMemInstr(ChooseLoadInstruction(
1846                                    subtreeRoot->getValue()->getType()),
1847                                mvec, subtreeRoot, target);
1848         break;
1849
1850       case 55:  // reg:   GetElemPtr(reg)
1851       case 56:  // reg:   GetElemPtrIdx(reg,reg)
1852         // If the GetElemPtr was folded into the user (parent), it will be
1853         // caught above.  For other cases, we have to compute the address.
1854         SetOperandsForMemInstr(ADD, mvec, subtreeRoot, target);
1855         break;
1856
1857       case 57:  // reg:  Alloca: Implement as 1 instruction:
1858       {         //          add %fp, offsetFromFP -> result
1859         AllocationInst* instr =
1860           cast<AllocationInst>(subtreeRoot->getInstruction());
1861         unsigned tsize =
1862           target.getTargetData().getTypeSize(instr->getAllocatedType());
1863         assert(tsize != 0);
1864         CreateCodeForFixedSizeAlloca(target, instr, tsize, 1, mvec);
1865         break;
1866       }
1867
1868       case 58:  // reg:   Alloca(reg): Implement as 3 instructions:
1869                 //      mul num, typeSz -> tmp
1870                 //      sub %sp, tmp    -> %sp
1871       {         //      add %sp, frameSizeBelowDynamicArea -> result
1872         AllocationInst* instr =
1873           cast<AllocationInst>(subtreeRoot->getInstruction());
1874         const Type* eltType = instr->getAllocatedType();
1875
1876         // If #elements is constant, use simpler code for fixed-size allocas
1877         int tsize = (int) target.getTargetData().getTypeSize(eltType);
1878         Value* numElementsVal = NULL;
1879         bool isArray = instr->isArrayAllocation();
1880
1881         if (!isArray ||
1882             isa<Constant>(numElementsVal = instr->getArraySize()))
1883           { // total size is constant: generate code for fixed-size alloca
1884             unsigned numElements = isArray?
1885               cast<ConstantUInt>(numElementsVal)->getValue() : 1;
1886             CreateCodeForFixedSizeAlloca(target, instr, tsize,
1887                                          numElements, mvec);
1888           }
1889         else // total size is not constant.
1890           CreateCodeForVariableSizeAlloca(target, instr, tsize,
1891                                           numElementsVal, mvec);
1892         break;
1893       }
1894
1895       case 61:  // reg:   Call
1896       {         // Generate a direct (CALL) or indirect (JMPL) call.
1897                 // Mark the return-address register, the indirection
1898                 // register (for indirect calls), the operands of the Call,
1899                 // and the return value (if any) as implicit operands
1900                 // of the machine instruction.
1901                 //
1902                 // If this is a varargs function, floating point arguments
1903                 // have to passed in integer registers so insert
1904                 // copy-float-to-int instructions for each float operand.
1905                 //
1906         CallInst *callInstr = cast<CallInst>(subtreeRoot->getInstruction());
1907         Value *callee = callInstr->getCalledValue();
1908
1909         // Create hidden virtual register for return address with type void*
1910         TmpInstruction* retAddrReg =
1911           new TmpInstruction(PointerType::get(Type::VoidTy), callInstr);
1912         MachineCodeForInstruction::get(callInstr).addTemp(retAddrReg);
1913
1914         // Generate the machine instruction and its operands.
1915         // Use CALL for direct function calls; this optimistically assumes
1916         // the PC-relative address fits in the CALL address field (22 bits).
1917         // Use JMPL for indirect calls.
1918         //
1919         if (isa<Function>(callee))      // direct function call
1920           M = BuildMI(CALL, 1).addPCDisp(callee);
1921         else                            // indirect function call
1922           M = BuildMI(JMPLCALL, 3).addReg(callee).addSImm((int64_t)0)
1923                                   .addRegDef(retAddrReg);
1924         mvec.push_back(M);
1925
1926         const FunctionType* funcType =
1927           cast<FunctionType>(cast<PointerType>(callee->getType())
1928                              ->getElementType());
1929         bool isVarArgs = funcType->isVarArg();
1930         bool noPrototype = isVarArgs && funcType->getNumParams() == 0;
1931
1932         // Use a descriptor to pass information about call arguments
1933         // to the register allocator.  This descriptor will be "owned"
1934         // and freed automatically when the MachineCodeForInstruction
1935         // object for the callInstr goes away.
1936         CallArgsDescriptor* argDesc = new CallArgsDescriptor(callInstr,
1937                                          retAddrReg, isVarArgs, noPrototype);
1938
1939         assert(callInstr->getOperand(0) == callee
1940                && "This is assumed in the loop below!");
1941
1942         for (unsigned i=1, N=callInstr->getNumOperands(); i < N; ++i)
1943           {
1944             Value* argVal = callInstr->getOperand(i);
1945             Instruction* intArgReg = NULL;
1946
1947             // Check for FP arguments to varargs functions.
1948             // Any such argument in the first $K$ args must be passed in an
1949             // integer register, where K = #integer argument registers.
1950             if (isVarArgs && argVal->getType()->isFloatingPoint())
1951               {
1952                 // If it is a function with no prototype, pass value
1953                 // as an FP value as well as a varargs value
1954                 if (noPrototype)
1955                   argDesc->getArgInfo(i-1).setUseFPArgReg();
1956
1957                 // If this arg. is in the first $K$ regs, add a copy
1958                 // float-to-int instruction to pass the value as an integer.
1959                 if (i <= target.getRegInfo().GetNumOfIntArgRegs())
1960                   {
1961                     MachineCodeForInstruction &destMCFI =
1962                       MachineCodeForInstruction::get(callInstr);
1963                     intArgReg = new TmpInstruction(Type::IntTy, argVal);
1964                     destMCFI.addTemp(intArgReg);
1965
1966                     vector<MachineInstr*> copyMvec;
1967                     target.getInstrInfo().CreateCodeToCopyFloatToInt(target,
1968                                            callInstr->getParent()->getParent(),
1969                                            argVal, (TmpInstruction*) intArgReg,
1970                                            copyMvec, destMCFI);
1971                     mvec.insert(mvec.begin(),copyMvec.begin(),copyMvec.end());
1972
1973                     argDesc->getArgInfo(i-1).setUseIntArgReg();
1974                     argDesc->getArgInfo(i-1).setArgCopy(intArgReg);
1975                   }
1976                 else
1977                   // Cannot fit in first $K$ regs so pass the arg on the stack
1978                   argDesc->getArgInfo(i-1).setUseStackSlot();
1979               }
1980
1981             if (intArgReg)
1982               mvec.back()->addImplicitRef(intArgReg);
1983
1984             mvec.back()->addImplicitRef(argVal);
1985           }
1986
1987         // Add the return value as an implicit ref.  The call operands
1988         // were added above.
1989         if (callInstr->getType() != Type::VoidTy)
1990           mvec.back()->addImplicitRef(callInstr, /*isDef*/ true);
1991
1992         // For the CALL instruction, the ret. addr. reg. is also implicit
1993         if (isa<Function>(callee))
1994           mvec.back()->addImplicitRef(retAddrReg, /*isDef*/ true);
1995
1996         // delay slot
1997         mvec.push_back(BuildMI(NOP, 0));
1998         break;
1999       }
2000
2001       case 62:  // reg:   Shl(reg, reg)
2002       {
2003         Value* argVal1 = subtreeRoot->leftChild()->getValue();
2004         Value* argVal2 = subtreeRoot->rightChild()->getValue();
2005         Instruction* shlInstr = subtreeRoot->getInstruction();
2006
2007         const Type* opType = argVal1->getType();
2008         assert((opType->isInteger() || isa<PointerType>(opType)) &&
2009                "Shl unsupported for other types");
2010
2011         CreateShiftInstructions(target, shlInstr->getParent()->getParent(),
2012                                 (opType == Type::LongTy)? SLLX : SLL,
2013                                 argVal1, argVal2, 0, shlInstr, mvec,
2014                                 MachineCodeForInstruction::get(shlInstr));
2015         break;
2016       }
2017
2018       case 63:  // reg:   Shr(reg, reg)
2019       { const Type* opType = subtreeRoot->leftChild()->getValue()->getType();
2020         assert((opType->isInteger() || isa<PointerType>(opType)) &&
2021                "Shr unsupported for other types");
2022         Add3OperandInstr(opType->isSigned()
2023                                ? (opType == Type::LongTy ? SRAX : SRA)
2024                                : (opType == Type::LongTy ? SRLX : SRL),
2025                          subtreeRoot, mvec);
2026         break;
2027       }
2028
2029       case 64:  // reg:   Phi(reg,reg)
2030         break;                          // don't forward the value
2031
2032       case 71:  // reg:     VReg
2033       case 72:  // reg:     Constant
2034         break;                          // don't forward the value
2035
2036       default:
2037         assert(0 && "Unrecognized BURG rule");
2038         break;
2039       }
2040     }
2041
2042   if (forwardOperandNum >= 0)
2043     { // We did not generate a machine instruction but need to use operand.
2044       // If user is in the same tree, replace Value in its machine operand.
2045       // If not, insert a copy instruction which should get coalesced away
2046       // by register allocation.
2047       if (subtreeRoot->parent() != NULL)
2048         ForwardOperand(subtreeRoot, subtreeRoot->parent(), forwardOperandNum);
2049       else
2050         {
2051           vector<MachineInstr*> minstrVec;
2052           Instruction* instr = subtreeRoot->getInstruction();
2053           target.getInstrInfo().
2054             CreateCopyInstructionsByType(target,
2055                                          instr->getParent()->getParent(),
2056                                          instr->getOperand(forwardOperandNum),
2057                                          instr, minstrVec,
2058                                         MachineCodeForInstruction::get(instr));
2059           assert(minstrVec.size() > 0);
2060           mvec.insert(mvec.end(), minstrVec.begin(), minstrVec.end());
2061         }
2062     }
2063
2064   if (maskUnsignedResult)
2065     { // If result is unsigned and smaller than int reg size,
2066       // we need to clear high bits of result value.
2067       assert(forwardOperandNum < 0 && "Need mask but no instruction generated");
2068       Instruction* dest = subtreeRoot->getInstruction();
2069       if (dest->getType()->isUnsigned())
2070         {
2071           unsigned destSize=target.getTargetData().getTypeSize(dest->getType());
2072           if (destSize <= 4)
2073             { // Mask high bits.  Use a TmpInstruction to represent the
2074               // intermediate result before masking.  Since those instructions
2075               // have already been generated, go back and substitute tmpI
2076               // for dest in the result position of each one of them.
2077               TmpInstruction *tmpI = new TmpInstruction(dest->getType(), dest,
2078                                                         NULL, "maskHi");
2079               MachineCodeForInstruction::get(dest).addTemp(tmpI);
2080
2081               for (unsigned i=0, N=mvec.size(); i < N; ++i)
2082                 mvec[i]->substituteValue(dest, tmpI);
2083
2084               M = BuildMI(SRL, 3).addReg(tmpI).addZImm(8*(4-destSize))
2085                                  .addReg(dest, MOTy::Def);
2086               mvec.push_back(M);
2087             }
2088           else if (destSize < target.getTargetData().getIntegerRegize())
2089             assert(0 && "Unsupported type size: 32 < size < 64 bits");
2090         }
2091     }
2092 }