lib/Target/IA64/IA64ISelPattern.cpp

   1 //===-- IA64ISelPattern.cpp - A pattern matching inst selector for IA64 ---===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Duraid Madina and is distributed under the
   6 // University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines a pattern matching instruction selector for IA64.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "IA64.h"
  15 #include "IA64InstrBuilder.h"
  16 #include "IA64RegisterInfo.h"
  17 #include "IA64MachineFunctionInfo.h"
  18 #include "llvm/Constants.h"                   // FIXME: REMOVE
  19 #include "llvm/Function.h"
  20 #include "llvm/CodeGen/MachineConstantPool.h" // FIXME: REMOVE
  21 #include "llvm/CodeGen/MachineFunction.h"
  22 #include "llvm/CodeGen/MachineFrameInfo.h"
  23 #include "llvm/CodeGen/SelectionDAG.h"
  24 #include "llvm/CodeGen/SelectionDAGISel.h"
  25 #include "llvm/CodeGen/SSARegMap.h"
  26 #include "llvm/Target/TargetData.h"
  27 #include "llvm/Target/TargetLowering.h"
  28 #include "llvm/Support/MathExtras.h"
  29 #include "llvm/ADT/Statistic.h"
  30 #include <set>
  31 #include <map>
  32 #include <algorithm>
  33 using namespace llvm;
  34
  35 //===----------------------------------------------------------------------===//
  36 //  IA64TargetLowering - IA64 Implementation of the TargetLowering interface
  37 namespace {
  38   class IA64TargetLowering : public TargetLowering {
  39     int VarArgsFrameIndex;            // FrameIndex for start of varargs area.
  40
  41     //int ReturnAddrIndex;              // FrameIndex for return slot.
  42     unsigned GP, SP, RP; // FIXME - clean this mess up
  43   public:
  44
  45    unsigned VirtGPR; // this is public so it can be accessed in the selector
  46    // for ISD::RET down below. add an accessor instead? FIXME
  47
  48    IA64TargetLowering(TargetMachine &TM) : TargetLowering(TM) {
  49
  50       // register class for general registers
  51       addRegisterClass(MVT::i64, IA64::GRRegisterClass);
  52
  53       // register class for FP registers
  54       addRegisterClass(MVT::f64, IA64::FPRegisterClass);
  55
  56       // register class for predicate registers
  57       addRegisterClass(MVT::i1, IA64::PRRegisterClass);
  58
  59       setOperationAction(ISD::BRCONDTWOWAY     , MVT::Other, Expand);
  60       setOperationAction(ISD::BRTWOWAY_CC      , MVT::Other, Expand);
  61       setOperationAction(ISD::FP_ROUND_INREG   , MVT::f32  , Expand);
  62
  63       setSetCCResultType(MVT::i1);
  64       setShiftAmountType(MVT::i64);
  65
  66       setOperationAction(ISD::EXTLOAD          , MVT::i1   , Promote);
  67
  68       setOperationAction(ISD::ZEXTLOAD         , MVT::i1   , Expand);
  69
  70       setOperationAction(ISD::SEXTLOAD         , MVT::i1   , Expand);
  71       setOperationAction(ISD::SEXTLOAD         , MVT::i8   , Expand);
  72       setOperationAction(ISD::SEXTLOAD         , MVT::i16  , Expand);
  73       setOperationAction(ISD::SEXTLOAD         , MVT::i32  , Expand);
  74
  75       setOperationAction(ISD::FREM             , MVT::f32  , Expand);
  76       setOperationAction(ISD::FREM             , MVT::f64  , Expand);
  77
  78       setOperationAction(ISD::UREM             , MVT::f32  , Expand);
  79       setOperationAction(ISD::UREM             , MVT::f64  , Expand);
  80
  81       setOperationAction(ISD::MEMMOVE          , MVT::Other, Expand);
  82       setOperationAction(ISD::MEMSET           , MVT::Other, Expand);
  83       setOperationAction(ISD::MEMCPY           , MVT::Other, Expand);
  84
  85       setOperationAction(ISD::SINT_TO_FP       , MVT::i1   , Promote);
  86       setOperationAction(ISD::UINT_TO_FP       , MVT::i1   , Promote);
  87
  88       // We don't support sin/cos/sqrt
  89       setOperationAction(ISD::FSIN , MVT::f64, Expand);
  90       setOperationAction(ISD::FCOS , MVT::f64, Expand);
  91       setOperationAction(ISD::FSQRT, MVT::f64, Expand);
  92       setOperationAction(ISD::FSIN , MVT::f32, Expand);
  93       setOperationAction(ISD::FCOS , MVT::f32, Expand);
  94       setOperationAction(ISD::FSQRT, MVT::f32, Expand);
  95
  96       //IA64 has these, but they are not implemented
  97       setOperationAction(ISD::CTTZ , MVT::i64  , Expand);
  98       setOperationAction(ISD::CTLZ , MVT::i64  , Expand);
  99       setOperationAction(ISD::ROTL , MVT::i64  , Expand);
 100       setOperationAction(ISD::ROTR , MVT::i64  , Expand);
 101       // FIXME: implement mulhs (xma.h) and mulhu (xma.hu)
 102       setOperationAction(ISD::MULHS , MVT::i64  , Expand);
 103       setOperationAction(ISD::MULHU , MVT::i64  , Expand);
 104
 105       // We don't have line number support yet.
 106       setOperationAction(ISD::LOCATION, MVT::Other, Expand);
 107       setOperationAction(ISD::DEBUG_LOC, MVT::Other, Expand);
 108       setOperationAction(ISD::DEBUG_LABEL, MVT::Other, Expand);
 109
 110       // Not implemented yet.
 111       setOperationAction(ISD::STACKSAVE, MVT::Other, Expand);
 112       setOperationAction(ISD::STACKRESTORE, MVT::Other, Expand);
 113
 114       computeRegisterProperties();
 115
 116       addLegalFPImmediate(+0.0);
 117       addLegalFPImmediate(+1.0);
 118       addLegalFPImmediate(-0.0);
 119       addLegalFPImmediate(-1.0);
 120     }
 121
 122     /// LowerArguments - This hook must be implemented to indicate how we should
 123     /// lower the arguments for the specified function, into the specified DAG.
 124     virtual std::vector<SDOperand>
 125     LowerArguments(Function &F, SelectionDAG &DAG);
 126
 127     /// LowerCallTo - This hook lowers an abstract call to a function into an
 128     /// actual call.
 129     virtual std::pair<SDOperand, SDOperand>
 130     LowerCallTo(SDOperand Chain, const Type *RetTy, bool isVarArg, unsigned CC,
 131                 bool isTailCall, SDOperand Callee, ArgListTy &Args,
 132                 SelectionDAG &DAG);
 133
 134     virtual SDOperand LowerVAStart(SDOperand Chain, SDOperand VAListP,
 135                                    Value *VAListV, SelectionDAG &DAG);
 136     virtual std::pair<SDOperand,SDOperand>
 137       LowerVAArg(SDOperand Chain, SDOperand VAListP, Value *VAListV,
 138                  const Type *ArgTy, SelectionDAG &DAG);
 139
 140     void restoreGP_SP_RP(MachineBasicBlock* BB)
 141     {
 142       BuildMI(BB, IA64::MOV, 1, IA64::r1).addReg(GP);
 143       BuildMI(BB, IA64::MOV, 1, IA64::r12).addReg(SP);
 144       BuildMI(BB, IA64::MOV, 1, IA64::rp).addReg(RP);
 145     }
 146
 147     void restoreSP_RP(MachineBasicBlock* BB)
 148     {
 149       BuildMI(BB, IA64::MOV, 1, IA64::r12).addReg(SP);
 150       BuildMI(BB, IA64::MOV, 1, IA64::rp).addReg(RP);
 151     }
 152
 153     void restoreRP(MachineBasicBlock* BB)
 154     {
 155       BuildMI(BB, IA64::MOV, 1, IA64::rp).addReg(RP);
 156     }
 157
 158     void restoreGP(MachineBasicBlock* BB)
 159     {
 160       BuildMI(BB, IA64::MOV, 1, IA64::r1).addReg(GP);
 161     }
 162
 163   };
 164 }
 165
 166
 167 std::vector<SDOperand>
 168 IA64TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG) {
 169   std::vector<SDOperand> ArgValues;
 170
 171   //
 172   // add beautiful description of IA64 stack frame format
 173   // here (from intel 24535803.pdf most likely)
 174   //
 175   MachineFunction &MF = DAG.getMachineFunction();
 176   MachineFrameInfo *MFI = MF.getFrameInfo();
 177
 178   GP = MF.getSSARegMap()->createVirtualRegister(getRegClassFor(MVT::i64));
 179   SP = MF.getSSARegMap()->createVirtualRegister(getRegClassFor(MVT::i64));
 180   RP = MF.getSSARegMap()->createVirtualRegister(getRegClassFor(MVT::i64));
 181
 182   MachineBasicBlock& BB = MF.front();
 183
 184   unsigned args_int[] = {IA64::r32, IA64::r33, IA64::r34, IA64::r35,
 185                          IA64::r36, IA64::r37, IA64::r38, IA64::r39};
 186
 187   unsigned args_FP[] = {IA64::F8, IA64::F9, IA64::F10, IA64::F11,
 188                         IA64::F12,IA64::F13,IA64::F14, IA64::F15};
 189
 190   unsigned argVreg[8];
 191   unsigned argPreg[8];
 192   unsigned argOpc[8];
 193
 194   unsigned used_FPArgs = 0; // how many FP args have been used so far?
 195
 196   unsigned ArgOffset = 0;
 197   int count = 0;
 198
 199   for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I)
 200     {
 201       SDOperand newroot, argt;
 202       if(count < 8) { // need to fix this logic? maybe.
 203
 204         switch (getValueType(I->getType())) {
 205           default:
 206             std::cerr << "ERROR in LowerArgs: unknown type "
 207               << getValueType(I->getType()) << "\n";
 208             abort();
 209           case MVT::f32:
 210             // fixme? (well, will need to for weird FP structy stuff,
 211             // see intel ABI docs)
 212           case MVT::f64:
 213 //XXX            BuildMI(&BB, IA64::IDEF, 0, args_FP[used_FPArgs]);
 214             MF.addLiveIn(args_FP[used_FPArgs]); // mark this reg as liveIn
 215             // floating point args go into f8..f15 as-needed, the increment
 216             argVreg[count] =                              // is below..:
 217             MF.getSSARegMap()->createVirtualRegister(getRegClassFor(MVT::f64));
 218             // FP args go into f8..f15 as needed: (hence the ++)
 219             argPreg[count] = args_FP[used_FPArgs++];
 220             argOpc[count] = IA64::FMOV;
 221             argt = newroot = DAG.getCopyFromReg(DAG.getRoot(), argVreg[count],
 222                                                 MVT::f64);
 223             if (I->getType() == Type::FloatTy)
 224               argt = DAG.getNode(ISD::FP_ROUND, MVT::f32, argt);
 225             break;
 226           case MVT::i1: // NOTE: as far as C abi stuff goes,
 227                         // bools are just boring old ints
 228           case MVT::i8:
 229           case MVT::i16:
 230           case MVT::i32:
 231           case MVT::i64:
 232 //XXX            BuildMI(&BB, IA64::IDEF, 0, args_int[count]);
 233             MF.addLiveIn(args_int[count]); // mark this register as liveIn
 234             argVreg[count] =
 235             MF.getSSARegMap()->createVirtualRegister(getRegClassFor(MVT::i64));
 236             argPreg[count] = args_int[count];
 237             argOpc[count] = IA64::MOV;
 238             argt = newroot =
 239               DAG.getCopyFromReg(DAG.getRoot(), argVreg[count], MVT::i64);
 240             if ( getValueType(I->getType()) != MVT::i64)
 241               argt = DAG.getNode(ISD::TRUNCATE, getValueType(I->getType()),
 242                   newroot);
 243             break;
 244         }
 245       } else { // more than 8 args go into the frame
 246         // Create the frame index object for this incoming parameter...
 247         ArgOffset = 16 + 8 * (count - 8);
 248         int FI = MFI->CreateFixedObject(8, ArgOffset);
 249
 250         // Create the SelectionDAG nodes corresponding to a load
 251         //from this parameter
 252         SDOperand FIN = DAG.getFrameIndex(FI, MVT::i64);
 253         argt = newroot = DAG.getLoad(getValueType(I->getType()),
 254                                      DAG.getEntryNode(), FIN, DAG.getSrcValue(NULL));
 255       }
 256       ++count;
 257       DAG.setRoot(newroot.getValue(1));
 258       ArgValues.push_back(argt);
 259     }
 260
 261
 262   // Create a vreg to hold the output of (what will become)
 263   // the "alloc" instruction
 264   VirtGPR = MF.getSSARegMap()->createVirtualRegister(getRegClassFor(MVT::i64));
 265   BuildMI(&BB, IA64::PSEUDO_ALLOC, 0, VirtGPR);
 266   // we create a PSEUDO_ALLOC (pseudo)instruction for now
 267
 268   BuildMI(&BB, IA64::IDEF, 0, IA64::r1);
 269
 270   // hmm:
 271   BuildMI(&BB, IA64::IDEF, 0, IA64::r12);
 272   BuildMI(&BB, IA64::IDEF, 0, IA64::rp);
 273   // ..hmm.
 274
 275   BuildMI(&BB, IA64::MOV, 1, GP).addReg(IA64::r1);
 276
 277   // hmm:
 278   BuildMI(&BB, IA64::MOV, 1, SP).addReg(IA64::r12);
 279   BuildMI(&BB, IA64::MOV, 1, RP).addReg(IA64::rp);
 280   // ..hmm.
 281
 282   unsigned tempOffset=0;
 283
 284   // if this is a varargs function, we simply lower llvm.va_start by
 285   // pointing to the first entry
 286   if(F.isVarArg()) {
 287     tempOffset=0;
 288     VarArgsFrameIndex = MFI->CreateFixedObject(8, tempOffset);
 289   }
 290
 291   // here we actually do the moving of args, and store them to the stack
 292   // too if this is a varargs function:
 293   for (int i = 0; i < count && i < 8; ++i) {
 294     BuildMI(&BB, argOpc[i], 1, argVreg[i]).addReg(argPreg[i]);
 295     if(F.isVarArg()) {
 296       // if this is a varargs function, we copy the input registers to the stack
 297       int FI = MFI->CreateFixedObject(8, tempOffset);
 298       tempOffset+=8;   //XXX: is it safe to use r22 like this?
 299       BuildMI(&BB, IA64::MOV, 1, IA64::r22).addFrameIndex(FI);
 300       // FIXME: we should use st8.spill here, one day
 301       BuildMI(&BB, IA64::ST8, 1, IA64::r22).addReg(argPreg[i]);
 302     }
 303   }
 304
 305   // Finally, inform the code generator which regs we return values in.
 306   // (see the ISD::RET: case down below)
 307   switch (getValueType(F.getReturnType())) {
 308   default: assert(0 && "i have no idea where to return this type!");
 309   case MVT::isVoid: break;
 310   case MVT::i1:
 311   case MVT::i8:
 312   case MVT::i16:
 313   case MVT::i32:
 314   case MVT::i64:
 315     MF.addLiveOut(IA64::r8);
 316     break;
 317   case MVT::f32:
 318   case MVT::f64:
 319     MF.addLiveOut(IA64::F8);
 320     break;
 321   }
 322
 323   return ArgValues;
 324 }
 325
 326 std::pair<SDOperand, SDOperand>
 327 IA64TargetLowering::LowerCallTo(SDOperand Chain,
 328                                 const Type *RetTy, bool isVarArg,
 329                                 unsigned CallingConv, bool isTailCall,
 330                                 SDOperand Callee, ArgListTy &Args,
 331                                 SelectionDAG &DAG) {
 332
 333   MachineFunction &MF = DAG.getMachineFunction();
 334
 335   unsigned NumBytes = 16;
 336   unsigned outRegsUsed = 0;
 337
 338   if (Args.size() > 8) {
 339     NumBytes += (Args.size() - 8) * 8;
 340     outRegsUsed = 8;
 341   } else {
 342     outRegsUsed = Args.size();
 343   }
 344
 345   // FIXME? this WILL fail if we ever try to pass around an arg that
 346   // consumes more than a single output slot (a 'real' double, int128
 347   // some sort of aggregate etc.), as we'll underestimate how many 'outX'
 348   // registers we use. Hopefully, the assembler will notice.
 349   MF.getInfo<IA64FunctionInfo>()->outRegsUsed=
 350     std::max(outRegsUsed, MF.getInfo<IA64FunctionInfo>()->outRegsUsed);
 351
 352   Chain = DAG.getNode(ISD::CALLSEQ_START, MVT::Other, Chain,
 353                         DAG.getConstant(NumBytes, getPointerTy()));
 354
 355   std::vector<SDOperand> args_to_use;
 356   for (unsigned i = 0, e = Args.size(); i != e; ++i)
 357     {
 358       switch (getValueType(Args[i].second)) {
 359       default: assert(0 && "unexpected argument type!");
 360       case MVT::i1:
 361       case MVT::i8:
 362       case MVT::i16:
 363       case MVT::i32:
 364         //promote to 64-bits, sign/zero extending based on type
 365         //of the argument
 366         if(Args[i].second->isSigned())
 367           Args[i].first = DAG.getNode(ISD::SIGN_EXTEND, MVT::i64,
 368               Args[i].first);
 369         else
 370           Args[i].first = DAG.getNode(ISD::ZERO_EXTEND, MVT::i64,
 371               Args[i].first);
 372         break;
 373       case MVT::f32:
 374         //promote to 64-bits
 375         Args[i].first = DAG.getNode(ISD::FP_EXTEND, MVT::f64, Args[i].first);
 376       case MVT::f64:
 377       case MVT::i64:
 378         break;
 379       }
 380       args_to_use.push_back(Args[i].first);
 381     }
 382
 383   std::vector<MVT::ValueType> RetVals;
 384   MVT::ValueType RetTyVT = getValueType(RetTy);
 385   if (RetTyVT != MVT::isVoid)
 386     RetVals.push_back(RetTyVT);
 387   RetVals.push_back(MVT::Other);
 388
 389   SDOperand TheCall = SDOperand(DAG.getCall(RetVals, Chain,
 390                                             Callee, args_to_use), 0);
 391   Chain = TheCall.getValue(RetTyVT != MVT::isVoid);
 392   Chain = DAG.getNode(ISD::CALLSEQ_END, MVT::Other, Chain,
 393                       DAG.getConstant(NumBytes, getPointerTy()));
 394   return std::make_pair(TheCall, Chain);
 395 }
 396
 397 SDOperand
 398 IA64TargetLowering::LowerVAStart(SDOperand Chain, SDOperand VAListP,
 399                                  Value *VAListV, SelectionDAG &DAG) {
 400   // vastart just stores the address of the VarArgsFrameIndex slot.
 401   SDOperand FR = DAG.getFrameIndex(VarArgsFrameIndex, MVT::i64);
 402   return DAG.getNode(ISD::STORE, MVT::Other, Chain, FR,
 403                      VAListP, DAG.getSrcValue(VAListV));
 404 }
 405
 406 std::pair<SDOperand,SDOperand> IA64TargetLowering::
 407 LowerVAArg(SDOperand Chain, SDOperand VAListP, Value *VAListV,
 408            const Type *ArgTy, SelectionDAG &DAG) {
 409
 410   MVT::ValueType ArgVT = getValueType(ArgTy);
 411   SDOperand Val = DAG.getLoad(MVT::i64, Chain,
 412                               VAListP, DAG.getSrcValue(VAListV));
 413   SDOperand Result = DAG.getLoad(ArgVT, DAG.getEntryNode(), Val,
 414                                  DAG.getSrcValue(NULL));
 415   unsigned Amt;
 416   if (ArgVT == MVT::i32 || ArgVT == MVT::f32)
 417     Amt = 8;
 418   else {
 419     assert((ArgVT == MVT::i64 || ArgVT == MVT::f64) &&
 420            "Other types should have been promoted for varargs!");
 421     Amt = 8;
 422   }
 423   Val = DAG.getNode(ISD::ADD, Val.getValueType(), Val,
 424                     DAG.getConstant(Amt, Val.getValueType()));
 425   Chain = DAG.getNode(ISD::STORE, MVT::Other, Chain,
 426                       Val, VAListP, DAG.getSrcValue(VAListV));
 427   return std::make_pair(Result, Chain);
 428 }
 429
 430 namespace {
 431
 432   //===--------------------------------------------------------------------===//
 433   /// ISel - IA64 specific code to select IA64 machine instructions for
 434   /// SelectionDAG operations.
 435   ///
 436   class ISel : public SelectionDAGISel {
 437     /// IA64Lowering - This object fully describes how to lower LLVM code to an
 438     /// IA64-specific SelectionDAG.
 439     IA64TargetLowering IA64Lowering;
 440     SelectionDAG *ISelDAG; // Hack to support us having a dag->dag transform
 441                            // for sdiv and udiv until it is put into the future
 442                            // dag combiner
 443
 444     /// ExprMap - As shared expressions are codegen'd, we keep track of which
 445     /// vreg the value is produced in, so we only emit one copy of each compiled
 446     /// tree.
 447     std::map<SDOperand, unsigned> ExprMap;
 448     std::set<SDOperand> LoweredTokens;
 449
 450   public:
 451     ISel(TargetMachine &TM) : SelectionDAGISel(IA64Lowering), IA64Lowering(TM),
 452                               ISelDAG(0) { }
 453
 454     /// InstructionSelectBasicBlock - This callback is invoked by
 455     /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
 456     virtual void InstructionSelectBasicBlock(SelectionDAG &DAG);
 457
 458     unsigned SelectExpr(SDOperand N);
 459     void Select(SDOperand N);
 460     // a dag->dag to transform mul-by-constant-int to shifts+adds/subs
 461     SDOperand BuildConstmulSequence(SDOperand N);
 462
 463     const char *getPassName() const { return "IA64 Instruction Selector"; }
 464   };
 465 }
 466
 467 /// InstructionSelectBasicBlock - This callback is invoked by SelectionDAGISel
 468 /// when it has created a SelectionDAG for us to codegen.
 469 void ISel::InstructionSelectBasicBlock(SelectionDAG &DAG) {
 470
 471   // Codegen the basic block.
 472   ISelDAG = &DAG;
 473   Select(DAG.getRoot());
 474
 475   // Clear state used for selection.
 476   ExprMap.clear();
 477   LoweredTokens.clear();
 478   ISelDAG = 0;
 479 }
 480
 481 // strip leading '0' characters from a string
 482 void munchLeadingZeros(std::string& inString) {
 483   while(inString.c_str()[0]=='0') {
 484     inString.erase(0, 1);
 485   }
 486 }
 487
 488 // strip trailing '0' characters from a string
 489 void munchTrailingZeros(std::string& inString) {
 490   int curPos=inString.length()-1;
 491
 492   while(inString.c_str()[curPos]=='0') {
 493     inString.erase(curPos, 1);
 494     curPos--;
 495   }
 496 }
 497
 498 // return how many consecutive '0' characters are at the end of a string
 499 unsigned int countTrailingZeros(std::string& inString) {
 500   int curPos=inString.length()-1;
 501   unsigned int zeroCount=0;
 502   // assert goes here
 503   while(inString.c_str()[curPos--]=='0') {
 504     zeroCount++;
 505   }
 506   return zeroCount;
 507 }
 508
 509 // booth encode a string of '1' and '0' characters (returns string of 'P' (+1)
 510 // '0' and 'N' (-1) characters)
 511 void boothEncode(std::string inString, std::string& boothEncodedString) {
 512
 513   int curpos=0;
 514   int replacements=0;
 515   int lim=inString.size();
 516
 517   while(curpos<lim) {
 518     if(inString[curpos]=='1') { // if we see a '1', look for a run of them
 519       int runlength=0;
 520       std::string replaceString="N";
 521
 522       // find the run length
 523       for(;inString[curpos+runlength]=='1';runlength++) ;
 524
 525       for(int i=0; i<runlength-1; i++)
 526         replaceString+="0";
 527       replaceString+="1";
 528
 529       if(runlength>1) {
 530         inString.replace(curpos, runlength+1, replaceString);
 531         curpos+=runlength-1;
 532       } else
 533         curpos++;
 534     } else { // a zero, we just keep chugging along
 535       curpos++;
 536     }
 537   }
 538
 539   // clean up (trim the string, reverse it and turn '1's into 'P's)
 540   munchTrailingZeros(inString);
 541   boothEncodedString="";
 542
 543   for(int i=inString.size()-1;i>=0;i--)
 544     if(inString[i]=='1')
 545       boothEncodedString+="P";
 546     else
 547       boothEncodedString+=inString[i];
 548
 549 }
 550
 551 struct shiftaddblob { // this encodes stuff like (x=) "A << B [+-] C << D"
 552   unsigned firstVal;    // A
 553   unsigned firstShift;  // B
 554   unsigned secondVal;   // C
 555   unsigned secondShift; // D
 556   bool isSub;
 557 };
 558
 559 /* this implements Lefevre's "pattern-based" constant multiplication,
 560  * see "Multiplication by an Integer Constant", INRIA report 1999-06
 561  *
 562  * TODO: implement a method to try rewriting P0N<->0PP / N0P<->0NN
 563  * to get better booth encodings - this does help in practice
 564  * TODO: weight shifts appropriately (most architectures can't
 565  * fuse a shift and an add for arbitrary shift amounts) */
 566 unsigned lefevre(const std::string inString,
 567                  std::vector<struct shiftaddblob> &ops) {
 568   std::string retstring;
 569   std::string s = inString;
 570   munchTrailingZeros(s);
 571
 572   int length=s.length()-1;
 573
 574   if(length==0) {
 575     return(0);
 576   }
 577
 578   std::vector<int> p,n;
 579
 580   for(int i=0; i<=length; i++) {
 581     if (s.c_str()[length-i]=='P') {
 582       p.push_back(i);
 583     } else if (s.c_str()[length-i]=='N') {
 584       n.push_back(i);
 585     }
 586   }
 587
 588   std::string t, u;
 589   int c = 0;
 590   bool f;
 591   std::map<const int, int> w;
 592
 593   for(unsigned i=0; i<p.size(); i++) {
 594     for(unsigned j=0; j<i; j++) {
 595       w[p[i]-p[j]]++;
 596     }
 597   }
 598
 599   for(unsigned i=1; i<n.size(); i++) {
 600     for(unsigned j=0; j<i; j++) {
 601       w[n[i]-n[j]]++;
 602     }
 603   }
 604
 605   for(unsigned i=0; i<p.size(); i++) {
 606     for(unsigned j=0; j<n.size(); j++) {
 607       w[-abs(p[i]-n[j])]++;
 608     }
 609   }
 610
 611   std::map<const int, int>::const_iterator ii;
 612   std::vector<int> d;
 613   std::multimap<int, int> sorted_by_value;
 614
 615   for(ii = w.begin(); ii!=w.end(); ii++)
 616     sorted_by_value.insert(std::pair<int, int>((*ii).second,(*ii).first));
 617
 618   for (std::multimap<int, int>::iterator it = sorted_by_value.begin();
 619        it != sorted_by_value.end(); ++it) {
 620     d.push_back((*it).second);
 621   }
 622
 623   int int_W=0;
 624   int int_d;
 625
 626   while(d.size()>0 && (w[int_d=d.back()] > int_W)) {
 627     d.pop_back();
 628     retstring=s; // hmmm
 629     int x=0;
 630     int z=abs(int_d)-1;
 631
 632     if(int_d>0) {
 633
 634       for(unsigned base=0; base<retstring.size(); base++) {
 635         if( ((base+z+1) < retstring.size()) &&
 636            retstring.c_str()[base]=='P' &&
 637            retstring.c_str()[base+z+1]=='P')
 638         {
 639           // match
 640           x++;
 641           retstring.replace(base, 1, "0");
 642           retstring.replace(base+z+1, 1, "p");
 643         }
 644       }
 645
 646       for(unsigned base=0; base<retstring.size(); base++) {
 647         if( ((base+z+1) < retstring.size()) &&
 648            retstring.c_str()[base]=='N' &&
 649            retstring.c_str()[base+z+1]=='N')
 650         {
 651           // match
 652           x++;
 653           retstring.replace(base, 1, "0");
 654           retstring.replace(base+z+1, 1, "n");
 655         }
 656       }
 657
 658     } else {
 659       for(unsigned base=0; base<retstring.size(); base++) {
 660         if( ((base+z+1) < retstring.size()) &&
 661             ((retstring.c_str()[base]=='P' &&
 662              retstring.c_str()[base+z+1]=='N') ||
 663             (retstring.c_str()[base]=='N' &&
 664              retstring.c_str()[base+z+1]=='P')) ) {
 665           // match
 666           x++;
 667
 668           if(retstring.c_str()[base]=='P') {
 669             retstring.replace(base, 1, "0");
 670             retstring.replace(base+z+1, 1, "p");
 671           } else { // retstring[base]=='N'
 672             retstring.replace(base, 1, "0");
 673             retstring.replace(base+z+1, 1, "n");
 674           }
 675         }
 676       }
 677     }
 678
 679     if(x>int_W) {
 680       int_W = x;
 681       t = retstring;
 682       c = int_d; // tofix
 683     }
 684
 685   } d.pop_back(); // hmm
 686
 687   u = t;
 688
 689   for(unsigned i=0; i<t.length(); i++) {
 690     if(t.c_str()[i]=='p' || t.c_str()[i]=='n')
 691       t.replace(i, 1, "0");
 692   }
 693
 694   for(unsigned i=0; i<u.length(); i++) {
 695     if(u[i]=='P' || u[i]=='N')
 696       u.replace(i, 1, "0");
 697     if(u[i]=='p')
 698       u.replace(i, 1, "P");
 699     if(u[i]=='n')
 700       u.replace(i, 1, "N");
 701   }
 702
 703   if( c<0 ) {
 704     f=true;
 705     c=-c;
 706   } else
 707     f=false;
 708
 709   int pos=0;
 710   while(u[pos]=='0')
 711     pos++;
 712
 713   bool hit=(u[pos]=='N');
 714
 715   int g=0;
 716   if(hit) {
 717     g=1;
 718     for(unsigned p=0; p<u.length(); p++) {
 719       bool isP=(u[p]=='P');
 720       bool isN=(u[p]=='N');
 721
 722       if(isP)
 723         u.replace(p, 1, "N");
 724       if(isN)
 725         u.replace(p, 1, "P");
 726     }
 727   }
 728
 729   munchLeadingZeros(u);
 730
 731   int i = lefevre(u, ops);
 732
 733   shiftaddblob blob;
 734
 735   blob.firstVal=i; blob.firstShift=c;
 736   blob.isSub=f;
 737   blob.secondVal=i; blob.secondShift=0;
 738
 739   ops.push_back(blob);
 740
 741   i = ops.size();
 742
 743   munchLeadingZeros(t);
 744
 745   if(t.length()==0)
 746     return i;
 747
 748   if(t.c_str()[0]!='P') {
 749     g=2;
 750     for(unsigned p=0; p<t.length(); p++) {
 751       bool isP=(t.c_str()[p]=='P');
 752       bool isN=(t.c_str()[p]=='N');
 753
 754       if(isP)
 755         t.replace(p, 1, "N");
 756       if(isN)
 757         t.replace(p, 1, "P");
 758     }
 759   }
 760
 761   int j = lefevre(t, ops);
 762
 763   int trail=countTrailingZeros(u);
 764   blob.secondVal=i; blob.secondShift=trail;
 765
 766   trail=countTrailingZeros(t);
 767   blob.firstVal=j; blob.firstShift=trail;
 768
 769   switch(g) {
 770     case 0:
 771       blob.isSub=false; // first + second
 772       break;
 773     case 1:
 774       blob.isSub=true; // first - second
 775       break;
 776     case 2:
 777       blob.isSub=true; // second - first
 778       int tmpval, tmpshift;
 779       tmpval=blob.firstVal;
 780       tmpshift=blob.firstShift;
 781       blob.firstVal=blob.secondVal;
 782       blob.firstShift=blob.secondShift;
 783       blob.secondVal=tmpval;
 784       blob.secondShift=tmpshift;
 785       break;
 786       //assert
 787   }
 788
 789   ops.push_back(blob);
 790   return ops.size();
 791 }
 792
 793 SDOperand ISel::BuildConstmulSequence(SDOperand N) {
 794   //FIXME: we should shortcut this stuff for multiplies by 2^n+1
 795   //       in particular, *3 is nicer as *2+1, not *4-1
 796   int64_t constant=cast<ConstantSDNode>(N.getOperand(1))->getValue();
 797
 798   bool flippedSign;
 799   unsigned preliminaryShift=0;
 800
 801   assert(constant != 0 && "erk, you're trying to multiply by constant zero\n");
 802
 803   // first, we make the constant to multiply by positive
 804   if(constant<0) {
 805     constant=-constant;
 806     flippedSign=true;
 807   } else {
 808     flippedSign=false;
 809   }
 810
 811   // next, we make it odd.
 812   for(; (constant%2==0); preliminaryShift++)
 813     constant>>=1;
 814
 815   //OK, we have a positive, odd number of 64 bits or less. Convert it
 816   //to a binary string, constantString[0] is the LSB
 817   char constantString[65];
 818   for(int i=0; i<64; i++)
 819     constantString[i]='0'+((constant>>i)&0x1);
 820   constantString[64]=0;
 821
 822   // now, Booth encode it
 823   std::string boothEncodedString;
 824   boothEncode(constantString, boothEncodedString);
 825
 826   std::vector<struct shiftaddblob> ops;
 827   // do the transformation, filling out 'ops'
 828   lefevre(boothEncodedString, ops);
 829
 830   assert(ops.size() < 80 && "constmul code has gone haywire\n");
 831   SDOperand results[80]; // temporary results (of adds/subs of shifts)
 832
 833   // now turn 'ops' into DAG bits
 834   for(unsigned i=0; i<ops.size(); i++) {
 835     SDOperand amt = ISelDAG->getConstant(ops[i].firstShift, MVT::i64);
 836     SDOperand val = (ops[i].firstVal == 0) ? N.getOperand(0) :
 837       results[ops[i].firstVal-1];
 838     SDOperand left = ISelDAG->getNode(ISD::SHL, MVT::i64, val, amt);
 839     amt = ISelDAG->getConstant(ops[i].secondShift, MVT::i64);
 840     val = (ops[i].secondVal == 0) ? N.getOperand(0) :
 841       results[ops[i].secondVal-1];
 842     SDOperand right = ISelDAG->getNode(ISD::SHL, MVT::i64, val, amt);
 843     if(ops[i].isSub)
 844       results[i] = ISelDAG->getNode(ISD::SUB, MVT::i64, left, right);
 845     else
 846       results[i] = ISelDAG->getNode(ISD::ADD, MVT::i64, left, right);
 847   }
 848
 849   // don't forget flippedSign and preliminaryShift!
 850   SDOperand shiftedresult;
 851   if(preliminaryShift) {
 852     SDOperand finalshift = ISelDAG->getConstant(preliminaryShift, MVT::i64);
 853     shiftedresult = ISelDAG->getNode(ISD::SHL, MVT::i64,
 854         results[ops.size()-1], finalshift);
 855   } else { // there was no preliminary divide-by-power-of-2 required
 856     shiftedresult = results[ops.size()-1];
 857   }
 858
 859   SDOperand finalresult;
 860   if(flippedSign) { // if we were multiplying by a negative constant:
 861     SDOperand zero = ISelDAG->getConstant(0, MVT::i64);
 862     // subtract the result from 0 to flip its sign
 863     finalresult = ISelDAG->getNode(ISD::SUB, MVT::i64, zero, shiftedresult);
 864   } else { // there was no preliminary multiply by -1 required
 865     finalresult = shiftedresult;
 866   }
 867
 868   return finalresult;
 869 }
 870
 871 /// ponderIntegerDivisionBy - When handling integer divides, if the divide
 872 /// is by a constant such that we can efficiently codegen it, this
 873 /// function says what to do. Currently, it returns 0 if the division must
 874 /// become a genuine divide, and 1 if the division can be turned into a
 875 /// right shift.
 876 static unsigned ponderIntegerDivisionBy(SDOperand N, bool isSigned,
 877                                       unsigned& Imm) {
 878   if (N.getOpcode() != ISD::Constant) return 0; // if not a divide by
 879                                                 // a constant, give up.
 880
 881   int64_t v = (int64_t)cast<ConstantSDNode>(N)->getSignExtended();
 882
 883   if (isPowerOf2_64(v)) { // if a division by a power of two, say so
 884     Imm = Log2_64(v);
 885     return 1;
 886   }
 887
 888   return 0; // fallthrough
 889 }
 890
 891 static unsigned ponderIntegerAndWith(SDOperand N, unsigned& Imm) {
 892   if (N.getOpcode() != ISD::Constant) return 0; // if not ANDing with
 893                                                 // a constant, give up.
 894
 895   int64_t v = (int64_t)cast<ConstantSDNode>(N)->getSignExtended();
 896
 897   if (isMask_64(v)) { // if ANDing with ((2^n)-1) for some n
 898     Imm = Log2_64(v) + 1;
 899     return 1; // say so
 900   }
 901
 902   return 0; // fallthrough
 903 }
 904
 905 static unsigned ponderIntegerAdditionWith(SDOperand N, unsigned& Imm) {
 906   if (N.getOpcode() != ISD::Constant) return 0; // if not adding a
 907                                                 // constant, give up.
 908   int64_t v = (int64_t)cast<ConstantSDNode>(N)->getSignExtended();
 909
 910   if (v <= 8191 && v >= -8192) { // if this constants fits in 14 bits, say so
 911     Imm = v & 0x3FFF; // 14 bits
 912     return 1;
 913   }
 914   return 0; // fallthrough
 915 }
 916
 917 static unsigned ponderIntegerSubtractionFrom(SDOperand N, unsigned& Imm) {
 918   if (N.getOpcode() != ISD::Constant) return 0; // if not subtracting a
 919                                                 // constant, give up.
 920   int64_t v = (int64_t)cast<ConstantSDNode>(N)->getSignExtended();
 921
 922   if (v <= 127 && v >= -128) { // if this constants fits in 8 bits, say so
 923     Imm = v & 0xFF; // 8 bits
 924     return 1;
 925   }
 926   return 0; // fallthrough
 927 }
 928
 929 unsigned ISel::SelectExpr(SDOperand N) {
 930   unsigned Result;
 931   unsigned Tmp1, Tmp2, Tmp3;
 932   unsigned Opc = 0;
 933   MVT::ValueType DestType = N.getValueType();
 934
 935   unsigned opcode = N.getOpcode();
 936
 937   SDNode *Node = N.Val;
 938   SDOperand Op0, Op1;
 939
 940   if (Node->getOpcode() == ISD::CopyFromReg)
 941     // Just use the specified register as our input.
 942     return cast<RegisterSDNode>(Node->getOperand(1))->getReg();
 943
 944   unsigned &Reg = ExprMap[N];
 945   if (Reg) return Reg;
 946
 947   if (N.getOpcode() != ISD::CALL && N.getOpcode() != ISD::TAILCALL)
 948     Reg = Result = (N.getValueType() != MVT::Other) ?
 949       MakeReg(N.getValueType()) : 1;
 950   else {
 951     // If this is a call instruction, make sure to prepare ALL of the result
 952     // values as well as the chain.
 953     if (Node->getNumValues() == 1)
 954       Reg = Result = 1;  // Void call, just a chain.
 955     else {
 956       Result = MakeReg(Node->getValueType(0));
 957       ExprMap[N.getValue(0)] = Result;
 958       for (unsigned i = 1, e = N.Val->getNumValues()-1; i != e; ++i)
 959         ExprMap[N.getValue(i)] = MakeReg(Node->getValueType(i));
 960       ExprMap[SDOperand(Node, Node->getNumValues()-1)] = 1;
 961     }
 962   }
 963
 964   switch (N.getOpcode()) {
 965   default:
 966     Node->dump();
 967     assert(0 && "Node not handled!\n");
 968
 969   case ISD::FrameIndex: {
 970     Tmp1 = cast<FrameIndexSDNode>(N)->getIndex();
 971     BuildMI(BB, IA64::MOV, 1, Result).addFrameIndex(Tmp1);
 972     return Result;
 973   }
 974
 975   case ISD::ConstantPool: {
 976     Tmp1 = BB->getParent()->getConstantPool()->
 977           getConstantPoolIndex(cast<ConstantPoolSDNode>(N)->get());
 978     IA64Lowering.restoreGP(BB); // FIXME: do i really need this?
 979     BuildMI(BB, IA64::ADD, 2, Result).addConstantPoolIndex(Tmp1)
 980       .addReg(IA64::r1);
 981     return Result;
 982   }
 983
 984   case ISD::ConstantFP: {
 985     Tmp1 = Result;   // Intermediate Register
 986     if (cast<ConstantFPSDNode>(N)->getValue() < 0.0 ||
 987         cast<ConstantFPSDNode>(N)->isExactlyValue(-0.0))
 988       Tmp1 = MakeReg(MVT::f64);
 989
 990     if (cast<ConstantFPSDNode>(N)->isExactlyValue(+0.0) ||
 991         cast<ConstantFPSDNode>(N)->isExactlyValue(-0.0))
 992       BuildMI(BB, IA64::FMOV, 1, Tmp1).addReg(IA64::F0); // load 0.0
 993     else if (cast<ConstantFPSDNode>(N)->isExactlyValue(+1.0) ||
 994              cast<ConstantFPSDNode>(N)->isExactlyValue(-1.0))
 995       BuildMI(BB, IA64::FMOV, 1, Tmp1).addReg(IA64::F1); // load 1.0
 996     else
 997       assert(0 && "Unexpected FP constant!");
 998     if (Tmp1 != Result)
 999       // we multiply by +1.0, negate (this is FNMA), and then add 0.0
1000       BuildMI(BB, IA64::FNMA, 3, Result).addReg(Tmp1).addReg(IA64::F1)
1001         .addReg(IA64::F0);
1002     return Result;
1003   }
1004
1005   case ISD::DYNAMIC_STACKALLOC: {
1006     // Generate both result values.
1007     if (Result != 1)
1008       ExprMap[N.getValue(1)] = 1;   // Generate the token
1009     else
1010       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
1011
1012     // FIXME: We are currently ignoring the requested alignment for handling
1013     // greater than the stack alignment.  This will need to be revisited at some
1014     // point.  Align = N.getOperand(2);
1015
1016     if (!isa<ConstantSDNode>(N.getOperand(2)) ||
1017         cast<ConstantSDNode>(N.getOperand(2))->getValue() != 0) {
1018       std::cerr << "Cannot allocate stack object with greater alignment than"
1019                 << " the stack alignment yet!";
1020       abort();
1021     }
1022
1023 /*
1024     Select(N.getOperand(0));
1025     if (ConstantSDNode* CN = dyn_cast<ConstantSDNode>(N.getOperand(1)))
1026     {
1027       if (CN->getValue() < 32000)
1028       {
1029         BuildMI(BB, IA64::ADDIMM22, 2, IA64::r12).addReg(IA64::r12)
1030           .addImm(-CN->getValue());
1031       } else {
1032         Tmp1 = SelectExpr(N.getOperand(1));
1033         // Subtract size from stack pointer, thereby allocating some space.
1034         BuildMI(BB, IA64::SUB, 2, IA64::r12).addReg(IA64::r12).addReg(Tmp1);
1035       }
1036     } else {
1037       Tmp1 = SelectExpr(N.getOperand(1));
1038       // Subtract size from stack pointer, thereby allocating some space.
1039       BuildMI(BB, IA64::SUB, 2, IA64::r12).addReg(IA64::r12).addReg(Tmp1);
1040     }
1041 */
1042     Select(N.getOperand(0));
1043     Tmp1 = SelectExpr(N.getOperand(1));
1044     // Subtract size from stack pointer, thereby allocating some space.
1045     BuildMI(BB, IA64::SUB, 2, IA64::r12).addReg(IA64::r12).addReg(Tmp1);
1046     // Put a pointer to the space into the result register, by copying the
1047     // stack pointer.
1048     BuildMI(BB, IA64::MOV, 1, Result).addReg(IA64::r12);
1049     return Result;
1050   }
1051
1052   case ISD::SELECT: {
1053       Tmp1 = SelectExpr(N.getOperand(0)); //Cond
1054       Tmp2 = SelectExpr(N.getOperand(1)); //Use if TRUE
1055       Tmp3 = SelectExpr(N.getOperand(2)); //Use if FALSE
1056
1057       unsigned bogoResult;
1058
1059       switch (N.getOperand(1).getValueType()) {
1060         default: assert(0 &&
1061         "ISD::SELECT: 'select'ing something other than i1, i64 or f64!\n");
1062         // for i1, we load the condition into an integer register, then
1063         // conditionally copy Tmp2 and Tmp3 to Tmp1 in parallel (only one
1064         // of them will go through, since the integer register will hold
1065         // either 0 or 1)
1066         case MVT::i1: {
1067           bogoResult=MakeReg(MVT::i1);
1068
1069           // load the condition into an integer register
1070           unsigned condReg=MakeReg(MVT::i64);
1071           unsigned dummy=MakeReg(MVT::i64);
1072           BuildMI(BB, IA64::MOV, 1, dummy).addReg(IA64::r0);
1073           BuildMI(BB, IA64::TPCADDIMM22, 2, condReg).addReg(dummy)
1074             .addImm(1).addReg(Tmp1);
1075
1076           // initialize Result (bool) to false (hence UNC) and if
1077           // the select condition (condReg) is false (0), copy Tmp3
1078           BuildMI(BB, IA64::PCMPEQUNC, 3, bogoResult)
1079             .addReg(condReg).addReg(IA64::r0).addReg(Tmp3);
1080
1081           // now, if the selection condition is true, write 1 to the
1082           // result if Tmp2 is 1
1083           BuildMI(BB, IA64::TPCMPNE, 3, Result).addReg(bogoResult)
1084             .addReg(condReg).addReg(IA64::r0).addReg(Tmp2);
1085           break;
1086         }
1087         // for i64/f64, we just copy Tmp3 and then conditionally overwrite it
1088         // with Tmp2 if Tmp1 is true
1089         case MVT::i64:
1090           bogoResult=MakeReg(MVT::i64);
1091           BuildMI(BB, IA64::MOV, 1, bogoResult).addReg(Tmp3);
1092           BuildMI(BB, IA64::CMOV, 2, Result).addReg(bogoResult).addReg(Tmp2)
1093             .addReg(Tmp1);
1094           break;
1095         case MVT::f64:
1096           bogoResult=MakeReg(MVT::f64);
1097           BuildMI(BB, IA64::FMOV, 1, bogoResult).addReg(Tmp3);
1098           BuildMI(BB, IA64::CFMOV, 2, Result).addReg(bogoResult).addReg(Tmp2)
1099             .addReg(Tmp1);
1100           break;
1101       }
1102
1103       return Result;
1104   }
1105
1106   case ISD::Constant: {
1107     unsigned depositPos=0;
1108     unsigned depositLen=0;
1109     switch (N.getValueType()) {
1110       default: assert(0 && "Cannot use constants of this type!");
1111       case MVT::i1: { // if a bool, we don't 'load' so much as generate
1112         // the constant:
1113         if(cast<ConstantSDNode>(N)->getValue())  // true:
1114           BuildMI(BB, IA64::CMPEQ, 2, Result).addReg(IA64::r0).addReg(IA64::r0);
1115         else // false:
1116           BuildMI(BB, IA64::CMPNE, 2, Result).addReg(IA64::r0).addReg(IA64::r0);
1117         return Result; // early exit
1118       }
1119       case MVT::i64: break;
1120     }
1121
1122     int64_t immediate = cast<ConstantSDNode>(N)->getValue();
1123
1124     if(immediate==0) { // if the constant is just zero,
1125       BuildMI(BB, IA64::MOV, 1, Result).addReg(IA64::r0); // just copy r0
1126       return Result; // early exit
1127     }
1128
1129     if (immediate <= 8191 && immediate >= -8192) {
1130       // if this constants fits in 14 bits, we use a mov the assembler will
1131       // turn into:   "adds rDest=imm,r0"  (and _not_ "andl"...)
1132       BuildMI(BB, IA64::MOVSIMM14, 1, Result).addSImm(immediate);
1133       return Result; // early exit
1134     }
1135
1136     if (immediate <= 2097151 && immediate >= -2097152) {
1137       // if this constants fits in 22 bits, we use a mov the assembler will
1138       // turn into:   "addl rDest=imm,r0"
1139       BuildMI(BB, IA64::MOVSIMM22, 1, Result).addSImm(immediate);
1140       return Result; // early exit
1141     }
1142
1143     /* otherwise, our immediate is big, so we use movl */
1144     uint64_t Imm = immediate;
1145     BuildMI(BB, IA64::MOVLIMM64, 1, Result).addImm64(Imm);
1146     return Result;
1147   }
1148
1149   case ISD::UNDEF: {
1150     BuildMI(BB, IA64::IDEF, 0, Result);
1151     return Result;
1152   }
1153
1154   case ISD::GlobalAddress: {
1155     GlobalValue *GV = cast<GlobalAddressSDNode>(N)->getGlobal();
1156     unsigned Tmp1 = MakeReg(MVT::i64);
1157
1158     BuildMI(BB, IA64::ADD, 2, Tmp1).addGlobalAddress(GV).addReg(IA64::r1);
1159     BuildMI(BB, IA64::LD8, 1, Result).addReg(Tmp1);
1160
1161     return Result;
1162   }
1163
1164   case ISD::ExternalSymbol: {
1165     const char *Sym = cast<ExternalSymbolSDNode>(N)->getSymbol();
1166 // assert(0 && "sorry, but what did you want an ExternalSymbol for again?");
1167     BuildMI(BB, IA64::MOV, 1, Result).addExternalSymbol(Sym); // XXX
1168     return Result;
1169   }
1170
1171   case ISD::FP_EXTEND: {
1172     Tmp1 = SelectExpr(N.getOperand(0));
1173     BuildMI(BB, IA64::FMOV, 1, Result).addReg(Tmp1);
1174     return Result;
1175   }
1176
1177   case ISD::ANY_EXTEND:
1178   case ISD::ZERO_EXTEND: {
1179     Tmp1 = SelectExpr(N.getOperand(0)); // value
1180
1181     assert(N.getOperand(0).getValueType() == MVT::i1 &&
1182            "Cannot zero-extend this type!");
1183
1184     // if the predicate reg has 1, we want a '1' in our GR.
1185     unsigned dummy = MakeReg(MVT::i64);
1186     // first load zero:
1187     BuildMI(BB, IA64::MOV, 1, dummy).addReg(IA64::r0);
1188     // ...then conditionally (PR:Tmp1) add 1:
1189     BuildMI(BB, IA64::TPCADDIMM22, 2, Result).addReg(dummy)
1190       .addImm(1).addReg(Tmp1);
1191     return Result; // XXX early exit!
1192   }
1193
1194   case ISD::SIGN_EXTEND:
1195     assert(N.getOperand(0).getValueType() == MVT::i1 &&
1196            "Cannot zero-extend this type!");
1197
1198     Tmp1 = SelectExpr(N.getOperand(0)); // value
1199     assert(0 && "don't know how to sign_extend from bool yet!");
1200     abort();
1201
1202   case ISD::TRUNCATE:
1203     // we use the funky dep.z (deposit (zero)) instruction to deposit bits
1204     // of R0 appropriately.
1205     assert(N.getOperand(0).getValueType() == MVT::i64 &&
1206            N.getValueType() == MVT::i1 && "Unknown truncate!");
1207     Tmp1 = SelectExpr(N.getOperand(0));
1208
1209     // if input (normal reg) is 0, 0!=0 -> false (0), if 1, 1!=0 ->true (1):
1210     BuildMI(BB, IA64::CMPNE, 2, Result).addReg(Tmp1).addReg(IA64::r0);
1211     return Result; // XXX early exit!
1212
1213 /*
1214   case ISD::FP_ROUND: {
1215     assert (DestType == MVT::f32 && N.getOperand(0).getValueType() == MVT::f64 &&
1216   "error: trying to FP_ROUND something other than f64 -> f32!\n");
1217     Tmp1 = SelectExpr(N.getOperand(0));
1218     BuildMI(BB, IA64::FADDS, 2, Result).addReg(Tmp1).addReg(IA64::F0);
1219     // we add 0.0 using a single precision add to do rounding
1220     return Result;
1221   }
1222 */
1223
1224 // FIXME: the following 4 cases need cleaning
1225   case ISD::SINT_TO_FP: {
1226     Tmp1 = SelectExpr(N.getOperand(0));
1227     Tmp2 = MakeReg(MVT::f64);
1228     unsigned dummy = MakeReg(MVT::f64);
1229     BuildMI(BB, IA64::SETFSIG, 1, Tmp2).addReg(Tmp1);
1230     BuildMI(BB, IA64::FCVTXF, 1, dummy).addReg(Tmp2);
1231     BuildMI(BB, IA64::FNORMD, 1, Result).addReg(dummy);
1232     return Result;
1233   }
1234
1235   case ISD::UINT_TO_FP: {
1236     Tmp1 = SelectExpr(N.getOperand(0));
1237     Tmp2 = MakeReg(MVT::f64);
1238     unsigned dummy = MakeReg(MVT::f64);
1239     BuildMI(BB, IA64::SETFSIG, 1, Tmp2).addReg(Tmp1);
1240     BuildMI(BB, IA64::FCVTXUF, 1, dummy).addReg(Tmp2);
1241     BuildMI(BB, IA64::FNORMD, 1, Result).addReg(dummy);
1242     return Result;
1243   }
1244
1245   case ISD::FP_TO_SINT: {
1246     Tmp1 = SelectExpr(N.getOperand(0));
1247     Tmp2 = MakeReg(MVT::f64);
1248     BuildMI(BB, IA64::FCVTFXTRUNC, 1, Tmp2).addReg(Tmp1);
1249     BuildMI(BB, IA64::GETFSIG, 1, Result).addReg(Tmp2);
1250     return Result;
1251   }
1252
1253   case ISD::FP_TO_UINT: {
1254     Tmp1 = SelectExpr(N.getOperand(0));
1255     Tmp2 = MakeReg(MVT::f64);
1256     BuildMI(BB, IA64::FCVTFXUTRUNC, 1, Tmp2).addReg(Tmp1);
1257     BuildMI(BB, IA64::GETFSIG, 1, Result).addReg(Tmp2);
1258     return Result;
1259   }
1260
1261   case ISD::FADD: {
1262     if (N.getOperand(0).getOpcode() == ISD::FMUL &&
1263         N.getOperand(0).Val->hasOneUse()) { // if we can fold this add
1264                                             // into an fma, do so:
1265                                             // ++FusedFP; // Statistic
1266       Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1267       Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1268       Tmp3 = SelectExpr(N.getOperand(1));
1269       BuildMI(BB, IA64::FMA, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1270       return Result; // early exit
1271     }
1272
1273     //else, fallthrough:
1274     Tmp1 = SelectExpr(N.getOperand(0));
1275     Tmp2 = SelectExpr(N.getOperand(1));
1276     BuildMI(BB, IA64::FADD, 2, Result).addReg(Tmp1).addReg(Tmp2);
1277     return Result;
1278   }
1279
1280   case ISD::ADD: {
1281     if (N.getOperand(0).getOpcode() == ISD::SHL &&
1282         N.getOperand(0).Val->hasOneUse()) { // if we might be able to fold
1283                                             // this add into a shladd, try:
1284       ConstantSDNode *CSD = NULL;
1285       if((CSD = dyn_cast<ConstantSDNode>(N.getOperand(0).getOperand(1))) &&
1286           (CSD->getValue() >= 1) && (CSD->getValue() <= 4) ) { // we can:
1287
1288         // ++FusedSHLADD; // Statistic
1289         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1290         int shl_amt = CSD->getValue();
1291         Tmp3 = SelectExpr(N.getOperand(1));
1292
1293         BuildMI(BB, IA64::SHLADD, 3, Result)
1294           .addReg(Tmp1).addImm(shl_amt).addReg(Tmp3);
1295         return Result; // early exit
1296       }
1297     }
1298
1299     //else, fallthrough:
1300     Tmp1 = SelectExpr(N.getOperand(0));
1301     switch (ponderIntegerAdditionWith(N.getOperand(1), Tmp3)) {
1302       case 1: // adding a constant that's 14 bits
1303         BuildMI(BB, IA64::ADDIMM14, 2, Result).addReg(Tmp1).addSImm(Tmp3);
1304         return Result; // early exit
1305     } // fallthrough and emit a reg+reg ADD:
1306     Tmp2 = SelectExpr(N.getOperand(1));
1307     BuildMI(BB, IA64::ADD, 2, Result).addReg(Tmp1).addReg(Tmp2);
1308     return Result;
1309   }
1310
1311   case ISD::FMUL:
1312     Tmp1 = SelectExpr(N.getOperand(0));
1313     Tmp2 = SelectExpr(N.getOperand(1));
1314     BuildMI(BB, IA64::FMPY, 2, Result).addReg(Tmp1).addReg(Tmp2);
1315     return Result;
1316
1317   case ISD::MUL: {
1318
1319     // TODO: speed!
1320 /* FIXME if(N.getOperand(1).getOpcode() != ISD::Constant) { // if not a const mul
1321  */
1322       // boring old integer multiply with xma
1323       Tmp1 = SelectExpr(N.getOperand(0));
1324       Tmp2 = SelectExpr(N.getOperand(1));
1325
1326       unsigned TempFR1=MakeReg(MVT::f64);
1327       unsigned TempFR2=MakeReg(MVT::f64);
1328       unsigned TempFR3=MakeReg(MVT::f64);
1329       BuildMI(BB, IA64::SETFSIG, 1, TempFR1).addReg(Tmp1);
1330       BuildMI(BB, IA64::SETFSIG, 1, TempFR2).addReg(Tmp2);
1331       BuildMI(BB, IA64::XMAL, 1, TempFR3).addReg(TempFR1).addReg(TempFR2)
1332         .addReg(IA64::F0);
1333       BuildMI(BB, IA64::GETFSIG, 1, Result).addReg(TempFR3);
1334       return Result; // early exit
1335    /* FIXME } else { // we are multiplying by an integer constant! yay
1336       return Reg = SelectExpr(BuildConstmulSequence(N)); // avert your eyes!
1337     } */
1338   }
1339
1340   case ISD::FSUB:
1341     if(N.getOperand(0).getOpcode() == ISD::FMUL &&
1342        N.getOperand(0).Val->hasOneUse()) { // if we can fold this sub
1343                                            // into an fms, do so:
1344                                            // ++FusedFP; // Statistic
1345       Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1346       Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1347       Tmp3 = SelectExpr(N.getOperand(1));
1348       BuildMI(BB, IA64::FMS, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1349       return Result; // early exit
1350     }
1351
1352     Tmp2 = SelectExpr(N.getOperand(1));
1353     Tmp1 = SelectExpr(N.getOperand(0));
1354     BuildMI(BB, IA64::FSUB, 2, Result).addReg(Tmp1).addReg(Tmp2);
1355     return Result;
1356
1357   case ISD::SUB: {
1358     Tmp2 = SelectExpr(N.getOperand(1));
1359     switch (ponderIntegerSubtractionFrom(N.getOperand(0), Tmp3)) {
1360       case 1: // subtracting *from* an 8 bit constant:
1361         BuildMI(BB, IA64::SUBIMM8, 2, Result).addSImm(Tmp3).addReg(Tmp2);
1362         return Result; // early exit
1363     } // fallthrough and emit a reg+reg SUB:
1364     Tmp1 = SelectExpr(N.getOperand(0));
1365     BuildMI(BB, IA64::SUB, 2, Result).addReg(Tmp1).addReg(Tmp2);
1366     return Result;
1367   }
1368
1369   case ISD::FABS: {
1370     Tmp1 = SelectExpr(N.getOperand(0));
1371     assert(DestType == MVT::f64 && "trying to fabs something other than f64?");
1372     BuildMI(BB, IA64::FABS, 1, Result).addReg(Tmp1);
1373     return Result;
1374   }
1375
1376   case ISD::FNEG: {
1377     assert(DestType == MVT::f64 && "trying to fneg something other than f64?");
1378
1379     if (ISD::FABS == N.getOperand(0).getOpcode()) { // && hasOneUse()?
1380       Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1381       BuildMI(BB, IA64::FNEGABS, 1, Result).addReg(Tmp1); // fold in abs
1382     } else {
1383       Tmp1 = SelectExpr(N.getOperand(0));
1384       BuildMI(BB, IA64::FNEG, 1, Result).addReg(Tmp1); // plain old fneg
1385     }
1386
1387     return Result;
1388   }
1389
1390   case ISD::AND: {
1391      switch (N.getValueType()) {
1392     default: assert(0 && "Cannot AND this type!");
1393     case MVT::i1: { // if a bool, we emit a pseudocode AND
1394       unsigned pA = SelectExpr(N.getOperand(0));
1395       unsigned pB = SelectExpr(N.getOperand(1));
1396
1397 /* our pseudocode for AND is:
1398  *
1399 (pA) cmp.eq.unc pC,p0 = r0,r0   // pC = pA
1400      cmp.eq pTemp,p0 = r0,r0    // pTemp = NOT pB
1401      ;;
1402 (pB) cmp.ne pTemp,p0 = r0,r0
1403      ;;
1404 (pTemp)cmp.ne pC,p0 = r0,r0    // if (NOT pB) pC = 0
1405
1406 */
1407       unsigned pTemp = MakeReg(MVT::i1);
1408
1409       unsigned bogusTemp1 = MakeReg(MVT::i1);
1410       unsigned bogusTemp2 = MakeReg(MVT::i1);
1411       unsigned bogusTemp3 = MakeReg(MVT::i1);
1412       unsigned bogusTemp4 = MakeReg(MVT::i1);
1413
1414       BuildMI(BB, IA64::PCMPEQUNC, 3, bogusTemp1)
1415         .addReg(IA64::r0).addReg(IA64::r0).addReg(pA);
1416       BuildMI(BB, IA64::CMPEQ, 2, bogusTemp2)
1417         .addReg(IA64::r0).addReg(IA64::r0);
1418       BuildMI(BB, IA64::TPCMPNE, 3, pTemp)
1419         .addReg(bogusTemp2).addReg(IA64::r0).addReg(IA64::r0).addReg(pB);
1420       BuildMI(BB, IA64::TPCMPNE, 3, Result)
1421         .addReg(bogusTemp1).addReg(IA64::r0).addReg(IA64::r0).addReg(pTemp);
1422       break;
1423     }
1424
1425     // if not a bool, we just AND away:
1426     case MVT::i8:
1427     case MVT::i16:
1428     case MVT::i32:
1429     case MVT::i64: {
1430       Tmp1 = SelectExpr(N.getOperand(0));
1431       switch (ponderIntegerAndWith(N.getOperand(1), Tmp3)) {
1432         case 1: // ANDing a constant that is 2^n-1 for some n
1433           switch (Tmp3) {
1434             case 8:  // if AND 0x00000000000000FF, be quaint and use zxt1
1435               BuildMI(BB, IA64::ZXT1, 1, Result).addReg(Tmp1);
1436               break;
1437             case 16: // if AND 0x000000000000FFFF, be quaint and use zxt2
1438               BuildMI(BB, IA64::ZXT2, 1, Result).addReg(Tmp1);
1439               break;
1440             case 32: // if AND 0x00000000FFFFFFFF, be quaint and use zxt4
1441               BuildMI(BB, IA64::ZXT4, 1, Result).addReg(Tmp1);
1442               break;
1443             default: // otherwise, use dep.z to paste zeros
1444             // FIXME: assert the dep.z is in bounds
1445               BuildMI(BB, IA64::DEPZ, 3, Result).addReg(Tmp1)
1446                 .addImm(0).addImm(Tmp3);
1447               break;
1448           }
1449           return Result; // early exit
1450       } // fallthrough and emit a simple AND:
1451       Tmp2 = SelectExpr(N.getOperand(1));
1452       BuildMI(BB, IA64::AND, 2, Result).addReg(Tmp1).addReg(Tmp2);
1453     }
1454     }
1455     return Result;
1456   }
1457
1458   case ISD::OR: {
1459   switch (N.getValueType()) {
1460     default: assert(0 && "Cannot OR this type!");
1461     case MVT::i1: { // if a bool, we emit a pseudocode OR
1462       unsigned pA = SelectExpr(N.getOperand(0));
1463       unsigned pB = SelectExpr(N.getOperand(1));
1464
1465       unsigned pTemp1 = MakeReg(MVT::i1);
1466
1467 /* our pseudocode for OR is:
1468  *
1469
1470 pC = pA OR pB
1471 -------------
1472
1473 (pA) cmp.eq.unc pC,p0 = r0,r0  // pC = pA
1474  ;;
1475 (pB) cmp.eq pC,p0 = r0,r0 // if (pB) pC = 1
1476
1477 */
1478       BuildMI(BB, IA64::PCMPEQUNC, 3, pTemp1)
1479         .addReg(IA64::r0).addReg(IA64::r0).addReg(pA);
1480       BuildMI(BB, IA64::TPCMPEQ, 4, Result)
1481         .addReg(pTemp1).addReg(IA64::r0).addReg(IA64::r0).addReg(pB);
1482       break;
1483     }
1484     // if not a bool, we just OR away:
1485     case MVT::i8:
1486     case MVT::i16:
1487     case MVT::i32:
1488     case MVT::i64: {
1489       Tmp1 = SelectExpr(N.getOperand(0));
1490       Tmp2 = SelectExpr(N.getOperand(1));
1491       BuildMI(BB, IA64::OR, 2, Result).addReg(Tmp1).addReg(Tmp2);
1492       break;
1493     }
1494     }
1495     return Result;
1496   }
1497
1498   case ISD::XOR: {
1499      switch (N.getValueType()) {
1500     default: assert(0 && "Cannot XOR this type!");
1501     case MVT::i1: { // if a bool, we emit a pseudocode XOR
1502       unsigned pY = SelectExpr(N.getOperand(0));
1503       unsigned pZ = SelectExpr(N.getOperand(1));
1504
1505 /* one possible routine for XOR is:
1506
1507       // Compute px = py ^ pz
1508         // using sum of products: px = (py & !pz) | (pz & !py)
1509         // Uses 5 instructions in 3 cycles.
1510         // cycle 1
1511 (pz)    cmp.eq.unc      px = r0, r0     // px = pz
1512 (py)    cmp.eq.unc      pt = r0, r0     // pt = py
1513         ;;
1514         // cycle 2
1515 (pt)    cmp.ne.and      px = r0, r0     // px = px & !pt (px = pz & !pt)
1516 (pz)    cmp.ne.and      pt = r0, r0     // pt = pt & !pz
1517         ;;
1518         } { .mmi
1519         // cycle 3
1520 (pt)    cmp.eq.or       px = r0, r0     // px = px | pt
1521
1522 *** Another, which we use here, requires one scratch GR. it is:
1523
1524         mov             rt = 0          // initialize rt off critical path
1525         ;;
1526
1527         // cycle 1
1528 (pz)    cmp.eq.unc      px = r0, r0     // px = pz
1529 (pz)    mov             rt = 1          // rt = pz
1530         ;;
1531         // cycle 2
1532 (py)    cmp.ne          px = 1, rt      // if (py) px = !pz
1533
1534 .. these routines kindly provided by Jim Hull
1535 */
1536       unsigned rt = MakeReg(MVT::i64);
1537
1538       // these two temporaries will never actually appear,
1539       // due to the two-address form of some of the instructions below
1540       unsigned bogoPR = MakeReg(MVT::i1);  // becomes Result
1541       unsigned bogoGR = MakeReg(MVT::i64); // becomes rt
1542
1543       BuildMI(BB, IA64::MOV, 1, bogoGR).addReg(IA64::r0);
1544       BuildMI(BB, IA64::PCMPEQUNC, 3, bogoPR)
1545         .addReg(IA64::r0).addReg(IA64::r0).addReg(pZ);
1546       BuildMI(BB, IA64::TPCADDIMM22, 2, rt)
1547         .addReg(bogoGR).addImm(1).addReg(pZ);
1548       BuildMI(BB, IA64::TPCMPIMM8NE, 3, Result)
1549         .addReg(bogoPR).addImm(1).addReg(rt).addReg(pY);
1550       break;
1551     }
1552     // if not a bool, we just XOR away:
1553     case MVT::i8:
1554     case MVT::i16:
1555     case MVT::i32:
1556     case MVT::i64: {
1557       Tmp1 = SelectExpr(N.getOperand(0));
1558       Tmp2 = SelectExpr(N.getOperand(1));
1559       BuildMI(BB, IA64::XOR, 2, Result).addReg(Tmp1).addReg(Tmp2);
1560       break;
1561     }
1562     }
1563     return Result;
1564   }
1565
1566   case ISD::CTPOP: {
1567     Tmp1 = SelectExpr(N.getOperand(0));
1568     BuildMI(BB, IA64::POPCNT, 1, Result).addReg(Tmp1);
1569     return Result;
1570   }
1571
1572   case ISD::SHL: {
1573     Tmp1 = SelectExpr(N.getOperand(0));
1574     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1575       Tmp2 = CN->getValue();
1576       BuildMI(BB, IA64::SHLI, 2, Result).addReg(Tmp1).addImm(Tmp2);
1577     } else {
1578       Tmp2 = SelectExpr(N.getOperand(1));
1579       BuildMI(BB, IA64::SHL, 2, Result).addReg(Tmp1).addReg(Tmp2);
1580     }
1581     return Result;
1582   }
1583
1584   case ISD::SRL: {
1585     Tmp1 = SelectExpr(N.getOperand(0));
1586     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1587       Tmp2 = CN->getValue();
1588       BuildMI(BB, IA64::SHRUI, 2, Result).addReg(Tmp1).addImm(Tmp2);
1589     } else {
1590       Tmp2 = SelectExpr(N.getOperand(1));
1591       BuildMI(BB, IA64::SHRU, 2, Result).addReg(Tmp1).addReg(Tmp2);
1592     }
1593     return Result;
1594   }
1595
1596   case ISD::SRA: {
1597     Tmp1 = SelectExpr(N.getOperand(0));
1598     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1599       Tmp2 = CN->getValue();
1600       BuildMI(BB, IA64::SHRSI, 2, Result).addReg(Tmp1).addImm(Tmp2);
1601     } else {
1602       Tmp2 = SelectExpr(N.getOperand(1));
1603       BuildMI(BB, IA64::SHRS, 2, Result).addReg(Tmp1).addReg(Tmp2);
1604     }
1605     return Result;
1606   }
1607
1608   case ISD::FDIV:
1609   case ISD::SDIV:
1610   case ISD::UDIV:
1611   case ISD::SREM:
1612   case ISD::UREM: {
1613
1614     Tmp1 = SelectExpr(N.getOperand(0));
1615     Tmp2 = SelectExpr(N.getOperand(1));
1616
1617     bool isFP=false;
1618
1619     if(DestType == MVT::f64) // XXX: we're not gonna be fed MVT::f32, are we?
1620       isFP=true;
1621
1622     bool isModulus=false; // is it a division or a modulus?
1623     bool isSigned=false;
1624
1625     switch(N.getOpcode()) {
1626       case ISD::FDIV:
1627       case ISD::SDIV:  isModulus=false; isSigned=true;  break;
1628       case ISD::UDIV:  isModulus=false; isSigned=false; break;
1629       case ISD::FREM:
1630       case ISD::SREM:  isModulus=true;  isSigned=true;  break;
1631       case ISD::UREM:  isModulus=true;  isSigned=false; break;
1632     }
1633
1634     if(!isModulus && !isFP) { // if this is an integer divide,
1635       switch (ponderIntegerDivisionBy(N.getOperand(1), isSigned, Tmp3)) {
1636         case 1: // division by a constant that's a power of 2
1637           Tmp1 = SelectExpr(N.getOperand(0));
1638           if(isSigned) {  // argument could be negative, so emit some code:
1639             unsigned divAmt=Tmp3;
1640             unsigned tempGR1=MakeReg(MVT::i64);
1641             unsigned tempGR2=MakeReg(MVT::i64);
1642             unsigned tempGR3=MakeReg(MVT::i64);
1643             BuildMI(BB, IA64::SHRS, 2, tempGR1)
1644               .addReg(Tmp1).addImm(divAmt-1);
1645             BuildMI(BB, IA64::EXTRU, 3, tempGR2)
1646               .addReg(tempGR1).addImm(64-divAmt).addImm(divAmt);
1647             BuildMI(BB, IA64::ADD, 2, tempGR3)
1648               .addReg(Tmp1).addReg(tempGR2);
1649             BuildMI(BB, IA64::SHRS, 2, Result)
1650               .addReg(tempGR3).addImm(divAmt);
1651           }
1652           else // unsigned div-by-power-of-2 becomes a simple shift right:
1653             BuildMI(BB, IA64::SHRU, 2, Result).addReg(Tmp1).addImm(Tmp3);
1654           return Result; // early exit
1655       }
1656     }
1657
1658     unsigned TmpPR=MakeReg(MVT::i1);  // we need two scratch
1659     unsigned TmpPR2=MakeReg(MVT::i1); // predicate registers,
1660     unsigned TmpF1=MakeReg(MVT::f64); // and one metric truckload of FP regs.
1661     unsigned TmpF2=MakeReg(MVT::f64); // lucky we have IA64?
1662     unsigned TmpF3=MakeReg(MVT::f64); // well, the real FIXME is to have
1663     unsigned TmpF4=MakeReg(MVT::f64); // isTwoAddress forms of these
1664     unsigned TmpF5=MakeReg(MVT::f64); // FP instructions so we can end up with
1665     unsigned TmpF6=MakeReg(MVT::f64); // stuff like setf.sig f10=f10 etc.
1666     unsigned TmpF7=MakeReg(MVT::f64);
1667     unsigned TmpF8=MakeReg(MVT::f64);
1668     unsigned TmpF9=MakeReg(MVT::f64);
1669     unsigned TmpF10=MakeReg(MVT::f64);
1670     unsigned TmpF11=MakeReg(MVT::f64);
1671     unsigned TmpF12=MakeReg(MVT::f64);
1672     unsigned TmpF13=MakeReg(MVT::f64);
1673     unsigned TmpF14=MakeReg(MVT::f64);
1674     unsigned TmpF15=MakeReg(MVT::f64);
1675
1676     // OK, emit some code:
1677
1678     if(!isFP) {
1679       // first, load the inputs into FP regs.
1680       BuildMI(BB, IA64::SETFSIG, 1, TmpF1).addReg(Tmp1);
1681       BuildMI(BB, IA64::SETFSIG, 1, TmpF2).addReg(Tmp2);
1682
1683       // next, convert the inputs to FP
1684       if(isSigned) {
1685         BuildMI(BB, IA64::FCVTXF, 1, TmpF3).addReg(TmpF1);
1686         BuildMI(BB, IA64::FCVTXF, 1, TmpF4).addReg(TmpF2);
1687       } else {
1688         BuildMI(BB, IA64::FCVTXUFS1, 1, TmpF3).addReg(TmpF1);
1689         BuildMI(BB, IA64::FCVTXUFS1, 1, TmpF4).addReg(TmpF2);
1690       }
1691
1692     } else { // this is an FP divide/remainder, so we 'leak' some temp
1693              // regs and assign TmpF3=Tmp1, TmpF4=Tmp2
1694       TmpF3=Tmp1;
1695       TmpF4=Tmp2;
1696     }
1697
1698     // we start by computing an approximate reciprocal (good to 9 bits?)
1699     // note, this instruction writes _both_ TmpF5 (answer) and TmpPR (predicate)
1700     BuildMI(BB, IA64::FRCPAS1, 4)
1701       .addReg(TmpF5, MachineOperand::Def)
1702       .addReg(TmpPR, MachineOperand::Def)
1703       .addReg(TmpF3).addReg(TmpF4);
1704
1705     if(!isModulus) { // if this is a divide, we worry about div-by-zero
1706       unsigned bogusPR=MakeReg(MVT::i1); // won't appear, due to twoAddress
1707                                        // TPCMPNE below
1708       BuildMI(BB, IA64::CMPEQ, 2, bogusPR).addReg(IA64::r0).addReg(IA64::r0);
1709       BuildMI(BB, IA64::TPCMPNE, 3, TmpPR2).addReg(bogusPR)
1710         .addReg(IA64::r0).addReg(IA64::r0).addReg(TmpPR);
1711     }
1712
1713     // now we apply newton's method, thrice! (FIXME: this is ~72 bits of
1714     // precision, don't need this much for f32/i32)
1715     BuildMI(BB, IA64::CFNMAS1, 4, TmpF6)
1716       .addReg(TmpF4).addReg(TmpF5).addReg(IA64::F1).addReg(TmpPR);
1717     BuildMI(BB, IA64::CFMAS1,  4, TmpF7)
1718       .addReg(TmpF3).addReg(TmpF5).addReg(IA64::F0).addReg(TmpPR);
1719     BuildMI(BB, IA64::CFMAS1,  4, TmpF8)
1720       .addReg(TmpF6).addReg(TmpF6).addReg(IA64::F0).addReg(TmpPR);
1721     BuildMI(BB, IA64::CFMAS1,  4, TmpF9)
1722       .addReg(TmpF6).addReg(TmpF7).addReg(TmpF7).addReg(TmpPR);
1723     BuildMI(BB, IA64::CFMAS1,  4,TmpF10)
1724       .addReg(TmpF6).addReg(TmpF5).addReg(TmpF5).addReg(TmpPR);
1725     BuildMI(BB, IA64::CFMAS1,  4,TmpF11)
1726       .addReg(TmpF8).addReg(TmpF9).addReg(TmpF9).addReg(TmpPR);
1727     BuildMI(BB, IA64::CFMAS1,  4,TmpF12)
1728       .addReg(TmpF8).addReg(TmpF10).addReg(TmpF10).addReg(TmpPR);
1729     BuildMI(BB, IA64::CFNMAS1, 4,TmpF13)
1730       .addReg(TmpF4).addReg(TmpF11).addReg(TmpF3).addReg(TmpPR);
1731
1732        // FIXME: this is unfortunate :(
1733        // the story is that the dest reg of the fnma above and the fma below
1734        // (and therefore possibly the src of the fcvt.fx[u] as well) cannot
1735        // be the same register, or this code breaks if the first argument is
1736        // zero. (e.g. without this hack, 0%8 yields -64, not 0.)
1737     BuildMI(BB, IA64::CFMAS1,  4,TmpF14)
1738       .addReg(TmpF13).addReg(TmpF12).addReg(TmpF11).addReg(TmpPR);
1739
1740     if(isModulus) { // XXX: fragile! fixes _only_ mod, *breaks* div! !
1741       BuildMI(BB, IA64::IUSE, 1).addReg(TmpF13); // hack :(
1742     }
1743
1744     if(!isFP) {
1745       // round to an integer
1746       if(isSigned)
1747         BuildMI(BB, IA64::FCVTFXTRUNCS1, 1, TmpF15).addReg(TmpF14);
1748       else
1749         BuildMI(BB, IA64::FCVTFXUTRUNCS1, 1, TmpF15).addReg(TmpF14);
1750     } else {
1751       BuildMI(BB, IA64::FMOV, 1, TmpF15).addReg(TmpF14);
1752      // EXERCISE: can you see why TmpF15=TmpF14 does not work here, and
1753      // we really do need the above FMOV? ;)
1754     }
1755
1756     if(!isModulus) {
1757       if(isFP) { // extra worrying about div-by-zero
1758       unsigned bogoResult=MakeReg(MVT::f64);
1759
1760       // we do a 'conditional fmov' (of the correct result, depending
1761       // on how the frcpa predicate turned out)
1762       BuildMI(BB, IA64::PFMOV, 2, bogoResult)
1763         .addReg(TmpF12).addReg(TmpPR2);
1764       BuildMI(BB, IA64::CFMOV, 2, Result)
1765         .addReg(bogoResult).addReg(TmpF15).addReg(TmpPR);
1766       }
1767       else {
1768         BuildMI(BB, IA64::GETFSIG, 1, Result).addReg(TmpF15);
1769       }
1770     } else { // this is a modulus
1771       if(!isFP) {
1772         // answer = q * (-b) + a
1773         unsigned ModulusResult = MakeReg(MVT::f64);
1774         unsigned TmpF = MakeReg(MVT::f64);
1775         unsigned TmpI = MakeReg(MVT::i64);
1776
1777         BuildMI(BB, IA64::SUB, 2, TmpI).addReg(IA64::r0).addReg(Tmp2);
1778         BuildMI(BB, IA64::SETFSIG, 1, TmpF).addReg(TmpI);
1779         BuildMI(BB, IA64::XMAL, 3, ModulusResult)
1780           .addReg(TmpF15).addReg(TmpF).addReg(TmpF1);
1781         BuildMI(BB, IA64::GETFSIG, 1, Result).addReg(ModulusResult);
1782       } else { // FP modulus! The horror... the horror....
1783         assert(0 && "sorry, no FP modulus just yet!\n!\n");
1784       }
1785     }
1786
1787     return Result;
1788   }
1789
1790   case ISD::SIGN_EXTEND_INREG: {
1791     Tmp1 = SelectExpr(N.getOperand(0));
1792     switch(cast<VTSDNode>(Node->getOperand(1))->getVT()) {
1793     default:
1794       Node->dump();
1795       assert(0 && "don't know how to sign extend this type");
1796       break;
1797     case MVT::i8: Opc = IA64::SXT1; break;
1798     case MVT::i16: Opc = IA64::SXT2; break;
1799     case MVT::i32: Opc = IA64::SXT4; break;
1800     }
1801     BuildMI(BB, Opc, 1, Result).addReg(Tmp1);
1802     return Result;
1803   }
1804
1805   case ISD::SETCC: {
1806     Tmp1 = SelectExpr(N.getOperand(0));
1807     ISD::CondCode CC = cast<CondCodeSDNode>(Node->getOperand(2))->get();
1808     if (MVT::isInteger(N.getOperand(0).getValueType())) {
1809
1810       if(ConstantSDNode *CSDN =
1811            dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1812       // if we are comparing against a constant zero
1813       if(CSDN->getValue()==0)
1814         Tmp2 = IA64::r0; // then we can just compare against r0
1815       else
1816         Tmp2 = SelectExpr(N.getOperand(1));
1817       } else // not comparing against a constant
1818         Tmp2 = SelectExpr(N.getOperand(1));
1819
1820       switch (CC) {
1821       default: assert(0 && "Unknown integer comparison!");
1822       case ISD::SETEQ:
1823         BuildMI(BB, IA64::CMPEQ, 2, Result).addReg(Tmp1).addReg(Tmp2);
1824         break;
1825       case ISD::SETGT:
1826         BuildMI(BB, IA64::CMPGT, 2, Result).addReg(Tmp1).addReg(Tmp2);
1827         break;
1828       case ISD::SETGE:
1829         BuildMI(BB, IA64::CMPGE, 2, Result).addReg(Tmp1).addReg(Tmp2);
1830         break;
1831       case ISD::SETLT:
1832         BuildMI(BB, IA64::CMPLT, 2, Result).addReg(Tmp1).addReg(Tmp2);
1833         break;
1834       case ISD::SETLE:
1835         BuildMI(BB, IA64::CMPLE, 2, Result).addReg(Tmp1).addReg(Tmp2);
1836         break;
1837       case ISD::SETNE:
1838         BuildMI(BB, IA64::CMPNE, 2, Result).addReg(Tmp1).addReg(Tmp2);
1839         break;
1840       case ISD::SETULT:
1841         BuildMI(BB, IA64::CMPLTU, 2, Result).addReg(Tmp1).addReg(Tmp2);
1842         break;
1843       case ISD::SETUGT:
1844         BuildMI(BB, IA64::CMPGTU, 2, Result).addReg(Tmp1).addReg(Tmp2);
1845         break;
1846       case ISD::SETULE:
1847         BuildMI(BB, IA64::CMPLEU, 2, Result).addReg(Tmp1).addReg(Tmp2);
1848         break;
1849       case ISD::SETUGE:
1850         BuildMI(BB, IA64::CMPGEU, 2, Result).addReg(Tmp1).addReg(Tmp2);
1851         break;
1852       }
1853     } else { // if not integer, should be FP.
1854       assert(N.getOperand(0).getValueType() != MVT::f32 &&
1855           "error: SETCC should have had incoming f32 promoted to f64!\n");
1856
1857       if(ConstantFPSDNode *CFPSDN =
1858            dyn_cast<ConstantFPSDNode>(N.getOperand(1))) {
1859
1860         // if we are comparing against a constant +0.0 or +1.0
1861         if(CFPSDN->isExactlyValue(+0.0))
1862           Tmp2 = IA64::F0; // then we can just compare against f0
1863         else if(CFPSDN->isExactlyValue(+1.0))
1864           Tmp2 = IA64::F1; // or f1
1865         else
1866           Tmp2 = SelectExpr(N.getOperand(1));
1867       } else // not comparing against a constant
1868         Tmp2 = SelectExpr(N.getOperand(1));
1869
1870       switch (CC) {
1871       default: assert(0 && "Unknown FP comparison!");
1872       case ISD::SETEQ:
1873         BuildMI(BB, IA64::FCMPEQ, 2, Result).addReg(Tmp1).addReg(Tmp2);
1874         break;
1875       case ISD::SETGT:
1876         BuildMI(BB, IA64::FCMPGT, 2, Result).addReg(Tmp1).addReg(Tmp2);
1877         break;
1878       case ISD::SETGE:
1879         BuildMI(BB, IA64::FCMPGE, 2, Result).addReg(Tmp1).addReg(Tmp2);
1880         break;
1881       case ISD::SETLT:
1882         BuildMI(BB, IA64::FCMPLT, 2, Result).addReg(Tmp1).addReg(Tmp2);
1883         break;
1884       case ISD::SETLE:
1885         BuildMI(BB, IA64::FCMPLE, 2, Result).addReg(Tmp1).addReg(Tmp2);
1886         break;
1887       case ISD::SETNE:
1888         BuildMI(BB, IA64::FCMPNE, 2, Result).addReg(Tmp1).addReg(Tmp2);
1889         break;
1890       case ISD::SETULT:
1891         BuildMI(BB, IA64::FCMPLTU, 2, Result).addReg(Tmp1).addReg(Tmp2);
1892         break;
1893       case ISD::SETUGT:
1894         BuildMI(BB, IA64::FCMPGTU, 2, Result).addReg(Tmp1).addReg(Tmp2);
1895         break;
1896       case ISD::SETULE:
1897         BuildMI(BB, IA64::FCMPLEU, 2, Result).addReg(Tmp1).addReg(Tmp2);
1898         break;
1899       case ISD::SETUGE:
1900         BuildMI(BB, IA64::FCMPGEU, 2, Result).addReg(Tmp1).addReg(Tmp2);
1901         break;
1902       }
1903     }
1904     return Result;
1905   }
1906
1907   case ISD::EXTLOAD:
1908   case ISD::ZEXTLOAD:
1909   case ISD::LOAD: {
1910     // Make sure we generate both values.
1911     if (Result != 1)
1912       ExprMap[N.getValue(1)] = 1;   // Generate the token
1913     else
1914       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
1915
1916     bool isBool=false;
1917
1918     if(opcode == ISD::LOAD) { // this is a LOAD
1919       switch (Node->getValueType(0)) {
1920         default: assert(0 && "Cannot load this type!");
1921         case MVT::i1:  Opc = IA64::LD1; isBool=true; break;
1922               // FIXME: for now, we treat bool loads the same as i8 loads */
1923         case MVT::i8:  Opc = IA64::LD1; break;
1924         case MVT::i16: Opc = IA64::LD2; break;
1925         case MVT::i32: Opc = IA64::LD4; break;
1926         case MVT::i64: Opc = IA64::LD8; break;
1927
1928         case MVT::f32: Opc = IA64::LDF4; break;
1929         case MVT::f64: Opc = IA64::LDF8; break;
1930       }
1931     } else { // this is an EXTLOAD or ZEXTLOAD
1932       MVT::ValueType TypeBeingLoaded =
1933         cast<VTSDNode>(Node->getOperand(3))->getVT();
1934       switch (TypeBeingLoaded) {
1935         default: assert(0 && "Cannot extload/zextload this type!");
1936         // FIXME: bools?
1937         case MVT::i8: Opc = IA64::LD1; break;
1938         case MVT::i16: Opc = IA64::LD2; break;
1939         case MVT::i32: Opc = IA64::LD4; break;
1940         case MVT::f32: Opc = IA64::LDF4; break;
1941       }
1942     }
1943
1944     SDOperand Chain = N.getOperand(0);
1945     SDOperand Address = N.getOperand(1);
1946
1947     if(Address.getOpcode() == ISD::GlobalAddress) {
1948       Select(Chain);
1949       unsigned dummy = MakeReg(MVT::i64);
1950       unsigned dummy2 = MakeReg(MVT::i64);
1951       BuildMI(BB, IA64::ADD, 2, dummy)
1952         .addGlobalAddress(cast<GlobalAddressSDNode>(Address)->getGlobal())
1953         .addReg(IA64::r1);
1954       BuildMI(BB, IA64::LD8, 1, dummy2).addReg(dummy);
1955       if(!isBool)
1956         BuildMI(BB, Opc, 1, Result).addReg(dummy2);
1957       else { // emit a little pseudocode to load a bool (stored in one byte)
1958              // into a predicate register
1959         assert(Opc==IA64::LD1 && "problem loading a bool");
1960         unsigned dummy3 = MakeReg(MVT::i64);
1961         BuildMI(BB, Opc, 1, dummy3).addReg(dummy2);
1962         // we compare to 0. true? 0. false? 1.
1963         BuildMI(BB, IA64::CMPNE, 2, Result).addReg(dummy3).addReg(IA64::r0);
1964       }
1965     } else if(ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(Address)) {
1966       unsigned CPIdx = BB->getParent()->getConstantPool()->
1967                            getConstantPoolIndex(CP->get());
1968       Select(Chain);
1969       IA64Lowering.restoreGP(BB);
1970       unsigned dummy = MakeReg(MVT::i64);
1971       unsigned dummy2 = MakeReg(MVT::i64);
1972       BuildMI(BB, IA64::MOVLIMM64, 1, dummy2).addConstantPoolIndex(CPIdx);
1973       BuildMI(BB, IA64::ADD, 2, dummy).addReg(dummy2).addReg(IA64::r1); //CPI+GP
1974
1975
1976  // OLD     BuildMI(BB, IA64::ADD, 2, dummy).addConstantPoolIndex(CPIdx)
1977  // (FIXME!)      .addReg(IA64::r1); // CPI+GP
1978       if(!isBool)
1979         BuildMI(BB, Opc, 1, Result).addReg(dummy);
1980       else { // emit a little pseudocode to load a bool (stored in one byte)
1981              // into a predicate register
1982         assert(Opc==IA64::LD1 && "problem loading a bool");
1983         unsigned dummy3 = MakeReg(MVT::i64);
1984         BuildMI(BB, Opc, 1, dummy3).addReg(dummy);
1985         // we compare to 0. true? 0. false? 1.
1986         BuildMI(BB, IA64::CMPNE, 2, Result).addReg(dummy3).addReg(IA64::r0);
1987       }
1988     } else if(Address.getOpcode() == ISD::FrameIndex) {
1989       Select(Chain);  // FIXME ? what about bools?
1990       unsigned dummy = MakeReg(MVT::i64);
1991       BuildMI(BB, IA64::MOV, 1, dummy)
1992         .addFrameIndex(cast<FrameIndexSDNode>(Address)->getIndex());
1993       if(!isBool)
1994         BuildMI(BB, Opc, 1, Result).addReg(dummy);
1995       else { // emit a little pseudocode to load a bool (stored in one byte)
1996              // into a predicate register
1997         assert(Opc==IA64::LD1 && "problem loading a bool");
1998         unsigned dummy3 = MakeReg(MVT::i64);
1999         BuildMI(BB, Opc, 1, dummy3).addReg(dummy);
2000         // we compare to 0. true? 0. false? 1.
2001         BuildMI(BB, IA64::CMPNE, 2, Result).addReg(dummy3).addReg(IA64::r0);
2002       }
2003     } else { // none of the above...
2004       Select(Chain);
2005       Tmp2 = SelectExpr(Address);
2006       if(!isBool)
2007         BuildMI(BB, Opc, 1, Result).addReg(Tmp2);
2008       else { // emit a little pseudocode to load a bool (stored in one byte)
2009              // into a predicate register
2010         assert(Opc==IA64::LD1 && "problem loading a bool");
2011         unsigned dummy = MakeReg(MVT::i64);
2012         BuildMI(BB, Opc, 1, dummy).addReg(Tmp2);
2013         // we compare to 0. true? 0. false? 1.
2014         BuildMI(BB, IA64::CMPNE, 2, Result).addReg(dummy).addReg(IA64::r0);
2015       }
2016     }
2017
2018     return Result;
2019   }
2020
2021   case ISD::CopyFromReg: {
2022     if (Result == 1)
2023         Result = ExprMap[N.getValue(0)] =
2024           MakeReg(N.getValue(0).getValueType());
2025
2026       SDOperand Chain   = N.getOperand(0);
2027
2028       Select(Chain);
2029       unsigned r = cast<RegisterSDNode>(Node->getOperand(1))->getReg();
2030
2031       if(N.getValueType() == MVT::i1) // if a bool, we use pseudocode
2032         BuildMI(BB, IA64::PCMPEQUNC, 3, Result)
2033           .addReg(IA64::r0).addReg(IA64::r0).addReg(r);
2034                             // (r) Result =cmp.eq.unc(r0,r0)
2035       else
2036         BuildMI(BB, IA64::MOV, 1, Result).addReg(r); // otherwise MOV
2037       return Result;
2038   }
2039
2040   case ISD::TAILCALL:
2041   case ISD::CALL: {
2042       Select(N.getOperand(0));
2043
2044       // The chain for this call is now lowered.
2045       ExprMap.insert(std::make_pair(N.getValue(Node->getNumValues()-1), 1));
2046
2047       //grab the arguments
2048       std::vector<unsigned> argvregs;
2049
2050       for(int i = 2, e = Node->getNumOperands(); i < e; ++i)
2051         argvregs.push_back(SelectExpr(N.getOperand(i)));
2052
2053       // see section 8.5.8 of "Itanium Software Conventions and
2054       // Runtime Architecture Guide to see some examples of what's going
2055       // on here. (in short: int args get mapped 1:1 'slot-wise' to out0->out7,
2056       // while FP args get mapped to F8->F15 as needed)
2057
2058       unsigned used_FPArgs=0; // how many FP Args have been used so far?
2059
2060       // in reg args
2061       for(int i = 0, e = std::min(8, (int)argvregs.size()); i < e; ++i)
2062       {
2063         unsigned intArgs[] = {IA64::out0, IA64::out1, IA64::out2, IA64::out3,
2064                               IA64::out4, IA64::out5, IA64::out6, IA64::out7 };
2065         unsigned FPArgs[] = {IA64::F8, IA64::F9, IA64::F10, IA64::F11,
2066                              IA64::F12, IA64::F13, IA64::F14, IA64::F15 };
2067
2068         switch(N.getOperand(i+2).getValueType())
2069         {
2070           default:  // XXX do we need to support MVT::i1 here?
2071             Node->dump();
2072             N.getOperand(i).Val->dump();
2073             std::cerr << "Type for " << i << " is: " <<
2074               N.getOperand(i+2).getValueType() << std::endl;
2075             assert(0 && "Unknown value type for call");
2076           case MVT::i64:
2077             BuildMI(BB, IA64::MOV, 1, intArgs[i]).addReg(argvregs[i]);
2078             break;
2079           case MVT::f64:
2080             BuildMI(BB, IA64::FMOV, 1, FPArgs[used_FPArgs++])
2081               .addReg(argvregs[i]);
2082             // FIXME: we don't need to do this _all_ the time:
2083             BuildMI(BB, IA64::GETFD, 1, intArgs[i]).addReg(argvregs[i]);
2084             break;
2085           }
2086       }
2087
2088       //in mem args
2089       for (int i = 8, e = argvregs.size(); i < e; ++i)
2090       {
2091         unsigned tempAddr = MakeReg(MVT::i64);
2092
2093         switch(N.getOperand(i+2).getValueType()) {
2094         default:
2095           Node->dump();
2096           N.getOperand(i).Val->dump();
2097           std::cerr << "Type for " << i << " is: " <<
2098             N.getOperand(i+2).getValueType() << "\n";
2099           assert(0 && "Unknown value type for call");
2100         case MVT::i1: // FIXME?
2101         case MVT::i8:
2102         case MVT::i16:
2103         case MVT::i32:
2104         case MVT::i64:
2105           BuildMI(BB, IA64::ADDIMM22, 2, tempAddr)
2106             .addReg(IA64::r12).addImm(16 + (i - 8) * 8); // r12 is SP
2107           BuildMI(BB, IA64::ST8, 2).addReg(tempAddr).addReg(argvregs[i]);
2108           break;
2109         case MVT::f32:
2110         case MVT::f64:
2111           BuildMI(BB, IA64::ADDIMM22, 2, tempAddr)
2112             .addReg(IA64::r12).addImm(16 + (i - 8) * 8); // r12 is SP
2113           BuildMI(BB, IA64::STF8, 2).addReg(tempAddr).addReg(argvregs[i]);
2114           break;
2115         }
2116       }
2117
2118     // build the right kind of call. if we can branch directly, do so:
2119     if (GlobalAddressSDNode *GASD =
2120                dyn_cast<GlobalAddressSDNode>(N.getOperand(1)))
2121       {
2122         BuildMI(BB, IA64::BRCALL, 1).addGlobalAddress(GASD->getGlobal(),true);
2123         IA64Lowering.restoreGP_SP_RP(BB);
2124       } else
2125     if (ExternalSymbolSDNode *ESSDN =
2126              dyn_cast<ExternalSymbolSDNode>(N.getOperand(1)))
2127       { // FIXME : currently need this case for correctness, to avoid
2128         // "non-pic code with imm relocation against dynamic symbol" errors
2129         BuildMI(BB, IA64::BRCALL, 1)
2130           .addExternalSymbol(ESSDN->getSymbol(), true);
2131         IA64Lowering.restoreGP_SP_RP(BB);
2132       }
2133     else { // otherwise we need to get the function descriptor
2134            // load the branch target (function)'s entry point and
2135            // GP, then branch
2136       Tmp1 = SelectExpr(N.getOperand(1));
2137
2138       unsigned targetEntryPoint=MakeReg(MVT::i64);
2139       unsigned targetGPAddr=MakeReg(MVT::i64);
2140       unsigned currentGP=MakeReg(MVT::i64);
2141
2142       // b6 is a scratch branch register, we load the target entry point
2143       // from the base of the function descriptor
2144       BuildMI(BB, IA64::LD8, 1, targetEntryPoint).addReg(Tmp1);
2145       BuildMI(BB, IA64::MOV, 1, IA64::B6).addReg(targetEntryPoint);
2146
2147       // save the current GP:
2148       BuildMI(BB, IA64::MOV, 1, currentGP).addReg(IA64::r1);
2149
2150       /* TODO: we need to make sure doing this never, ever loads a
2151        * bogus value into r1 (GP). */
2152       // load the target GP (which is at mem[functiondescriptor+8])
2153       BuildMI(BB, IA64::ADDIMM22, 2, targetGPAddr)
2154         .addReg(Tmp1).addImm(8); // FIXME: addimm22? why not postincrement ld
2155       BuildMI(BB, IA64::LD8, 1, IA64::r1).addReg(targetGPAddr);
2156
2157       // and then jump: (well, call)
2158       BuildMI(BB, IA64::BRCALL, 1).addReg(IA64::B6);
2159       // and finally restore the old GP
2160       BuildMI(BB, IA64::MOV, 1, IA64::r1).addReg(currentGP);
2161       IA64Lowering.restoreSP_RP(BB);
2162     }
2163
2164     switch (Node->getValueType(0)) {
2165     default: assert(0 && "Unknown value type for call result!");
2166     case MVT::Other: return 1;
2167     case MVT::i1:
2168       BuildMI(BB, IA64::CMPNE, 2, Result)
2169         .addReg(IA64::r8).addReg(IA64::r0);
2170       break;
2171     case MVT::i8:
2172     case MVT::i16:
2173     case MVT::i32:
2174     case MVT::i64:
2175       BuildMI(BB, IA64::MOV, 1, Result).addReg(IA64::r8);
2176       break;
2177     case MVT::f64:
2178       BuildMI(BB, IA64::FMOV, 1, Result).addReg(IA64::F8);
2179       break;
2180     }
2181     return Result+N.ResNo;
2182   }
2183
2184   } // <- uhhh XXX
2185   return 0;
2186 }
2187
2188 void ISel::Select(SDOperand N) {
2189   unsigned Tmp1, Tmp2, Opc;
2190   unsigned opcode = N.getOpcode();
2191
2192   if (!LoweredTokens.insert(N).second)
2193     return;  // Already selected.
2194
2195   SDNode *Node = N.Val;
2196
2197   switch (Node->getOpcode()) {
2198   default:
2199     Node->dump(); std::cerr << "\n";
2200     assert(0 && "Node not handled yet!");
2201
2202   case ISD::EntryToken: return;  // Noop
2203
2204   case ISD::TokenFactor: {
2205     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
2206       Select(Node->getOperand(i));
2207     return;
2208   }
2209
2210   case ISD::CopyToReg: {
2211     Select(N.getOperand(0));
2212     Tmp1 = SelectExpr(N.getOperand(2));
2213     Tmp2 = cast<RegisterSDNode>(N.getOperand(1))->getReg();
2214
2215     if (Tmp1 != Tmp2) {
2216       // if a bool, we use pseudocode
2217       if (N.getOperand(2).getValueType() == MVT::i1)
2218         BuildMI(BB, IA64::PCMPEQUNC, 3, Tmp2)
2219           .addReg(IA64::r0).addReg(IA64::r0).addReg(Tmp1);
2220                                    // (Tmp1) Tmp2 = cmp.eq.unc(r0,r0)
2221       else
2222         BuildMI(BB, IA64::MOV, 1, Tmp2).addReg(Tmp1);
2223                       // XXX is this the right way 'round? ;)
2224       // FIXME: WHAT ABOUT FLOATING POINT?
2225     }
2226     return;
2227   }
2228
2229   case ISD::RET: {
2230
2231   /* what the heck is going on here:
2232
2233 <_sabre_> ret with two operands is obvious: chain and value
2234 <camel_> yep
2235 <_sabre_> ret with 3 values happens when 'expansion' occurs
2236 <_sabre_> e.g. i64 gets split into 2x i32
2237 <camel_> oh right
2238 <_sabre_> you don't have this case on ia64
2239 <camel_> yep
2240 <_sabre_> so the two returned values go into EAX/EDX on ia32
2241 <camel_> ahhh *memories*
2242 <_sabre_> :)
2243 <camel_> ok, thanks :)
2244 <_sabre_> so yeah, everything that has a side effect takes a 'token chain'
2245 <_sabre_> this is the first operand always
2246 <_sabre_> these operand often define chains, they are the last operand
2247 <_sabre_> they are printed as 'ch' if you do DAG.dump()
2248   */
2249
2250     switch (N.getNumOperands()) {
2251     default:
2252       assert(0 && "Unknown return instruction!");
2253     case 2:
2254         Select(N.getOperand(0));
2255         Tmp1 = SelectExpr(N.getOperand(1));
2256       switch (N.getOperand(1).getValueType()) {
2257       default: assert(0 && "All other types should have been promoted!!");
2258                // FIXME: do I need to add support for bools here?
2259                // (return '0' or '1' r8, basically...)
2260                //
2261                // FIXME: need to round floats - 80 bits is bad, the tester
2262                // told me so
2263       case MVT::i64:
2264         // we mark r8 as live on exit up above in LowerArguments()
2265         BuildMI(BB, IA64::MOV, 1, IA64::r8).addReg(Tmp1);
2266         break;
2267       case MVT::f64:
2268         // we mark F8 as live on exit up above in LowerArguments()
2269         BuildMI(BB, IA64::FMOV, 1, IA64::F8).addReg(Tmp1);
2270       }
2271       break;
2272     case 1:
2273       Select(N.getOperand(0));
2274       break;
2275     }
2276     // before returning, restore the ar.pfs register (set by the 'alloc' up top)
2277     BuildMI(BB, IA64::MOV, 1).addReg(IA64::AR_PFS).addReg(IA64Lowering.VirtGPR);
2278     BuildMI(BB, IA64::RET, 0); // and then just emit a 'ret' instruction
2279     return;
2280   }
2281
2282   case ISD::BR: {
2283     Select(N.getOperand(0));
2284     MachineBasicBlock *Dest =
2285       cast<BasicBlockSDNode>(N.getOperand(1))->getBasicBlock();
2286     BuildMI(BB, IA64::BRLCOND_NOTCALL, 1).addReg(IA64::p0).addMBB(Dest);
2287     // XXX HACK! we do _not_ need long branches all the time
2288     return;
2289   }
2290
2291   case ISD::BRCOND: {
2292     MachineBasicBlock *Dest =
2293       cast<BasicBlockSDNode>(N.getOperand(2))->getBasicBlock();
2294
2295     Select(N.getOperand(0));
2296     Tmp1 = SelectExpr(N.getOperand(1));
2297     BuildMI(BB, IA64::BRLCOND_NOTCALL, 1).addReg(Tmp1).addMBB(Dest);
2298     // XXX HACK! we do _not_ need long branches all the time
2299     return;
2300   }
2301
2302   case ISD::EXTLOAD:
2303   case ISD::ZEXTLOAD:
2304   case ISD::SEXTLOAD:
2305   case ISD::LOAD:
2306   case ISD::TAILCALL:
2307   case ISD::CALL:
2308   case ISD::CopyFromReg:
2309   case ISD::DYNAMIC_STACKALLOC:
2310     SelectExpr(N);
2311     return;
2312
2313   case ISD::TRUNCSTORE:
2314   case ISD::STORE: {
2315       Select(N.getOperand(0));
2316       Tmp1 = SelectExpr(N.getOperand(1)); // value
2317
2318       bool isBool=false;
2319
2320       if(opcode == ISD::STORE) {
2321         switch (N.getOperand(1).getValueType()) {
2322           default: assert(0 && "Cannot store this type!");
2323           case MVT::i1:  Opc = IA64::ST1; isBool=true; break;
2324               // FIXME?: for now, we treat bool loads the same as i8 stores */
2325           case MVT::i8:  Opc = IA64::ST1; break;
2326           case MVT::i16: Opc = IA64::ST2; break;
2327           case MVT::i32: Opc = IA64::ST4; break;
2328           case MVT::i64: Opc = IA64::ST8; break;
2329
2330           case MVT::f32: Opc = IA64::STF4; break;
2331           case MVT::f64: Opc = IA64::STF8; break;
2332         }
2333       } else { // truncstore
2334         switch(cast<VTSDNode>(Node->getOperand(4))->getVT()) {
2335           default: assert(0 && "unknown type in truncstore");
2336           case MVT::i1: Opc = IA64::ST1; isBool=true; break;
2337                         //FIXME: DAG does not promote this load?
2338           case MVT::i8: Opc = IA64::ST1; break;
2339           case MVT::i16: Opc = IA64::ST2; break;
2340           case MVT::i32: Opc = IA64::ST4; break;
2341           case MVT::f32: Opc = IA64::STF4; break;
2342         }
2343       }
2344
2345       if(N.getOperand(2).getOpcode() == ISD::GlobalAddress) {
2346         unsigned dummy = MakeReg(MVT::i64);
2347         unsigned dummy2 = MakeReg(MVT::i64);
2348         BuildMI(BB, IA64::ADD, 2, dummy)
2349           .addGlobalAddress(cast<GlobalAddressSDNode>
2350               (N.getOperand(2))->getGlobal()).addReg(IA64::r1);
2351         BuildMI(BB, IA64::LD8, 1, dummy2).addReg(dummy);
2352
2353         if(!isBool)
2354           BuildMI(BB, Opc, 2).addReg(dummy2).addReg(Tmp1);
2355         else { // we are storing a bool, so emit a little pseudocode
2356                // to store a predicate register as one byte
2357           assert(Opc==IA64::ST1);
2358           unsigned dummy3 = MakeReg(MVT::i64);
2359           unsigned dummy4 = MakeReg(MVT::i64);
2360           BuildMI(BB, IA64::MOV, 1, dummy3).addReg(IA64::r0);
2361           BuildMI(BB, IA64::TPCADDIMM22, 2, dummy4)
2362             .addReg(dummy3).addImm(1).addReg(Tmp1); // if(Tmp1) dummy=0+1;
2363           BuildMI(BB, Opc, 2).addReg(dummy2).addReg(dummy4);
2364         }
2365       } else if(N.getOperand(2).getOpcode() == ISD::FrameIndex) {
2366
2367         // FIXME? (what about bools?)
2368
2369         unsigned dummy = MakeReg(MVT::i64);
2370         BuildMI(BB, IA64::MOV, 1, dummy)
2371           .addFrameIndex(cast<FrameIndexSDNode>(N.getOperand(2))->getIndex());
2372         BuildMI(BB, Opc, 2).addReg(dummy).addReg(Tmp1);
2373       } else { // otherwise
2374         Tmp2 = SelectExpr(N.getOperand(2)); //address
2375         if(!isBool)
2376           BuildMI(BB, Opc, 2).addReg(Tmp2).addReg(Tmp1);
2377         else { // we are storing a bool, so emit a little pseudocode
2378                // to store a predicate register as one byte
2379           assert(Opc==IA64::ST1);
2380           unsigned dummy3 = MakeReg(MVT::i64);
2381           unsigned dummy4 = MakeReg(MVT::i64);
2382           BuildMI(BB, IA64::MOV, 1, dummy3).addReg(IA64::r0);
2383           BuildMI(BB, IA64::TPCADDIMM22, 2, dummy4)
2384             .addReg(dummy3).addImm(1).addReg(Tmp1); // if(Tmp1) dummy=0+1;
2385           BuildMI(BB, Opc, 2).addReg(Tmp2).addReg(dummy4);
2386         }
2387       }
2388     return;
2389   }
2390
2391   case ISD::CALLSEQ_START:
2392   case ISD::CALLSEQ_END: {
2393     Select(N.getOperand(0));
2394     Tmp1 = cast<ConstantSDNode>(N.getOperand(1))->getValue();
2395
2396     Opc = N.getOpcode() == ISD::CALLSEQ_START ? IA64::ADJUSTCALLSTACKDOWN :
2397                                                 IA64::ADJUSTCALLSTACKUP;
2398     BuildMI(BB, Opc, 1).addImm(Tmp1);
2399     return;
2400   }
2401
2402     return;
2403   }
2404   assert(0 && "GAME OVER. INSERT COIN?");
2405 }
2406
2407
2408 /// createIA64PatternInstructionSelector - This pass converts an LLVM function
2409 /// into a machine code representation using pattern matching and a machine
2410 /// description file.
2411 ///
2412 FunctionPass *llvm::createIA64PatternInstructionSelector(TargetMachine &TM) {
2413   return new ISel(TM);
2414 }
2415
2416