lib/Target/SparcV9/SparcV9BurgISel.cpp

   1 //===- SparcV9BurgISel.cpp - SparcV9 BURG-based Instruction Selector ------===//
   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 // SparcV9 BURG-based instruction selector. It uses the SSA graph to
  11 // construct a forest of BURG instruction trees (class InstrForest) and then
  12 // uses the BURG-generated tree grammar (BURM) to find the optimal instruction
  13 // sequences for the SparcV9.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "MachineInstrAnnot.h"
  18 #include "SparcV9BurgISel.h"
  19 #include "SparcV9InstrForest.h"
  20 #include "SparcV9Internals.h"
  21 #include "SparcV9TmpInstr.h"
  22 #include "SparcV9FrameInfo.h"
  23 #include "SparcV9RegisterInfo.h"
  24 #include "MachineFunctionInfo.h"
  25 #include "llvm/CodeGen/IntrinsicLowering.h"
  26 #include "llvm/CodeGen/MachineConstantPool.h"
  27 #include "llvm/CodeGen/MachineFunction.h"
  28 #include "llvm/CodeGen/MachineInstr.h"
  29 #include "llvm/CodeGen/MachineInstrBuilder.h"
  30 #include "llvm/Constants.h"
  31 #include "llvm/DerivedTypes.h"
  32 #include "llvm/Instructions.h"
  33 #include "llvm/Intrinsics.h"
  34 #include "llvm/Module.h"
  35 #include "llvm/Pass.h"
  36 #include "llvm/Support/CFG.h"
  37 #include "llvm/Target/TargetInstrInfo.h"
  38 #include "llvm/Target/TargetMachine.h"
  39 #include "llvm/Type.h"
  40 #include "llvm/Config/alloca.h"
  41 #include "llvm/Support/CommandLine.h"
  42 #include "llvm/Support/LeakDetector.h"
  43 #include "llvm/Support/MathExtras.h"
  44 #include "llvm/ADT/STLExtras.h"
  45 #include "llvm/ADT/hash_map"
  46 #include <algorithm>
  47 #include <cmath>
  48 #include <iostream>
  49 using namespace llvm;
  50
  51 //==------------------------------------------------------------------------==//
  52 //          InstrForest (V9ISel BURG instruction trees) implementation
  53 //==------------------------------------------------------------------------==//
  54
  55 namespace llvm {
  56
  57 class InstructionNode : public InstrTreeNode {
  58   bool codeIsFoldedIntoParent;
  59
  60 public:
  61   InstructionNode(Instruction *_instr);
  62
  63   Instruction *getInstruction() const {
  64     assert(treeNodeType == NTInstructionNode);
  65     return cast<Instruction>(val);
  66   }
  67
  68   void markFoldedIntoParent() { codeIsFoldedIntoParent = true; }
  69   bool isFoldedIntoParent()   { return codeIsFoldedIntoParent; }
  70
  71   // Methods to support type inquiry through isa, cast, and dyn_cast:
  72   static inline bool classof(const InstructionNode *N) { return true; }
  73   static inline bool classof(const InstrTreeNode *N) {
  74     return N->getNodeType() == InstrTreeNode::NTInstructionNode;
  75   }
  76
  77 protected:
  78   virtual void dumpNode(int indent) const;
  79 };
  80
  81 class VRegListNode : public InstrTreeNode {
  82 public:
  83   VRegListNode() : InstrTreeNode(NTVRegListNode, 0) { opLabel = VRegListOp; }
  84   // Methods to support type inquiry through isa, cast, and dyn_cast:
  85   static inline bool classof(const VRegListNode  *N) { return true; }
  86   static inline bool classof(const InstrTreeNode *N) {
  87     return N->getNodeType() == InstrTreeNode::NTVRegListNode;
  88   }
  89 protected:
  90   virtual void dumpNode(int indent) const;
  91 };
  92
  93 class VRegNode : public InstrTreeNode {
  94 public:
  95   VRegNode(Value* _val) : InstrTreeNode(NTVRegNode, _val) {
  96     opLabel = VRegNodeOp;
  97   }
  98   // Methods to support type inquiry through isa, cast, and dyn_cast:
  99   static inline bool classof(const VRegNode  *N) { return true; }
 100   static inline bool classof(const InstrTreeNode *N) {
 101     return N->getNodeType() == InstrTreeNode::NTVRegNode;
 102   }
 103 protected:
 104   virtual void dumpNode(int indent) const;
 105 };
 106
 107 class ConstantNode : public InstrTreeNode {
 108 public:
 109   ConstantNode(Constant *constVal)
 110     : InstrTreeNode(NTConstNode, (Value*)constVal) {
 111     opLabel = ConstantNodeOp;
 112   }
 113   Constant *getConstVal() const { return (Constant*) val;}
 114   // Methods to support type inquiry through isa, cast, and dyn_cast:
 115   static inline bool classof(const ConstantNode  *N) { return true; }
 116   static inline bool classof(const InstrTreeNode *N) {
 117     return N->getNodeType() == InstrTreeNode::NTConstNode;
 118   }
 119 protected:
 120   virtual void dumpNode(int indent) const;
 121 };
 122
 123 class LabelNode : public InstrTreeNode {
 124 public:
 125   LabelNode(BasicBlock* BB) : InstrTreeNode(NTLabelNode, (Value*)BB) {
 126     opLabel = LabelNodeOp;
 127   }
 128   BasicBlock *getBasicBlock() const { return (BasicBlock*)val;}
 129   // Methods to support type inquiry through isa, cast, and dyn_cast:
 130   static inline bool classof(const LabelNode     *N) { return true; }
 131   static inline bool classof(const InstrTreeNode *N) {
 132     return N->getNodeType() == InstrTreeNode::NTLabelNode;
 133   }
 134 protected:
 135   virtual void dumpNode(int indent) const;
 136 };
 137
 138 /// InstrForest -  A forest of instruction trees for a single function.
 139 /// The goal of InstrForest is to group instructions into a single
 140 /// tree if one or more of them might be potentially combined into a
 141 /// single complex instruction in the target machine. We group two
 142 /// instructions O and I if: (1) Instruction O computes an operand used
 143 /// by instruction I, and (2) O and I are part of the same basic block,
 144 /// and (3) O has only a single use, viz., I.
 145 ///
 146 class InstrForest : private hash_map<const Instruction *, InstructionNode*> {
 147 public:
 148   // Use a vector for the root set to get a deterministic iterator
 149   // for stable code generation.  Even though we need to erase nodes
 150   // during forest construction, a vector should still be efficient
 151   // because the elements to erase are nearly always near the end.
 152   typedef std::vector<InstructionNode*> RootSet;
 153   typedef RootSet::      iterator       root_iterator;
 154   typedef RootSet::const_iterator const_root_iterator;
 155
 156 private:
 157   RootSet treeRoots;
 158
 159 public:
 160   /*ctor*/      InstrForest     (Function *F);
 161   /*dtor*/      ~InstrForest    ();
 162
 163   /// getTreeNodeForInstr - Returns the tree node for an Instruction.
 164   ///
 165   inline InstructionNode *getTreeNodeForInstr(Instruction* instr) {
 166     return (*this)[instr];
 167   }
 168
 169   /// Iterators for the root nodes for all the trees.
 170   ///
 171   const_root_iterator roots_begin() const     { return treeRoots.begin(); }
 172         root_iterator roots_begin()           { return treeRoots.begin(); }
 173   const_root_iterator roots_end  () const     { return treeRoots.end();   }
 174         root_iterator roots_end  ()           { return treeRoots.end();   }
 175
 176   void dump() const;
 177
 178 private:
 179   // Methods used to build the instruction forest.
 180   void eraseRoot    (InstructionNode* node);
 181   void setLeftChild (InstrTreeNode* parent, InstrTreeNode* child);
 182   void setRightChild(InstrTreeNode* parent, InstrTreeNode* child);
 183   void setParent    (InstrTreeNode* child,  InstrTreeNode* parent);
 184   void noteTreeNodeForInstr(Instruction* instr, InstructionNode* treeNode);
 185   InstructionNode* buildTreeForInstruction(Instruction* instr);
 186 };
 187
 188 void InstrTreeNode::dump(int dumpChildren, int indent) const {
 189   dumpNode(indent);
 190
 191   if (dumpChildren) {
 192     if (LeftChild)
 193       LeftChild->dump(dumpChildren, indent+1);
 194     if (RightChild)
 195       RightChild->dump(dumpChildren, indent+1);
 196   }
 197 }
 198
 199 InstructionNode::InstructionNode(Instruction* I)
 200   : InstrTreeNode(NTInstructionNode, I), codeIsFoldedIntoParent(false) {
 201   opLabel = I->getOpcode();
 202
 203   // Distinguish special cases of some instructions such as Ret and Br
 204   //
 205   if (opLabel == Instruction::Ret && cast<ReturnInst>(I)->getReturnValue()) {
 206     opLabel = RetValueOp;                // ret(value) operation
 207   }
 208   else if (opLabel ==Instruction::Br && !cast<BranchInst>(I)->isUnconditional())
 209   {
 210     opLabel = BrCondOp;         // br(cond) operation
 211   } else if (opLabel >= Instruction::SetEQ && opLabel <= Instruction::SetGT) {
 212     opLabel = SetCCOp;          // common label for all SetCC ops
 213   } else if (opLabel == Instruction::Alloca && I->getNumOperands() > 0) {
 214     opLabel = AllocaN;           // Alloca(ptr, N) operation
 215   } else if (opLabel == Instruction::GetElementPtr &&
 216              cast<GetElementPtrInst>(I)->hasIndices()) {
 217     opLabel = opLabel + 100;             // getElem with index vector
 218   } else if (opLabel == Instruction::Xor &&
 219              BinaryOperator::isNot(I)) {
 220     opLabel = (I->getType() == Type::BoolTy)?  NotOp  // boolean Not operator
 221       : BNotOp; // bitwise Not operator
 222   } else if (opLabel == Instruction::And || opLabel == Instruction::Or ||
 223              opLabel == Instruction::Xor) {
 224     // Distinguish bitwise operators from logical operators!
 225     if (I->getType() != Type::BoolTy)
 226       opLabel = opLabel + 100;   // bitwise operator
 227   } else if (opLabel == Instruction::Cast) {
 228     const Type *ITy = I->getType();
 229     switch(ITy->getTypeID())
 230     {
 231     case Type::BoolTyID:    opLabel = ToBoolTy;    break;
 232     case Type::UByteTyID:   opLabel = ToUByteTy;   break;
 233     case Type::SByteTyID:   opLabel = ToSByteTy;   break;
 234     case Type::UShortTyID:  opLabel = ToUShortTy;  break;
 235     case Type::ShortTyID:   opLabel = ToShortTy;   break;
 236     case Type::UIntTyID:    opLabel = ToUIntTy;    break;
 237     case Type::IntTyID:     opLabel = ToIntTy;     break;
 238     case Type::ULongTyID:   opLabel = ToULongTy;   break;
 239     case Type::LongTyID:    opLabel = ToLongTy;    break;
 240     case Type::FloatTyID:   opLabel = ToFloatTy;   break;
 241     case Type::DoubleTyID:  opLabel = ToDoubleTy;  break;
 242     case Type::ArrayTyID:   opLabel = ToArrayTy;   break;
 243     case Type::PointerTyID: opLabel = ToPointerTy; break;
 244     default:
 245       // Just use `Cast' opcode otherwise. It's probably ignored.
 246       break;
 247     }
 248   }
 249 }
 250
 251 void InstructionNode::dumpNode(int indent) const {
 252   for (int i=0; i < indent; i++)
 253     std::cerr << "    ";
 254   std::cerr << getInstruction()->getOpcodeName()
 255             << " [label " << getOpLabel() << "]" << "\n";
 256 }
 257
 258 void VRegListNode::dumpNode(int indent) const {
 259   for (int i=0; i < indent; i++)
 260     std::cerr << "    ";
 261
 262   std::cerr << "List" << "\n";
 263 }
 264
 265 void VRegNode::dumpNode(int indent) const {
 266   for (int i=0; i < indent; i++)
 267     std::cerr << "    ";
 268     std::cerr << "VReg " << *getValue() << "\n";
 269 }
 270
 271 void ConstantNode::dumpNode(int indent) const {
 272   for (int i=0; i < indent; i++)
 273     std::cerr << "    ";
 274   std::cerr << "Constant " << *getValue() << "\n";
 275 }
 276
 277 void LabelNode::dumpNode(int indent) const {
 278   for (int i=0; i < indent; i++)
 279     std::cerr << "    ";
 280
 281   std::cerr << "Label " << *getValue() << "\n";
 282 }
 283
 284 /// InstrForest ctor - Create a forest of instruction trees for a
 285 /// single function.
 286 ///
 287 InstrForest::InstrForest(Function *F) {
 288   for (Function::iterator BB = F->begin(), FE = F->end(); BB != FE; ++BB) {
 289     for(BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
 290       buildTreeForInstruction(I);
 291   }
 292 }
 293
 294 InstrForest::~InstrForest() {
 295   for_each(treeRoots.begin(), treeRoots.end(), deleter<InstructionNode>);
 296 }
 297
 298 void InstrForest::dump() const {
 299   for (const_root_iterator I = roots_begin(); I != roots_end(); ++I)
 300     (*I)->dump(/*dumpChildren*/ 1, /*indent*/ 0);
 301 }
 302
 303 inline void InstrForest::eraseRoot(InstructionNode* node) {
 304   for (RootSet::reverse_iterator RI=treeRoots.rbegin(), RE=treeRoots.rend();
 305        RI != RE; ++RI)
 306     if (*RI == node)
 307       treeRoots.erase(RI.base()-1);
 308 }
 309
 310 inline void InstrForest::noteTreeNodeForInstr(Instruction *instr,
 311                                               InstructionNode *treeNode) {
 312   (*this)[instr] = treeNode;
 313   treeRoots.push_back(treeNode);        // mark node as root of a new tree
 314 }
 315
 316 inline void InstrForest::setLeftChild(InstrTreeNode *parent,
 317                                       InstrTreeNode *child) {
 318   parent->LeftChild = child;
 319   child->Parent = parent;
 320   if (InstructionNode* instrNode = dyn_cast<InstructionNode>(child))
 321     eraseRoot(instrNode); // no longer a tree root
 322 }
 323
 324 inline void InstrForest::setRightChild(InstrTreeNode *parent,
 325                                        InstrTreeNode *child) {
 326   parent->RightChild = child;
 327   child->Parent = parent;
 328   if (InstructionNode* instrNode = dyn_cast<InstructionNode>(child))
 329     eraseRoot(instrNode); // no longer a tree root
 330 }
 331
 332 InstructionNode* InstrForest::buildTreeForInstruction(Instruction *instr) {
 333   InstructionNode *treeNode = getTreeNodeForInstr(instr);
 334   if (treeNode) {
 335     // treeNode has already been constructed for this instruction
 336     assert(treeNode->getInstruction() == instr);
 337     return treeNode;
 338   }
 339
 340   // Otherwise, create a new tree node for this instruction.
 341   treeNode = new InstructionNode(instr);
 342   noteTreeNodeForInstr(instr, treeNode);
 343
 344   if (instr->getOpcode() == Instruction::Call) {
 345     // Operands of call instruction
 346     return treeNode;
 347   }
 348
 349   // If the instruction has more than 2 instruction operands,
 350   // then we need to create artificial list nodes to hold them.
 351   // (Note that we only count operands that get tree nodes, and not
 352   // others such as branch labels for a branch or switch instruction.)
 353   // To do this efficiently, we'll walk all operands, build treeNodes
 354   // for all appropriate operands and save them in an array.  We then
 355   // insert children at the end, creating list nodes where needed.
 356   // As a performance optimization, allocate a child array only
 357   // if a fixed array is too small.
 358   int numChildren = 0;
 359   InstrTreeNode** childArray = new InstrTreeNode*[instr->getNumOperands()];
 360
 361   // Walk the operands of the instruction
 362   for (Instruction::op_iterator O = instr->op_begin(); O!=instr->op_end();
 363        ++O) {
 364       Value* operand = *O;
 365
 366       // Check if the operand is a data value, not an branch label, type,
 367       // method or module.  If the operand is an address type (i.e., label
 368       // or method) that is used in an non-branching operation, e.g., `add'.
 369       // that should be considered a data value.
 370       // Check latter condition here just to simplify the next IF.
 371       bool includeAddressOperand =
 372         (isa<BasicBlock>(operand) || isa<Function>(operand))
 373         && !instr->isTerminator();
 374
 375       if (includeAddressOperand || isa<Instruction>(operand) ||
 376           isa<Constant>(operand) || isa<Argument>(operand)) {
 377         // This operand is a data value.
 378         // An instruction that computes the incoming value is added as a
 379         // child of the current instruction if:
 380         //   the value has only a single use
 381         //   AND both instructions are in the same basic block.
 382         //   AND the current instruction is not a PHI (because the incoming
 383         //              value is conceptually in a predecessor block,
 384         //              even though it may be in the same static block)
 385         // (Note that if the value has only a single use (viz., `instr'),
 386         //  the def of the value can be safely moved just before instr
 387         //  and therefore it is safe to combine these two instructions.)
 388         // In all other cases, the virtual register holding the value
 389         // is used directly, i.e., made a child of the instruction node.
 390         InstrTreeNode* opTreeNode;
 391         if (isa<Instruction>(operand) && operand->hasOneUse() &&
 392             cast<Instruction>(operand)->getParent() == instr->getParent() &&
 393             instr->getOpcode() != Instruction::PHI &&
 394             instr->getOpcode() != Instruction::Call) {
 395           // Recursively create a treeNode for it.
 396           opTreeNode = buildTreeForInstruction((Instruction*)operand);
 397         } else if (Constant *CPV = dyn_cast<Constant>(operand)) {
 398           if (isa<GlobalValue>(CPV))
 399             opTreeNode = new VRegNode(operand);
 400           else
 401             // Create a leaf node for a constant
 402             opTreeNode = new ConstantNode(CPV);
 403         } else {
 404           // Create a leaf node for the virtual register
 405           opTreeNode = new VRegNode(operand);
 406         }
 407
 408         childArray[numChildren++] = opTreeNode;
 409       }
 410     }
 411
 412   // Add any selected operands as children in the tree.
 413   // Certain instructions can have more than 2 in some instances (viz.,
 414   // a CALL or a memory access -- LOAD, STORE, and GetElemPtr -- to an
 415   // array or struct). Make the operands of every such instruction into
 416   // a right-leaning binary tree with the operand nodes at the leaves
 417   // and VRegList nodes as internal nodes.
 418   InstrTreeNode *parent = treeNode;
 419
 420   if (numChildren > 2) {
 421     unsigned instrOpcode = treeNode->getInstruction()->getOpcode();
 422     assert(instrOpcode == Instruction::PHI ||
 423            instrOpcode == Instruction::Call ||
 424            instrOpcode == Instruction::Load ||
 425            instrOpcode == Instruction::Store ||
 426            instrOpcode == Instruction::GetElementPtr);
 427   }
 428
 429   // Insert the first child as a direct child
 430   if (numChildren >= 1)
 431     setLeftChild(parent, childArray[0]);
 432
 433   int n;
 434
 435   // Create a list node for children 2 .. N-1, if any
 436   for (n = numChildren-1; n >= 2; n--) {
 437     // We have more than two children
 438     InstrTreeNode *listNode = new VRegListNode();
 439     setRightChild(parent, listNode);
 440     setLeftChild(listNode, childArray[numChildren - n]);
 441     parent = listNode;
 442   }
 443
 444   // Now insert the last remaining child (if any).
 445   if (numChildren >= 2) {
 446     assert(n == 1);
 447     setRightChild(parent, childArray[numChildren - 1]);
 448   }
 449
 450   delete [] childArray;
 451   return treeNode;
 452 }
 453 //==------------------------------------------------------------------------==//
 454 //                V9ISel Command-line options and declarations
 455 //==------------------------------------------------------------------------==//
 456
 457 namespace {
 458   /// Allow the user to select the amount of debugging information printed
 459   /// out by V9ISel.
 460   ///
 461   enum SelectDebugLevel_t {
 462     Select_NoDebugInfo,
 463     Select_PrintMachineCode,
 464     Select_DebugInstTrees,
 465     Select_DebugBurgTrees,
 466   };
 467   cl::opt<SelectDebugLevel_t>
 468   SelectDebugLevel("dselect", cl::Hidden,
 469                    cl::desc("enable instruction selection debug information"),
 470                    cl::values(
 471      clEnumValN(Select_NoDebugInfo,      "n", "disable debug output"),
 472      clEnumValN(Select_PrintMachineCode, "y", "print generated machine code"),
 473      clEnumValN(Select_DebugInstTrees,   "i",
 474                 "print debugging info for instruction selection"),
 475      clEnumValN(Select_DebugBurgTrees,   "b", "print burg trees"),
 476                               clEnumValEnd));
 477
 478
 479   /// V9ISel - This is the FunctionPass that drives the instruction selection
 480   /// process on the SparcV9 target.
 481   ///
 482   class V9ISel : public FunctionPass {
 483     TargetMachine &Target;
 484     void InsertCodeForPhis(Function &F);
 485     void InsertPhiElimInstructions(BasicBlock *BB,
 486                                    const std::vector<MachineInstr*>& CpVec);
 487     void SelectInstructionsForTree(InstrTreeNode* treeRoot, int goalnt);
 488     void PostprocessMachineCodeForTree(InstructionNode* instrNode,
 489                                        int ruleForNode, short* nts);
 490   public:
 491     V9ISel(TargetMachine &TM) : Target(TM) {}
 492
 493     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 494       AU.setPreservesCFG();
 495     }
 496
 497     bool runOnFunction(Function &F);
 498     virtual const char *getPassName() const {
 499       return "SparcV9 BURG Instruction Selector";
 500     }
 501   };
 502 }
 503
 504
 505 //==------------------------------------------------------------------------==//
 506 //                     Various V9ISel helper functions
 507 //==------------------------------------------------------------------------==//
 508
 509 static const uint32_t MAXLO   = (1 << 10) - 1; // set bits set by %lo(*)
 510 static const uint32_t MAXSIMM = (1 << 12) - 1; // set bits in simm13 field of OR
 511
 512 /// ConvertConstantToIntType - Function to get the value of an integral
 513 /// constant in the form that must be put into the machine register.  The
 514 /// specified constant is interpreted as (i.e., converted if necessary to) the
 515 /// specified destination type.  The result is always returned as an uint64_t,
 516 /// since the representation of int64_t and uint64_t are identical.  The
 517 /// argument can be any known const.  isValidConstant is set to true if a valid
 518 /// constant was found.
 519 ///
 520 uint64_t ConvertConstantToIntType(const TargetMachine &target, const Value *V,
 521                                   const Type *destType, bool &isValidConstant) {
 522   isValidConstant = false;
 523   uint64_t C = 0;
 524
 525   if (! destType->isIntegral() && ! isa<PointerType>(destType))
 526     return C;
 527
 528   if (! isa<Constant>(V) || isa<GlobalValue>(V))
 529     return C;
 530
 531   // GlobalValue: no conversions needed: get value and return it
 532   if (const GlobalValue* GV = dyn_cast<GlobalValue>(V)) {
 533     isValidConstant = true;             // may be overwritten by recursive call
 534     return ConvertConstantToIntType(target, GV, destType, isValidConstant);
 535   }
 536
 537   // ConstantBool: no conversions needed: get value and return it
 538   if (const ConstantBool *CB = dyn_cast<ConstantBool>(V)) {
 539     isValidConstant = true;
 540     return (uint64_t) CB->getValue();
 541   }
 542
 543   // ConstantPointerNull: it's really just a big, shiny version of zero.
 544   if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(V)) {
 545     isValidConstant = true;
 546     return 0;
 547   }
 548
 549   // For other types of constants, some conversion may be needed.
 550   // First, extract the constant operand according to its own type
 551   if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
 552     switch(CE->getOpcode()) {
 553     case Instruction::Cast:             // recursively get the value as cast
 554       C = ConvertConstantToIntType(target, CE->getOperand(0), CE->getType(),
 555                                    isValidConstant);
 556       break;
 557     default:                            // not simplifying other ConstantExprs
 558       break;
 559     }
 560   else if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
 561     isValidConstant = true;
 562     C = CI->getRawValue();
 563   } else if (const ConstantFP *CFP = dyn_cast<ConstantFP>(V)) {
 564     isValidConstant = true;
 565     double fC = CFP->getValue();
 566     C = (destType->isSigned()? (uint64_t) (int64_t) fC
 567                              : (uint64_t)           fC);
 568   }
 569
 570   // Now if a valid value was found, convert it to destType.
 571   if (isValidConstant) {
 572     unsigned opSize   = target.getTargetData().getTypeSize(V->getType());
 573     unsigned destSize = target.getTargetData().getTypeSize(destType);
 574     uint64_t maskHi   = (destSize < 8)? (1U << 8*destSize) - 1 : ~0;
 575     assert(opSize <= 8 && destSize <= 8 && ">8-byte int type unexpected");
 576
 577     if (destType->isSigned()) {
 578       if (opSize > destSize)            // operand is larger than dest:
 579         C = C & maskHi;                 // mask high bits
 580
 581       if (opSize > destSize ||
 582           (opSize == destSize && ! V->getType()->isSigned()))
 583         if (C & (1U << (8*destSize - 1)))
 584           C =  C | ~maskHi;             // sign-extend from destSize to 64 bits
 585     }
 586     else {
 587       if (opSize > destSize || (V->getType()->isSigned() && destSize < 8)) {
 588         // operand is larger than dest,
 589         //    OR both are equal but smaller than the full register size
 590         //       AND operand is signed, so it may have extra sign bits:
 591         // mask high bits
 592         C = C & maskHi;
 593       }
 594     }
 595   }
 596
 597   return C;
 598 }
 599
 600 /// CreateSETUWConst - Copy a 32-bit unsigned constant into the register
 601 /// `dest', using SETHI, OR in the worst case.  This function correctly emulates
 602 /// the SETUW pseudo-op for SPARC v9 (if argument isSigned == false). The
 603 /// isSigned=true case is used to implement SETSW without duplicating code. It
 604 /// optimizes some common cases:
 605 /// (1) Small value that fits in simm13 field of OR: don't need SETHI.
 606 /// (2) isSigned = true and C is a small negative signed value, i.e.,
 607 ///     high bits are 1, and the remaining bits fit in simm13(OR).
 608 static inline void
 609 CreateSETUWConst(uint32_t C,
 610                  Instruction* dest, std::vector<MachineInstr*>& mvec,
 611                  bool isSigned = false) {
 612   MachineInstr *miSETHI = NULL, *miOR = NULL;
 613
 614   // In order to get efficient code, we should not generate the SETHI if
 615   // all high bits are 1 (i.e., this is a small signed value that fits in
 616   // the simm13 field of OR).  So we check for and handle that case specially.
 617   // NOTE: The value C = 0x80000000 is bad: sC < 0 *and* -sC < 0.
 618   //       In fact, sC == -sC, so we have to check for this explicitly.
 619   int32_t sC = (int32_t) C;
 620   bool smallNegValue =isSigned && sC < 0 && sC != -sC && -sC < (int32_t)MAXSIMM;
 621
 622   // Set the high 22 bits in dest if non-zero and simm13 field of OR not enough
 623   if (!smallNegValue && (C & ~MAXLO) && C > MAXSIMM) {
 624     miSETHI = BuildMI(V9::SETHI, 2).addZImm(C).addRegDef(dest);
 625     miSETHI->getOperand(0).markHi32();
 626     mvec.push_back(miSETHI);
 627   }
 628
 629   // Set the low 10 or 12 bits in dest.  This is necessary if no SETHI
 630   // was generated, or if the low 10 bits are non-zero.
 631   if (miSETHI==NULL || C & MAXLO) {
 632     if (miSETHI) {
 633       // unsigned value with high-order bits set using SETHI
 634       miOR = BuildMI(V9::ORi,3).addReg(dest).addZImm(C).addRegDef(dest);
 635       miOR->getOperand(1).markLo32();
 636     } else {
 637       // unsigned or small signed value that fits in simm13 field of OR
 638       assert(smallNegValue || (C & ~MAXSIMM) == 0);
 639       miOR = BuildMI(V9::ORi, 3).addMReg(SparcV9::g0)
 640         .addSImm(sC).addRegDef(dest);
 641     }
 642     mvec.push_back(miOR);
 643   }
 644
 645   assert((miSETHI || miOR) && "Oops, no code was generated!");
 646 }
 647
 648 /// CreateSETSWConst - Set a 32-bit signed constant in the register `dest',
 649 /// with sign-extension to 64 bits.  This uses SETHI, OR, SRA in the worst case.
 650 /// This function correctly emulates the SETSW pseudo-op for SPARC v9.  It
 651 /// optimizes the same cases as SETUWConst, plus:
 652 /// (1) SRA is not needed for positive or small negative values.
 653 ///
 654 static inline void
 655 CreateSETSWConst(int32_t C,
 656                  Instruction* dest, std::vector<MachineInstr*>& mvec) {
 657   // Set the low 32 bits of dest
 658   CreateSETUWConst((uint32_t) C,  dest, mvec, /*isSigned*/true);
 659
 660   // Sign-extend to the high 32 bits if needed.
 661   // NOTE: The value C = 0x80000000 is bad: -C == C and so -C is < MAXSIMM
 662   if (C < 0 && (C == -C || -C > (int32_t) MAXSIMM))
 663     mvec.push_back(BuildMI(V9::SRAi5,3).addReg(dest).addZImm(0).addRegDef(dest));
 664 }
 665
 666 /// CreateSETXConst - Set a 64-bit signed or unsigned constant in the
 667 /// register `dest'.  Use SETUWConst for each 32 bit word, plus a
 668 /// left-shift-by-32 in between.  This function correctly emulates the SETX
 669 /// pseudo-op for SPARC v9.  It optimizes the same cases as SETUWConst for each
 670 /// 32 bit word.
 671 ///
 672 static inline void
 673 CreateSETXConst(uint64_t C,
 674                 Instruction* tmpReg, Instruction* dest,
 675                 std::vector<MachineInstr*>& mvec) {
 676   assert(C > (unsigned int) ~0 && "Use SETUW/SETSW for 32-bit values!");
 677
 678   MachineInstr* MI;
 679
 680   // Code to set the upper 32 bits of the value in register `tmpReg'
 681   CreateSETUWConst((C >> 32), tmpReg, mvec);
 682
 683   // Shift tmpReg left by 32 bits
 684   mvec.push_back(BuildMI(V9::SLLXi6, 3).addReg(tmpReg).addZImm(32)
 685                  .addRegDef(tmpReg));
 686
 687   // Code to set the low 32 bits of the value in register `dest'
 688   CreateSETUWConst(C, dest, mvec);
 689
 690   // dest = OR(tmpReg, dest)
 691   mvec.push_back(BuildMI(V9::ORr,3).addReg(dest).addReg(tmpReg).addRegDef(dest));
 692 }
 693
 694 /// CreateSETUWLabel - Set a 32-bit constant (given by a symbolic label) in
 695 /// the register `dest'.
 696 ///
 697 static inline void
 698 CreateSETUWLabel(Value* val,
 699                  Instruction* dest, std::vector<MachineInstr*>& mvec) {
 700   MachineInstr* MI;
 701
 702   // Set the high 22 bits in dest
 703   MI = BuildMI(V9::SETHI, 2).addReg(val).addRegDef(dest);
 704   MI->getOperand(0).markHi32();
 705   mvec.push_back(MI);
 706
 707   // Set the low 10 bits in dest
 708   MI = BuildMI(V9::ORr, 3).addReg(dest).addReg(val).addRegDef(dest);
 709   MI->getOperand(1).markLo32();
 710   mvec.push_back(MI);
 711 }
 712
 713 /// CreateSETXLabel - Set a 64-bit constant (given by a symbolic label) in the
 714 /// register `dest'.
 715 ///
 716 static inline void
 717 CreateSETXLabel(Value* val, Instruction* tmpReg,
 718                 Instruction* dest, std::vector<MachineInstr*>& mvec) {
 719   assert(isa<Constant>(val) &&
 720          "I only know about constant values and global addresses");
 721
 722   MachineInstr* MI;
 723
 724   MI = BuildMI(V9::SETHI, 2).addPCDisp(val).addRegDef(tmpReg);
 725   MI->getOperand(0).markHi64();
 726   mvec.push_back(MI);
 727
 728   MI = BuildMI(V9::ORi, 3).addReg(tmpReg).addPCDisp(val).addRegDef(tmpReg);
 729   MI->getOperand(1).markLo64();
 730   mvec.push_back(MI);
 731
 732   mvec.push_back(BuildMI(V9::SLLXi6, 3).addReg(tmpReg).addZImm(32)
 733                  .addRegDef(tmpReg));
 734   MI = BuildMI(V9::SETHI, 2).addPCDisp(val).addRegDef(dest);
 735   MI->getOperand(0).markHi32();
 736   mvec.push_back(MI);
 737
 738   MI = BuildMI(V9::ORr, 3).addReg(dest).addReg(tmpReg).addRegDef(dest);
 739   mvec.push_back(MI);
 740
 741   MI = BuildMI(V9::ORi, 3).addReg(dest).addPCDisp(val).addRegDef(dest);
 742   MI->getOperand(1).markLo32();
 743   mvec.push_back(MI);
 744 }
 745
 746 /// CreateUIntSetInstruction - Create code to Set an unsigned constant in the
 747 /// register `dest'.  Uses CreateSETUWConst, CreateSETSWConst or CreateSETXConst
 748 /// as needed.  CreateSETSWConst is an optimization for the case that the
 749 /// unsigned value has all ones in the 33 high bits (so that sign-extension sets
 750 /// them all).
 751 ///
 752 static inline void
 753 CreateUIntSetInstruction(uint64_t C, Instruction* dest,
 754                          std::vector<MachineInstr*>& mvec,
 755                          MachineCodeForInstruction& mcfi) {
 756   static const uint64_t lo32 = (uint32_t) ~0;
 757   if (C <= lo32)                        // High 32 bits are 0.  Set low 32 bits.
 758     CreateSETUWConst((uint32_t) C, dest, mvec);
 759   else if ((C & ~lo32) == ~lo32 && (C & (1U << 31))) {
 760     // All high 33 (not 32) bits are 1s: sign-extension will take care
 761     // of high 32 bits, so use the sequence for signed int
 762     CreateSETSWConst((int32_t) C, dest, mvec);
 763   } else if (C > lo32) {
 764     // C does not fit in 32 bits
 765     TmpInstruction* tmpReg = new TmpInstruction(mcfi, Type::IntTy);
 766     CreateSETXConst(C, tmpReg, dest, mvec);
 767   }
 768 }
 769
 770 /// CreateIntSetInstruction - Create code to Set a signed constant in the
 771 /// register `dest'.  Really the same as CreateUIntSetInstruction.
 772 ///
 773 static inline void
 774 CreateIntSetInstruction(int64_t C, Instruction* dest,
 775                         std::vector<MachineInstr*>& mvec,
 776                         MachineCodeForInstruction& mcfi) {
 777   CreateUIntSetInstruction((uint64_t) C, dest, mvec, mcfi);
 778 }
 779
 780 /// MaxConstantsTableTy - Table mapping LLVM opcodes to the max. immediate
 781 /// constant usable for that operation in the SparcV9 backend. Used by
 782 /// ConstantMayNotFitInImmedField().
 783 ///
 784 struct MaxConstantsTableTy {
 785   // Entry == 0 ==> no immediate constant field exists at all.
 786   // Entry >  0 ==> abs(immediate constant) <= Entry
 787   std::vector<int> tbl;
 788
 789   int getMaxConstantForInstr (unsigned llvmOpCode);
 790   MaxConstantsTableTy ();
 791   unsigned size() const            { return tbl.size (); }
 792   int &operator[] (unsigned index) { return tbl[index];  }
 793 };
 794
 795 int MaxConstantsTableTy::getMaxConstantForInstr(unsigned llvmOpCode) {
 796   int modelOpCode = -1;
 797
 798   if (llvmOpCode >= Instruction::BinaryOpsBegin &&
 799       llvmOpCode <  Instruction::BinaryOpsEnd)
 800     modelOpCode = V9::ADDi;
 801   else
 802     switch(llvmOpCode) {
 803     case Instruction::Ret:   modelOpCode = V9::JMPLCALLi; break;
 804
 805     case Instruction::Malloc:
 806     case Instruction::Alloca:
 807     case Instruction::GetElementPtr:
 808     case Instruction::PHI:
 809     case Instruction::Cast:
 810     case Instruction::Call:  modelOpCode = V9::ADDi; break;
 811
 812     case Instruction::Shl:
 813     case Instruction::Shr:   modelOpCode = V9::SLLXi6; break;
 814
 815     default: break;
 816     };
 817
 818   return (modelOpCode < 0)? 0: SparcV9MachineInstrDesc[modelOpCode].maxImmedConst;
 819 }
 820
 821 MaxConstantsTableTy::MaxConstantsTableTy () : tbl (Instruction::OtherOpsEnd) {
 822   unsigned op;
 823   assert(tbl.size() == Instruction::OtherOpsEnd &&
 824          "assignments below will be illegal!");
 825   for (op = Instruction::TermOpsBegin; op < Instruction::TermOpsEnd; ++op)
 826     tbl[op] = getMaxConstantForInstr(op);
 827   for (op = Instruction::BinaryOpsBegin; op < Instruction::BinaryOpsEnd; ++op)
 828     tbl[op] = getMaxConstantForInstr(op);
 829   for (op = Instruction::MemoryOpsBegin; op < Instruction::MemoryOpsEnd; ++op)
 830     tbl[op] = getMaxConstantForInstr(op);
 831   for (op = Instruction::OtherOpsBegin; op < Instruction::OtherOpsEnd; ++op)
 832     tbl[op] = getMaxConstantForInstr(op);
 833 }
 834
 835 bool ConstantMayNotFitInImmedField(const Constant* CV, const Instruction* I) {
 836   // The one and only MaxConstantsTable, used only by this function.
 837   static MaxConstantsTableTy MaxConstantsTable;
 838
 839   if (I->getOpcode() >= MaxConstantsTable.size()) // user-defined op (or bug!)
 840     return true;
 841
 842   if (isa<ConstantPointerNull>(CV))               // can always use %g0
 843     return false;
 844
 845   if (isa<SwitchInst>(I)) // Switch instructions will be lowered!
 846     return false;
 847
 848   if (const ConstantInt* CI = dyn_cast<ConstantInt>(CV))
 849     return labs((int64_t)CI->getRawValue()) > MaxConstantsTable[I->getOpcode()];
 850
 851   if (isa<ConstantBool>(CV))
 852     return 1 > MaxConstantsTable[I->getOpcode()];
 853
 854   return true;
 855 }
 856
 857 /// ChooseLoadInstruction - Return the appropriate load instruction opcode
 858 /// based on the given LLVM value type.
 859 ///
 860 static inline MachineOpCode ChooseLoadInstruction(const Type *DestTy) {
 861   switch (DestTy->getTypeID()) {
 862   case Type::BoolTyID:
 863   case Type::UByteTyID:   return V9::LDUBr;
 864   case Type::SByteTyID:   return V9::LDSBr;
 865   case Type::UShortTyID:  return V9::LDUHr;
 866   case Type::ShortTyID:   return V9::LDSHr;
 867   case Type::UIntTyID:    return V9::LDUWr;
 868   case Type::IntTyID:     return V9::LDSWr;
 869   case Type::PointerTyID:
 870   case Type::ULongTyID:
 871   case Type::LongTyID:    return V9::LDXr;
 872   case Type::FloatTyID:   return V9::LDFr;
 873   case Type::DoubleTyID:  return V9::LDDFr;
 874   default: assert(0 && "Invalid type for Load instruction");
 875   }
 876   return 0;
 877 }
 878
 879 /// ChooseStoreInstruction - Return the appropriate store instruction opcode
 880 /// based on the given LLVM value type.
 881 ///
 882 static inline MachineOpCode ChooseStoreInstruction(const Type *DestTy) {
 883   switch (DestTy->getTypeID()) {
 884   case Type::BoolTyID:
 885   case Type::UByteTyID:
 886   case Type::SByteTyID:   return V9::STBr;
 887   case Type::UShortTyID:
 888   case Type::ShortTyID:   return V9::STHr;
 889   case Type::UIntTyID:
 890   case Type::IntTyID:     return V9::STWr;
 891   case Type::PointerTyID:
 892   case Type::ULongTyID:
 893   case Type::LongTyID:    return V9::STXr;
 894   case Type::FloatTyID:   return V9::STFr;
 895   case Type::DoubleTyID:  return V9::STDFr;
 896   default: assert(0 && "Invalid type for Store instruction");
 897   }
 898   return 0;
 899 }
 900
 901 static inline MachineOpCode ChooseAddInstructionByType(const Type* resultType) {
 902   MachineOpCode opCode = V9::INVALID_OPCODE;
 903   if (resultType->isIntegral() || isa<PointerType>(resultType)
 904       || isa<FunctionType>(resultType) || resultType == Type::LabelTy) {
 905     opCode = V9::ADDr;
 906   } else
 907     switch(resultType->getTypeID()) {
 908     case Type::FloatTyID:  opCode = V9::FADDS; break;
 909     case Type::DoubleTyID: opCode = V9::FADDD; break;
 910     default: assert(0 && "Invalid type for ADD instruction"); break;
 911     }
 912
 913   return opCode;
 914 }
 915
 916 /// convertOpcodeFromRegToImm - Because the SparcV9 instruction selector likes
 917 /// to re-write operands to instructions, making them change from a Value*
 918 /// (virtual register) to a Constant* (making an immediate field), we need to
 919 /// change the opcode from a register-based instruction to an immediate-based
 920 /// instruction, hence this mapping.
 921 ///
 922 static unsigned convertOpcodeFromRegToImm(unsigned Opcode) {
 923   switch (Opcode) {
 924     /* arithmetic */
 925   case V9::ADDr:     return V9::ADDi;
 926   case V9::ADDccr:   return V9::ADDcci;
 927   case V9::ADDCr:    return V9::ADDCi;
 928   case V9::ADDCccr:  return V9::ADDCcci;
 929   case V9::SUBr:     return V9::SUBi;
 930   case V9::SUBccr:   return V9::SUBcci;
 931   case V9::SUBCr:    return V9::SUBCi;
 932   case V9::SUBCccr:  return V9::SUBCcci;
 933   case V9::MULXr:    return V9::MULXi;
 934   case V9::SDIVXr:   return V9::SDIVXi;
 935   case V9::UDIVXr:   return V9::UDIVXi;
 936
 937     /* logical */
 938   case V9::ANDr:    return V9::ANDi;
 939   case V9::ANDccr:  return V9::ANDcci;
 940   case V9::ANDNr:   return V9::ANDNi;
 941   case V9::ANDNccr: return V9::ANDNcci;
 942   case V9::ORr:     return V9::ORi;
 943   case V9::ORccr:   return V9::ORcci;
 944   case V9::ORNr:    return V9::ORNi;
 945   case V9::ORNccr:  return V9::ORNcci;
 946   case V9::XORr:    return V9::XORi;
 947   case V9::XORccr:  return V9::XORcci;
 948   case V9::XNORr:   return V9::XNORi;
 949   case V9::XNORccr: return V9::XNORcci;
 950
 951     /* shift */
 952   case V9::SLLr5:   return V9::SLLi5;
 953   case V9::SRLr5:   return V9::SRLi5;
 954   case V9::SRAr5:   return V9::SRAi5;
 955   case V9::SLLXr6:  return V9::SLLXi6;
 956   case V9::SRLXr6:  return V9::SRLXi6;
 957   case V9::SRAXr6:  return V9::SRAXi6;
 958
 959     /* Conditional move on int comparison with zero */
 960   case V9::MOVRZr:   return V9::MOVRZi;
 961   case V9::MOVRLEZr: return V9::MOVRLEZi;
 962   case V9::MOVRLZr:  return V9::MOVRLZi;
 963   case V9::MOVRNZr:  return V9::MOVRNZi;
 964   case V9::MOVRGZr:  return V9::MOVRGZi;
 965   case V9::MOVRGEZr: return V9::MOVRGEZi;
 966
 967
 968     /* Conditional move on int condition code */
 969   case V9::MOVAr:   return V9::MOVAi;
 970   case V9::MOVNr:   return V9::MOVNi;
 971   case V9::MOVNEr:  return V9::MOVNEi;
 972   case V9::MOVEr:   return V9::MOVEi;
 973   case V9::MOVGr:   return V9::MOVGi;
 974   case V9::MOVLEr:  return V9::MOVLEi;
 975   case V9::MOVGEr:  return V9::MOVGEi;
 976   case V9::MOVLr:   return V9::MOVLi;
 977   case V9::MOVGUr:  return V9::MOVGUi;
 978   case V9::MOVLEUr: return V9::MOVLEUi;
 979   case V9::MOVCCr:  return V9::MOVCCi;
 980   case V9::MOVCSr:  return V9::MOVCSi;
 981   case V9::MOVPOSr: return V9::MOVPOSi;
 982   case V9::MOVNEGr: return V9::MOVNEGi;
 983   case V9::MOVVCr:  return V9::MOVVCi;
 984   case V9::MOVVSr:  return V9::MOVVSi;
 985
 986     /* Conditional move of int reg on fp condition code */
 987   case V9::MOVFAr:   return V9::MOVFAi;
 988   case V9::MOVFNr:   return V9::MOVFNi;
 989   case V9::MOVFUr:   return V9::MOVFUi;
 990   case V9::MOVFGr:   return V9::MOVFGi;
 991   case V9::MOVFUGr:  return V9::MOVFUGi;
 992   case V9::MOVFLr:   return V9::MOVFLi;
 993   case V9::MOVFULr:  return V9::MOVFULi;
 994   case V9::MOVFLGr:  return V9::MOVFLGi;
 995   case V9::MOVFNEr:  return V9::MOVFNEi;
 996   case V9::MOVFEr:   return V9::MOVFEi;
 997   case V9::MOVFUEr:  return V9::MOVFUEi;
 998   case V9::MOVFGEr:  return V9::MOVFGEi;
 999   case V9::MOVFUGEr: return V9::MOVFUGEi;
1000   case V9::MOVFLEr:  return V9::MOVFLEi;
1001   case V9::MOVFULEr: return V9::MOVFULEi;
1002   case V9::MOVFOr:   return V9::MOVFOi;
1003
1004     /* load */
1005   case V9::LDSBr:   return V9::LDSBi;
1006   case V9::LDSHr:   return V9::LDSHi;
1007   case V9::LDSWr:   return V9::LDSWi;
1008   case V9::LDUBr:   return V9::LDUBi;
1009   case V9::LDUHr:   return V9::LDUHi;
1010   case V9::LDUWr:   return V9::LDUWi;
1011   case V9::LDXr:    return V9::LDXi;
1012   case V9::LDFr:    return V9::LDFi;
1013   case V9::LDDFr:   return V9::LDDFi;
1014   case V9::LDQFr:   return V9::LDQFi;
1015   case V9::LDFSRr:  return V9::LDFSRi;
1016   case V9::LDXFSRr: return V9::LDXFSRi;
1017
1018     /* store */
1019   case V9::STBr:    return V9::STBi;
1020   case V9::STHr:    return V9::STHi;
1021   case V9::STWr:    return V9::STWi;
1022   case V9::STXr:    return V9::STXi;
1023   case V9::STFr:    return V9::STFi;
1024   case V9::STDFr:   return V9::STDFi;
1025   case V9::STFSRr:  return V9::STFSRi;
1026   case V9::STXFSRr: return V9::STXFSRi;
1027
1028     /* jump & return */
1029   case V9::JMPLCALLr: return V9::JMPLCALLi;
1030   case V9::JMPLRETr:  return V9::JMPLRETi;
1031
1032   /* save and restore */
1033   case V9::SAVEr:     return V9::SAVEi;
1034   case V9::RESTOREr:  return V9::RESTOREi;
1035
1036   default:
1037     // It's already in correct format
1038     // Or, it's just not handled yet, but an assert() would break LLC
1039 #if 0
1040     std::cerr << "Unhandled opcode in convertOpcodeFromRegToImm(): " << Opcode
1041               << "\n";
1042 #endif
1043     return Opcode;
1044   }
1045 }
1046
1047 /// CreateCodeToLoadConst - Create an instruction sequence to put the
1048 /// constant `val' into the virtual register `dest'.  `val' may be a Constant or
1049 /// a GlobalValue, viz., the constant address of a global variable or function.
1050 /// The generated instructions are returned in `mvec'. Any temp. registers
1051 /// (TmpInstruction) created are recorded in mcfi. Any stack space required is
1052 /// allocated via MachineFunction.
1053 ///
1054 void CreateCodeToLoadConst(const TargetMachine& target, Function* F,
1055                            Value* val, Instruction* dest,
1056                            std::vector<MachineInstr*>& mvec,
1057                            MachineCodeForInstruction& mcfi) {
1058   assert(isa<Constant>(val) &&
1059          "I only know about constant values and global addresses");
1060
1061   // Use a "set" instruction for known constants or symbolic constants (labels)
1062   // that can go in an integer reg.
1063   // We have to use a "load" instruction for all other constants,
1064   // in particular, floating point constants.
1065   const Type* valType = val->getType();
1066
1067   if (isa<GlobalValue>(val)) {
1068       TmpInstruction* tmpReg =
1069         new TmpInstruction(mcfi, PointerType::get(val->getType()), val);
1070       CreateSETXLabel(val, tmpReg, dest, mvec);
1071       return;
1072   }
1073
1074   bool isValid;
1075   uint64_t C = ConvertConstantToIntType(target, val, dest->getType(), isValid);
1076   if (isValid) {
1077     if (dest->getType()->isSigned())
1078       CreateUIntSetInstruction(C, dest, mvec, mcfi);
1079     else
1080       CreateIntSetInstruction((int64_t) C, dest, mvec, mcfi);
1081
1082   } else {
1083     // Make an instruction sequence to load the constant, viz:
1084     //            SETX <addr-of-constant>, tmpReg, addrReg
1085     //            LOAD  /*addr*/ addrReg, /*offset*/ 0, dest
1086     // First, create a tmp register to be used by the SETX sequence.
1087     TmpInstruction* tmpReg =
1088       new TmpInstruction(mcfi, PointerType::get(val->getType()));
1089
1090     // Create another TmpInstruction for the address register
1091     TmpInstruction* addrReg =
1092       new TmpInstruction(mcfi, PointerType::get(val->getType()));
1093
1094     // Get the constant pool index for this constant
1095     MachineConstantPool *CP = MachineFunction::get(F).getConstantPool();
1096     Constant *C = cast<Constant>(val);
1097     unsigned CPI = CP->getConstantPoolIndex(C);
1098
1099     // Put the address of the constant into a register
1100     MachineInstr* MI;
1101
1102     MI = BuildMI(V9::SETHI, 2).addConstantPoolIndex(CPI).addRegDef(tmpReg);
1103     MI->getOperand(0).markHi64();
1104     mvec.push_back(MI);
1105
1106     MI = BuildMI(V9::ORi, 3).addReg(tmpReg).addConstantPoolIndex(CPI)
1107       .addRegDef(tmpReg);
1108     MI->getOperand(1).markLo64();
1109     mvec.push_back(MI);
1110
1111     mvec.push_back(BuildMI(V9::SLLXi6, 3).addReg(tmpReg).addZImm(32)
1112                    .addRegDef(tmpReg));
1113     MI = BuildMI(V9::SETHI, 2).addConstantPoolIndex(CPI).addRegDef(addrReg);
1114     MI->getOperand(0).markHi32();
1115     mvec.push_back(MI);
1116
1117     MI = BuildMI(V9::ORr, 3).addReg(addrReg).addReg(tmpReg).addRegDef(addrReg);
1118     mvec.push_back(MI);
1119
1120     MI = BuildMI(V9::ORi, 3).addReg(addrReg).addConstantPoolIndex(CPI)
1121       .addRegDef(addrReg);
1122     MI->getOperand(1).markLo32();
1123     mvec.push_back(MI);
1124
1125     // Now load the constant from out ConstantPool label
1126     unsigned Opcode = ChooseLoadInstruction(val->getType());
1127     Opcode = convertOpcodeFromRegToImm(Opcode);
1128     mvec.push_back(BuildMI(Opcode, 3)
1129                    .addReg(addrReg).addSImm((int64_t)0).addRegDef(dest));
1130   }
1131 }
1132
1133 /// CreateCodeToCopyFloatToInt - Similarly, create an instruction sequence
1134 /// to copy an FP register `val' to an integer register `dest' by copying to
1135 /// memory and back.  The generated instructions are returned in `mvec'.  Any
1136 /// temp. virtual registers (TmpInstruction) created are recorded in mcfi.
1137 /// Temporary stack space required is allocated via MachineFunction.
1138 ///
1139 void CreateCodeToCopyFloatToInt(const TargetMachine& target, Function* F,
1140                                 Value* val, Instruction* dest,
1141                                 std::vector<MachineInstr*>& mvec,
1142                                 MachineCodeForInstruction& mcfi) {
1143   const Type* opTy   = val->getType();
1144   const Type* destTy = dest->getType();
1145   assert(opTy->isFloatingPoint() && "Source type must be float/double");
1146   assert((destTy->isIntegral() || isa<PointerType>(destTy))
1147          && "Dest type must be integer, bool or pointer");
1148
1149   // FIXME: For now, we allocate permanent space because the stack frame
1150   // manager does not allow locals to be allocated (e.g., for alloca) after
1151   // a temp is allocated!
1152   int offset = MachineFunction::get(F).getInfo<SparcV9FunctionInfo>()->allocateLocalVar(val);
1153
1154   unsigned FPReg = target.getRegInfo()->getFramePointer();
1155
1156   // Store instruction stores `val' to [%fp+offset].
1157   // The store opCode is based only the source value being copied.
1158   unsigned StoreOpcode = ChooseStoreInstruction(opTy);
1159   StoreOpcode = convertOpcodeFromRegToImm(StoreOpcode);
1160   mvec.push_back(BuildMI(StoreOpcode, 3)
1161                  .addReg(val).addMReg(FPReg).addSImm(offset));
1162
1163   // Load instruction loads [%fp+offset] to `dest'.
1164   // The type of the load opCode is the integer type that matches the
1165   // source type in size:
1166   // On SparcV9: int for float, long for double.
1167   // Note that we *must* use signed loads even for unsigned dest types, to
1168   // ensure correct sign-extension for UByte, UShort or UInt:
1169   const Type* loadTy = (opTy == Type::FloatTy)? Type::IntTy : Type::LongTy;
1170   unsigned LoadOpcode = ChooseLoadInstruction(loadTy);
1171   LoadOpcode = convertOpcodeFromRegToImm(LoadOpcode);
1172   mvec.push_back(BuildMI(LoadOpcode, 3).addMReg(FPReg)
1173                  .addSImm(offset).addRegDef(dest));
1174 }
1175
1176 /// CreateBitExtensionInstructions - Helper function for sign-extension and
1177 /// zero-extension. For SPARC v9, we sign-extend the given operand using SLL;
1178 /// SRA/SRL.
1179 ///
1180 inline void
1181 CreateBitExtensionInstructions(bool signExtend, const TargetMachine& target,
1182                                Function* F, Value* srcVal, Value* destVal,
1183                                unsigned int numLowBits,
1184                                std::vector<MachineInstr*>& mvec,
1185                                MachineCodeForInstruction& mcfi) {
1186   MachineInstr* M;
1187
1188   assert(numLowBits <= 32 && "Otherwise, nothing should be done here!");
1189
1190   if (numLowBits < 32) {
1191     // SLL is needed since operand size is < 32 bits.
1192     TmpInstruction *tmpI = new TmpInstruction(mcfi, destVal->getType(),
1193                                               srcVal, destVal, "make32");
1194     mvec.push_back(BuildMI(V9::SLLXi6, 3).addReg(srcVal)
1195                    .addZImm(32-numLowBits).addRegDef(tmpI));
1196     srcVal = tmpI;
1197   }
1198
1199   mvec.push_back(BuildMI(signExtend? V9::SRAi5 : V9::SRLi5, 3)
1200                  .addReg(srcVal).addZImm(32-numLowBits).addRegDef(destVal));
1201 }
1202
1203 /// CreateSignExtensionInstructions - Create instruction sequence to produce
1204 /// a sign-extended register value from an arbitrary-sized integer value (sized
1205 /// in bits, not bytes). The generated instructions are returned in `mvec'. Any
1206 /// temp. registers (TmpInstruction) created are recorded in mcfi. Any stack
1207 /// space required is allocated via MachineFunction.
1208 ///
1209 void CreateSignExtensionInstructions(const TargetMachine& target,
1210                                      Function* F, Value* srcVal, Value* destVal,
1211                                      unsigned int numLowBits,
1212                                      std::vector<MachineInstr*>& mvec,
1213                                      MachineCodeForInstruction& mcfi) {
1214   CreateBitExtensionInstructions(/*signExtend*/ true, target, F, srcVal,
1215                                  destVal, numLowBits, mvec, mcfi);
1216 }
1217
1218 /// CreateZeroExtensionInstructions - Create instruction sequence to produce
1219 /// a zero-extended register value from an arbitrary-sized integer value (sized
1220 /// in bits, not bytes).  For SPARC v9, we sign-extend the given operand using
1221 /// SLL; SRL.  The generated instructions are returned in `mvec'.  Any temp.
1222 /// registers (TmpInstruction) created are recorded in mcfi.  Any stack space
1223 /// required is allocated via MachineFunction.
1224 ///
1225 void CreateZeroExtensionInstructions(const TargetMachine& target,
1226                                      Function* F, Value* srcVal, Value* destVal,
1227                                      unsigned int numLowBits,
1228                                      std::vector<MachineInstr*>& mvec,
1229                                      MachineCodeForInstruction& mcfi) {
1230   CreateBitExtensionInstructions(/*signExtend*/ false, target, F, srcVal,
1231                                  destVal, numLowBits, mvec, mcfi);
1232 }
1233
1234 /// CreateCodeToCopyIntToFloat - Create an instruction sequence to copy an
1235 /// integer register `val' to a floating point register `dest' by copying to
1236 /// memory and back. val must be an integral type.  dest must be a Float or
1237 /// Double. The generated instructions are returned in `mvec'. Any temp.
1238 /// registers (TmpInstruction) created are recorded in mcfi. Any stack space
1239 /// required is allocated via MachineFunction.
1240 ///
1241 void CreateCodeToCopyIntToFloat(const TargetMachine& target,
1242                                 Function* F, Value* val, Instruction* dest,
1243                                 std::vector<MachineInstr*>& mvec,
1244                                 MachineCodeForInstruction& mcfi) {
1245   assert((val->getType()->isIntegral() || isa<PointerType>(val->getType()))
1246          && "Source type must be integral (integer or bool) or pointer");
1247   assert(dest->getType()->isFloatingPoint()
1248          && "Dest type must be float/double");
1249
1250   // Get a stack slot to use for the copy
1251   int offset = MachineFunction::get(F).getInfo<SparcV9FunctionInfo>()->allocateLocalVar(val);
1252
1253   // Get the size of the source value being copied.
1254   size_t srcSize = target.getTargetData().getTypeSize(val->getType());
1255
1256   // Store instruction stores `val' to [%fp+offset].
1257   // The store and load opCodes are based on the size of the source value.
1258   // If the value is smaller than 32 bits, we must sign- or zero-extend it
1259   // to 32 bits since the load-float will load 32 bits.
1260   // Note that the store instruction is the same for signed and unsigned ints.
1261   const Type* storeType = (srcSize <= 4)? Type::IntTy : Type::LongTy;
1262   Value* storeVal = val;
1263   if (srcSize < target.getTargetData().getTypeSize(Type::FloatTy)) {
1264     // sign- or zero-extend respectively
1265     storeVal = new TmpInstruction(mcfi, storeType, val);
1266     if (val->getType()->isSigned())
1267       CreateSignExtensionInstructions(target, F, val, storeVal, 8*srcSize,
1268                                       mvec, mcfi);
1269     else
1270       CreateZeroExtensionInstructions(target, F, val, storeVal, 8*srcSize,
1271                                       mvec, mcfi);
1272   }
1273
1274   unsigned FPReg = target.getRegInfo()->getFramePointer();
1275   unsigned StoreOpcode = ChooseStoreInstruction(storeType);
1276   StoreOpcode = convertOpcodeFromRegToImm(StoreOpcode);
1277   mvec.push_back(BuildMI(StoreOpcode, 3)
1278                  .addReg(storeVal).addMReg(FPReg).addSImm(offset));
1279
1280   // Load instruction loads [%fp+offset] to `dest'.
1281   // The type of the load opCode is the floating point type that matches the
1282   // stored type in size:
1283   // On SparcV9: float for int or smaller, double for long.
1284   const Type* loadType = (srcSize <= 4)? Type::FloatTy : Type::DoubleTy;
1285   unsigned LoadOpcode = ChooseLoadInstruction(loadType);
1286   LoadOpcode = convertOpcodeFromRegToImm(LoadOpcode);
1287   mvec.push_back(BuildMI(LoadOpcode, 3)
1288                  .addMReg(FPReg).addSImm(offset).addRegDef(dest));
1289 }
1290
1291 /// InsertCodeToLoadConstant - Generates code to load the constant
1292 /// into a TmpInstruction (virtual reg) and returns the virtual register.
1293 ///
1294 static TmpInstruction*
1295 InsertCodeToLoadConstant(Function *F, Value* opValue, Instruction* vmInstr,
1296                          std::vector<MachineInstr*>& loadConstVec,
1297                          TargetMachine& target) {
1298   // Create a tmp virtual register to hold the constant.
1299   MachineCodeForInstruction &mcfi = MachineCodeForInstruction::get(vmInstr);
1300   TmpInstruction* tmpReg = new TmpInstruction(mcfi, opValue);
1301
1302   CreateCodeToLoadConst(target, F, opValue, tmpReg, loadConstVec, mcfi);
1303
1304   // Record the mapping from the tmp VM instruction to machine instruction.
1305   // Do this for all machine instructions that were not mapped to any
1306   // other temp values created by
1307   // tmpReg->addMachineInstruction(loadConstVec.back());
1308   return tmpReg;
1309 }
1310
1311 MachineOperand::MachineOperandType
1312 ChooseRegOrImmed(int64_t intValue, bool isSigned,
1313                  MachineOpCode opCode, const TargetMachine& target,
1314                  bool canUseImmed, unsigned int& getMachineRegNum,
1315                  int64_t& getImmedValue) {
1316   MachineOperand::MachineOperandType opType=MachineOperand::MO_VirtualRegister;
1317   getMachineRegNum = 0;
1318   getImmedValue = 0;
1319
1320   if (canUseImmed &&
1321       target.getInstrInfo()->constantFitsInImmedField(opCode, intValue)) {
1322       opType = isSigned? MachineOperand::MO_SignExtendedImmed
1323                        : MachineOperand::MO_UnextendedImmed;
1324       getImmedValue = intValue;
1325   } else if (intValue == 0 &&
1326              target.getRegInfo()->getZeroRegNum() != (unsigned)-1) {
1327     opType = MachineOperand::MO_MachineRegister;
1328     getMachineRegNum = target.getRegInfo()->getZeroRegNum();
1329   }
1330
1331   return opType;
1332 }
1333
1334 MachineOperand::MachineOperandType
1335 ChooseRegOrImmed(Value* val,
1336                  MachineOpCode opCode, const TargetMachine& target,
1337                  bool canUseImmed, unsigned int& getMachineRegNum,
1338                  int64_t& getImmedValue) {
1339   getMachineRegNum = 0;
1340   getImmedValue = 0;
1341
1342   // To use reg or immed, constant needs to be integer, bool, or a NULL pointer.
1343   // ConvertConstantToIntType() does the right conversions.
1344   bool isValidConstant;
1345   uint64_t valueToUse =
1346     ConvertConstantToIntType(target, val, val->getType(), isValidConstant);
1347   if (! isValidConstant)
1348     return MachineOperand::MO_VirtualRegister;
1349
1350   // Now check if the constant value fits in the IMMED field.
1351   return ChooseRegOrImmed((int64_t) valueToUse, val->getType()->isSigned(),
1352                           opCode, target, canUseImmed,
1353                           getMachineRegNum, getImmedValue);
1354 }
1355
1356 /// CreateCopyInstructionsByType - Create instruction(s) to copy src to dest,
1357 /// for arbitrary types. The generated instructions are returned in `mvec'. Any
1358 /// temp. registers (TmpInstruction) created are recorded in mcfi. Any stack
1359 /// space required is allocated via MachineFunction.
1360 ///
1361 void CreateCopyInstructionsByType(const TargetMachine& target,
1362                                   Function *F, Value* src, Instruction* dest,
1363                                   std::vector<MachineInstr*>& mvec,
1364                                   MachineCodeForInstruction& mcfi) {
1365   bool loadConstantToReg = false;
1366   const Type* resultType = dest->getType();
1367   MachineOpCode opCode = ChooseAddInstructionByType(resultType);
1368   assert (opCode != V9::INVALID_OPCODE
1369           && "Unsupported result type in CreateCopyInstructionsByType()");
1370
1371   // If `src' is a constant that doesn't fit in the immed field or if it is
1372   // a global variable (i.e., a constant address), generate a load
1373   // instruction instead of an add.
1374   if (isa<GlobalValue>(src))
1375     loadConstantToReg = true;
1376   else if (isa<Constant>(src)) {
1377     unsigned int machineRegNum;
1378     int64_t immedValue;
1379     MachineOperand::MachineOperandType opType =
1380       ChooseRegOrImmed(src, opCode, target, /*canUseImmed*/ true,
1381                        machineRegNum, immedValue);
1382
1383     if (opType == MachineOperand::MO_VirtualRegister)
1384       loadConstantToReg = true;
1385   }
1386
1387   if (loadConstantToReg) {
1388     // `src' is constant and cannot fit in immed field for the ADD.
1389     // Insert instructions to "load" the constant into a register.
1390     CreateCodeToLoadConst(target, F, src, dest, mvec, mcfi);
1391   } else {
1392     // Create a reg-to-reg copy instruction for the given type:
1393     // -- For FP values, create a FMOVS or FMOVD instruction
1394     // -- For non-FP values, create an add-with-0 instruction (opCode as above)
1395     // Make `src' the second operand, in case it is a small constant!
1396     MachineInstr* MI;
1397     if (resultType->isFloatingPoint())
1398       MI = (BuildMI(resultType == Type::FloatTy? V9::FMOVS : V9::FMOVD, 2)
1399             .addReg(src).addRegDef(dest));
1400     else {
1401         const Type* Ty =isa<PointerType>(resultType)? Type::ULongTy :resultType;
1402         MI = (BuildMI(opCode, 3)
1403               .addSImm((int64_t) 0).addReg(src).addRegDef(dest));
1404     }
1405     mvec.push_back(MI);
1406   }
1407 }
1408
1409 /// FixConstantOperandsForInstr - Make a machine instruction use its constant
1410 /// operands more efficiently.  If the constant is 0, then use the hardwired 0
1411 /// register, if any.  Else, if the constant fits in the IMMEDIATE field, then
1412 /// use that field.  Otherwise, else create instructions to put the constant
1413 /// into a register, either directly or by loading explicitly from the constant
1414 /// pool.  In the first 2 cases, the operand of `minstr' is modified in place.
1415 /// Returns a vector of machine instructions generated for operands that fall
1416 /// under case 3; these must be inserted before `minstr'.
1417 ///
1418 std::vector<MachineInstr*>
1419 FixConstantOperandsForInstr(Instruction* vmInstr, MachineInstr* minstr,
1420                             TargetMachine& target) {
1421   std::vector<MachineInstr*> MVec;
1422
1423   MachineOpCode opCode = minstr->getOpcode();
1424   const TargetInstrInfo& instrInfo = *target.getInstrInfo();
1425   int resultPos = instrInfo.get(opCode).resultPos;
1426   int immedPos = instrInfo.getImmedConstantPos(opCode);
1427
1428   Function *F = vmInstr->getParent()->getParent();
1429
1430   for (unsigned op=0; op < minstr->getNumOperands(); op++) {
1431       const MachineOperand& mop = minstr->getOperand(op);
1432
1433       // Skip the result position, preallocated machine registers, or operands
1434       // that cannot be constants (CC regs or PC-relative displacements)
1435       if (resultPos == (int)op ||
1436           mop.getType() == MachineOperand::MO_MachineRegister ||
1437           mop.getType() == MachineOperand::MO_CCRegister ||
1438           mop.getType() == MachineOperand::MO_PCRelativeDisp)
1439         continue;
1440
1441       bool constantThatMustBeLoaded = false;
1442       unsigned int machineRegNum = 0;
1443       int64_t immedValue = 0;
1444       Value* opValue = NULL;
1445       MachineOperand::MachineOperandType opType =
1446         MachineOperand::MO_VirtualRegister;
1447
1448       // Operand may be a virtual register or a compile-time constant
1449       if (mop.getType() == MachineOperand::MO_VirtualRegister) {
1450         assert(mop.getVRegValue() != NULL);
1451         opValue = mop.getVRegValue();
1452         if (Constant *opConst = dyn_cast<Constant>(opValue))
1453           if (!isa<GlobalValue>(opConst)) {
1454             opType = ChooseRegOrImmed(opConst, opCode, target,
1455                                       (immedPos == (int)op), machineRegNum,
1456                                       immedValue);
1457             if (opType == MachineOperand::MO_VirtualRegister)
1458               constantThatMustBeLoaded = true;
1459           }
1460       } else {
1461         // If the operand is from the constant pool, don't try to change it.
1462         if (mop.getType() == MachineOperand::MO_ConstantPoolIndex) {
1463           continue;
1464         }
1465         assert(mop.isImmediate());
1466         bool isSigned = mop.getType() == MachineOperand::MO_SignExtendedImmed;
1467
1468         // Bit-selection flags indicate an instruction that is extracting
1469         // bits from its operand so ignore this even if it is a big constant.
1470         if (mop.isHiBits32() || mop.isLoBits32() ||
1471             mop.isHiBits64() || mop.isLoBits64())
1472           continue;
1473
1474         opType = ChooseRegOrImmed(mop.getImmedValue(), isSigned,
1475                                   opCode, target, (immedPos == (int)op),
1476                                   machineRegNum, immedValue);
1477
1478         if (opType == MachineOperand::MO_SignExtendedImmed ||
1479             opType == MachineOperand::MO_UnextendedImmed) {
1480           // The optype is an immediate value
1481           // This means we need to change the opcode, e.g. ADDr -> ADDi
1482           unsigned newOpcode = convertOpcodeFromRegToImm(opCode);
1483           minstr->setOpcode(newOpcode);
1484         }
1485
1486         if (opType == mop.getType())
1487           continue;           // no change: this is the most common case
1488
1489         if (opType == MachineOperand::MO_VirtualRegister) {
1490           constantThatMustBeLoaded = true;
1491           opValue = isSigned
1492             ? (Value*)ConstantSInt::get(Type::LongTy, immedValue)
1493             : (Value*)ConstantUInt::get(Type::ULongTy,(uint64_t)immedValue);
1494         }
1495       }
1496
1497       if (opType == MachineOperand::MO_MachineRegister)
1498         minstr->SetMachineOperandReg(op, machineRegNum);
1499       else if (opType == MachineOperand::MO_SignExtendedImmed ||
1500                opType == MachineOperand::MO_UnextendedImmed) {
1501         minstr->SetMachineOperandConst(op, opType, immedValue);
1502         // The optype is or has become an immediate
1503         // This means we need to change the opcode, e.g. ADDr -> ADDi
1504         unsigned newOpcode = convertOpcodeFromRegToImm(opCode);
1505         minstr->setOpcode(newOpcode);
1506       } else if (constantThatMustBeLoaded ||
1507                (opValue && isa<GlobalValue>(opValue)))
1508         { // opValue is a constant that must be explicitly loaded into a reg
1509           assert(opValue);
1510           TmpInstruction* tmpReg = InsertCodeToLoadConstant(F, opValue, vmInstr,
1511                                                             MVec, target);
1512           minstr->SetMachineOperandVal(op, MachineOperand::MO_VirtualRegister,
1513                                        tmpReg);
1514         }
1515     }
1516
1517   // Also, check for implicit operands used by the machine instruction
1518   // (no need to check those defined since they cannot be constants).
1519   // These include:
1520   // -- arguments to a Call
1521   // -- return value of a Return
1522   // Any such operand that is a constant value needs to be fixed also.
1523   // The current instructions with implicit refs (viz., Call and Return)
1524   // have no immediate fields, so the constant always needs to be loaded
1525   // into a register.
1526   bool isCall = instrInfo.isCall(opCode);
1527   unsigned lastCallArgNum = 0;          // unused if not a call
1528   CallArgsDescriptor* argDesc = NULL;   // unused if not a call
1529   if (isCall)
1530     argDesc = CallArgsDescriptor::get(minstr);
1531
1532   for (unsigned i=0, N=minstr->getNumImplicitRefs(); i < N; ++i)
1533     if (isa<Constant>(minstr->getImplicitRef(i))) {
1534         Value* oldVal = minstr->getImplicitRef(i);
1535         TmpInstruction* tmpReg =
1536           InsertCodeToLoadConstant(F, oldVal, vmInstr, MVec, target);
1537         minstr->setImplicitRef(i, tmpReg);
1538
1539         if (isCall) {
1540           // find and replace the argument in the CallArgsDescriptor
1541           unsigned i=lastCallArgNum;
1542           while (argDesc->getArgInfo(i).getArgVal() != oldVal)
1543             ++i;
1544           assert(i < argDesc->getNumArgs() &&
1545                  "Constant operands to a call *must* be in the arg list");
1546           lastCallArgNum = i;
1547           argDesc->getArgInfo(i).replaceArgVal(tmpReg);
1548         }
1549       }
1550
1551   return MVec;
1552 }
1553
1554 static inline void Add3OperandInstr(unsigned Opcode, InstructionNode* Node,
1555                                     std::vector<MachineInstr*>& mvec) {
1556   mvec.push_back(BuildMI(Opcode, 3).addReg(Node->leftChild()->getValue())
1557                                    .addReg(Node->rightChild()->getValue())
1558                                    .addRegDef(Node->getValue()));
1559 }
1560
1561 /// IsZero - Check for a constant 0.
1562 ///
1563 static inline bool IsZero(Value* idx) {
1564   return (idx == ConstantSInt::getNullValue(idx->getType()));
1565 }
1566
1567 /// FoldGetElemChain - Fold a chain of GetElementPtr instructions containing
1568 /// only constant offsets into an equivalent (Pointer, IndexVector) pair.
1569 /// Returns the pointer Value, and stores the resulting IndexVector in argument
1570 /// chainIdxVec. This is a helper function for FoldConstantIndices that does the
1571 /// actual folding.
1572 //
1573 static Value*
1574 FoldGetElemChain(InstrTreeNode* ptrNode, std::vector<Value*>& chainIdxVec,
1575                  bool lastInstHasLeadingNonZero) {
1576   InstructionNode* gepNode = dyn_cast<InstructionNode>(ptrNode);
1577   GetElementPtrInst* gepInst =
1578     dyn_cast_or_null<GetElementPtrInst>(gepNode ? gepNode->getInstruction() :0);
1579
1580   // ptr value is not computed in this tree or ptr value does not come from GEP
1581   // instruction
1582   if (gepInst == NULL)
1583     return NULL;
1584
1585   // Return NULL if we don't fold any instructions in.
1586   Value* ptrVal = NULL;
1587
1588   // Now chase the chain of getElementInstr instructions, if any.
1589   // Check for any non-constant indices and stop there.
1590   // Also, stop if the first index of child is a non-zero array index
1591   // and the last index of the current node is a non-array index:
1592   // in that case, a non-array declared type is being accessed as an array
1593   // which is not type-safe, but could be legal.
1594   InstructionNode* ptrChild = gepNode;
1595   while (ptrChild && (ptrChild->getOpLabel() == Instruction::GetElementPtr ||
1596                       ptrChild->getOpLabel() == GetElemPtrIdx)) {
1597     // Child is a GetElemPtr instruction
1598     gepInst = cast<GetElementPtrInst>(ptrChild->getValue());
1599     User::op_iterator OI, firstIdx = gepInst->idx_begin();
1600     User::op_iterator lastIdx = gepInst->idx_end();
1601     bool allConstantOffsets = true;
1602
1603     // The first index of every GEP must be an array index.
1604     assert((*firstIdx)->getType() == Type::LongTy &&
1605            "INTERNAL ERROR: Structure index for a pointer type!");
1606
1607     // If the last instruction had a leading non-zero index, check if the
1608     // current one references a sequential (i.e., indexable) type.
1609     // If not, the code is not type-safe and we would create an illegal GEP
1610     // by folding them, so don't fold any more instructions.
1611     if (lastInstHasLeadingNonZero)
1612       if (! isa<SequentialType>(gepInst->getType()->getElementType()))
1613         break;   // cannot fold in any preceding getElementPtr instrs.
1614
1615     // Check that all offsets are constant for this instruction
1616     for (OI = firstIdx; allConstantOffsets && OI != lastIdx; ++OI)
1617       allConstantOffsets = isa<ConstantInt>(*OI);
1618
1619     if (allConstantOffsets) {
1620       // Get pointer value out of ptrChild.
1621       ptrVal = gepInst->getPointerOperand();
1622
1623       // Insert its index vector at the start, skipping any leading [0]
1624       // Remember the old size to check if anything was inserted.
1625       unsigned oldSize = chainIdxVec.size();
1626       int firstIsZero = IsZero(*firstIdx);
1627       chainIdxVec.insert(chainIdxVec.begin(), firstIdx + firstIsZero, lastIdx);
1628
1629       // Remember if it has leading zero index: it will be discarded later.
1630       if (oldSize < chainIdxVec.size())
1631         lastInstHasLeadingNonZero = !firstIsZero;
1632
1633       // Mark the folded node so no code is generated for it.
1634       ((InstructionNode*) ptrChild)->markFoldedIntoParent();
1635
1636       // Get the previous GEP instruction and continue trying to fold
1637       ptrChild = dyn_cast<InstructionNode>(ptrChild->leftChild());
1638     } else // cannot fold this getElementPtr instr. or any preceding ones
1639       break;
1640   }
1641
1642   // If the first getElementPtr instruction had a leading [0], add it back.
1643   // Note that this instruction is the *last* one that was successfully
1644   // folded *and* contributed any indices, in the loop above.
1645   if (ptrVal && ! lastInstHasLeadingNonZero)
1646     chainIdxVec.insert(chainIdxVec.begin(), ConstantSInt::get(Type::LongTy,0));
1647
1648   return ptrVal;
1649 }
1650
1651 /// GetGEPInstArgs - Helper function for GetMemInstArgs that handles the
1652 /// final getElementPtr instruction used by (or same as) the memory operation.
1653 /// Extracts the indices of the current instruction and tries to fold in
1654 /// preceding ones if all indices of the current one are constant.
1655 ///
1656 static Value *GetGEPInstArgs(InstructionNode *gepNode,
1657                              std::vector<Value *> &idxVec,
1658                              bool &allConstantIndices) {
1659   allConstantIndices = true;
1660   GetElementPtrInst* gepI = cast<GetElementPtrInst>(gepNode->getInstruction());
1661
1662   // Default pointer is the one from the current instruction.
1663   Value* ptrVal = gepI->getPointerOperand();
1664   InstrTreeNode* ptrChild = gepNode->leftChild();
1665
1666   // Extract the index vector of the GEP instruction.
1667   // If all indices are constant and first index is zero, try to fold
1668   // in preceding GEPs with all constant indices.
1669   for (User::op_iterator OI=gepI->idx_begin(),  OE=gepI->idx_end();
1670        allConstantIndices && OI != OE; ++OI)
1671     if (! isa<Constant>(*OI))
1672       allConstantIndices = false;     // note: this also terminates loop!
1673
1674   // If we have only constant indices, fold chains of constant indices
1675   // in this and any preceding GetElemPtr instructions.
1676   bool foldedGEPs = false;
1677   bool leadingNonZeroIdx = gepI && ! IsZero(*gepI->idx_begin());
1678   if (allConstantIndices)
1679     if (Value* newPtr = FoldGetElemChain(ptrChild, idxVec, leadingNonZeroIdx)) {
1680       ptrVal = newPtr;
1681       foldedGEPs = true;
1682     }
1683
1684   // Append the index vector of the current instruction.
1685   // Skip the leading [0] index if preceding GEPs were folded into this.
1686   idxVec.insert(idxVec.end(),
1687                 gepI->idx_begin() + (foldedGEPs && !leadingNonZeroIdx),
1688                 gepI->idx_end());
1689
1690   return ptrVal;
1691 }
1692
1693 /// GetMemInstArgs - Get the pointer value and the index vector for a memory
1694 /// operation (GetElementPtr, Load, or Store).  If all indices of the given
1695 /// memory operation are constant, fold in constant indices in a chain of
1696 /// preceding GetElementPtr instructions (if any), and return the pointer value
1697 /// of the first instruction in the chain. All folded instructions are marked so
1698 /// no code is generated for them. Returns the pointer Value to use, and
1699 /// returns the resulting IndexVector in idxVec. Sets allConstantIndices
1700 /// to true/false if all indices are/aren't const.
1701 ///
1702 static Value *GetMemInstArgs(InstructionNode *memInstrNode,
1703                              std::vector<Value*> &idxVec,
1704                              bool& allConstantIndices) {
1705   allConstantIndices = false;
1706   Instruction* memInst = memInstrNode->getInstruction();
1707   assert(idxVec.size() == 0 && "Need empty vector to return indices");
1708
1709   // If there is a GetElemPtr instruction to fold in to this instr,
1710   // it must be in the left child for Load and GetElemPtr, and in the
1711   // right child for Store instructions.
1712   InstrTreeNode* ptrChild = (memInst->getOpcode() == Instruction::Store
1713                              ? memInstrNode->rightChild()
1714                              : memInstrNode->leftChild());
1715
1716   // Default pointer is the one from the current instruction.
1717   Value* ptrVal = ptrChild->getValue();
1718
1719   // Find the "last" GetElemPtr instruction: this one or the immediate child.
1720   // There will be none if this is a load or a store from a scalar pointer.
1721   InstructionNode* gepNode = NULL;
1722   if (isa<GetElementPtrInst>(memInst))
1723     gepNode = memInstrNode;
1724   else if (isa<InstructionNode>(ptrChild) && isa<GetElementPtrInst>(ptrVal)) {
1725     // Child of load/store is a GEP and memInst is its only use.
1726     // Use its indices and mark it as folded.
1727     gepNode = cast<InstructionNode>(ptrChild);
1728     gepNode->markFoldedIntoParent();
1729   }
1730
1731   // If there are no indices, return the current pointer.
1732   // Else extract the pointer from the GEP and fold the indices.
1733   return gepNode ? GetGEPInstArgs(gepNode, idxVec, allConstantIndices)
1734                  : ptrVal;
1735 }
1736
1737 static inline MachineOpCode
1738 ChooseBprInstruction(const InstructionNode* instrNode) {
1739   MachineOpCode opCode;
1740
1741   Instruction* setCCInstr =
1742     ((InstructionNode*) instrNode->leftChild())->getInstruction();
1743
1744   switch(setCCInstr->getOpcode()) {
1745   case Instruction::SetEQ: opCode = V9::BRZ;   break;
1746   case Instruction::SetNE: opCode = V9::BRNZ;  break;
1747   case Instruction::SetLE: opCode = V9::BRLEZ; break;
1748   case Instruction::SetGE: opCode = V9::BRGEZ; break;
1749   case Instruction::SetLT: opCode = V9::BRLZ;  break;
1750   case Instruction::SetGT: opCode = V9::BRGZ;  break;
1751   default:
1752     assert(0 && "Unrecognized VM instruction!");
1753     opCode = V9::INVALID_OPCODE;
1754     break;
1755   }
1756
1757   return opCode;
1758 }
1759
1760 static inline MachineOpCode
1761 ChooseBpccInstruction(const InstructionNode* instrNode,
1762                       const BinaryOperator* setCCInstr) {
1763   MachineOpCode opCode = V9::INVALID_OPCODE;
1764
1765   bool isSigned = setCCInstr->getOperand(0)->getType()->isSigned();
1766
1767   if (isSigned) {
1768     switch(setCCInstr->getOpcode()) {
1769     case Instruction::SetEQ: opCode = V9::BE;  break;
1770     case Instruction::SetNE: opCode = V9::BNE; break;
1771     case Instruction::SetLE: opCode = V9::BLE; break;
1772     case Instruction::SetGE: opCode = V9::BGE; break;
1773     case Instruction::SetLT: opCode = V9::BL;  break;
1774     case Instruction::SetGT: opCode = V9::BG;  break;
1775     default:
1776       assert(0 && "Unrecognized VM instruction!");
1777       break;
1778     }
1779   } else {
1780     switch(setCCInstr->getOpcode()) {
1781     case Instruction::SetEQ: opCode = V9::BE;   break;
1782     case Instruction::SetNE: opCode = V9::BNE;  break;
1783     case Instruction::SetLE: opCode = V9::BLEU; break;
1784     case Instruction::SetGE: opCode = V9::BCC;  break;
1785     case Instruction::SetLT: opCode = V9::BCS;  break;
1786     case Instruction::SetGT: opCode = V9::BGU;  break;
1787     default:
1788       assert(0 && "Unrecognized VM instruction!");
1789       break;
1790     }
1791   }
1792
1793   return opCode;
1794 }
1795
1796 static inline MachineOpCode
1797 ChooseBFpccInstruction(const InstructionNode* instrNode,
1798                        const BinaryOperator* setCCInstr) {
1799   MachineOpCode opCode = V9::INVALID_OPCODE;
1800
1801   switch(setCCInstr->getOpcode()) {
1802   case Instruction::SetEQ: opCode = V9::FBE;  break;
1803   case Instruction::SetNE: opCode = V9::FBNE; break;
1804   case Instruction::SetLE: opCode = V9::FBLE; break;
1805   case Instruction::SetGE: opCode = V9::FBGE; break;
1806   case Instruction::SetLT: opCode = V9::FBL;  break;
1807   case Instruction::SetGT: opCode = V9::FBG;  break;
1808   default:
1809     assert(0 && "Unrecognized VM instruction!");
1810     break;
1811   }
1812
1813   return opCode;
1814 }
1815
1816 // GetTmpForCC - Create a unique TmpInstruction for a boolean value,
1817 // representing the CC register used by a branch on that value.
1818 // For now, hack this using a little static cache of TmpInstructions.
1819 // Eventually the entire BURG instruction selection should be put
1820 // into a separate class that can hold such information.
1821 // The static cache is not too bad because the memory for these
1822 // TmpInstructions will be freed along with the rest of the Function anyway.
1823 //
1824 static TmpInstruction *GetTmpForCC (Value* boolVal, const Function *F,
1825                                     const Type* ccType,
1826                                     MachineCodeForInstruction& mcfi) {
1827   typedef hash_map<const Value*, TmpInstruction*> BoolTmpCache;
1828   static BoolTmpCache boolToTmpCache;     // Map boolVal -> TmpInstruction*
1829   static const Function *lastFunction = 0;// Use to flush cache between funcs
1830
1831   assert(boolVal->getType() == Type::BoolTy && "Weird but ok! Delete assert");
1832
1833   if (lastFunction != F) {
1834     lastFunction = F;
1835     boolToTmpCache.clear();
1836   }
1837
1838   // Look for tmpI and create a new one otherwise.  The new value is
1839   // directly written to map using the ref returned by operator[].
1840   TmpInstruction*& tmpI = boolToTmpCache[boolVal];
1841   if (tmpI == NULL)
1842     tmpI = new TmpInstruction(mcfi, ccType, boolVal);
1843
1844   return tmpI;
1845 }
1846
1847 static inline MachineOpCode
1848 ChooseBccInstruction(const InstructionNode* instrNode, const Type*& setCCType) {
1849   InstructionNode* setCCNode = (InstructionNode*) instrNode->leftChild();
1850   assert(setCCNode->getOpLabel() == SetCCOp);
1851   BinaryOperator* setCCInstr =cast<BinaryOperator>(setCCNode->getInstruction());
1852   setCCType = setCCInstr->getOperand(0)->getType();
1853
1854   if (setCCType->isFloatingPoint())
1855     return ChooseBFpccInstruction(instrNode, setCCInstr);
1856   else
1857     return ChooseBpccInstruction(instrNode, setCCInstr);
1858 }
1859
1860 /// ChooseMovFpcciInstruction - WARNING: since this function has only one
1861 /// caller, it always returns the opcode that expects an immediate and a
1862 /// register. If this function is ever used in cases where an opcode that takes
1863 /// two registers is required, then modify this function and use
1864 /// convertOpcodeFromRegToImm() where required. It will be necessary to expand
1865 /// convertOpcodeFromRegToImm() to handle the new cases of opcodes.
1866 ///
1867 static inline MachineOpCode
1868 ChooseMovFpcciInstruction(const InstructionNode* instrNode) {
1869   MachineOpCode opCode = V9::INVALID_OPCODE;
1870
1871   switch(instrNode->getInstruction()->getOpcode()) {
1872   case Instruction::SetEQ: opCode = V9::MOVFEi;  break;
1873   case Instruction::SetNE: opCode = V9::MOVFNEi; break;
1874   case Instruction::SetLE: opCode = V9::MOVFLEi; break;
1875   case Instruction::SetGE: opCode = V9::MOVFGEi; break;
1876   case Instruction::SetLT: opCode = V9::MOVFLi;  break;
1877   case Instruction::SetGT: opCode = V9::MOVFGi;  break;
1878   default:
1879     assert(0 && "Unrecognized VM instruction!");
1880     break;
1881   }
1882
1883   return opCode;
1884 }
1885
1886 /// ChooseMovpcciForSetCC -- Choose a conditional-move instruction
1887 /// based on the type of SetCC operation.
1888 ///
1889 /// WARNING: like the previous function, this function always returns
1890 /// the opcode that expects an immediate and a register.  See above.
1891 ///
1892 static MachineOpCode ChooseMovpcciForSetCC(const InstructionNode* instrNode) {
1893   MachineOpCode opCode = V9::INVALID_OPCODE;
1894
1895   const Type* opType = instrNode->leftChild()->getValue()->getType();
1896   assert(opType->isIntegral() || isa<PointerType>(opType));
1897   bool noSign = opType->isUnsigned() || isa<PointerType>(opType);
1898
1899   switch(instrNode->getInstruction()->getOpcode()) {
1900   case Instruction::SetEQ: opCode = V9::MOVEi;                        break;
1901   case Instruction::SetLE: opCode = noSign? V9::MOVLEUi : V9::MOVLEi; break;
1902   case Instruction::SetGE: opCode = noSign? V9::MOVCCi  : V9::MOVGEi; break;
1903   case Instruction::SetLT: opCode = noSign? V9::MOVCSi  : V9::MOVLi;  break;
1904   case Instruction::SetGT: opCode = noSign? V9::MOVGUi  : V9::MOVGi;  break;
1905   case Instruction::SetNE: opCode = V9::MOVNEi;                       break;
1906   default: assert(0 && "Unrecognized LLVM instr!"); break;
1907   }
1908
1909   return opCode;
1910 }
1911
1912 /// ChooseMovpregiForSetCC -- Choose a conditional-move-on-register-value
1913 /// instruction based on the type of SetCC operation.  These instructions
1914 /// compare a register with 0 and perform the move is the comparison is true.
1915 ///
1916 /// WARNING: like the previous function, this function it always returns
1917 /// the opcode that expects an immediate and a register.  See above.
1918 ///
1919 static MachineOpCode ChooseMovpregiForSetCC(const InstructionNode* instrNode) {
1920   MachineOpCode opCode = V9::INVALID_OPCODE;
1921
1922   switch(instrNode->getInstruction()->getOpcode()) {
1923   case Instruction::SetEQ: opCode = V9::MOVRZi;  break;
1924   case Instruction::SetLE: opCode = V9::MOVRLEZi; break;
1925   case Instruction::SetGE: opCode = V9::MOVRGEZi; break;
1926   case Instruction::SetLT: opCode = V9::MOVRLZi;  break;
1927   case Instruction::SetGT: opCode = V9::MOVRGZi;  break;
1928   case Instruction::SetNE: opCode = V9::MOVRNZi; break;
1929   default: assert(0 && "Unrecognized VM instr!"); break;
1930   }
1931
1932   return opCode;
1933 }
1934
1935 static inline MachineOpCode
1936 ChooseConvertToFloatInstr(const TargetMachine& target,
1937                           OpLabel vopCode, const Type* opType) {
1938   assert((vopCode == ToFloatTy || vopCode == ToDoubleTy) &&
1939          "Unrecognized convert-to-float opcode!");
1940   assert((opType->isIntegral() || opType->isFloatingPoint() ||
1941           isa<PointerType>(opType))
1942          && "Trying to convert a non-scalar type to FLOAT/DOUBLE?");
1943
1944   MachineOpCode opCode = V9::INVALID_OPCODE;
1945
1946   unsigned opSize = target.getTargetData().getTypeSize(opType);
1947
1948   if (opType == Type::FloatTy)
1949     opCode = (vopCode == ToFloatTy? V9::NOP : V9::FSTOD);
1950   else if (opType == Type::DoubleTy)
1951     opCode = (vopCode == ToFloatTy? V9::FDTOS : V9::NOP);
1952   else if (opSize <= 4)
1953     opCode = (vopCode == ToFloatTy? V9::FITOS : V9::FITOD);
1954   else {
1955     assert(opSize == 8 && "Unrecognized type size > 4 and < 8!");
1956     opCode = (vopCode == ToFloatTy? V9::FXTOS : V9::FXTOD);
1957   }
1958
1959   return opCode;
1960 }
1961
1962 static inline MachineOpCode
1963 ChooseConvertFPToIntInstr(const TargetMachine& target,
1964                           const Type* destType, const Type* opType) {
1965   assert((opType == Type::FloatTy || opType == Type::DoubleTy)
1966          && "This function should only be called for FLOAT or DOUBLE");
1967   assert((destType->isIntegral() || isa<PointerType>(destType))
1968          && "Trying to convert FLOAT/DOUBLE to a non-scalar type?");
1969
1970   MachineOpCode opCode = V9::INVALID_OPCODE;
1971
1972   unsigned destSize = target.getTargetData().getTypeSize(destType);
1973
1974   if (destType == Type::UIntTy)
1975     assert(destType != Type::UIntTy && "Expand FP-to-uint beforehand.");
1976   else if (destSize <= 4)
1977     opCode = (opType == Type::FloatTy)? V9::FSTOI : V9::FDTOI;
1978   else {
1979     assert(destSize == 8 && "Unrecognized type size > 4 and < 8!");
1980     opCode = (opType == Type::FloatTy)? V9::FSTOX : V9::FDTOX;
1981   }
1982
1983   return opCode;
1984 }
1985
1986 static MachineInstr*
1987 CreateConvertFPToIntInstr(const TargetMachine& target, Value* srcVal,
1988                           Value* destVal, const Type* destType) {
1989   MachineOpCode opCode = ChooseConvertFPToIntInstr(target, destType,
1990                                                    srcVal->getType());
1991   assert(opCode != V9::INVALID_OPCODE && "Expected to need conversion!");
1992   return BuildMI(opCode, 2).addReg(srcVal).addRegDef(destVal);
1993 }
1994
1995 /// CreateCodeToConvertFloatToInt: Convert FP value to signed or unsigned
1996 /// integer.  The FP value must be converted to the dest type in an FP register,
1997 /// and the result is then copied from FP to int register via memory.  SPARC
1998 /// does not have a float-to-uint conversion, only a float-to-int (fdtoi).
1999 /// Since fdtoi converts to signed integers, any FP value V between MAXINT+1 and
2000 /// MAXUNSIGNED (i.e., 2^31 <= V <= 2^32-1) would be converted incorrectly.
2001 /// Therefore, for converting an FP value to uint32_t, we first need to convert
2002 /// to uint64_t and then to uint32_t.
2003 ///
2004 static void
2005 CreateCodeToConvertFloatToInt(const TargetMachine& target,
2006                               Value* opVal, Instruction* destI,
2007                               std::vector<MachineInstr*>& mvec,
2008                               MachineCodeForInstruction& mcfi) {
2009   Function* F = destI->getParent()->getParent();
2010
2011   // Create a temporary to represent the FP register into which the
2012   // int value will placed after conversion.  The type of this temporary
2013   // depends on the type of FP register to use: single-prec for a 32-bit
2014   // int or smaller; double-prec for a 64-bit int.
2015   size_t destSize = target.getTargetData().getTypeSize(destI->getType());
2016
2017   const Type* castDestType = destI->getType(); // type for the cast instr result
2018   const Type* castDestRegType;          // type for cast instruction result reg
2019   TmpInstruction* destForCast;          // dest for cast instruction
2020   Instruction* fpToIntCopyDest = destI; // dest for fp-reg-to-int-reg copy instr
2021
2022   // For converting an FP value to uint32_t, we first need to convert to
2023   // uint64_t and then to uint32_t, as explained above.
2024   if (destI->getType() == Type::UIntTy) {
2025     castDestType    = Type::ULongTy;       // use this instead of type of destI
2026     castDestRegType = Type::DoubleTy;      // uint64_t needs 64-bit FP register.
2027     destForCast     = new TmpInstruction(mcfi, castDestRegType, opVal);
2028     fpToIntCopyDest = new TmpInstruction(mcfi, castDestType, destForCast);
2029   } else {
2030     castDestRegType = (destSize > 4)? Type::DoubleTy : Type::FloatTy;
2031     destForCast = new TmpInstruction(mcfi, castDestRegType, opVal);
2032   }
2033
2034   // Create the fp-to-int conversion instruction (src and dest regs are FP regs)
2035   mvec.push_back(CreateConvertFPToIntInstr(target, opVal, destForCast,
2036                                            castDestType));
2037
2038   // Create the fpreg-to-intreg copy code
2039   CreateCodeToCopyFloatToInt(target, F, destForCast, fpToIntCopyDest, mvec,
2040                              mcfi);
2041
2042   // Create the uint64_t to uint32_t conversion, if needed
2043   if (destI->getType() == Type::UIntTy)
2044     CreateZeroExtensionInstructions(target, F, fpToIntCopyDest, destI,
2045                                     /*numLowBits*/ 32, mvec, mcfi);
2046 }
2047
2048 static inline MachineOpCode
2049 ChooseAddInstruction(const InstructionNode* instrNode) {
2050   return ChooseAddInstructionByType(instrNode->getInstruction()->getType());
2051 }
2052
2053 static inline MachineInstr*
2054 CreateMovFloatInstruction(const InstructionNode* instrNode,
2055                           const Type* resultType) {
2056   return BuildMI((resultType == Type::FloatTy) ? V9::FMOVS : V9::FMOVD, 2)
2057                    .addReg(instrNode->leftChild()->getValue())
2058                    .addRegDef(instrNode->getValue());
2059 }
2060
2061 static inline MachineInstr*
2062 CreateAddConstInstruction(const InstructionNode* instrNode) {
2063   MachineInstr* minstr = NULL;
2064
2065   Value* constOp = ((InstrTreeNode*) instrNode->rightChild())->getValue();
2066   assert(isa<Constant>(constOp));
2067
2068   // Cases worth optimizing are:
2069   // (1) Add with 0 for float or double: use an FMOV of appropriate type,
2070   //     instead of an FADD (1 vs 3 cycles).  There is no integer MOV.
2071   if (ConstantFP *FPC = dyn_cast<ConstantFP>(constOp)) {
2072     double dval = FPC->getValue();
2073     if (dval == 0.0)
2074       minstr = CreateMovFloatInstruction(instrNode,
2075                                         instrNode->getInstruction()->getType());
2076   }
2077
2078   return minstr;
2079 }
2080
2081 static inline MachineOpCode ChooseSubInstructionByType(const Type* resultType) {
2082   MachineOpCode opCode = V9::INVALID_OPCODE;
2083
2084   if (resultType->isInteger() || isa<PointerType>(resultType)) {
2085       opCode = V9::SUBr;
2086   } else {
2087     switch(resultType->getTypeID()) {
2088     case Type::FloatTyID:  opCode = V9::FSUBS; break;
2089     case Type::DoubleTyID: opCode = V9::FSUBD; break;
2090     default: assert(0 && "Invalid type for SUB instruction"); break;
2091     }
2092   }
2093
2094   return opCode;
2095 }
2096
2097 static inline MachineInstr*
2098 CreateSubConstInstruction(const InstructionNode* instrNode) {
2099   MachineInstr* minstr = NULL;
2100
2101   Value* constOp = ((InstrTreeNode*) instrNode->rightChild())->getValue();
2102   assert(isa<Constant>(constOp));
2103
2104   // Cases worth optimizing are:
2105   // (1) Sub with 0 for float or double: use an FMOV of appropriate type,
2106   //     instead of an FSUB (1 vs 3 cycles).  There is no integer MOV.
2107   if (ConstantFP *FPC = dyn_cast<ConstantFP>(constOp)) {
2108     double dval = FPC->getValue();
2109     if (dval == 0.0)
2110       minstr = CreateMovFloatInstruction(instrNode,
2111                                         instrNode->getInstruction()->getType());
2112   }
2113
2114   return minstr;
2115 }
2116
2117 static inline MachineOpCode
2118 ChooseFcmpInstruction(const InstructionNode* instrNode) {
2119   MachineOpCode opCode = V9::INVALID_OPCODE;
2120
2121   Value* operand = ((InstrTreeNode*) instrNode->leftChild())->getValue();
2122   switch(operand->getType()->getTypeID()) {
2123   case Type::FloatTyID:  opCode = V9::FCMPS; break;
2124   case Type::DoubleTyID: opCode = V9::FCMPD; break;
2125   default: assert(0 && "Invalid type for FCMP instruction"); break;
2126   }
2127
2128   return opCode;
2129 }
2130
2131 /// BothFloatToDouble - Assumes that leftArg and rightArg of instrNode are both
2132 /// cast instructions. Returns true if both are floats cast to double.
2133 ///
2134 static inline bool BothFloatToDouble(const InstructionNode* instrNode) {
2135   InstrTreeNode* leftArg = instrNode->leftChild();
2136   InstrTreeNode* rightArg = instrNode->rightChild();
2137   InstrTreeNode* leftArgArg = leftArg->leftChild();
2138   InstrTreeNode* rightArgArg = rightArg->leftChild();
2139   assert(leftArg->getValue()->getType() == rightArg->getValue()->getType());
2140   return (leftArg->getValue()->getType() == Type::DoubleTy &&
2141           leftArgArg->getValue()->getType() == Type::FloatTy &&
2142           rightArgArg->getValue()->getType() == Type::FloatTy);
2143 }
2144
2145 static inline MachineOpCode ChooseMulInstructionByType(const Type* resultType) {
2146   MachineOpCode opCode = V9::INVALID_OPCODE;
2147
2148   if (resultType->isInteger())
2149     opCode = V9::MULXr;
2150   else
2151     switch(resultType->getTypeID()) {
2152     case Type::FloatTyID:  opCode = V9::FMULS; break;
2153     case Type::DoubleTyID: opCode = V9::FMULD; break;
2154     default: assert(0 && "Invalid type for MUL instruction"); break;
2155     }
2156
2157   return opCode;
2158 }
2159
2160 static inline MachineInstr*
2161 CreateIntNegInstruction(const TargetMachine& target, Value* vreg) {
2162   return BuildMI(V9::SUBr, 3).addMReg(target.getRegInfo()->getZeroRegNum())
2163     .addReg(vreg).addRegDef(vreg);
2164 }
2165
2166 /// CreateShiftInstructions - Create instruction sequence for any shift
2167 /// operation. SLL or SLLX on an operand smaller than the integer reg. size
2168 /// (64bits) requires a second instruction for explicit sign-extension. Note
2169 /// that we only have to worry about a sign-bit appearing in the most
2170 /// significant bit of the operand after shifting (e.g., bit 32 of Int or bit 16
2171 /// of Short), so we do not have to worry about results that are as large as a
2172 /// normal integer register.
2173 ///
2174 static inline void
2175 CreateShiftInstructions(const TargetMachine& target, Function* F,
2176                         MachineOpCode shiftOpCode, Value* argVal1,
2177                         Value* optArgVal2, /* Use optArgVal2 if not NULL */
2178                         unsigned optShiftNum, /* else use optShiftNum */
2179                         Instruction* destVal, std::vector<MachineInstr*>& mvec,
2180                         MachineCodeForInstruction& mcfi) {
2181   assert((optArgVal2 != NULL || optShiftNum <= 64) &&
2182          "Large shift sizes unexpected, but can be handled below: "
2183          "You need to check whether or not it fits in immed field below");
2184
2185   // If this is a logical left shift of a type smaller than the standard
2186   // integer reg. size, we have to extend the sign-bit into upper bits
2187   // of dest, so we need to put the result of the SLL into a temporary.
2188   Value* shiftDest = destVal;
2189   unsigned opSize = target.getTargetData().getTypeSize(argVal1->getType());
2190
2191   if ((shiftOpCode == V9::SLLr5 || shiftOpCode == V9::SLLXr6) && opSize < 8) {
2192     // put SLL result into a temporary
2193     shiftDest = new TmpInstruction(mcfi, argVal1, optArgVal2, "sllTmp");
2194   }
2195
2196   MachineInstr* M = (optArgVal2 != NULL)
2197     ? BuildMI(shiftOpCode, 3).addReg(argVal1).addReg(optArgVal2)
2198                              .addReg(shiftDest, MachineOperand::Def)
2199     : BuildMI(shiftOpCode, 3).addReg(argVal1).addZImm(optShiftNum)
2200                              .addReg(shiftDest, MachineOperand::Def);
2201   mvec.push_back(M);
2202
2203   if (shiftDest != destVal) {
2204     // extend the sign-bit of the result into all upper bits of dest
2205     assert(8*opSize <= 32 && "Unexpected type size > 4 and < IntRegSize?");
2206     CreateSignExtensionInstructions(target, F, shiftDest, destVal, 8*opSize,
2207                                     mvec, mcfi);
2208   }
2209 }
2210
2211 /// CreateMulConstInstruction - Does not create any instructions if we
2212 /// cannot exploit constant to create a cheaper instruction. This returns the
2213 /// approximate cost of the instructions generated, which is used to pick the
2214 /// cheapest when both operands are constant.
2215 ///
2216 static unsigned
2217 CreateMulConstInstruction(const TargetMachine &target, Function* F,
2218                           Value* lval, Value* rval, Instruction* destVal,
2219                           std::vector<MachineInstr*>& mvec,
2220                           MachineCodeForInstruction& mcfi) {
2221   // Use max. multiply cost, viz., cost of MULX
2222   unsigned cost = target.getInstrInfo()->minLatency(V9::MULXr);
2223   unsigned firstNewInstr = mvec.size();
2224
2225   Value* constOp = rval;
2226   if (! isa<Constant>(constOp))
2227     return cost;
2228
2229   // Cases worth optimizing are:
2230   // (1) Multiply by 0 or 1 for any type: replace with copy (ADD or FMOV)
2231   // (2) Multiply by 2^x for integer types: replace with Shift
2232   const Type* resultType = destVal->getType();
2233
2234   if (resultType->isInteger() || isa<PointerType>(resultType)) {
2235     bool isValidConst;
2236     int64_t C = (int64_t) ConvertConstantToIntType(target, constOp,
2237                                                    constOp->getType(),
2238                                                    isValidConst);
2239     if (isValidConst) {
2240       unsigned pow;
2241       bool needNeg = false;
2242       if (C < 0) {
2243         needNeg = true;
2244         C = -C;
2245       }
2246
2247       if (C == 0 || C == 1) {
2248         cost = target.getInstrInfo()->minLatency(V9::ADDr);
2249         unsigned Zero = target.getRegInfo()->getZeroRegNum();
2250         MachineInstr* M;
2251         if (C == 0)
2252           M =BuildMI(V9::ADDr,3).addMReg(Zero).addMReg(Zero).addRegDef(destVal);
2253         else
2254           M = BuildMI(V9::ADDr,3).addReg(lval).addMReg(Zero).addRegDef(destVal);
2255         mvec.push_back(M);
2256       } else if (isPowerOf2(C, pow)) {
2257         unsigned opSize = target.getTargetData().getTypeSize(resultType);
2258         MachineOpCode opCode = (opSize <= 32)? V9::SLLr5 : V9::SLLXr6;
2259         CreateShiftInstructions(target, F, opCode, lval, NULL, pow,
2260                                 destVal, mvec, mcfi);
2261       }
2262
2263       if (mvec.size() > 0 && needNeg) {
2264         // insert <reg = SUB 0, reg> after the instr to flip the sign
2265         MachineInstr* M = CreateIntNegInstruction(target, destVal);
2266         mvec.push_back(M);
2267       }
2268     }
2269   } else {
2270     if (ConstantFP *FPC = dyn_cast<ConstantFP>(constOp)) {
2271       double dval = FPC->getValue();
2272       if (fabs(dval) == 1) {
2273         MachineOpCode opCode =  (dval < 0)
2274           ? (resultType == Type::FloatTy? V9::FNEGS : V9::FNEGD)
2275           : (resultType == Type::FloatTy? V9::FMOVS : V9::FMOVD);
2276         mvec.push_back(BuildMI(opCode,2).addReg(lval).addRegDef(destVal));
2277       }
2278     }
2279   }
2280
2281   if (firstNewInstr < mvec.size()) {
2282     cost = 0;
2283     for (unsigned i=firstNewInstr; i < mvec.size(); ++i)
2284       cost += target.getInstrInfo()->minLatency(mvec[i]->getOpcode());
2285   }
2286
2287   return cost;
2288 }
2289
2290 /// CreateCheapestMulConstInstruction - Does not create any instructions
2291 /// if we cannot exploit constant to create a cheaper instruction.
2292 ///
2293 static inline void
2294 CreateCheapestMulConstInstruction(const TargetMachine &target, Function* F,
2295                                   Value* lval, Value* rval,
2296                                   Instruction* destVal,
2297                                   std::vector<MachineInstr*>& mvec,
2298                                   MachineCodeForInstruction& mcfi) {
2299   Value* constOp;
2300   if (isa<Constant>(lval) && isa<Constant>(rval)) {
2301     // both operands are constant: evaluate and "set" in dest
2302     Constant* P = ConstantExpr::get(Instruction::Mul,
2303                                     cast<Constant>(lval),
2304                                     cast<Constant>(rval));
2305     CreateCodeToLoadConst (target, F, P, destVal, mvec, mcfi);
2306   }
2307   else if (isa<Constant>(rval))         // rval is constant, but not lval
2308     CreateMulConstInstruction(target, F, lval, rval, destVal, mvec, mcfi);
2309   else if (isa<Constant>(lval))         // lval is constant, but not rval
2310     CreateMulConstInstruction(target, F, lval, rval, destVal, mvec, mcfi);
2311
2312   // else neither is constant
2313   return;
2314 }
2315
2316 /// CreateMulInstruction - Returns NULL if we cannot exploit constant
2317 /// to create a cheaper instruction.
2318 ///
2319 static inline void
2320 CreateMulInstruction(const TargetMachine &target, Function* F,
2321                      Value* lval, Value* rval, Instruction* destVal,
2322                      std::vector<MachineInstr*>& mvec,
2323                      MachineCodeForInstruction& mcfi,
2324                      MachineOpCode forceMulOp = -1) {
2325   unsigned L = mvec.size();
2326   CreateCheapestMulConstInstruction(target,F, lval, rval, destVal, mvec, mcfi);
2327   if (mvec.size() == L) {
2328     // no instructions were added so create MUL reg, reg, reg.
2329     // Use FSMULD if both operands are actually floats cast to doubles.
2330     // Otherwise, use the default opcode for the appropriate type.
2331     MachineOpCode mulOp = ((forceMulOp != -1)
2332                            ? forceMulOp
2333                            : ChooseMulInstructionByType(destVal->getType()));
2334     mvec.push_back(BuildMI(mulOp, 3).addReg(lval).addReg(rval)
2335                    .addRegDef(destVal));
2336   }
2337 }
2338
2339 /// ChooseDivInstruction - Generate a divide instruction for Div or Rem.
2340 /// For Rem, this assumes that the operand type will be signed if the result
2341 /// type is signed.  This is correct because they must have the same sign.
2342 ///
2343 static inline MachineOpCode
2344 ChooseDivInstruction(TargetMachine &target, const InstructionNode* instrNode) {
2345   MachineOpCode opCode = V9::INVALID_OPCODE;
2346
2347   const Type* resultType = instrNode->getInstruction()->getType();
2348
2349   if (resultType->isInteger())
2350     opCode = resultType->isSigned()? V9::SDIVXr : V9::UDIVXr;
2351   else
2352     switch(resultType->getTypeID()) {
2353       case Type::FloatTyID:  opCode = V9::FDIVS; break;
2354       case Type::DoubleTyID: opCode = V9::FDIVD; break;
2355       default: assert(0 && "Invalid type for DIV instruction"); break;
2356       }
2357
2358   return opCode;
2359 }
2360
2361 /// CreateDivConstInstruction - Return if we cannot exploit constant to create
2362 /// a cheaper instruction.
2363 ///
2364 static void CreateDivConstInstruction(TargetMachine &target,
2365                                       const InstructionNode* instrNode,
2366                                       std::vector<MachineInstr*>& mvec) {
2367   Value* LHS  = instrNode->leftChild()->getValue();
2368   Value* constOp = ((InstrTreeNode*) instrNode->rightChild())->getValue();
2369   if (!isa<Constant>(constOp))
2370     return;
2371
2372   Instruction* destVal = instrNode->getInstruction();
2373   unsigned ZeroReg = target.getRegInfo()->getZeroRegNum();
2374
2375   // Cases worth optimizing are:
2376   // (1) Divide by 1 for any type: replace with copy (ADD or FMOV)
2377   // (2) Divide by 2^x for integer types: replace with SR[L or A]{X}
2378   const Type* resultType = instrNode->getInstruction()->getType();
2379
2380   if (resultType->isInteger()) {
2381     unsigned pow;
2382     bool isValidConst;
2383     int64_t C = (int64_t) ConvertConstantToIntType(target, constOp,
2384                                                    constOp->getType(),
2385                                                    isValidConst);
2386     if (isValidConst) {
2387       bool needNeg = false;
2388       if (C < 0) {
2389         needNeg = true;
2390         C = -C;
2391       }
2392
2393       if (C == 1) {
2394         mvec.push_back(BuildMI(V9::ADDr, 3).addReg(LHS).addMReg(ZeroReg)
2395                        .addRegDef(destVal));
2396       } else if (isPowerOf2(C, pow)) {
2397         unsigned opCode;
2398         Value* shiftOperand;
2399         unsigned opSize = target.getTargetData().getTypeSize(resultType);
2400
2401         if (resultType->isSigned()) {
2402           // For N / 2^k, if the operand N is negative,
2403           // we need to add (2^k - 1) before right-shifting by k, i.e.,
2404           //
2405           //    (N / 2^k) = N >> k,               if N >= 0;
2406           //                (N + 2^k - 1) >> k,   if N < 0
2407           //
2408           // If N is <= 32 bits, use:
2409           //    sra N, 31, t1           // t1 = ~0,         if N < 0,  0 else
2410           //    srl t1, 32-k, t2        // t2 = 2^k - 1,    if N < 0,  0 else
2411           //    add t2, N, t3           // t3 = N + 2^k -1, if N < 0,  N else
2412           //    sra t3, k, result       // result = N / 2^k
2413           //
2414           // If N is 64 bits, use:
2415           //    srax N,  k-1,  t1       // t1 = sign bit in high k positions
2416           //    srlx t1, 64-k, t2       // t2 = 2^k - 1,    if N < 0,  0 else
2417           //    add t2, N, t3           // t3 = N + 2^k -1, if N < 0,  N else
2418           //    sra t3, k, result       // result = N / 2^k
2419           TmpInstruction *sraTmp, *srlTmp, *addTmp;
2420           MachineCodeForInstruction& mcfi
2421             = MachineCodeForInstruction::get(destVal);
2422           sraTmp = new TmpInstruction(mcfi, resultType, LHS, 0, "getSign");
2423           srlTmp = new TmpInstruction(mcfi, resultType, LHS, 0, "getPlus2km1");
2424           addTmp = new TmpInstruction(mcfi, resultType, LHS, srlTmp,"incIfNeg");
2425
2426           // Create the SRA or SRAX instruction to get the sign bit
2427           mvec.push_back(BuildMI((opSize > 4)? V9::SRAXi6 : V9::SRAi5, 3)
2428                          .addReg(LHS)
2429                          .addSImm((resultType==Type::LongTy)? pow-1 : 31)
2430                          .addRegDef(sraTmp));
2431
2432           // Create the SRL or SRLX instruction to get the sign bit
2433           mvec.push_back(BuildMI((opSize > 4)? V9::SRLXi6 : V9::SRLi5, 3)
2434                          .addReg(sraTmp)
2435                          .addSImm((resultType==Type::LongTy)? 64-pow : 32-pow)
2436                          .addRegDef(srlTmp));
2437
2438           // Create the ADD instruction to add 2^pow-1 for negative values
2439           mvec.push_back(BuildMI(V9::ADDr, 3).addReg(LHS).addReg(srlTmp)
2440                          .addRegDef(addTmp));
2441
2442           // Get the shift operand and "right-shift" opcode to do the divide
2443           shiftOperand = addTmp;
2444           opCode = (opSize > 4)? V9::SRAXi6 : V9::SRAi5;
2445         } else {
2446           // Get the shift operand and "right-shift" opcode to do the divide
2447           shiftOperand = LHS;
2448           opCode = (opSize > 4)? V9::SRLXi6 : V9::SRLi5;
2449         }
2450
2451         // Now do the actual shift!
2452         mvec.push_back(BuildMI(opCode, 3).addReg(shiftOperand).addZImm(pow)
2453                        .addRegDef(destVal));
2454       }
2455
2456       if (needNeg && (C == 1 || isPowerOf2(C, pow))) {
2457         // insert <reg = SUB 0, reg> after the instr to flip the sign
2458         mvec.push_back(CreateIntNegInstruction(target, destVal));
2459       }
2460     }
2461   } else {
2462     if (ConstantFP *FPC = dyn_cast<ConstantFP>(constOp)) {
2463       double dval = FPC->getValue();
2464       if (fabs(dval) == 1) {
2465         unsigned opCode =
2466           (dval < 0) ? (resultType == Type::FloatTy? V9::FNEGS : V9::FNEGD)
2467           : (resultType == Type::FloatTy? V9::FMOVS : V9::FMOVD);
2468
2469         mvec.push_back(BuildMI(opCode, 2).addReg(LHS).addRegDef(destVal));
2470       }
2471     }
2472   }
2473 }
2474
2475 static void CreateCodeForVariableSizeAlloca(const TargetMachine& target,
2476                                             Instruction* result, unsigned tsize,
2477                                             Value* numElementsVal,
2478                                             std::vector<MachineInstr*>& getMvec)
2479 {
2480   Value* totalSizeVal;
2481   MachineInstr* M;
2482   MachineCodeForInstruction& mcfi = MachineCodeForInstruction::get(result);
2483   Function *F = result->getParent()->getParent();
2484
2485   // Enforce the alignment constraints on the stack pointer at
2486   // compile time if the total size is a known constant.
2487   if (isa<Constant>(numElementsVal)) {
2488     bool isValid;
2489     int64_t numElem = (int64_t)
2490       ConvertConstantToIntType(target, numElementsVal,
2491                                numElementsVal->getType(), isValid);
2492     assert(isValid && "Unexpectedly large array dimension in alloca!");
2493     int64_t total = numElem * tsize;
2494     if (int extra= total % SparcV9FrameInfo::StackFrameSizeAlignment)
2495       total += SparcV9FrameInfo::StackFrameSizeAlignment - extra;
2496     totalSizeVal = ConstantSInt::get(Type::IntTy, total);
2497   } else {
2498     // The size is not a constant.  Generate code to compute it and
2499     // code to pad the size for stack alignment.
2500     // Create a Value to hold the (constant) element size
2501     Value* tsizeVal = ConstantSInt::get(Type::IntTy, tsize);
2502
2503     // Create temporary values to hold the result of MUL, SLL, SRL
2504     // To pad `size' to next smallest multiple of 16:
2505     //          size = (size + 15) & (-16 = 0xfffffffffffffff0)
2506     TmpInstruction* tmpProd = new TmpInstruction(mcfi,numElementsVal, tsizeVal);
2507     TmpInstruction* tmpAdd15= new TmpInstruction(mcfi,numElementsVal, tmpProd);
2508     TmpInstruction* tmpAndf0= new TmpInstruction(mcfi,numElementsVal, tmpAdd15);
2509
2510     // Instruction 1: mul numElements, typeSize -> tmpProd
2511     // This will optimize the MUL as far as possible.
2512     CreateMulInstruction(target, F, numElementsVal, tsizeVal, tmpProd, getMvec,
2513                          mcfi, -1);
2514
2515     // Instruction 2: andn tmpProd, 0x0f -> tmpAndn
2516     getMvec.push_back(BuildMI(V9::ADDi, 3).addReg(tmpProd).addSImm(15)
2517                       .addReg(tmpAdd15, MachineOperand::Def));
2518
2519     // Instruction 3: add tmpAndn, 0x10 -> tmpAdd16
2520     getMvec.push_back(BuildMI(V9::ANDi, 3).addReg(tmpAdd15).addSImm(-16)
2521                       .addReg(tmpAndf0, MachineOperand::Def));
2522
2523     totalSizeVal = tmpAndf0;
2524   }
2525
2526   // Get the constant offset from SP for dynamically allocated storage
2527   // and create a temporary Value to hold it.
2528   MachineFunction& mcInfo = MachineFunction::get(F);
2529   bool growUp;
2530   ConstantSInt* dynamicAreaOffset =
2531     ConstantSInt::get(Type::IntTy,
2532                     target.getFrameInfo()->getDynamicAreaOffset(mcInfo,growUp));
2533   assert(! growUp && "Has SPARC v9 stack frame convention changed?");
2534
2535   unsigned SPReg = target.getRegInfo()->getStackPointer();
2536
2537   // Instruction 2: sub %sp, totalSizeVal -> %sp
2538   getMvec.push_back(BuildMI(V9::SUBr, 3).addMReg(SPReg).addReg(totalSizeVal)
2539                     .addMReg(SPReg,MachineOperand::Def));
2540
2541   // Instruction 3: add %sp, frameSizeBelowDynamicArea -> result
2542   getMvec.push_back(BuildMI(V9::ADDr,3).addMReg(SPReg).addReg(dynamicAreaOffset)
2543                     .addRegDef(result));
2544 }
2545
2546 static void
2547 CreateCodeForFixedSizeAlloca(const TargetMachine& target,
2548                              Instruction* result, unsigned tsize,
2549                              unsigned numElements,
2550                              std::vector<MachineInstr*>& getMvec) {
2551   assert(result && result->getParent() &&
2552          "Result value is not part of a function?");
2553   Function *F = result->getParent()->getParent();
2554   MachineFunction &mcInfo = MachineFunction::get(F);
2555
2556   // If the alloca is of zero bytes (which is perfectly legal) we bump it up to
2557   // one byte.  This is unnecessary, but I really don't want to break any
2558   // fragile logic in this code.  FIXME.
2559   if (tsize == 0)
2560     tsize = 1;
2561
2562   // Put the variable in the dynamically sized area of the frame if either:
2563   // (a) The offset is too large to use as an immediate in load/stores
2564   //     (check LDX because all load/stores have the same-size immed. field).
2565   // (b) The object is "large", so it could cause many other locals,
2566   //     spills, and temporaries to have large offsets.
2567   //     NOTE: We use LARGE = 8 * argSlotSize = 64 bytes.
2568   // You've gotta love having only 13 bits for constant offset values :-|.
2569   //
2570   unsigned paddedSize;
2571   int offsetFromFP = mcInfo.getInfo<SparcV9FunctionInfo>()->computeOffsetforLocalVar(result,
2572                                                                 paddedSize,
2573                                                          tsize * numElements);
2574
2575   if (((int)paddedSize) > 8 * SparcV9FrameInfo::SizeOfEachArgOnStack ||
2576       !target.getInstrInfo()->constantFitsInImmedField(V9::LDXi,offsetFromFP)) {
2577     CreateCodeForVariableSizeAlloca(target, result, tsize,
2578                                     ConstantSInt::get(Type::IntTy,numElements),
2579                                     getMvec);
2580     return;
2581   }
2582
2583   // else offset fits in immediate field so go ahead and allocate it.
2584   offsetFromFP = mcInfo.getInfo<SparcV9FunctionInfo>()->allocateLocalVar(result, tsize *numElements);
2585
2586   // Create a temporary Value to hold the constant offset.
2587   // This is needed because it may not fit in the immediate field.
2588   ConstantSInt* offsetVal = ConstantSInt::get(Type::IntTy, offsetFromFP);
2589
2590   // Instruction 1: add %fp, offsetFromFP -> result
2591   unsigned FPReg = target.getRegInfo()->getFramePointer();
2592   getMvec.push_back(BuildMI(V9::ADDr, 3).addMReg(FPReg).addReg(offsetVal)
2593                     .addRegDef(result));
2594 }
2595
2596 /// SetOperandsForMemInstr - Choose addressing mode for the given load or store
2597 /// instruction.  Use [reg+reg] if it is an indexed reference, and the index
2598 /// offset is not a constant or if it cannot fit in the offset field.  Use
2599 /// [reg+offset] in all other cases.  This assumes that all array refs are
2600 /// "lowered" to one of these forms:
2601 ///    %x = load (subarray*) ptr, constant      ; single constant offset
2602 ///    %x = load (subarray*) ptr, offsetVal     ; single non-constant offset
2603 /// Generally, this should happen via strength reduction + LICM.  Also, strength
2604 /// reduction should take care of using the same register for the loop index
2605 /// variable and an array index, when that is profitable.
2606 ///
2607 static void SetOperandsForMemInstr(unsigned Opcode,
2608                                    std::vector<MachineInstr*>& mvec,
2609                                    InstructionNode* vmInstrNode,
2610                                    const TargetMachine& target) {
2611   Instruction* memInst = vmInstrNode->getInstruction();
2612   // Index vector, ptr value, and flag if all indices are const.
2613   std::vector<Value*> idxVec;
2614   bool allConstantIndices;
2615   Value* ptrVal = GetMemInstArgs(vmInstrNode, idxVec, allConstantIndices);
2616
2617   // Now create the appropriate operands for the machine instruction.
2618   // First, initialize so we default to storing the offset in a register.
2619   int64_t smallConstOffset = 0;
2620   Value* valueForRegOffset = NULL;
2621   MachineOperand::MachineOperandType offsetOpType =
2622     MachineOperand::MO_VirtualRegister;
2623
2624   // Check if there is an index vector and if so, compute the
2625   // right offset for structures and for arrays
2626   if (!idxVec.empty()) {
2627     const PointerType* ptrType = cast<PointerType>(ptrVal->getType());
2628
2629     // If all indices are constant, compute the combined offset directly.
2630     if (allConstantIndices) {
2631       // Compute the offset value using the index vector. Create a
2632       // virtual reg. for it since it may not fit in the immed field.
2633       uint64_t offset = target.getTargetData().getIndexedOffset(ptrType,idxVec);
2634       valueForRegOffset = ConstantSInt::get(Type::LongTy, offset);
2635     } else {
2636       // There is at least one non-constant offset.  Therefore, this must
2637       // be an array ref, and must have been lowered to a single non-zero
2638       // offset.  (An extra leading zero offset, if any, can be ignored.)
2639       // Generate code sequence to compute address from index.
2640       bool firstIdxIsZero = IsZero(idxVec[0]);
2641       assert(idxVec.size() == 1U + firstIdxIsZero
2642              && "Array refs must be lowered before Instruction Selection");
2643
2644       Value* idxVal = idxVec[firstIdxIsZero];
2645
2646       std::vector<MachineInstr*> mulVec;
2647       Instruction* addr =
2648         new TmpInstruction(MachineCodeForInstruction::get(memInst),
2649                            Type::ULongTy, memInst);
2650
2651       // Get the array type indexed by idxVal, and compute its element size.
2652       // The call to getTypeSize() will fail if size is not constant.
2653       const Type* vecType = (firstIdxIsZero
2654                              ? GetElementPtrInst::getIndexedType(ptrType,
2655                                            std::vector<Value*>(1U, idxVec[0]),
2656                                            /*AllowCompositeLeaf*/ true)
2657                                  : ptrType);
2658       const Type* eltType = cast<SequentialType>(vecType)->getElementType();
2659       ConstantUInt* eltSizeVal = ConstantUInt::get(Type::ULongTy,
2660                                    target.getTargetData().getTypeSize(eltType));
2661
2662       // CreateMulInstruction() folds constants intelligently enough.
2663       CreateMulInstruction(target, memInst->getParent()->getParent(),
2664                            idxVal,         /* lval, not likely to be const*/
2665                            eltSizeVal,     /* rval, likely to be constant */
2666                            addr,           /* result */
2667                            mulVec, MachineCodeForInstruction::get(memInst),
2668                            -1);
2669
2670       assert(mulVec.size() > 0 && "No multiply code created?");
2671       mvec.insert(mvec.end(), mulVec.begin(), mulVec.end());
2672
2673       valueForRegOffset = addr;
2674     }
2675   } else {
2676     offsetOpType = MachineOperand::MO_SignExtendedImmed;
2677     smallConstOffset = 0;
2678   }
2679
2680   // For STORE:
2681   //   Operand 0 is value, operand 1 is ptr, operand 2 is offset
2682   // For LOAD or GET_ELEMENT_PTR,
2683   //   Operand 0 is ptr, operand 1 is offset, operand 2 is result.
2684   unsigned offsetOpNum, ptrOpNum;
2685   MachineInstr *MI;
2686   if (memInst->getOpcode() == Instruction::Store) {
2687     if (offsetOpType == MachineOperand::MO_VirtualRegister) {
2688       MI = BuildMI(Opcode, 3).addReg(vmInstrNode->leftChild()->getValue())
2689                              .addReg(ptrVal).addReg(valueForRegOffset);
2690     } else {
2691       Opcode = convertOpcodeFromRegToImm(Opcode);
2692       MI = BuildMI(Opcode, 3).addReg(vmInstrNode->leftChild()->getValue())
2693                              .addReg(ptrVal).addSImm(smallConstOffset);
2694     }
2695   } else {
2696     if (offsetOpType == MachineOperand::MO_VirtualRegister) {
2697       MI = BuildMI(Opcode, 3).addReg(ptrVal).addReg(valueForRegOffset)
2698                              .addRegDef(memInst);
2699     } else {
2700       Opcode = convertOpcodeFromRegToImm(Opcode);
2701       MI = BuildMI(Opcode, 3).addReg(ptrVal).addSImm(smallConstOffset)
2702                              .addRegDef(memInst);
2703     }
2704   }
2705   mvec.push_back(MI);
2706 }
2707
2708 /// ForwardOperand - Substitute operand `operandNum' of the instruction in
2709 /// node `treeNode' in place of the use(s) of that instruction in node `parent'.
2710 /// Check both explicit and implicit operands!  Also make sure to skip over a
2711 /// parent who: (1) is a list node in the Burg tree, or (2) itself had its
2712 /// results forwarded to its parent.
2713 ///
2714 static void ForwardOperand (InstructionNode *treeNode, InstrTreeNode *parent,
2715                             int operandNum) {
2716   assert(treeNode && parent && "Invalid invocation of ForwardOperand");
2717
2718   Instruction* unusedOp = treeNode->getInstruction();
2719   Value* fwdOp = unusedOp->getOperand(operandNum);
2720
2721   // The parent itself may be a list node, so find the real parent instruction
2722   while (parent->getNodeType() != InstrTreeNode::NTInstructionNode) {
2723     parent = parent->parent();
2724     assert(parent && "ERROR: Non-instruction node has no parent in tree.");
2725   }
2726   InstructionNode* parentInstrNode = (InstructionNode*) parent;
2727
2728   Instruction* userInstr = parentInstrNode->getInstruction();
2729   MachineCodeForInstruction &mvec = MachineCodeForInstruction::get(userInstr);
2730
2731   // The parent's mvec would be empty if it was itself forwarded.
2732   // Recursively call ForwardOperand in that case...
2733   //
2734   if (mvec.size() == 0) {
2735     assert(parent->parent() != NULL &&
2736            "Parent could not have been forwarded, yet has no instructions?");
2737     ForwardOperand(treeNode, parent->parent(), operandNum);
2738   } else {
2739     for (unsigned i=0, N=mvec.size(); i < N; i++) {
2740       MachineInstr* minstr = mvec[i];
2741       for (unsigned i=0, numOps=minstr->getNumOperands(); i < numOps; ++i) {
2742         const MachineOperand& mop = minstr->getOperand(i);
2743         if (mop.getType() == MachineOperand::MO_VirtualRegister &&
2744             mop.getVRegValue() == unusedOp) {
2745           minstr->SetMachineOperandVal(i, MachineOperand::MO_VirtualRegister,
2746                                        fwdOp);
2747         }
2748       }
2749
2750       for (unsigned i=0,numOps=minstr->getNumImplicitRefs(); i<numOps; ++i)
2751         if (minstr->getImplicitRef(i) == unusedOp)
2752           minstr->setImplicitRef(i, fwdOp);
2753     }
2754   }
2755 }
2756
2757 /// AllUsesAreBranches - Returns true if all the uses of I are
2758 /// Branch instructions, false otherwise.
2759 ///
2760 inline bool AllUsesAreBranches(const Instruction* I) {
2761   for (Value::use_const_iterator UI=I->use_begin(), UE=I->use_end();
2762        UI != UE; ++UI)
2763     if (! isa<TmpInstruction>(*UI)     // ignore tmp instructions here
2764         && cast<Instruction>(*UI)->getOpcode() != Instruction::Br)
2765       return false;
2766   return true;
2767 }
2768
2769 /// CodeGenIntrinsic - Generate code for any intrinsic that needs a special
2770 /// code sequence instead of a regular call.  If not that kind of intrinsic, do
2771 /// nothing. Returns true if code was generated, otherwise false.
2772 ///
2773 static bool CodeGenIntrinsic(Intrinsic::ID iid, CallInst &callInstr,
2774                              TargetMachine &target,
2775                              std::vector<MachineInstr*>& mvec) {
2776   switch (iid) {
2777   default:
2778     assert(0 && "Unknown intrinsic function call should have been lowered!");
2779   case Intrinsic::vastart: {
2780     // Get the address of the first incoming vararg argument on the stack
2781     Function* func = cast<Function>(callInstr.getParent()->getParent());
2782     int numFixedArgs   = func->getFunctionType()->getNumParams();
2783     int fpReg          = SparcV9::i6;
2784     int firstVarArgOff = numFixedArgs * 8 +
2785                          SparcV9FrameInfo::FirstIncomingArgOffsetFromFP;
2786     mvec.push_back(BuildMI(V9::ADDi, 3).addMReg(fpReg).addSImm(firstVarArgOff).
2787                    addRegDef(&callInstr));
2788     return true;
2789   }
2790
2791   case Intrinsic::vaend:
2792     return true;                        // no-op on SparcV9
2793
2794   case Intrinsic::vacopy:
2795     // Simple copy of current va_list (arg1) to new va_list (result)
2796     mvec.push_back(BuildMI(V9::ORr, 3).
2797                    addMReg(target.getRegInfo()->getZeroRegNum()).
2798                    addReg(callInstr.getOperand(1)).
2799                    addRegDef(&callInstr));
2800     return true;
2801   }
2802 }
2803
2804 /// ThisIsAChainRule - returns true if the given  BURG rule is a chain rule.
2805 ///
2806 extern bool ThisIsAChainRule(int eruleno) {
2807   switch(eruleno) {
2808     case 111:   // stmt:  reg
2809     case 123:
2810     case 124:
2811     case 125:
2812     case 126:
2813     case 127:
2814     case 128:
2815     case 129:
2816     case 130:
2817     case 131:
2818     case 132:
2819     case 133:
2820     case 155:
2821     case 221:
2822     case 222:
2823     case 241:
2824     case 242:
2825     case 243:
2826     case 244:
2827     case 245:
2828     case 321:
2829       return true; break;
2830
2831     default:
2832       return false; break;
2833     }
2834 }
2835
2836 /// GetInstructionsByRule - Choose machine instructions for the
2837 /// SPARC V9 according to the patterns chosen by the BURG-generated parser.
2838 /// This is where most of the work in the V9 instruction selector gets done.
2839 ///
2840 void GetInstructionsByRule(InstructionNode* subtreeRoot, int ruleForNode,
2841                            short* nts, TargetMachine &target,
2842                            std::vector<MachineInstr*>& mvec) {
2843   bool checkCast = false;               // initialize here to use fall-through
2844   bool maskUnsignedResult = false;
2845   int nextRule;
2846   int forwardOperandNum = -1;
2847   unsigned allocaSize = 0;
2848   MachineInstr* M, *M2;
2849   unsigned L;
2850   bool foldCase = false;
2851
2852   mvec.clear();
2853
2854   // If the code for this instruction was folded into the parent (user),
2855   // then do nothing!
2856   if (subtreeRoot->isFoldedIntoParent())
2857     return;
2858
2859   // Let's check for chain rules outside the switch so that we don't have
2860   // to duplicate the list of chain rule production numbers here again
2861   if (ThisIsAChainRule(ruleForNode)) {
2862     // Chain rules have a single nonterminal on the RHS.
2863     // Get the rule that matches the RHS non-terminal and use that instead.
2864     assert(nts[0] && ! nts[1]
2865            && "A chain rule should have only one RHS non-terminal!");
2866     nextRule = burm_rule(subtreeRoot->state, nts[0]);
2867     nts = burm_nts[nextRule];
2868     GetInstructionsByRule(subtreeRoot, nextRule, nts, target, mvec);
2869   } else {
2870     switch(ruleForNode) {
2871       case 1:   // stmt:   Ret
2872       case 2:   // stmt:   RetValue(reg)
2873       {         // NOTE: Prepass of register allocation is responsible
2874                 //       for moving return value to appropriate register.
2875                 // Copy the return value to the required return register.
2876                 // Mark the return Value as an implicit ref of the RET instr..
2877                 // Mark the return-address register as a hidden virtual reg.
2878                 // Finally put a NOP in the delay slot.
2879         ReturnInst *returnInstr=cast<ReturnInst>(subtreeRoot->getInstruction());
2880         Value* retVal = returnInstr->getReturnValue();
2881         MachineCodeForInstruction& mcfi =
2882           MachineCodeForInstruction::get(returnInstr);
2883
2884         // Create a hidden virtual reg to represent the return address register
2885         // used by the machine instruction but not represented in LLVM.
2886         Instruction* returnAddrTmp = new TmpInstruction(mcfi, returnInstr);
2887
2888         MachineInstr* retMI =
2889           BuildMI(V9::JMPLRETi, 3).addReg(returnAddrTmp).addSImm(8)
2890           .addMReg(target.getRegInfo()->getZeroRegNum(), MachineOperand::Def);
2891
2892         // If there is a value to return, we need to:
2893         // (a) Sign-extend the value if it is smaller than 8 bytes (reg size)
2894         // (b) Insert a copy to copy the return value to the appropriate reg.
2895         //     -- For FP values, create a FMOVS or FMOVD instruction
2896         //     -- For non-FP values, create an add-with-0 instruction
2897         if (retVal != NULL) {
2898           const SparcV9RegInfo& regInfo =
2899             (SparcV9RegInfo&) *target.getRegInfo();
2900           const Type* retType = retVal->getType();
2901           unsigned regClassID = regInfo.getRegClassIDOfType(retType);
2902           unsigned retRegNum = (retType->isFloatingPoint()
2903                                 ? (unsigned) SparcV9FloatRegClass::f0
2904                                 : (unsigned) SparcV9IntRegClass::i0);
2905           retRegNum = regInfo.getUnifiedRegNum(regClassID, retRegNum);
2906
2907           // Insert sign-extension instructions for small signed values.
2908           Value* retValToUse = retVal;
2909           if (retType->isIntegral() && retType->isSigned()) {
2910             unsigned retSize = target.getTargetData().getTypeSize(retType);
2911             if (retSize <= 4) {
2912               // Create a temporary virtual reg. to hold the sign-extension.
2913               retValToUse = new TmpInstruction(mcfi, retVal);
2914
2915               // Sign-extend retVal and put the result in the temporary reg.
2916               CreateSignExtensionInstructions
2917                 (target, returnInstr->getParent()->getParent(),
2918                  retVal, retValToUse, 8*retSize, mvec, mcfi);
2919             }
2920           }
2921
2922           // (b) Now, insert a copy to to the appropriate register:
2923           //     -- For FP values, create a FMOVS or FMOVD instruction
2924           //     -- For non-FP values, create an add-with-0 instruction
2925           // First, create a virtual register to represent the register and
2926           // mark this vreg as being an implicit operand of the ret MI.
2927           TmpInstruction* retVReg =
2928             new TmpInstruction(mcfi, retValToUse, NULL, "argReg");
2929
2930           retMI->addImplicitRef(retVReg);
2931
2932           if (retType->isFloatingPoint())
2933             M = (BuildMI(retType==Type::FloatTy? V9::FMOVS : V9::FMOVD, 2)
2934                  .addReg(retValToUse).addReg(retVReg, MachineOperand::Def));
2935           else
2936             M = (BuildMI(ChooseAddInstructionByType(retType), 3)
2937                  .addReg(retValToUse).addSImm((int64_t) 0)
2938                  .addReg(retVReg, MachineOperand::Def));
2939
2940           // Mark the operand with the register it should be assigned
2941           M->SetRegForOperand(M->getNumOperands()-1, retRegNum);
2942           retMI->SetRegForImplicitRef(retMI->getNumImplicitRefs()-1, retRegNum);
2943
2944           mvec.push_back(M);
2945         }
2946
2947         // Now insert the RET instruction and a NOP for the delay slot
2948         mvec.push_back(retMI);
2949         mvec.push_back(BuildMI(V9::NOP, 0));
2950
2951         break;
2952       }
2953
2954       case 3:   // stmt:   Store(reg,reg)
2955       case 4:   // stmt:   Store(reg,ptrreg)
2956         SetOperandsForMemInstr(ChooseStoreInstruction(
2957                         subtreeRoot->leftChild()->getValue()->getType()),
2958                                mvec, subtreeRoot, target);
2959         break;
2960
2961       case 5:   // stmt:   BrUncond
2962         {
2963           BranchInst *BI = cast<BranchInst>(subtreeRoot->getInstruction());
2964           mvec.push_back(BuildMI(V9::BA, 1).addPCDisp(BI->getSuccessor(0)));
2965
2966           // delay slot
2967           mvec.push_back(BuildMI(V9::NOP, 0));
2968           break;
2969         }
2970
2971       case 206: // stmt:   BrCond(setCCconst)
2972       { // setCCconst => boolean was computed with `%b = setCC type reg1 const'
2973         // If the constant is ZERO, we can use the branch-on-integer-register
2974         // instructions and avoid the SUBcc instruction entirely.
2975         // Otherwise this is just the same as case 5, so just fall through.
2976         //
2977         InstrTreeNode* constNode = subtreeRoot->leftChild()->rightChild();
2978         assert(constNode &&
2979                constNode->getNodeType() ==InstrTreeNode::NTConstNode);
2980         Constant *constVal = cast<Constant>(constNode->getValue());
2981         bool isValidConst;
2982
2983         if ((constVal->getType()->isInteger()
2984              || isa<PointerType>(constVal->getType()))
2985             && ConvertConstantToIntType(target,
2986                              constVal, constVal->getType(), isValidConst) == 0
2987             && isValidConst)
2988           {
2989             // That constant is a zero after all...
2990             // Use the left child of setCC as the first argument!
2991             // Mark the setCC node so that no code is generated for it.
2992             InstructionNode* setCCNode = (InstructionNode*)
2993                                          subtreeRoot->leftChild();
2994             assert(setCCNode->getOpLabel() == SetCCOp);
2995             setCCNode->markFoldedIntoParent();
2996
2997             BranchInst* brInst=cast<BranchInst>(subtreeRoot->getInstruction());
2998
2999             M = BuildMI(ChooseBprInstruction(subtreeRoot), 2)
3000                                 .addReg(setCCNode->leftChild()->getValue())
3001                                 .addPCDisp(brInst->getSuccessor(0));
3002             mvec.push_back(M);
3003
3004             // delay slot
3005             mvec.push_back(BuildMI(V9::NOP, 0));
3006
3007             // false branch
3008             mvec.push_back(BuildMI(V9::BA, 1)
3009                            .addPCDisp(brInst->getSuccessor(1)));
3010
3011             // delay slot
3012             mvec.push_back(BuildMI(V9::NOP, 0));
3013             break;
3014           }
3015         // ELSE FALL THROUGH
3016       }
3017
3018       case 6:   // stmt:   BrCond(setCC)
3019       { // bool => boolean was computed with SetCC.
3020         // The branch to use depends on whether it is FP, signed, or unsigned.
3021         // If it is an integer CC, we also need to find the unique
3022         // TmpInstruction representing that CC.
3023         //
3024         BranchInst* brInst = cast<BranchInst>(subtreeRoot->getInstruction());
3025         const Type* setCCType;
3026         unsigned Opcode = ChooseBccInstruction(subtreeRoot, setCCType);
3027         Value* ccValue = GetTmpForCC(subtreeRoot->leftChild()->getValue(),
3028                                      brInst->getParent()->getParent(),
3029                                      setCCType,
3030                                      MachineCodeForInstruction::get(brInst));
3031         M = BuildMI(Opcode, 2).addCCReg(ccValue)
3032                               .addPCDisp(brInst->getSuccessor(0));
3033         mvec.push_back(M);
3034
3035         // delay slot
3036         mvec.push_back(BuildMI(V9::NOP, 0));
3037
3038         // false branch
3039         mvec.push_back(BuildMI(V9::BA, 1).addPCDisp(brInst->getSuccessor(1)));
3040
3041         // delay slot
3042         mvec.push_back(BuildMI(V9::NOP, 0));
3043         break;
3044       }
3045
3046       case 208: // stmt:   BrCond(boolconst)
3047       {
3048         // boolconst => boolean is a constant; use BA to first or second label
3049         Constant* constVal =
3050           cast<Constant>(subtreeRoot->leftChild()->getValue());
3051         unsigned dest = cast<ConstantBool>(constVal)->getValue()? 0 : 1;
3052
3053         M = BuildMI(V9::BA, 1).addPCDisp(
3054           cast<BranchInst>(subtreeRoot->getInstruction())->getSuccessor(dest));
3055         mvec.push_back(M);
3056
3057         // delay slot
3058         mvec.push_back(BuildMI(V9::NOP, 0));
3059         break;
3060       }
3061
3062       case   8: // stmt:   BrCond(boolreg)
3063       { // boolreg   => boolean is recorded in an integer register.
3064         //              Use branch-on-integer-register instruction.
3065         //
3066         BranchInst *BI = cast<BranchInst>(subtreeRoot->getInstruction());
3067         M = BuildMI(V9::BRNZ, 2).addReg(subtreeRoot->leftChild()->getValue())
3068           .addPCDisp(BI->getSuccessor(0));
3069         mvec.push_back(M);
3070
3071         // delay slot
3072         mvec.push_back(BuildMI(V9::NOP, 0));
3073
3074         // false branch
3075         mvec.push_back(BuildMI(V9::BA, 1).addPCDisp(BI->getSuccessor(1)));
3076
3077         // delay slot
3078         mvec.push_back(BuildMI(V9::NOP, 0));
3079         break;
3080       }
3081
3082       case 9:   // stmt:   Switch(reg)
3083         assert(0 && "*** SWITCH instruction is not implemented yet.");
3084         break;
3085
3086       case 10:  // reg:   VRegList(reg, reg)
3087         assert(0 && "VRegList should never be the topmost non-chain rule");
3088         break;
3089
3090       case 21:  // bool:  Not(bool,reg): Compute with a conditional-move-on-reg
3091       { // First find the unary operand. It may be left or right, usually right.
3092         Instruction* notI = subtreeRoot->getInstruction();
3093         Value* notArg = BinaryOperator::getNotArgument(
3094                            cast<BinaryOperator>(subtreeRoot->getInstruction()));
3095         unsigned ZeroReg = target.getRegInfo()->getZeroRegNum();
3096
3097         // Unconditionally set register to 0
3098         mvec.push_back(BuildMI(V9::SETHI, 2).addZImm(0).addRegDef(notI));
3099
3100         // Now conditionally move 1 into the register.
3101         // Mark the register as a use (as well as a def) because the old
3102         // value will be retained if the condition is false.
3103         mvec.push_back(BuildMI(V9::MOVRZi, 3).addReg(notArg).addZImm(1)
3104                        .addReg(notI, MachineOperand::UseAndDef));
3105
3106         break;
3107       }
3108
3109       case 421: // reg:   BNot(reg,reg): Compute as reg = reg XOR-NOT 0
3110       { // First find the unary operand. It may be left or right, usually right.
3111         Value* notArg = BinaryOperator::getNotArgument(
3112                            cast<BinaryOperator>(subtreeRoot->getInstruction()));
3113         unsigned ZeroReg = target.getRegInfo()->getZeroRegNum();
3114         mvec.push_back(BuildMI(V9::XNORr, 3).addReg(notArg).addMReg(ZeroReg)
3115                                        .addRegDef(subtreeRoot->getValue()));
3116         break;
3117       }
3118
3119       case 322: // reg:   Not(tobool, reg):
3120         // Fold CAST-TO-BOOL with NOT by inverting the sense of cast-to-bool
3121         foldCase = true;
3122         // Just fall through!
3123
3124       case 22:  // reg:   ToBoolTy(reg):
3125       {
3126         Instruction* castI = subtreeRoot->getInstruction();
3127         Value* opVal = subtreeRoot->leftChild()->getValue();
3128         assert(opVal->getType()->isIntegral() ||
3129                isa<PointerType>(opVal->getType()));
3130
3131         // Unconditionally set register to 0
3132         mvec.push_back(BuildMI(V9::SETHI, 2).addZImm(0).addRegDef(castI));
3133
3134         // Now conditionally move 1 into the register.
3135         // Mark the register as a use (as well as a def) because the old
3136         // value will be retained if the condition is false.
3137         MachineOpCode opCode = foldCase? V9::MOVRZi : V9::MOVRNZi;
3138         mvec.push_back(BuildMI(opCode, 3).addReg(opVal).addZImm(1)
3139                        .addReg(castI, MachineOperand::UseAndDef));
3140
3141         break;
3142       }
3143
3144       case 23:  // reg:   ToUByteTy(reg)
3145       case 24:  // reg:   ToSByteTy(reg)
3146       case 25:  // reg:   ToUShortTy(reg)
3147       case 26:  // reg:   ToShortTy(reg)
3148       case 27:  // reg:   ToUIntTy(reg)
3149       case 28:  // reg:   ToIntTy(reg)
3150       case 29:  // reg:   ToULongTy(reg)
3151       case 30:  // reg:   ToLongTy(reg)
3152       {
3153         //======================================================================
3154         // Rules for integer conversions:
3155         //
3156         //--------
3157         // From ISO 1998 C++ Standard, Sec. 4.7:
3158         //
3159         // 2. If the destination type is unsigned, the resulting value is
3160         // the least unsigned integer congruent to the source integer
3161         // (modulo 2n where n is the number of bits used to represent the
3162         // unsigned type). [Note: In a two s complement representation,
3163         // this conversion is conceptual and there is no change in the
3164         // bit pattern (if there is no truncation). ]
3165         //
3166         // 3. If the destination type is signed, the value is unchanged if
3167         // it can be represented in the destination type (and bitfield width);
3168         // otherwise, the value is implementation-defined.
3169         //--------
3170         //
3171         // Since we assume 2s complement representations, this implies:
3172         //
3173         // -- If operand is smaller than destination, zero-extend or sign-extend
3174         //    according to the signedness of the *operand*: source decides:
3175         //    (1) If operand is signed, sign-extend it.
3176         //        If dest is unsigned, zero-ext the result!
3177         //    (2) If operand is unsigned, our current invariant is that
3178         //        it's high bits are correct, so zero-extension is not needed.
3179         //
3180         // -- If operand is same size as or larger than destination,
3181         //    zero-extend or sign-extend according to the signedness of
3182         //    the *destination*: destination decides:
3183         //    (1) If destination is signed, sign-extend (truncating if needed)
3184         //        This choice is implementation defined.  We sign-extend the
3185         //        operand, which matches both Sun's cc and gcc3.2.
3186         //    (2) If destination is unsigned, zero-extend (truncating if needed)
3187         //======================================================================
3188
3189         Instruction* destI =  subtreeRoot->getInstruction();
3190         Function* currentFunc = destI->getParent()->getParent();
3191         MachineCodeForInstruction& mcfi=MachineCodeForInstruction::get(destI);
3192
3193         Value* opVal = subtreeRoot->leftChild()->getValue();
3194         const Type* opType = opVal->getType();
3195         const Type* destType = destI->getType();
3196         unsigned opSize   = target.getTargetData().getTypeSize(opType);
3197         unsigned destSize = target.getTargetData().getTypeSize(destType);
3198
3199         bool isIntegral = opType->isIntegral() || isa<PointerType>(opType);
3200
3201         if (opType == Type::BoolTy ||
3202             opType == destType ||
3203             isIntegral && opSize == destSize && opSize == 8) {
3204           // nothing to do in all these cases
3205           forwardOperandNum = 0;          // forward first operand to user
3206
3207         } else if (opType->isFloatingPoint()) {
3208
3209           CreateCodeToConvertFloatToInt(target, opVal, destI, mvec, mcfi);
3210           if (destI->getType()->isUnsigned() && destI->getType() !=Type::UIntTy)
3211             maskUnsignedResult = true; // not handled by fp->int code
3212
3213         } else if (isIntegral) {
3214
3215           bool opSigned     = opType->isSigned();
3216           bool destSigned   = destType->isSigned();
3217           unsigned extSourceInBits = 8 * std::min<unsigned>(opSize, destSize);
3218
3219           assert(! (opSize == destSize && opSigned == destSigned) &&
3220                  "How can different int types have same size and signedness?");
3221
3222           bool signExtend = (opSize <  destSize && opSigned ||
3223                              opSize >= destSize && destSigned);
3224
3225           bool signAndZeroExtend = (opSize < destSize && destSize < 8u &&
3226                                     opSigned && !destSigned);
3227           assert(!signAndZeroExtend || signExtend);
3228
3229           bool zeroExtendOnly = opSize >= destSize && !destSigned;
3230           assert(!zeroExtendOnly || !signExtend);
3231
3232           if (signExtend) {
3233             Value* signExtDest = (signAndZeroExtend
3234                                   ? new TmpInstruction(mcfi, destType, opVal)
3235                                   : destI);
3236
3237             CreateSignExtensionInstructions
3238               (target, currentFunc,opVal,signExtDest,extSourceInBits,mvec,mcfi);
3239
3240             if (signAndZeroExtend)
3241               CreateZeroExtensionInstructions
3242               (target, currentFunc, signExtDest, destI, 8*destSize, mvec, mcfi);
3243           }
3244           else if (zeroExtendOnly) {
3245             CreateZeroExtensionInstructions
3246               (target, currentFunc, opVal, destI, extSourceInBits, mvec, mcfi);
3247           }
3248           else
3249             forwardOperandNum = 0;          // forward first operand to user
3250
3251         } else
3252           assert(0 && "Unrecognized operand type for convert-to-integer");
3253
3254         break;
3255       }
3256
3257       case  31: // reg:   ToFloatTy(reg):
3258       case  32: // reg:   ToDoubleTy(reg):
3259       case 232: // reg:   ToDoubleTy(Constant):
3260
3261         // If this instruction has a parent (a user) in the tree
3262         // and the user is translated as an FsMULd instruction,
3263         // then the cast is unnecessary.  So check that first.
3264         // In the future, we'll want to do the same for the FdMULq instruction,
3265         // so do the check here instead of only for ToFloatTy(reg).
3266         //
3267         if (subtreeRoot->parent() != NULL) {
3268           const MachineCodeForInstruction& mcfi =
3269             MachineCodeForInstruction::get(
3270                 cast<InstructionNode>(subtreeRoot->parent())->getInstruction());
3271           if (mcfi.size() == 0 || mcfi.front()->getOpcode() == V9::FSMULD)
3272             forwardOperandNum = 0;    // forward first operand to user
3273         }
3274
3275         if (forwardOperandNum != 0) {    // we do need the cast
3276           Value* leftVal = subtreeRoot->leftChild()->getValue();
3277           const Type* opType = leftVal->getType();
3278           MachineOpCode opCode=ChooseConvertToFloatInstr(target,
3279                                        subtreeRoot->getOpLabel(), opType);
3280           if (opCode == V9::NOP) {      // no conversion needed
3281             forwardOperandNum = 0;      // forward first operand to user
3282           } else {
3283             // If the source operand is a non-FP type it must be
3284             // first copied from int to float register via memory!
3285             Instruction *dest = subtreeRoot->getInstruction();
3286             Value* srcForCast;
3287             int n = 0;
3288             if (! opType->isFloatingPoint()) {
3289               // Create a temporary to represent the FP register
3290               // into which the integer will be copied via memory.
3291               // The type of this temporary will determine the FP
3292               // register used: single-prec for a 32-bit int or smaller,
3293               // double-prec for a 64-bit int.
3294               //
3295               uint64_t srcSize =
3296                 target.getTargetData().getTypeSize(leftVal->getType());
3297               Type* tmpTypeToUse =
3298                 (srcSize <= 4)? Type::FloatTy : Type::DoubleTy;
3299               MachineCodeForInstruction &destMCFI =
3300                 MachineCodeForInstruction::get(dest);
3301               srcForCast = new TmpInstruction(destMCFI, tmpTypeToUse, dest);
3302
3303               CreateCodeToCopyIntToFloat(target,
3304                          dest->getParent()->getParent(),
3305                          leftVal, cast<Instruction>(srcForCast),
3306                          mvec, destMCFI);
3307             } else
3308               srcForCast = leftVal;
3309
3310             M = BuildMI(opCode, 2).addReg(srcForCast).addRegDef(dest);
3311             mvec.push_back(M);
3312           }
3313         }
3314         break;
3315
3316       case 19:  // reg:   ToArrayTy(reg):
3317       case 20:  // reg:   ToPointerTy(reg):
3318         forwardOperandNum = 0;          // forward first operand to user
3319         break;
3320
3321       case 233: // reg:   Add(reg, Constant)
3322         maskUnsignedResult = true;
3323         M = CreateAddConstInstruction(subtreeRoot);
3324         if (M != NULL) {
3325           mvec.push_back(M);
3326           break;
3327         }
3328         // ELSE FALL THROUGH
3329
3330       case 33:  // reg:   Add(reg, reg)
3331         maskUnsignedResult = true;
3332         Add3OperandInstr(ChooseAddInstruction(subtreeRoot), subtreeRoot, mvec);
3333         break;
3334
3335       case 234: // reg:   Sub(reg, Constant)
3336         maskUnsignedResult = true;
3337         M = CreateSubConstInstruction(subtreeRoot);
3338         if (M != NULL) {
3339           mvec.push_back(M);
3340           break;
3341         }
3342         // ELSE FALL THROUGH
3343
3344       case 34:  // reg:   Sub(reg, reg)
3345         maskUnsignedResult = true;
3346         Add3OperandInstr(ChooseSubInstructionByType(
3347                                    subtreeRoot->getInstruction()->getType()),
3348                          subtreeRoot, mvec);
3349         break;
3350
3351       case 135: // reg:   Mul(todouble, todouble)
3352         checkCast = true;
3353         // FALL THROUGH
3354
3355       case 35:  // reg:   Mul(reg, reg)
3356       {
3357         maskUnsignedResult = true;
3358         MachineOpCode forceOp = ((checkCast && BothFloatToDouble(subtreeRoot))
3359                                  ? (MachineOpCode)V9::FSMULD
3360                                  : -1);
3361         Instruction* mulInstr = subtreeRoot->getInstruction();
3362         CreateMulInstruction(target, mulInstr->getParent()->getParent(),
3363                              subtreeRoot->leftChild()->getValue(),
3364                              subtreeRoot->rightChild()->getValue(),
3365                              mulInstr, mvec,
3366                              MachineCodeForInstruction::get(mulInstr),forceOp);
3367         break;
3368       }
3369       case 335: // reg:   Mul(todouble, todoubleConst)
3370         checkCast = true;
3371         // FALL THROUGH
3372
3373       case 235: // reg:   Mul(reg, Constant)
3374       {
3375         maskUnsignedResult = true;
3376         MachineOpCode forceOp = ((checkCast && BothFloatToDouble(subtreeRoot))
3377                                  ? (MachineOpCode)V9::FSMULD
3378                                  : -1);
3379         Instruction* mulInstr = subtreeRoot->getInstruction();
3380         CreateMulInstruction(target, mulInstr->getParent()->getParent(),
3381                              subtreeRoot->leftChild()->getValue(),
3382                              subtreeRoot->rightChild()->getValue(),
3383                              mulInstr, mvec,
3384                              MachineCodeForInstruction::get(mulInstr),
3385                              forceOp);
3386         break;
3387       }
3388       case 236: // reg:   Div(reg, Constant)
3389         maskUnsignedResult = true;
3390         L = mvec.size();
3391         CreateDivConstInstruction(target, subtreeRoot, mvec);
3392         if (mvec.size() > L)
3393           break;
3394         // ELSE FALL THROUGH
3395
3396       case 36:  // reg:   Div(reg, reg)
3397       {
3398         maskUnsignedResult = true;
3399
3400         // If either operand of divide is smaller than 64 bits, we have
3401         // to make sure the unused top bits are correct because they affect
3402         // the result.  These bits are already correct for unsigned values.
3403         // They may be incorrect for signed values, so sign extend to fill in.
3404         Instruction* divI = subtreeRoot->getInstruction();
3405         Value* divOp1 = subtreeRoot->leftChild()->getValue();
3406         Value* divOp2 = subtreeRoot->rightChild()->getValue();
3407         Value* divOp1ToUse = divOp1;
3408         Value* divOp2ToUse = divOp2;
3409         if (divI->getType()->isSigned()) {
3410           unsigned opSize=target.getTargetData().getTypeSize(divI->getType());
3411           if (opSize < 8) {
3412             MachineCodeForInstruction& mcfi=MachineCodeForInstruction::get(divI);
3413             divOp1ToUse = new TmpInstruction(mcfi, divOp1);
3414             divOp2ToUse = new TmpInstruction(mcfi, divOp2);
3415             CreateSignExtensionInstructions(target,
3416                                               divI->getParent()->getParent(),
3417                                               divOp1, divOp1ToUse,
3418                                               8*opSize, mvec, mcfi);
3419             CreateSignExtensionInstructions(target,
3420                                               divI->getParent()->getParent(),
3421                                               divOp2, divOp2ToUse,
3422                                               8*opSize, mvec, mcfi);
3423           }
3424         }
3425
3426         mvec.push_back(BuildMI(ChooseDivInstruction(target, subtreeRoot), 3)
3427                        .addReg(divOp1ToUse)
3428                        .addReg(divOp2ToUse)
3429                        .addRegDef(divI));
3430
3431         break;
3432       }
3433
3434       case  37: // reg:   Rem(reg, reg)
3435       case 237: // reg:   Rem(reg, Constant)
3436       {
3437         maskUnsignedResult = true;
3438
3439         Instruction* remI   = subtreeRoot->getInstruction();
3440         Value* divOp1 = subtreeRoot->leftChild()->getValue();
3441         Value* divOp2 = subtreeRoot->rightChild()->getValue();
3442
3443         MachineCodeForInstruction& mcfi = MachineCodeForInstruction::get(remI);
3444
3445         // If second operand of divide is smaller than 64 bits, we have
3446         // to make sure the unused top bits are correct because they affect
3447         // the result.  These bits are already correct for unsigned values.
3448         // They may be incorrect for signed values, so sign extend to fill in.
3449         //
3450         Value* divOpToUse = divOp2;
3451         if (divOp2->getType()->isSigned()) {
3452           unsigned opSize=target.getTargetData().getTypeSize(divOp2->getType());
3453           if (opSize < 8) {
3454             divOpToUse = new TmpInstruction(mcfi, divOp2);
3455             CreateSignExtensionInstructions(target,
3456                                               remI->getParent()->getParent(),
3457                                               divOp2, divOpToUse,
3458                                               8*opSize, mvec, mcfi);
3459           }
3460         }
3461
3462         // Now compute: result = rem V1, V2 as:
3463         //      result = V1 - (V1 / signExtend(V2)) * signExtend(V2)
3464         //
3465         TmpInstruction* quot = new TmpInstruction(mcfi, divOp1, divOpToUse);
3466         TmpInstruction* prod = new TmpInstruction(mcfi, quot, divOpToUse);
3467
3468         mvec.push_back(BuildMI(ChooseDivInstruction(target, subtreeRoot), 3)
3469                        .addReg(divOp1).addReg(divOpToUse).addRegDef(quot));
3470
3471         mvec.push_back(BuildMI(ChooseMulInstructionByType(remI->getType()), 3)
3472                        .addReg(quot).addReg(divOpToUse).addRegDef(prod));
3473
3474         mvec.push_back(BuildMI(ChooseSubInstructionByType(remI->getType()), 3)
3475                        .addReg(divOp1).addReg(prod).addRegDef(remI));
3476
3477         break;
3478       }
3479
3480       case  38: // bool:   And(bool, bool)
3481       case 138: // bool:   And(bool, not)
3482       case 238: // bool:   And(bool, boolconst)
3483       case 338: // reg :   BAnd(reg, reg)
3484       case 538: // reg :   BAnd(reg, Constant)
3485         Add3OperandInstr(V9::ANDr, subtreeRoot, mvec);
3486         break;
3487
3488       case 438: // bool:   BAnd(bool, bnot)
3489       { // Use the argument of NOT as the second argument!
3490         // Mark the NOT node so that no code is generated for it.
3491         // If the type is boolean, set 1 or 0 in the result register.
3492         InstructionNode* notNode = (InstructionNode*) subtreeRoot->rightChild();
3493         Value* notArg = BinaryOperator::getNotArgument(
3494                            cast<BinaryOperator>(notNode->getInstruction()));
3495         notNode->markFoldedIntoParent();
3496         Value *lhs = subtreeRoot->leftChild()->getValue();
3497         Value *dest = subtreeRoot->getValue();
3498         mvec.push_back(BuildMI(V9::ANDNr, 3).addReg(lhs).addReg(notArg)
3499                                        .addReg(dest, MachineOperand::Def));
3500
3501         if (notArg->getType() == Type::BoolTy) {
3502           // set 1 in result register if result of above is non-zero
3503           mvec.push_back(BuildMI(V9::MOVRNZi, 3).addReg(dest).addZImm(1)
3504                          .addReg(dest, MachineOperand::UseAndDef));
3505         }
3506
3507         break;
3508       }
3509
3510       case  39: // bool:   Or(bool, bool)
3511       case 139: // bool:   Or(bool, not)
3512       case 239: // bool:   Or(bool, boolconst)
3513       case 339: // reg :   BOr(reg, reg)
3514       case 539: // reg :   BOr(reg, Constant)
3515         Add3OperandInstr(V9::ORr, subtreeRoot, mvec);
3516         break;
3517
3518       case 439: // bool:   BOr(bool, bnot)
3519       { // Use the argument of NOT as the second argument!
3520         // Mark the NOT node so that no code is generated for it.
3521         // If the type is boolean, set 1 or 0 in the result register.
3522         InstructionNode* notNode = (InstructionNode*) subtreeRoot->rightChild();
3523         Value* notArg = BinaryOperator::getNotArgument(
3524                            cast<BinaryOperator>(notNode->getInstruction()));
3525         notNode->markFoldedIntoParent();
3526         Value *lhs = subtreeRoot->leftChild()->getValue();
3527         Value *dest = subtreeRoot->getValue();
3528
3529         mvec.push_back(BuildMI(V9::ORNr, 3).addReg(lhs).addReg(notArg)
3530                        .addReg(dest, MachineOperand::Def));
3531
3532         if (notArg->getType() == Type::BoolTy) {
3533           // set 1 in result register if result of above is non-zero
3534           mvec.push_back(BuildMI(V9::MOVRNZi, 3).addReg(dest).addZImm(1)
3535                          .addReg(dest, MachineOperand::UseAndDef));
3536         }
3537
3538         break;
3539       }
3540
3541       case  40: // bool:   Xor(bool, bool)
3542       case 140: // bool:   Xor(bool, not)
3543       case 240: // bool:   Xor(bool, boolconst)
3544       case 340: // reg :   BXor(reg, reg)
3545       case 540: // reg :   BXor(reg, Constant)
3546         Add3OperandInstr(V9::XORr, subtreeRoot, mvec);
3547         break;
3548
3549       case 440: // bool:   BXor(bool, bnot)
3550       { // Use the argument of NOT as the second argument!
3551         // Mark the NOT node so that no code is generated for it.
3552         // If the type is boolean, set 1 or 0 in the result register.
3553         InstructionNode* notNode = (InstructionNode*) subtreeRoot->rightChild();
3554         Value* notArg = BinaryOperator::getNotArgument(
3555                            cast<BinaryOperator>(notNode->getInstruction()));
3556         notNode->markFoldedIntoParent();
3557         Value *lhs = subtreeRoot->leftChild()->getValue();
3558         Value *dest = subtreeRoot->getValue();
3559         mvec.push_back(BuildMI(V9::XNORr, 3).addReg(lhs).addReg(notArg)
3560                        .addReg(dest, MachineOperand::Def));
3561
3562         if (notArg->getType() == Type::BoolTy) {
3563           // set 1 in result register if result of above is non-zero
3564           mvec.push_back(BuildMI(V9::MOVRNZi, 3).addReg(dest).addZImm(1)
3565                          .addReg(dest, MachineOperand::UseAndDef));
3566         }
3567         break;
3568       }
3569
3570       case 41:  // setCCconst:   SetCC(reg, Constant)
3571       { // Comparison is with a constant:
3572         //
3573         // If the bool result must be computed into a register (see below),
3574         // and the constant is int ZERO, we can use the MOVR[op] instructions
3575         // and avoid the SUBcc instruction entirely.
3576         // Otherwise this is just the same as case 42, so just fall through.
3577         //
3578         // The result of the SetCC must be computed and stored in a register if
3579         // it is used outside the current basic block (so it must be computed
3580         // as a boolreg) or it is used by anything other than a branch.
3581         // We will use a conditional move to do this.
3582         //
3583         Instruction* setCCInstr = subtreeRoot->getInstruction();
3584         bool computeBoolVal = (subtreeRoot->parent() == NULL ||
3585                                ! AllUsesAreBranches(setCCInstr));
3586
3587         if (computeBoolVal) {
3588           InstrTreeNode* constNode = subtreeRoot->rightChild();
3589           assert(constNode &&
3590                  constNode->getNodeType() ==InstrTreeNode::NTConstNode);
3591           Constant *constVal = cast<Constant>(constNode->getValue());
3592           bool isValidConst;
3593
3594           if ((constVal->getType()->isInteger()
3595                || isa<PointerType>(constVal->getType()))
3596               && ConvertConstantToIntType(target,
3597                              constVal, constVal->getType(), isValidConst) == 0
3598               && isValidConst)
3599           {
3600             // That constant is an integer zero after all...
3601             // Use a MOVR[op] to compute the boolean result
3602             // Unconditionally set register to 0
3603             mvec.push_back(BuildMI(V9::SETHI, 2).addZImm(0)
3604                            .addRegDef(setCCInstr));
3605
3606             // Now conditionally move 1 into the register.
3607             // Mark the register as a use (as well as a def) because the old
3608             // value will be retained if the condition is false.
3609             MachineOpCode movOpCode = ChooseMovpregiForSetCC(subtreeRoot);
3610             mvec.push_back(BuildMI(movOpCode, 3)
3611                            .addReg(subtreeRoot->leftChild()->getValue())
3612                            .addZImm(1)
3613                            .addReg(setCCInstr, MachineOperand::UseAndDef));
3614
3615             break;
3616           }
3617         }
3618         // ELSE FALL THROUGH
3619       }
3620
3621       case 42:  // bool:   SetCC(reg, reg):
3622       {
3623         // This generates a SUBCC instruction, putting the difference in a
3624         // result reg. if needed, and/or setting a condition code if needed.
3625         //
3626         Instruction* setCCInstr = subtreeRoot->getInstruction();
3627         Value* leftVal  = subtreeRoot->leftChild()->getValue();
3628         Value* rightVal = subtreeRoot->rightChild()->getValue();
3629         const Type* opType = leftVal->getType();
3630         bool isFPCompare = opType->isFloatingPoint();
3631
3632         // If the boolean result of the SetCC is used outside the current basic
3633         // block (so it must be computed as a boolreg) or is used by anything
3634         // other than a branch, the boolean must be computed and stored
3635         // in a result register.  We will use a conditional move to do this.
3636         //
3637         bool computeBoolVal = (subtreeRoot->parent() == NULL ||
3638                                ! AllUsesAreBranches(setCCInstr));
3639
3640         // A TmpInstruction is created to represent the CC "result".
3641         // Unlike other instances of TmpInstruction, this one is used
3642         // by machine code of multiple LLVM instructions, viz.,
3643         // the SetCC and the branch.  Make sure to get the same one!
3644         // Note that we do this even for FP CC registers even though they
3645         // are explicit operands, because the type of the operand
3646         // needs to be a floating point condition code, not an integer
3647         // condition code.  Think of this as casting the bool result to
3648         // a FP condition code register.
3649         // Later, we mark the 4th operand as being a CC register, and as a def.
3650         //
3651         TmpInstruction* tmpForCC = GetTmpForCC(setCCInstr,
3652                                     setCCInstr->getParent()->getParent(),
3653                                     leftVal->getType(),
3654                                     MachineCodeForInstruction::get(setCCInstr));
3655
3656         // If the operands are signed values smaller than 4 bytes, then they
3657         // must be sign-extended in order to do a valid 32-bit comparison
3658         // and get the right result in the 32-bit CC register (%icc).
3659         //
3660         Value* leftOpToUse  = leftVal;
3661         Value* rightOpToUse = rightVal;
3662         if (opType->isIntegral() && opType->isSigned()) {
3663           unsigned opSize = target.getTargetData().getTypeSize(opType);
3664           if (opSize < 4) {
3665             MachineCodeForInstruction& mcfi =
3666               MachineCodeForInstruction::get(setCCInstr);
3667
3668             // create temporary virtual regs. to hold the sign-extensions
3669             leftOpToUse  = new TmpInstruction(mcfi, leftVal);
3670             rightOpToUse = new TmpInstruction(mcfi, rightVal);
3671
3672             // sign-extend each operand and put the result in the temporary reg.
3673             CreateSignExtensionInstructions
3674               (target, setCCInstr->getParent()->getParent(),
3675                leftVal, leftOpToUse, 8*opSize, mvec, mcfi);
3676             CreateSignExtensionInstructions
3677               (target, setCCInstr->getParent()->getParent(),
3678                rightVal, rightOpToUse, 8*opSize, mvec, mcfi);
3679           }
3680         }
3681
3682         if (! isFPCompare) {
3683           // Integer condition: set CC and discard result.
3684           mvec.push_back(BuildMI(V9::SUBccr, 4)
3685                          .addReg(leftOpToUse)
3686                          .addReg(rightOpToUse)
3687                          .addMReg(target.getRegInfo()->
3688                                    getZeroRegNum(), MachineOperand::Def)
3689                          .addCCReg(tmpForCC, MachineOperand::Def));
3690         } else {
3691           // FP condition: dest of FCMP should be some FCCn register
3692           mvec.push_back(BuildMI(ChooseFcmpInstruction(subtreeRoot), 3)
3693                          .addCCReg(tmpForCC, MachineOperand::Def)
3694                          .addReg(leftOpToUse)
3695                          .addReg(rightOpToUse));
3696         }
3697
3698         if (computeBoolVal) {
3699           MachineOpCode movOpCode = (isFPCompare
3700                                      ? ChooseMovFpcciInstruction(subtreeRoot)
3701                                      : ChooseMovpcciForSetCC(subtreeRoot));
3702
3703           // Unconditionally set register to 0
3704           M = BuildMI(V9::SETHI, 2).addZImm(0).addRegDef(setCCInstr);
3705           mvec.push_back(M);
3706
3707           // Now conditionally move 1 into the register.
3708           // Mark the register as a use (as well as a def) because the old
3709           // value will be retained if the condition is false.
3710           M = (BuildMI(movOpCode, 3).addCCReg(tmpForCC).addZImm(1)
3711                .addReg(setCCInstr, MachineOperand::UseAndDef));
3712           mvec.push_back(M);
3713         }
3714         break;
3715       }
3716
3717       case 51:  // reg:   Load(reg)
3718       case 52:  // reg:   Load(ptrreg)
3719         SetOperandsForMemInstr(ChooseLoadInstruction(
3720                                    subtreeRoot->getValue()->getType()),
3721                                mvec, subtreeRoot, target);
3722         break;
3723
3724       case 55:  // reg:   GetElemPtr(reg)
3725       case 56:  // reg:   GetElemPtrIdx(reg,reg)
3726         // If the GetElemPtr was folded into the user (parent), it will be
3727         // caught above.  For other cases, we have to compute the address.
3728         SetOperandsForMemInstr(V9::ADDr, mvec, subtreeRoot, target);
3729         break;
3730
3731       case 57:  // reg:  Alloca: Implement as 1 instruction:
3732       {         //          add %fp, offsetFromFP -> result
3733         AllocationInst* instr =
3734           cast<AllocationInst>(subtreeRoot->getInstruction());
3735         unsigned tsize =
3736           target.getTargetData().getTypeSize(instr->getAllocatedType());
3737         assert(tsize != 0);
3738         CreateCodeForFixedSizeAlloca(target, instr, tsize, 1, mvec);
3739         break;
3740       }
3741
3742       case 58:  // reg:   Alloca(reg): Implement as 3 instructions:
3743                 //      mul num, typeSz -> tmp
3744                 //      sub %sp, tmp    -> %sp
3745       {         //      add %sp, frameSizeBelowDynamicArea -> result
3746         AllocationInst* instr =
3747           cast<AllocationInst>(subtreeRoot->getInstruction());
3748         const Type* eltType = instr->getAllocatedType();
3749
3750         // If #elements is constant, use simpler code for fixed-size allocas
3751         int tsize = (int) target.getTargetData().getTypeSize(eltType);
3752         Value* numElementsVal = NULL;
3753         bool isArray = instr->isArrayAllocation();
3754
3755         if (!isArray || isa<Constant>(numElementsVal = instr->getArraySize())) {
3756           // total size is constant: generate code for fixed-size alloca
3757           unsigned numElements = isArray?
3758             cast<ConstantUInt>(numElementsVal)->getValue() : 1;
3759           CreateCodeForFixedSizeAlloca(target, instr, tsize,
3760                                        numElements, mvec);
3761         } else {
3762           // total size is not constant.
3763           CreateCodeForVariableSizeAlloca(target, instr, tsize,
3764                                           numElementsVal, mvec);
3765         }
3766         break;
3767       }
3768
3769       case 61:  // reg:   Call
3770       {         // Generate a direct (CALL) or indirect (JMPL) call.
3771                 // Mark the return-address register, the indirection
3772                 // register (for indirect calls), the operands of the Call,
3773                 // and the return value (if any) as implicit operands
3774                 // of the machine instruction.
3775                 //
3776                 // If this is a varargs function, floating point arguments
3777                 // have to passed in integer registers so insert
3778                 // copy-float-to-int instructions for each float operand.
3779                 //
3780         CallInst *callInstr = cast<CallInst>(subtreeRoot->getInstruction());
3781         Value *callee = callInstr->getCalledValue();
3782         Function* calledFunc = dyn_cast<Function>(callee);
3783
3784         // Check if this is an intrinsic function that needs a special code
3785         // sequence (e.g., va_start).  Indirect calls cannot be special.
3786         //
3787         bool specialIntrinsic = false;
3788         Intrinsic::ID iid;
3789         if (calledFunc && (iid=(Intrinsic::ID)calledFunc->getIntrinsicID()))
3790           specialIntrinsic = CodeGenIntrinsic(iid, *callInstr, target, mvec);
3791
3792         // If not, generate the normal call sequence for the function.
3793         // This can also handle any intrinsics that are just function calls.
3794         //
3795         if (! specialIntrinsic) {
3796           Function* currentFunc = callInstr->getParent()->getParent();
3797           MachineFunction& MF = MachineFunction::get(currentFunc);
3798           MachineCodeForInstruction& mcfi =
3799             MachineCodeForInstruction::get(callInstr);
3800           const SparcV9RegInfo& regInfo =
3801             (SparcV9RegInfo&) *target.getRegInfo();
3802           const TargetFrameInfo& frameInfo = *target.getFrameInfo();
3803
3804           // Create hidden virtual register for return address with type void*
3805           TmpInstruction* retAddrReg =
3806             new TmpInstruction(mcfi, PointerType::get(Type::VoidTy), callInstr);
3807
3808           // Generate the machine instruction and its operands.
3809           // Use CALL for direct function calls; this optimistically assumes
3810           // the PC-relative address fits in the CALL address field (22 bits).
3811           // Use JMPL for indirect calls.
3812           // This will be added to mvec later, after operand copies.
3813           //
3814           MachineInstr* callMI;
3815           if (calledFunc)             // direct function call
3816             callMI = BuildMI(V9::CALL, 1).addPCDisp(callee);
3817           else                        // indirect function call
3818             callMI = (BuildMI(V9::JMPLCALLi,3).addReg(callee)
3819                       .addSImm((int64_t)0).addRegDef(retAddrReg));
3820
3821           const FunctionType* funcType =
3822             cast<FunctionType>(cast<PointerType>(callee->getType())
3823                                ->getElementType());
3824           bool isVarArgs = funcType->isVarArg();
3825           bool noPrototype = isVarArgs && funcType->getNumParams() == 0;
3826
3827           // Use a descriptor to pass information about call arguments
3828           // to the register allocator.  This descriptor will be "owned"
3829           // and freed automatically when the MachineCodeForInstruction
3830           // object for the callInstr goes away.
3831           CallArgsDescriptor* argDesc =
3832             new CallArgsDescriptor(callInstr, retAddrReg,isVarArgs,noPrototype);
3833           assert(callInstr->getOperand(0) == callee
3834                  && "This is assumed in the loop below!");
3835
3836           // Insert sign-extension instructions for small signed values,
3837           // if this is an unknown function (i.e., called via a funcptr)
3838           // or an external one (i.e., which may not be compiled by llc).
3839           //
3840           if (calledFunc == NULL || calledFunc->isExternal()) {
3841             for (unsigned i=1, N=callInstr->getNumOperands(); i < N; ++i) {
3842               Value* argVal = callInstr->getOperand(i);
3843               const Type* argType = argVal->getType();
3844               if (argType->isIntegral() && argType->isSigned()) {
3845                 unsigned argSize = target.getTargetData().getTypeSize(argType);
3846                 if (argSize <= 4) {
3847                   // create a temporary virtual reg. to hold the sign-extension
3848                   TmpInstruction* argExtend = new TmpInstruction(mcfi, argVal);
3849
3850                   // sign-extend argVal and put the result in the temporary reg.
3851                   CreateSignExtensionInstructions
3852                     (target, currentFunc, argVal, argExtend,
3853                      8*argSize, mvec, mcfi);
3854
3855                   // replace argVal with argExtend in CallArgsDescriptor
3856                   argDesc->getArgInfo(i-1).replaceArgVal(argExtend);
3857                 }
3858               }
3859             }
3860           }
3861
3862           // Insert copy instructions to get all the arguments into
3863           // all the places that they need to be.
3864           //
3865           for (unsigned i=1, N=callInstr->getNumOperands(); i < N; ++i) {
3866             int argNo = i-1;
3867             CallArgInfo& argInfo = argDesc->getArgInfo(argNo);
3868             Value* argVal = argInfo.getArgVal(); // don't use callInstr arg here
3869             const Type* argType = argVal->getType();
3870             unsigned regType = regInfo.getRegTypeForDataType(argType);
3871             unsigned argSize = target.getTargetData().getTypeSize(argType);
3872             int regNumForArg = SparcV9RegInfo::getInvalidRegNum();
3873             unsigned regClassIDOfArgReg;
3874
3875             // Check for FP arguments to varargs functions.
3876             // Any such argument in the first $K$ args must be passed in an
3877             // integer register.  If there is no prototype, it must also
3878             // be passed as an FP register.
3879             // K = #integer argument registers.
3880             bool isFPArg = argVal->getType()->isFloatingPoint();
3881             if (isVarArgs && isFPArg) {
3882
3883               if (noPrototype) {
3884                 // It is a function with no prototype: pass value
3885                 // as an FP value as well as a varargs value.  The FP value
3886                 // may go in a register or on the stack.  The copy instruction
3887                 // to the outgoing reg/stack is created by the normal argument
3888                 // handling code since this is the "normal" passing mode.
3889                 //
3890                 regNumForArg = regInfo.regNumForFPArg(regType,
3891                                                       false, false, argNo,
3892                                                       regClassIDOfArgReg);
3893                 if (regNumForArg == regInfo.getInvalidRegNum())
3894                   argInfo.setUseStackSlot();
3895                 else
3896                   argInfo.setUseFPArgReg();
3897               }
3898
3899               // If this arg. is in the first $K$ regs, add special copy-
3900               // float-to-int instructions to pass the value as an int.
3901               // To check if it is in the first $K$, get the register
3902               // number for the arg #i.  These copy instructions are
3903               // generated here because they are extra cases and not needed
3904               // for the normal argument handling (some code reuse is
3905               // possible though -- later).
3906               //
3907               int copyRegNum = regInfo.regNumForIntArg(false, false, argNo,
3908                                                        regClassIDOfArgReg);
3909               if (copyRegNum != regInfo.getInvalidRegNum()) {
3910                 // Create a virtual register to represent copyReg. Mark
3911                 // this vreg as being an implicit operand of the call MI
3912                 const Type* loadTy = (argType == Type::FloatTy
3913                                       ? Type::IntTy : Type::LongTy);
3914                 TmpInstruction* argVReg = new TmpInstruction(mcfi, loadTy,
3915                                                              argVal, NULL,
3916                                                              "argRegCopy");
3917                 callMI->addImplicitRef(argVReg);
3918
3919                 // Get a temp stack location to use to copy
3920                 // float-to-int via the stack.
3921                 //
3922                 // FIXME: For now, we allocate permanent space because
3923                 // the stack frame manager does not allow locals to be
3924                 // allocated (e.g., for alloca) after a temp is
3925                 // allocated!
3926                 //
3927                 // int tmpOffset = MF.getInfo<SparcV9FunctionInfo>()->pushTempValue(argSize);
3928                 int tmpOffset = MF.getInfo<SparcV9FunctionInfo>()->allocateLocalVar(argVReg);
3929
3930                 // Generate the store from FP reg to stack
3931                 unsigned StoreOpcode = ChooseStoreInstruction(argType);
3932                 M = BuildMI(convertOpcodeFromRegToImm(StoreOpcode), 3)
3933                   .addReg(argVal).addMReg(regInfo.getFramePointer())
3934                   .addSImm(tmpOffset);
3935                 mvec.push_back(M);
3936
3937                 // Generate the load from stack to int arg reg
3938                 unsigned LoadOpcode = ChooseLoadInstruction(loadTy);
3939                 M = BuildMI(convertOpcodeFromRegToImm(LoadOpcode), 3)
3940                   .addMReg(regInfo.getFramePointer()).addSImm(tmpOffset)
3941                   .addReg(argVReg, MachineOperand::Def);
3942
3943                 // Mark operand with register it should be assigned
3944                 // both for copy and for the callMI
3945                 M->SetRegForOperand(M->getNumOperands()-1, copyRegNum);
3946                 callMI->SetRegForImplicitRef(callMI->getNumImplicitRefs()-1,
3947                                              copyRegNum);
3948                 mvec.push_back(M);
3949
3950                 // Add info about the argument to the CallArgsDescriptor
3951                 argInfo.setUseIntArgReg();
3952                 argInfo.setArgCopy(copyRegNum);
3953               } else {
3954                 // Cannot fit in first $K$ regs so pass arg on stack
3955                 argInfo.setUseStackSlot();
3956               }
3957             } else if (isFPArg) {
3958               // Get the outgoing arg reg to see if there is one.
3959               regNumForArg = regInfo.regNumForFPArg(regType, false, false,
3960                                                     argNo, regClassIDOfArgReg);
3961               if (regNumForArg == regInfo.getInvalidRegNum())
3962                 argInfo.setUseStackSlot();
3963               else {
3964                 argInfo.setUseFPArgReg();
3965                 regNumForArg =regInfo.getUnifiedRegNum(regClassIDOfArgReg,
3966                                                        regNumForArg);
3967               }
3968             } else {
3969               // Get the outgoing arg reg to see if there is one.
3970               regNumForArg = regInfo.regNumForIntArg(false,false,
3971                                                      argNo, regClassIDOfArgReg);
3972               if (regNumForArg == regInfo.getInvalidRegNum())
3973                 argInfo.setUseStackSlot();
3974               else {
3975                 argInfo.setUseIntArgReg();
3976                 regNumForArg =regInfo.getUnifiedRegNum(regClassIDOfArgReg,
3977                                                        regNumForArg);
3978               }
3979             }
3980
3981             //
3982             // Now insert copy instructions to stack slot or arg. register
3983             //
3984             if (argInfo.usesStackSlot()) {
3985               // Get the stack offset for this argument slot.
3986               // FP args on stack are right justified so adjust offset!
3987               // int arguments are also right justified but they are
3988               // always loaded as a full double-word so the offset does
3989               // not need to be adjusted.
3990               int argOffset = frameInfo.getOutgoingArgOffset(MF, argNo);
3991               if (argType->isFloatingPoint()) {
3992                 unsigned slotSize = SparcV9FrameInfo::SizeOfEachArgOnStack;
3993                 assert(argSize <= slotSize && "Insufficient slot size!");
3994                 argOffset += slotSize - argSize;
3995               }
3996
3997               // Now generate instruction to copy argument to stack
3998               MachineOpCode storeOpCode =
3999                 (argType->isFloatingPoint()
4000                  ? ((argSize == 4)? V9::STFi : V9::STDFi) : V9::STXi);
4001
4002               M = BuildMI(storeOpCode, 3).addReg(argVal)
4003                 .addMReg(regInfo.getStackPointer()).addSImm(argOffset);
4004               mvec.push_back(M);
4005             }
4006             else if (regNumForArg != regInfo.getInvalidRegNum()) {
4007
4008               // Create a virtual register to represent the arg reg. Mark
4009               // this vreg as being an implicit operand of the call MI.
4010               TmpInstruction* argVReg =
4011                 new TmpInstruction(mcfi, argVal, NULL, "argReg");
4012
4013               callMI->addImplicitRef(argVReg);
4014
4015               // Generate the reg-to-reg copy into the outgoing arg reg.
4016               // -- For FP values, create a FMOVS or FMOVD instruction
4017               // -- For non-FP values, create an add-with-0 instruction
4018               if (argType->isFloatingPoint())
4019                 M=(BuildMI(argType==Type::FloatTy? V9::FMOVS :V9::FMOVD,2)
4020                    .addReg(argVal).addReg(argVReg, MachineOperand::Def));
4021               else
4022                 M = (BuildMI(ChooseAddInstructionByType(argType), 3)
4023                      .addReg(argVal).addSImm((int64_t) 0)
4024                      .addReg(argVReg, MachineOperand::Def));
4025
4026               // Mark the operand with the register it should be assigned
4027               M->SetRegForOperand(M->getNumOperands()-1, regNumForArg);
4028               callMI->SetRegForImplicitRef(callMI->getNumImplicitRefs()-1,
4029                                            regNumForArg);
4030
4031               mvec.push_back(M);
4032             }
4033             else
4034               assert(argInfo.getArgCopy() != regInfo.getInvalidRegNum() &&
4035                      "Arg. not in stack slot, primary or secondary register?");
4036           }
4037
4038           // add call instruction and delay slot before copying return value
4039           mvec.push_back(callMI);
4040           mvec.push_back(BuildMI(V9::NOP, 0));
4041
4042           // Add the return value as an implicit ref.  The call operands
4043           // were added above.  Also, add code to copy out the return value.
4044           // This is always register-to-register for int or FP return values.
4045           //
4046           if (callInstr->getType() != Type::VoidTy) {
4047             // Get the return value reg.
4048             const Type* retType = callInstr->getType();
4049
4050             int regNum = (retType->isFloatingPoint()
4051                           ? (unsigned) SparcV9FloatRegClass::f0
4052                           : (unsigned) SparcV9IntRegClass::o0);
4053             unsigned regClassID = regInfo.getRegClassIDOfType(retType);
4054             regNum = regInfo.getUnifiedRegNum(regClassID, regNum);
4055
4056             // Create a virtual register to represent it and mark
4057             // this vreg as being an implicit operand of the call MI
4058             TmpInstruction* retVReg =
4059               new TmpInstruction(mcfi, callInstr, NULL, "argReg");
4060
4061             callMI->addImplicitRef(retVReg, /*isDef*/ true);
4062
4063             // Generate the reg-to-reg copy from the return value reg.
4064             // -- For FP values, create a FMOVS or FMOVD instruction
4065             // -- For non-FP values, create an add-with-0 instruction
4066             if (retType->isFloatingPoint())
4067               M = (BuildMI(retType==Type::FloatTy? V9::FMOVS : V9::FMOVD, 2)
4068                    .addReg(retVReg).addReg(callInstr, MachineOperand::Def));
4069             else
4070               M = (BuildMI(ChooseAddInstructionByType(retType), 3)
4071                    .addReg(retVReg).addSImm((int64_t) 0)
4072                    .addReg(callInstr, MachineOperand::Def));
4073
4074             // Mark the operand with the register it should be assigned
4075             // Also mark the implicit ref of the call defining this operand
4076             M->SetRegForOperand(0, regNum);
4077             callMI->SetRegForImplicitRef(callMI->getNumImplicitRefs()-1,regNum);
4078
4079             mvec.push_back(M);
4080           }
4081
4082           // For the CALL instruction, the ret. addr. reg. is also implicit
4083           if (isa<Function>(callee))
4084             callMI->addImplicitRef(retAddrReg, /*isDef*/ true);
4085
4086           MF.getInfo<SparcV9FunctionInfo>()->popAllTempValues();  // free temps used for this inst
4087         }
4088
4089         break;
4090       }
4091
4092       case 62:  // reg:   Shl(reg, reg)
4093       {
4094         Value* argVal1 = subtreeRoot->leftChild()->getValue();
4095         Value* argVal2 = subtreeRoot->rightChild()->getValue();
4096         Instruction* shlInstr = subtreeRoot->getInstruction();
4097
4098         const Type* opType = argVal1->getType();
4099         assert((opType->isInteger() || isa<PointerType>(opType)) &&
4100                "Shl unsupported for other types");
4101         unsigned opSize = target.getTargetData().getTypeSize(opType);
4102
4103         CreateShiftInstructions(target, shlInstr->getParent()->getParent(),
4104                                 (opSize > 4)? V9::SLLXr6:V9::SLLr5,
4105                                 argVal1, argVal2, 0, shlInstr, mvec,
4106                                 MachineCodeForInstruction::get(shlInstr));
4107         break;
4108       }
4109
4110       case 63:  // reg:   Shr(reg, reg)
4111       {
4112         const Type* opType = subtreeRoot->leftChild()->getValue()->getType();
4113         assert((opType->isInteger() || isa<PointerType>(opType)) &&
4114                "Shr unsupported for other types");
4115         unsigned opSize = target.getTargetData().getTypeSize(opType);
4116         Add3OperandInstr(opType->isSigned()
4117                          ? (opSize > 4? V9::SRAXr6 : V9::SRAr5)
4118                          : (opSize > 4? V9::SRLXr6 : V9::SRLr5),
4119                          subtreeRoot, mvec);
4120         break;
4121       }
4122
4123       case 64:  // reg:   Phi(reg,reg)
4124         break;                          // don't forward the value
4125
4126       case 65:  // reg:   VANext(reg):  the va_next(va_list, type) instruction
4127       { // Increment the va_list pointer register according to the type.
4128         // All LLVM argument types are <= 64 bits, so use one doubleword.
4129         Instruction* vaNextI = subtreeRoot->getInstruction();
4130         assert(target.getTargetData().getTypeSize(vaNextI->getType()) <= 8 &&
4131                "We assumed that all LLVM parameter types <= 8 bytes!");
4132         unsigned argSize = SparcV9FrameInfo::SizeOfEachArgOnStack;
4133         mvec.push_back(BuildMI(V9::ADDi, 3).addReg(vaNextI->getOperand(0)).
4134                        addSImm(argSize).addRegDef(vaNextI));
4135         break;
4136       }
4137
4138       case 66:  // reg:   VAArg (reg): the va_arg instruction
4139       { // Load argument from stack using current va_list pointer value.
4140         // Use 64-bit load for all non-FP args, and LDDF or double for FP.
4141         Instruction* vaArgI = subtreeRoot->getInstruction();
4142         MachineOpCode loadOp = (vaArgI->getType()->isFloatingPoint()
4143                                 ? (vaArgI->getType() == Type::FloatTy
4144                                    ? V9::LDFi : V9::LDDFi)
4145                                 : V9::LDXi);
4146         mvec.push_back(BuildMI(loadOp, 3).addReg(vaArgI->getOperand(0)).
4147                        addSImm(0).addRegDef(vaArgI));
4148         break;
4149       }
4150
4151       case 71:  // reg:     VReg
4152       case 72:  // reg:     Constant
4153         break;                          // don't forward the value
4154
4155       default:
4156         assert(0 && "Unrecognized BURG rule");
4157         break;
4158       }
4159     }
4160
4161   if (forwardOperandNum >= 0) {
4162     // We did not generate a machine instruction but need to use operand.
4163     // If user is in the same tree, replace Value in its machine operand.
4164     // If not, insert a copy instruction which should get coalesced away
4165     // by register allocation.
4166     if (subtreeRoot->parent() != NULL)
4167       ForwardOperand(subtreeRoot, subtreeRoot->parent(), forwardOperandNum);
4168     else {
4169       std::vector<MachineInstr*> minstrVec;
4170       Instruction* instr = subtreeRoot->getInstruction();
4171       CreateCopyInstructionsByType(target,
4172                                      instr->getParent()->getParent(),
4173                                      instr->getOperand(forwardOperandNum),
4174                                      instr, minstrVec,
4175                                      MachineCodeForInstruction::get(instr));
4176       assert(minstrVec.size() > 0);
4177       mvec.insert(mvec.end(), minstrVec.begin(), minstrVec.end());
4178     }
4179   }
4180
4181   if (maskUnsignedResult) {
4182     // If result is unsigned and smaller than int reg size,
4183     // we need to clear high bits of result value.
4184     assert(forwardOperandNum < 0 && "Need mask but no instruction generated");
4185     Instruction* dest = subtreeRoot->getInstruction();
4186     if (dest->getType()->isUnsigned()) {
4187       unsigned destSize=target.getTargetData().getTypeSize(dest->getType());
4188       if (destSize <= 4) {
4189         // Mask high 64 - N bits, where N = 4*destSize.
4190
4191         // Use a TmpInstruction to represent the
4192         // intermediate result before masking.  Since those instructions
4193         // have already been generated, go back and substitute tmpI
4194         // for dest in the result position of each one of them.
4195         //
4196         MachineCodeForInstruction& mcfi = MachineCodeForInstruction::get(dest);
4197         TmpInstruction *tmpI = new TmpInstruction(mcfi, dest->getType(),
4198                                                   dest, NULL, "maskHi");
4199         Value* srlArgToUse = tmpI;
4200
4201         unsigned numSubst = 0;
4202         for (unsigned i=0, N=mvec.size(); i < N; ++i) {
4203
4204           // Make sure we substitute all occurrences of dest in these instrs.
4205           // Otherwise, we will have bogus code.
4206           bool someArgsWereIgnored = false;
4207
4208           // Make sure not to substitute an upwards-exposed use -- that would
4209           // introduce a use of `tmpI' with no preceding def.  Therefore,
4210           // substitute a use or def-and-use operand only if a previous def
4211           // operand has already been substituted (i.e., numSubst > 0).
4212           //
4213           numSubst += mvec[i]->substituteValue(dest, tmpI,
4214                                                /*defsOnly*/ numSubst == 0,
4215                                                /*notDefsAndUses*/ numSubst > 0,
4216                                                someArgsWereIgnored);
4217           assert(!someArgsWereIgnored &&
4218                  "Operand `dest' exists but not replaced: probably bogus!");
4219         }
4220         assert(numSubst > 0 && "Operand `dest' not replaced: probably bogus!");
4221
4222         // Left shift 32-N if size (N) is less than 32 bits.
4223         // Use another tmp. virtual register to represent this result.
4224         if (destSize < 4) {
4225           srlArgToUse = new TmpInstruction(mcfi, dest->getType(),
4226                                            tmpI, NULL, "maskHi2");
4227           mvec.push_back(BuildMI(V9::SLLXi6, 3).addReg(tmpI)
4228                          .addZImm(8*(4-destSize))
4229                          .addReg(srlArgToUse, MachineOperand::Def));
4230         }
4231
4232         // Logical right shift 32-N to get zero extension in top 64-N bits.
4233         mvec.push_back(BuildMI(V9::SRLi5, 3).addReg(srlArgToUse)
4234                          .addZImm(8*(4-destSize))
4235                          .addReg(dest, MachineOperand::Def));
4236
4237       } else if (destSize < 8) {
4238         assert(0 && "Unsupported type size: 32 < size < 64 bits");
4239       }
4240     }
4241   }
4242 }
4243
4244 } // End llvm namespace
4245
4246 //==------------------------------------------------------------------------==//
4247 //                     Class V9ISel Implementation
4248 //==------------------------------------------------------------------------==//
4249
4250 bool V9ISel::runOnFunction(Function &F) {
4251   // First pass - Walk the function, lowering any calls to intrinsic functions
4252   // which the instruction selector cannot handle.
4253   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
4254     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; )
4255       if (CallInst *CI = dyn_cast<CallInst>(I++))
4256         if (Function *F = CI->getCalledFunction())
4257           switch (F->getIntrinsicID()) {
4258           case Intrinsic::not_intrinsic:
4259           case Intrinsic::vastart:
4260           case Intrinsic::vacopy:
4261           case Intrinsic::vaend:
4262             // We directly implement these intrinsics.  Note that this knowledge
4263             // is incestuously entangled with the code in
4264             // SparcInstrSelection.cpp and must be updated when it is updated.
4265             // Since ALL of the code in this library is incestuously intertwined
4266             // with it already and sparc specific, we will live with this.
4267             break;
4268           default:
4269             // All other intrinsic calls we must lower.
4270             Instruction *Before = CI->getPrev();
4271             Target.getIntrinsicLowering().LowerIntrinsicCall(CI);
4272             if (Before) {        // Move iterator to instruction after call
4273               I = Before;  ++I;
4274             } else {
4275               I = BB->begin();
4276             }
4277           }
4278
4279   // Build the instruction trees to be given as inputs to BURG.
4280   InstrForest instrForest(&F);
4281   if (SelectDebugLevel >= Select_DebugInstTrees) {
4282     std::cerr << "\n\n*** Input to instruction selection for function "
4283               << F.getName() << "\n\n" << F
4284               << "\n\n*** Instruction trees for function "
4285               << F.getName() << "\n\n";
4286     instrForest.dump();
4287   }
4288
4289   // Invoke BURG instruction selection for each tree
4290   for (InstrForest::const_root_iterator RI = instrForest.roots_begin();
4291        RI != instrForest.roots_end(); ++RI) {
4292     InstructionNode* basicNode = *RI;
4293     assert(basicNode->parent() == NULL && "A `root' node has a parent?");
4294
4295     // Invoke BURM to label each tree node with a state
4296     burm_label(basicNode);
4297     if (SelectDebugLevel >= Select_DebugBurgTrees) {
4298       printcover(basicNode, 1, 0);
4299       std::cerr << "\nCover cost == " << treecost(basicNode, 1, 0) <<"\n\n";
4300       printMatches(basicNode);
4301     }
4302
4303     // Then recursively walk the tree to select instructions
4304     SelectInstructionsForTree(basicNode, /*goalnt*/1);
4305   }
4306
4307   // Create the MachineBasicBlocks and add all of the MachineInstrs
4308   // defined in the MachineCodeForInstruction objects to the MachineBasicBlocks.
4309   MachineFunction &MF = MachineFunction::get(&F);
4310   std::map<const BasicBlock *, MachineBasicBlock *> MBBMap;
4311   for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) {
4312     MachineBasicBlock *MBB = new MachineBasicBlock(BI);
4313     MF.getBasicBlockList().push_back(MBB);
4314     MBBMap[BI] = MBB;
4315
4316     for (BasicBlock::iterator II = BI->begin(); II != BI->end(); ++II) {
4317       MachineCodeForInstruction &mvec = MachineCodeForInstruction::get(II);
4318       MBB->insert(MBB->end(), mvec.begin(), mvec.end());
4319     }
4320   }
4321
4322   // Initialize Machine-CFG for the function.
4323   for (MachineFunction::iterator i = MF.begin (), e = MF.end (); i != e; ++i) {
4324     MachineBasicBlock &MBB = *i;
4325     const BasicBlock *BB = MBB.getBasicBlock ();
4326     // for each successor S of BB, add MBBMap[S] as a successor of MBB.
4327     for (succ_const_iterator si = succ_begin(BB), se = succ_end(BB); si != se;
4328          ++si) {
4329       MachineBasicBlock *succMBB = MBBMap[*si];
4330       assert (succMBB && "Can't find MachineBasicBlock for this successor");
4331       MBB.addSuccessor (succMBB);
4332     }
4333   }
4334
4335   // Insert phi elimination code
4336   InsertCodeForPhis(F);
4337
4338   if (SelectDebugLevel >= Select_PrintMachineCode) {
4339     std::cerr << "\n*** Machine instructions after INSTRUCTION SELECTION\n";
4340     MachineFunction::get(&F).dump();
4341   }
4342
4343   return true;
4344 }
4345
4346 /// InsertCodeForPhis - This method inserts Phi elimination code for
4347 /// all Phi nodes in the given function.  After this method is called,
4348 /// the Phi nodes still exist in the LLVM code, but copies are added to the
4349 /// machine code.
4350 ///
4351 void V9ISel::InsertCodeForPhis(Function &F) {
4352   // Iterate over every Phi node PN in F:
4353   MachineFunction &MF = MachineFunction::get(&F);
4354   for (MachineFunction::iterator BB = MF.begin(); BB != MF.end(); ++BB) {
4355     for (BasicBlock::const_iterator IIt = BB->getBasicBlock()->begin();
4356          const PHINode *PN = dyn_cast<PHINode>(IIt); ++IIt) {
4357       // Create a new temporary register to hold the result of the Phi copy.
4358       // The leak detector shouldn't track these nodes.  They are not garbage,
4359       // even though their parent field is never filled in.
4360       Value *PhiCpRes = new PHINode(PN->getType(), PN->getName() + ":PhiCp");
4361       LeakDetector::removeGarbageObject(PhiCpRes);
4362
4363       // For each of PN's incoming values, insert a copy in the corresponding
4364       // predecessor block.
4365       MachineCodeForInstruction &MCforPN = MachineCodeForInstruction::get (PN);
4366       for (unsigned i = 0; i < PN->getNumIncomingValues(); ++i) {
4367         std::vector<MachineInstr*> mvec, CpVec;
4368         Target.getRegInfo()->cpValue2Value(PN->getIncomingValue(i),
4369                                            PhiCpRes, mvec);
4370         for (std::vector<MachineInstr*>::iterator MI=mvec.begin();
4371              MI != mvec.end(); ++MI) {
4372           std::vector<MachineInstr*> CpVec2 =
4373             FixConstantOperandsForInstr(const_cast<PHINode*>(PN), *MI, Target);
4374           CpVec2.push_back(*MI);
4375           CpVec.insert(CpVec.end(), CpVec2.begin(), CpVec2.end());
4376         }
4377         // Insert the copy instructions into the predecessor BB.
4378         InsertPhiElimInstructions(PN->getIncomingBlock(i), CpVec);
4379         MCforPN.insert (MCforPN.end (), CpVec.begin (), CpVec.end ());
4380       }
4381       // Insert a copy instruction from PhiCpRes to PN.
4382       std::vector<MachineInstr*> mvec;
4383       Target.getRegInfo()->cpValue2Value(PhiCpRes, const_cast<PHINode*>(PN),
4384                                         mvec);
4385       BB->insert(BB->begin(), mvec.begin(), mvec.end());
4386       MCforPN.insert (MCforPN.end (), mvec.begin (), mvec.end ());
4387     }  // for each Phi Instr in BB
4388   } // for all BBs in function
4389 }
4390
4391 /// InsertPhiElimInstructions - Inserts the instructions in CpVec into the
4392 /// MachineBasicBlock corresponding to BB, just before its terminator
4393 /// instruction. This is used by InsertCodeForPhis() to insert copies, above.
4394 ///
4395 void V9ISel::InsertPhiElimInstructions(BasicBlock *BB,
4396                                        const std::vector<MachineInstr*>& CpVec)
4397 {
4398   Instruction *TermInst = (Instruction*)BB->getTerminator();
4399   MachineCodeForInstruction &MC4Term = MachineCodeForInstruction::get(TermInst);
4400   MachineInstr *FirstMIOfTerm = MC4Term.front();
4401   assert (FirstMIOfTerm && "No Machine Instrs for terminator");
4402
4403   MachineBasicBlock *MBB = FirstMIOfTerm->getParent();
4404   assert(MBB && "Machine BB for predecessor's terminator not found");
4405   MachineBasicBlock::iterator MCIt = FirstMIOfTerm;
4406   assert(MCIt != MBB->end() && "Start inst of terminator not found");
4407
4408   // Insert the copy instructions just before the first machine instruction
4409   // generated for the terminator.
4410   MBB->insert(MCIt, CpVec.begin(), CpVec.end());
4411 }
4412
4413 /// SelectInstructionsForTree - Recursively walk the tree to select
4414 /// instructions. Do this top-down so that child instructions can exploit
4415 /// decisions made at the child instructions.
4416 ///
4417 /// E.g., if br(setle(reg,const)) decides the constant is 0 and uses
4418 /// a branch-on-integer-register instruction, then the setle node
4419 /// can use that information to avoid generating the SUBcc instruction.
4420 ///
4421 /// Note that this cannot be done bottom-up because setle must do this
4422 /// only if it is a child of the branch (otherwise, the result of setle
4423 /// may be used by multiple instructions).
4424 ///
4425 void V9ISel::SelectInstructionsForTree(InstrTreeNode* treeRoot, int goalnt) {
4426   // Get the rule that matches this node.
4427   int ruleForNode = burm_rule(treeRoot->state, goalnt);
4428
4429   if (ruleForNode == 0) {
4430     std::cerr << "Could not match instruction tree for instr selection\n";
4431     abort();
4432   }
4433
4434   // Get this rule's non-terminals and the corresponding child nodes (if any)
4435   short *nts = burm_nts[ruleForNode];
4436
4437   // First, select instructions for the current node and rule.
4438   // (If this is a list node, not an instruction, then skip this step).
4439   // This function is specific to the target architecture.
4440   if (treeRoot->opLabel != VRegListOp) {
4441     std::vector<MachineInstr*> minstrVec;
4442     InstructionNode* instrNode = (InstructionNode*)treeRoot;
4443     assert(instrNode->getNodeType() == InstrTreeNode::NTInstructionNode);
4444     GetInstructionsByRule(instrNode, ruleForNode, nts, Target, minstrVec);
4445     MachineCodeForInstruction &mvec =
4446       MachineCodeForInstruction::get(instrNode->getInstruction());
4447     mvec.insert(mvec.end(), minstrVec.begin(), minstrVec.end());
4448   }
4449
4450   // Then, recursively compile the child nodes, if any.
4451   //
4452   if (nts[0]) {
4453     // i.e., there is at least one kid
4454     InstrTreeNode* kids[2];
4455     int currentRule = ruleForNode;
4456     burm_kids(treeRoot, currentRule, kids);
4457
4458     // First skip over any chain rules so that we don't visit
4459     // the current node again.
4460     while (ThisIsAChainRule(currentRule)) {
4461       currentRule = burm_rule(treeRoot->state, nts[0]);
4462       nts = burm_nts[currentRule];
4463       burm_kids(treeRoot, currentRule, kids);
4464     }
4465
4466     // Now we have the first non-chain rule so we have found
4467     // the actual child nodes.  Recursively compile them.
4468     for (unsigned i = 0; nts[i]; i++) {
4469       assert(i < 2);
4470       InstrTreeNode::InstrTreeNodeType nodeType = kids[i]->getNodeType();
4471       if (nodeType == InstrTreeNode::NTVRegListNode ||
4472           nodeType == InstrTreeNode::NTInstructionNode)
4473         SelectInstructionsForTree(kids[i], nts[i]);
4474     }
4475   }
4476
4477   // Finally, do any post-processing on this node after its children
4478   // have been translated.
4479   if (treeRoot->opLabel != VRegListOp)
4480     PostprocessMachineCodeForTree((InstructionNode*)treeRoot, ruleForNode, nts);
4481 }
4482
4483 /// PostprocessMachineCodeForTree - Apply any final cleanups to
4484 /// machine code for the root of a subtree after selection for all its
4485 /// children has been completed.
4486 ///
4487 void V9ISel::PostprocessMachineCodeForTree(InstructionNode *instrNode,
4488                                            int ruleForNode, short *nts) {
4489   // Fix up any constant operands in the machine instructions to either
4490   // use an immediate field or to load the constant into a register.
4491   // Walk backwards and use direct indexes to allow insertion before current.
4492   Instruction* vmInstr = instrNode->getInstruction();
4493   MachineCodeForInstruction &mvec = MachineCodeForInstruction::get(vmInstr);
4494   for (unsigned i = mvec.size(); i != 0; --i) {
4495     std::vector<MachineInstr*> loadConstVec =
4496       FixConstantOperandsForInstr(vmInstr, mvec[i-1], Target);
4497     mvec.insert(mvec.begin()+i-1, loadConstVec.begin(), loadConstVec.end());
4498   }
4499 }
4500
4501 /// createSparcV9BurgInstSelector - Creates and returns a new SparcV9
4502 /// BURG-based instruction selection pass.
4503 ///
4504 FunctionPass *llvm::createSparcV9BurgInstSelector(TargetMachine &TM) {
4505   return new V9ISel(TM);
4506 }