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