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