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