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