lib/Target/IA64/IA64ISelPattern.cpp

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