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