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