lib/Target/SparcV9/SparcV9InstrSelection.cpp

   1 //===-- SparcInstrSelection.cpp -------------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  BURS instruction selection for SPARC V9 architecture.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Constants.h"
  15 #include "llvm/DerivedTypes.h"
  16 #include "llvm/Instructions.h"
  17 #include "llvm/Intrinsics.h"
  18 #include "llvm/Module.h"
  19 #include "llvm/CodeGen/InstrForest.h"
  20 #include "llvm/CodeGen/InstrSelection.h"
  21 #include "llvm/CodeGen/InstrSelectionSupport.h"
  22 #include "llvm/CodeGen/MachineCodeForInstruction.h"
  23 #include "llvm/CodeGen/MachineFunction.h"
  24 #include "llvm/CodeGen/MachineFunctionInfo.h"
  25 #include "llvm/CodeGen/MachineInstrBuilder.h"
  26 #include "llvm/CodeGen/MachineInstrAnnot.h"
  27 #include "SparcInstrSelectionSupport.h"
  28 #include "SparcInternals.h"
  29 #include "SparcRegClassInfo.h"
  30 #include "SparcRegInfo.h"
  31 #include "Support/MathExtras.h"
  32 #include <algorithm>
  33 #include <cmath>
  34
  35 namespace llvm {
  36
  37 static inline void Add3OperandInstr(unsigned Opcode, InstructionNode* Node,
  38                                     std::vector<MachineInstr*>& mvec) {
  39   mvec.push_back(BuildMI(Opcode, 3).addReg(Node->leftChild()->getValue())
  40                                    .addReg(Node->rightChild()->getValue())
  41                                    .addRegDef(Node->getValue()));
  42 }
  43
  44
  45 //---------------------------------------------------------------------------
  46 // Function: FoldGetElemChain
  47 //
  48 // Purpose:
  49 //   Fold a chain of GetElementPtr instructions containing only
  50 //   constant offsets into an equivalent (Pointer, IndexVector) pair.
  51 //   Returns the pointer Value, and stores the resulting IndexVector
  52 //   in argument chainIdxVec. This is a helper function for
  53 //   FoldConstantIndices that does the actual folding.
  54 //---------------------------------------------------------------------------
  55
  56
  57 // Check for a constant 0.
  58 static inline bool
  59 IsZero(Value* idx)
  60 {
  61   return (idx == ConstantSInt::getNullValue(idx->getType()));
  62 }
  63
  64 static Value*
  65 FoldGetElemChain(InstrTreeNode* ptrNode, std::vector<Value*>& chainIdxVec,
  66                  bool lastInstHasLeadingNonZero)
  67 {
  68   InstructionNode* gepNode = dyn_cast<InstructionNode>(ptrNode);
  69   GetElementPtrInst* gepInst =
  70     dyn_cast_or_null<GetElementPtrInst>(gepNode ? gepNode->getInstruction() :0);
  71
  72   // ptr value is not computed in this tree or ptr value does not come from GEP
  73   // instruction
  74   if (gepInst == NULL)
  75     return NULL;
  76
  77   // Return NULL if we don't fold any instructions in.
  78   Value* ptrVal = NULL;
  79
  80   // Now chase the chain of getElementInstr instructions, if any.
  81   // Check for any non-constant indices and stop there.
  82   // Also, stop if the first index of child is a non-zero array index
  83   // and the last index of the current node is a non-array index:
  84   // in that case, a non-array declared type is being accessed as an array
  85   // which is not type-safe, but could be legal.
  86   //
  87   InstructionNode* ptrChild = gepNode;
  88   while (ptrChild && (ptrChild->getOpLabel() == Instruction::GetElementPtr ||
  89                       ptrChild->getOpLabel() == GetElemPtrIdx))
  90   {
  91     // Child is a GetElemPtr instruction
  92     gepInst = cast<GetElementPtrInst>(ptrChild->getValue());
  93     User::op_iterator OI, firstIdx = gepInst->idx_begin();
  94     User::op_iterator lastIdx = gepInst->idx_end();
  95     bool allConstantOffsets = true;
  96
  97     // The first index of every GEP must be an array index.
  98     assert((*firstIdx)->getType() == Type::LongTy &&
  99            "INTERNAL ERROR: Structure index for a pointer type!");
 100
 101     // If the last instruction had a leading non-zero index, check if the
 102     // current one references a sequential (i.e., indexable) type.
 103     // If not, the code is not type-safe and we would create an illegal GEP
 104     // by folding them, so don't fold any more instructions.
 105     //
 106     if (lastInstHasLeadingNonZero)
 107       if (! isa<SequentialType>(gepInst->getType()->getElementType()))
 108         break;   // cannot fold in any preceding getElementPtr instrs.
 109
 110     // Check that all offsets are constant for this instruction
 111     for (OI = firstIdx; allConstantOffsets && OI != lastIdx; ++OI)
 112       allConstantOffsets = isa<ConstantInt>(*OI);
 113
 114     if (allConstantOffsets) {
 115       // Get pointer value out of ptrChild.
 116       ptrVal = gepInst->getPointerOperand();
 117
 118       // Insert its index vector at the start, skipping any leading [0]
 119       // Remember the old size to check if anything was inserted.
 120       unsigned oldSize = chainIdxVec.size();
 121       int firstIsZero = IsZero(*firstIdx);
 122       chainIdxVec.insert(chainIdxVec.begin(), firstIdx + firstIsZero, lastIdx);
 123
 124       // Remember if it has leading zero index: it will be discarded later.
 125       if (oldSize < chainIdxVec.size())
 126         lastInstHasLeadingNonZero = !firstIsZero;
 127
 128       // Mark the folded node so no code is generated for it.
 129       ((InstructionNode*) ptrChild)->markFoldedIntoParent();
 130
 131       // Get the previous GEP instruction and continue trying to fold
 132       ptrChild = dyn_cast<InstructionNode>(ptrChild->leftChild());
 133     } else // cannot fold this getElementPtr instr. or any preceding ones
 134       break;
 135   }
 136
 137   // If the first getElementPtr instruction had a leading [0], add it back.
 138   // Note that this instruction is the *last* one that was successfully
 139   // folded *and* contributed any indices, in the loop above.
 140   //
 141   if (ptrVal && ! lastInstHasLeadingNonZero)
 142     chainIdxVec.insert(chainIdxVec.begin(), ConstantSInt::get(Type::LongTy,0));
 143
 144   return ptrVal;
 145 }
 146
 147
 148 //---------------------------------------------------------------------------
 149 // Function: GetGEPInstArgs
 150 //
 151 // Purpose:
 152 //   Helper function for GetMemInstArgs that handles the final getElementPtr
 153 //   instruction used by (or same as) the memory operation.
 154 //   Extracts the indices of the current instruction and tries to fold in
 155 //   preceding ones if all indices of the current one are constant.
 156 //---------------------------------------------------------------------------
 157
 158 static Value *
 159 GetGEPInstArgs(InstructionNode* gepNode,
 160                std::vector<Value*>& idxVec,
 161                bool& allConstantIndices)
 162 {
 163   allConstantIndices = true;
 164   GetElementPtrInst* gepI = cast<GetElementPtrInst>(gepNode->getInstruction());
 165
 166   // Default pointer is the one from the current instruction.
 167   Value* ptrVal = gepI->getPointerOperand();
 168   InstrTreeNode* ptrChild = gepNode->leftChild();
 169
 170   // Extract the index vector of the GEP instruction.
 171   // If all indices are constant and first index is zero, try to fold
 172   // in preceding GEPs with all constant indices.
 173   for (User::op_iterator OI=gepI->idx_begin(),  OE=gepI->idx_end();
 174        allConstantIndices && OI != OE; ++OI)
 175     if (! isa<Constant>(*OI))
 176       allConstantIndices = false;     // note: this also terminates loop!
 177
 178   // If we have only constant indices, fold chains of constant indices
 179   // in this and any preceding GetElemPtr instructions.
 180   bool foldedGEPs = false;
 181   bool leadingNonZeroIdx = gepI && ! IsZero(*gepI->idx_begin());
 182   if (allConstantIndices)
 183     if (Value* newPtr = FoldGetElemChain(ptrChild, idxVec, leadingNonZeroIdx)) {
 184       ptrVal = newPtr;
 185       foldedGEPs = true;
 186     }
 187
 188   // Append the index vector of the current instruction.
 189   // Skip the leading [0] index if preceding GEPs were folded into this.
 190   idxVec.insert(idxVec.end(),
 191                 gepI->idx_begin() + (foldedGEPs && !leadingNonZeroIdx),
 192                 gepI->idx_end());
 193
 194   return ptrVal;
 195 }
 196
 197 //---------------------------------------------------------------------------
 198 // Function: GetMemInstArgs
 199 //
 200 // Purpose:
 201 //   Get the pointer value and the index vector for a memory operation
 202 //   (GetElementPtr, Load, or Store).  If all indices of the given memory
 203 //   operation are constant, fold in constant indices in a chain of
 204 //   preceding GetElementPtr instructions (if any), and return the
 205 //   pointer value of the first instruction in the chain.
 206 //   All folded instructions are marked so no code is generated for them.
 207 //
 208 // Return values:
 209 //   Returns the pointer Value to use.
 210 //   Returns the resulting IndexVector in idxVec.
 211 //   Returns true/false in allConstantIndices if all indices are/aren't const.
 212 //---------------------------------------------------------------------------
 213
 214 static Value*
 215 GetMemInstArgs(InstructionNode* memInstrNode,
 216                std::vector<Value*>& idxVec,
 217                bool& allConstantIndices)
 218 {
 219   allConstantIndices = false;
 220   Instruction* memInst = memInstrNode->getInstruction();
 221   assert(idxVec.size() == 0 && "Need empty vector to return indices");
 222
 223   // If there is a GetElemPtr instruction to fold in to this instr,
 224   // it must be in the left child for Load and GetElemPtr, and in the
 225   // right child for Store instructions.
 226   InstrTreeNode* ptrChild = (memInst->getOpcode() == Instruction::Store
 227                              ? memInstrNode->rightChild()
 228                              : memInstrNode->leftChild());
 229
 230   // Default pointer is the one from the current instruction.
 231   Value* ptrVal = ptrChild->getValue();
 232
 233   // Find the "last" GetElemPtr instruction: this one or the immediate child.
 234   // There will be none if this is a load or a store from a scalar pointer.
 235   InstructionNode* gepNode = NULL;
 236   if (isa<GetElementPtrInst>(memInst))
 237     gepNode = memInstrNode;
 238   else if (isa<InstructionNode>(ptrChild) && isa<GetElementPtrInst>(ptrVal)) {
 239     // Child of load/store is a GEP and memInst is its only use.
 240     // Use its indices and mark it as folded.
 241     gepNode = cast<InstructionNode>(ptrChild);
 242     gepNode->markFoldedIntoParent();
 243   }
 244
 245   // If there are no indices, return the current pointer.
 246   // Else extract the pointer from the GEP and fold the indices.
 247   return gepNode ? GetGEPInstArgs(gepNode, idxVec, allConstantIndices)
 248                  : ptrVal;
 249 }
 250
 251
 252 //************************ Internal Functions ******************************/
 253
 254
 255 static inline MachineOpCode
 256 ChooseBprInstruction(const InstructionNode* instrNode)
 257 {
 258   MachineOpCode opCode;
 259
 260   Instruction* setCCInstr =
 261     ((InstructionNode*) instrNode->leftChild())->getInstruction();
 262
 263   switch(setCCInstr->getOpcode())
 264   {
 265   case Instruction::SetEQ: opCode = V9::BRZ;   break;
 266   case Instruction::SetNE: opCode = V9::BRNZ;  break;
 267   case Instruction::SetLE: opCode = V9::BRLEZ; break;
 268   case Instruction::SetGE: opCode = V9::BRGEZ; break;
 269   case Instruction::SetLT: opCode = V9::BRLZ;  break;
 270   case Instruction::SetGT: opCode = V9::BRGZ;  break;
 271   default:
 272     assert(0 && "Unrecognized VM instruction!");
 273     opCode = V9::INVALID_OPCODE;
 274     break;
 275   }
 276
 277   return opCode;
 278 }
 279
 280
 281 static inline MachineOpCode
 282 ChooseBpccInstruction(const InstructionNode* instrNode,
 283                       const BinaryOperator* setCCInstr)
 284 {
 285   MachineOpCode opCode = V9::INVALID_OPCODE;
 286
 287   bool isSigned = setCCInstr->getOperand(0)->getType()->isSigned();
 288
 289   if (isSigned) {
 290     switch(setCCInstr->getOpcode())
 291     {
 292     case Instruction::SetEQ: opCode = V9::BE;  break;
 293     case Instruction::SetNE: opCode = V9::BNE; break;
 294     case Instruction::SetLE: opCode = V9::BLE; break;
 295     case Instruction::SetGE: opCode = V9::BGE; break;
 296     case Instruction::SetLT: opCode = V9::BL;  break;
 297     case Instruction::SetGT: opCode = V9::BG;  break;
 298     default:
 299       assert(0 && "Unrecognized VM instruction!");
 300       break;
 301     }
 302   } else {
 303     switch(setCCInstr->getOpcode())
 304     {
 305     case Instruction::SetEQ: opCode = V9::BE;   break;
 306     case Instruction::SetNE: opCode = V9::BNE;  break;
 307     case Instruction::SetLE: opCode = V9::BLEU; break;
 308     case Instruction::SetGE: opCode = V9::BCC;  break;
 309     case Instruction::SetLT: opCode = V9::BCS;  break;
 310     case Instruction::SetGT: opCode = V9::BGU;  break;
 311     default:
 312       assert(0 && "Unrecognized VM instruction!");
 313       break;
 314     }
 315   }
 316
 317   return opCode;
 318 }
 319
 320 static inline MachineOpCode
 321 ChooseBFpccInstruction(const InstructionNode* instrNode,
 322                        const BinaryOperator* setCCInstr)
 323 {
 324   MachineOpCode opCode = V9::INVALID_OPCODE;
 325
 326   switch(setCCInstr->getOpcode())
 327   {
 328   case Instruction::SetEQ: opCode = V9::FBE;  break;
 329   case Instruction::SetNE: opCode = V9::FBNE; break;
 330   case Instruction::SetLE: opCode = V9::FBLE; break;
 331   case Instruction::SetGE: opCode = V9::FBGE; break;
 332   case Instruction::SetLT: opCode = V9::FBL;  break;
 333   case Instruction::SetGT: opCode = V9::FBG;  break;
 334   default:
 335     assert(0 && "Unrecognized VM instruction!");
 336     break;
 337   }
 338
 339   return opCode;
 340 }
 341
 342
 343 // Create a unique TmpInstruction for a boolean value,
 344 // representing the CC register used by a branch on that value.
 345 // For now, hack this using a little static cache of TmpInstructions.
 346 // Eventually the entire BURG instruction selection should be put
 347 // into a separate class that can hold such information.
 348 // The static cache is not too bad because the memory for these
 349 // TmpInstructions will be freed along with the rest of the Function anyway.
 350 //
 351 static TmpInstruction*
 352 GetTmpForCC(Value* boolVal, const Function *F, const Type* ccType,
 353             MachineCodeForInstruction& mcfi)
 354 {
 355   typedef hash_map<const Value*, TmpInstruction*> BoolTmpCache;
 356   static BoolTmpCache boolToTmpCache;     // Map boolVal -> TmpInstruction*
 357   static const Function *lastFunction = 0;// Use to flush cache between funcs
 358
 359   assert(boolVal->getType() == Type::BoolTy && "Weird but ok! Delete assert");
 360
 361   if (lastFunction != F) {
 362     lastFunction = F;
 363     boolToTmpCache.clear();
 364   }
 365
 366   // Look for tmpI and create a new one otherwise.  The new value is
 367   // directly written to map using the ref returned by operator[].
 368   TmpInstruction*& tmpI = boolToTmpCache[boolVal];
 369   if (tmpI == NULL)
 370     tmpI = new TmpInstruction(mcfi, ccType, boolVal);
 371
 372   return tmpI;
 373 }
 374
 375
 376 static inline MachineOpCode
 377 ChooseBccInstruction(const InstructionNode* instrNode,
 378                      const Type*& setCCType)
 379 {
 380   InstructionNode* setCCNode = (InstructionNode*) instrNode->leftChild();
 381   assert(setCCNode->getOpLabel() == SetCCOp);
 382   BinaryOperator* setCCInstr =cast<BinaryOperator>(setCCNode->getInstruction());
 383   setCCType = setCCInstr->getOperand(0)->getType();
 384
 385   if (setCCType->isFloatingPoint())
 386     return ChooseBFpccInstruction(instrNode, setCCInstr);
 387   else
 388     return ChooseBpccInstruction(instrNode, setCCInstr);
 389 }
 390
 391
 392 // WARNING: since this function has only one caller, it always returns
 393 // the opcode that expects an immediate and a register. If this function
 394 // is ever used in cases where an opcode that takes two registers is required,
 395 // then modify this function and use convertOpcodeFromRegToImm() where required.
 396 //
 397 // It will be necessary to expand convertOpcodeFromRegToImm() to handle the
 398 // new cases of opcodes.
 399 static inline MachineOpCode
 400 ChooseMovFpcciInstruction(const InstructionNode* instrNode)
 401 {
 402   MachineOpCode opCode = V9::INVALID_OPCODE;
 403
 404   switch(instrNode->getInstruction()->getOpcode())
 405   {
 406   case Instruction::SetEQ: opCode = V9::MOVFEi;  break;
 407   case Instruction::SetNE: opCode = V9::MOVFNEi; break;
 408   case Instruction::SetLE: opCode = V9::MOVFLEi; break;
 409   case Instruction::SetGE: opCode = V9::MOVFGEi; break;
 410   case Instruction::SetLT: opCode = V9::MOVFLi;  break;
 411   case Instruction::SetGT: opCode = V9::MOVFGi;  break;
 412   default:
 413     assert(0 && "Unrecognized VM instruction!");
 414     break;
 415   }
 416
 417   return opCode;
 418 }
 419
 420
 421 // ChooseMovpcciForSetCC -- Choose a conditional-move instruction
 422 // based on the type of SetCC operation.
 423 //
 424 // WARNING: since this function has only one caller, it always returns
 425 // the opcode that expects an immediate and a register. If this function
 426 // is ever used in cases where an opcode that takes two registers is required,
 427 // then modify this function and use convertOpcodeFromRegToImm() where required.
 428 //
 429 // It will be necessary to expand convertOpcodeFromRegToImm() to handle the
 430 // new cases of opcodes.
 431 //
 432 static MachineOpCode
 433 ChooseMovpcciForSetCC(const InstructionNode* instrNode)
 434 {
 435   MachineOpCode opCode = V9::INVALID_OPCODE;
 436
 437   const Type* opType = instrNode->leftChild()->getValue()->getType();
 438   assert(opType->isIntegral() || isa<PointerType>(opType));
 439   bool noSign = opType->isUnsigned() || isa<PointerType>(opType);
 440
 441   switch(instrNode->getInstruction()->getOpcode())
 442   {
 443   case Instruction::SetEQ: opCode = V9::MOVEi;                        break;
 444   case Instruction::SetLE: opCode = noSign? V9::MOVLEUi : V9::MOVLEi; break;
 445   case Instruction::SetGE: opCode = noSign? V9::MOVCCi  : V9::MOVGEi; break;
 446   case Instruction::SetLT: opCode = noSign? V9::MOVCSi  : V9::MOVLi;  break;
 447   case Instruction::SetGT: opCode = noSign? V9::MOVGUi  : V9::MOVGi;  break;
 448   case Instruction::SetNE: opCode = V9::MOVNEi;                       break;
 449   default: assert(0 && "Unrecognized LLVM instr!"); break;
 450   }
 451
 452   return opCode;
 453 }
 454
 455
 456 // ChooseMovpregiForSetCC -- Choose a conditional-move-on-register-value
 457 // instruction based on the type of SetCC operation.  These instructions
 458 // compare a register with 0 and perform the move is the comparison is true.
 459 //
 460 // WARNING: like the previous function, this function it always returns
 461 // the opcode that expects an immediate and a register.  See above.
 462 //
 463 static MachineOpCode
 464 ChooseMovpregiForSetCC(const InstructionNode* instrNode)
 465 {
 466   MachineOpCode opCode = V9::INVALID_OPCODE;
 467
 468   switch(instrNode->getInstruction()->getOpcode())
 469   {
 470   case Instruction::SetEQ: opCode = V9::MOVRZi;  break;
 471   case Instruction::SetLE: opCode = V9::MOVRLEZi; break;
 472   case Instruction::SetGE: opCode = V9::MOVRGEZi; break;
 473   case Instruction::SetLT: opCode = V9::MOVRLZi;  break;
 474   case Instruction::SetGT: opCode = V9::MOVRGZi;  break;
 475   case Instruction::SetNE: opCode = V9::MOVRNZi; break;
 476   default: assert(0 && "Unrecognized VM instr!"); break;
 477   }
 478
 479   return opCode;
 480 }
 481
 482
 483 static inline MachineOpCode
 484 ChooseConvertToFloatInstr(const TargetMachine& target,
 485                           OpLabel vopCode, const Type* opType)
 486 {
 487   assert((vopCode == ToFloatTy || vopCode == ToDoubleTy) &&
 488          "Unrecognized convert-to-float opcode!");
 489   assert((opType->isIntegral() || opType->isFloatingPoint() ||
 490           isa<PointerType>(opType))
 491          && "Trying to convert a non-scalar type to FLOAT/DOUBLE?");
 492
 493   MachineOpCode opCode = V9::INVALID_OPCODE;
 494
 495   unsigned opSize = target.getTargetData().getTypeSize(opType);
 496
 497   if (opType == Type::FloatTy)
 498     opCode = (vopCode == ToFloatTy? V9::NOP : V9::FSTOD);
 499   else if (opType == Type::DoubleTy)
 500     opCode = (vopCode == ToFloatTy? V9::FDTOS : V9::NOP);
 501   else if (opSize <= 4)
 502     opCode = (vopCode == ToFloatTy? V9::FITOS : V9::FITOD);
 503   else {
 504     assert(opSize == 8 && "Unrecognized type size > 4 and < 8!");
 505     opCode = (vopCode == ToFloatTy? V9::FXTOS : V9::FXTOD);
 506   }
 507
 508   return opCode;
 509 }
 510
 511 static inline MachineOpCode
 512 ChooseConvertFPToIntInstr(const TargetMachine& target,
 513                           const Type* destType, const Type* opType)
 514 {
 515   assert((opType == Type::FloatTy || opType == Type::DoubleTy)
 516          && "This function should only be called for FLOAT or DOUBLE");
 517   assert((destType->isIntegral() || isa<PointerType>(destType))
 518          && "Trying to convert FLOAT/DOUBLE to a non-scalar type?");
 519
 520   MachineOpCode opCode = V9::INVALID_OPCODE;
 521
 522   unsigned destSize = target.getTargetData().getTypeSize(destType);
 523
 524   if (destType == Type::UIntTy)
 525     assert(destType != Type::UIntTy && "Expand FP-to-uint beforehand.");
 526   else if (destSize <= 4)
 527     opCode = (opType == Type::FloatTy)? V9::FSTOI : V9::FDTOI;
 528   else {
 529     assert(destSize == 8 && "Unrecognized type size > 4 and < 8!");
 530     opCode = (opType == Type::FloatTy)? V9::FSTOX : V9::FDTOX;
 531   }
 532
 533   return opCode;
 534 }
 535
 536 static MachineInstr*
 537 CreateConvertFPToIntInstr(const TargetMachine& target,
 538                           Value* srcVal,
 539                           Value* destVal,
 540                           const Type* destType)
 541 {
 542   MachineOpCode opCode = ChooseConvertFPToIntInstr(target, destType,
 543                                                    srcVal->getType());
 544   assert(opCode != V9::INVALID_OPCODE && "Expected to need conversion!");
 545   return BuildMI(opCode, 2).addReg(srcVal).addRegDef(destVal);
 546 }
 547
 548 // CreateCodeToConvertFloatToInt: Convert FP value to signed or unsigned integer
 549 // The FP value must be converted to the dest type in an FP register,
 550 // and the result is then copied from FP to int register via memory.
 551 // SPARC does not have a float-to-uint conversion, only a float-to-int (fdtoi).
 552 // Since fdtoi converts to signed integers, any FP value V between MAXINT+1
 553 // and MAXUNSIGNED (i.e., 2^31 <= V <= 2^32-1) would be converted incorrectly.
 554 // Therefore, for converting an FP value to uint32_t, we first need to convert
 555 // to uint64_t and then to uint32_t.
 556 //
 557 static void
 558 CreateCodeToConvertFloatToInt(const TargetMachine& target,
 559                               Value* opVal,
 560                               Instruction* destI,
 561                               std::vector<MachineInstr*>& mvec,
 562                               MachineCodeForInstruction& mcfi)
 563 {
 564   Function* F = destI->getParent()->getParent();
 565
 566   // Create a temporary to represent the FP register into which the
 567   // int value will placed after conversion.  The type of this temporary
 568   // depends on the type of FP register to use: single-prec for a 32-bit
 569   // int or smaller; double-prec for a 64-bit int.
 570   //
 571   size_t destSize = target.getTargetData().getTypeSize(destI->getType());
 572
 573   const Type* castDestType = destI->getType(); // type for the cast instr result
 574   const Type* castDestRegType;          // type for cast instruction result reg
 575   TmpInstruction* destForCast;          // dest for cast instruction
 576   Instruction* fpToIntCopyDest = destI; // dest for fp-reg-to-int-reg copy instr
 577
 578   // For converting an FP value to uint32_t, we first need to convert to
 579   // uint64_t and then to uint32_t, as explained above.
 580   if (destI->getType() == Type::UIntTy) {
 581     castDestType    = Type::ULongTy;       // use this instead of type of destI
 582     castDestRegType = Type::DoubleTy;      // uint64_t needs 64-bit FP register.
 583     destForCast     = new TmpInstruction(mcfi, castDestRegType, opVal);
 584     fpToIntCopyDest = new TmpInstruction(mcfi, castDestType, destForCast);
 585   }
 586   else {
 587     castDestRegType = (destSize > 4)? Type::DoubleTy : Type::FloatTy;
 588     destForCast = new TmpInstruction(mcfi, castDestRegType, opVal);
 589   }
 590
 591   // Create the fp-to-int conversion instruction (src and dest regs are FP regs)
 592   mvec.push_back(CreateConvertFPToIntInstr(target, opVal, destForCast,
 593                                            castDestType));
 594
 595   // Create the fpreg-to-intreg copy code
 596   target.getInstrInfo().CreateCodeToCopyFloatToInt(target, F, destForCast,
 597                                                    fpToIntCopyDest, mvec, mcfi);
 598
 599   // Create the uint64_t to uint32_t conversion, if needed
 600   if (destI->getType() == Type::UIntTy)
 601     target.getInstrInfo().
 602       CreateZeroExtensionInstructions(target, F, fpToIntCopyDest, destI,
 603                                       /*numLowBits*/ 32, mvec, mcfi);
 604 }
 605
 606
 607 static inline MachineOpCode
 608 ChooseAddInstruction(const InstructionNode* instrNode)
 609 {
 610   return ChooseAddInstructionByType(instrNode->getInstruction()->getType());
 611 }
 612
 613
 614 static inline MachineInstr*
 615 CreateMovFloatInstruction(const InstructionNode* instrNode,
 616                           const Type* resultType)
 617 {
 618   return BuildMI((resultType == Type::FloatTy) ? V9::FMOVS : V9::FMOVD, 2)
 619                    .addReg(instrNode->leftChild()->getValue())
 620                    .addRegDef(instrNode->getValue());
 621 }
 622
 623 static inline MachineInstr*
 624 CreateAddConstInstruction(const InstructionNode* instrNode)
 625 {
 626   MachineInstr* minstr = NULL;
 627
 628   Value* constOp = ((InstrTreeNode*) instrNode->rightChild())->getValue();
 629   assert(isa<Constant>(constOp));
 630
 631   // Cases worth optimizing are:
 632   // (1) Add with 0 for float or double: use an FMOV of appropriate type,
 633   //     instead of an FADD (1 vs 3 cycles).  There is no integer MOV.
 634   //
 635   if (ConstantFP *FPC = dyn_cast<ConstantFP>(constOp)) {
 636     double dval = FPC->getValue();
 637     if (dval == 0.0)
 638       minstr = CreateMovFloatInstruction(instrNode,
 639                                         instrNode->getInstruction()->getType());
 640   }
 641
 642   return minstr;
 643 }
 644
 645
 646 static inline MachineOpCode
 647 ChooseSubInstructionByType(const Type* resultType)
 648 {
 649   MachineOpCode opCode = V9::INVALID_OPCODE;
 650
 651   if (resultType->isInteger() || isa<PointerType>(resultType)) {
 652       opCode = V9::SUBr;
 653   } else {
 654     switch(resultType->getPrimitiveID())
 655     {
 656     case Type::FloatTyID:  opCode = V9::FSUBS; break;
 657     case Type::DoubleTyID: opCode = V9::FSUBD; break;
 658     default: assert(0 && "Invalid type for SUB instruction"); break;
 659     }
 660   }
 661
 662   return opCode;
 663 }
 664
 665
 666 static inline MachineInstr*
 667 CreateSubConstInstruction(const InstructionNode* instrNode)
 668 {
 669   MachineInstr* minstr = NULL;
 670
 671   Value* constOp = ((InstrTreeNode*) instrNode->rightChild())->getValue();
 672   assert(isa<Constant>(constOp));
 673
 674   // Cases worth optimizing are:
 675   // (1) Sub with 0 for float or double: use an FMOV of appropriate type,
 676   //     instead of an FSUB (1 vs 3 cycles).  There is no integer MOV.
 677   //
 678   if (ConstantFP *FPC = dyn_cast<ConstantFP>(constOp)) {
 679     double dval = FPC->getValue();
 680     if (dval == 0.0)
 681       minstr = CreateMovFloatInstruction(instrNode,
 682                                         instrNode->getInstruction()->getType());
 683   }
 684
 685   return minstr;
 686 }
 687
 688
 689 static inline MachineOpCode
 690 ChooseFcmpInstruction(const InstructionNode* instrNode)
 691 {
 692   MachineOpCode opCode = V9::INVALID_OPCODE;
 693
 694   Value* operand = ((InstrTreeNode*) instrNode->leftChild())->getValue();
 695   switch(operand->getType()->getPrimitiveID()) {
 696   case Type::FloatTyID:  opCode = V9::FCMPS; break;
 697   case Type::DoubleTyID: opCode = V9::FCMPD; break;
 698   default: assert(0 && "Invalid type for FCMP instruction"); break;
 699   }
 700
 701   return opCode;
 702 }
 703
 704
 705 // Assumes that leftArg and rightArg are both cast instructions.
 706 //
 707 static inline bool
 708 BothFloatToDouble(const InstructionNode* instrNode)
 709 {
 710   InstrTreeNode* leftArg = instrNode->leftChild();
 711   InstrTreeNode* rightArg = instrNode->rightChild();
 712   InstrTreeNode* leftArgArg = leftArg->leftChild();
 713   InstrTreeNode* rightArgArg = rightArg->leftChild();
 714   assert(leftArg->getValue()->getType() == rightArg->getValue()->getType());
 715
 716   // Check if both arguments are floats cast to double
 717   return (leftArg->getValue()->getType() == Type::DoubleTy &&
 718           leftArgArg->getValue()->getType() == Type::FloatTy &&
 719           rightArgArg->getValue()->getType() == Type::FloatTy);
 720 }
 721
 722
 723 static inline MachineOpCode
 724 ChooseMulInstructionByType(const Type* resultType)
 725 {
 726   MachineOpCode opCode = V9::INVALID_OPCODE;
 727
 728   if (resultType->isInteger())
 729     opCode = V9::MULXr;
 730   else
 731     switch(resultType->getPrimitiveID())
 732     {
 733     case Type::FloatTyID:  opCode = V9::FMULS; break;
 734     case Type::DoubleTyID: opCode = V9::FMULD; break;
 735     default: assert(0 && "Invalid type for MUL instruction"); break;
 736     }
 737
 738   return opCode;
 739 }
 740
 741
 742
 743 static inline MachineInstr*
 744 CreateIntNegInstruction(const TargetMachine& target,
 745                         Value* vreg)
 746 {
 747   return BuildMI(V9::SUBr, 3).addMReg(target.getRegInfo().getZeroRegNum())
 748     .addReg(vreg).addRegDef(vreg);
 749 }
 750
 751
 752 // Create instruction sequence for any shift operation.
 753 // SLL or SLLX on an operand smaller than the integer reg. size (64bits)
 754 // requires a second instruction for explicit sign-extension.
 755 // Note that we only have to worry about a sign-bit appearing in the
 756 // most significant bit of the operand after shifting (e.g., bit 32 of
 757 // Int or bit 16 of Short), so we do not have to worry about results
 758 // that are as large as a normal integer register.
 759 //
 760 static inline void
 761 CreateShiftInstructions(const TargetMachine& target,
 762                         Function* F,
 763                         MachineOpCode shiftOpCode,
 764                         Value* argVal1,
 765                         Value* optArgVal2, /* Use optArgVal2 if not NULL */
 766                         unsigned optShiftNum, /* else use optShiftNum */
 767                         Instruction* destVal,
 768                         std::vector<MachineInstr*>& mvec,
 769                         MachineCodeForInstruction& mcfi)
 770 {
 771   assert((optArgVal2 != NULL || optShiftNum <= 64) &&
 772          "Large shift sizes unexpected, but can be handled below: "
 773          "You need to check whether or not it fits in immed field below");
 774
 775   // If this is a logical left shift of a type smaller than the standard
 776   // integer reg. size, we have to extend the sign-bit into upper bits
 777   // of dest, so we need to put the result of the SLL into a temporary.
 778   //
 779   Value* shiftDest = destVal;
 780   unsigned opSize = target.getTargetData().getTypeSize(argVal1->getType());
 781
 782   if ((shiftOpCode == V9::SLLr5 || shiftOpCode == V9::SLLXr6) && opSize < 8) {
 783     // put SLL result into a temporary
 784     shiftDest = new TmpInstruction(mcfi, argVal1, optArgVal2, "sllTmp");
 785   }
 786
 787   MachineInstr* M = (optArgVal2 != NULL)
 788     ? BuildMI(shiftOpCode, 3).addReg(argVal1).addReg(optArgVal2)
 789                              .addReg(shiftDest, MOTy::Def)
 790     : BuildMI(shiftOpCode, 3).addReg(argVal1).addZImm(optShiftNum)
 791                              .addReg(shiftDest, MOTy::Def);
 792   mvec.push_back(M);
 793
 794   if (shiftDest != destVal) {
 795     // extend the sign-bit of the result into all upper bits of dest
 796     assert(8*opSize <= 32 && "Unexpected type size > 4 and < IntRegSize?");
 797     target.getInstrInfo().
 798       CreateSignExtensionInstructions(target, F, shiftDest, destVal,
 799                                       8*opSize, mvec, mcfi);
 800   }
 801 }
 802
 803
 804 // Does not create any instructions if we cannot exploit constant to
 805 // create a cheaper instruction.
 806 // This returns the approximate cost of the instructions generated,
 807 // which is used to pick the cheapest when both operands are constant.
 808 static unsigned
 809 CreateMulConstInstruction(const TargetMachine &target, Function* F,
 810                           Value* lval, Value* rval, Instruction* destVal,
 811                           std::vector<MachineInstr*>& mvec,
 812                           MachineCodeForInstruction& mcfi)
 813 {
 814   /* Use max. multiply cost, viz., cost of MULX */
 815   unsigned cost = target.getInstrInfo().minLatency(V9::MULXr);
 816   unsigned firstNewInstr = mvec.size();
 817
 818   Value* constOp = rval;
 819   if (! isa<Constant>(constOp))
 820     return cost;
 821
 822   // Cases worth optimizing are:
 823   // (1) Multiply by 0 or 1 for any type: replace with copy (ADD or FMOV)
 824   // (2) Multiply by 2^x for integer types: replace with Shift
 825   //
 826   const Type* resultType = destVal->getType();
 827
 828   if (resultType->isInteger() || isa<PointerType>(resultType)) {
 829     bool isValidConst;
 830     int64_t C = (int64_t) target.getInstrInfo().ConvertConstantToIntType(target,
 831                                      constOp, constOp->getType(), isValidConst);
 832     if (isValidConst) {
 833       unsigned pow;
 834       bool needNeg = false;
 835       if (C < 0) {
 836         needNeg = true;
 837         C = -C;
 838       }
 839
 840       if (C == 0 || C == 1) {
 841         cost = target.getInstrInfo().minLatency(V9::ADDr);
 842         unsigned Zero = target.getRegInfo().getZeroRegNum();
 843         MachineInstr* M;
 844         if (C == 0)
 845           M =BuildMI(V9::ADDr,3).addMReg(Zero).addMReg(Zero).addRegDef(destVal);
 846         else
 847           M = BuildMI(V9::ADDr,3).addReg(lval).addMReg(Zero).addRegDef(destVal);
 848         mvec.push_back(M);
 849       } else if (isPowerOf2(C, pow)) {
 850         unsigned opSize = target.getTargetData().getTypeSize(resultType);
 851         MachineOpCode opCode = (opSize <= 32)? V9::SLLr5 : V9::SLLXr6;
 852         CreateShiftInstructions(target, F, opCode, lval, NULL, pow,
 853                                 destVal, mvec, mcfi);
 854       }
 855
 856       if (mvec.size() > 0 && needNeg) {
 857         // insert <reg = SUB 0, reg> after the instr to flip the sign
 858         MachineInstr* M = CreateIntNegInstruction(target, destVal);
 859         mvec.push_back(M);
 860       }
 861     }
 862   } else {
 863     if (ConstantFP *FPC = dyn_cast<ConstantFP>(constOp)) {
 864       double dval = FPC->getValue();
 865       if (fabs(dval) == 1) {
 866         MachineOpCode opCode =  (dval < 0)
 867           ? (resultType == Type::FloatTy? V9::FNEGS : V9::FNEGD)
 868           : (resultType == Type::FloatTy? V9::FMOVS : V9::FMOVD);
 869         mvec.push_back(BuildMI(opCode,2).addReg(lval).addRegDef(destVal));
 870       }
 871     }
 872   }
 873
 874   if (firstNewInstr < mvec.size()) {
 875     cost = 0;
 876     for (unsigned i=firstNewInstr; i < mvec.size(); ++i)
 877       cost += target.getInstrInfo().minLatency(mvec[i]->getOpcode());
 878   }
 879
 880   return cost;
 881 }
 882
 883
 884 // Does not create any instructions if we cannot exploit constant to
 885 // create a cheaper instruction.
 886 //
 887 static inline void
 888 CreateCheapestMulConstInstruction(const TargetMachine &target,
 889                                   Function* F,
 890                                   Value* lval, Value* rval,
 891                                   Instruction* destVal,
 892                                   std::vector<MachineInstr*>& mvec,
 893                                   MachineCodeForInstruction& mcfi)
 894 {
 895   Value* constOp;
 896   if (isa<Constant>(lval) && isa<Constant>(rval)) {
 897     // both operands are constant: evaluate and "set" in dest
 898     Constant* P = ConstantExpr::get(Instruction::Mul,
 899                                     cast<Constant>(lval),
 900                                     cast<Constant>(rval));
 901     target.getInstrInfo().CreateCodeToLoadConst(target,F,P,destVal,mvec,mcfi);
 902   }
 903   else if (isa<Constant>(rval))         // rval is constant, but not lval
 904     CreateMulConstInstruction(target, F, lval, rval, destVal, mvec, mcfi);
 905   else if (isa<Constant>(lval))         // lval is constant, but not rval
 906     CreateMulConstInstruction(target, F, lval, rval, destVal, mvec, mcfi);
 907
 908   // else neither is constant
 909   return;
 910 }
 911
 912 // Return NULL if we cannot exploit constant to create a cheaper instruction
 913 static inline void
 914 CreateMulInstruction(const TargetMachine &target, Function* F,
 915                      Value* lval, Value* rval, Instruction* destVal,
 916                      std::vector<MachineInstr*>& mvec,
 917                      MachineCodeForInstruction& mcfi,
 918                      MachineOpCode forceMulOp = INVALID_MACHINE_OPCODE)
 919 {
 920   unsigned L = mvec.size();
 921   CreateCheapestMulConstInstruction(target,F, lval, rval, destVal, mvec, mcfi);
 922   if (mvec.size() == L) {
 923     // no instructions were added so create MUL reg, reg, reg.
 924     // Use FSMULD if both operands are actually floats cast to doubles.
 925     // Otherwise, use the default opcode for the appropriate type.
 926     MachineOpCode mulOp = ((forceMulOp != INVALID_MACHINE_OPCODE)
 927                            ? forceMulOp
 928                            : ChooseMulInstructionByType(destVal->getType()));
 929     mvec.push_back(BuildMI(mulOp, 3).addReg(lval).addReg(rval)
 930                    .addRegDef(destVal));
 931   }
 932 }
 933
 934
 935 // Generate a divide instruction for Div or Rem.
 936 // For Rem, this assumes that the operand type will be signed if the result
 937 // type is signed.  This is correct because they must have the same sign.
 938 //
 939 static inline MachineOpCode
 940 ChooseDivInstruction(TargetMachine &target,
 941                      const InstructionNode* instrNode)
 942 {
 943   MachineOpCode opCode = V9::INVALID_OPCODE;
 944
 945   const Type* resultType = instrNode->getInstruction()->getType();
 946
 947   if (resultType->isInteger())
 948     opCode = resultType->isSigned()? V9::SDIVXr : V9::UDIVXr;
 949   else
 950     switch(resultType->getPrimitiveID())
 951       {
 952       case Type::FloatTyID:  opCode = V9::FDIVS; break;
 953       case Type::DoubleTyID: opCode = V9::FDIVD; break;
 954       default: assert(0 && "Invalid type for DIV instruction"); break;
 955       }
 956
 957   return opCode;
 958 }
 959
 960
 961 // Return if we cannot exploit constant to create a cheaper instruction
 962 static void
 963 CreateDivConstInstruction(TargetMachine &target,
 964                           const InstructionNode* instrNode,
 965                           std::vector<MachineInstr*>& mvec)
 966 {
 967   Value* LHS  = instrNode->leftChild()->getValue();
 968   Value* constOp = ((InstrTreeNode*) instrNode->rightChild())->getValue();
 969   if (!isa<Constant>(constOp))
 970     return;
 971
 972   Instruction* destVal = instrNode->getInstruction();
 973   unsigned ZeroReg = target.getRegInfo().getZeroRegNum();
 974
 975   // Cases worth optimizing are:
 976   // (1) Divide by 1 for any type: replace with copy (ADD or FMOV)
 977   // (2) Divide by 2^x for integer types: replace with SR[L or A]{X}
 978   //
 979   const Type* resultType = instrNode->getInstruction()->getType();
 980
 981   if (resultType->isInteger()) {
 982     unsigned pow;
 983     bool isValidConst;
 984     int64_t C = (int64_t) target.getInstrInfo().ConvertConstantToIntType(target,
 985                                      constOp, constOp->getType(), isValidConst);
 986     if (isValidConst) {
 987       bool needNeg = false;
 988       if (C < 0) {
 989         needNeg = true;
 990         C = -C;
 991       }
 992
 993       if (C == 1) {
 994         mvec.push_back(BuildMI(V9::ADDr, 3).addReg(LHS).addMReg(ZeroReg)
 995                        .addRegDef(destVal));
 996       } else if (isPowerOf2(C, pow)) {
 997         unsigned opCode;
 998         Value* shiftOperand;
 999         unsigned opSize = target.getTargetData().getTypeSize(resultType);
1000
1001         if (resultType->isSigned()) {
1002           // For N / 2^k, if the operand N is negative,
1003           // we need to add (2^k - 1) before right-shifting by k, i.e.,
1004           //
1005           //    (N / 2^k) = N >> k,               if N >= 0;
1006           //                (N + 2^k - 1) >> k,   if N < 0
1007           //
1008           // If N is <= 32 bits, use:
1009           //    sra N, 31, t1           // t1 = ~0,         if N < 0,  0 else
1010           //    srl t1, 32-k, t2        // t2 = 2^k - 1,    if N < 0,  0 else
1011           //    add t2, N, t3           // t3 = N + 2^k -1, if N < 0,  N else
1012           //    sra t3, k, result       // result = N / 2^k
1013           //
1014           // If N is 64 bits, use:
1015           //    srax N,  k-1,  t1       // t1 = sign bit in high k positions
1016           //    srlx t1, 64-k, t2       // t2 = 2^k - 1,    if N < 0,  0 else
1017           //    add t2, N, t3           // t3 = N + 2^k -1, if N < 0,  N else
1018           //    sra t3, k, result       // result = N / 2^k
1019           //
1020           TmpInstruction *sraTmp, *srlTmp, *addTmp;
1021           MachineCodeForInstruction& mcfi
1022             = MachineCodeForInstruction::get(destVal);
1023           sraTmp = new TmpInstruction(mcfi, resultType, LHS, 0, "getSign");
1024           srlTmp = new TmpInstruction(mcfi, resultType, LHS, 0, "getPlus2km1");
1025           addTmp = new TmpInstruction(mcfi, resultType, LHS, srlTmp,"incIfNeg");
1026
1027           // Create the SRA or SRAX instruction to get the sign bit
1028           mvec.push_back(BuildMI((opSize > 4)? V9::SRAXi6 : V9::SRAi5, 3)
1029                          .addReg(LHS)
1030                          .addSImm((resultType==Type::LongTy)? pow-1 : 31)
1031                          .addRegDef(sraTmp));
1032
1033           // Create the SRL or SRLX instruction to get the sign bit
1034           mvec.push_back(BuildMI((opSize > 4)? V9::SRLXi6 : V9::SRLi5, 3)
1035                          .addReg(sraTmp)
1036                          .addSImm((resultType==Type::LongTy)? 64-pow : 32-pow)
1037                          .addRegDef(srlTmp));
1038
1039           // Create the ADD instruction to add 2^pow-1 for negative values
1040           mvec.push_back(BuildMI(V9::ADDr, 3).addReg(LHS).addReg(srlTmp)
1041                          .addRegDef(addTmp));
1042
1043           // Get the shift operand and "right-shift" opcode to do the divide
1044           shiftOperand = addTmp;
1045           opCode = (opSize > 4)? V9::SRAXi6 : V9::SRAi5;
1046         } else {
1047           // Get the shift operand and "right-shift" opcode to do the divide
1048           shiftOperand = LHS;
1049           opCode = (opSize > 4)? V9::SRLXi6 : V9::SRLi5;
1050         }
1051
1052         // Now do the actual shift!
1053         mvec.push_back(BuildMI(opCode, 3).addReg(shiftOperand).addZImm(pow)
1054                        .addRegDef(destVal));
1055       }
1056
1057       if (needNeg && (C == 1 || isPowerOf2(C, pow))) {
1058         // insert <reg = SUB 0, reg> after the instr to flip the sign
1059         mvec.push_back(CreateIntNegInstruction(target, destVal));
1060       }
1061     }
1062   } else {
1063     if (ConstantFP *FPC = dyn_cast<ConstantFP>(constOp)) {
1064       double dval = FPC->getValue();
1065       if (fabs(dval) == 1) {
1066         unsigned opCode =
1067           (dval < 0) ? (resultType == Type::FloatTy? V9::FNEGS : V9::FNEGD)
1068           : (resultType == Type::FloatTy? V9::FMOVS : V9::FMOVD);
1069
1070         mvec.push_back(BuildMI(opCode, 2).addReg(LHS).addRegDef(destVal));
1071       }
1072     }
1073   }
1074 }
1075
1076
1077 static void
1078 CreateCodeForVariableSizeAlloca(const TargetMachine& target,
1079                                 Instruction* result,
1080                                 unsigned tsize,
1081                                 Value* numElementsVal,
1082                                 std::vector<MachineInstr*>& getMvec)
1083 {
1084   Value* totalSizeVal;
1085   MachineInstr* M;
1086   MachineCodeForInstruction& mcfi = MachineCodeForInstruction::get(result);
1087   Function *F = result->getParent()->getParent();
1088
1089   // Enforce the alignment constraints on the stack pointer at
1090   // compile time if the total size is a known constant.
1091   if (isa<Constant>(numElementsVal)) {
1092     bool isValid;
1093     int64_t numElem = (int64_t) target.getInstrInfo().
1094       ConvertConstantToIntType(target, numElementsVal,
1095                                numElementsVal->getType(), isValid);
1096     assert(isValid && "Unexpectedly large array dimension in alloca!");
1097     int64_t total = numElem * tsize;
1098     if (int extra= total % target.getFrameInfo().getStackFrameSizeAlignment())
1099       total += target.getFrameInfo().getStackFrameSizeAlignment() - extra;
1100     totalSizeVal = ConstantSInt::get(Type::IntTy, total);
1101   } else {
1102     // The size is not a constant.  Generate code to compute it and
1103     // code to pad the size for stack alignment.
1104     // Create a Value to hold the (constant) element size
1105     Value* tsizeVal = ConstantSInt::get(Type::IntTy, tsize);
1106
1107     // Create temporary values to hold the result of MUL, SLL, SRL
1108     // To pad `size' to next smallest multiple of 16:
1109     //          size = (size + 15) & (-16 = 0xfffffffffffffff0)
1110     //
1111     TmpInstruction* tmpProd = new TmpInstruction(mcfi,numElementsVal, tsizeVal);
1112     TmpInstruction* tmpAdd15= new TmpInstruction(mcfi,numElementsVal, tmpProd);
1113     TmpInstruction* tmpAndf0= new TmpInstruction(mcfi,numElementsVal, tmpAdd15);
1114
1115     // Instruction 1: mul numElements, typeSize -> tmpProd
1116     // This will optimize the MUL as far as possible.
1117     CreateMulInstruction(target, F, numElementsVal, tsizeVal, tmpProd, getMvec,
1118                          mcfi, INVALID_MACHINE_OPCODE);
1119
1120     // Instruction 2: andn tmpProd, 0x0f -> tmpAndn
1121     getMvec.push_back(BuildMI(V9::ADDi, 3).addReg(tmpProd).addSImm(15)
1122                       .addReg(tmpAdd15, MOTy::Def));
1123
1124     // Instruction 3: add tmpAndn, 0x10 -> tmpAdd16
1125     getMvec.push_back(BuildMI(V9::ANDi, 3).addReg(tmpAdd15).addSImm(-16)
1126                       .addReg(tmpAndf0, MOTy::Def));
1127
1128     totalSizeVal = tmpAndf0;
1129   }
1130
1131   // Get the constant offset from SP for dynamically allocated storage
1132   // and create a temporary Value to hold it.
1133   MachineFunction& mcInfo = MachineFunction::get(F);
1134   bool growUp;
1135   ConstantSInt* dynamicAreaOffset =
1136     ConstantSInt::get(Type::IntTy,
1137                      target.getFrameInfo().getDynamicAreaOffset(mcInfo,growUp));
1138   assert(! growUp && "Has SPARC v9 stack frame convention changed?");
1139
1140   unsigned SPReg = target.getRegInfo().getStackPointer();
1141
1142   // Instruction 2: sub %sp, totalSizeVal -> %sp
1143   getMvec.push_back(BuildMI(V9::SUBr, 3).addMReg(SPReg).addReg(totalSizeVal)
1144                     .addMReg(SPReg,MOTy::Def));
1145
1146   // Instruction 3: add %sp, frameSizeBelowDynamicArea -> result
1147   getMvec.push_back(BuildMI(V9::ADDr,3).addMReg(SPReg).addReg(dynamicAreaOffset)
1148                     .addRegDef(result));
1149 }
1150
1151
1152 static void
1153 CreateCodeForFixedSizeAlloca(const TargetMachine& target,
1154                              Instruction* result,
1155                              unsigned tsize,
1156                              unsigned numElements,
1157                              std::vector<MachineInstr*>& getMvec)
1158 {
1159   assert(tsize > 0 && "Illegal (zero) type size for alloca");
1160   assert(result && result->getParent() &&
1161          "Result value is not part of a function?");
1162   Function *F = result->getParent()->getParent();
1163   MachineFunction &mcInfo = MachineFunction::get(F);
1164
1165   // Put the variable in the dynamically sized area of the frame if either:
1166   // (a) The offset is too large to use as an immediate in load/stores
1167   //     (check LDX because all load/stores have the same-size immed. field).
1168   // (b) The object is "large", so it could cause many other locals,
1169   //     spills, and temporaries to have large offsets.
1170   //     NOTE: We use LARGE = 8 * argSlotSize = 64 bytes.
1171   // You've gotta love having only 13 bits for constant offset values :-|.
1172   //
1173   unsigned paddedSize;
1174   int offsetFromFP = mcInfo.getInfo()->computeOffsetforLocalVar(result,
1175                                                                 paddedSize,
1176                                                          tsize * numElements);
1177
1178   if (((int)paddedSize) > 8 * target.getFrameInfo().getSizeOfEachArgOnStack() ||
1179       ! target.getInstrInfo().constantFitsInImmedField(V9::LDXi,offsetFromFP)) {
1180     CreateCodeForVariableSizeAlloca(target, result, tsize,
1181                                     ConstantSInt::get(Type::IntTy,numElements),
1182                                     getMvec);
1183     return;
1184   }
1185
1186   // else offset fits in immediate field so go ahead and allocate it.
1187   offsetFromFP = mcInfo.getInfo()->allocateLocalVar(result, tsize *numElements);
1188
1189   // Create a temporary Value to hold the constant offset.
1190   // This is needed because it may not fit in the immediate field.
1191   ConstantSInt* offsetVal = ConstantSInt::get(Type::IntTy, offsetFromFP);
1192
1193   // Instruction 1: add %fp, offsetFromFP -> result
1194   unsigned FPReg = target.getRegInfo().getFramePointer();
1195   getMvec.push_back(BuildMI(V9::ADDr, 3).addMReg(FPReg).addReg(offsetVal)
1196                     .addRegDef(result));
1197 }
1198
1199
1200 //------------------------------------------------------------------------
1201 // Function SetOperandsForMemInstr
1202 //
1203 // Choose addressing mode for the given load or store instruction.
1204 // Use [reg+reg] if it is an indexed reference, and the index offset is
1205 //               not a constant or if it cannot fit in the offset field.
1206 // Use [reg+offset] in all other cases.
1207 //
1208 // This assumes that all array refs are "lowered" to one of these forms:
1209 //      %x = load (subarray*) ptr, constant     ; single constant offset
1210 //      %x = load (subarray*) ptr, offsetVal    ; single non-constant offset
1211 // Generally, this should happen via strength reduction + LICM.
1212 // Also, strength reduction should take care of using the same register for
1213 // the loop index variable and an array index, when that is profitable.
1214 //------------------------------------------------------------------------
1215
1216 static void
1217 SetOperandsForMemInstr(unsigned Opcode,
1218                        std::vector<MachineInstr*>& mvec,
1219                        InstructionNode* vmInstrNode,
1220                        const TargetMachine& target)
1221 {
1222   Instruction* memInst = vmInstrNode->getInstruction();
1223   // Index vector, ptr value, and flag if all indices are const.
1224   std::vector<Value*> idxVec;
1225   bool allConstantIndices;
1226   Value* ptrVal = GetMemInstArgs(vmInstrNode, idxVec, allConstantIndices);
1227
1228   // Now create the appropriate operands for the machine instruction.
1229   // First, initialize so we default to storing the offset in a register.
1230   int64_t smallConstOffset = 0;
1231   Value* valueForRegOffset = NULL;
1232   MachineOperand::MachineOperandType offsetOpType =
1233     MachineOperand::MO_VirtualRegister;
1234
1235   // Check if there is an index vector and if so, compute the
1236   // right offset for structures and for arrays
1237   //
1238   if (!idxVec.empty()) {
1239     const PointerType* ptrType = cast<PointerType>(ptrVal->getType());
1240
1241     // If all indices are constant, compute the combined offset directly.
1242     if (allConstantIndices) {
1243       // Compute the offset value using the index vector. Create a
1244       // virtual reg. for it since it may not fit in the immed field.
1245       uint64_t offset = target.getTargetData().getIndexedOffset(ptrType,idxVec);
1246       valueForRegOffset = ConstantSInt::get(Type::LongTy, offset);
1247     } else {
1248       // There is at least one non-constant offset.  Therefore, this must
1249       // be an array ref, and must have been lowered to a single non-zero
1250       // offset.  (An extra leading zero offset, if any, can be ignored.)
1251       // Generate code sequence to compute address from index.
1252       //
1253       bool firstIdxIsZero = IsZero(idxVec[0]);
1254       assert(idxVec.size() == 1U + firstIdxIsZero
1255              && "Array refs must be lowered before Instruction Selection");
1256
1257       Value* idxVal = idxVec[firstIdxIsZero];
1258
1259       std::vector<MachineInstr*> mulVec;
1260       Instruction* addr =
1261         new TmpInstruction(MachineCodeForInstruction::get(memInst),
1262                            Type::ULongTy, memInst);
1263
1264       // Get the array type indexed by idxVal, and compute its element size.
1265       // The call to getTypeSize() will fail if size is not constant.
1266       const Type* vecType = (firstIdxIsZero
1267                              ? GetElementPtrInst::getIndexedType(ptrType,
1268                                            std::vector<Value*>(1U, idxVec[0]),
1269                                            /*AllowCompositeLeaf*/ true)
1270                                  : ptrType);
1271       const Type* eltType = cast<SequentialType>(vecType)->getElementType();
1272       ConstantUInt* eltSizeVal = ConstantUInt::get(Type::ULongTy,
1273                                    target.getTargetData().getTypeSize(eltType));
1274
1275       // CreateMulInstruction() folds constants intelligently enough.
1276       CreateMulInstruction(target, memInst->getParent()->getParent(),
1277                            idxVal,         /* lval, not likely to be const*/
1278                            eltSizeVal,     /* rval, likely to be constant */
1279                            addr,           /* result */
1280                            mulVec, MachineCodeForInstruction::get(memInst),
1281                            INVALID_MACHINE_OPCODE);
1282
1283       assert(mulVec.size() > 0 && "No multiply code created?");
1284       mvec.insert(mvec.end(), mulVec.begin(), mulVec.end());
1285
1286       valueForRegOffset = addr;
1287     }
1288   } else {
1289     offsetOpType = MachineOperand::MO_SignExtendedImmed;
1290     smallConstOffset = 0;
1291   }
1292
1293   // For STORE:
1294   //   Operand 0 is value, operand 1 is ptr, operand 2 is offset
1295   // For LOAD or GET_ELEMENT_PTR,
1296   //   Operand 0 is ptr, operand 1 is offset, operand 2 is result.
1297   //
1298   unsigned offsetOpNum, ptrOpNum;
1299   MachineInstr *MI;
1300   if (memInst->getOpcode() == Instruction::Store) {
1301     if (offsetOpType == MachineOperand::MO_VirtualRegister) {
1302       MI = BuildMI(Opcode, 3).addReg(vmInstrNode->leftChild()->getValue())
1303                              .addReg(ptrVal).addReg(valueForRegOffset);
1304     } else {
1305       Opcode = convertOpcodeFromRegToImm(Opcode);
1306       MI = BuildMI(Opcode, 3).addReg(vmInstrNode->leftChild()->getValue())
1307                              .addReg(ptrVal).addSImm(smallConstOffset);
1308     }
1309   } else {
1310     if (offsetOpType == MachineOperand::MO_VirtualRegister) {
1311       MI = BuildMI(Opcode, 3).addReg(ptrVal).addReg(valueForRegOffset)
1312                              .addRegDef(memInst);
1313     } else {
1314       Opcode = convertOpcodeFromRegToImm(Opcode);
1315       MI = BuildMI(Opcode, 3).addReg(ptrVal).addSImm(smallConstOffset)
1316                              .addRegDef(memInst);
1317     }
1318   }
1319   mvec.push_back(MI);
1320 }
1321
1322
1323 //
1324 // Substitute operand `operandNum' of the instruction in node `treeNode'
1325 // in place of the use(s) of that instruction in node `parent'.
1326 // Check both explicit and implicit operands!
1327 // Also make sure to skip over a parent who:
1328 // (1) is a list node in the Burg tree, or
1329 // (2) itself had its results forwarded to its parent
1330 //
1331 static void
1332 ForwardOperand(InstructionNode* treeNode,
1333                InstrTreeNode*   parent,
1334                int operandNum)
1335 {
1336   assert(treeNode && parent && "Invalid invocation of ForwardOperand");
1337
1338   Instruction* unusedOp = treeNode->getInstruction();
1339   Value* fwdOp = unusedOp->getOperand(operandNum);
1340
1341   // The parent itself may be a list node, so find the real parent instruction
1342   while (parent->getNodeType() != InstrTreeNode::NTInstructionNode)
1343     {
1344       parent = parent->parent();
1345       assert(parent && "ERROR: Non-instruction node has no parent in tree.");
1346     }
1347   InstructionNode* parentInstrNode = (InstructionNode*) parent;
1348
1349   Instruction* userInstr = parentInstrNode->getInstruction();
1350   MachineCodeForInstruction &mvec = MachineCodeForInstruction::get(userInstr);
1351
1352   // The parent's mvec would be empty if it was itself forwarded.
1353   // Recursively call ForwardOperand in that case...
1354   //
1355   if (mvec.size() == 0) {
1356     assert(parent->parent() != NULL &&
1357            "Parent could not have been forwarded, yet has no instructions?");
1358     ForwardOperand(treeNode, parent->parent(), operandNum);
1359   } else {
1360     for (unsigned i=0, N=mvec.size(); i < N; i++) {
1361       MachineInstr* minstr = mvec[i];
1362       for (unsigned i=0, numOps=minstr->getNumOperands(); i < numOps; ++i) {
1363         const MachineOperand& mop = minstr->getOperand(i);
1364         if (mop.getType() == MachineOperand::MO_VirtualRegister &&
1365             mop.getVRegValue() == unusedOp)
1366         {
1367           minstr->SetMachineOperandVal(i, MachineOperand::MO_VirtualRegister,
1368                                        fwdOp);
1369         }
1370       }
1371
1372       for (unsigned i=0,numOps=minstr->getNumImplicitRefs(); i<numOps; ++i)
1373         if (minstr->getImplicitRef(i) == unusedOp)
1374           minstr->setImplicitRef(i, fwdOp);
1375     }
1376   }
1377 }
1378
1379
1380 inline bool
1381 AllUsesAreBranches(const Instruction* setccI)
1382 {
1383   for (Value::use_const_iterator UI=setccI->use_begin(), UE=setccI->use_end();
1384        UI != UE; ++UI)
1385     if (! isa<TmpInstruction>(*UI)     // ignore tmp instructions here
1386         && cast<Instruction>(*UI)->getOpcode() != Instruction::Br)
1387       return false;
1388   return true;
1389 }
1390
1391 // Generate code for any intrinsic that needs a special code sequence
1392 // instead of a regular call.  If not that kind of intrinsic, do nothing.
1393 // Returns true if code was generated, otherwise false.
1394 //
1395 static bool CodeGenIntrinsic(Intrinsic::ID iid, CallInst &callInstr,
1396                              TargetMachine &target,
1397                              std::vector<MachineInstr*>& mvec) {
1398   switch (iid) {
1399   default:
1400     assert(0 && "Unknown intrinsic function call should have been lowered!");
1401   case Intrinsic::va_start: {
1402     // Get the address of the first incoming vararg argument on the stack
1403     bool ignore;
1404     Function* func = cast<Function>(callInstr.getParent()->getParent());
1405     int numFixedArgs   = func->getFunctionType()->getNumParams();
1406     int fpReg          = target.getFrameInfo().getIncomingArgBaseRegNum();
1407     int argSize        = target.getFrameInfo().getSizeOfEachArgOnStack();
1408     int firstVarArgOff = numFixedArgs * argSize + target.getFrameInfo().
1409       getFirstIncomingArgOffset(MachineFunction::get(func), ignore);
1410     mvec.push_back(BuildMI(V9::ADDi, 3).addMReg(fpReg).addSImm(firstVarArgOff).
1411                    addRegDef(&callInstr));
1412     return true;
1413   }
1414
1415   case Intrinsic::va_end:
1416     return true;                        // no-op on Sparc
1417
1418   case Intrinsic::va_copy:
1419     // Simple copy of current va_list (arg1) to new va_list (result)
1420     mvec.push_back(BuildMI(V9::ORr, 3).
1421                    addMReg(target.getRegInfo().getZeroRegNum()).
1422                    addReg(callInstr.getOperand(1)).
1423                    addRegDef(&callInstr));
1424     return true;
1425   }
1426 }
1427
1428 //******************* Externally Visible Functions *************************/
1429
1430 //------------------------------------------------------------------------
1431 // External Function: ThisIsAChainRule
1432 //
1433 // Purpose:
1434 //   Check if a given BURG rule is a chain rule.
1435 //------------------------------------------------------------------------
1436
1437 extern bool
1438 ThisIsAChainRule(int eruleno)
1439 {
1440   switch(eruleno)
1441     {
1442     case 111:   // stmt:  reg
1443     case 123:
1444     case 124:
1445     case 125:
1446     case 126:
1447     case 127:
1448     case 128:
1449     case 129:
1450     case 130:
1451     case 131:
1452     case 132:
1453     case 133:
1454     case 155:
1455     case 221:
1456     case 222:
1457     case 241:
1458     case 242:
1459     case 243:
1460     case 244:
1461     case 245:
1462     case 321:
1463       return true; break;
1464
1465     default:
1466       return false; break;
1467     }
1468 }
1469
1470
1471 //------------------------------------------------------------------------
1472 // External Function: GetInstructionsByRule
1473 //
1474 // Purpose:
1475 //   Choose machine instructions for the SPARC according to the
1476 //   patterns chosen by the BURG-generated parser.
1477 //------------------------------------------------------------------------
1478
1479 void
1480 GetInstructionsByRule(InstructionNode* subtreeRoot,
1481                       int ruleForNode,
1482                       short* nts,
1483                       TargetMachine &target,
1484                       std::vector<MachineInstr*>& mvec)
1485 {
1486   bool checkCast = false;               // initialize here to use fall-through
1487   bool maskUnsignedResult = false;
1488   int nextRule;
1489   int forwardOperandNum = -1;
1490   unsigned allocaSize = 0;
1491   MachineInstr* M, *M2;
1492   unsigned L;
1493   bool foldCase = false;
1494
1495   mvec.clear();
1496
1497   // If the code for this instruction was folded into the parent (user),
1498   // then do nothing!
1499   if (subtreeRoot->isFoldedIntoParent())
1500     return;
1501
1502   //
1503   // Let's check for chain rules outside the switch so that we don't have
1504   // to duplicate the list of chain rule production numbers here again
1505   //
1506   if (ThisIsAChainRule(ruleForNode)) {
1507     // Chain rules have a single nonterminal on the RHS.
1508     // Get the rule that matches the RHS non-terminal and use that instead.
1509     //
1510     assert(nts[0] && ! nts[1]
1511            && "A chain rule should have only one RHS non-terminal!");
1512     nextRule = burm_rule(subtreeRoot->state, nts[0]);
1513     nts = burm_nts[nextRule];
1514     GetInstructionsByRule(subtreeRoot, nextRule, nts, target, mvec);
1515   } else {
1516     switch(ruleForNode) {
1517       case 1:   // stmt:   Ret
1518       case 2:   // stmt:   RetValue(reg)
1519       {         // NOTE: Prepass of register allocation is responsible
1520                 //       for moving return value to appropriate register.
1521                 // Copy the return value to the required return register.
1522                 // Mark the return Value as an implicit ref of the RET instr..
1523                 // Mark the return-address register as a hidden virtual reg.
1524                 // Finally put a NOP in the delay slot.
1525         ReturnInst *returnInstr=cast<ReturnInst>(subtreeRoot->getInstruction());
1526         Value* retVal = returnInstr->getReturnValue();
1527         MachineCodeForInstruction& mcfi =
1528           MachineCodeForInstruction::get(returnInstr);
1529
1530         // Create a hidden virtual reg to represent the return address register
1531         // used by the machine instruction but not represented in LLVM.
1532         //
1533         Instruction* returnAddrTmp = new TmpInstruction(mcfi, returnInstr);
1534
1535         MachineInstr* retMI =
1536           BuildMI(V9::JMPLRETi, 3).addReg(returnAddrTmp).addSImm(8)
1537           .addMReg(target.getRegInfo().getZeroRegNum(), MOTy::Def);
1538
1539         // If there is a value to return, we need to:
1540         // (a) Sign-extend the value if it is smaller than 8 bytes (reg size)
1541         // (b) Insert a copy to copy the return value to the appropriate reg.
1542         //     -- For FP values, create a FMOVS or FMOVD instruction
1543         //     -- For non-FP values, create an add-with-0 instruction
1544         //
1545         if (retVal != NULL) {
1546           const SparcRegInfo& regInfo =
1547             (SparcRegInfo&) target.getRegInfo();
1548           const Type* retType = retVal->getType();
1549           unsigned regClassID = regInfo.getRegClassIDOfType(retType);
1550           unsigned retRegNum = (retType->isFloatingPoint()
1551                                 ? (unsigned) SparcFloatRegClass::f0
1552                                 : (unsigned) SparcIntRegClass::i0);
1553           retRegNum = regInfo.getUnifiedRegNum(regClassID, retRegNum);
1554
1555           // () Insert sign-extension instructions for small signed values.
1556           //
1557           Value* retValToUse = retVal;
1558           if (retType->isIntegral() && retType->isSigned()) {
1559             unsigned retSize = target.getTargetData().getTypeSize(retType);
1560             if (retSize <= 4) {
1561               // create a temporary virtual reg. to hold the sign-extension
1562               retValToUse = new TmpInstruction(mcfi, retVal);
1563
1564               // sign-extend retVal and put the result in the temporary reg.
1565               target.getInstrInfo().CreateSignExtensionInstructions
1566                 (target, returnInstr->getParent()->getParent(),
1567                  retVal, retValToUse, 8*retSize, mvec, mcfi);
1568             }
1569           }
1570
1571           // (b) Now, insert a copy to to the appropriate register:
1572           //     -- For FP values, create a FMOVS or FMOVD instruction
1573           //     -- For non-FP values, create an add-with-0 instruction
1574           //
1575           // First, create a virtual register to represent the register and
1576           // mark this vreg as being an implicit operand of the ret MI.
1577           TmpInstruction* retVReg =
1578             new TmpInstruction(mcfi, retValToUse, NULL, "argReg");
1579
1580           retMI->addImplicitRef(retVReg);
1581
1582           if (retType->isFloatingPoint())
1583             M = (BuildMI(retType==Type::FloatTy? V9::FMOVS : V9::FMOVD, 2)
1584                  .addReg(retValToUse).addReg(retVReg, MOTy::Def));
1585           else
1586             M = (BuildMI(ChooseAddInstructionByType(retType), 3)
1587                  .addReg(retValToUse).addSImm((int64_t) 0)
1588                  .addReg(retVReg, MOTy::Def));
1589
1590           // Mark the operand with the register it should be assigned
1591           M->SetRegForOperand(M->getNumOperands()-1, retRegNum);
1592           retMI->SetRegForImplicitRef(retMI->getNumImplicitRefs()-1, retRegNum);
1593
1594           mvec.push_back(M);
1595         }
1596
1597         // Now insert the RET instruction and a NOP for the delay slot
1598         mvec.push_back(retMI);
1599         mvec.push_back(BuildMI(V9::NOP, 0));
1600
1601         break;
1602       }
1603
1604       case 3:   // stmt:   Store(reg,reg)
1605       case 4:   // stmt:   Store(reg,ptrreg)
1606         SetOperandsForMemInstr(ChooseStoreInstruction(
1607                         subtreeRoot->leftChild()->getValue()->getType()),
1608                                mvec, subtreeRoot, target);
1609         break;
1610
1611       case 5:   // stmt:   BrUncond
1612         {
1613           BranchInst *BI = cast<BranchInst>(subtreeRoot->getInstruction());
1614           mvec.push_back(BuildMI(V9::BA, 1).addPCDisp(BI->getSuccessor(0)));
1615
1616           // delay slot
1617           mvec.push_back(BuildMI(V9::NOP, 0));
1618           break;
1619         }
1620
1621       case 206: // stmt:   BrCond(setCCconst)
1622       { // setCCconst => boolean was computed with `%b = setCC type reg1 const'
1623         // If the constant is ZERO, we can use the branch-on-integer-register
1624         // instructions and avoid the SUBcc instruction entirely.
1625         // Otherwise this is just the same as case 5, so just fall through.
1626         //
1627         InstrTreeNode* constNode = subtreeRoot->leftChild()->rightChild();
1628         assert(constNode &&
1629                constNode->getNodeType() ==InstrTreeNode::NTConstNode);
1630         Constant *constVal = cast<Constant>(constNode->getValue());
1631         bool isValidConst;
1632
1633         if ((constVal->getType()->isInteger()
1634              || isa<PointerType>(constVal->getType()))
1635             && target.getInstrInfo().ConvertConstantToIntType(target,
1636                              constVal, constVal->getType(), isValidConst) == 0
1637             && isValidConst)
1638           {
1639             // That constant is a zero after all...
1640             // Use the left child of setCC as the first argument!
1641             // Mark the setCC node so that no code is generated for it.
1642             InstructionNode* setCCNode = (InstructionNode*)
1643                                          subtreeRoot->leftChild();
1644             assert(setCCNode->getOpLabel() == SetCCOp);
1645             setCCNode->markFoldedIntoParent();
1646
1647             BranchInst* brInst=cast<BranchInst>(subtreeRoot->getInstruction());
1648
1649             M = BuildMI(ChooseBprInstruction(subtreeRoot), 2)
1650                                 .addReg(setCCNode->leftChild()->getValue())
1651                                 .addPCDisp(brInst->getSuccessor(0));
1652             mvec.push_back(M);
1653
1654             // delay slot
1655             mvec.push_back(BuildMI(V9::NOP, 0));
1656
1657             // false branch
1658             mvec.push_back(BuildMI(V9::BA, 1)
1659                            .addPCDisp(brInst->getSuccessor(1)));
1660
1661             // delay slot
1662             mvec.push_back(BuildMI(V9::NOP, 0));
1663             break;
1664           }
1665         // ELSE FALL THROUGH
1666       }
1667
1668       case 6:   // stmt:   BrCond(setCC)
1669       { // bool => boolean was computed with SetCC.
1670         // The branch to use depends on whether it is FP, signed, or unsigned.
1671         // If it is an integer CC, we also need to find the unique
1672         // TmpInstruction representing that CC.
1673         //
1674         BranchInst* brInst = cast<BranchInst>(subtreeRoot->getInstruction());
1675         const Type* setCCType;
1676         unsigned Opcode = ChooseBccInstruction(subtreeRoot, setCCType);
1677         Value* ccValue = GetTmpForCC(subtreeRoot->leftChild()->getValue(),
1678                                      brInst->getParent()->getParent(),
1679                                      setCCType,
1680                                      MachineCodeForInstruction::get(brInst));
1681         M = BuildMI(Opcode, 2).addCCReg(ccValue)
1682                               .addPCDisp(brInst->getSuccessor(0));
1683         mvec.push_back(M);
1684
1685         // delay slot
1686         mvec.push_back(BuildMI(V9::NOP, 0));
1687
1688         // false branch
1689         mvec.push_back(BuildMI(V9::BA, 1).addPCDisp(brInst->getSuccessor(1)));
1690
1691         // delay slot
1692         mvec.push_back(BuildMI(V9::NOP, 0));
1693         break;
1694       }
1695
1696       case 208: // stmt:   BrCond(boolconst)
1697       {
1698         // boolconst => boolean is a constant; use BA to first or second label
1699         Constant* constVal =
1700           cast<Constant>(subtreeRoot->leftChild()->getValue());
1701         unsigned dest = cast<ConstantBool>(constVal)->getValue()? 0 : 1;
1702
1703         M = BuildMI(V9::BA, 1).addPCDisp(
1704           cast<BranchInst>(subtreeRoot->getInstruction())->getSuccessor(dest));
1705         mvec.push_back(M);
1706
1707         // delay slot
1708         mvec.push_back(BuildMI(V9::NOP, 0));
1709         break;
1710       }
1711
1712       case   8: // stmt:   BrCond(boolreg)
1713       { // boolreg   => boolean is recorded in an integer register.
1714         //              Use branch-on-integer-register instruction.
1715         //
1716         BranchInst *BI = cast<BranchInst>(subtreeRoot->getInstruction());
1717         M = BuildMI(V9::BRNZ, 2).addReg(subtreeRoot->leftChild()->getValue())
1718           .addPCDisp(BI->getSuccessor(0));
1719         mvec.push_back(M);
1720
1721         // delay slot
1722         mvec.push_back(BuildMI(V9::NOP, 0));
1723
1724         // false branch
1725         mvec.push_back(BuildMI(V9::BA, 1).addPCDisp(BI->getSuccessor(1)));
1726
1727         // delay slot
1728         mvec.push_back(BuildMI(V9::NOP, 0));
1729         break;
1730       }
1731
1732       case 9:   // stmt:   Switch(reg)
1733         assert(0 && "*** SWITCH instruction is not implemented yet.");
1734         break;
1735
1736       case 10:  // reg:   VRegList(reg, reg)
1737         assert(0 && "VRegList should never be the topmost non-chain rule");
1738         break;
1739
1740       case 21:  // bool:  Not(bool,reg): Compute with a conditional-move-on-reg
1741       { // First find the unary operand. It may be left or right, usually right.
1742         Instruction* notI = subtreeRoot->getInstruction();
1743         Value* notArg = BinaryOperator::getNotArgument(
1744                            cast<BinaryOperator>(subtreeRoot->getInstruction()));
1745         unsigned ZeroReg = target.getRegInfo().getZeroRegNum();
1746
1747         // Unconditionally set register to 0
1748         mvec.push_back(BuildMI(V9::SETHI, 2).addZImm(0).addRegDef(notI));
1749
1750         // Now conditionally move 1 into the register.
1751         // Mark the register as a use (as well as a def) because the old
1752         // value will be retained if the condition is false.
1753         mvec.push_back(BuildMI(V9::MOVRZi, 3).addReg(notArg).addZImm(1)
1754                        .addReg(notI, MOTy::UseAndDef));
1755
1756         break;
1757       }
1758
1759       case 421: // reg:   BNot(reg,reg): Compute as reg = reg XOR-NOT 0
1760       { // First find the unary operand. It may be left or right, usually right.
1761         Value* notArg = BinaryOperator::getNotArgument(
1762                            cast<BinaryOperator>(subtreeRoot->getInstruction()));
1763         unsigned ZeroReg = target.getRegInfo().getZeroRegNum();
1764         mvec.push_back(BuildMI(V9::XNORr, 3).addReg(notArg).addMReg(ZeroReg)
1765                                        .addRegDef(subtreeRoot->getValue()));
1766         break;
1767       }
1768
1769       case 322: // reg:   Not(tobool, reg):
1770         // Fold CAST-TO-BOOL with NOT by inverting the sense of cast-to-bool
1771         foldCase = true;
1772         // Just fall through!
1773
1774       case 22:  // reg:   ToBoolTy(reg):
1775       {
1776         Instruction* castI = subtreeRoot->getInstruction();
1777         Value* opVal = subtreeRoot->leftChild()->getValue();
1778         assert(opVal->getType()->isIntegral() ||
1779                isa<PointerType>(opVal->getType()));
1780
1781         // Unconditionally set register to 0
1782         mvec.push_back(BuildMI(V9::SETHI, 2).addZImm(0).addRegDef(castI));
1783
1784         // Now conditionally move 1 into the register.
1785         // Mark the register as a use (as well as a def) because the old
1786         // value will be retained if the condition is false.
1787         MachineOpCode opCode = foldCase? V9::MOVRZi : V9::MOVRNZi;
1788         mvec.push_back(BuildMI(opCode, 3).addReg(opVal).addZImm(1)
1789                        .addReg(castI, MOTy::UseAndDef));
1790
1791         break;
1792       }
1793
1794       case 23:  // reg:   ToUByteTy(reg)
1795       case 24:  // reg:   ToSByteTy(reg)
1796       case 25:  // reg:   ToUShortTy(reg)
1797       case 26:  // reg:   ToShortTy(reg)
1798       case 27:  // reg:   ToUIntTy(reg)
1799       case 28:  // reg:   ToIntTy(reg)
1800       case 29:  // reg:   ToULongTy(reg)
1801       case 30:  // reg:   ToLongTy(reg)
1802       {
1803         //======================================================================
1804         // Rules for integer conversions:
1805         //
1806         //--------
1807         // From ISO 1998 C++ Standard, Sec. 4.7:
1808         //
1809         // 2. If the destination type is unsigned, the resulting value is
1810         // the least unsigned integer congruent to the source integer
1811         // (modulo 2n where n is the number of bits used to represent the
1812         // unsigned type). [Note: In a two s complement representation,
1813         // this conversion is conceptual and there is no change in the
1814         // bit pattern (if there is no truncation). ]
1815         //
1816         // 3. If the destination type is signed, the value is unchanged if
1817         // it can be represented in the destination type (and bitfield width);
1818         // otherwise, the value is implementation-defined.
1819         //--------
1820         //
1821         // Since we assume 2s complement representations, this implies:
1822         //
1823         // -- If operand is smaller than destination, zero-extend or sign-extend
1824         //    according to the signedness of the *operand*: source decides:
1825         //    (1) If operand is signed, sign-extend it.
1826         //        If dest is unsigned, zero-ext the result!
1827         //    (2) If operand is unsigned, our current invariant is that
1828         //        it's high bits are correct, so zero-extension is not needed.
1829         //
1830         // -- If operand is same size as or larger than destination,
1831         //    zero-extend or sign-extend according to the signedness of
1832         //    the *destination*: destination decides:
1833         //    (1) If destination is signed, sign-extend (truncating if needed)
1834         //        This choice is implementation defined.  We sign-extend the
1835         //        operand, which matches both Sun's cc and gcc3.2.
1836         //    (2) If destination is unsigned, zero-extend (truncating if needed)
1837         //======================================================================
1838
1839         Instruction* destI =  subtreeRoot->getInstruction();
1840         Function* currentFunc = destI->getParent()->getParent();
1841         MachineCodeForInstruction& mcfi=MachineCodeForInstruction::get(destI);
1842
1843         Value* opVal = subtreeRoot->leftChild()->getValue();
1844         const Type* opType = opVal->getType();
1845         const Type* destType = destI->getType();
1846         unsigned opSize   = target.getTargetData().getTypeSize(opType);
1847         unsigned destSize = target.getTargetData().getTypeSize(destType);
1848
1849         bool isIntegral = opType->isIntegral() || isa<PointerType>(opType);
1850
1851         if (opType == Type::BoolTy ||
1852             opType == destType ||
1853             isIntegral && opSize == destSize && opSize == 8) {
1854           // nothing to do in all these cases
1855           forwardOperandNum = 0;          // forward first operand to user
1856
1857         } else if (opType->isFloatingPoint()) {
1858
1859           CreateCodeToConvertFloatToInt(target, opVal, destI, mvec, mcfi);
1860           if (destI->getType()->isUnsigned() && destI->getType() !=Type::UIntTy)
1861             maskUnsignedResult = true; // not handled by fp->int code
1862
1863         } else if (isIntegral) {
1864
1865           bool opSigned     = opType->isSigned();
1866           bool destSigned   = destType->isSigned();
1867           unsigned extSourceInBits = 8 * std::min<unsigned>(opSize, destSize);
1868
1869           assert(! (opSize == destSize && opSigned == destSigned) &&
1870                  "How can different int types have same size and signedness?");
1871
1872           bool signExtend = (opSize <  destSize && opSigned ||
1873                              opSize >= destSize && destSigned);
1874
1875           bool signAndZeroExtend = (opSize < destSize && destSize < 8u &&
1876                                     opSigned && !destSigned);
1877           assert(!signAndZeroExtend || signExtend);
1878
1879           bool zeroExtendOnly = opSize >= destSize && !destSigned;
1880           assert(!zeroExtendOnly || !signExtend);
1881
1882           if (signExtend) {
1883             Value* signExtDest = (signAndZeroExtend
1884                                   ? new TmpInstruction(mcfi, destType, opVal)
1885                                   : destI);
1886
1887             target.getInstrInfo().CreateSignExtensionInstructions
1888               (target, currentFunc,opVal,signExtDest,extSourceInBits,mvec,mcfi);
1889
1890             if (signAndZeroExtend)
1891               target.getInstrInfo().CreateZeroExtensionInstructions
1892               (target, currentFunc, signExtDest, destI, 8*destSize, mvec, mcfi);
1893           }
1894           else if (zeroExtendOnly) {
1895             target.getInstrInfo().CreateZeroExtensionInstructions
1896               (target, currentFunc, opVal, destI, extSourceInBits, mvec, mcfi);
1897           }
1898           else
1899             forwardOperandNum = 0;          // forward first operand to user
1900
1901         } else
1902           assert(0 && "Unrecognized operand type for convert-to-integer");
1903
1904         break;
1905       }
1906
1907       case  31: // reg:   ToFloatTy(reg):
1908       case  32: // reg:   ToDoubleTy(reg):
1909       case 232: // reg:   ToDoubleTy(Constant):
1910
1911         // If this instruction has a parent (a user) in the tree
1912         // and the user is translated as an FsMULd instruction,
1913         // then the cast is unnecessary.  So check that first.
1914         // In the future, we'll want to do the same for the FdMULq instruction,
1915         // so do the check here instead of only for ToFloatTy(reg).
1916         //
1917         if (subtreeRoot->parent() != NULL) {
1918           const MachineCodeForInstruction& mcfi =
1919             MachineCodeForInstruction::get(
1920                 cast<InstructionNode>(subtreeRoot->parent())->getInstruction());
1921           if (mcfi.size() == 0 || mcfi.front()->getOpcode() == V9::FSMULD)
1922             forwardOperandNum = 0;    // forward first operand to user
1923         }
1924
1925         if (forwardOperandNum != 0) {    // we do need the cast
1926           Value* leftVal = subtreeRoot->leftChild()->getValue();
1927           const Type* opType = leftVal->getType();
1928           MachineOpCode opCode=ChooseConvertToFloatInstr(target,
1929                                        subtreeRoot->getOpLabel(), opType);
1930           if (opCode == V9::NOP) {      // no conversion needed
1931             forwardOperandNum = 0;      // forward first operand to user
1932           } else {
1933             // If the source operand is a non-FP type it must be
1934             // first copied from int to float register via memory!
1935             Instruction *dest = subtreeRoot->getInstruction();
1936             Value* srcForCast;
1937             int n = 0;
1938             if (! opType->isFloatingPoint()) {
1939               // Create a temporary to represent the FP register
1940               // into which the integer will be copied via memory.
1941               // The type of this temporary will determine the FP
1942               // register used: single-prec for a 32-bit int or smaller,
1943               // double-prec for a 64-bit int.
1944               //
1945               uint64_t srcSize =
1946                 target.getTargetData().getTypeSize(leftVal->getType());
1947               Type* tmpTypeToUse =
1948                 (srcSize <= 4)? Type::FloatTy : Type::DoubleTy;
1949               MachineCodeForInstruction &destMCFI =
1950                 MachineCodeForInstruction::get(dest);
1951               srcForCast = new TmpInstruction(destMCFI, tmpTypeToUse, dest);
1952
1953               target.getInstrInfo().CreateCodeToCopyIntToFloat(target,
1954                          dest->getParent()->getParent(),
1955                          leftVal, cast<Instruction>(srcForCast),
1956                          mvec, destMCFI);
1957             } else
1958               srcForCast = leftVal;
1959
1960             M = BuildMI(opCode, 2).addReg(srcForCast).addRegDef(dest);
1961             mvec.push_back(M);
1962           }
1963         }
1964         break;
1965
1966       case 19:  // reg:   ToArrayTy(reg):
1967       case 20:  // reg:   ToPointerTy(reg):
1968         forwardOperandNum = 0;          // forward first operand to user
1969         break;
1970
1971       case 233: // reg:   Add(reg, Constant)
1972         maskUnsignedResult = true;
1973         M = CreateAddConstInstruction(subtreeRoot);
1974         if (M != NULL) {
1975           mvec.push_back(M);
1976           break;
1977         }
1978         // ELSE FALL THROUGH
1979
1980       case 33:  // reg:   Add(reg, reg)
1981         maskUnsignedResult = true;
1982         Add3OperandInstr(ChooseAddInstruction(subtreeRoot), subtreeRoot, mvec);
1983         break;
1984
1985       case 234: // reg:   Sub(reg, Constant)
1986         maskUnsignedResult = true;
1987         M = CreateSubConstInstruction(subtreeRoot);
1988         if (M != NULL) {
1989           mvec.push_back(M);
1990           break;
1991         }
1992         // ELSE FALL THROUGH
1993
1994       case 34:  // reg:   Sub(reg, reg)
1995         maskUnsignedResult = true;
1996         Add3OperandInstr(ChooseSubInstructionByType(
1997                                    subtreeRoot->getInstruction()->getType()),
1998                          subtreeRoot, mvec);
1999         break;
2000
2001       case 135: // reg:   Mul(todouble, todouble)
2002         checkCast = true;
2003         // FALL THROUGH
2004
2005       case 35:  // reg:   Mul(reg, reg)
2006       {
2007         maskUnsignedResult = true;
2008         MachineOpCode forceOp = ((checkCast && BothFloatToDouble(subtreeRoot))
2009                                  ? V9::FSMULD
2010                                  : INVALID_MACHINE_OPCODE);
2011         Instruction* mulInstr = subtreeRoot->getInstruction();
2012         CreateMulInstruction(target, mulInstr->getParent()->getParent(),
2013                              subtreeRoot->leftChild()->getValue(),
2014                              subtreeRoot->rightChild()->getValue(),
2015                              mulInstr, mvec,
2016                              MachineCodeForInstruction::get(mulInstr),forceOp);
2017         break;
2018       }
2019       case 335: // reg:   Mul(todouble, todoubleConst)
2020         checkCast = true;
2021         // FALL THROUGH
2022
2023       case 235: // reg:   Mul(reg, Constant)
2024       {
2025         maskUnsignedResult = true;
2026         MachineOpCode forceOp = ((checkCast && BothFloatToDouble(subtreeRoot))
2027                                  ? V9::FSMULD
2028                                  : INVALID_MACHINE_OPCODE);
2029         Instruction* mulInstr = subtreeRoot->getInstruction();
2030         CreateMulInstruction(target, mulInstr->getParent()->getParent(),
2031                              subtreeRoot->leftChild()->getValue(),
2032                              subtreeRoot->rightChild()->getValue(),
2033                              mulInstr, mvec,
2034                              MachineCodeForInstruction::get(mulInstr),
2035                              forceOp);
2036         break;
2037       }
2038       case 236: // reg:   Div(reg, Constant)
2039         maskUnsignedResult = true;
2040         L = mvec.size();
2041         CreateDivConstInstruction(target, subtreeRoot, mvec);
2042         if (mvec.size() > L)
2043           break;
2044         // ELSE FALL THROUGH
2045
2046       case 36:  // reg:   Div(reg, reg)
2047       {
2048         maskUnsignedResult = true;
2049
2050         // If either operand of divide is smaller than 64 bits, we have
2051         // to make sure the unused top bits are correct because they affect
2052         // the result.  These bits are already correct for unsigned values.
2053         // They may be incorrect for signed values, so sign extend to fill in.
2054         Instruction* divI = subtreeRoot->getInstruction();
2055         Value* divOp1 = subtreeRoot->leftChild()->getValue();
2056         Value* divOp2 = subtreeRoot->rightChild()->getValue();
2057         Value* divOp1ToUse = divOp1;
2058         Value* divOp2ToUse = divOp2;
2059         if (divI->getType()->isSigned()) {
2060           unsigned opSize=target.getTargetData().getTypeSize(divI->getType());
2061           if (opSize < 8) {
2062             MachineCodeForInstruction& mcfi=MachineCodeForInstruction::get(divI);
2063             divOp1ToUse = new TmpInstruction(mcfi, divOp1);
2064             divOp2ToUse = new TmpInstruction(mcfi, divOp2);
2065             target.getInstrInfo().
2066               CreateSignExtensionInstructions(target,
2067                                               divI->getParent()->getParent(),
2068                                               divOp1, divOp1ToUse,
2069                                               8*opSize, mvec, mcfi);
2070             target.getInstrInfo().
2071               CreateSignExtensionInstructions(target,
2072                                               divI->getParent()->getParent(),
2073                                               divOp2, divOp2ToUse,
2074                                               8*opSize, mvec, mcfi);
2075           }
2076         }
2077
2078         mvec.push_back(BuildMI(ChooseDivInstruction(target, subtreeRoot), 3)
2079                        .addReg(divOp1ToUse)
2080                        .addReg(divOp2ToUse)
2081                        .addRegDef(divI));
2082
2083         break;
2084       }
2085
2086       case  37: // reg:   Rem(reg, reg)
2087       case 237: // reg:   Rem(reg, Constant)
2088       {
2089         maskUnsignedResult = true;
2090
2091         Instruction* remI   = subtreeRoot->getInstruction();
2092         Value* divOp1 = subtreeRoot->leftChild()->getValue();
2093         Value* divOp2 = subtreeRoot->rightChild()->getValue();
2094
2095         MachineCodeForInstruction& mcfi = MachineCodeForInstruction::get(remI);
2096
2097         // If second operand of divide is smaller than 64 bits, we have
2098         // to make sure the unused top bits are correct because they affect
2099         // the result.  These bits are already correct for unsigned values.
2100         // They may be incorrect for signed values, so sign extend to fill in.
2101         //
2102         Value* divOpToUse = divOp2;
2103         if (divOp2->getType()->isSigned()) {
2104           unsigned opSize=target.getTargetData().getTypeSize(divOp2->getType());
2105           if (opSize < 8) {
2106             divOpToUse = new TmpInstruction(mcfi, divOp2);
2107             target.getInstrInfo().
2108               CreateSignExtensionInstructions(target,
2109                                               remI->getParent()->getParent(),
2110                                               divOp2, divOpToUse,
2111                                               8*opSize, mvec, mcfi);
2112           }
2113         }
2114
2115         // Now compute: result = rem V1, V2 as:
2116         //      result = V1 - (V1 / signExtend(V2)) * signExtend(V2)
2117         //
2118         TmpInstruction* quot = new TmpInstruction(mcfi, divOp1, divOpToUse);
2119         TmpInstruction* prod = new TmpInstruction(mcfi, quot, divOpToUse);
2120
2121         mvec.push_back(BuildMI(ChooseDivInstruction(target, subtreeRoot), 3)
2122                        .addReg(divOp1).addReg(divOpToUse).addRegDef(quot));
2123
2124         mvec.push_back(BuildMI(ChooseMulInstructionByType(remI->getType()), 3)
2125                        .addReg(quot).addReg(divOpToUse).addRegDef(prod));
2126
2127         mvec.push_back(BuildMI(ChooseSubInstructionByType(remI->getType()), 3)
2128                        .addReg(divOp1).addReg(prod).addRegDef(remI));
2129
2130         break;
2131       }
2132
2133       case  38: // bool:   And(bool, bool)
2134       case 138: // bool:   And(bool, not)
2135       case 238: // bool:   And(bool, boolconst)
2136       case 338: // reg :   BAnd(reg, reg)
2137       case 538: // reg :   BAnd(reg, Constant)
2138         Add3OperandInstr(V9::ANDr, subtreeRoot, mvec);
2139         break;
2140
2141       case 438: // bool:   BAnd(bool, bnot)
2142       { // Use the argument of NOT as the second argument!
2143         // Mark the NOT node so that no code is generated for it.
2144         // If the type is boolean, set 1 or 0 in the result register.
2145         InstructionNode* notNode = (InstructionNode*) subtreeRoot->rightChild();
2146         Value* notArg = BinaryOperator::getNotArgument(
2147                            cast<BinaryOperator>(notNode->getInstruction()));
2148         notNode->markFoldedIntoParent();
2149         Value *lhs = subtreeRoot->leftChild()->getValue();
2150         Value *dest = subtreeRoot->getValue();
2151         mvec.push_back(BuildMI(V9::ANDNr, 3).addReg(lhs).addReg(notArg)
2152                                        .addReg(dest, MOTy::Def));
2153
2154         if (notArg->getType() == Type::BoolTy) {
2155           // set 1 in result register if result of above is non-zero
2156           mvec.push_back(BuildMI(V9::MOVRNZi, 3).addReg(dest).addZImm(1)
2157                          .addReg(dest, MOTy::UseAndDef));
2158         }
2159
2160         break;
2161       }
2162
2163       case  39: // bool:   Or(bool, bool)
2164       case 139: // bool:   Or(bool, not)
2165       case 239: // bool:   Or(bool, boolconst)
2166       case 339: // reg :   BOr(reg, reg)
2167       case 539: // reg :   BOr(reg, Constant)
2168         Add3OperandInstr(V9::ORr, subtreeRoot, mvec);
2169         break;
2170
2171       case 439: // bool:   BOr(bool, bnot)
2172       { // Use the argument of NOT as the second argument!
2173         // Mark the NOT node so that no code is generated for it.
2174         // If the type is boolean, set 1 or 0 in the result register.
2175         InstructionNode* notNode = (InstructionNode*) subtreeRoot->rightChild();
2176         Value* notArg = BinaryOperator::getNotArgument(
2177                            cast<BinaryOperator>(notNode->getInstruction()));
2178         notNode->markFoldedIntoParent();
2179         Value *lhs = subtreeRoot->leftChild()->getValue();
2180         Value *dest = subtreeRoot->getValue();
2181
2182         mvec.push_back(BuildMI(V9::ORNr, 3).addReg(lhs).addReg(notArg)
2183                        .addReg(dest, MOTy::Def));
2184
2185         if (notArg->getType() == Type::BoolTy) {
2186           // set 1 in result register if result of above is non-zero
2187           mvec.push_back(BuildMI(V9::MOVRNZi, 3).addReg(dest).addZImm(1)
2188                          .addReg(dest, MOTy::UseAndDef));
2189         }
2190
2191         break;
2192       }
2193
2194       case  40: // bool:   Xor(bool, bool)
2195       case 140: // bool:   Xor(bool, not)
2196       case 240: // bool:   Xor(bool, boolconst)
2197       case 340: // reg :   BXor(reg, reg)
2198       case 540: // reg :   BXor(reg, Constant)
2199         Add3OperandInstr(V9::XORr, subtreeRoot, mvec);
2200         break;
2201
2202       case 440: // bool:   BXor(bool, bnot)
2203       { // Use the argument of NOT as the second argument!
2204         // Mark the NOT node so that no code is generated for it.
2205         // If the type is boolean, set 1 or 0 in the result register.
2206         InstructionNode* notNode = (InstructionNode*) subtreeRoot->rightChild();
2207         Value* notArg = BinaryOperator::getNotArgument(
2208                            cast<BinaryOperator>(notNode->getInstruction()));
2209         notNode->markFoldedIntoParent();
2210         Value *lhs = subtreeRoot->leftChild()->getValue();
2211         Value *dest = subtreeRoot->getValue();
2212         mvec.push_back(BuildMI(V9::XNORr, 3).addReg(lhs).addReg(notArg)
2213                        .addReg(dest, MOTy::Def));
2214
2215         if (notArg->getType() == Type::BoolTy) {
2216           // set 1 in result register if result of above is non-zero
2217           mvec.push_back(BuildMI(V9::MOVRNZi, 3).addReg(dest).addZImm(1)
2218                          .addReg(dest, MOTy::UseAndDef));
2219         }
2220         break;
2221       }
2222
2223       case 41:  // setCCconst:   SetCC(reg, Constant)
2224       { // Comparison is with a constant:
2225         //
2226         // If the bool result must be computed into a register (see below),
2227         // and the constant is int ZERO, we can use the MOVR[op] instructions
2228         // and avoid the SUBcc instruction entirely.
2229         // Otherwise this is just the same as case 42, so just fall through.
2230         //
2231         // The result of the SetCC must be computed and stored in a register if
2232         // it is used outside the current basic block (so it must be computed
2233         // as a boolreg) or it is used by anything other than a branch.
2234         // We will use a conditional move to do this.
2235         //
2236         Instruction* setCCInstr = subtreeRoot->getInstruction();
2237         bool computeBoolVal = (subtreeRoot->parent() == NULL ||
2238                                ! AllUsesAreBranches(setCCInstr));
2239
2240         if (computeBoolVal) {
2241           InstrTreeNode* constNode = subtreeRoot->rightChild();
2242           assert(constNode &&
2243                  constNode->getNodeType() ==InstrTreeNode::NTConstNode);
2244           Constant *constVal = cast<Constant>(constNode->getValue());
2245           bool isValidConst;
2246
2247           if ((constVal->getType()->isInteger()
2248                || isa<PointerType>(constVal->getType()))
2249               && target.getInstrInfo().ConvertConstantToIntType(target,
2250                              constVal, constVal->getType(), isValidConst) == 0
2251               && isValidConst)
2252           {
2253             // That constant is an integer zero after all...
2254             // Use a MOVR[op] to compute the boolean result
2255             // Unconditionally set register to 0
2256             mvec.push_back(BuildMI(V9::SETHI, 2).addZImm(0)
2257                            .addRegDef(setCCInstr));
2258
2259             // Now conditionally move 1 into the register.
2260             // Mark the register as a use (as well as a def) because the old
2261             // value will be retained if the condition is false.
2262             MachineOpCode movOpCode = ChooseMovpregiForSetCC(subtreeRoot);
2263             mvec.push_back(BuildMI(movOpCode, 3)
2264                            .addReg(subtreeRoot->leftChild()->getValue())
2265                            .addZImm(1).addReg(setCCInstr, MOTy::UseAndDef));
2266
2267             break;
2268           }
2269         }
2270         // ELSE FALL THROUGH
2271       }
2272
2273       case 42:  // bool:   SetCC(reg, reg):
2274       {
2275         // This generates a SUBCC instruction, putting the difference in a
2276         // result reg. if needed, and/or setting a condition code if needed.
2277         //
2278         Instruction* setCCInstr = subtreeRoot->getInstruction();
2279         Value* leftVal  = subtreeRoot->leftChild()->getValue();
2280         Value* rightVal = subtreeRoot->rightChild()->getValue();
2281         const Type* opType = leftVal->getType();
2282         bool isFPCompare = opType->isFloatingPoint();
2283
2284         // If the boolean result of the SetCC is used outside the current basic
2285         // block (so it must be computed as a boolreg) or is used by anything
2286         // other than a branch, the boolean must be computed and stored
2287         // in a result register.  We will use a conditional move to do this.
2288         //
2289         bool computeBoolVal = (subtreeRoot->parent() == NULL ||
2290                                ! AllUsesAreBranches(setCCInstr));
2291
2292         // A TmpInstruction is created to represent the CC "result".
2293         // Unlike other instances of TmpInstruction, this one is used
2294         // by machine code of multiple LLVM instructions, viz.,
2295         // the SetCC and the branch.  Make sure to get the same one!
2296         // Note that we do this even for FP CC registers even though they
2297         // are explicit operands, because the type of the operand
2298         // needs to be a floating point condition code, not an integer
2299         // condition code.  Think of this as casting the bool result to
2300         // a FP condition code register.
2301         // Later, we mark the 4th operand as being a CC register, and as a def.
2302         //
2303         TmpInstruction* tmpForCC = GetTmpForCC(setCCInstr,
2304                                     setCCInstr->getParent()->getParent(),
2305                                     leftVal->getType(),
2306                                     MachineCodeForInstruction::get(setCCInstr));
2307
2308         // If the operands are signed values smaller than 4 bytes, then they
2309         // must be sign-extended in order to do a valid 32-bit comparison
2310         // and get the right result in the 32-bit CC register (%icc).
2311         //
2312         Value* leftOpToUse  = leftVal;
2313         Value* rightOpToUse = rightVal;
2314         if (opType->isIntegral() && opType->isSigned()) {
2315           unsigned opSize = target.getTargetData().getTypeSize(opType);
2316           if (opSize < 4) {
2317             MachineCodeForInstruction& mcfi =
2318               MachineCodeForInstruction::get(setCCInstr);
2319
2320             // create temporary virtual regs. to hold the sign-extensions
2321             leftOpToUse  = new TmpInstruction(mcfi, leftVal);
2322             rightOpToUse = new TmpInstruction(mcfi, rightVal);
2323
2324             // sign-extend each operand and put the result in the temporary reg.
2325             target.getInstrInfo().CreateSignExtensionInstructions
2326               (target, setCCInstr->getParent()->getParent(),
2327                leftVal, leftOpToUse, 8*opSize, mvec, mcfi);
2328             target.getInstrInfo().CreateSignExtensionInstructions
2329               (target, setCCInstr->getParent()->getParent(),
2330                rightVal, rightOpToUse, 8*opSize, mvec, mcfi);
2331           }
2332         }
2333
2334         if (! isFPCompare) {
2335           // Integer condition: set CC and discard result.
2336           mvec.push_back(BuildMI(V9::SUBccr, 4)
2337                          .addReg(leftOpToUse)
2338                          .addReg(rightOpToUse)
2339                          .addMReg(target.getRegInfo().getZeroRegNum(),MOTy::Def)
2340                          .addCCReg(tmpForCC, MOTy::Def));
2341         } else {
2342           // FP condition: dest of FCMP should be some FCCn register
2343           mvec.push_back(BuildMI(ChooseFcmpInstruction(subtreeRoot), 3)
2344                          .addCCReg(tmpForCC, MOTy::Def)
2345                          .addReg(leftOpToUse)
2346                          .addReg(rightOpToUse));
2347         }
2348
2349         if (computeBoolVal) {
2350           MachineOpCode movOpCode = (isFPCompare
2351                                      ? ChooseMovFpcciInstruction(subtreeRoot)
2352                                      : ChooseMovpcciForSetCC(subtreeRoot));
2353
2354           // Unconditionally set register to 0
2355           M = BuildMI(V9::SETHI, 2).addZImm(0).addRegDef(setCCInstr);
2356           mvec.push_back(M);
2357
2358           // Now conditionally move 1 into the register.
2359           // Mark the register as a use (as well as a def) because the old
2360           // value will be retained if the condition is false.
2361           M = (BuildMI(movOpCode, 3).addCCReg(tmpForCC).addZImm(1)
2362                .addReg(setCCInstr, MOTy::UseAndDef));
2363           mvec.push_back(M);
2364         }
2365         break;
2366       }
2367
2368       case 51:  // reg:   Load(reg)
2369       case 52:  // reg:   Load(ptrreg)
2370         SetOperandsForMemInstr(ChooseLoadInstruction(
2371                                    subtreeRoot->getValue()->getType()),
2372                                mvec, subtreeRoot, target);
2373         break;
2374
2375       case 55:  // reg:   GetElemPtr(reg)
2376       case 56:  // reg:   GetElemPtrIdx(reg,reg)
2377         // If the GetElemPtr was folded into the user (parent), it will be
2378         // caught above.  For other cases, we have to compute the address.
2379         SetOperandsForMemInstr(V9::ADDr, mvec, subtreeRoot, target);
2380         break;
2381
2382       case 57:  // reg:  Alloca: Implement as 1 instruction:
2383       {         //          add %fp, offsetFromFP -> result
2384         AllocationInst* instr =
2385           cast<AllocationInst>(subtreeRoot->getInstruction());
2386         unsigned tsize =
2387           target.getTargetData().getTypeSize(instr->getAllocatedType());
2388         assert(tsize != 0);
2389         CreateCodeForFixedSizeAlloca(target, instr, tsize, 1, mvec);
2390         break;
2391       }
2392
2393       case 58:  // reg:   Alloca(reg): Implement as 3 instructions:
2394                 //      mul num, typeSz -> tmp
2395                 //      sub %sp, tmp    -> %sp
2396       {         //      add %sp, frameSizeBelowDynamicArea -> result
2397         AllocationInst* instr =
2398           cast<AllocationInst>(subtreeRoot->getInstruction());
2399         const Type* eltType = instr->getAllocatedType();
2400
2401         // If #elements is constant, use simpler code for fixed-size allocas
2402         int tsize = (int) target.getTargetData().getTypeSize(eltType);
2403         Value* numElementsVal = NULL;
2404         bool isArray = instr->isArrayAllocation();
2405
2406         if (!isArray || isa<Constant>(numElementsVal = instr->getArraySize())) {
2407           // total size is constant: generate code for fixed-size alloca
2408           unsigned numElements = isArray?
2409             cast<ConstantUInt>(numElementsVal)->getValue() : 1;
2410           CreateCodeForFixedSizeAlloca(target, instr, tsize,
2411                                        numElements, mvec);
2412         } else {
2413           // total size is not constant.
2414           CreateCodeForVariableSizeAlloca(target, instr, tsize,
2415                                           numElementsVal, mvec);
2416         }
2417         break;
2418       }
2419
2420       case 61:  // reg:   Call
2421       {         // Generate a direct (CALL) or indirect (JMPL) call.
2422                 // Mark the return-address register, the indirection
2423                 // register (for indirect calls), the operands of the Call,
2424                 // and the return value (if any) as implicit operands
2425                 // of the machine instruction.
2426                 //
2427                 // If this is a varargs function, floating point arguments
2428                 // have to passed in integer registers so insert
2429                 // copy-float-to-int instructions for each float operand.
2430                 //
2431         CallInst *callInstr = cast<CallInst>(subtreeRoot->getInstruction());
2432         Value *callee = callInstr->getCalledValue();
2433         Function* calledFunc = dyn_cast<Function>(callee);
2434
2435         // Check if this is an intrinsic function that needs a special code
2436         // sequence (e.g., va_start).  Indirect calls cannot be special.
2437         //
2438         bool specialIntrinsic = false;
2439         Intrinsic::ID iid;
2440         if (calledFunc && (iid=(Intrinsic::ID)calledFunc->getIntrinsicID()))
2441           specialIntrinsic = CodeGenIntrinsic(iid, *callInstr, target, mvec);
2442
2443         // If not, generate the normal call sequence for the function.
2444         // This can also handle any intrinsics that are just function calls.
2445         //
2446         if (! specialIntrinsic) {
2447           Function* currentFunc = callInstr->getParent()->getParent();
2448           MachineFunction& MF = MachineFunction::get(currentFunc);
2449           MachineCodeForInstruction& mcfi =
2450             MachineCodeForInstruction::get(callInstr);
2451           const SparcRegInfo& regInfo =
2452             (SparcRegInfo&) target.getRegInfo();
2453           const TargetFrameInfo& frameInfo = target.getFrameInfo();
2454
2455           // Create hidden virtual register for return address with type void*
2456           TmpInstruction* retAddrReg =
2457             new TmpInstruction(mcfi, PointerType::get(Type::VoidTy), callInstr);
2458
2459           // Generate the machine instruction and its operands.
2460           // Use CALL for direct function calls; this optimistically assumes
2461           // the PC-relative address fits in the CALL address field (22 bits).
2462           // Use JMPL for indirect calls.
2463           // This will be added to mvec later, after operand copies.
2464           //
2465           MachineInstr* callMI;
2466           if (calledFunc)             // direct function call
2467             callMI = BuildMI(V9::CALL, 1).addPCDisp(callee);
2468           else                        // indirect function call
2469             callMI = (BuildMI(V9::JMPLCALLi,3).addReg(callee)
2470                       .addSImm((int64_t)0).addRegDef(retAddrReg));
2471
2472           const FunctionType* funcType =
2473             cast<FunctionType>(cast<PointerType>(callee->getType())
2474                                ->getElementType());
2475           bool isVarArgs = funcType->isVarArg();
2476           bool noPrototype = isVarArgs && funcType->getNumParams() == 0;
2477
2478           // Use a descriptor to pass information about call arguments
2479           // to the register allocator.  This descriptor will be "owned"
2480           // and freed automatically when the MachineCodeForInstruction
2481           // object for the callInstr goes away.
2482           CallArgsDescriptor* argDesc =
2483             new CallArgsDescriptor(callInstr, retAddrReg,isVarArgs,noPrototype);
2484           assert(callInstr->getOperand(0) == callee
2485                  && "This is assumed in the loop below!");
2486
2487           // Insert sign-extension instructions for small signed values,
2488           // if this is an unknown function (i.e., called via a funcptr)
2489           // or an external one (i.e., which may not be compiled by llc).
2490           //
2491           if (calledFunc == NULL || calledFunc->isExternal()) {
2492             for (unsigned i=1, N=callInstr->getNumOperands(); i < N; ++i) {
2493               Value* argVal = callInstr->getOperand(i);
2494               const Type* argType = argVal->getType();
2495               if (argType->isIntegral() && argType->isSigned()) {
2496                 unsigned argSize = target.getTargetData().getTypeSize(argType);
2497                 if (argSize <= 4) {
2498                   // create a temporary virtual reg. to hold the sign-extension
2499                   TmpInstruction* argExtend = new TmpInstruction(mcfi, argVal);
2500
2501                   // sign-extend argVal and put the result in the temporary reg.
2502                   target.getInstrInfo().CreateSignExtensionInstructions
2503                     (target, currentFunc, argVal, argExtend,
2504                      8*argSize, mvec, mcfi);
2505
2506                   // replace argVal with argExtend in CallArgsDescriptor
2507                   argDesc->getArgInfo(i-1).replaceArgVal(argExtend);
2508                 }
2509               }
2510             }
2511           }
2512
2513           // Insert copy instructions to get all the arguments into
2514           // all the places that they need to be.
2515           //
2516           for (unsigned i=1, N=callInstr->getNumOperands(); i < N; ++i) {
2517             int argNo = i-1;
2518             CallArgInfo& argInfo = argDesc->getArgInfo(argNo);
2519             Value* argVal = argInfo.getArgVal(); // don't use callInstr arg here
2520             const Type* argType = argVal->getType();
2521             unsigned regType = regInfo.getRegTypeForDataType(argType);
2522             unsigned argSize = target.getTargetData().getTypeSize(argType);
2523             int regNumForArg = TargetRegInfo::getInvalidRegNum();
2524             unsigned regClassIDOfArgReg;
2525
2526             // Check for FP arguments to varargs functions.
2527             // Any such argument in the first $K$ args must be passed in an
2528             // integer register.  If there is no prototype, it must also
2529             // be passed as an FP register.
2530             // K = #integer argument registers.
2531             bool isFPArg = argVal->getType()->isFloatingPoint();
2532             if (isVarArgs && isFPArg) {
2533
2534               if (noPrototype) {
2535                 // It is a function with no prototype: pass value
2536                 // as an FP value as well as a varargs value.  The FP value
2537                 // may go in a register or on the stack.  The copy instruction
2538                 // to the outgoing reg/stack is created by the normal argument
2539                 // handling code since this is the "normal" passing mode.
2540                 //
2541                 regNumForArg = regInfo.regNumForFPArg(regType,
2542                                                       false, false, argNo,
2543                                                       regClassIDOfArgReg);
2544                 if (regNumForArg == regInfo.getInvalidRegNum())
2545                   argInfo.setUseStackSlot();
2546                 else
2547                   argInfo.setUseFPArgReg();
2548               }
2549
2550               // If this arg. is in the first $K$ regs, add special copy-
2551               // float-to-int instructions to pass the value as an int.
2552               // To check if it is in the first $K$, get the register
2553               // number for the arg #i.  These copy instructions are
2554               // generated here because they are extra cases and not needed
2555               // for the normal argument handling (some code reuse is
2556               // possible though -- later).
2557               //
2558               int copyRegNum = regInfo.regNumForIntArg(false, false, argNo,
2559                                                        regClassIDOfArgReg);
2560               if (copyRegNum != regInfo.getInvalidRegNum()) {
2561                 // Create a virtual register to represent copyReg. Mark
2562                 // this vreg as being an implicit operand of the call MI
2563                 const Type* loadTy = (argType == Type::FloatTy
2564                                       ? Type::IntTy : Type::LongTy);
2565                 TmpInstruction* argVReg = new TmpInstruction(mcfi, loadTy,
2566                                                              argVal, NULL,
2567                                                              "argRegCopy");
2568                 callMI->addImplicitRef(argVReg);
2569
2570                 // Get a temp stack location to use to copy
2571                 // float-to-int via the stack.
2572                 //
2573                 // FIXME: For now, we allocate permanent space because
2574                 // the stack frame manager does not allow locals to be
2575                 // allocated (e.g., for alloca) after a temp is
2576                 // allocated!
2577                 //
2578                 // int tmpOffset = MF.getInfo()->pushTempValue(argSize);
2579                 int tmpOffset = MF.getInfo()->allocateLocalVar(argVReg);
2580
2581                 // Generate the store from FP reg to stack
2582                 unsigned StoreOpcode = ChooseStoreInstruction(argType);
2583                 M = BuildMI(convertOpcodeFromRegToImm(StoreOpcode), 3)
2584                   .addReg(argVal).addMReg(regInfo.getFramePointer())
2585                   .addSImm(tmpOffset);
2586                 mvec.push_back(M);
2587
2588                 // Generate the load from stack to int arg reg
2589                 unsigned LoadOpcode = ChooseLoadInstruction(loadTy);
2590                 M = BuildMI(convertOpcodeFromRegToImm(LoadOpcode), 3)
2591                   .addMReg(regInfo.getFramePointer()).addSImm(tmpOffset)
2592                   .addReg(argVReg, MOTy::Def);
2593
2594                 // Mark operand with register it should be assigned
2595                 // both for copy and for the callMI
2596                 M->SetRegForOperand(M->getNumOperands()-1, copyRegNum);
2597                 callMI->SetRegForImplicitRef(callMI->getNumImplicitRefs()-1,
2598                                              copyRegNum);
2599                 mvec.push_back(M);
2600
2601                 // Add info about the argument to the CallArgsDescriptor
2602                 argInfo.setUseIntArgReg();
2603                 argInfo.setArgCopy(copyRegNum);
2604               } else {
2605                 // Cannot fit in first $K$ regs so pass arg on stack
2606                 argInfo.setUseStackSlot();
2607               }
2608             } else if (isFPArg) {
2609               // Get the outgoing arg reg to see if there is one.
2610               regNumForArg = regInfo.regNumForFPArg(regType, false, false,
2611                                                     argNo, regClassIDOfArgReg);
2612               if (regNumForArg == regInfo.getInvalidRegNum())
2613                 argInfo.setUseStackSlot();
2614               else {
2615                 argInfo.setUseFPArgReg();
2616                 regNumForArg =regInfo.getUnifiedRegNum(regClassIDOfArgReg,
2617                                                        regNumForArg);
2618               }
2619             } else {
2620               // Get the outgoing arg reg to see if there is one.
2621               regNumForArg = regInfo.regNumForIntArg(false,false,
2622                                                      argNo, regClassIDOfArgReg);
2623               if (regNumForArg == regInfo.getInvalidRegNum())
2624                 argInfo.setUseStackSlot();
2625               else {
2626                 argInfo.setUseIntArgReg();
2627                 regNumForArg =regInfo.getUnifiedRegNum(regClassIDOfArgReg,
2628                                                        regNumForArg);
2629               }
2630             }
2631
2632             //
2633             // Now insert copy instructions to stack slot or arg. register
2634             //
2635             if (argInfo.usesStackSlot()) {
2636               // Get the stack offset for this argument slot.
2637               // FP args on stack are right justified so adjust offset!
2638               // int arguments are also right justified but they are
2639               // always loaded as a full double-word so the offset does
2640               // not need to be adjusted.
2641               int argOffset = frameInfo.getOutgoingArgOffset(MF, argNo);
2642               if (argType->isFloatingPoint()) {
2643                 unsigned slotSize = frameInfo.getSizeOfEachArgOnStack();
2644                 assert(argSize <= slotSize && "Insufficient slot size!");
2645                 argOffset += slotSize - argSize;
2646               }
2647
2648               // Now generate instruction to copy argument to stack
2649               MachineOpCode storeOpCode =
2650                 (argType->isFloatingPoint()
2651                  ? ((argSize == 4)? V9::STFi : V9::STDFi) : V9::STXi);
2652
2653               M = BuildMI(storeOpCode, 3).addReg(argVal)
2654                 .addMReg(regInfo.getStackPointer()).addSImm(argOffset);
2655               mvec.push_back(M);
2656             }
2657             else if (regNumForArg != regInfo.getInvalidRegNum()) {
2658
2659               // Create a virtual register to represent the arg reg. Mark
2660               // this vreg as being an implicit operand of the call MI.
2661               TmpInstruction* argVReg =
2662                 new TmpInstruction(mcfi, argVal, NULL, "argReg");
2663
2664               callMI->addImplicitRef(argVReg);
2665
2666               // Generate the reg-to-reg copy into the outgoing arg reg.
2667               // -- For FP values, create a FMOVS or FMOVD instruction
2668               // -- For non-FP values, create an add-with-0 instruction
2669               if (argType->isFloatingPoint())
2670                 M=(BuildMI(argType==Type::FloatTy? V9::FMOVS :V9::FMOVD,2)
2671                    .addReg(argVal).addReg(argVReg, MOTy::Def));
2672               else
2673                 M = (BuildMI(ChooseAddInstructionByType(argType), 3)
2674                      .addReg(argVal).addSImm((int64_t) 0)
2675                      .addReg(argVReg, MOTy::Def));
2676
2677               // Mark the operand with the register it should be assigned
2678               M->SetRegForOperand(M->getNumOperands()-1, regNumForArg);
2679               callMI->SetRegForImplicitRef(callMI->getNumImplicitRefs()-1,
2680                                            regNumForArg);
2681
2682               mvec.push_back(M);
2683             }
2684             else
2685               assert(argInfo.getArgCopy() != regInfo.getInvalidRegNum() &&
2686                      "Arg. not in stack slot, primary or secondary register?");
2687           }
2688
2689           // add call instruction and delay slot before copying return value
2690           mvec.push_back(callMI);
2691           mvec.push_back(BuildMI(V9::NOP, 0));
2692
2693           // Add the return value as an implicit ref.  The call operands
2694           // were added above.  Also, add code to copy out the return value.
2695           // This is always register-to-register for int or FP return values.
2696           //
2697           if (callInstr->getType() != Type::VoidTy) {
2698             // Get the return value reg.
2699             const Type* retType = callInstr->getType();
2700
2701             int regNum = (retType->isFloatingPoint()
2702                           ? (unsigned) SparcFloatRegClass::f0
2703                           : (unsigned) SparcIntRegClass::o0);
2704             unsigned regClassID = regInfo.getRegClassIDOfType(retType);
2705             regNum = regInfo.getUnifiedRegNum(regClassID, regNum);
2706
2707             // Create a virtual register to represent it and mark
2708             // this vreg as being an implicit operand of the call MI
2709             TmpInstruction* retVReg =
2710               new TmpInstruction(mcfi, callInstr, NULL, "argReg");
2711
2712             callMI->addImplicitRef(retVReg, /*isDef*/ true);
2713
2714             // Generate the reg-to-reg copy from the return value reg.
2715             // -- For FP values, create a FMOVS or FMOVD instruction
2716             // -- For non-FP values, create an add-with-0 instruction
2717             if (retType->isFloatingPoint())
2718               M = (BuildMI(retType==Type::FloatTy? V9::FMOVS : V9::FMOVD, 2)
2719                    .addReg(retVReg).addReg(callInstr, MOTy::Def));
2720             else
2721               M = (BuildMI(ChooseAddInstructionByType(retType), 3)
2722                    .addReg(retVReg).addSImm((int64_t) 0)
2723                    .addReg(callInstr, MOTy::Def));
2724
2725             // Mark the operand with the register it should be assigned
2726             // Also mark the implicit ref of the call defining this operand
2727             M->SetRegForOperand(0, regNum);
2728             callMI->SetRegForImplicitRef(callMI->getNumImplicitRefs()-1,regNum);
2729
2730             mvec.push_back(M);
2731           }
2732
2733           // For the CALL instruction, the ret. addr. reg. is also implicit
2734           if (isa<Function>(callee))
2735             callMI->addImplicitRef(retAddrReg, /*isDef*/ true);
2736
2737           MF.getInfo()->popAllTempValues();  // free temps used for this inst
2738         }
2739
2740         break;
2741       }
2742
2743       case 62:  // reg:   Shl(reg, reg)
2744       {
2745         Value* argVal1 = subtreeRoot->leftChild()->getValue();
2746         Value* argVal2 = subtreeRoot->rightChild()->getValue();
2747         Instruction* shlInstr = subtreeRoot->getInstruction();
2748
2749         const Type* opType = argVal1->getType();
2750         assert((opType->isInteger() || isa<PointerType>(opType)) &&
2751                "Shl unsupported for other types");
2752         unsigned opSize = target.getTargetData().getTypeSize(opType);
2753
2754         CreateShiftInstructions(target, shlInstr->getParent()->getParent(),
2755                                 (opSize > 4)? V9::SLLXr6:V9::SLLr5,
2756                                 argVal1, argVal2, 0, shlInstr, mvec,
2757                                 MachineCodeForInstruction::get(shlInstr));
2758         break;
2759       }
2760
2761       case 63:  // reg:   Shr(reg, reg)
2762       {
2763         const Type* opType = subtreeRoot->leftChild()->getValue()->getType();
2764         assert((opType->isInteger() || isa<PointerType>(opType)) &&
2765                "Shr unsupported for other types");
2766         unsigned opSize = target.getTargetData().getTypeSize(opType);
2767         Add3OperandInstr(opType->isSigned()
2768                          ? (opSize > 4? V9::SRAXr6 : V9::SRAr5)
2769                          : (opSize > 4? V9::SRLXr6 : V9::SRLr5),
2770                          subtreeRoot, mvec);
2771         break;
2772       }
2773
2774       case 64:  // reg:   Phi(reg,reg)
2775         break;                          // don't forward the value
2776
2777       case 65:  // reg:   VANext(reg):  the va_next(va_list, type) instruction
2778       { // Increment the va_list pointer register according to the type.
2779         // All LLVM argument types are <= 64 bits, so use one doubleword.
2780         Instruction* vaNextI = subtreeRoot->getInstruction();
2781         assert(target.getTargetData().getTypeSize(vaNextI->getType()) <= 8 &&
2782                "We assumed that all LLVM parameter types <= 8 bytes!");
2783         int argSize = target.getFrameInfo().getSizeOfEachArgOnStack();
2784         mvec.push_back(BuildMI(V9::ADDi, 3).addReg(vaNextI->getOperand(0)).
2785                        addSImm(argSize).addRegDef(vaNextI));
2786         break;
2787       }
2788
2789       case 66:  // reg:   VAArg (reg): the va_arg instruction
2790       { // Load argument from stack using current va_list pointer value.
2791         // Use 64-bit load for all non-FP args, and LDDF or double for FP.
2792         Instruction* vaArgI = subtreeRoot->getInstruction();
2793         MachineOpCode loadOp = (vaArgI->getType()->isFloatingPoint()
2794                                 ? (vaArgI->getType() == Type::FloatTy
2795                                    ? V9::LDFi : V9::LDDFi)
2796                                 : V9::LDXi);
2797         mvec.push_back(BuildMI(loadOp, 3).addReg(vaArgI->getOperand(0)).
2798                        addSImm(0).addRegDef(vaArgI));
2799         break;
2800       }
2801
2802       case 71:  // reg:     VReg
2803       case 72:  // reg:     Constant
2804         break;                          // don't forward the value
2805
2806       default:
2807         assert(0 && "Unrecognized BURG rule");
2808         break;
2809       }
2810     }
2811
2812   if (forwardOperandNum >= 0) {
2813     // We did not generate a machine instruction but need to use operand.
2814     // If user is in the same tree, replace Value in its machine operand.
2815     // If not, insert a copy instruction which should get coalesced away
2816     // by register allocation.
2817     if (subtreeRoot->parent() != NULL)
2818       ForwardOperand(subtreeRoot, subtreeRoot->parent(), forwardOperandNum);
2819     else {
2820       std::vector<MachineInstr*> minstrVec;
2821       Instruction* instr = subtreeRoot->getInstruction();
2822       target.getInstrInfo().
2823         CreateCopyInstructionsByType(target,
2824                                      instr->getParent()->getParent(),
2825                                      instr->getOperand(forwardOperandNum),
2826                                      instr, minstrVec,
2827                                      MachineCodeForInstruction::get(instr));
2828       assert(minstrVec.size() > 0);
2829       mvec.insert(mvec.end(), minstrVec.begin(), minstrVec.end());
2830     }
2831   }
2832
2833   if (maskUnsignedResult) {
2834     // If result is unsigned and smaller than int reg size,
2835     // we need to clear high bits of result value.
2836     assert(forwardOperandNum < 0 && "Need mask but no instruction generated");
2837     Instruction* dest = subtreeRoot->getInstruction();
2838     if (dest->getType()->isUnsigned()) {
2839       unsigned destSize=target.getTargetData().getTypeSize(dest->getType());
2840       if (destSize <= 4) {
2841         // Mask high 64 - N bits, where N = 4*destSize.
2842
2843         // Use a TmpInstruction to represent the
2844         // intermediate result before masking.  Since those instructions
2845         // have already been generated, go back and substitute tmpI
2846         // for dest in the result position of each one of them.
2847         //
2848         MachineCodeForInstruction& mcfi = MachineCodeForInstruction::get(dest);
2849         TmpInstruction *tmpI = new TmpInstruction(mcfi, dest->getType(),
2850                                                   dest, NULL, "maskHi");
2851         Value* srlArgToUse = tmpI;
2852
2853         unsigned numSubst = 0;
2854         for (unsigned i=0, N=mvec.size(); i < N; ++i) {
2855
2856           // Make sure we substitute all occurrences of dest in these instrs.
2857           // Otherwise, we will have bogus code.
2858           bool someArgsWereIgnored = false;
2859
2860           // Make sure not to substitute an upwards-exposed use -- that would
2861           // introduce a use of `tmpI' with no preceding def.  Therefore,
2862           // substitute a use or def-and-use operand only if a previous def
2863           // operand has already been substituted (i.e., numSusbt > 0).
2864           //
2865           numSubst += mvec[i]->substituteValue(dest, tmpI,
2866                                                /*defsOnly*/ numSubst == 0,
2867                                                /*notDefsAndUses*/ numSubst > 0,
2868                                                someArgsWereIgnored);
2869           assert(!someArgsWereIgnored &&
2870                  "Operand `dest' exists but not replaced: probably bogus!");
2871         }
2872         assert(numSubst > 0 && "Operand `dest' not replaced: probably bogus!");
2873
2874         // Left shift 32-N if size (N) is less than 32 bits.
2875         // Use another tmp. virtual register to represent this result.
2876         if (destSize < 4) {
2877           srlArgToUse = new TmpInstruction(mcfi, dest->getType(),
2878                                            tmpI, NULL, "maskHi2");
2879           mvec.push_back(BuildMI(V9::SLLXi6, 3).addReg(tmpI)
2880                          .addZImm(8*(4-destSize))
2881                          .addReg(srlArgToUse, MOTy::Def));
2882         }
2883
2884         // Logical right shift 32-N to get zero extension in top 64-N bits.
2885         mvec.push_back(BuildMI(V9::SRLi5, 3).addReg(srlArgToUse)
2886                        .addZImm(8*(4-destSize)).addReg(dest, MOTy::Def));
2887
2888       } else if (destSize < 8) {
2889         assert(0 && "Unsupported type size: 32 < size < 64 bits");
2890       }
2891     }
2892   }
2893 }
2894
2895 }