LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

SparcV9BurgISel.cpp

Go to the documentation of this file.
00001 //===- SparcV9BurgISel.cpp - SparcV9 BURG-based Instruction Selector ------===//
00002 // 
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 // 
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // SparcV9 BURG-based instruction selector. It uses the SSA graph to
00011 // construct a forest of BURG instruction trees (class InstrForest) and then
00012 // uses the BURG-generated tree grammar (BURM) to find the optimal instruction
00013 // sequences for the SparcV9.
00014 //  
00015 //===----------------------------------------------------------------------===//
00016 
00017 #include "MachineInstrAnnot.h"
00018 #include "SparcV9BurgISel.h"
00019 #include "SparcV9InstrForest.h"
00020 #include "SparcV9Internals.h"
00021 #include "SparcV9TmpInstr.h"
00022 #include "SparcV9FrameInfo.h"
00023 #include "SparcV9RegisterInfo.h"
00024 #include "MachineFunctionInfo.h"
00025 #include "llvm/CodeGen/IntrinsicLowering.h"
00026 #include "llvm/CodeGen/MachineConstantPool.h"
00027 #include "llvm/CodeGen/MachineFunction.h"
00028 #include "llvm/CodeGen/MachineInstr.h"
00029 #include "llvm/CodeGen/MachineInstrBuilder.h"
00030 #include "llvm/Constants.h"
00031 #include "llvm/DerivedTypes.h"
00032 #include "llvm/Instructions.h"
00033 #include "llvm/Intrinsics.h"
00034 #include "llvm/Module.h"
00035 #include "llvm/Pass.h"
00036 #include "llvm/Support/CFG.h"
00037 #include "llvm/Target/TargetInstrInfo.h"
00038 #include "llvm/Target/TargetMachine.h"
00039 #include "llvm/Type.h"
00040 #include "llvm/Config/alloca.h"
00041 #include "llvm/Support/CommandLine.h"
00042 #include "llvm/Support/LeakDetector.h"
00043 #include "llvm/Support/MathExtras.h"
00044 #include "llvm/ADT/STLExtras.h"
00045 #include "llvm/ADT/hash_map"
00046 #include <algorithm>
00047 #include <cmath>
00048 #include <iostream>
00049 using namespace llvm;
00050 
00051 //==------------------------------------------------------------------------==//
00052 //          InstrForest (V9ISel BURG instruction trees) implementation
00053 //==------------------------------------------------------------------------==//
00054 
00055 namespace llvm {
00056 
00057 class InstructionNode : public InstrTreeNode {
00058   bool codeIsFoldedIntoParent;
00059   
00060 public:
00061   InstructionNode(Instruction *_instr);
00062 
00063   Instruction *getInstruction() const {
00064     assert(treeNodeType == NTInstructionNode);
00065     return cast<Instruction>(val);
00066   }
00067 
00068   void markFoldedIntoParent() { codeIsFoldedIntoParent = true; }
00069   bool isFoldedIntoParent()   { return codeIsFoldedIntoParent; }
00070 
00071   // Methods to support type inquiry through isa, cast, and dyn_cast:
00072   static inline bool classof(const InstructionNode *N) { return true; }
00073   static inline bool classof(const InstrTreeNode *N) {
00074     return N->getNodeType() == InstrTreeNode::NTInstructionNode;
00075   }
00076   
00077 protected:
00078   virtual void dumpNode(int indent) const;
00079 };
00080 
00081 class VRegListNode : public InstrTreeNode {
00082 public:
00083   VRegListNode() : InstrTreeNode(NTVRegListNode, 0) { opLabel = VRegListOp; }
00084   // Methods to support type inquiry through isa, cast, and dyn_cast:
00085   static inline bool classof(const VRegListNode  *N) { return true; }
00086   static inline bool classof(const InstrTreeNode *N) {
00087     return N->getNodeType() == InstrTreeNode::NTVRegListNode;
00088   }
00089 protected:
00090   virtual void dumpNode(int indent) const;
00091 };
00092 
00093 class VRegNode : public InstrTreeNode {
00094 public:
00095   VRegNode(Value* _val) : InstrTreeNode(NTVRegNode, _val) {
00096     opLabel = VRegNodeOp;
00097   }
00098   // Methods to support type inquiry through isa, cast, and dyn_cast:
00099   static inline bool classof(const VRegNode  *N) { return true; }
00100   static inline bool classof(const InstrTreeNode *N) {
00101     return N->getNodeType() == InstrTreeNode::NTVRegNode;
00102   }
00103 protected:
00104   virtual void dumpNode(int indent) const;
00105 };
00106 
00107 class ConstantNode : public InstrTreeNode {
00108 public:
00109   ConstantNode(Constant *constVal) 
00110     : InstrTreeNode(NTConstNode, (Value*)constVal) {
00111     opLabel = ConstantNodeOp;    
00112   }
00113   Constant *getConstVal() const { return (Constant*) val;}
00114   // Methods to support type inquiry through isa, cast, and dyn_cast:
00115   static inline bool classof(const ConstantNode  *N) { return true; }
00116   static inline bool classof(const InstrTreeNode *N) {
00117     return N->getNodeType() == InstrTreeNode::NTConstNode;
00118   }
00119 protected:
00120   virtual void dumpNode(int indent) const;
00121 };
00122 
00123 class LabelNode : public InstrTreeNode {
00124 public:
00125   LabelNode(BasicBlock* BB) : InstrTreeNode(NTLabelNode, (Value*)BB) {
00126     opLabel = LabelNodeOp;
00127   }
00128   BasicBlock *getBasicBlock() const { return (BasicBlock*)val;}
00129   // Methods to support type inquiry through isa, cast, and dyn_cast:
00130   static inline bool classof(const LabelNode     *N) { return true; }
00131   static inline bool classof(const InstrTreeNode *N) {
00132     return N->getNodeType() == InstrTreeNode::NTLabelNode;
00133   }
00134 protected:
00135   virtual void dumpNode(int indent) const;
00136 };
00137 
00138 /// InstrForest -  A forest of instruction trees for a single function.
00139 /// The goal of InstrForest is to group instructions into a single
00140 /// tree if one or more of them might be potentially combined into a
00141 /// single complex instruction in the target machine. We group two
00142 /// instructions O and I if: (1) Instruction O computes an operand used
00143 /// by instruction I, and (2) O and I are part of the same basic block,
00144 /// and (3) O has only a single use, viz., I.
00145 /// 
00146 class InstrForest : private hash_map<const Instruction *, InstructionNode*> {
00147 public:
00148   // Use a vector for the root set to get a deterministic iterator
00149   // for stable code generation.  Even though we need to erase nodes
00150   // during forest construction, a vector should still be efficient
00151   // because the elements to erase are nearly always near the end.
00152   typedef std::vector<InstructionNode*> RootSet;
00153   typedef RootSet::      iterator       root_iterator;
00154   typedef RootSet::const_iterator const_root_iterator;
00155   
00156 private:
00157   RootSet treeRoots;
00158   
00159 public:
00160   /*ctor*/  InstrForest (Function *F);
00161   /*dtor*/  ~InstrForest  ();
00162   
00163   /// getTreeNodeForInstr - Returns the tree node for an Instruction.
00164   ///
00165   inline InstructionNode *getTreeNodeForInstr(Instruction* instr) {
00166     return (*this)[instr];
00167   }
00168   
00169   /// Iterators for the root nodes for all the trees.
00170   ///
00171   const_root_iterator roots_begin() const     { return treeRoots.begin(); }
00172         root_iterator roots_begin()           { return treeRoots.begin(); }
00173   const_root_iterator roots_end  () const     { return treeRoots.end();   }
00174         root_iterator roots_end  ()           { return treeRoots.end();   }
00175   
00176   void dump() const;
00177   
00178 private:
00179   // Methods used to build the instruction forest.
00180   void eraseRoot    (InstructionNode* node);
00181   void setLeftChild (InstrTreeNode* parent, InstrTreeNode* child);
00182   void setRightChild(InstrTreeNode* parent, InstrTreeNode* child);
00183   void setParent    (InstrTreeNode* child,  InstrTreeNode* parent);
00184   void noteTreeNodeForInstr(Instruction* instr, InstructionNode* treeNode);
00185   InstructionNode* buildTreeForInstruction(Instruction* instr);
00186 };
00187 
00188 void InstrTreeNode::dump(int dumpChildren, int indent) const {
00189   dumpNode(indent);
00190   
00191   if (dumpChildren) {
00192     if (LeftChild)
00193       LeftChild->dump(dumpChildren, indent+1);
00194     if (RightChild)
00195       RightChild->dump(dumpChildren, indent+1);
00196   }
00197 }
00198 
00199 InstructionNode::InstructionNode(Instruction* I)
00200   : InstrTreeNode(NTInstructionNode, I), codeIsFoldedIntoParent(false) {
00201   opLabel = I->getOpcode();
00202 
00203   // Distinguish special cases of some instructions such as Ret and Br
00204   // 
00205   if (opLabel == Instruction::Ret && cast<ReturnInst>(I)->getReturnValue()) {
00206     opLabel = RetValueOp;                // ret(value) operation
00207   }
00208   else if (opLabel ==Instruction::Br && !cast<BranchInst>(I)->isUnconditional())
00209   {
00210     opLabel = BrCondOp;   // br(cond) operation
00211   } else if (opLabel >= Instruction::SetEQ && opLabel <= Instruction::SetGT) {
00212     opLabel = SetCCOp;    // common label for all SetCC ops
00213   } else if (opLabel == Instruction::Alloca && I->getNumOperands() > 0) {
00214     opLabel = AllocaN;     // Alloca(ptr, N) operation
00215   } else if (opLabel == Instruction::GetElementPtr &&
00216              cast<GetElementPtrInst>(I)->hasIndices()) {
00217     opLabel = opLabel + 100;     // getElem with index vector
00218   } else if (opLabel == Instruction::Xor &&
00219              BinaryOperator::isNot(I)) {
00220     opLabel = (I->getType() == Type::BoolTy)?  NotOp  // boolean Not operator
00221       : BNotOp; // bitwise Not operator
00222   } else if (opLabel == Instruction::And || opLabel == Instruction::Or ||
00223              opLabel == Instruction::Xor) {
00224     // Distinguish bitwise operators from logical operators!
00225     if (I->getType() != Type::BoolTy)
00226       opLabel = opLabel + 100;   // bitwise operator
00227   } else if (opLabel == Instruction::Cast) {
00228     const Type *ITy = I->getType();
00229     switch(ITy->getTypeID())
00230     {
00231     case Type::BoolTyID:    opLabel = ToBoolTy;    break;
00232     case Type::UByteTyID:   opLabel = ToUByteTy;   break;
00233     case Type::SByteTyID:   opLabel = ToSByteTy;   break;
00234     case Type::UShortTyID:  opLabel = ToUShortTy;  break;
00235     case Type::ShortTyID:   opLabel = ToShortTy;   break;
00236     case Type::UIntTyID:    opLabel = ToUIntTy;    break;
00237     case Type::IntTyID:     opLabel = ToIntTy;     break;
00238     case Type::ULongTyID:   opLabel = ToULongTy;   break;
00239     case Type::LongTyID:    opLabel = ToLongTy;    break;
00240     case Type::FloatTyID:   opLabel = ToFloatTy;   break;
00241     case Type::DoubleTyID:  opLabel = ToDoubleTy;  break;
00242     case Type::ArrayTyID:   opLabel = ToArrayTy;   break;
00243     case Type::PointerTyID: opLabel = ToPointerTy; break;
00244     default:
00245       // Just use `Cast' opcode otherwise. It's probably ignored.
00246       break;
00247     }
00248   }
00249 }
00250 
00251 void InstructionNode::dumpNode(int indent) const {
00252   for (int i=0; i < indent; i++)
00253     std::cerr << "    ";
00254   std::cerr << getInstruction()->getOpcodeName()
00255             << " [label " << getOpLabel() << "]" << "\n";
00256 }
00257 
00258 void VRegListNode::dumpNode(int indent) const {
00259   for (int i=0; i < indent; i++)
00260     std::cerr << "    ";
00261   
00262   std::cerr << "List" << "\n";
00263 }
00264 
00265 void VRegNode::dumpNode(int indent) const {
00266   for (int i=0; i < indent; i++)
00267     std::cerr << "    ";
00268     std::cerr << "VReg " << *getValue() << "\n";
00269 }
00270 
00271 void ConstantNode::dumpNode(int indent) const {
00272   for (int i=0; i < indent; i++)
00273     std::cerr << "    ";
00274   std::cerr << "Constant " << *getValue() << "\n";
00275 }
00276 
00277 void LabelNode::dumpNode(int indent) const {
00278   for (int i=0; i < indent; i++)
00279     std::cerr << "    ";
00280   
00281   std::cerr << "Label " << *getValue() << "\n";
00282 }
00283 
00284 /// InstrForest ctor - Create a forest of instruction trees for a
00285 /// single function.
00286 ///
00287 InstrForest::InstrForest(Function *F) {
00288   for (Function::iterator BB = F->begin(), FE = F->end(); BB != FE; ++BB) {
00289     for(BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
00290       buildTreeForInstruction(I);
00291   }
00292 }
00293 
00294 InstrForest::~InstrForest() {
00295   for_each(treeRoots.begin(), treeRoots.end(), deleter<InstructionNode>);
00296 }
00297 
00298 void InstrForest::dump() const {
00299   for (const_root_iterator I = roots_begin(); I != roots_end(); ++I)
00300     (*I)->dump(/*dumpChildren*/ 1, /*indent*/ 0);
00301 }
00302 
00303 inline void InstrForest::eraseRoot(InstructionNode* node) {
00304   for (RootSet::reverse_iterator RI=treeRoots.rbegin(), RE=treeRoots.rend();
00305        RI != RE; ++RI)
00306     if (*RI == node)
00307       treeRoots.erase(RI.base()-1);
00308 }
00309 
00310 inline void InstrForest::noteTreeNodeForInstr(Instruction *instr,
00311                                               InstructionNode *treeNode) {
00312   (*this)[instr] = treeNode;
00313   treeRoots.push_back(treeNode);  // mark node as root of a new tree
00314 }
00315 
00316 inline void InstrForest::setLeftChild(InstrTreeNode *parent,
00317                                       InstrTreeNode *child) {
00318   parent->LeftChild = child;
00319   child->Parent = parent;
00320   if (InstructionNode* instrNode = dyn_cast<InstructionNode>(child))
00321     eraseRoot(instrNode); // no longer a tree root
00322 }
00323 
00324 inline void InstrForest::setRightChild(InstrTreeNode *parent,
00325                                        InstrTreeNode *child) {
00326   parent->RightChild = child;
00327   child->Parent = parent;
00328   if (InstructionNode* instrNode = dyn_cast<InstructionNode>(child))
00329     eraseRoot(instrNode); // no longer a tree root
00330 }
00331 
00332 InstructionNode* InstrForest::buildTreeForInstruction(Instruction *instr) {
00333   InstructionNode *treeNode = getTreeNodeForInstr(instr);
00334   if (treeNode) {
00335     // treeNode has already been constructed for this instruction
00336     assert(treeNode->getInstruction() == instr);
00337     return treeNode;
00338   }
00339   
00340   // Otherwise, create a new tree node for this instruction.
00341   treeNode = new InstructionNode(instr);
00342   noteTreeNodeForInstr(instr, treeNode);
00343   
00344   if (instr->getOpcode() == Instruction::Call) {
00345     // Operands of call instruction
00346     return treeNode;
00347   }
00348   
00349   // If the instruction has more than 2 instruction operands,
00350   // then we need to create artificial list nodes to hold them.
00351   // (Note that we only count operands that get tree nodes, and not
00352   // others such as branch labels for a branch or switch instruction.)
00353   // To do this efficiently, we'll walk all operands, build treeNodes
00354   // for all appropriate operands and save them in an array.  We then
00355   // insert children at the end, creating list nodes where needed.
00356   // As a performance optimization, allocate a child array only
00357   // if a fixed array is too small.
00358   int numChildren = 0;
00359   InstrTreeNode** childArray = new InstrTreeNode*[instr->getNumOperands()];
00360   
00361   // Walk the operands of the instruction
00362   for (Instruction::op_iterator O = instr->op_begin(); O!=instr->op_end();
00363        ++O) {
00364       Value* operand = *O;
00365       
00366       // Check if the operand is a data value, not an branch label, type,
00367       // method or module.  If the operand is an address type (i.e., label
00368       // or method) that is used in an non-branching operation, e.g., `add'.
00369       // that should be considered a data value.
00370       // Check latter condition here just to simplify the next IF.
00371       bool includeAddressOperand =
00372   (isa<BasicBlock>(operand) || isa<Function>(operand))
00373   && !instr->isTerminator();
00374     
00375       if (includeAddressOperand || isa<Instruction>(operand) ||
00376     isa<Constant>(operand) || isa<Argument>(operand)) {
00377         // This operand is a data value.
00378         // An instruction that computes the incoming value is added as a
00379         // child of the current instruction if:
00380         //   the value has only a single use
00381         //   AND both instructions are in the same basic block.
00382         //   AND the current instruction is not a PHI (because the incoming
00383         //    value is conceptually in a predecessor block,
00384         //    even though it may be in the same static block)
00385         // (Note that if the value has only a single use (viz., `instr'),
00386         //  the def of the value can be safely moved just before instr
00387         //  and therefore it is safe to combine these two instructions.)
00388         // In all other cases, the virtual register holding the value
00389         // is used directly, i.e., made a child of the instruction node.
00390         InstrTreeNode* opTreeNode;
00391         if (isa<Instruction>(operand) && operand->hasOneUse() &&
00392             cast<Instruction>(operand)->getParent() == instr->getParent() &&
00393             instr->getOpcode() != Instruction::PHI &&
00394             instr->getOpcode() != Instruction::Call) {
00395           // Recursively create a treeNode for it.
00396           opTreeNode = buildTreeForInstruction((Instruction*)operand);
00397         } else if (Constant *CPV = dyn_cast<Constant>(operand)) {
00398           if (isa<GlobalValue>(CPV))
00399             opTreeNode = new VRegNode(operand);
00400           else if (isa<UndefValue>(CPV)) {
00401             opTreeNode = new
00402                ConstantNode(Constant::getNullValue(CPV->getType()));
00403           } else {
00404             // Create a leaf node for a constant
00405             opTreeNode = new ConstantNode(CPV);
00406           }
00407         } else {
00408           // Create a leaf node for the virtual register
00409           opTreeNode = new VRegNode(operand);
00410         }
00411 
00412         childArray[numChildren++] = opTreeNode;
00413       }
00414     }
00415   
00416   // Add any selected operands as children in the tree.
00417   // Certain instructions can have more than 2 in some instances (viz.,
00418   // a CALL or a memory access -- LOAD, STORE, and GetElemPtr -- to an
00419   // array or struct). Make the operands of every such instruction into
00420   // a right-leaning binary tree with the operand nodes at the leaves
00421   // and VRegList nodes as internal nodes.
00422   InstrTreeNode *parent = treeNode;
00423   
00424   if (numChildren > 2) {
00425     unsigned instrOpcode = treeNode->getInstruction()->getOpcode();
00426     assert(instrOpcode == Instruction::PHI ||
00427            instrOpcode == Instruction::Call ||
00428            instrOpcode == Instruction::Load ||
00429            instrOpcode == Instruction::Store ||
00430            instrOpcode == Instruction::GetElementPtr);
00431   }
00432   
00433   // Insert the first child as a direct child
00434   if (numChildren >= 1)
00435     setLeftChild(parent, childArray[0]);
00436 
00437   int n;
00438   
00439   // Create a list node for children 2 .. N-1, if any
00440   for (n = numChildren-1; n >= 2; n--) {
00441     // We have more than two children
00442     InstrTreeNode *listNode = new VRegListNode();
00443     setRightChild(parent, listNode);
00444     setLeftChild(listNode, childArray[numChildren - n]);
00445     parent = listNode;
00446   }
00447   
00448   // Now insert the last remaining child (if any).
00449   if (numChildren >= 2) {
00450     assert(n == 1);
00451     setRightChild(parent, childArray[numChildren - 1]);
00452   }
00453 
00454   delete [] childArray;
00455   return treeNode;
00456 }
00457 //==------------------------------------------------------------------------==//
00458 //                V9ISel Command-line options and declarations
00459 //==------------------------------------------------------------------------==//
00460 
00461 namespace {
00462   /// Allow the user to select the amount of debugging information printed
00463   /// out by V9ISel.
00464   ///
00465   enum SelectDebugLevel_t {
00466     Select_NoDebugInfo,
00467     Select_PrintMachineCode, 
00468     Select_DebugInstTrees, 
00469     Select_DebugBurgTrees,
00470   };
00471   cl::opt<SelectDebugLevel_t>
00472   SelectDebugLevel("dselect", cl::Hidden,
00473                    cl::desc("enable instruction selection debug information"),
00474                    cl::values(
00475      clEnumValN(Select_NoDebugInfo,      "n", "disable debug output"),
00476      clEnumValN(Select_PrintMachineCode, "y", "print generated machine code"),
00477      clEnumValN(Select_DebugInstTrees,   "i",
00478                 "print debugging info for instruction selection"),
00479      clEnumValN(Select_DebugBurgTrees,   "b", "print burg trees"),
00480                               clEnumValEnd));
00481 
00482 
00483   /// V9ISel - This is the FunctionPass that drives the instruction selection
00484   /// process on the SparcV9 target.
00485   ///
00486   class V9ISel : public FunctionPass {
00487     TargetMachine &Target;
00488     void InsertCodeForPhis(Function &F);
00489     void InsertPhiElimInstructions(BasicBlock *BB,
00490                                    const std::vector<MachineInstr*>& CpVec);
00491     void SelectInstructionsForTree(InstrTreeNode* treeRoot, int goalnt);
00492     void PostprocessMachineCodeForTree(InstructionNode* instrNode,
00493                                        int ruleForNode, short* nts);
00494   public:
00495     V9ISel(TargetMachine &TM) : Target(TM) {}
00496 
00497     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00498       AU.setPreservesCFG();
00499     }
00500     
00501     bool runOnFunction(Function &F);
00502     virtual const char *getPassName() const {
00503       return "SparcV9 BURG Instruction Selector";
00504     }
00505   };
00506 }
00507 
00508 
00509 //==------------------------------------------------------------------------==//
00510 //                     Various V9ISel helper functions
00511 //==------------------------------------------------------------------------==//
00512 
00513 static const uint32_t MAXLO   = (1 << 10) - 1; // set bits set by %lo(*)
00514 static const uint32_t MAXSIMM = (1 << 12) - 1; // set bits in simm13 field of OR
00515 
00516 /// ConvertConstantToIntType - Function to get the value of an integral
00517 /// constant in the form that must be put into the machine register.  The
00518 /// specified constant is interpreted as (i.e., converted if necessary to) the
00519 /// specified destination type.  The result is always returned as an uint64_t,
00520 /// since the representation of int64_t and uint64_t are identical.  The
00521 /// argument can be any known const.  isValidConstant is set to true if a valid
00522 /// constant was found.
00523 /// 
00524 uint64_t ConvertConstantToIntType(const TargetMachine &target, const Value *V,
00525                                   const Type *destType, bool &isValidConstant) {
00526   isValidConstant = false;
00527   uint64_t C = 0;
00528 
00529   if (! destType->isIntegral() && ! isa<PointerType>(destType))
00530     return C;
00531 
00532   if (! isa<Constant>(V) || isa<GlobalValue>(V))
00533     return C;
00534 
00535   // GlobalValue: no conversions needed: get value and return it
00536   if (const GlobalValue* GV = dyn_cast<GlobalValue>(V)) {
00537     isValidConstant = true;             // may be overwritten by recursive call
00538     return ConvertConstantToIntType(target, GV, destType, isValidConstant);
00539   }
00540 
00541   // ConstantBool: no conversions needed: get value and return it
00542   if (const ConstantBool *CB = dyn_cast<ConstantBool>(V)) {
00543     isValidConstant = true;
00544     return (uint64_t) CB->getValue();
00545   }
00546 
00547   // ConstantPointerNull: it's really just a big, shiny version of zero.
00548   if (isa<ConstantPointerNull>(V)) {
00549     isValidConstant = true;
00550     return 0;
00551   }
00552 
00553   // For other types of constants, some conversion may be needed.
00554   // First, extract the constant operand according to its own type
00555   if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
00556     switch(CE->getOpcode()) {
00557     case Instruction::Cast:             // recursively get the value as cast
00558       C = ConvertConstantToIntType(target, CE->getOperand(0), CE->getType(),
00559                                    isValidConstant);
00560       break;
00561     default:                            // not simplifying other ConstantExprs
00562       break;
00563     }
00564   else if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
00565     isValidConstant = true;
00566     C = CI->getRawValue();
00567   } else if (const ConstantFP *CFP = dyn_cast<ConstantFP>(V)) {
00568     isValidConstant = true;
00569     double fC = CFP->getValue();
00570     C = (destType->isSigned()? (uint64_t) (int64_t) fC
00571                              : (uint64_t)           fC);
00572   } else if (isa<UndefValue>(V)) {
00573     isValidConstant = true;
00574     C = 0;
00575   }
00576 
00577   // Now if a valid value was found, convert it to destType.
00578   if (isValidConstant) {
00579     unsigned opSize   = target.getTargetData().getTypeSize(V->getType());
00580     unsigned destSize = target.getTargetData().getTypeSize(destType);
00581     uint64_t maskHi   = (destSize < 8)? (1U << 8*destSize) - 1 : ~0;
00582     assert(opSize <= 8 && destSize <= 8 && ">8-byte int type unexpected");
00583     
00584     if (destType->isSigned()) {
00585       if (opSize > destSize)            // operand is larger than dest:
00586         C = C & maskHi;                 // mask high bits
00587 
00588       if (opSize > destSize ||
00589           (opSize == destSize && ! V->getType()->isSigned()))
00590         if (C & (1U << (8*destSize - 1)))
00591           C =  C | ~maskHi;             // sign-extend from destSize to 64 bits
00592     }
00593     else {
00594       if (opSize > destSize || (V->getType()->isSigned() && destSize < 8)) {
00595         // operand is larger than dest,
00596         //    OR both are equal but smaller than the full register size
00597         //       AND operand is signed, so it may have extra sign bits:
00598         // mask high bits
00599         C = C & maskHi;
00600       }
00601     }
00602   }
00603 
00604   return C;
00605 }
00606 
00607 /// CreateSETUWConst - Copy a 32-bit unsigned constant into the register
00608 /// `dest', using SETHI, OR in the worst case.  This function correctly emulates
00609 /// the SETUW pseudo-op for SPARC v9 (if argument isSigned == false). The
00610 /// isSigned=true case is used to implement SETSW without duplicating code. It
00611 /// optimizes some common cases:
00612 /// (1) Small value that fits in simm13 field of OR: don't need SETHI.
00613 /// (2) isSigned = true and C is a small negative signed value, i.e.,
00614 ///     high bits are 1, and the remaining bits fit in simm13(OR).
00615 static inline void
00616 CreateSETUWConst(uint32_t C,
00617                  Instruction* dest, std::vector<MachineInstr*>& mvec,
00618                  bool isSigned = false) {
00619   MachineInstr *miSETHI = NULL, *miOR = NULL;
00620 
00621   // In order to get efficient code, we should not generate the SETHI if
00622   // all high bits are 1 (i.e., this is a small signed value that fits in
00623   // the simm13 field of OR).  So we check for and handle that case specially.
00624   // NOTE: The value C = 0x80000000 is bad: sC < 0 *and* -sC < 0.
00625   //       In fact, sC == -sC, so we have to check for this explicitly.
00626   int32_t sC = (int32_t) C;
00627   bool smallNegValue =isSigned && sC < 0 && sC != -sC && -sC < (int32_t)MAXSIMM;
00628 
00629   // Set the high 22 bits in dest if non-zero and simm13 field of OR not enough
00630   if (!smallNegValue && (C & ~MAXLO) && C > MAXSIMM) {
00631     miSETHI = BuildMI(V9::SETHI, 2).addZImm(C).addRegDef(dest);
00632     miSETHI->getOperand(0).markHi32();
00633     mvec.push_back(miSETHI);
00634   }
00635   
00636   // Set the low 10 or 12 bits in dest.  This is necessary if no SETHI
00637   // was generated, or if the low 10 bits are non-zero.
00638   if (miSETHI==NULL || C & MAXLO) {
00639     if (miSETHI) {
00640       // unsigned value with high-order bits set using SETHI
00641       miOR = BuildMI(V9::ORi,3).addReg(dest).addZImm(C).addRegDef(dest);
00642       miOR->getOperand(1).markLo32();
00643     } else {
00644       // unsigned or small signed value that fits in simm13 field of OR
00645       assert(smallNegValue || (C & ~MAXSIMM) == 0);
00646       miOR = BuildMI(V9::ORi, 3).addMReg(SparcV9::g0)
00647         .addSImm(sC).addRegDef(dest);
00648     }
00649     mvec.push_back(miOR);
00650   }
00651   
00652   assert((miSETHI || miOR) && "Oops, no code was generated!");
00653 }
00654 
00655 /// CreateSETSWConst - Set a 32-bit signed constant in the register `dest',
00656 /// with sign-extension to 64 bits.  This uses SETHI, OR, SRA in the worst case.
00657 /// This function correctly emulates the SETSW pseudo-op for SPARC v9.  It
00658 /// optimizes the same cases as SETUWConst, plus:
00659 /// (1) SRA is not needed for positive or small negative values.
00660 /// 
00661 static inline void
00662 CreateSETSWConst(int32_t C,
00663                  Instruction* dest, std::vector<MachineInstr*>& mvec) {
00664   // Set the low 32 bits of dest
00665   CreateSETUWConst((uint32_t) C,  dest, mvec, /*isSigned*/true);
00666 
00667   // Sign-extend to the high 32 bits if needed.
00668   // NOTE: The value C = 0x80000000 is bad: -C == C and so -C is < MAXSIMM
00669   if (C < 0 && (C == -C || -C > (int32_t) MAXSIMM))
00670     mvec.push_back(BuildMI(V9::SRAi5,3).addReg(dest).addZImm(0).addRegDef(dest));
00671 }
00672 
00673 /// CreateSETXConst - Set a 64-bit signed or unsigned constant in the
00674 /// register `dest'.  Use SETUWConst for each 32 bit word, plus a
00675 /// left-shift-by-32 in between.  This function correctly emulates the SETX
00676 /// pseudo-op for SPARC v9.  It optimizes the same cases as SETUWConst for each
00677 /// 32 bit word.
00678 /// 
00679 static inline void
00680 CreateSETXConst(uint64_t C,
00681                 Instruction* tmpReg, Instruction* dest,
00682                 std::vector<MachineInstr*>& mvec) {
00683   assert(C > (unsigned int) ~0 && "Use SETUW/SETSW for 32-bit values!");
00684   
00685   MachineInstr* MI;
00686   
00687   // Code to set the upper 32 bits of the value in register `tmpReg'
00688   CreateSETUWConst((C >> 32), tmpReg, mvec);
00689   
00690   // Shift tmpReg left by 32 bits
00691   mvec.push_back(BuildMI(V9::SLLXi6, 3).addReg(tmpReg).addZImm(32)
00692                  .addRegDef(tmpReg));
00693   
00694   // Code to set the low 32 bits of the value in register `dest'
00695   CreateSETUWConst(C, dest, mvec);
00696   
00697   // dest = OR(tmpReg, dest)
00698   mvec.push_back(BuildMI(V9::ORr,3).addReg(dest).addReg(tmpReg).addRegDef(dest));
00699 }
00700 
00701 /// CreateSETUWLabel - Set a 32-bit constant (given by a symbolic label) in
00702 /// the register `dest'.
00703 /// 
00704 static inline void
00705 CreateSETUWLabel(Value* val,
00706                  Instruction* dest, std::vector<MachineInstr*>& mvec) {
00707   MachineInstr* MI;
00708   
00709   // Set the high 22 bits in dest
00710   MI = BuildMI(V9::SETHI, 2).addReg(val).addRegDef(dest);
00711   MI->getOperand(0).markHi32();
00712   mvec.push_back(MI);
00713   
00714   // Set the low 10 bits in dest
00715   MI = BuildMI(V9::ORr, 3).addReg(dest).addReg(val).addRegDef(dest);
00716   MI->getOperand(1).markLo32();
00717   mvec.push_back(MI);
00718 }
00719 
00720 /// CreateSETXLabel - Set a 64-bit constant (given by a symbolic label) in the
00721 /// register `dest'.
00722 /// 
00723 static inline void
00724 CreateSETXLabel(Value* val, Instruction* tmpReg,
00725                 Instruction* dest, std::vector<MachineInstr*>& mvec) {
00726   assert(isa<Constant>(val) && 
00727          "I only know about constant values and global addresses");
00728   
00729   MachineInstr* MI;
00730   
00731   MI = BuildMI(V9::SETHI, 2).addPCDisp(val).addRegDef(tmpReg);
00732   MI->getOperand(0).markHi64();
00733   mvec.push_back(MI);
00734   
00735   MI = BuildMI(V9::ORi, 3).addReg(tmpReg).addPCDisp(val).addRegDef(tmpReg);
00736   MI->getOperand(1).markLo64();
00737   mvec.push_back(MI);
00738   
00739   mvec.push_back(BuildMI(V9::SLLXi6, 3).addReg(tmpReg).addZImm(32)
00740                  .addRegDef(tmpReg));
00741   MI = BuildMI(V9::SETHI, 2).addPCDisp(val).addRegDef(dest);
00742   MI->getOperand(0).markHi32();
00743   mvec.push_back(MI);
00744   
00745   MI = BuildMI(V9::ORr, 3).addReg(dest).addReg(tmpReg).addRegDef(dest);
00746   mvec.push_back(MI);
00747   
00748   MI = BuildMI(V9::ORi, 3).addReg(dest).addPCDisp(val).addRegDef(dest);
00749   MI->getOperand(1).markLo32();
00750   mvec.push_back(MI);
00751 }
00752 
00753 /// CreateUIntSetInstruction - Create code to Set an unsigned constant in the
00754 /// register `dest'.  Uses CreateSETUWConst, CreateSETSWConst or CreateSETXConst
00755 /// as needed.  CreateSETSWConst is an optimization for the case that the
00756 /// unsigned value has all ones in the 33 high bits (so that sign-extension sets
00757 /// them all).
00758 /// 
00759 static inline void
00760 CreateUIntSetInstruction(uint64_t C, Instruction* dest,
00761                          std::vector<MachineInstr*>& mvec,
00762                          MachineCodeForInstruction& mcfi) {
00763   static const uint64_t lo32 = (uint32_t) ~0;
00764   if (C <= lo32)                        // High 32 bits are 0.  Set low 32 bits.
00765     CreateSETUWConst((uint32_t) C, dest, mvec);
00766   else if ((C & ~lo32) == ~lo32 && (C & (1U << 31))) {
00767     // All high 33 (not 32) bits are 1s: sign-extension will take care
00768     // of high 32 bits, so use the sequence for signed int
00769     CreateSETSWConst((int32_t) C, dest, mvec);
00770   } else if (C > lo32) {
00771     // C does not fit in 32 bits
00772     TmpInstruction* tmpReg = new TmpInstruction(mcfi, Type::IntTy);
00773     CreateSETXConst(C, tmpReg, dest, mvec);
00774   }
00775 }
00776 
00777 /// CreateIntSetInstruction - Create code to Set a signed constant in the
00778 /// register `dest'.  Really the same as CreateUIntSetInstruction.
00779 /// 
00780 static inline void
00781 CreateIntSetInstruction(int64_t C, Instruction* dest,
00782                         std::vector<MachineInstr*>& mvec,
00783                         MachineCodeForInstruction& mcfi) {
00784   CreateUIntSetInstruction((uint64_t) C, dest, mvec, mcfi);
00785 }
00786 
00787 /// MaxConstantsTableTy - Table mapping LLVM opcodes to the max. immediate
00788 /// constant usable for that operation in the SparcV9 backend. Used by
00789 /// ConstantMayNotFitInImmedField().
00790 /// 
00791 struct MaxConstantsTableTy {
00792   // Entry == 0 ==> no immediate constant field exists at all.
00793   // Entry >  0 ==> abs(immediate constant) <= Entry
00794   std::vector<int> tbl;
00795 
00796   int getMaxConstantForInstr (unsigned llvmOpCode);
00797   MaxConstantsTableTy ();
00798   unsigned size() const            { return tbl.size (); }
00799   int &operator[] (unsigned index) { return tbl[index];  }
00800 };
00801 
00802 int MaxConstantsTableTy::getMaxConstantForInstr(unsigned llvmOpCode) {
00803   int modelOpCode = -1;
00804 
00805   if (llvmOpCode >= Instruction::BinaryOpsBegin &&
00806       llvmOpCode <  Instruction::BinaryOpsEnd)
00807     modelOpCode = V9::ADDi;
00808   else
00809     switch(llvmOpCode) {
00810     case Instruction::Ret:   modelOpCode = V9::JMPLCALLi; break;
00811 
00812     case Instruction::Malloc:         
00813     case Instruction::Alloca:         
00814     case Instruction::GetElementPtr:  
00815     case Instruction::PHI:       
00816     case Instruction::Cast:
00817     case Instruction::Call:  modelOpCode = V9::ADDi; break;
00818 
00819     case Instruction::Shl:
00820     case Instruction::Shr:   modelOpCode = V9::SLLXi6; break;
00821 
00822     default: break;
00823     };
00824 
00825   return (modelOpCode < 0)? 0: SparcV9MachineInstrDesc[modelOpCode].maxImmedConst;
00826 }
00827 
00828 MaxConstantsTableTy::MaxConstantsTableTy () : tbl (Instruction::OtherOpsEnd) {
00829   unsigned op;
00830   assert(tbl.size() == Instruction::OtherOpsEnd &&
00831          "assignments below will be illegal!");
00832   for (op = Instruction::TermOpsBegin; op < Instruction::TermOpsEnd; ++op)
00833     tbl[op] = getMaxConstantForInstr(op);
00834   for (op = Instruction::BinaryOpsBegin; op < Instruction::BinaryOpsEnd; ++op)
00835     tbl[op] = getMaxConstantForInstr(op);
00836   for (op = Instruction::MemoryOpsBegin; op < Instruction::MemoryOpsEnd; ++op)
00837     tbl[op] = getMaxConstantForInstr(op);
00838   for (op = Instruction::OtherOpsBegin; op < Instruction::OtherOpsEnd; ++op)
00839     tbl[op] = getMaxConstantForInstr(op);
00840 }
00841 
00842 bool ConstantMayNotFitInImmedField(const Constant* CV, const Instruction* I) {
00843   // The one and only MaxConstantsTable, used only by this function.
00844   static MaxConstantsTableTy MaxConstantsTable;
00845 
00846   if (I->getOpcode() >= MaxConstantsTable.size()) // user-defined op (or bug!)
00847     return true;
00848 
00849   // can always use %g0
00850   if (isa<ConstantPointerNull>(CV) || isa<UndefValue>(CV))
00851     return false;
00852 
00853   if (isa<SwitchInst>(I)) // Switch instructions will be lowered!
00854     return false;
00855 
00856   if (const ConstantInt* CI = dyn_cast<ConstantInt>(CV))
00857     return labs((int64_t)CI->getRawValue()) > MaxConstantsTable[I->getOpcode()];
00858 
00859   if (isa<ConstantBool>(CV))
00860     return 1 > MaxConstantsTable[I->getOpcode()];
00861 
00862   return true;
00863 }
00864 
00865 /// ChooseLoadInstruction - Return the appropriate load instruction opcode
00866 /// based on the given LLVM value type.
00867 /// 
00868 static inline MachineOpCode ChooseLoadInstruction(const Type *DestTy) {
00869   switch (DestTy->getTypeID()) {
00870   case Type::BoolTyID:
00871   case Type::UByteTyID:   return V9::LDUBr;
00872   case Type::SByteTyID:   return V9::LDSBr;
00873   case Type::UShortTyID:  return V9::LDUHr;
00874   case Type::ShortTyID:   return V9::LDSHr;
00875   case Type::UIntTyID:    return V9::LDUWr;
00876   case Type::IntTyID:     return V9::LDSWr;
00877   case Type::PointerTyID:
00878   case Type::ULongTyID:
00879   case Type::LongTyID:    return V9::LDXr;
00880   case Type::FloatTyID:   return V9::LDFr;
00881   case Type::DoubleTyID:  return V9::LDDFr;
00882   default: assert(0 && "Invalid type for Load instruction");
00883   }
00884   return 0;
00885 }
00886 
00887 /// ChooseStoreInstruction - Return the appropriate store instruction opcode
00888 /// based on the given LLVM value type.
00889 /// 
00890 static inline MachineOpCode ChooseStoreInstruction(const Type *DestTy) {
00891   switch (DestTy->getTypeID()) {
00892   case Type::BoolTyID:
00893   case Type::UByteTyID:
00894   case Type::SByteTyID:   return V9::STBr;
00895   case Type::UShortTyID:
00896   case Type::ShortTyID:   return V9::STHr;
00897   case Type::UIntTyID:
00898   case Type::IntTyID:     return V9::STWr;
00899   case Type::PointerTyID:
00900   case Type::ULongTyID:
00901   case Type::LongTyID:    return V9::STXr;
00902   case Type::FloatTyID:   return V9::STFr;
00903   case Type::DoubleTyID:  return V9::STDFr;
00904   default: assert(0 && "Invalid type for Store instruction");
00905   }
00906   return 0;
00907 }
00908 
00909 static inline MachineOpCode ChooseAddInstructionByType(const Type* resultType) {
00910   MachineOpCode opCode = V9::INVALID_OPCODE;
00911   if (resultType->isIntegral() || isa<PointerType>(resultType)
00912       || isa<FunctionType>(resultType) || resultType == Type::LabelTy) {
00913     opCode = V9::ADDr;
00914   } else
00915     switch(resultType->getTypeID()) {
00916     case Type::FloatTyID:  opCode = V9::FADDS; break;
00917     case Type::DoubleTyID: opCode = V9::FADDD; break;
00918     default: assert(0 && "Invalid type for ADD instruction"); break; 
00919     }
00920   
00921   return opCode;
00922 }
00923 
00924 /// convertOpcodeFromRegToImm - Because the SparcV9 instruction selector likes
00925 /// to re-write operands to instructions, making them change from a Value*
00926 /// (virtual register) to a Constant* (making an immediate field), we need to
00927 /// change the opcode from a register-based instruction to an immediate-based
00928 /// instruction, hence this mapping.
00929 /// 
00930 static unsigned convertOpcodeFromRegToImm(unsigned Opcode) {
00931   switch (Opcode) {
00932     /* arithmetic */
00933   case V9::ADDr:     return V9::ADDi;
00934   case V9::ADDccr:   return V9::ADDcci;
00935   case V9::ADDCr:    return V9::ADDCi;
00936   case V9::ADDCccr:  return V9::ADDCcci;
00937   case V9::SUBr:     return V9::SUBi;
00938   case V9::SUBccr:   return V9::SUBcci;
00939   case V9::SUBCr:    return V9::SUBCi;
00940   case V9::SUBCccr:  return V9::SUBCcci;
00941   case V9::MULXr:    return V9::MULXi;
00942   case V9::SDIVXr:   return V9::SDIVXi;
00943   case V9::UDIVXr:   return V9::UDIVXi;
00944 
00945     /* logical */
00946   case V9::ANDr:    return V9::ANDi;
00947   case V9::ANDccr:  return V9::ANDcci;
00948   case V9::ANDNr:   return V9::ANDNi;
00949   case V9::ANDNccr: return V9::ANDNcci;
00950   case V9::ORr:     return V9::ORi;
00951   case V9::ORccr:   return V9::ORcci;
00952   case V9::ORNr:    return V9::ORNi;
00953   case V9::ORNccr:  return V9::ORNcci;
00954   case V9::XORr:    return V9::XORi;
00955   case V9::XORccr:  return V9::XORcci;
00956   case V9::XNORr:   return V9::XNORi;
00957   case V9::XNORccr: return V9::XNORcci;
00958 
00959     /* shift */
00960   case V9::SLLr5:   return V9::SLLi5;
00961   case V9::SRLr5:   return V9::SRLi5;
00962   case V9::SRAr5:   return V9::SRAi5;
00963   case V9::SLLXr6:  return V9::SLLXi6;
00964   case V9::SRLXr6:  return V9::SRLXi6;
00965   case V9::SRAXr6:  return V9::SRAXi6;
00966 
00967     /* Conditional move on int comparison with zero */
00968   case V9::MOVRZr:   return V9::MOVRZi;
00969   case V9::MOVRLEZr: return V9::MOVRLEZi;
00970   case V9::MOVRLZr:  return V9::MOVRLZi;
00971   case V9::MOVRNZr:  return V9::MOVRNZi;
00972   case V9::MOVRGZr:  return V9::MOVRGZi;
00973   case V9::MOVRGEZr: return V9::MOVRGEZi;
00974 
00975 
00976     /* Conditional move on int condition code */
00977   case V9::MOVAr:   return V9::MOVAi;
00978   case V9::MOVNr:   return V9::MOVNi;
00979   case V9::MOVNEr:  return V9::MOVNEi;
00980   case V9::MOVEr:   return V9::MOVEi;
00981   case V9::MOVGr:   return V9::MOVGi;
00982   case V9::MOVLEr:  return V9::MOVLEi;
00983   case V9::MOVGEr:  return V9::MOVGEi;
00984   case V9::MOVLr:   return V9::MOVLi;
00985   case V9::MOVGUr:  return V9::MOVGUi;
00986   case V9::MOVLEUr: return V9::MOVLEUi;
00987   case V9::MOVCCr:  return V9::MOVCCi;
00988   case V9::MOVCSr:  return V9::MOVCSi;
00989   case V9::MOVPOSr: return V9::MOVPOSi;
00990   case V9::MOVNEGr: return V9::MOVNEGi;
00991   case V9::MOVVCr:  return V9::MOVVCi;
00992   case V9::MOVVSr:  return V9::MOVVSi;
00993 
00994     /* Conditional move of int reg on fp condition code */
00995   case V9::MOVFAr:   return V9::MOVFAi;
00996   case V9::MOVFNr:   return V9::MOVFNi;
00997   case V9::MOVFUr:   return V9::MOVFUi;
00998   case V9::MOVFGr:   return V9::MOVFGi;
00999   case V9::MOVFUGr:  return V9::MOVFUGi;
01000   case V9::MOVFLr:   return V9::MOVFLi;
01001   case V9::MOVFULr:  return V9::MOVFULi;
01002   case V9::MOVFLGr:  return V9::MOVFLGi;
01003   case V9::MOVFNEr:  return V9::MOVFNEi;
01004   case V9::MOVFEr:   return V9::MOVFEi;
01005   case V9::MOVFUEr:  return V9::MOVFUEi;
01006   case V9::MOVFGEr:  return V9::MOVFGEi;
01007   case V9::MOVFUGEr: return V9::MOVFUGEi;
01008   case V9::MOVFLEr:  return V9::MOVFLEi;
01009   case V9::MOVFULEr: return V9::MOVFULEi;
01010   case V9::MOVFOr:   return V9::MOVFOi;
01011 
01012     /* load */
01013   case V9::LDSBr:   return V9::LDSBi;
01014   case V9::LDSHr:   return V9::LDSHi;
01015   case V9::LDSWr:   return V9::LDSWi;
01016   case V9::LDUBr:   return V9::LDUBi;
01017   case V9::LDUHr:   return V9::LDUHi;
01018   case V9::LDUWr:   return V9::LDUWi;
01019   case V9::LDXr:    return V9::LDXi;
01020   case V9::LDFr:    return V9::LDFi;
01021   case V9::LDDFr:   return V9::LDDFi;
01022   case V9::LDQFr:   return V9::LDQFi;
01023   case V9::LDFSRr:  return V9::LDFSRi;
01024   case V9::LDXFSRr: return V9::LDXFSRi;
01025 
01026     /* store */
01027   case V9::STBr:    return V9::STBi;
01028   case V9::STHr:    return V9::STHi;
01029   case V9::STWr:    return V9::STWi;
01030   case V9::STXr:    return V9::STXi;
01031   case V9::STFr:    return V9::STFi;
01032   case V9::STDFr:   return V9::STDFi;
01033   case V9::STFSRr:  return V9::STFSRi;
01034   case V9::STXFSRr: return V9::STXFSRi;
01035 
01036     /* jump & return */
01037   case V9::JMPLCALLr: return V9::JMPLCALLi;
01038   case V9::JMPLRETr:  return V9::JMPLRETi;
01039 
01040   /* save and restore */
01041   case V9::SAVEr:     return V9::SAVEi;
01042   case V9::RESTOREr:  return V9::RESTOREi;
01043 
01044   default:
01045     // It's already in correct format
01046     // Or, it's just not handled yet, but an assert() would break LLC
01047 #if 0
01048     std::cerr << "Unhandled opcode in convertOpcodeFromRegToImm(): " << Opcode 
01049               << "\n";
01050 #endif
01051     return Opcode;
01052   }
01053 }
01054 
01055 /// CreateCodeToLoadConst - Create an instruction sequence to put the
01056 /// constant `val' into the virtual register `dest'.  `val' may be a Constant or
01057 /// a GlobalValue, viz., the constant address of a global variable or function.
01058 /// The generated instructions are returned in `mvec'. Any temp. registers
01059 /// (TmpInstruction) created are recorded in mcfi. Any stack space required is
01060 /// allocated via MachineFunction.
01061 /// 
01062 void CreateCodeToLoadConst(const TargetMachine& target, Function* F,
01063                            Value* val, Instruction* dest,
01064                            std::vector<MachineInstr*>& mvec,
01065                            MachineCodeForInstruction& mcfi) {
01066   assert(isa<Constant>(val) &&
01067          "I only know about constant values and global addresses");
01068   
01069   // Use a "set" instruction for known constants or symbolic constants (labels)
01070   // that can go in an integer reg.
01071   // We have to use a "load" instruction for all other constants,
01072   // in particular, floating point constants.
01073   const Type* valType = val->getType();
01074   
01075   if (isa<GlobalValue>(val)) {
01076       TmpInstruction* tmpReg =
01077         new TmpInstruction(mcfi, PointerType::get(val->getType()), val);
01078       CreateSETXLabel(val, tmpReg, dest, mvec);
01079       return;
01080   }
01081 
01082   bool isValid;
01083   uint64_t C = ConvertConstantToIntType(target, val, dest->getType(), isValid);
01084   if (isValid) {
01085     if (dest->getType()->isSigned())
01086       CreateUIntSetInstruction(C, dest, mvec, mcfi);
01087     else
01088       CreateIntSetInstruction((int64_t) C, dest, mvec, mcfi);
01089 
01090   } else {
01091     // Make an instruction sequence to load the constant, viz:
01092     //            SETX <addr-of-constant>, tmpReg, addrReg
01093     //            LOAD  /*addr*/ addrReg, /*offset*/ 0, dest
01094     // First, create a tmp register to be used by the SETX sequence.
01095     TmpInstruction* tmpReg =
01096       new TmpInstruction(mcfi, PointerType::get(val->getType()));
01097       
01098     // Create another TmpInstruction for the address register
01099     TmpInstruction* addrReg =
01100       new TmpInstruction(mcfi, PointerType::get(val->getType()));
01101     
01102     // Get the constant pool index for this constant
01103     MachineConstantPool *CP = MachineFunction::get(F).getConstantPool();
01104     Constant *C = cast<Constant>(val);
01105     unsigned CPI = CP->getConstantPoolIndex(C);
01106 
01107     // Put the address of the constant into a register
01108     MachineInstr* MI;
01109   
01110     MI = BuildMI(V9::SETHI, 2).addConstantPoolIndex(CPI).addRegDef(tmpReg);
01111     MI->getOperand(0).markHi64();
01112     mvec.push_back(MI);
01113   
01114     //Create another tmp register for the SETX sequence to preserve SSA
01115     TmpInstruction* tmpReg2 =
01116       new TmpInstruction(mcfi, PointerType::get(val->getType()));
01117     
01118     MI = BuildMI(V9::ORi, 3).addReg(tmpReg).addConstantPoolIndex(CPI)
01119       .addRegDef(tmpReg2);
01120     MI->getOperand(1).markLo64();
01121     mvec.push_back(MI);
01122   
01123     //Create another tmp register for the SETX sequence to preserve SSA
01124     TmpInstruction* tmpReg3 =
01125       new TmpInstruction(mcfi, PointerType::get(val->getType()));
01126 
01127     mvec.push_back(BuildMI(V9::SLLXi6, 3).addReg(tmpReg2).addZImm(32)
01128                    .addRegDef(tmpReg3));
01129     MI = BuildMI(V9::SETHI, 2).addConstantPoolIndex(CPI).addRegDef(addrReg);
01130     MI->getOperand(0).markHi32();
01131     mvec.push_back(MI);
01132   
01133     // Create another TmpInstruction for the address register
01134     TmpInstruction* addrReg2 =
01135       new TmpInstruction(mcfi, PointerType::get(val->getType()));
01136     
01137 
01138     MI = BuildMI(V9::ORr, 3).addReg(addrReg).addReg(tmpReg3).addRegDef(addrReg2);
01139     mvec.push_back(MI);
01140   
01141     // Create another TmpInstruction for the address register
01142     TmpInstruction* addrReg3 =
01143       new TmpInstruction(mcfi, PointerType::get(val->getType()));
01144 
01145     MI = BuildMI(V9::ORi, 3).addReg(addrReg2).addConstantPoolIndex(CPI)
01146       .addRegDef(addrReg3);
01147     MI->getOperand(1).markLo32();
01148     mvec.push_back(MI);
01149 
01150     // Now load the constant from out ConstantPool label
01151     unsigned Opcode = ChooseLoadInstruction(val->getType());
01152     Opcode = convertOpcodeFromRegToImm(Opcode);
01153     mvec.push_back(BuildMI(Opcode, 3)
01154                    .addReg(addrReg3).addSImm((int64_t)0).addRegDef(dest));
01155   }
01156 }
01157 
01158 /// CreateCodeToCopyFloatToInt - Similarly, create an instruction sequence
01159 /// to copy an FP register `val' to an integer register `dest' by copying to
01160 /// memory and back.  The generated instructions are returned in `mvec'.  Any
01161 /// temp. virtual registers (TmpInstruction) created are recorded in mcfi.
01162 /// Temporary stack space required is allocated via MachineFunction.
01163 /// 
01164 void CreateCodeToCopyFloatToInt(const TargetMachine& target, Function* F,
01165                                 Value* val, Instruction* dest,
01166                                 std::vector<MachineInstr*>& mvec,
01167                                 MachineCodeForInstruction& mcfi) {
01168   const Type* opTy   = val->getType();
01169   const Type* destTy = dest->getType();
01170   assert(opTy->isFloatingPoint() && "Source type must be float/double");
01171   assert((destTy->isIntegral() || isa<PointerType>(destTy))
01172          && "Dest type must be integer, bool or pointer");
01173 
01174   // FIXME: For now, we allocate permanent space because the stack frame
01175   // manager does not allow locals to be allocated (e.g., for alloca) after
01176   // a temp is allocated!
01177   int offset = MachineFunction::get(F).getInfo<SparcV9FunctionInfo>()->allocateLocalVar(val); 
01178 
01179   unsigned FPReg = target.getRegInfo()->getFramePointer();
01180 
01181   // Store instruction stores `val' to [%fp+offset].
01182   // The store opCode is based only the source value being copied.
01183   unsigned StoreOpcode = ChooseStoreInstruction(opTy);
01184   StoreOpcode = convertOpcodeFromRegToImm(StoreOpcode);  
01185   mvec.push_back(BuildMI(StoreOpcode, 3)
01186                  .addReg(val).addMReg(FPReg).addSImm(offset));
01187 
01188   // Load instruction loads [%fp+offset] to `dest'.
01189   // The type of the load opCode is the integer type that matches the
01190   // source type in size:
01191   // On SparcV9: int for float, long for double.
01192   // Note that we *must* use signed loads even for unsigned dest types, to
01193   // ensure correct sign-extension for UByte, UShort or UInt:
01194   const Type* loadTy = (opTy == Type::FloatTy)? Type::IntTy : Type::LongTy;
01195   unsigned LoadOpcode = ChooseLoadInstruction(loadTy);
01196   LoadOpcode = convertOpcodeFromRegToImm(LoadOpcode);
01197   mvec.push_back(BuildMI(LoadOpcode, 3).addMReg(FPReg)
01198                  .addSImm(offset).addRegDef(dest));
01199 }
01200 
01201 /// CreateBitExtensionInstructions - Helper function for sign-extension and
01202 /// zero-extension. For SPARC v9, we sign-extend the given operand using SLL;
01203 /// SRA/SRL.
01204 /// 
01205 inline void
01206 CreateBitExtensionInstructions(bool signExtend, const TargetMachine& target,
01207                                Function* F, Value* srcVal, Value* destVal,
01208                                unsigned int numLowBits,
01209                                std::vector<MachineInstr*>& mvec,
01210                                MachineCodeForInstruction& mcfi) {
01211   MachineInstr* M;
01212 
01213   assert(numLowBits <= 32 && "Otherwise, nothing should be done here!");
01214 
01215   if (numLowBits < 32) {
01216     // SLL is needed since operand size is < 32 bits.
01217     TmpInstruction *tmpI = new TmpInstruction(mcfi, destVal->getType(),
01218                                               srcVal, destVal, "make32");
01219     mvec.push_back(BuildMI(V9::SLLXi6, 3).addReg(srcVal)
01220                    .addZImm(32-numLowBits).addRegDef(tmpI));
01221     srcVal = tmpI;
01222   }
01223 
01224   mvec.push_back(BuildMI(signExtend? V9::SRAi5 : V9::SRLi5, 3)
01225                  .addReg(srcVal).addZImm(32-numLowBits).addRegDef(destVal));
01226 }
01227 
01228 /// CreateSignExtensionInstructions - Create instruction sequence to produce
01229 /// a sign-extended register value from an arbitrary-sized integer value (sized
01230 /// in bits, not bytes). The generated instructions are returned in `mvec'. Any
01231 /// temp. registers (TmpInstruction) created are recorded in mcfi. Any stack
01232 /// space required is allocated via MachineFunction.
01233 /// 
01234 void CreateSignExtensionInstructions(const TargetMachine& target,
01235                                      Function* F, Value* srcVal, Value* destVal,
01236                                      unsigned int numLowBits,
01237                                      std::vector<MachineInstr*>& mvec,
01238                                      MachineCodeForInstruction& mcfi) {
01239   CreateBitExtensionInstructions(/*signExtend*/ true, target, F, srcVal,
01240                                  destVal, numLowBits, mvec, mcfi);
01241 }
01242 
01243 /// CreateZeroExtensionInstructions - Create instruction sequence to produce
01244 /// a zero-extended register value from an arbitrary-sized integer value (sized
01245 /// in bits, not bytes).  For SPARC v9, we sign-extend the given operand using
01246 /// SLL; SRL.  The generated instructions are returned in `mvec'.  Any temp.
01247 /// registers (TmpInstruction) created are recorded in mcfi.  Any stack space
01248 /// required is allocated via MachineFunction.
01249 /// 
01250 void CreateZeroExtensionInstructions(const TargetMachine& target,
01251                                      Function* F, Value* srcVal, Value* destVal,
01252                                      unsigned int numLowBits,
01253                                      std::vector<MachineInstr*>& mvec,
01254                                      MachineCodeForInstruction& mcfi) {
01255   CreateBitExtensionInstructions(/*signExtend*/ false, target, F, srcVal,
01256                                  destVal, numLowBits, mvec, mcfi);
01257 }
01258 
01259 /// CreateCodeToCopyIntToFloat - Create an instruction sequence to copy an
01260 /// integer register `val' to a floating point register `dest' by copying to
01261 /// memory and back. val must be an integral type.  dest must be a Float or
01262 /// Double. The generated instructions are returned in `mvec'. Any temp.
01263 /// registers (TmpInstruction) created are recorded in mcfi. Any stack space
01264 /// required is allocated via MachineFunction.
01265 ///
01266 void CreateCodeToCopyIntToFloat(const TargetMachine& target,
01267                                 Function* F, Value* val, Instruction* dest,
01268                                 std::vector<MachineInstr*>& mvec,
01269                                 MachineCodeForInstruction& mcfi) {
01270   assert((val->getType()->isIntegral() || isa<PointerType>(val->getType()))
01271          && "Source type must be integral (integer or bool) or pointer");
01272   assert(dest->getType()->isFloatingPoint()
01273          && "Dest type must be float/double");
01274 
01275   // Get a stack slot to use for the copy
01276   int offset = MachineFunction::get(F).getInfo<SparcV9FunctionInfo>()->allocateLocalVar(val);
01277 
01278   // Get the size of the source value being copied. 
01279   size_t srcSize = target.getTargetData().getTypeSize(val->getType());
01280 
01281   // Store instruction stores `val' to [%fp+offset].
01282   // The store and load opCodes are based on the size of the source value.
01283   // If the value is smaller than 32 bits, we must sign- or zero-extend it
01284   // to 32 bits since the load-float will load 32 bits.
01285   // Note that the store instruction is the same for signed and unsigned ints.
01286   const Type* storeType = (srcSize <= 4)? Type::IntTy : Type::LongTy;
01287   Value* storeVal = val;
01288   if (srcSize < target.getTargetData().getTypeSize(Type::FloatTy)) {
01289     // sign- or zero-extend respectively
01290     storeVal = new TmpInstruction(mcfi, storeType, val);
01291     if (val->getType()->isSigned())
01292       CreateSignExtensionInstructions(target, F, val, storeVal, 8*srcSize,
01293                                       mvec, mcfi);
01294     else
01295       CreateZeroExtensionInstructions(target, F, val, storeVal, 8*srcSize,
01296                                       mvec, mcfi);
01297   }
01298 
01299   unsigned FPReg = target.getRegInfo()->getFramePointer();
01300   unsigned StoreOpcode = ChooseStoreInstruction(storeType);
01301   StoreOpcode = convertOpcodeFromRegToImm(StoreOpcode);
01302   mvec.push_back(BuildMI(StoreOpcode, 3)
01303                  .addReg(storeVal).addMReg(FPReg).addSImm(offset));
01304 
01305   // Load instruction loads [%fp+offset] to `dest'.
01306   // The type of the load opCode is the floating point type that matches the
01307   // stored type in size:
01308   // On SparcV9: float for int or smaller, double for long.
01309   const Type* loadType = (srcSize <= 4)? Type::FloatTy : Type::DoubleTy;
01310   unsigned LoadOpcode = ChooseLoadInstruction(loadType);
01311   LoadOpcode = convertOpcodeFromRegToImm(LoadOpcode);
01312   mvec.push_back(BuildMI(LoadOpcode, 3)
01313                  .addMReg(FPReg).addSImm(offset).addRegDef(dest));
01314 }
01315 
01316 /// InsertCodeToLoadConstant - Generates code to load the constant
01317 /// into a TmpInstruction (virtual reg) and returns the virtual register.
01318 /// 
01319 static TmpInstruction*
01320 InsertCodeToLoadConstant(Function *F, Value* opValue, Instruction* vmInstr,
01321                          std::vector<MachineInstr*>& loadConstVec,
01322                          TargetMachine& target) {
01323   // Create a tmp virtual register to hold the constant.
01324   MachineCodeForInstruction &mcfi = MachineCodeForInstruction::get(vmInstr);
01325   TmpInstruction* tmpReg = new TmpInstruction(mcfi, opValue);
01326   
01327   CreateCodeToLoadConst(target, F, opValue, tmpReg, loadConstVec, mcfi);
01328   
01329   // Record the mapping from the tmp VM instruction to machine instruction.
01330   // Do this for all machine instructions that were not mapped to any
01331   // other temp values created by 
01332   // tmpReg->addMachineInstruction(loadConstVec.back());
01333   return tmpReg;
01334 }
01335 
01336 MachineOperand::MachineOperandType
01337 ChooseRegOrImmed(int64_t intValue, bool isSigned,
01338                  MachineOpCode opCode, const TargetMachine& target,
01339                  bool canUseImmed, unsigned int& getMachineRegNum,
01340                  int64_t& getImmedValue) {
01341   MachineOperand::MachineOperandType opType=MachineOperand::MO_VirtualRegister;
01342   getMachineRegNum = 0;
01343   getImmedValue = 0;
01344 
01345   if (canUseImmed &&
01346       target.getInstrInfo()->constantFitsInImmedField(opCode, intValue)) {
01347       opType = isSigned? MachineOperand::MO_SignExtendedImmed
01348                        : MachineOperand::MO_UnextendedImmed;
01349       getImmedValue = intValue;
01350   } else if (intValue == 0 &&
01351              target.getRegInfo()->getZeroRegNum() != (unsigned)-1) {
01352     opType = MachineOperand::MO_MachineRegister;
01353     getMachineRegNum = target.getRegInfo()->getZeroRegNum();
01354   }
01355 
01356   return opType;
01357 }
01358 
01359 MachineOperand::MachineOperandType
01360 ChooseRegOrImmed(Value* val,
01361                  MachineOpCode opCode, const TargetMachine& target,
01362      bool canUseImmed, unsigned int& getMachineRegNum,
01363      int64_t& getImmedValue) {
01364   getMachineRegNum = 0;
01365   getImmedValue = 0;
01366 
01367   // To use reg or immed, constant needs to be integer, bool, or a NULL pointer.
01368   // ConvertConstantToIntType() does the right conversions.
01369   bool isValidConstant;
01370   uint64_t valueToUse =
01371     ConvertConstantToIntType(target, val, val->getType(), isValidConstant);
01372   if (! isValidConstant)
01373     return MachineOperand::MO_VirtualRegister;
01374 
01375   // Now check if the constant value fits in the IMMED field.
01376   return ChooseRegOrImmed((int64_t) valueToUse, val->getType()->isSigned(),
01377                           opCode, target, canUseImmed,
01378                           getMachineRegNum, getImmedValue);
01379 }
01380 
01381 /// CreateCopyInstructionsByType - Create instruction(s) to copy src to dest,
01382 /// for arbitrary types. The generated instructions are returned in `mvec'. Any
01383 /// temp. registers (TmpInstruction) created are recorded in mcfi. Any stack
01384 /// space required is allocated via MachineFunction.
01385 /// 
01386 void CreateCopyInstructionsByType(const TargetMachine& target,
01387                                   Function *F, Value* src, Instruction* dest,
01388                                   std::vector<MachineInstr*>& mvec,
01389                                   MachineCodeForInstruction& mcfi) {
01390   bool loadConstantToReg = false;
01391   const Type* resultType = dest->getType();
01392   MachineOpCode opCode = ChooseAddInstructionByType(resultType);
01393   assert (opCode != V9::INVALID_OPCODE
01394           && "Unsupported result type in CreateCopyInstructionsByType()");
01395 
01396   // If `src' is a constant that doesn't fit in the immed field or if it is
01397   // a global variable (i.e., a constant address), generate a load
01398   // instruction instead of an add.
01399   if (isa<GlobalValue>(src))
01400     loadConstantToReg = true;
01401   else if (isa<Constant>(src)) {
01402     unsigned int machineRegNum;
01403     int64_t immedValue;
01404     MachineOperand::MachineOperandType opType =
01405       ChooseRegOrImmed(src, opCode, target, /*canUseImmed*/ true,
01406                        machineRegNum, immedValue);
01407       
01408     if (opType == MachineOperand::MO_VirtualRegister)
01409       loadConstantToReg = true;
01410   }
01411   
01412   if (loadConstantToReg) { 
01413     // `src' is constant and cannot fit in immed field for the ADD.
01414     // Insert instructions to "load" the constant into a register.
01415     CreateCodeToLoadConst(target, F, src, dest, mvec, mcfi);
01416   } else { 
01417     // Create a reg-to-reg copy instruction for the given type:
01418     // -- For FP values, create a FMOVS or FMOVD instruction
01419     // -- For non-FP values, create an add-with-0 instruction (opCode as above)
01420     // Make `src' the second operand, in case it is a small constant!
01421     MachineInstr* MI;
01422     if (resultType->isFloatingPoint())
01423       MI = (BuildMI(resultType == Type::FloatTy? V9::FMOVS : V9::FMOVD, 2)
01424             .addReg(src).addRegDef(dest));
01425     else {
01426         const Type* Ty =isa<PointerType>(resultType)? Type::ULongTy :resultType;
01427         MI = (BuildMI(opCode, 3)
01428               .addSImm((int64_t) 0).addReg(src).addRegDef(dest));
01429     }
01430     mvec.push_back(MI);
01431   }
01432 }
01433 
01434 /// FixConstantOperandsForInstr - Make a machine instruction use its constant
01435 /// operands more efficiently.  If the constant is 0, then use the hardwired 0
01436 /// register, if any.  Else, if the constant fits in the IMMEDIATE field, then
01437 /// use that field.  Otherwise, else create instructions to put the constant
01438 /// into a register, either directly or by loading explicitly from the constant
01439 /// pool.  In the first 2 cases, the operand of `minstr' is modified in place.
01440 /// Returns a vector of machine instructions generated for operands that fall
01441 /// under case 3; these must be inserted before `minstr'.
01442 /// 
01443 std::vector<MachineInstr*>
01444 FixConstantOperandsForInstr(Instruction* vmInstr, MachineInstr* minstr,
01445                             TargetMachine& target) {
01446   std::vector<MachineInstr*> MVec;
01447   
01448   MachineOpCode opCode = minstr->getOpcode();
01449   const TargetInstrInfo& instrInfo = *target.getInstrInfo();
01450   int resultPos = instrInfo.get(opCode).resultPos;
01451   int immedPos = instrInfo.getImmedConstantPos(opCode);
01452 
01453   Function *F = vmInstr->getParent()->getParent();
01454 
01455   for (unsigned op=0; op < minstr->getNumOperands(); op++) {
01456       const MachineOperand& mop = minstr->getOperand(op);
01457           
01458       // Skip the result position, preallocated machine registers, or operands
01459       // that cannot be constants (CC regs or PC-relative displacements)
01460       if (resultPos == (int)op ||
01461           mop.getType() == MachineOperand::MO_MachineRegister ||
01462           mop.getType() == MachineOperand::MO_CCRegister ||
01463           mop.getType() == MachineOperand::MO_PCRelativeDisp)
01464         continue;
01465 
01466       bool constantThatMustBeLoaded = false;
01467       unsigned int machineRegNum = 0;
01468       int64_t immedValue = 0;
01469       Value* opValue = NULL;
01470       MachineOperand::MachineOperandType opType =
01471         MachineOperand::MO_VirtualRegister;
01472 
01473       // Operand may be a virtual register or a compile-time constant
01474       if (mop.getType() == MachineOperand::MO_VirtualRegister) {
01475         assert(mop.getVRegValue() != NULL);
01476         opValue = mop.getVRegValue();
01477         if (Constant *opConst = dyn_cast<Constant>(opValue)) 
01478           if (!isa<GlobalValue>(opConst)) {
01479             opType = ChooseRegOrImmed(opConst, opCode, target,
01480                                       (immedPos == (int)op), machineRegNum,
01481                                       immedValue);
01482             if (opType == MachineOperand::MO_VirtualRegister)
01483               constantThatMustBeLoaded = true;
01484           }
01485       } else {
01486         // If the operand is from the constant pool, don't try to change it.
01487         if (mop.getType() == MachineOperand::MO_ConstantPoolIndex) {
01488           continue;
01489         }
01490         assert(mop.isImmediate());
01491         bool isSigned = mop.getType() == MachineOperand::MO_SignExtendedImmed;
01492 
01493         // Bit-selection flags indicate an instruction that is extracting
01494         // bits from its operand so ignore this even if it is a big constant.
01495         if (mop.isHiBits32() || mop.isLoBits32() ||
01496             mop.isHiBits64() || mop.isLoBits64())
01497           continue;
01498 
01499         opType = ChooseRegOrImmed(mop.getImmedValue(), isSigned,
01500                                   opCode, target, (immedPos == (int)op), 
01501                                   machineRegNum, immedValue);
01502 
01503         if (opType == MachineOperand::MO_SignExtendedImmed ||
01504             opType == MachineOperand::MO_UnextendedImmed) {
01505           // The optype is an immediate value
01506           // This means we need to change the opcode, e.g. ADDr -> ADDi
01507           unsigned newOpcode = convertOpcodeFromRegToImm(opCode);
01508           minstr->setOpcode(newOpcode);
01509         }
01510 
01511         if (opType == mop.getType()) 
01512           continue;           // no change: this is the most common case
01513 
01514         if (opType == MachineOperand::MO_VirtualRegister) {
01515           constantThatMustBeLoaded = true;
01516           opValue = isSigned
01517             ? (Value*)ConstantSInt::get(Type::LongTy, immedValue)
01518             : (Value*)ConstantUInt::get(Type::ULongTy,(uint64_t)immedValue);
01519         }
01520       }
01521 
01522       if (opType == MachineOperand::MO_MachineRegister)
01523         minstr->SetMachineOperandReg(op, machineRegNum);
01524       else if (opType == MachineOperand::MO_SignExtendedImmed ||
01525                opType == MachineOperand::MO_UnextendedImmed) {
01526         minstr->SetMachineOperandConst(op, opType, immedValue);
01527         // The optype is or has become an immediate
01528         // This means we need to change the opcode, e.g. ADDr -> ADDi
01529         unsigned newOpcode = convertOpcodeFromRegToImm(opCode);
01530         minstr->setOpcode(newOpcode);
01531       } else if (constantThatMustBeLoaded ||
01532                (opValue && isa<GlobalValue>(opValue)))
01533         { // opValue is a constant that must be explicitly loaded into a reg
01534           assert(opValue);
01535           TmpInstruction* tmpReg = InsertCodeToLoadConstant(F, opValue, vmInstr,
01536                                                             MVec, target);
01537           minstr->SetMachineOperandVal(op, MachineOperand::MO_VirtualRegister,
01538                                        tmpReg);
01539         }
01540     }
01541   
01542   // Also, check for implicit operands used by the machine instruction
01543   // (no need to check those defined since they cannot be constants).
01544   // These include:
01545   // -- arguments to a Call
01546   // -- return value of a Return
01547   // Any such operand that is a constant value needs to be fixed also.
01548   // The current instructions with implicit refs (viz., Call and Return)
01549   // have no immediate fields, so the constant always needs to be loaded
01550   // into a register.
01551   bool isCall = instrInfo.isCall(opCode);
01552   unsigned lastCallArgNum = 0;          // unused if not a call
01553   CallArgsDescriptor* argDesc = NULL;   // unused if not a call
01554   if (isCall)
01555     argDesc = CallArgsDescriptor::get(minstr);
01556   
01557   for (unsigned i=0, N=minstr->getNumImplicitRefs(); i < N; ++i)
01558     if (isa<Constant>(minstr->getImplicitRef(i))) {
01559         Value* oldVal = minstr->getImplicitRef(i);
01560         TmpInstruction* tmpReg =
01561           InsertCodeToLoadConstant(F, oldVal, vmInstr, MVec, target);
01562         minstr->setImplicitRef(i, tmpReg);
01563         
01564         if (isCall) {
01565           // find and replace the argument in the CallArgsDescriptor
01566           unsigned i=lastCallArgNum;
01567           while (argDesc->getArgInfo(i).getArgVal() != oldVal)
01568             ++i;
01569           assert(i < argDesc->getNumArgs() &&
01570                  "Constant operands to a call *must* be in the arg list");
01571           lastCallArgNum = i;
01572           argDesc->getArgInfo(i).replaceArgVal(tmpReg);
01573         }
01574       }
01575   
01576   return MVec;
01577 }
01578 
01579 static inline void Add3OperandInstr(unsigned Opcode, InstructionNode* Node,
01580                                     std::vector<MachineInstr*>& mvec) {
01581   mvec.push_back(BuildMI(Opcode, 3).addReg(Node->leftChild()->getValue())
01582                                    .addReg(Node->rightChild()->getValue())
01583                                    .addRegDef(Node->getValue()));
01584 }
01585 
01586 /// IsZero - Check for a constant 0.
01587 ///
01588 static inline bool IsZero(Value* idx) {
01589   return (isa<Constant>(idx) && cast<Constant>(idx)->isNullValue()) ||
01590          isa<UndefValue>(idx);
01591 }
01592 
01593 /// FoldGetElemChain - Fold a chain of GetElementPtr instructions containing
01594 /// only constant offsets into an equivalent (Pointer, IndexVector) pair.
01595 /// Returns the pointer Value, and stores the resulting IndexVector in argument
01596 /// chainIdxVec. This is a helper function for FoldConstantIndices that does the
01597 /// actual folding.
01598 //
01599 static Value*
01600 FoldGetElemChain(InstrTreeNode* ptrNode, std::vector<Value*>& chainIdxVec,
01601                  bool lastInstHasLeadingNonZero) {
01602   InstructionNode* gepNode = dyn_cast<InstructionNode>(ptrNode);
01603   GetElementPtrInst* gepInst =
01604     dyn_cast_or_null<GetElementPtrInst>(gepNode ? gepNode->getInstruction() :0);
01605 
01606   // ptr value is not computed in this tree or ptr value does not come from GEP
01607   // instruction
01608   if (gepInst == NULL)
01609     return NULL;
01610 
01611   // Return NULL if we don't fold any instructions in.
01612   Value* ptrVal = NULL;
01613 
01614   // Now chase the chain of getElementInstr instructions, if any.
01615   // Check for any non-constant indices and stop there.
01616   // Also, stop if the first index of child is a non-zero array index
01617   // and the last index of the current node is a non-array index:
01618   // in that case, a non-array declared type is being accessed as an array
01619   // which is not type-safe, but could be legal.
01620   InstructionNode* ptrChild = gepNode;
01621   while (ptrChild && (ptrChild->getOpLabel() == Instruction::GetElementPtr ||
01622                       ptrChild->getOpLabel() == GetElemPtrIdx)) {
01623     // Child is a GetElemPtr instruction
01624     gepInst = cast<GetElementPtrInst>(ptrChild->getValue());
01625     User::op_iterator OI, firstIdx = gepInst->idx_begin();
01626     User::op_iterator lastIdx = gepInst->idx_end();
01627     bool allConstantOffsets = true;
01628 
01629     // The first index of every GEP must be an array index.
01630     assert((*firstIdx)->getType() == Type::LongTy &&
01631            "INTERNAL ERROR: Structure index for a pointer type!");
01632 
01633     // If the last instruction had a leading non-zero index, check if the
01634     // current one references a sequential (i.e., indexable) type.
01635     // If not, the code is not type-safe and we would create an illegal GEP
01636     // by folding them, so don't fold any more instructions.
01637     if (lastInstHasLeadingNonZero)
01638       if (! isa<SequentialType>(gepInst->getType()->getElementType()))
01639         break;   // cannot fold in any preceding getElementPtr instrs.
01640 
01641     // Check that all offsets are constant for this instruction
01642     for (OI = firstIdx; allConstantOffsets && OI != lastIdx; ++OI)
01643       allConstantOffsets = isa<ConstantInt>(*OI);
01644 
01645     if (allConstantOffsets) {
01646       // Get pointer value out of ptrChild.
01647       ptrVal = gepInst->getPointerOperand();
01648 
01649       // Insert its index vector at the start, skipping any leading [0]
01650       // Remember the old size to check if anything was inserted.
01651       unsigned oldSize = chainIdxVec.size();
01652       int firstIsZero = IsZero(*firstIdx);
01653       chainIdxVec.insert(chainIdxVec.begin(), firstIdx + firstIsZero, lastIdx);
01654 
01655       // Remember if it has leading zero index: it will be discarded later.
01656       if (oldSize < chainIdxVec.size())
01657         lastInstHasLeadingNonZero = !firstIsZero;
01658 
01659       // Mark the folded node so no code is generated for it.
01660       ((InstructionNode*) ptrChild)->markFoldedIntoParent();
01661 
01662       // Get the previous GEP instruction and continue trying to fold
01663       ptrChild = dyn_cast<InstructionNode>(ptrChild->leftChild());
01664     } else // cannot fold this getElementPtr instr. or any preceding ones
01665       break;
01666   }
01667 
01668   // If the first getElementPtr instruction had a leading [0], add it back.
01669   // Note that this instruction is the *last* one that was successfully
01670   // folded *and* contributed any indices, in the loop above.
01671   if (ptrVal && ! lastInstHasLeadingNonZero) 
01672     chainIdxVec.insert(chainIdxVec.begin(), ConstantSInt::get(Type::LongTy,0));
01673 
01674   return ptrVal;
01675 }
01676 
01677 /// GetGEPInstArgs - Helper function for GetMemInstArgs that handles the
01678 /// final getElementPtr instruction used by (or same as) the memory operation.
01679 /// Extracts the indices of the current instruction and tries to fold in
01680 /// preceding ones if all indices of the current one are constant.
01681 ///
01682 static Value *GetGEPInstArgs(InstructionNode *gepNode,
01683                              std::vector<Value *> &idxVec,
01684                              bool &allConstantIndices) {
01685   allConstantIndices = true;
01686   GetElementPtrInst* gepI = cast<GetElementPtrInst>(gepNode->getInstruction());
01687 
01688   // Default pointer is the one from the current instruction.
01689   Value* ptrVal = gepI->getPointerOperand();
01690   InstrTreeNode* ptrChild = gepNode->leftChild(); 
01691 
01692   // Extract the index vector of the GEP instruction.
01693   // If all indices are constant and first index is zero, try to fold
01694   // in preceding GEPs with all constant indices.
01695   for (User::op_iterator OI=gepI->idx_begin(),  OE=gepI->idx_end();
01696        allConstantIndices && OI != OE; ++OI)
01697     if (! isa<Constant>(*OI))
01698       allConstantIndices = false;     // note: this also terminates loop!
01699 
01700   // If we have only constant indices, fold chains of constant indices
01701   // in this and any preceding GetElemPtr instructions.
01702   bool foldedGEPs = false;
01703   bool leadingNonZeroIdx = gepI && ! IsZero(*gepI->idx_begin());
01704   if (allConstantIndices)
01705     if (Value* newPtr = FoldGetElemChain(ptrChild, idxVec, leadingNonZeroIdx)) {
01706       ptrVal = newPtr;
01707       foldedGEPs = true;
01708     }
01709 
01710   // Append the index vector of the current instruction.
01711   // Skip the leading [0] index if preceding GEPs were folded into this.
01712   idxVec.insert(idxVec.end(),
01713                 gepI->idx_begin() + (foldedGEPs && !leadingNonZeroIdx),
01714                 gepI->idx_end());
01715 
01716   return ptrVal;
01717 }
01718 
01719 /// GetMemInstArgs - Get the pointer value and the index vector for a memory
01720 /// operation (GetElementPtr, Load, or Store).  If all indices of the given
01721 /// memory operation are constant, fold in constant indices in a chain of
01722 /// preceding GetElementPtr instructions (if any), and return the pointer value
01723 /// of the first instruction in the chain. All folded instructions are marked so
01724 /// no code is generated for them. Returns the pointer Value to use, and
01725 /// returns the resulting IndexVector in idxVec. Sets allConstantIndices
01726 /// to true/false if all indices are/aren't const.
01727 /// 
01728 static Value *GetMemInstArgs(InstructionNode *memInstrNode,
01729                              std::vector<Value*> &idxVec,
01730                              bool& allConstantIndices) {
01731   allConstantIndices = false;
01732   Instruction* memInst = memInstrNode->getInstruction();
01733   assert(idxVec.size() == 0 && "Need empty vector to return indices");
01734 
01735   // If there is a GetElemPtr instruction to fold in to this instr,
01736   // it must be in the left child for Load and GetElemPtr, and in the
01737   // right child for Store instructions.
01738   InstrTreeNode* ptrChild = (memInst->getOpcode() == Instruction::Store
01739                              ? memInstrNode->rightChild()
01740                              : memInstrNode->leftChild()); 
01741   
01742   // Default pointer is the one from the current instruction.
01743   Value* ptrVal = ptrChild->getValue(); 
01744 
01745   // Find the "last" GetElemPtr instruction: this one or the immediate child.
01746   // There will be none if this is a load or a store from a scalar pointer.
01747   InstructionNode* gepNode = NULL;
01748   if (isa<GetElementPtrInst>(memInst))
01749     gepNode = memInstrNode;
01750   else if (isa<InstructionNode>(ptrChild) && isa<GetElementPtrInst>(ptrVal)) {
01751     // Child of load/store is a GEP and memInst is its only use.
01752     // Use its indices and mark it as folded.
01753     gepNode = cast<InstructionNode>(ptrChild);
01754     gepNode->markFoldedIntoParent();
01755   }
01756 
01757   // If there are no indices, return the current pointer.
01758   // Else extract the pointer from the GEP and fold the indices.
01759   return gepNode ? GetGEPInstArgs(gepNode, idxVec, allConstantIndices)
01760                  : ptrVal;
01761 }
01762 
01763 static inline MachineOpCode 
01764 ChooseBprInstruction(const InstructionNode* instrNode) {
01765   MachineOpCode opCode;
01766   
01767   Instruction* setCCInstr =
01768     ((InstructionNode*) instrNode->leftChild())->getInstruction();
01769   
01770   switch(setCCInstr->getOpcode()) {
01771   case Instruction::SetEQ: opCode = V9::BRZ;   break;
01772   case Instruction::SetNE: opCode = V9::BRNZ;  break;
01773   case Instruction::SetLE: opCode = V9::BRLEZ; break;
01774   case Instruction::SetGE: opCode = V9::BRGEZ; break;
01775   case Instruction::SetLT: opCode = V9::BRLZ;  break;
01776   case Instruction::SetGT: opCode = V9::BRGZ;  break;
01777   default:
01778     assert(0 && "Unrecognized VM instruction!");
01779     opCode = V9::INVALID_OPCODE;
01780     break; 
01781   }
01782   
01783   return opCode;
01784 }
01785 
01786 static inline MachineOpCode 
01787 ChooseBpccInstruction(const InstructionNode* instrNode,
01788                       const BinaryOperator* setCCInstr) {
01789   MachineOpCode opCode = V9::INVALID_OPCODE;
01790   
01791   bool isSigned = setCCInstr->getOperand(0)->getType()->isSigned();
01792   
01793   if (isSigned) {
01794     switch(setCCInstr->getOpcode()) {
01795     case Instruction::SetEQ: opCode = V9::BE;  break;
01796     case Instruction::SetNE: opCode = V9::BNE; break;
01797     case Instruction::SetLE: opCode = V9::BLE; break;
01798     case Instruction::SetGE: opCode = V9::BGE; break;
01799     case Instruction::SetLT: opCode = V9::BL;  break;
01800     case Instruction::SetGT: opCode = V9::BG;  break;
01801     default:
01802       assert(0 && "Unrecognized VM instruction!");
01803       break; 
01804     }
01805   } else {
01806     switch(setCCInstr->getOpcode()) {
01807     case Instruction::SetEQ: opCode = V9::BE;   break;
01808     case Instruction::SetNE: opCode = V9::BNE;  break;
01809     case Instruction::SetLE: opCode = V9::BLEU; break;
01810     case Instruction::SetGE: opCode = V9::BCC;  break;
01811     case Instruction::SetLT: opCode = V9::BCS;  break;
01812     case Instruction::SetGT: opCode = V9::BGU;  break;
01813     default:
01814       assert(0 && "Unrecognized VM instruction!");
01815       break; 
01816     }
01817   }
01818   
01819   return opCode;
01820 }
01821 
01822 static inline MachineOpCode 
01823 ChooseBFpccInstruction(const InstructionNode* instrNode,
01824                        const BinaryOperator* setCCInstr) {
01825   MachineOpCode opCode = V9::INVALID_OPCODE;
01826   
01827   switch(setCCInstr->getOpcode()) {
01828   case Instruction::SetEQ: opCode = V9::FBE;  break;
01829   case Instruction::SetNE: opCode = V9::FBNE; break;
01830   case Instruction::SetLE: opCode = V9::FBLE; break;
01831   case Instruction::SetGE: opCode = V9::FBGE; break;
01832   case Instruction::SetLT: opCode = V9::FBL;  break;
01833   case Instruction::SetGT: opCode = V9::FBG;  break;
01834   default:
01835     assert(0 && "Unrecognized VM instruction!");
01836     break; 
01837   }
01838   
01839   return opCode;
01840 }
01841 
01842 // GetTmpForCC - Create a unique TmpInstruction for a boolean value,
01843 // representing the CC register used by a branch on that value.
01844 // For now, hack this using a little static cache of TmpInstructions.
01845 // Eventually the entire BURG instruction selection should be put
01846 // into a separate class that can hold such information.
01847 // The static cache is not too bad because the memory for these
01848 // TmpInstructions will be freed along with the rest of the Function anyway.
01849 // 
01850 static TmpInstruction *GetTmpForCC (Value* boolVal, const Function *F,
01851                                     const Type* ccType,
01852                                     MachineCodeForInstruction& mcfi) {
01853   typedef hash_map<const Value*, TmpInstruction*> BoolTmpCache;
01854   static BoolTmpCache boolToTmpCache;     // Map boolVal -> TmpInstruction*
01855   static const Function *lastFunction = 0;// Use to flush cache between funcs
01856   
01857   assert(boolVal->getType() == Type::BoolTy && "Weird but ok! Delete assert");
01858   
01859   if (lastFunction != F) {
01860     lastFunction = F;
01861     boolToTmpCache.clear();
01862   }
01863   
01864   // Look for tmpI and create a new one otherwise.  The new value is
01865   // directly written to map using the ref returned by operator[].
01866   TmpInstruction*& tmpI = boolToTmpCache[boolVal];
01867   if (tmpI == NULL)
01868     tmpI = new TmpInstruction(mcfi, ccType, boolVal);
01869   
01870   return tmpI;
01871 }
01872 
01873 static inline MachineOpCode 
01874 ChooseBccInstruction(const InstructionNode* instrNode, const Type*& setCCType) {
01875   InstructionNode* setCCNode = (InstructionNode*) instrNode->leftChild();
01876   assert(setCCNode->getOpLabel() == SetCCOp);
01877   BinaryOperator* setCCInstr =cast<BinaryOperator>(setCCNode->getInstruction());
01878   setCCType = setCCInstr->getOperand(0)->getType();
01879   
01880   if (setCCType->isFloatingPoint())
01881     return ChooseBFpccInstruction(instrNode, setCCInstr);
01882   else
01883     return ChooseBpccInstruction(instrNode, setCCInstr);
01884 }
01885 
01886 /// ChooseMovFpcciInstruction - WARNING: since this function has only one
01887 /// caller, it always returns the opcode that expects an immediate and a
01888 /// register. If this function is ever used in cases where an opcode that takes
01889 /// two registers is required, then modify this function and use
01890 /// convertOpcodeFromRegToImm() where required. It will be necessary to expand
01891 /// convertOpcodeFromRegToImm() to handle the new cases of opcodes.
01892 /// 
01893 static inline MachineOpCode 
01894 ChooseMovFpcciInstruction(const InstructionNode* instrNode) {
01895   MachineOpCode opCode = V9::INVALID_OPCODE;
01896   
01897   switch(instrNode->getInstruction()->getOpcode()) {
01898   case Instruction::SetEQ: opCode = V9::MOVFEi;  break;
01899   case Instruction::SetNE: opCode = V9::MOVFNEi; break;
01900   case Instruction::SetLE: opCode = V9::MOVFLEi; break;
01901   case Instruction::SetGE: opCode = V9::MOVFGEi; break;
01902   case Instruction::SetLT: opCode = V9::MOVFLi;  break;
01903   case Instruction::SetGT: opCode = V9::MOVFGi;  break;
01904   default:
01905     assert(0 && "Unrecognized VM instruction!");
01906     break; 
01907   }
01908   
01909   return opCode;
01910 }
01911 
01912 /// ChooseMovpcciForSetCC -- Choose a conditional-move instruction
01913 /// based on the type of SetCC operation.
01914 /// 
01915 /// WARNING: like the previous function, this function always returns
01916 /// the opcode that expects an immediate and a register.  See above.
01917 /// 
01918 static MachineOpCode ChooseMovpcciForSetCC(const InstructionNode* instrNode) {
01919   MachineOpCode opCode = V9::INVALID_OPCODE;
01920 
01921   const Type* opType = instrNode->leftChild()->getValue()->getType();
01922   assert(opType->isIntegral() || isa<PointerType>(opType));
01923   bool noSign = opType->isUnsigned() || isa<PointerType>(opType);
01924   
01925   switch(instrNode->getInstruction()->getOpcode()) {
01926   case Instruction::SetEQ: opCode = V9::MOVEi;                        break;
01927   case Instruction::SetLE: opCode = noSign? V9::MOVLEUi : V9::MOVLEi; break;
01928   case Instruction::SetGE: opCode = noSign? V9::MOVCCi  : V9::MOVGEi; break;
01929   case Instruction::SetLT: opCode = noSign? V9::MOVCSi  : V9::MOVLi;  break;
01930   case Instruction::SetGT: opCode = noSign? V9::MOVGUi  : V9::MOVGi;  break;
01931   case Instruction::SetNE: opCode = V9::MOVNEi;                       break;
01932   default: assert(0 && "Unrecognized LLVM instr!"); break; 
01933   }
01934   
01935   return opCode;
01936 }
01937 
01938 /// ChooseMovpregiForSetCC -- Choose a conditional-move-on-register-value
01939 /// instruction based on the type of SetCC operation.  These instructions
01940 /// compare a register with 0 and perform the move is the comparison is true.
01941 /// 
01942 /// WARNING: like the previous function, this function it always returns
01943 /// the opcode that expects an immediate and a register.  See above.
01944 /// 
01945 static MachineOpCode ChooseMovpregiForSetCC(const InstructionNode* instrNode) {
01946   MachineOpCode opCode = V9::INVALID_OPCODE;
01947   
01948   switch(instrNode->getInstruction()->getOpcode()) {
01949   case Instruction::SetEQ: opCode = V9::MOVRZi;  break;
01950   case Instruction::SetLE: opCode = V9::MOVRLEZi; break;
01951   case Instruction::SetGE: opCode = V9::MOVRGEZi; break;
01952   case Instruction::SetLT: opCode = V9::MOVRLZi;  break;
01953   case Instruction::SetGT: opCode = V9::MOVRGZi;  break;
01954   case Instruction::SetNE: opCode = V9::MOVRNZi; break;
01955   default: assert(0 && "Unrecognized VM instr!"); break; 
01956   }
01957   
01958   return opCode;
01959 }
01960 
01961 static inline MachineOpCode
01962 ChooseConvertToFloatInstr(const TargetMachine& target,
01963                           OpLabel vopCode, const Type* opType) {
01964   assert((vopCode == ToFloatTy || vopCode == ToDoubleTy) &&
01965          "Unrecognized convert-to-float opcode!");
01966   assert((opType->isIntegral() || opType->isFloatingPoint() ||
01967           isa<PointerType>(opType))
01968          && "Trying to convert a non-scalar type to FLOAT/DOUBLE?");
01969 
01970   MachineOpCode opCode = V9::INVALID_OPCODE;
01971 
01972   unsigned opSize = target.getTargetData().getTypeSize(opType);
01973 
01974   if (opType == Type::FloatTy)
01975     opCode = (vopCode == ToFloatTy? V9::NOP : V9::FSTOD);
01976   else if (opType == Type::DoubleTy)
01977     opCode = (vopCode == ToFloatTy? V9::FDTOS : V9::NOP);
01978   else if (opSize <= 4)
01979     opCode = (vopCode == ToFloatTy? V9::FITOS : V9::FITOD);
01980   else {
01981     assert(opSize == 8 && "Unrecognized type size > 4 and < 8!");
01982     opCode = (vopCode == ToFloatTy? V9::FXTOS : V9::FXTOD);
01983   }
01984   
01985   return opCode;
01986 }
01987 
01988 static inline MachineOpCode 
01989 ChooseConvertFPToIntInstr(const TargetMachine& target,
01990                           const Type* destType, const Type* opType) {
01991   assert((opType == Type::FloatTy || opType == Type::DoubleTy)
01992          && "This function should only be called for FLOAT or DOUBLE");
01993   assert((destType->isIntegral() || isa<PointerType>(destType))
01994          && "Trying to convert FLOAT/DOUBLE to a non-scalar type?");
01995 
01996   MachineOpCode opCode = V9::INVALID_OPCODE;
01997 
01998   unsigned destSize = target.getTargetData().getTypeSize(destType);
01999 
02000   if (destType == Type::UIntTy)
02001     assert(destType != Type::UIntTy && "Expand FP-to-uint beforehand.");
02002   else if (destSize <= 4)
02003     opCode = (opType == Type::FloatTy)? V9::FSTOI : V9::FDTOI;
02004   else {
02005     assert(destSize == 8 && "Unrecognized type size > 4 and < 8!");
02006     opCode = (opType == Type::FloatTy)? V9::FSTOX : V9::FDTOX;
02007   }
02008 
02009   return opCode;
02010 }
02011 
02012 static MachineInstr*
02013 CreateConvertFPToIntInstr(const TargetMachine& target, Value* srcVal,
02014                           Value* destVal, const Type* destType) {
02015   MachineOpCode opCode = ChooseConvertFPToIntInstr(target, destType,
02016                                                    srcVal->getType());
02017   assert(opCode != V9::INVALID_OPCODE && "Expected to need conversion!");
02018   return BuildMI(opCode, 2).addReg(srcVal).addRegDef(destVal);
02019 }
02020 
02021 /// CreateCodeToConvertFloatToInt: Convert FP value to signed or unsigned
02022 /// integer.  The FP value must be converted to the dest type in an FP register,
02023 /// and the result is then copied from FP to int register via memory.  SPARC
02024 /// does not have a float-to-uint conversion, only a float-to-int (fdtoi).
02025 /// Since fdtoi converts to signed integers, any FP value V between MAXINT+1 and
02026 /// MAXUNSIGNED (i.e., 2^31 <= V <= 2^32-1) would be converted incorrectly.
02027 /// Therefore, for converting an FP value to uint32_t, we first need to convert
02028 /// to uint64_t and then to uint32_t.
02029 /// 
02030 static void
02031 CreateCodeToConvertFloatToInt(const TargetMachine& target,
02032                               Value* opVal, Instruction* destI,
02033                               std::vector<MachineInstr*>& mvec,
02034                               MachineCodeForInstruction& mcfi) {
02035   Function* F = destI->getParent()->getParent();
02036 
02037   // Create a temporary to represent the FP register into which the
02038   // int value will placed after conversion.  The type of this temporary
02039   // depends on the type of FP register to use: single-prec for a 32-bit
02040   // int or smaller; double-prec for a 64-bit int.
02041   size_t destSize = target.getTargetData().getTypeSize(destI->getType());
02042 
02043   const Type* castDestType = destI->getType(); // type for the cast instr result
02044   const Type* castDestRegType;          // type for cast instruction result reg
02045   TmpInstruction* destForCast;          // dest for cast instruction
02046   Instruction* fpToIntCopyDest = destI; // dest for fp-reg-to-int-reg copy instr
02047 
02048   // For converting an FP value to uint32_t, we first need to convert to
02049   // uint64_t and then to uint32_t, as explained above.
02050   if (destI->getType() == Type::UIntTy) {
02051     castDestType    = Type::ULongTy;       // use this instead of type of destI
02052     castDestRegType = Type::DoubleTy;      // uint64_t needs 64-bit FP register.
02053     destForCast     = new TmpInstruction(mcfi, castDestRegType, opVal);
02054     fpToIntCopyDest = new TmpInstruction(mcfi, castDestType, destForCast);
02055   } else {
02056     castDestRegType = (destSize > 4)? Type::DoubleTy : Type::FloatTy;
02057     destForCast = new TmpInstruction(mcfi, castDestRegType, opVal);
02058   }
02059 
02060   // Create the fp-to-int conversion instruction (src and dest regs are FP regs)
02061   mvec.push_back(CreateConvertFPToIntInstr(target, opVal, destForCast,
02062                                            castDestType));
02063 
02064   // Create the fpreg-to-intreg copy code
02065   CreateCodeToCopyFloatToInt(target, F, destForCast, fpToIntCopyDest, mvec,
02066                              mcfi);
02067 
02068   // Create the uint64_t to uint32_t conversion, if needed
02069   if (destI->getType() == Type::UIntTy)
02070     CreateZeroExtensionInstructions(target, F, fpToIntCopyDest, destI,
02071                                     /*numLowBits*/ 32, mvec, mcfi);
02072 }
02073 
02074 static inline MachineOpCode 
02075 ChooseAddInstruction(const InstructionNode* instrNode) {
02076   return ChooseAddInstructionByType(instrNode->getInstruction()->getType());
02077 }
02078 
02079 static inline MachineInstr* 
02080 CreateMovFloatInstruction(const InstructionNode* instrNode,
02081                           const Type* resultType) {
02082   return BuildMI((resultType == Type::FloatTy) ? V9::FMOVS : V9::FMOVD, 2)
02083                    .addReg(instrNode->leftChild()->getValue())
02084                    .addRegDef(instrNode->getValue());
02085 }
02086 
02087 static inline MachineInstr* 
02088 CreateAddConstInstruction(const InstructionNode* instrNode) {
02089   MachineInstr* minstr = NULL;
02090   
02091   Value* constOp = ((InstrTreeNode*) instrNode->rightChild())->getValue();
02092   assert(isa<Constant>(constOp));
02093   
02094   // Cases worth optimizing are:
02095   // (1) Add with 0 for float or double: use an FMOV of appropriate type,
02096   //   instead of an FADD (1 vs 3 cycles).  There is no integer MOV.
02097   if (ConstantFP *FPC = dyn_cast<ConstantFP>(constOp)) {
02098     double dval = FPC->getValue();
02099     if (dval == 0.0)
02100       minstr = CreateMovFloatInstruction(instrNode,
02101                                         instrNode->getInstruction()->getType());
02102   }
02103   
02104   return minstr;
02105 }
02106 
02107 static inline MachineOpCode ChooseSubInstructionByType(const Type* resultType) {
02108   MachineOpCode opCode = V9::INVALID_OPCODE;
02109   
02110   if (resultType->isInteger() || isa<PointerType>(resultType)) {
02111       opCode = V9::SUBr;
02112   } else {
02113     switch(resultType->getTypeID()) {
02114     case Type::FloatTyID:  opCode = V9::FSUBS; break;
02115     case Type::DoubleTyID: opCode = V9::FSUBD; break;
02116     default: assert(0 && "Invalid type for SUB instruction"); break; 
02117     }
02118   }
02119 
02120   return opCode;
02121 }
02122 
02123 static inline MachineInstr* 
02124 CreateSubConstInstruction(const InstructionNode* instrNode) {
02125   MachineInstr* minstr = NULL;
02126   
02127   Value* constOp = ((InstrTreeNode*) instrNode->rightChild())->getValue();
02128   assert(isa<Constant>(constOp));
02129   
02130   // Cases worth optimizing are:
02131   // (1) Sub with 0 for float or double: use an FMOV of appropriate type,
02132   //   instead of an FSUB (1 vs 3 cycles).  There is no integer MOV.
02133   if (ConstantFP *FPC = dyn_cast<ConstantFP>(constOp)) {
02134     double dval = FPC->getValue();
02135     if (dval == 0.0)
02136       minstr = CreateMovFloatInstruction(instrNode,
02137                                         instrNode->getInstruction()->getType());
02138   }
02139   
02140   return minstr;
02141 }
02142 
02143 static inline MachineOpCode 
02144 ChooseFcmpInstruction(const InstructionNode* instrNode) {
02145   MachineOpCode opCode = V9::INVALID_OPCODE;
02146   
02147   Value* operand = ((InstrTreeNode*) instrNode->leftChild())->getValue();
02148   switch(operand->getType()->getTypeID()) {
02149   case Type::FloatTyID:  opCode = V9::FCMPS; break;
02150   case Type::DoubleTyID: opCode = V9::FCMPD; break;
02151   default: assert(0 && "Invalid type for FCMP instruction"); break; 
02152   }
02153   
02154   return opCode;
02155 }
02156 
02157 /// BothFloatToDouble - Assumes that leftArg and rightArg of instrNode are both
02158 /// cast instructions. Returns true if both are floats cast to double.
02159 /// 
02160 static inline bool BothFloatToDouble(const InstructionNode* instrNode) {
02161   InstrTreeNode* leftArg = instrNode->leftChild();
02162   InstrTreeNode* rightArg = instrNode->rightChild();
02163   InstrTreeNode* leftArgArg = leftArg->leftChild();
02164   InstrTreeNode* rightArgArg = rightArg->leftChild();
02165   assert(leftArg->getValue()->getType() == rightArg->getValue()->getType());
02166   return (leftArg->getValue()->getType() == Type::DoubleTy &&
02167           leftArgArg->getValue()->getType() == Type::FloatTy &&
02168           rightArgArg->getValue()->getType() == Type::FloatTy);
02169 }
02170 
02171 static inline MachineOpCode ChooseMulInstructionByType(const Type* resultType) {
02172   MachineOpCode opCode = V9::INVALID_OPCODE;
02173   
02174   if (resultType->isInteger())
02175     opCode = V9::MULXr;
02176   else
02177     switch(resultType->getTypeID()) {
02178     case Type::FloatTyID:  opCode = V9::FMULS; break;
02179     case Type::DoubleTyID: opCode = V9::FMULD; break;
02180     default: assert(0 && "Invalid type for MUL instruction"); break; 
02181     }
02182   
02183   return opCode;
02184 }
02185 
02186 static inline MachineInstr*
02187 CreateIntNegInstruction(const TargetMachine& target, Value* vreg) {
02188   return BuildMI(V9::SUBr, 3).addMReg(target.getRegInfo()->getZeroRegNum())
02189     .addReg(vreg).addRegDef(vreg);
02190 }
02191 
02192 /// CreateShiftInstructions - Create instruction sequence for any shift
02193 /// operation. SLL or SLLX on an operand smaller than the integer reg. size
02194 /// (64bits) requires a second instruction for explicit sign-extension. Note
02195 /// that we only have to worry about a sign-bit appearing in the most
02196 /// significant bit of the operand after shifting (e.g., bit 32 of Int or bit 16
02197 /// of Short), so we do not have to worry about results that are as large as a
02198 /// normal integer register.
02199 /// 
02200 static inline void
02201 CreateShiftInstructions(const TargetMachine& target, Function* F,
02202                         MachineOpCode shiftOpCode, Value* argVal1,
02203                         Value* optArgVal2, /* Use optArgVal2 if not NULL */
02204                         unsigned optShiftNum, /* else use optShiftNum */
02205                         Instruction* destVal, std::vector<MachineInstr*>& mvec,
02206                         MachineCodeForInstruction& mcfi) {
02207   assert((optArgVal2 != NULL || optShiftNum <= 64) &&
02208          "Large shift sizes unexpected, but can be handled below: "
02209          "You need to check whether or not it fits in immed field below");
02210   
02211   // If this is a logical left shift of a type smaller than the standard
02212   // integer reg. size, we have to extend the sign-bit into upper bits
02213   // of dest, so we need to put the result of the SLL into a temporary.
02214   Value* shiftDest = destVal;
02215   unsigned opSize = target.getTargetData().getTypeSize(argVal1->getType());
02216 
02217   if ((shiftOpCode == V9::SLLr5 || shiftOpCode == V9::SLLXr6) && opSize < 8) {
02218     // put SLL result into a temporary
02219     shiftDest = new TmpInstruction(mcfi, argVal1, optArgVal2, "sllTmp");
02220   }
02221   
02222   MachineInstr* M = (optArgVal2 != NULL)
02223     ? BuildMI(shiftOpCode, 3).addReg(argVal1).addReg(optArgVal2)
02224                              .addReg(shiftDest, MachineOperand::Def)
02225     : BuildMI(shiftOpCode, 3).addReg(argVal1).addZImm(optShiftNum)
02226                              .addReg(shiftDest, MachineOperand::Def);
02227   mvec.push_back(M);
02228   
02229   if (shiftDest != destVal) {
02230     // extend the sign-bit of the result into all upper bits of dest
02231     assert(8*opSize <= 32 && "Unexpected type size > 4 and < IntRegSize?");
02232     CreateSignExtensionInstructions(target, F, shiftDest, destVal, 8*opSize,
02233                                     mvec, mcfi);
02234   }
02235 }
02236 
02237 /// CreateMulConstInstruction - Does not create any instructions if we
02238 /// cannot exploit constant to create a cheaper instruction. This returns the
02239 /// approximate cost of the instructions generated, which is used to pick the
02240 /// cheapest when both operands are constant.
02241 /// 
02242 static unsigned
02243 CreateMulConstInstruction(const TargetMachine &target, Function* F,
02244                           Value* lval, Value* rval, Instruction* destVal,
02245                           std::vector<MachineInstr*>& mvec,
02246                           MachineCodeForInstruction& mcfi) {
02247   // Use max. multiply cost, viz., cost of MULX
02248   unsigned cost = target.getInstrInfo()->minLatency(V9::MULXr);
02249   unsigned firstNewInstr = mvec.size();
02250   
02251   Value* constOp = rval;
02252   if (! isa<Constant>(constOp))
02253     return cost;
02254   
02255   // Cases worth optimizing are:
02256   // (1) Multiply by 0 or 1 for any type: replace with copy (ADD or FMOV)
02257   // (2) Multiply by 2^x for integer types: replace with Shift
02258   const Type* resultType = destVal->getType();
02259   
02260   if (resultType->isInteger() || isa<PointerType>(resultType)) {
02261     bool isValidConst;
02262     int64_t C = (int64_t) ConvertConstantToIntType(target, constOp,
02263                                                    constOp->getType(),
02264                                                    isValidConst);
02265     if (isValidConst) {
02266       unsigned pow;
02267       bool needNeg = false;
02268       if (C < 0) {
02269         needNeg = true;
02270         C = -C;
02271       }
02272           
02273       if (C == 0 || C == 1) {
02274         cost = target.getInstrInfo()->minLatency(V9::ADDr);
02275         unsigned Zero = target.getRegInfo()->getZeroRegNum();
02276         MachineInstr* M;
02277         if (C == 0)
02278           M =BuildMI(V9::ADDr,3).addMReg(Zero).addMReg(Zero).addRegDef(destVal);
02279         else
02280           M = BuildMI(V9::ADDr,3).addReg(lval).addMReg(Zero).addRegDef(destVal);
02281         mvec.push_back(M);
02282       } else if (isPowerOf2(C, pow)) {
02283         unsigned opSize = target.getTargetData().getTypeSize(resultType);
02284         MachineOpCode opCode = (opSize <= 32)? V9::SLLr5 : V9::SLLXr6;
02285         CreateShiftInstructions(target, F, opCode, lval, NULL, pow,
02286                                 destVal, mvec, mcfi);
02287       }
02288           
02289       if (mvec.size() > 0 && needNeg) {
02290         // insert <reg = SUB 0, reg> after the instr to flip the sign
02291         MachineInstr* M = CreateIntNegInstruction(target, destVal);
02292         mvec.push_back(M);
02293       }
02294     }
02295   } else {
02296     if (ConstantFP *FPC = dyn_cast<ConstantFP>(constOp)) {
02297       double dval = FPC->getValue();
02298       if (fabs(dval) == 1) {
02299         MachineOpCode opCode =  (dval < 0)
02300           ? (resultType == Type::FloatTy? V9::FNEGS : V9::FNEGD)
02301           : (resultType == Type::FloatTy? V9::FMOVS : V9::FMOVD);
02302         mvec.push_back(BuildMI(opCode,2).addReg(lval).addRegDef(destVal));
02303       } 
02304     }
02305   }
02306   
02307   if (firstNewInstr < mvec.size()) {
02308     cost = 0;
02309     for (unsigned i=firstNewInstr; i < mvec.size(); ++i)
02310       cost += target.getInstrInfo()->minLatency(mvec[i]->getOpcode());
02311   }
02312   
02313   return cost;
02314 }
02315 
02316 /// CreateCheapestMulConstInstruction - Does not create any instructions
02317 /// if we cannot exploit constant to create a cheaper instruction.
02318 ///
02319 static inline void
02320 CreateCheapestMulConstInstruction(const TargetMachine &target, Function* F,
02321                                   Value* lval, Value* rval,
02322                                   Instruction* destVal,
02323                                   std::vector<MachineInstr*>& mvec,
02324                                   MachineCodeForInstruction& mcfi) {
02325   Value* constOp;
02326   if (isa<Constant>(lval) && isa<Constant>(rval)) {
02327     // both operands are constant: evaluate and "set" in dest
02328     Constant* P = ConstantExpr::get(Instruction::Mul,
02329                                     cast<Constant>(lval),
02330                                     cast<Constant>(rval));
02331     CreateCodeToLoadConst (target, F, P, destVal, mvec, mcfi);
02332   }
02333   else if (isa<Constant>(rval))         // rval is constant, but not lval
02334     CreateMulConstInstruction(target, F, lval, rval, destVal, mvec, mcfi);
02335   else if (isa<Constant>(lval))         // lval is constant, but not rval
02336     CreateMulConstInstruction(target, F, lval, rval, destVal, mvec, mcfi);
02337   
02338   // else neither is constant
02339   return;
02340 }
02341 
02342 /// CreateMulInstruction - Returns NULL if we cannot exploit constant
02343 /// to create a cheaper instruction.
02344 /// 
02345 static inline void
02346 CreateMulInstruction(const TargetMachine &target, Function* F,
02347                      Value* lval, Value* rval, Instruction* destVal,
02348                      std::vector<MachineInstr*>& mvec,
02349                      MachineCodeForInstruction& mcfi,
02350                      MachineOpCode forceMulOp = -1) {
02351   unsigned L = mvec.size();
02352   CreateCheapestMulConstInstruction(target,F, lval, rval, destVal, mvec, mcfi);
02353   if (mvec.size() == L) {
02354     // no instructions were added so create MUL reg, reg, reg.
02355     // Use FSMULD if both operands are actually floats cast to doubles.
02356     // Otherwise, use the default opcode for the appropriate type.
02357     MachineOpCode mulOp = ((forceMulOp != -1)
02358                            ? forceMulOp 
02359                            : ChooseMulInstructionByType(destVal->getType()));
02360     mvec.push_back(BuildMI(mulOp, 3).addReg(lval).addReg(rval)
02361                    .addRegDef(destVal));
02362   }
02363 }
02364 
02365 /// ChooseDivInstruction - Generate a divide instruction for Div or Rem.
02366 /// For Rem, this assumes that the operand type will be signed if the result
02367 /// type is signed.  This is correct because they must have the same sign.
02368 /// 
02369 static inline MachineOpCode 
02370 ChooseDivInstruction(TargetMachine &target, const InstructionNode* instrNode) {
02371   MachineOpCode opCode = V9::INVALID_OPCODE;
02372   
02373   const Type* resultType = instrNode->getInstruction()->getType();
02374   
02375   if (resultType->isInteger())
02376     opCode = resultType->isSigned()? V9::SDIVXr : V9::UDIVXr;
02377   else
02378     switch(resultType->getTypeID()) {
02379       case Type::FloatTyID:  opCode = V9::FDIVS; break;
02380       case Type::DoubleTyID: opCode = V9::FDIVD; break;
02381       default: assert(0 && "Invalid type for DIV instruction"); break; 
02382       }
02383   
02384   return opCode;
02385 }
02386 
02387 /// CreateDivConstInstruction - Return if we cannot exploit constant to create
02388 /// a cheaper instruction.
02389 /// 
02390 static void CreateDivConstInstruction(TargetMachine &target,
02391                                       const InstructionNode* instrNode,
02392                                       std::vector<MachineInstr*>& mvec) {
02393   Value* LHS  = instrNode->leftChild()->getValue();
02394   Value* constOp = ((InstrTreeNode*) instrNode->rightChild())->getValue();
02395   if (!isa<Constant>(constOp))
02396     return;
02397 
02398   Instruction* destVal = instrNode->getInstruction();
02399   unsigned ZeroReg = target.getRegInfo()->getZeroRegNum();
02400   
02401   // Cases worth optimizing are:
02402   // (1) Divide by 1 for any type: replace with copy (ADD or FMOV)
02403   // (2) Divide by 2^x for integer types: replace with SR[L or A]{X}
02404   const Type* resultType = instrNode->getInstruction()->getType();
02405  
02406   if (resultType->isInteger()) {
02407     unsigned pow;
02408     bool isValidConst;
02409     int64_t C = (int64_t) ConvertConstantToIntType(target, constOp,
02410                                                    constOp->getType(),
02411                                                    isValidConst);
02412     if (isValidConst) {
02413       bool needNeg = false;
02414       if (C < 0) {
02415         needNeg = true;
02416         C = -C;
02417       }
02418       
02419       if (C == 1) {
02420         mvec.push_back(BuildMI(V9::ADDr, 3).addReg(LHS).addMReg(ZeroReg)
02421                        .addRegDef(destVal));
02422       } else if (isPowerOf2(C, pow)) {
02423         unsigned opCode;
02424         Value* shiftOperand;
02425         unsigned opSize = target.getTargetData().getTypeSize(resultType);
02426 
02427         if (resultType->isSigned()) {
02428           // For N / 2^k, if the operand N is negative,
02429           // we need to add (2^k - 1) before right-shifting by k, i.e.,
02430           // 
02431           //    (N / 2^k) = N >> k,               if N >= 0;
02432           //                (N + 2^k - 1) >> k,   if N < 0
02433           // 
02434           // If N is <= 32 bits, use:
02435           //    sra N, 31, t1           // t1 = ~0,         if N < 0,  0 else
02436           //    srl t1, 32-k, t2        // t2 = 2^k - 1,    if N < 0,  0 else
02437           //    add t2, N, t3           // t3 = N + 2^k -1, if N < 0,  N else
02438     //    sra t3, k, result       // result = N / 2^k
02439           // 
02440           // If N is 64 bits, use:
02441           //    srax N,  k-1,  t1       // t1 = sign bit in high k positions
02442           //    srlx t1, 64-k, t2       // t2 = 2^k - 1,    if N < 0,  0 else
02443           //    add t2, N, t3           // t3 = N + 2^k -1, if N < 0,  N else
02444     //    sra t3, k, result       // result = N / 2^k
02445           TmpInstruction *sraTmp, *srlTmp, *addTmp;
02446           MachineCodeForInstruction& mcfi
02447             = MachineCodeForInstruction::get(destVal);
02448           sraTmp = new TmpInstruction(mcfi, resultType, LHS, 0, "getSign");
02449           srlTmp = new TmpInstruction(mcfi, resultType, LHS, 0, "getPlus2km1");
02450           addTmp = new TmpInstruction(mcfi, resultType, LHS, srlTmp,"incIfNeg");
02451 
02452           // Create the SRA or SRAX instruction to get the sign bit
02453           mvec.push_back(BuildMI((opSize > 4)? V9::SRAXi6 : V9::SRAi5, 3)
02454                          .addReg(LHS)
02455                          .addSImm((resultType==Type::LongTy)? pow-1 : 31)
02456                          .addRegDef(sraTmp));
02457 
02458           // Create the SRL or SRLX instruction to get the sign bit
02459           mvec.push_back(BuildMI((opSize > 4)? V9::SRLXi6 : V9::SRLi5, 3)
02460                          .addReg(sraTmp)
02461                          .addSImm((resultType==Type::LongTy)? 64-pow : 32-pow)
02462                          .addRegDef(srlTmp));
02463 
02464           // Create the ADD instruction to add 2^pow-1 for negative values
02465           mvec.push_back(BuildMI(V9::ADDr, 3).addReg(LHS).addReg(srlTmp)
02466                          .addRegDef(addTmp));
02467 
02468           // Get the shift operand and "right-shift" opcode to do the divide
02469           shiftOperand = addTmp;
02470           opCode = (opSize > 4)? V9::SRAXi6 : V9::SRAi5;
02471         } else {
02472           // Get the shift operand and "right-shift" opcode to do the divide
02473           shiftOperand = LHS;
02474           opCode = (opSize > 4)? V9::SRLXi6 : V9::SRLi5;
02475         }
02476 
02477         // Now do the actual shift!
02478         mvec.push_back(BuildMI(opCode, 3).addReg(shiftOperand).addZImm(pow)
02479                        .addRegDef(destVal));
02480       }
02481           
02482       if (needNeg && (C == 1 || isPowerOf2(C, pow))) {
02483         // insert <reg = SUB 0, reg> after the instr to flip the sign
02484         mvec.push_back(CreateIntNegInstruction(target, destVal));
02485       }
02486     }
02487   } else {
02488     if (ConstantFP *FPC = dyn_cast<ConstantFP>(constOp)) {
02489       double dval = FPC->getValue();
02490       if (fabs(dval) == 1) {
02491         unsigned opCode = 
02492           (dval < 0) ? (resultType == Type::FloatTy? V9::FNEGS : V9::FNEGD)
02493           : (resultType == Type::FloatTy? V9::FMOVS : V9::FMOVD);
02494               
02495         mvec.push_back(BuildMI(opCode, 2).addReg(LHS).addRegDef(destVal));
02496       } 
02497     }
02498   }
02499 }
02500 
02501 static void CreateCodeForVariableSizeAlloca(const TargetMachine& target,
02502                                             Instruction* result, unsigned tsize,
02503                                             Value* numElementsVal,
02504                                             std::vector<MachineInstr*>& getMvec)
02505 {
02506   Value* totalSizeVal;
02507   MachineInstr* M;
02508   MachineCodeForInstruction& mcfi = MachineCodeForInstruction::get(result);
02509   Function *F = result->getParent()->getParent();
02510 
02511   // Enforce the alignment constraints on the stack pointer at
02512   // compile time if the total size is a known constant.
02513   if (isa<Constant>(numElementsVal)) {
02514     bool isValid;
02515     int64_t numElem = (int64_t)
02516       ConvertConstantToIntType(target, numElementsVal,
02517                                numElementsVal->getType(), isValid);
02518     assert(isValid && "Unexpectedly large array dimension in alloca!");
02519     int64_t total = numElem * tsize;
02520     if (int extra= total % SparcV9FrameInfo::StackFrameSizeAlignment)
02521       total += SparcV9FrameInfo::StackFrameSizeAlignment - extra;
02522     totalSizeVal = ConstantSInt::get(Type::IntTy, total);
02523   } else {
02524     // The size is not a constant.  Generate code to compute it and
02525     // code to pad the size for stack alignment.
02526     // Create a Value to hold the (constant) element size
02527     Value* tsizeVal = ConstantSInt::get(Type::IntTy, tsize);
02528 
02529     // Create temporary values to hold the result of MUL, SLL, SRL
02530     // To pad `size' to next smallest multiple of 16:
02531     //          size = (size + 15) & (-16 = 0xfffffffffffffff0)
02532     TmpInstruction* tmpProd = new TmpInstruction(mcfi,numElementsVal, tsizeVal);
02533     TmpInstruction* tmpAdd15= new TmpInstruction(mcfi,numElementsVal, tmpProd);
02534     TmpInstruction* tmpAndf0= new TmpInstruction(mcfi,numElementsVal, tmpAdd15);
02535 
02536     // Instruction 1: mul numElements, typeSize -> tmpProd
02537     // This will optimize the MUL as far as possible.
02538     CreateMulInstruction(target, F, numElementsVal, tsizeVal, tmpProd, getMvec,
02539                          mcfi, -1);
02540 
02541     // Instruction 2: andn tmpProd, 0x0f -> tmpAndn
02542     getMvec.push_back(BuildMI(V9::ADDi, 3).addReg(tmpProd).addSImm(15)
02543                       .addReg(tmpAdd15, MachineOperand::Def));
02544 
02545     // Instruction 3: add tmpAndn, 0x10 -> tmpAdd16
02546     getMvec.push_back(BuildMI(V9::ANDi, 3).addReg(tmpAdd15).addSImm(-16)
02547                       .addReg(tmpAndf0, MachineOperand::Def));
02548 
02549     totalSizeVal = tmpAndf0;
02550   }
02551 
02552   // Get the constant offset from SP for dynamically allocated storage
02553   // and create a temporary Value to hold it.
02554   MachineFunction& mcInfo = MachineFunction::get(F);
02555   bool growUp;
02556   ConstantSInt* dynamicAreaOffset =
02557     ConstantSInt::get(Type::IntTy,
02558                     target.getFrameInfo()->getDynamicAreaOffset(mcInfo,growUp));
02559   assert(! growUp && "Has SPARC v9 stack frame convention changed?");
02560 
02561   unsigned SPReg = target.getRegInfo()->getStackPointer();
02562 
02563   // Instruction 2: sub %sp, totalSizeVal -> %sp
02564   getMvec.push_back(BuildMI(V9::SUBr, 3).addMReg(SPReg).addReg(totalSizeVal)
02565                     .addMReg(SPReg,MachineOperand::Def));
02566 
02567   // Instruction 3: add %sp, frameSizeBelowDynamicArea -> result
02568   getMvec.push_back(BuildMI(V9::ADDr,3).addMReg(SPReg).addReg(dynamicAreaOffset)
02569                     .addRegDef(result));
02570 }        
02571 
02572 static void
02573 CreateCodeForFixedSizeAlloca(const TargetMachine& target,
02574                              Instruction* result, unsigned tsize,
02575                              unsigned numElements,
02576                              std::vector<MachineInstr*>& getMvec) {
02577   assert(result && result->getParent() &&
02578          "Result value is not part of a function?");
02579   Function *F = result->getParent()->getParent();
02580   MachineFunction &mcInfo = MachineFunction::get(F);
02581 
02582   // If the alloca is of zero bytes (which is perfectly legal) we bump it up to
02583   // one byte.  This is unnecessary, but I really don't want to break any
02584   // fragile logic in this code.  FIXME.
02585   if (tsize == 0)
02586     tsize = 1;
02587 
02588   // Put the variable in the dynamically sized area of the frame if either:
02589   // (a) The offset is too large to use as an immediate in load/stores
02590   //     (check LDX because all load/stores have the same-size immed. field).
02591   // (b) The object is "large", so it could cause many other locals,
02592   //     spills, and temporaries to have large offsets.
02593   //     NOTE: We use LARGE = 8 * argSlotSize = 64 bytes.
02594   // You've gotta love having only 13 bits for constant offset values :-|.
02595   // 
02596   unsigned paddedSize;
02597   int offsetFromFP = mcInfo.getInfo<SparcV9FunctionInfo>()->computeOffsetforLocalVar(result,
02598                                                                 paddedSize,
02599                                                          tsize * numElements);
02600 
02601   if (((int)paddedSize) > 8 * SparcV9FrameInfo::SizeOfEachArgOnStack ||
02602       !target.getInstrInfo()->constantFitsInImmedField(V9::LDXi,offsetFromFP)) {
02603     CreateCodeForVariableSizeAlloca(target, result, tsize, 
02604             ConstantSInt::get(Type::IntTy,numElements),
02605             getMvec);
02606     return;
02607   }
02608   
02609   // else offset fits in immediate field so go ahead and allocate it.
02610   offsetFromFP = mcInfo.getInfo<SparcV9FunctionInfo>()->allocateLocalVar(result, tsize *numElements);
02611   
02612   // Create a temporary Value to hold the constant offset.
02613   // This is needed because it may not fit in the immediate field.
02614   ConstantSInt* offsetVal = ConstantSInt::get(Type::IntTy, offsetFromFP);
02615   
02616   // Instruction 1: add %fp, offsetFromFP -> result
02617   unsigned FPReg = target.getRegInfo()->getFramePointer();
02618   getMvec.push_back(BuildMI(V9::ADDr, 3).addMReg(FPReg).addReg(offsetVal)
02619                     .addRegDef(result));
02620 }
02621 
02622 /// SetOperandsForMemInstr - Choose addressing mode for the given load or store
02623 /// instruction.  Use [reg+reg] if it is an indexed reference, and the index
02624 /// offset is not a constant or if it cannot fit in the offset field.  Use
02625 /// [reg+offset] in all other cases.  This assumes that all array refs are
02626 /// "lowered" to one of these forms:
02627 ///    %x = load (subarray*) ptr, constant  ; single constant offset
02628 ///    %x = load (subarray*) ptr, offsetVal ; single non-constant offset
02629 /// Generally, this should happen via strength reduction + LICM.  Also, strength
02630 /// reduction should take care of using the same register for the loop index
02631 /// variable and an array index, when that is profitable.
02632 ///
02633 static void SetOperandsForMemInstr(unsigned Opcode,
02634                                    std::vector<MachineInstr*>& mvec,
02635                                    InstructionNode* vmInstrNode,
02636                                    const TargetMachine& target) {
02637   Instruction* memInst = vmInstrNode->getInstruction();
02638   // Index vector, ptr value, and flag if all indices are const.
02639   std::vector<Value*> idxVec;
02640   bool allConstantIndices;
02641   Value* ptrVal = GetMemInstArgs(vmInstrNode, idxVec, allConstantIndices);
02642 
02643   // Now create the appropriate operands for the machine instruction.
02644   // First, initialize so we default to storing the offset in a register.
02645   int64_t smallConstOffset = 0;
02646   Value* valueForRegOffset = NULL;
02647   MachineOperand::MachineOperandType offsetOpType =
02648     MachineOperand::MO_VirtualRegister;
02649 
02650   // Check if there is an index vector and if so, compute the
02651   // right offset for structures and for arrays 
02652   if (!idxVec.empty()) {
02653     const PointerType* ptrType = cast<PointerType>(ptrVal->getType());
02654       
02655     // If all indices are constant, compute the combined offset directly.
02656     if (allConstantIndices) {
02657       // Compute the offset value using the index vector. Create a
02658       // virtual reg. for it since it may not fit in the immed field.
02659       uint64_t offset = target.getTargetData().getIndexedOffset(ptrType,idxVec);
02660       valueForRegOffset = ConstantSInt::get(Type::LongTy, offset);
02661     } else {
02662       // There is at least one non-constant offset.  Therefore, this must
02663       // be an array ref, and must have been lowered to a single non-zero
02664       // offset.  (An extra leading zero offset, if any, can be ignored.)
02665       // Generate code sequence to compute address from index.
02666       bool firstIdxIsZero = IsZero(idxVec[0]);
02667       assert(idxVec.size() == 1U + firstIdxIsZero 
02668              && "Array refs must be lowered before Instruction Selection");
02669 
02670       Value* idxVal = idxVec[firstIdxIsZero];
02671 
02672       std::vector<MachineInstr*> mulVec;
02673       Instruction* addr =
02674         new TmpInstruction(MachineCodeForInstruction::get(memInst),
02675                            Type::ULongTy, memInst);
02676 
02677       // Get the array type indexed by idxVal, and compute its element size.
02678       // The call to getTypeSize() will fail if size is not constant.
02679       const Type* vecType = (firstIdxIsZero
02680                              ? GetElementPtrInst::getIndexedType(ptrType,
02681                                            std::vector<Value*>(1U, idxVec[0]),
02682                                            /*AllowCompositeLeaf*/ true)
02683                                  : ptrType);
02684       const Type* eltType = cast<SequentialType>(vecType)->getElementType();
02685       ConstantUInt* eltSizeVal = ConstantUInt::get(Type::ULongTy,
02686                                    target.getTargetData().getTypeSize(eltType));
02687 
02688       // CreateMulInstruction() folds constants intelligently enough.
02689       CreateMulInstruction(target, memInst->getParent()->getParent(),
02690                            idxVal,         /* lval, not likely to be const*/
02691                            eltSizeVal,     /* rval, likely to be constant */
02692                            addr,           /* result */
02693                            mulVec, MachineCodeForInstruction::get(memInst),
02694                            -1);
02695 
02696       assert(mulVec.size() > 0 && "No multiply code created?");
02697       mvec.insert(mvec.end(), mulVec.begin(), mulVec.end());
02698       
02699       valueForRegOffset = addr;
02700     }
02701   } else {
02702     offsetOpType = MachineOperand::MO_SignExtendedImmed;
02703     smallConstOffset = 0;
02704   }
02705 
02706   // For STORE:
02707   //   Operand 0 is value, operand 1 is ptr, operand 2 is offset
02708   // For LOAD or GET_ELEMENT_PTR,
02709   //   Operand 0 is ptr, operand 1 is offset, operand 2 is result.
02710   unsigned offsetOpNum, ptrOpNum;
02711   MachineInstr *MI;
02712   if (memInst->getOpcode() == Instruction::Store) {
02713     if (offsetOpType == MachineOperand::MO_VirtualRegister) {
02714       MI = BuildMI(Opcode, 3).addReg(vmInstrNode->leftChild()->getValue())
02715                              .addReg(ptrVal).addReg(valueForRegOffset);
02716     } else {
02717       Opcode = convertOpcodeFromRegToImm(Opcode);
02718       MI = BuildMI(Opcode, 3).addReg(vmInstrNode->leftChild()->getValue())
02719                              .addReg(ptrVal).addSImm(smallConstOffset);
02720     }
02721   } else {
02722     if (offsetOpType == MachineOperand::MO_VirtualRegister) {
02723       MI = BuildMI(Opcode, 3).addReg(ptrVal).addReg(valueForRegOffset)
02724                              .addRegDef(memInst);
02725     } else {
02726       Opcode = convertOpcodeFromRegToImm(Opcode);
02727       MI = BuildMI(Opcode, 3).addReg(ptrVal).addSImm(smallConstOffset)
02728                              .addRegDef(memInst);
02729     }
02730   }
02731   mvec.push_back(MI);
02732 }
02733 
02734 /// ForwardOperand - Substitute operand `operandNum' of the instruction in
02735 /// node `treeNode' in place of the use(s) of that instruction in node `parent'.
02736 /// Check both explicit and implicit operands!  Also make sure to skip over a
02737 /// parent who: (1) is a list node in the Burg tree, or (2) itself had its
02738 /// results forwarded to its parent.
02739 /// 
02740 static void ForwardOperand (InstructionNode *treeNode, InstrTreeNode *parent,
02741                             int operandNum) {
02742   assert(treeNode && parent && "Invalid invocation of ForwardOperand");
02743   
02744   Instruction* unusedOp = treeNode->getInstruction();
02745   Value* fwdOp = unusedOp->getOperand(operandNum);
02746 
02747   // The parent itself may be a list node, so find the real parent instruction
02748   while (parent->getNodeType() != InstrTreeNode::NTInstructionNode) {
02749     parent = parent->parent();
02750     assert(parent && "ERROR: Non-instruction node has no parent in tree.");
02751   }
02752   InstructionNode* parentInstrNode = (InstructionNode*) parent;
02753   
02754   Instruction* userInstr = parentInstrNode->getInstruction();
02755   MachineCodeForInstruction &mvec = MachineCodeForInstruction::get(userInstr);
02756 
02757   // The parent's mvec would be empty if it was itself forwarded.
02758   // Recursively call ForwardOperand in that case...
02759   //
02760   if (mvec.size() == 0) {
02761     assert(parent->parent() != NULL &&
02762            "Parent could not have been forwarded, yet has no instructions?");
02763     ForwardOperand(treeNode, parent->parent(), operandNum);
02764   } else {
02765     for (unsigned i=0, N=mvec.size(); i < N; i++) {
02766       MachineInstr* minstr = mvec[i];
02767       for (unsigned i=0, numOps=minstr->getNumOperands(); i < numOps; ++i) {
02768         const MachineOperand& mop = minstr->getOperand(i);
02769         if (mop.getType() == MachineOperand::MO_VirtualRegister &&
02770             mop.getVRegValue() == unusedOp) {
02771           minstr->SetMachineOperandVal(i, MachineOperand::MO_VirtualRegister,
02772                                        fwdOp);
02773         }
02774       }
02775           
02776       for (unsigned i=0,numOps=minstr->getNumImplicitRefs(); i<numOps; ++i)
02777         if (minstr->getImplicitRef(i) == unusedOp)
02778           minstr->setImplicitRef(i, fwdOp);
02779     }
02780   }
02781 }
02782 
02783 /// AllUsesAreBranches - Returns true if all the uses of I are
02784 /// Branch instructions, false otherwise.
02785 /// 
02786 inline bool AllUsesAreBranches(const Instruction* I) {
02787   for (Value::use_const_iterator UI=I->use_begin(), UE=I->use_end();
02788        UI != UE; ++UI)
02789     if (! isa<TmpInstruction>(*UI)     // ignore tmp instructions here
02790         && cast<Instruction>(*UI)->getOpcode() != Instruction::Br)
02791       return false;
02792   return true;
02793 }
02794 
02795 /// CodeGenIntrinsic - Generate code for any intrinsic that needs a special
02796 /// code sequence instead of a regular call.  If not that kind of intrinsic, do
02797 /// nothing. Returns true if code was generated, otherwise false.
02798 /// 
02799 static bool CodeGenIntrinsic(Intrinsic::ID iid, CallInst &callInstr,
02800                              TargetMachine &target,
02801                              std::vector<MachineInstr*>& mvec) {
02802   switch (iid) {
02803   default:
02804     assert(0 && "Unknown intrinsic function call should have been lowered!");
02805   case Intrinsic::vastart: {
02806     // Get the address of the first incoming vararg argument on the stack
02807     Function* func = cast<Function>(callInstr.getParent()->getParent());
02808     int numFixedArgs   = func->getFunctionType()->getNumParams();
02809     int fpReg          = SparcV9::i6;
02810     int firstVarArgOff = numFixedArgs * 8 + 
02811                          SparcV9FrameInfo::FirstIncomingArgOffsetFromFP;
02812     mvec.push_back(BuildMI(V9::ADDi, 3).addMReg(fpReg).addSImm(firstVarArgOff).
02813                    addRegDef(&callInstr));
02814     return true;
02815   }
02816 
02817   case Intrinsic::vaend:
02818     return true;                        // no-op on SparcV9
02819 
02820   case Intrinsic::vacopy:
02821     // Simple copy of current va_list (arg1) to new va_list (result)
02822     mvec.push_back(BuildMI(V9::ORr, 3).
02823                    addMReg(target.getRegInfo()->getZeroRegNum()).
02824                    addReg(callInstr.getOperand(1)).
02825                    addRegDef(&callInstr));
02826     return true;
02827   }
02828 }
02829 
02830 /// ThisIsAChainRule - returns true if the given  BURG rule is a chain rule.
02831 /// 
02832 extern bool ThisIsAChainRule(int eruleno) {
02833   switch(eruleno) {
02834     case 111: // stmt:  reg
02835     case 123:
02836     case 124:
02837     case 125:
02838     case 126:
02839     case 127:
02840     case 128:
02841     case 129:
02842     case 130:
02843     case 131:
02844     case 132:
02845     case 133:
02846     case 155:
02847     case 221:
02848     case 222:
02849     case 241:
02850     case 242:
02851     case 243:
02852     case 244:
02853     case 245:
02854     case 321:
02855       return true; break;
02856 
02857     default:
02858       return false; break;
02859     }
02860 }
02861 
02862 /// GetInstructionsByRule - Choose machine instructions for the
02863 /// SPARC V9 according to the patterns chosen by the BURG-generated parser.
02864 /// This is where most of the work in the V9 instruction selector gets done.
02865 /// 
02866 void GetInstructionsByRule(InstructionNode* subtreeRoot, int ruleForNode,
02867                            short* nts, TargetMachine &target,
02868                            std::vector<MachineInstr*>& mvec) {
02869   bool checkCast = false;   // initialize here to use fall-through
02870   bool maskUnsignedResult = false;
02871   int nextRule;
02872   int forwardOperandNum = -1;
02873   unsigned allocaSize = 0;
02874   MachineInstr* M, *M2;
02875   unsigned L;
02876   bool foldCase = false;
02877 
02878   mvec.clear(); 
02879   
02880   // If the code for this instruction was folded into the parent (user),
02881   // then do nothing!
02882   if (subtreeRoot->isFoldedIntoParent())
02883     return;
02884   
02885   // Let's check for chain rules outside the switch so that we don't have
02886   // to duplicate the list of chain rule production numbers here again
02887   if (ThisIsAChainRule(ruleForNode)) {
02888     // Chain rules have a single nonterminal on the RHS.
02889     // Get the rule that matches the RHS non-terminal and use that instead.
02890     assert(nts[0] && ! nts[1]
02891            && "A chain rule should have only one RHS non-terminal!");
02892     nextRule = burm_rule(subtreeRoot->state, nts[0]);
02893     nts = burm_nts[nextRule];
02894     GetInstructionsByRule(subtreeRoot, nextRule, nts, target, mvec);
02895   } else {
02896     switch(ruleForNode) {
02897       case 1:   // stmt:   Ret
02898       case 2:   // stmt:   RetValue(reg)
02899       {         // NOTE: Prepass of register allocation is responsible
02900                 //   for moving return value to appropriate register.
02901                 // Copy the return value to the required return register.
02902                 // Mark the return Value as an implicit ref of the RET instr..
02903                 // Mark the return-address register as a hidden virtual reg.
02904           // Finally put a NOP in the delay slot.
02905         ReturnInst *returnInstr=cast<ReturnInst>(subtreeRoot->getInstruction());
02906         Value* retVal = returnInstr->getReturnValue();
02907         MachineCodeForInstruction& mcfi =
02908           MachineCodeForInstruction::get(returnInstr);
02909 
02910         // Create a hidden virtual reg to represent the return address register
02911         // used by the machine instruction but not represented in LLVM.
02912         Instruction* returnAddrTmp = new TmpInstruction(mcfi, returnInstr);
02913 
02914         MachineInstr* retMI = 
02915           BuildMI(V9::JMPLRETi, 3).addReg(returnAddrTmp).addSImm(8)
02916           .addMReg(target.getRegInfo()->getZeroRegNum(), MachineOperand::Def);
02917       
02918         // If there is a value to return, we need to:
02919         // (a) Sign-extend the value if it is smaller than 8 bytes (reg size)
02920         // (b) Insert a copy to copy the return value to the appropriate reg.
02921         //     -- For FP values, create a FMOVS or FMOVD instruction
02922         //     -- For non-FP values, create an add-with-0 instruction
02923         if (retVal != NULL) {
02924           const SparcV9RegInfo& regInfo =
02925             (SparcV9RegInfo&) *target.getRegInfo();
02926           const Type* retType = retVal->getType();
02927           unsigned regClassID = regInfo.getRegClassIDOfType(retType);
02928           unsigned retRegNum = (retType->isFloatingPoint()
02929                                 ? (unsigned) SparcV9FloatRegClass::f0
02930                                 : (unsigned) SparcV9IntRegClass::i0);
02931           retRegNum = regInfo.getUnifiedRegNum(regClassID, retRegNum);
02932 
02933           // Insert sign-extension instructions for small signed values.
02934           Value* retValToUse = retVal;
02935           if (retType->isIntegral() && retType->isSigned()) {
02936             unsigned retSize = target.getTargetData().getTypeSize(retType);
02937             if (retSize <= 4) {
02938               // Create a temporary virtual reg. to hold the sign-extension.
02939               retValToUse = new TmpInstruction(mcfi, retVal);
02940 
02941               // Sign-extend retVal and put the result in the temporary reg.
02942               CreateSignExtensionInstructions
02943                 (target, returnInstr->getParent()->getParent(),
02944                  retVal, retValToUse, 8*retSize, mvec, mcfi);
02945             }
02946           }
02947 
02948           // (b) Now, insert a copy to to the appropriate register:
02949           //     -- For FP values, create a FMOVS or FMOVD instruction
02950           //     -- For non-FP values, create an add-with-0 instruction
02951           // First, create a virtual register to represent the register and
02952           // mark this vreg as being an implicit operand of the ret MI.
02953           TmpInstruction* retVReg = 
02954             new TmpInstruction(mcfi, retValToUse, NULL, "argReg");
02955           
02956           retMI->addImplicitRef(retVReg);
02957           
02958           if (retType->isFloatingPoint())
02959             M = (BuildMI(retType==Type::FloatTy? V9::FMOVS : V9::FMOVD, 2)
02960                  .addReg(retValToUse).addReg(retVReg, MachineOperand::Def));
02961           else
02962             M = (BuildMI(ChooseAddInstructionByType(retType), 3)
02963                  .addReg(retValToUse).addSImm((int64_t) 0)
02964                  .addReg(retVReg, MachineOperand::Def));
02965 
02966           // Mark the operand with the register it should be assigned
02967           M->SetRegForOperand(M->getNumOperands()-1, retRegNum);
02968           retMI->SetRegForImplicitRef(retMI->getNumImplicitRefs()-1, retRegNum);
02969 
02970           mvec.push_back(M);
02971         }
02972         
02973         // Now insert the RET instruction and a NOP for the delay slot
02974         mvec.push_back(retMI);
02975         mvec.push_back(BuildMI(V9::NOP, 0));
02976         
02977         break;
02978       }  
02979         
02980       case 3: // stmt:   Store(reg,reg)
02981       case 4: // stmt:   Store(reg,ptrreg)
02982         SetOperandsForMemInstr(ChooseStoreInstruction(
02983                         subtreeRoot->leftChild()->getValue()->getType()),
02984                                mvec, subtreeRoot, target);
02985         break;
02986 
02987       case 5: // stmt:   BrUncond
02988         {
02989           BranchInst *BI = cast<BranchInst>(subtreeRoot->getInstruction());
02990           mvec.push_back(BuildMI(V9::BA, 1).addPCDisp(BI->getSuccessor(0)));
02991         
02992           // delay slot
02993           mvec.push_back(BuildMI(V9::NOP, 0));
02994           break;
02995         }
02996 
02997       case 206: // stmt:   BrCond(setCCconst)
02998       { // setCCconst => boolean was computed with `%b = setCC type reg1 const'
02999         // If the constant is ZERO, we can use the branch-on-integer-register
03000         // instructions and avoid the SUBcc instruction entirely.
03001         // Otherwise this is just the same as case 5, so just fall through.
03002         // 
03003         InstrTreeNode* constNode = subtreeRoot->leftChild()->rightChild();
03004         assert(constNode &&
03005                constNode->getNodeType() ==InstrTreeNode::NTConstNode);
03006         Constant *constVal = cast<Constant>(constNode->getValue());
03007         bool isValidConst;
03008         
03009         if ((constVal->getType()->isInteger()
03010              || isa<PointerType>(constVal->getType()))
03011             && ConvertConstantToIntType(target,
03012                              constVal, constVal->getType(), isValidConst) == 0
03013             && isValidConst)
03014           {
03015             // That constant is a zero after all...
03016             // Use the left child of setCC as the first argument!
03017             // Mark the setCC node so that no code is generated for it.
03018             InstructionNode* setCCNode = (InstructionNode*)
03019                                          subtreeRoot->leftChild();
03020             assert(setCCNode->getOpLabel() == SetCCOp);
03021             setCCNode->markFoldedIntoParent();
03022             
03023             BranchInst* brInst=cast<BranchInst>(subtreeRoot->getInstruction());
03024             
03025             M = BuildMI(ChooseBprInstruction(subtreeRoot), 2)
03026                                 .addReg(setCCNode->leftChild()->getValue())
03027                                 .addPCDisp(brInst->getSuccessor(0));
03028             mvec.push_back(M);
03029             
03030             // delay slot
03031             mvec.push_back(BuildMI(V9::NOP, 0));
03032 
03033             // false branch
03034             mvec.push_back(BuildMI(V9::BA, 1)
03035                            .addPCDisp(brInst->getSuccessor(1)));
03036             
03037             // delay slot
03038             mvec.push_back(BuildMI(V9::NOP, 0));
03039             break;
03040           }
03041         // ELSE FALL THROUGH
03042       }
03043 
03044       case 6: // stmt:   BrCond(setCC)
03045       { // bool => boolean was computed with SetCC.
03046         // The branch to use depends on whether it is FP, signed, or unsigned.
03047         // If it is an integer CC, we also need to find the unique
03048         // TmpInstruction representing that CC.
03049         // 
03050         BranchInst* brInst = cast<BranchInst>(subtreeRoot->getInstruction());
03051         const Type* setCCType;
03052         unsigned Opcode = ChooseBccInstruction(subtreeRoot, setCCType);
03053         Value* ccValue = GetTmpForCC(subtreeRoot->leftChild()->getValue(),
03054                                      brInst->getParent()->getParent(),
03055                                      setCCType,
03056                                      MachineCodeForInstruction::get(brInst));
03057         M = BuildMI(Opcode, 2).addCCReg(ccValue)
03058                               .addPCDisp(brInst->getSuccessor(0));
03059         mvec.push_back(M);
03060 
03061         // delay slot
03062         mvec.push_back(BuildMI(V9::NOP, 0));
03063 
03064         // false branch
03065         mvec.push_back(BuildMI(V9::BA, 1).addPCDisp(brInst->getSuccessor(1)));
03066 
03067         // delay slot
03068         mvec.push_back(BuildMI(V9::NOP, 0));
03069         break;
03070       }
03071         
03072       case 208: // stmt:   BrCond(boolconst)
03073       {
03074         // boolconst => boolean is a constant; use BA to first or second label
03075         Constant* constVal = 
03076           cast<Constant>(subtreeRoot->leftChild()->getValue());
03077         unsigned dest = cast<ConstantBool>(constVal)->getValue()? 0 : 1;
03078         
03079         M = BuildMI(V9::BA, 1).addPCDisp(
03080           cast<BranchInst>(subtreeRoot->getInstruction())->getSuccessor(dest));
03081         mvec.push_back(M);
03082         
03083         // delay slot
03084         mvec.push_back(BuildMI(V9::NOP, 0));
03085         break;
03086       }
03087         
03088       case   8: // stmt:   BrCond(boolreg)
03089       { // boolreg   => boolean is recorded in an integer register.
03090         //              Use branch-on-integer-register instruction.
03091         // 
03092         BranchInst *BI = cast<BranchInst>(subtreeRoot->getInstruction());
03093         M = BuildMI(V9::BRNZ, 2).addReg(subtreeRoot->leftChild()->getValue())
03094           .addPCDisp(BI->getSuccessor(0));
03095         mvec.push_back(M);
03096 
03097         // delay slot
03098         mvec.push_back(BuildMI(V9::NOP, 0));
03099 
03100         // false branch
03101         mvec.push_back(BuildMI(V9::BA, 1).addPCDisp(BI->getSuccessor(1)));
03102         
03103         // delay slot
03104         mvec.push_back(BuildMI(V9::NOP, 0));
03105         break;
03106       }  
03107       
03108       case 9: // stmt:   Switch(reg)
03109         assert(0 && "*** SWITCH instruction is not implemented yet.");
03110         break;
03111 
03112       case 10:  // reg:   VRegList(reg, reg)
03113         assert(0 && "VRegList should never be the topmost non-chain rule");
03114         break;
03115 
03116       case 21:  // bool:  Not(bool,reg): Compute with a conditional-move-on-reg
03117       { // First find the unary operand. It may be left or right, usually right.
03118         Instruction* notI = subtreeRoot->getInstruction();
03119         Value* notArg = BinaryOperator::getNotArgument(
03120                            cast<BinaryOperator>(subtreeRoot->getInstruction()));
03121         unsigned ZeroReg = target.getRegInfo()->getZeroRegNum();
03122 
03123         // Unconditionally set register to 0
03124         mvec.push_back(BuildMI(V9::SETHI, 2).addZImm(0).addRegDef(notI));
03125 
03126         // Now conditionally move 1 into the register.
03127         // Mark the register as a use (as well as a def) because the old
03128         // value will be retained if the condition is false.
03129         mvec.push_back(BuildMI(V9::MOVRZi, 3).addReg(notArg).addZImm(1)
03130                        .addReg(notI, MachineOperand::UseAndDef));
03131 
03132         break;
03133       }
03134 
03135       case 421: // reg:   BNot(reg,reg): Compute as reg = reg XOR-NOT 0
03136       { // First find the unary operand. It may be left or right, usually right.
03137         Value* notArg = BinaryOperator::getNotArgument(
03138                            cast<BinaryOperator>(subtreeRoot->getInstruction()));
03139         unsigned ZeroReg = target.getRegInfo()->getZeroRegNum();
03140         mvec.push_back(BuildMI(V9::XNORr, 3).addReg(notArg).addMReg(ZeroReg)
03141                                        .addRegDef(subtreeRoot->getValue()));
03142         break;
03143       }
03144 
03145       case 322: // reg:   Not(tobool, reg):
03146         // Fold CAST-TO-BOOL with NOT by inverting the sense of cast-to-bool
03147         foldCase = true;
03148         // Just fall through!
03149 
03150       case 22:  // reg:   ToBoolTy(reg):
03151       {
03152         Instruction* castI = subtreeRoot->getInstruction();
03153         Value* opVal = subtreeRoot->leftChild()->getValue();
03154         assert(opVal->getType()->isIntegral() ||
03155                isa<PointerType>(opVal->getType()));
03156 
03157         // Unconditionally set register to 0
03158         mvec.push_back(BuildMI(V9::SETHI, 2).addZImm(0).addRegDef(castI));
03159 
03160         // Now conditionally move 1 into the register.
03161         // Mark the register as a use (as well as a def) because the old
03162         // value will be retained if the condition is false.
03163         MachineOpCode opCode = foldCase? V9::MOVRZi : V9::MOVRNZi;
03164         mvec.push_back(BuildMI(opCode, 3).addReg(opVal).addZImm(1)
03165                        .addReg(castI, MachineOperand::UseAndDef));
03166 
03167         break;
03168       }
03169       
03170       case 23:  // reg:   ToUByteTy(reg)
03171       case 24:  // reg:   ToSByteTy(reg)
03172       case 25:  // reg:   ToUShortTy(reg)
03173       case 26:  // reg:   ToShortTy(reg)
03174       case 27:  // reg:   ToUIntTy(reg)
03175       case 28:  // reg:   ToIntTy(reg)
03176       case 29:  // reg:   ToULongTy(reg)
03177       case 30:  // reg:   ToLongTy(reg)
03178       {
03179         //======================================================================
03180         // Rules for integer conversions:
03181         // 
03182         //--------
03183         // From ISO 1998 C++ Standard, Sec. 4.7:
03184         //
03185         // 2. If the destination type is unsigned, the resulting value is
03186         // the least unsigned integer congruent to the source integer
03187         // (modulo 2n where n is the number of bits used to represent the
03188         // unsigned type). [Note: In a two s complement representation,
03189         // this conversion is conceptual and there is no change in the
03190         // bit pattern (if there is no truncation). ]
03191         // 
03192         // 3. If the destination type is signed, the value is unchanged if
03193         // it can be represented in the destination type (and bitfield width);
03194         // otherwise, the value is implementation-defined.
03195         //--------
03196         // 
03197         // Since we assume 2s complement representations, this implies:
03198         // 
03199         // -- If operand is smaller than destination, zero-extend or sign-extend
03200         //    according to the signedness of the *operand*: source decides:
03201         //    (1) If operand is signed, sign-extend it.
03202         //        If dest is unsigned, zero-ext the result!
03203         //    (2) If operand is unsigned, our current invariant is that
03204         //        it's high bits are correct, so zero-extension is not needed.
03205         // 
03206         // -- If operand is same size as or larger than destination,
03207         //    zero-extend or sign-extend according to the signedness of
03208         //    the *destination*: destination decides:
03209         //    (1) If destination is signed, sign-extend (truncating if needed)
03210         //        This choice is implementation defined.  We sign-extend the
03211         //        operand, which matches both Sun's cc and gcc3.2.
03212         //    (2) If destination is unsigned, zero-extend (truncating if needed)
03213         //======================================================================
03214 
03215         Instruction* destI =  subtreeRoot->getInstruction();
03216         Function* currentFunc = destI->getParent()->getParent();
03217         MachineCodeForInstruction& mcfi=MachineCodeForInstruction::get(destI);
03218 
03219         Value* opVal = subtreeRoot->leftChild()->getValue();
03220         const Type* opType = opVal->getType();
03221         const Type* destType = destI->getType();
03222         unsigned opSize   = target.getTargetData().getTypeSize(opType);
03223         unsigned destSize = target.getTargetData().getTypeSize(destType);
03224         
03225         bool isIntegral = opType->isIntegral() || isa<PointerType>(opType);
03226 
03227         if (opType == Type::BoolTy ||
03228             opType == destType ||
03229             isIntegral && opSize == destSize && opSize == 8) {
03230           // nothing to do in all these cases
03231           forwardOperandNum = 0;          // forward first operand to user
03232 
03233         } else if (opType->isFloatingPoint()) {
03234 
03235           CreateCodeToConvertFloatToInt(target, opVal, destI, mvec, mcfi);
03236           if (destI->getType()->isUnsigned() && destI->getType() !=Type::UIntTy)
03237             maskUnsignedResult = true; // not handled by fp->int code
03238 
03239         } else if (isIntegral) {
03240 
03241           bool opSigned     = opType->isSigned();
03242           bool destSigned   = destType->isSigned();
03243           unsigned extSourceInBits = 8 * std::min<unsigned>(opSize, destSize);
03244 
03245           assert(! (opSize == destSize && opSigned == destSigned) &&
03246                  "How can different int types have same size and signedness?");
03247 
03248           bool signExtend = (opSize <  destSize && opSigned ||
03249                              opSize >= destSize && destSigned);
03250 
03251           bool signAndZeroExtend = (opSize < destSize && destSize < 8u &&
03252                                     opSigned && !destSigned);
03253           assert(!signAndZeroExtend || signExtend);
03254 
03255           bool zeroExtendOnly = opSize >= destSize && !destSigned;
03256           assert(!zeroExtendOnly || !signExtend);
03257 
03258           if (signExtend) {
03259             Value* signExtDest = (signAndZeroExtend
03260                                   ? new TmpInstruction(mcfi, destType, opVal)
03261                                   : destI);
03262 
03263             CreateSignExtensionInstructions
03264               (target, currentFunc,opVal,signExtDest,extSourceInBits,mvec,mcfi);
03265 
03266             if (signAndZeroExtend)
03267               CreateZeroExtensionInstructions
03268               (target, currentFunc, signExtDest, destI, 8*destSize, mvec, mcfi);
03269           }
03270           else if (zeroExtendOnly) {
03271             CreateZeroExtensionInstructions
03272               (target, currentFunc, opVal, destI, extSourceInBits, mvec, mcfi);
03273           }
03274           else
03275             forwardOperandNum = 0;          // forward first operand to user
03276 
03277         } else
03278           assert(0 && "Unrecognized operand type for convert-to-integer");
03279 
03280         break;
03281       }
03282       
03283       case  31: // reg:   ToFloatTy(reg):
03284       case  32: // reg:   ToDoubleTy(reg):
03285       case 232: // reg:   ToDoubleTy(Constant):
03286       
03287         // If this instruction has a parent (a user) in the tree 
03288         // and the user is translated as an FsMULd instruction,
03289         // then the cast is unnecessary.  So check that first.
03290         // In the future, we'll want to do the same for the FdMULq instruction,
03291         // so do the check here instead of only for ToFloatTy(reg).
03292         // 
03293         if (subtreeRoot->parent() != NULL) {
03294           const MachineCodeForInstruction& mcfi =
03295             MachineCodeForInstruction::get(
03296                 cast<InstructionNode>(subtreeRoot->parent())->getInstruction());
03297           if (mcfi.size() == 0 || mcfi.front()->getOpcode() == V9::FSMULD)
03298             forwardOperandNum = 0;    // forward first operand to user
03299         }
03300 
03301         if (forwardOperandNum != 0) {    // we do need the cast
03302           Value* leftVal = subtreeRoot->leftChild()->getValue();
03303           const Type* opType = leftVal->getType();
03304           MachineOpCode opCode=ChooseConvertToFloatInstr(target,
03305                                        subtreeRoot->getOpLabel(), opType);
03306           if (opCode == V9::NOP) {      // no conversion needed
03307             forwardOperandNum = 0;      // forward first operand to user
03308           } else {
03309             // If the source operand is a non-FP type it must be
03310             // first copied from int to float register via memory!
03311             Instruction *dest = subtreeRoot->getInstruction();
03312             Value* srcForCast;
03313             int n = 0;
03314             if (! opType->isFloatingPoint()) {
03315               // Create a temporary to represent the FP register
03316               // into which the integer will be copied via memory.
03317               // The type of this temporary will determine the FP
03318               // register used: single-prec for a 32-bit int or smaller,
03319               // double-prec for a 64-bit int.
03320               // 
03321               uint64_t srcSize =
03322                 target.getTargetData().getTypeSize(leftVal->getType());
03323               Type* tmpTypeToUse =
03324                 (srcSize <= 4)? Type::FloatTy : Type::DoubleTy;
03325               MachineCodeForInstruction &destMCFI = 
03326                 MachineCodeForInstruction::get(dest);
03327               srcForCast = new TmpInstruction(destMCFI, tmpTypeToUse, dest);
03328 
03329               CreateCodeToCopyIntToFloat(target,
03330                          dest->getParent()->getParent(),
03331                          leftVal, cast<Instruction>(srcForCast),
03332                          mvec, destMCFI);
03333             } else
03334               srcForCast = leftVal;
03335 
03336             M = BuildMI(opCode, 2).addReg(srcForCast).addRegDef(dest);
03337             mvec.push_back(M);
03338           }
03339         }
03340         break;
03341 
03342       case 19:  // reg:   ToArrayTy(reg):
03343       case 20:  // reg:   ToPointerTy(reg):
03344         forwardOperandNum = 0;          // forward first operand to user
03345         break;
03346 
03347       case 233: // reg:   Add(reg, Constant)
03348         maskUnsignedResult = true;
03349         M = CreateAddConstInstruction(subtreeRoot);
03350         if (M != NULL) {
03351           mvec.push_back(M);
03352           break;
03353         }
03354         // ELSE FALL THROUGH
03355         
03356       case 33:  // reg:   Add(reg, reg)
03357         maskUnsignedResult = true;
03358         Add3OperandInstr(ChooseAddInstruction(subtreeRoot), subtreeRoot, mvec);
03359         break;
03360 
03361       case 234: // reg:   Sub(reg, Constant)
03362         maskUnsignedResult = true;
03363         M = CreateSubConstInstruction(subtreeRoot);
03364         if (M != NULL) {
03365           mvec.push_back(M);
03366           break;
03367         }
03368         // ELSE FALL THROUGH
03369         
03370       case 34:  // reg:   Sub(reg, reg)
03371         maskUnsignedResult = true;
03372         Add3OperandInstr(ChooseSubInstructionByType(
03373                                    subtreeRoot->getInstruction()->getType()),
03374                          subtreeRoot, mvec);
03375         break;
03376 
03377       case 135: // reg:   Mul(todouble, todouble)
03378         checkCast = true;
03379         // FALL THROUGH 
03380 
03381       case 35:  // reg:   Mul(reg, reg)
03382       {
03383         maskUnsignedResult = true;
03384         MachineOpCode forceOp = ((checkCast && BothFloatToDouble(subtreeRoot))
03385                                  ? (MachineOpCode)V9::FSMULD
03386                                  : -1);
03387         Instruction* mulInstr = subtreeRoot->getInstruction();
03388         CreateMulInstruction(target, mulInstr->getParent()->getParent(),
03389                              subtreeRoot->leftChild()->getValue(),
03390                              subtreeRoot->rightChild()->getValue(),
03391                              mulInstr, mvec,
03392                              MachineCodeForInstruction::get(mulInstr),forceOp);
03393         break;
03394       }
03395       case 335: // reg:   Mul(todouble, todoubleConst)
03396         checkCast = true;
03397         // FALL THROUGH 
03398 
03399       case 235: // reg:   Mul(reg, Constant)
03400       {
03401         maskUnsignedResult = true;
03402         MachineOpCode forceOp = ((checkCast && BothFloatToDouble(subtreeRoot))
03403                                  ? (MachineOpCode)V9::FSMULD
03404                                  : -1);
03405         Instruction* mulInstr = subtreeRoot->getInstruction();
03406         CreateMulInstruction(target, mulInstr->getParent()->getParent(),
03407                              subtreeRoot->leftChild()->getValue(),
03408                              subtreeRoot->rightChild()->getValue(),
03409                              mulInstr, mvec,
03410                              MachineCodeForInstruction::get(mulInstr),
03411                              forceOp);
03412         break;
03413       }
03414       case 236: // reg:   Div(reg, Constant)
03415         maskUnsignedResult = true;
03416         L = mvec.size();
03417         CreateDivConstInstruction(target, subtreeRoot, mvec);
03418         if (mvec.size() > L)
03419           break;
03420         // ELSE FALL THROUGH
03421       
03422       case 36:  // reg:   Div(reg, reg)
03423       {
03424         maskUnsignedResult = true;
03425 
03426         // If either operand of divide is smaller than 64 bits, we have
03427         // to make sure the unused top bits are correct because they affect
03428         // the result.  These bits are already correct for unsigned values.
03429         // They may be incorrect for signed values, so sign extend to fill in.
03430         Instruction* divI = subtreeRoot->getInstruction();
03431         Value* divOp1 = subtreeRoot->leftChild()->getValue();
03432         Value* divOp2 = subtreeRoot->rightChild()->getValue();
03433         Value* divOp1ToUse = divOp1;
03434         Value* divOp2ToUse = divOp2;
03435         if (divI->getType()->isSigned()) {
03436           unsigned opSize=target.getTargetData().getTypeSize(divI->getType());
03437           if (opSize < 8) {
03438             MachineCodeForInstruction& mcfi=MachineCodeForInstruction::get(divI);
03439             divOp1ToUse = new TmpInstruction(mcfi, divOp1);
03440             divOp2ToUse = new TmpInstruction(mcfi, divOp2);
03441             CreateSignExtensionInstructions(target,
03442                                               divI->getParent()->getParent(),
03443                                               divOp1, divOp1ToUse,
03444                                               8*opSize, mvec, mcfi);
03445             CreateSignExtensionInstructions(target,
03446                                               divI->getParent()->getParent(),
03447                                               divOp2, divOp2ToUse,
03448                                               8*opSize, mvec, mcfi);
03449           }
03450         }
03451 
03452         mvec.push_back(BuildMI(ChooseDivInstruction(target, subtreeRoot), 3)
03453                        .addReg(divOp1ToUse)
03454                        .addReg(divOp2ToUse)
03455                        .addRegDef(divI));
03456 
03457         break;
03458       }
03459 
03460       case  37: // reg:   Rem(reg, reg)
03461       case 237: // reg:   Rem(reg, Constant)
03462       {
03463         maskUnsignedResult = true;
03464 
03465         Instruction* remI   = subtreeRoot->getInstruction();
03466         Value* divOp1 = subtreeRoot->leftChild()->getValue();
03467         Value* divOp2 = subtreeRoot->rightChild()->getValue();
03468 
03469         MachineCodeForInstruction& mcfi = MachineCodeForInstruction::get(remI);
03470         
03471         // If second operand of divide is smaller than 64 bits, we have
03472         // to make sure the unused top bits are correct because they affect
03473         // the result.  These bits are already correct for unsigned values.
03474         // They may be incorrect for signed values, so sign extend to fill in.
03475         // 
03476         Value* divOpToUse = divOp2;
03477         if (divOp2->getType()->isSigned()) {
03478           unsigned opSize=target.getTargetData().getTypeSize(divOp2->getType());
03479           if (opSize < 8) {
03480             divOpToUse = new TmpInstruction(mcfi, divOp2);
03481             CreateSignExtensionInstructions(target,
03482                                               remI->getParent()->getParent(),
03483                                               divOp2, divOpToUse,
03484                                               8*opSize, mvec, mcfi);
03485           }
03486         }
03487 
03488         // Now compute: result = rem V1, V2 as:
03489         //      result = V1 - (V1 / signExtend(V2)) * signExtend(V2)
03490         // 
03491         TmpInstruction* quot = new TmpInstruction(mcfi, divOp1, divOpToUse);
03492         TmpInstruction* prod = new TmpInstruction(mcfi, quot, divOpToUse);
03493 
03494         mvec.push_back(BuildMI(ChooseDivInstruction(target, subtreeRoot), 3)
03495                        .addReg(divOp1).addReg(divOpToUse).addRegDef(quot));
03496         
03497         mvec.push_back(BuildMI(ChooseMulInstructionByType(remI->getType()), 3)
03498                        .addReg(quot).addReg(divOpToUse).addRegDef(prod));
03499         
03500         mvec.push_back(BuildMI(ChooseSubInstructionByType(remI->getType()), 3)
03501                        .addReg(divOp1).addReg(prod).addRegDef(remI));
03502         
03503         break;
03504       }
03505       
03506       case  38: // bool:   And(bool, bool)
03507       case 138: // bool:   And(bool, not)
03508       case 238: // bool:   And(bool, boolconst)
03509       case 338: // reg :   BAnd(reg, reg)
03510       case 538: // reg :   BAnd(reg, Constant)
03511         Add3OperandInstr(V9::ANDr, subtreeRoot, mvec);
03512         break;
03513 
03514       case 438: // bool:   BAnd(bool, bnot)
03515       { // Use the argument of NOT as the second argument!
03516         // Mark the NOT node so that no code is generated for it.
03517         // If the type is boolean, set 1 or 0 in the result register.
03518         InstructionNode* notNode = (InstructionNode*) subtreeRoot->rightChild();
03519         Value* notArg = BinaryOperator::getNotArgument(
03520                            cast<BinaryOperator>(notNode->getInstruction()));
03521         notNode->markFoldedIntoParent();
03522         Value *lhs = subtreeRoot->leftChild()->getValue();
03523         Value *dest = subtreeRoot->getValue();
03524         mvec.push_back(BuildMI(V9::ANDNr, 3).addReg(lhs).addReg(notArg)
03525                                        .addReg(dest, MachineOperand::Def));
03526 
03527         if (notArg->getType() == Type::BoolTy) {
03528           // set 1 in result register if result of above is non-zero
03529           mvec.push_back(BuildMI(V9::MOVRNZi, 3).addReg(dest).addZImm(1)
03530                          .addReg(dest, MachineOperand::UseAndDef));
03531         }
03532 
03533         break;
03534       }
03535 
03536       case  39: // bool:   Or(bool, bool)
03537       case 139: // bool:   Or(bool, not)
03538       case 239: // bool:   Or(bool, boolconst)
03539       case 339: // reg :   BOr(reg, reg)
03540       case 539: // reg :   BOr(reg, Constant)
03541         Add3OperandInstr(V9::ORr, subtreeRoot, mvec);
03542         break;
03543 
03544       case 439: // bool:   BOr(bool, bnot)
03545       { // Use the argument of NOT as the second argument!
03546         // Mark the NOT node so that no code is generated for it.
03547         // If the type is boolean, set 1 or 0 in the result register.
03548         InstructionNode* notNode = (InstructionNode*) subtreeRoot->rightChild();
03549         Value* notArg = BinaryOperator::getNotArgument(
03550                            cast<BinaryOperator>(notNode->getInstruction()));
03551         notNode->markFoldedIntoParent();
03552         Value *lhs = subtreeRoot->leftChild()->getValue();
03553         Value *dest = subtreeRoot->getValue();
03554 
03555         mvec.push_back(BuildMI(V9::ORNr, 3).addReg(lhs).addReg(notArg)
03556                        .addReg(dest, MachineOperand::Def));
03557 
03558         if (notArg->getType() == Type::BoolTy) {
03559           // set 1 in result register if result of above is non-zero
03560           mvec.push_back(BuildMI(V9::MOVRNZi, 3).addReg(dest).addZImm(1)
03561                          .addReg(dest, MachineOperand::UseAndDef));
03562         }
03563 
03564         break;
03565       }
03566 
03567       case  40: // bool:   Xor(bool, bool)
03568       case 140: // bool:   Xor(bool, not)
03569       case 240: // bool:   Xor(bool, boolconst)
03570       case 340: // reg :   BXor(reg, reg)
03571       case 540: // reg :   BXor(reg, Constant)
03572         Add3OperandInstr(V9::XORr, subtreeRoot, mvec);
03573         break;
03574 
03575       case 440: // bool:   BXor(bool, bnot)
03576       { // Use the argument of NOT as the second argument!
03577         // Mark the NOT node so that no code is generated for it.
03578         // If the type is boolean, set 1 or 0 in the result register.
03579         InstructionNode* notNode = (InstructionNode*) subtreeRoot->rightChild();
03580         Value* notArg = BinaryOperator::getNotArgument(
03581                            cast<BinaryOperator>(notNode->getInstruction()));
03582         notNode->markFoldedIntoParent();
03583         Value *lhs = subtreeRoot->leftChild()->getValue();
03584         Value *dest = subtreeRoot->getValue();
03585         mvec.push_back(BuildMI(V9::XNORr, 3).addReg(lhs).addReg(notArg)
03586                        .addReg(dest, MachineOperand::Def));
03587 
03588         if (notArg->getType() == Type::BoolTy) {
03589           // set 1 in result register if result of above is non-zero
03590           mvec.push_back(BuildMI(V9::MOVRNZi, 3).addReg(dest).addZImm(1)
03591                          .addReg(dest, MachineOperand::UseAndDef));
03592         }
03593         break;
03594       }
03595 
03596       case 41:  // setCCconst:   SetCC(reg, Constant)
03597       { // Comparison is with a constant:
03598         // 
03599         // If the bool result must be computed into a register (see below),
03600         // and the constant is int ZERO, we can use the MOVR[op] instructions
03601         // and avoid the SUBcc instruction entirely.
03602         // Otherwise this is just the same as case 42, so just fall through.
03603         // 
03604         // The result of the SetCC must be computed and stored in a register if
03605         // it is used outside the current basic block (so it must be computed
03606         // as a boolreg) or it is used by anything other than a branch.
03607         // We will use a conditional move to do this.
03608         // 
03609         Instruction* setCCInstr = subtreeRoot->getInstruction();
03610         bool computeBoolVal = (subtreeRoot->parent() == NULL ||
03611                                ! AllUsesAreBranches(setCCInstr));
03612 
03613         if (computeBoolVal) {
03614           InstrTreeNode* constNode = subtreeRoot->rightChild();
03615           assert(constNode &&
03616                  constNode->getNodeType() ==InstrTreeNode::NTConstNode);
03617           Constant *constVal = cast<Constant>(constNode->getValue());
03618           bool isValidConst;
03619           
03620           if ((constVal->getType()->isInteger()
03621                || isa<PointerType>(constVal->getType()))
03622               && ConvertConstantToIntType(target,
03623                              constVal, constVal->getType(), isValidConst) == 0
03624               && isValidConst)
03625           {
03626             // That constant is an integer zero after all...
03627             // Use a MOVR[op] to compute the boolean result
03628             // Unconditionally set register to 0
03629             mvec.push_back(BuildMI(V9::SETHI, 2).addZImm(0)
03630                            .addRegDef(setCCInstr));
03631                 
03632             // Now conditionally move 1 into the register.
03633             // Mark the register as a use (as well as a def) because the old
03634             // value will be retained if the condition is false.
03635             MachineOpCode movOpCode = ChooseMovpregiForSetCC(subtreeRoot);
03636             mvec.push_back(BuildMI(movOpCode, 3)
03637                            .addReg(subtreeRoot->leftChild()->getValue())
03638                            .addZImm(1)
03639                            .addReg(setCCInstr, MachineOperand::UseAndDef));
03640                 
03641             break;
03642           }
03643         }
03644         // ELSE FALL THROUGH
03645       }
03646 
03647       case 42:  // bool:   SetCC(reg, reg):
03648       {
03649         // This generates a SUBCC instruction, putting the difference in a
03650         // result reg. if needed, and/or setting a condition code if needed.
03651         // 
03652         Instruction* setCCInstr = subtreeRoot->getInstruction();
03653         Value* leftVal  = subtreeRoot->leftChild()->getValue();
03654         Value* rightVal = subtreeRoot->rightChild()->getValue();
03655         const Type* opType = leftVal->getType();
03656         bool isFPCompare = opType->isFloatingPoint();
03657         
03658         // If the boolean result of the SetCC is used outside the current basic
03659         // block (so it must be computed as a boolreg) or is used by anything
03660         // other than a branch, the boolean must be computed and stored
03661         // in a result register.  We will use a conditional move to do this.
03662         // 
03663         bool computeBoolVal = (subtreeRoot->parent() == NULL ||
03664                                ! AllUsesAreBranches(setCCInstr));
03665         
03666         // A TmpInstruction is created to represent the CC "result".
03667         // Unlike other instances of TmpInstruction, this one is used
03668         // by machine code of multiple LLVM instructions, viz.,
03669         // the SetCC and the branch.  Make sure to get the same one!
03670         // Note that we do this even for FP CC registers even though they
03671         // are explicit operands, because the type of the operand
03672         // needs to be a floating point condition code, not an integer
03673         // condition code.  Think of this as casting the bool result to
03674         // a FP condition code register.
03675         // Later, we mark the 4th operand as being a CC register, and as a def.
03676         // 
03677         TmpInstruction* tmpForCC = GetTmpForCC(setCCInstr,
03678                                     setCCInstr->getParent()->getParent(),
03679                                     leftVal->getType(),
03680                                     MachineCodeForInstruction::get(setCCInstr));
03681 
03682         // If the operands are signed values smaller than 4 bytes, then they
03683         // must be sign-extended in order to do a valid 32-bit comparison
03684         // and get the right result in the 32-bit CC register (%icc).
03685         // 
03686         Value* leftOpToUse  = leftVal;
03687         Value* rightOpToUse = rightVal;
03688         if (opType->isIntegral() && opType->isSigned()) {
03689           unsigned opSize = target.getTargetData().getTypeSize(opType);
03690           if (opSize < 4) {
03691             MachineCodeForInstruction& mcfi =
03692               MachineCodeForInstruction::get(setCCInstr); 
03693 
03694             // create temporary virtual regs. to hold the sign-extensions
03695             leftOpToUse  = new TmpInstruction(mcfi, leftVal);
03696             rightOpToUse = new TmpInstruction(mcfi, rightVal);
03697             
03698             // sign-extend each operand and put the result in the temporary reg.
03699             CreateSignExtensionInstructions
03700               (target, setCCInstr->getParent()->getParent(),
03701                leftVal, leftOpToUse, 8*opSize, mvec, mcfi);
03702             CreateSignExtensionInstructions
03703               (target, setCCInstr->getParent()->getParent(),
03704                rightVal, rightOpToUse, 8*opSize, mvec, mcfi);
03705           }
03706         }
03707 
03708         if (! isFPCompare) {
03709           // Integer condition: set CC and discard result.
03710           mvec.push_back(BuildMI(V9::SUBccr, 4)
03711                          .addReg(leftOpToUse)
03712                          .addReg(rightOpToUse)
03713                          .addMReg(target.getRegInfo()->
03714                                    getZeroRegNum(), MachineOperand::Def)
03715                          .addCCReg(tmpForCC, MachineOperand::Def));
03716         } else {
03717           // FP condition: dest of FCMP should be some FCCn register
03718           mvec.push_back(BuildMI(ChooseFcmpInstruction(subtreeRoot), 3)
03719                          .addCCReg(tmpForCC, MachineOperand::Def)
03720                          .addReg(leftOpToUse)
03721                          .addReg(rightOpToUse));
03722         }
03723         
03724         if (computeBoolVal) {
03725           MachineOpCode movOpCode = (isFPCompare
03726                                      ? ChooseMovFpcciInstruction(subtreeRoot)
03727                                      : ChooseMovpcciForSetCC(subtreeRoot));
03728 
03729           // Unconditionally set register to 0
03730           M = BuildMI(V9::SETHI, 2).addZImm(0).addRegDef(setCCInstr);
03731           mvec.push_back(M);
03732           
03733           // Now conditionally move 1 into the register.
03734           // Mark the register as a use (as well as a def) because the old
03735           // value will be retained if the condition is false.
03736           M = (BuildMI(movOpCode, 3).addCCReg(tmpForCC).addZImm(1)
03737                .addReg(setCCInstr, MachineOperand::UseAndDef));
03738           mvec.push_back(M);
03739         }
03740         break;
03741       }    
03742       
03743       case 51:  // reg:   Load(reg)
03744       case 52:  // reg:   Load(ptrreg)
03745         SetOperandsForMemInstr(ChooseLoadInstruction(
03746                                    subtreeRoot->getValue()->getType()),
03747                                mvec, subtreeRoot, target);
03748         break;
03749 
03750       case 55:  // reg:   GetElemPtr(reg)
03751       case 56:  // reg:   GetElemPtrIdx(reg,reg)
03752         // If the GetElemPtr was folded into the user (parent), it will be
03753         // caught above.  For other cases, we have to compute the address.
03754         SetOperandsForMemInstr(V9::ADDr, mvec, subtreeRoot, target);
03755         break;
03756 
03757       case 57:  // reg:  Alloca: Implement as 1 instruction:
03758       {         //      add %fp, offsetFromFP -> result
03759         AllocationInst* instr =
03760           cast<AllocationInst>(subtreeRoot->getInstruction());
03761         unsigned tsize =
03762           target.getTargetData().getTypeSize(instr->getAllocatedType());
03763         assert(tsize != 0);
03764         CreateCodeForFixedSizeAlloca(target, instr, tsize, 1, mvec);
03765         break;
03766       }
03767 
03768       case 58:  // reg:   Alloca(reg): Implement as 3 instructions:
03769                 //  mul num, typeSz -> tmp
03770                 //  sub %sp, tmp    -> %sp
03771       {         //  add %sp, frameSizeBelowDynamicArea -> result
03772         AllocationInst* instr =
03773           cast<AllocationInst>(subtreeRoot->getInstruction());
03774         const Type* eltType = instr->getAllocatedType();
03775         
03776         // If #elements is constant, use simpler code for fixed-size allocas
03777         int tsize = (int) target.getTargetData().getTypeSize(eltType);
03778         Value* numElementsVal = NULL;
03779         bool isArray = instr->isArrayAllocation();
03780         
03781         if (!isArray || isa<Constant>(numElementsVal = instr->getArraySize())) {
03782           // total size is constant: generate code for fixed-size alloca
03783           unsigned numElements = isArray? 
03784             cast<ConstantUInt>(numElementsVal)->getValue() : 1;
03785           CreateCodeForFixedSizeAlloca(target, instr, tsize,
03786                                        numElements, mvec);
03787         } else {
03788           // total size is not constant.
03789           CreateCodeForVariableSizeAlloca(target, instr, tsize,
03790                                           numElementsVal, mvec);
03791         }
03792         break;
03793       }
03794 
03795       case 61:  // reg:   Call
03796       {         // Generate a direct (CALL) or indirect (JMPL) call.
03797                 // Mark the return-address register, the indirection
03798                 // register (for indirect calls), the operands of the Call,
03799                 // and the return value (if any) as implicit operands
03800                 // of the machine instruction.
03801                 // 
03802                 // If this is a varargs function, floating point arguments
03803                 // have to passed in integer registers so insert
03804                 // copy-float-to-int instructions for each float operand.
03805                 // 
03806         CallInst *callInstr = cast<CallInst>(subtreeRoot->getInstruction());
03807         Value *callee = callInstr->getCalledValue();
03808         Function* calledFunc = dyn_cast<Function>(callee);
03809 
03810         // Check if this is an intrinsic function that needs a special code
03811         // sequence (e.g., va_start).  Indirect calls cannot be special.
03812         // 
03813         bool specialIntrinsic = false;
03814         Intrinsic::ID iid;
03815         if (calledFunc && (iid=(Intrinsic::ID)calledFunc->getIntrinsicID()))
03816           specialIntrinsic = CodeGenIntrinsic(iid, *callInstr, target, mvec);
03817 
03818         // If not, generate the normal call sequence for the function.
03819         // This can also handle any intrinsics that are just function calls.
03820         // 
03821         if (! specialIntrinsic) {
03822           Function* currentFunc = callInstr->getParent()->getParent();
03823           MachineFunction& MF = MachineFunction::get(currentFunc);
03824           MachineCodeForInstruction& mcfi =
03825             MachineCodeForInstruction::get(callInstr); 
03826           const SparcV9RegInfo& regInfo =
03827             (SparcV9RegInfo&) *target.getRegInfo();
03828           const TargetFrameInfo& frameInfo = *target.getFrameInfo();
03829 
03830           // Create hidden virtual register for return address with type void*
03831           TmpInstruction* retAddrReg =
03832             new TmpInstruction(mcfi, PointerType::get(Type::VoidTy), callInstr);
03833 
03834           // Generate the machine instruction and its operands.
03835           // Use CALL for direct function calls; this optimistically assumes
03836           // the PC-relative address fits in the CALL address field (22 bits).
03837           // Use JMPL for indirect calls.
03838           // This will be added to mvec later, after operand copies.
03839           // 
03840           MachineInstr* callMI;
03841           if (calledFunc)             // direct function call
03842             callMI = BuildMI(V9::CALL, 1).addPCDisp(callee);
03843           else                        // indirect function call
03844             callMI = (BuildMI(V9::JMPLCALLi,3).addReg(callee)
03845                       .addSImm((int64_t)0).addRegDef(retAddrReg));
03846 
03847           const FunctionType* funcType =
03848             cast<FunctionType>(cast<PointerType>(callee->getType())
03849                                ->getElementType());
03850           bool isVarArgs = funcType->isVarArg();
03851           bool noPrototype = isVarArgs && funcType->getNumParams() == 0;
03852         
03853           // Use a descriptor to pass information about call arguments
03854           // to the register allocator.  This descriptor will be "owned"
03855           // and freed automatically when the MachineCodeForInstruction
03856           // object for the callInstr goes away.
03857           CallArgsDescriptor* argDesc =
03858             new CallArgsDescriptor(callInstr, retAddrReg,isVarArgs,noPrototype);
03859           assert(callInstr->getOperand(0) == callee
03860                  && "This is assumed in the loop below!");
03861 
03862           // Insert sign-extension instructions for small signed values,
03863           // if this is an unknown function (i.e., called via a funcptr)
03864           // or an external one (i.e., which may not be compiled by llc).
03865           // 
03866           if (calledFunc == NULL || calledFunc->isExternal()) {
03867             for (unsigned i=1, N=callInstr->getNumOperands(); i < N; ++i) {
03868               Value* argVal = callInstr->getOperand(i);
03869               const Type* argType = argVal->getType();
03870               if (argType->isIntegral() && argType->isSigned()) {
03871                 unsigned argSize = target.getTargetData().getTypeSize(argType);
03872                 if (argSize <= 4) {
03873                   // create a temporary virtual reg. to hold the sign-extension
03874                   TmpInstruction* argExtend = new TmpInstruction(mcfi, argVal);
03875 
03876                   // sign-extend argVal and put the result in the temporary reg.
03877                   CreateSignExtensionInstructions
03878                     (target, currentFunc, argVal, argExtend,
03879                      8*argSize, mvec, mcfi);
03880 
03881                   // replace argVal with argExtend in CallArgsDescriptor
03882                   argDesc->getArgInfo(i-1).replaceArgVal(argExtend);
03883                 }
03884               }
03885             }
03886           }
03887 
03888           // Insert copy instructions to get all the arguments into
03889           // all the places that they need to be.
03890           // 
03891           for (unsigned i=1, N=callInstr->getNumOperands(); i < N; ++i) {
03892             int argNo = i-1;
03893             CallArgInfo& argInfo = argDesc->getArgInfo(argNo);
03894             Value* argVal = argInfo.getArgVal(); // don't use callInstr arg here
03895             const Type* argType = argVal->getType();
03896             unsigned regType = regInfo.getRegTypeForDataType(argType);
03897             unsigned argSize = target.getTargetData().getTypeSize(argType);
03898             int regNumForArg = SparcV9RegInfo::getInvalidRegNum();
03899             unsigned regClassIDOfArgReg;
03900 
03901             // Check for FP arguments to varargs functions.
03902             // Any such argument in the first $K$ args must be passed in an
03903             // integer register.  If there is no prototype, it must also
03904             // be passed as an FP register.
03905             // K = #integer argument registers.
03906             bool isFPArg = argVal->getType()->isFloatingPoint();
03907             if (isVarArgs && isFPArg) {
03908 
03909               if (noPrototype) {
03910                 // It is a function with no prototype: pass value
03911                 // as an FP value as well as a varargs value.  The FP value
03912                 // may go in a register or on the stack.  The copy instruction
03913                 // to the outgoing reg/stack is created by the normal argument
03914                 // handling code since this is the "normal" passing mode.
03915                 // 
03916                 regNumForArg = regInfo.regNumForFPArg(regType,
03917                                                       false, false, argNo,
03918                                                       regClassIDOfArgReg);
03919                 if (regNumForArg == regInfo.getInvalidRegNum())
03920                   argInfo.setUseStackSlot();
03921                 else
03922                   argInfo.setUseFPArgReg();
03923               }
03924               
03925               // If this arg. is in the first $K$ regs, add special copy-
03926               // float-to-int instructions to pass the value as an int.
03927               // To check if it is in the first $K$, get the register
03928               // number for the arg #i.  These copy instructions are
03929               // generated here because they are extra cases and not needed
03930               // for the normal argument handling (some code reuse is
03931               // possible though -- later).
03932               // 
03933               int copyRegNum = regInfo.regNumForIntArg(false, false, argNo,
03934                                                        regClassIDOfArgReg);
03935               if (copyRegNum != regInfo.getInvalidRegNum()) {
03936                 // Create a virtual register to represent copyReg. Mark
03937                 // this vreg as being an implicit operand of the call MI
03938                 const Type* loadTy = (argType == Type::FloatTy
03939                                       ? Type::IntTy : Type::LongTy);
03940                 TmpInstruction* argVReg = new TmpInstruction(mcfi, loadTy,
03941                                                              argVal, NULL,
03942                                                              "argRegCopy");
03943                 callMI->addImplicitRef(argVReg);
03944                 
03945                 // Get a temp stack location to use to copy
03946                 // float-to-int via the stack.
03947                 // 
03948                 // FIXME: For now, we allocate permanent space because
03949                 // the stack frame manager does not allow locals to be
03950                 // allocated (e.g., for alloca) after a temp is
03951                 // allocated!
03952                 // 
03953                 // int tmpOffset = MF.getInfo<SparcV9FunctionInfo>()->pushTempValue(argSize);
03954                 int tmpOffset = MF.getInfo<SparcV9FunctionInfo>()->allocateLocalVar(argVReg);
03955                     
03956                 // Generate the store from FP reg to stack
03957                 unsigned StoreOpcode = ChooseStoreInstruction(argType);
03958                 M = BuildMI(convertOpcodeFromRegToImm(StoreOpcode), 3)
03959                   .addReg(argVal).addMReg(regInfo.getFramePointer())
03960                   .addSImm(tmpOffset);
03961                 mvec.push_back(M);
03962                         
03963                 // Generate the load from stack to int arg reg
03964                 unsigned LoadOpcode = ChooseLoadInstruction(loadTy);
03965                 M = BuildMI(convertOpcodeFromRegToImm(LoadOpcode), 3)
03966                   .addMReg(regInfo.getFramePointer()).addSImm(tmpOffset)
03967                   .addReg(argVReg, MachineOperand::Def);
03968 
03969                 // Mark operand with register it should be assigned
03970                 // both for copy and for the callMI
03971                 M->SetRegForOperand(M->getNumOperands()-1, copyRegNum);
03972                 callMI->SetRegForImplicitRef(callMI->getNumImplicitRefs()-1,
03973                                              copyRegNum);
03974                 mvec.push_back(M);
03975 
03976                 // Add info about the argument to the CallArgsDescriptor
03977                 argInfo.setUseIntArgReg();
03978                 argInfo.setArgCopy(copyRegNum);
03979               } else {
03980                 // Cannot fit in first $K$ regs so pass arg on stack
03981                 argInfo.setUseStackSlot();
03982               }
03983             } else if (isFPArg) {
03984               // Get the outgoing arg reg to see if there is one.
03985               regNumForArg = regInfo.regNumForFPArg(regType, false, false,
03986                                                     argNo, regClassIDOfArgReg);
03987               if (regNumForArg == regInfo.getInvalidRegNum())
03988                 argInfo.setUseStackSlot();
03989               else {
03990                 argInfo.setUseFPArgReg();
03991                 regNumForArg =regInfo.getUnifiedRegNum(regClassIDOfArgReg,
03992                                                        regNumForArg);
03993               }
03994             } else {
03995               // Get the outgoing arg reg to see if there is one.
03996               regNumForArg = regInfo.regNumForIntArg(false,false,
03997                                                      argNo, regClassIDOfArgReg);
03998               if (regNumForArg == regInfo.getInvalidRegNum())
03999                 argInfo.setUseStackSlot();
04000               else {
04001                 argInfo.setUseIntArgReg();
04002                 regNumForArg =regInfo.getUnifiedRegNum(regClassIDOfArgReg,
04003                                                        regNumForArg);
04004               }
04005             }                
04006 
04007             // 
04008             // Now insert copy instructions to stack slot or arg. register
04009             // 
04010             if (argInfo.usesStackSlot()) {
04011               // Get the stack offset for this argument slot.
04012               // FP args on stack are right justified so adjust offset!
04013               // int arguments are also right justified but they are
04014               // always loaded as a full double-word so the offset does
04015               // not need to be adjusted.
04016               int argOffset = frameInfo.getOutgoingArgOffset(MF, argNo);
04017               if (argType->isFloatingPoint()) {
04018                 unsigned slotSize = SparcV9FrameInfo::SizeOfEachArgOnStack;
04019                 assert(argSize <= slotSize && "Insufficient slot size!");
04020                 argOffset += slotSize - argSize;
04021               }
04022 
04023               // Now generate instruction to copy argument to stack
04024               MachineOpCode storeOpCode =
04025                 (argType->isFloatingPoint()
04026                  ? ((argSize == 4)? V9::STFi : V9::STDFi) : V9::STXi);
04027 
04028               M = BuildMI(storeOpCode, 3).addReg(argVal)
04029                 .addMReg(regInfo.getStackPointer()).addSImm(argOffset);
04030               mvec.push_back(M);
04031             }
04032             else if (regNumForArg != regInfo.getInvalidRegNum()) {
04033 
04034               // Create a virtual register to represent the arg reg. Mark
04035               // this vreg as being an implicit operand of the call MI.
04036               TmpInstruction* argVReg = 
04037                 new TmpInstruction(mcfi, argVal, NULL, "argReg");
04038 
04039               callMI->addImplicitRef(argVReg);
04040               
04041               // Generate the reg-to-reg copy into the outgoing arg reg.
04042               // -- For FP values, create a FMOVS or FMOVD instruction
04043               // -- For non-FP values, create an add-with-0 instruction
04044               if (argType->isFloatingPoint())
04045                 M=(BuildMI(argType==Type::FloatTy? V9::FMOVS :V9::FMOVD,2)
04046                    .addReg(argVal).addReg(argVReg, MachineOperand::Def));
04047               else
04048                 M = (BuildMI(ChooseAddInstructionByType(argType), 3)
04049                      .addReg(argVal).addSImm((int64_t) 0)
04050                      .addReg(argVReg, MachineOperand::Def));
04051               
04052               // Mark the operand with the register it should be assigned
04053               M->SetRegForOperand(M->getNumOperands()-1, regNumForArg);
04054               callMI->SetRegForImplicitRef(callMI->getNumImplicitRefs()-1,
04055                                            regNumForArg);
04056 
04057               mvec.push_back(M);
04058             }
04059             else
04060               assert(argInfo.getArgCopy() != regInfo.getInvalidRegNum() &&
04061                      "Arg. not in stack slot, primary or secondary register?");
04062           }
04063 
04064           // add call instruction and delay slot before copying return value
04065           mvec.push_back(callMI);
04066           mvec.push_back(BuildMI(V9::NOP, 0));
04067 
04068           // Add the return value as an implicit ref.  The call operands
04069           // were added above.  Also, add code to copy out the return value.
04070           // This is always register-to-register for int or FP return values.
04071           // 
04072           if (callInstr->getType() != Type::VoidTy) { 
04073             // Get the return value reg.
04074             const Type* retType = callInstr->getType();
04075 
04076             int regNum = (retType->isFloatingPoint()
04077                           ? (unsigned) SparcV9FloatRegClass::f0 
04078                           : (unsigned) SparcV9IntRegClass::o0);
04079             unsigned regClassID = regInfo.getRegClassIDOfType(retType);
04080             regNum = regInfo.getUnifiedRegNum(regClassID, regNum);
04081 
04082             // Create a virtual register to represent it and mark
04083             // this vreg as being an implicit operand of the call MI
04084             TmpInstruction* retVReg = 
04085               new TmpInstruction(mcfi, callInstr, NULL, "argReg");
04086 
04087             callMI->addImplicitRef(retVReg, /*isDef*/ true);
04088 
04089             // Generate the reg-to-reg copy from the return value reg.
04090             // -- For FP values, create a FMOVS or FMOVD instruction
04091             // -- For non-FP values, create an add-with-0 instruction
04092             if (retType->isFloatingPoint())
04093               M = (BuildMI(retType==Type::FloatTy? V9::FMOVS : V9::FMOVD, 2)
04094                    .addReg(retVReg).addReg(callInstr, MachineOperand::Def));
04095             else
04096               M = (BuildMI(ChooseAddInstructionByType(retType), 3)
04097                    .addReg(retVReg).addSImm((int64_t) 0)
04098                    .addReg(callInstr, MachineOperand::Def));
04099 
04100             // Mark the operand with the register it should be assigned
04101             // Also mark the implicit ref of the call defining this operand
04102             M->SetRegForOperand(0, regNum);
04103             callMI->SetRegForImplicitRef(callMI->getNumImplicitRefs()-1,regNum);
04104 
04105             mvec.push_back(M);
04106           }
04107 
04108           // For the CALL instruction, the ret. addr. reg. is also implicit
04109           if (isa<Function>(callee))
04110             callMI->addImplicitRef(retAddrReg, /*isDef*/ true);
04111 
04112           MF.getInfo<SparcV9FunctionInfo>()->popAllTempValues();  // free temps used for this inst
04113         }
04114 
04115         break;
04116       }
04117       
04118       case 62:  // reg:   Shl(reg, reg)
04119       {
04120         Value* argVal1 = subtreeRoot->leftChild()->getValue();
04121         Value* argVal2 = subtreeRoot->rightChild()->getValue();
04122         Instruction* shlInstr = subtreeRoot->getInstruction();
04123         
04124         const Type* opType = argVal1->getType();
04125         assert((opType->isInteger() || isa<PointerType>(opType)) &&
04126                "Shl unsupported for other types");
04127         unsigned opSize = target.getTargetData().getTypeSize(opType);
04128         
04129         CreateShiftInstructions(target, shlInstr->getParent()->getParent(),
04130                                 (opSize > 4)? V9::SLLXr6:V9::SLLr5,
04131                                 argVal1, argVal2, 0, shlInstr, mvec,
04132                                 MachineCodeForInstruction::get(shlInstr));
04133         break;
04134       }
04135       
04136       case 63:  // reg:   Shr(reg, reg)
04137       { 
04138         const Type* opType = subtreeRoot->leftChild()->getValue()->getType();
04139         assert((opType->isInteger() || isa<PointerType>(opType)) &&
04140                "Shr unsupported for other types");
04141         unsigned opSize = target.getTargetData().getTypeSize(opType);
04142         Add3OperandInstr(opType->isSigned()
04143                          ? (opSize > 4? V9::SRAXr6 : V9::SRAr5)
04144                          : (opSize > 4? V9::SRLXr6 : V9::SRLr5),
04145                          subtreeRoot, mvec);
04146         break;
04147       }
04148       
04149       case 64:  // reg:   Phi(reg,reg)
04150         break;                          // don't forward the value
04151 
04152       case 65:  // reg:   VANext(reg):  the va_next(va_list, type) instruction
04153       { // Increment the va_list pointer register according to the type.
04154         // All LLVM argument types are <= 64 bits, so use one doubleword.
04155         Instruction* vaNextI = subtreeRoot->getInstruction();
04156         assert(target.getTargetData().getTypeSize(vaNextI->getType()) <= 8 &&
04157                "We assumed that all LLVM parameter types <= 8 bytes!");
04158         unsigned argSize = SparcV9FrameInfo::SizeOfEachArgOnStack;
04159         mvec.push_back(BuildMI(V9::ADDi, 3).addReg(vaNextI->getOperand(0)).
04160                        addSImm(argSize).addRegDef(vaNextI));
04161         break;
04162       }
04163 
04164       case 66:  // reg:   VAArg (reg): the va_arg instruction
04165       { // Load argument from stack using current va_list pointer value.
04166         // Use 64-bit load for all non-FP args, and LDDF or double for FP.
04167         Instruction* vaArgI = subtreeRoot->getInstruction();
04168         MachineOpCode loadOp = (vaArgI->getType()->isFloatingPoint()
04169                                 ? (vaArgI->getType() == Type::FloatTy
04170                                    ? V9::LDFi : V9::LDDFi)
04171                                 : V9::LDXi);
04172         mvec.push_back(BuildMI(loadOp, 3).addReg(vaArgI->getOperand(0)).
04173                        addSImm(0).addRegDef(vaArgI));
04174         break;
04175       }
04176       
04177       case 71:  // reg:     VReg
04178       case 72:  // reg:     Constant
04179         break;                          // don't forward the value
04180 
04181       default:
04182         assert(0 && "Unrecognized BURG rule");
04183         break;
04184       }
04185     }
04186 
04187   if (forwardOperandNum >= 0) {
04188     // We did not generate a machine instruction but need to use operand.
04189     // If user is in the same tree, replace Value in its machine operand.
04190     // If not, insert a copy instruction which should get coalesced away
04191     // by register allocation.
04192     if (subtreeRoot->parent() != NULL)
04193       ForwardOperand(subtreeRoot, subtreeRoot->parent(), forwardOperandNum);
04194     else {
04195       std::vector<MachineInstr*> minstrVec;
04196       Instruction* instr = subtreeRoot->getInstruction();
04197       CreateCopyInstructionsByType(target,
04198                                      instr->getParent()->getParent(),
04199                                      instr->getOperand(forwardOperandNum),
04200                                      instr, minstrVec,
04201                                      MachineCodeForInstruction::get(instr));
04202       assert(minstrVec.size() > 0);
04203       mvec.insert(mvec.end(), minstrVec.begin(), minstrVec.end());
04204     }
04205   }
04206 
04207   if (maskUnsignedResult) {
04208     // If result is unsigned and smaller than int reg size,
04209     // we need to clear high bits of result value.
04210     assert(forwardOperandNum < 0 && "Need mask but no instruction generated");
04211     Instruction* dest = subtreeRoot->getInstruction();
04212     if (dest->getType()->isUnsigned()) {
04213       unsigned destSize=target.getTargetData().getTypeSize(dest->getType());
04214       if (destSize <= 4) {
04215         // Mask high 64 - N bits, where N = 4*destSize.
04216         
04217         // Use a TmpInstruction to represent the
04218         // intermediate result before masking.  Since those instructions
04219         // have already been generated, go back and substitute tmpI
04220         // for dest in the result position of each one of them.
04221         // 
04222         MachineCodeForInstruction& mcfi = MachineCodeForInstruction::get(dest);
04223         TmpInstruction *tmpI = new TmpInstruction(mcfi, dest->getType(),
04224                                                   dest, NULL, "maskHi");
04225         Value* srlArgToUse = tmpI;
04226 
04227         unsigned numSubst = 0;
04228         for (unsigned i=0, N=mvec.size(); i < N; ++i) {
04229 
04230           // Make sure we substitute all occurrences of dest in these instrs.
04231           // Otherwise, we will have bogus code.
04232           bool someArgsWereIgnored = false;
04233 
04234           // Make sure not to substitute an upwards-exposed use -- that would
04235           // introduce a use of `tmpI' with no preceding def.  Therefore,
04236           // substitute a use or def-and-use operand only if a previous def
04237           // operand has already been substituted (i.e., numSubst > 0).
04238           // 
04239           numSubst += mvec[i]->substituteValue(dest, tmpI,
04240                                                /*defsOnly*/ numSubst == 0,
04241                                                /*notDefsAndUses*/ numSubst > 0,
04242                                                someArgsWereIgnored);
04243           assert(!someArgsWereIgnored &&
04244                  "Operand `dest' exists but not replaced: probably bogus!");
04245         }
04246         assert(numSubst > 0 && "Operand `dest' not replaced: probably bogus!");
04247 
04248         // Left shift 32-N if size (N) is less than 32 bits.
04249         // Use another tmp. virtual register to represent this result.
04250         if (destSize < 4) {
04251           srlArgToUse = new TmpInstruction(mcfi, dest->getType(),
04252                                            tmpI, NULL, "maskHi2");
04253           mvec.push_back(BuildMI(V9::SLLXi6, 3).addReg(tmpI)
04254                          .addZImm(8*(4-destSize))
04255                          .addReg(srlArgToUse, MachineOperand::Def));
04256         }
04257 
04258         // Logical right shift 32-N to get zero extension in top 64-N bits.
04259         mvec.push_back(BuildMI(V9::SRLi5, 3).addReg(srlArgToUse)
04260                          .addZImm(8*(4-destSize))
04261                          .addReg(dest, MachineOperand::Def));
04262 
04263       } else if (destSize < 8) {
04264         assert(0 && "Unsupported type size: 32 < size < 64 bits");
04265       }
04266     }
04267   }
04268 }
04269 
04270 } // End llvm namespace
04271 
04272 //==------------------------------------------------------------------------==//
04273 //                     Class V9ISel Implementation
04274 //==------------------------------------------------------------------------==//
04275 
04276 bool V9ISel::runOnFunction(Function &F) {
04277   // First pass - Walk the function, lowering any calls to intrinsic functions
04278   // which the instruction selector cannot handle.
04279   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
04280     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; )
04281       if (CallInst *CI = dyn_cast<CallInst>(I++))
04282         if (Function *F = CI->getCalledFunction())
04283           switch (F->getIntrinsicID()) {
04284           case Intrinsic::not_intrinsic:
04285           case Intrinsic::vastart:
04286           case Intrinsic::vacopy:
04287           case Intrinsic::vaend:
04288             // We directly implement these intrinsics.  Note that this knowledge
04289             // is incestuously entangled with the code in
04290             // SparcInstrSelection.cpp and must be updated when it is updated.
04291             // Since ALL of the code in this library is incestuously intertwined
04292             // with it already and sparc specific, we will live with this.
04293             break;
04294           default:
04295             // All other intrinsic calls we must lower.
04296             Instruction *Before = CI->getPrev();
04297             Target.getIntrinsicLowering().LowerIntrinsicCall(CI);
04298             if (Before) {        // Move iterator to instruction after call
04299               I = Before;  ++I;
04300             } else {
04301               I = BB->begin();
04302             }
04303           }
04304 
04305   // Build the instruction trees to be given as inputs to BURG.
04306   InstrForest instrForest(&F);
04307   if (SelectDebugLevel >= Select_DebugInstTrees) {
04308     std::cerr << "\n\n*** Input to instruction selection for function "
04309               << F.getName() << "\n\n" << F
04310               << "\n\n*** Instruction trees for function "
04311               << F.getName() << "\n\n";
04312     instrForest.dump();
04313   }
04314   
04315   // Invoke BURG instruction selection for each tree
04316   for (InstrForest::const_root_iterator RI = instrForest.roots_begin();
04317        RI != instrForest.roots_end(); ++RI) {
04318     InstructionNode* basicNode = *RI;
04319     assert(basicNode->parent() == NULL && "A `root' node has a parent?"); 
04320       
04321     // Invoke BURM to label each tree node with a state
04322     burm_label(basicNode);
04323     if (SelectDebugLevel >= Select_DebugBurgTrees) {
04324       printcover(basicNode, 1, 0);
04325       std::cerr << "\nCover cost == " << treecost(basicNode, 1, 0) <<"\n\n";
04326       printMatches(basicNode);
04327     }
04328       
04329     // Then recursively walk the tree to select instructions
04330     SelectInstructionsForTree(basicNode, /*goalnt*/1);
04331   }
04332   
04333   // Create the MachineBasicBlocks and add all of the MachineInstrs
04334   // defined in the MachineCodeForInstruction objects to the MachineBasicBlocks.
04335   MachineFunction &MF = MachineFunction::get(&F);
04336   std::map<const BasicBlock *, MachineBasicBlock *> MBBMap;
04337   for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) {
04338     MachineBasicBlock *MBB = new MachineBasicBlock(BI);
04339     MF.getBasicBlockList().push_back(MBB);
04340     MBBMap[BI] = MBB;
04341 
04342     for (BasicBlock::iterator II = BI->begin(); II != BI->end(); ++II) {
04343       MachineCodeForInstruction &mvec = MachineCodeForInstruction::get(II);
04344       MBB->insert(MBB->end(), mvec.begin(), mvec.end());
04345     }
04346   }
04347 
04348   // Initialize Machine-CFG for the function.
04349   for (MachineFunction::iterator i = MF.begin (), e = MF.end (); i != e; ++i) {
04350     MachineBasicBlock &MBB = *i;
04351     const BasicBlock *BB = MBB.getBasicBlock ();
04352     // for each successor S of BB, add MBBMap[S] as a successor of MBB.
04353     for (succ_const_iterator si = succ_begin(BB), se = succ_end(BB); si != se;
04354          ++si) {
04355       MachineBasicBlock *succMBB = MBBMap[*si];
04356       assert (succMBB && "Can't find MachineBasicBlock for this successor");
04357       MBB.addSuccessor (succMBB);
04358     }
04359   }
04360 
04361   // Insert phi elimination code
04362   InsertCodeForPhis(F);
04363   
04364   if (SelectDebugLevel >= Select_PrintMachineCode) {
04365     std::cerr << "\n*** Machine instructions after INSTRUCTION SELECTION\n";
04366     MachineFunction::get(&F).dump();
04367   }
04368   
04369   return true;
04370 }
04371 
04372 /// InsertCodeForPhis - This method inserts Phi elimination code for
04373 /// all Phi nodes in the given function.  After this method is called,
04374 /// the Phi nodes still exist in the LLVM code, but copies are added to the
04375 /// machine code.
04376 ///
04377 void V9ISel::InsertCodeForPhis(Function &F) {
04378   // Iterate over every Phi node PN in F:
04379   MachineFunction &MF = MachineFunction::get(&F);
04380   for (MachineFunction::iterator BB = MF.begin(); BB != MF.end(); ++BB) {
04381     for (BasicBlock::const_iterator IIt = BB->getBasicBlock()->begin();
04382          const PHINode *PN = dyn_cast<PHINode>(IIt); ++IIt) {
04383       // Create a new temporary register to hold the result of the Phi copy.
04384       // The leak detector shouldn't track these nodes.  They are not garbage,
04385       // even though their parent field is never filled in.
04386       Value *PhiCpRes = new PHINode(PN->getType(), PN->getName() + ":PhiCp");
04387       LeakDetector::removeGarbageObject(PhiCpRes);
04388 
04389       // For each of PN's incoming values, insert a copy in the corresponding
04390       // predecessor block.
04391       MachineCodeForInstruction &MCforPN = MachineCodeForInstruction::get (PN);
04392       for (unsigned i = 0; i < PN->getNumIncomingValues(); ++i) {
04393         std::vector<MachineInstr*> mvec, CpVec;
04394         Target.getRegInfo()->cpValue2Value(PN->getIncomingValue(i), 
04395                                            PhiCpRes, mvec);
04396         for (std::vector<MachineInstr*>::iterator MI=mvec.begin();
04397              MI != mvec.end(); ++MI) {
04398           std::vector<MachineInstr*> CpVec2 =
04399             FixConstantOperandsForInstr(const_cast<PHINode*>(PN), *MI, Target);
04400           CpVec2.push_back(*MI);
04401           CpVec.insert(CpVec.end(), CpVec2.begin(), CpVec2.end());
04402         }
04403         // Insert the copy instructions into the predecessor BB.        
04404         InsertPhiElimInstructions(PN->getIncomingBlock(i), CpVec);
04405         MCforPN.insert (MCforPN.end (), CpVec.begin (), CpVec.end ());
04406       }
04407       // Insert a copy instruction from PhiCpRes to PN.
04408       std::vector<MachineInstr*> mvec;
04409       Target.getRegInfo()->cpValue2Value(PhiCpRes, const_cast<PHINode*>(PN),
04410                                         mvec);
04411       BB->insert(BB->begin(), mvec.begin(), mvec.end());
04412       MCforPN.insert (MCforPN.end (), mvec.begin (), mvec.end ());
04413     }  // for each Phi Instr in BB
04414   } // for all BBs in function
04415 }
04416 
04417 /// InsertPhiElimInstructions - Inserts the instructions in CpVec into the
04418 /// MachineBasicBlock corresponding to BB, just before its terminator
04419 /// instruction. This is used by InsertCodeForPhis() to insert copies, above.
04420 ///
04421 void V9ISel::InsertPhiElimInstructions(BasicBlock *BB,
04422                                        const std::vector<MachineInstr*>& CpVec)
04423 { 
04424   Instruction *TermInst = (Instruction*)BB->getTerminator();
04425   MachineCodeForInstruction &MC4Term = MachineCodeForInstruction::get(TermInst);
04426   MachineInstr *FirstMIOfTerm = MC4Term.front();
04427   assert (FirstMIOfTerm && "No Machine Instrs for terminator");
04428 
04429   MachineBasicBlock *MBB = FirstMIOfTerm->getParent();
04430   assert(MBB && "Machine BB for predecessor's terminator not found");
04431   MachineBasicBlock::iterator MCIt = FirstMIOfTerm;
04432   assert(MCIt != MBB->end() && "Start inst of terminator not found");
04433   
04434   // Insert the copy instructions just before the first machine instruction
04435   // generated for the terminator.
04436   MBB->insert(MCIt, CpVec.begin(), CpVec.end());
04437 }
04438 
04439 /// SelectInstructionsForTree - Recursively walk the tree to select
04440 /// instructions. Do this top-down so that child instructions can exploit
04441 /// decisions made at the child instructions.
04442 /// 
04443 /// E.g., if br(setle(reg,const)) decides the constant is 0 and uses
04444 /// a branch-on-integer-register instruction, then the setle node
04445 /// can use that information to avoid generating the SUBcc instruction.
04446 ///
04447 /// Note that this cannot be done bottom-up because setle must do this
04448 /// only if it is a child of the branch (otherwise, the result of setle
04449 /// may be used by multiple instructions).
04450 ///
04451 void V9ISel::SelectInstructionsForTree(InstrTreeNode* treeRoot, int goalnt) {
04452   // Get the rule that matches this node.
04453   int ruleForNode = burm_rule(treeRoot->state, goalnt);
04454   
04455   if (ruleForNode == 0) {
04456     std::cerr << "Could not match instruction tree for instr selection\n";
04457     abort();
04458   }
04459   
04460   // Get this rule's non-terminals and the corresponding child nodes (if any)
04461   short *nts = burm_nts[ruleForNode];
04462   
04463   // First, select instructions for the current node and rule.
04464   // (If this is a list node, not an instruction, then skip this step).
04465   // This function is specific to the target architecture.
04466   if (treeRoot->opLabel != VRegListOp) {
04467     std::vector<MachineInstr*> minstrVec;
04468     InstructionNode* instrNode = (InstructionNode*)treeRoot;
04469     assert(instrNode->getNodeType() == InstrTreeNode::NTInstructionNode);
04470     GetInstructionsByRule(instrNode, ruleForNode, nts, Target, minstrVec);
04471     MachineCodeForInstruction &mvec = 
04472       MachineCodeForInstruction::get(instrNode->getInstruction());
04473     mvec.insert(mvec.end(), minstrVec.begin(), minstrVec.end());
04474   }
04475   
04476   // Then, recursively compile the child nodes, if any.
04477   // 
04478   if (nts[0]) {
04479     // i.e., there is at least one kid
04480     InstrTreeNode* kids[2];
04481     int currentRule = ruleForNode;
04482     burm_kids(treeRoot, currentRule, kids);
04483     
04484     // First skip over any chain rules so that we don't visit
04485     // the current node again.
04486     while (ThisIsAChainRule(currentRule)) {
04487       currentRule = burm_rule(treeRoot->state, nts[0]);
04488       nts = burm_nts[currentRule];
04489       burm_kids(treeRoot, currentRule, kids);
04490     }
04491       
04492     // Now we have the first non-chain rule so we have found
04493     // the actual child nodes.  Recursively compile them.
04494     for (unsigned i = 0; nts[i]; i++) {
04495       assert(i < 2);
04496       InstrTreeNode::InstrTreeNodeType nodeType = kids[i]->getNodeType();
04497       if (nodeType == InstrTreeNode::NTVRegListNode ||
04498           nodeType == InstrTreeNode::NTInstructionNode)
04499         SelectInstructionsForTree(kids[i], nts[i]);
04500     }
04501   }
04502   
04503   // Finally, do any post-processing on this node after its children
04504   // have been translated.
04505   if (treeRoot->opLabel != VRegListOp)
04506     PostprocessMachineCodeForTree((InstructionNode*)treeRoot, ruleForNode, nts);
04507 }
04508 
04509 /// PostprocessMachineCodeForTree - Apply any final cleanups to
04510 /// machine code for the root of a subtree after selection for all its
04511 /// children has been completed.
04512 ///
04513 void V9ISel::PostprocessMachineCodeForTree(InstructionNode *instrNode,
04514                                            int ruleForNode, short *nts) {
04515   // Fix up any constant operands in the machine instructions to either
04516   // use an immediate field or to load the constant into a register.
04517   // Walk backwards and use direct indexes to allow insertion before current.
04518   Instruction* vmInstr = instrNode->getInstruction();
04519   MachineCodeForInstruction &mvec = MachineCodeForInstruction::get(vmInstr);
04520   for (unsigned i = mvec.size(); i != 0; --i) {
04521     std::vector<MachineInstr*> loadConstVec =
04522       FixConstantOperandsForInstr(vmInstr, mvec[i-1], Target);
04523     mvec.insert(mvec.begin()+i-1, loadConstVec.begin(), loadConstVec.end());
04524   }
04525 }
04526 
04527 /// createSparcV9BurgInstSelector - Creates and returns a new SparcV9
04528 /// BURG-based instruction selection pass.
04529 ///
04530 FunctionPass *llvm::createSparcV9BurgInstSelector(TargetMachine &TM) {
04531   return new V9ISel(TM);
04532 }