lib/Target/SystemZ/SystemZISelDAGToDAG.cpp

   1 //==-- SystemZISelDAGToDAG.cpp - A dag to dag inst selector for SystemZ ---===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines an instruction selector for the SystemZ target.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "SystemZ.h"
  15 #include "SystemZISelLowering.h"
  16 #include "SystemZTargetMachine.h"
  17 #include "llvm/DerivedTypes.h"
  18 #include "llvm/Function.h"
  19 #include "llvm/Intrinsics.h"
  20 #include "llvm/CallingConv.h"
  21 #include "llvm/Constants.h"
  22 #include "llvm/CodeGen/MachineFrameInfo.h"
  23 #include "llvm/CodeGen/MachineFunction.h"
  24 #include "llvm/CodeGen/MachineInstrBuilder.h"
  25 #include "llvm/CodeGen/MachineRegisterInfo.h"
  26 #include "llvm/CodeGen/SelectionDAG.h"
  27 #include "llvm/CodeGen/SelectionDAGISel.h"
  28 #include "llvm/Target/TargetLowering.h"
  29 #include "llvm/Support/Compiler.h"
  30 #include "llvm/Support/Debug.h"
  31 using namespace llvm;
  32
  33 static const unsigned subreg_even32 = 1;
  34 static const unsigned subreg_odd32  = 2;
  35 static const unsigned subreg_even   = 3;
  36 static const unsigned subreg_odd    = 4;
  37
  38 namespace {
  39   /// SystemZRRIAddressMode - This corresponds to rriaddr, but uses SDValue's
  40   /// instead of register numbers for the leaves of the matched tree.
  41   struct SystemZRRIAddressMode {
  42     enum {
  43       RegBase,
  44       FrameIndexBase
  45     } BaseType;
  46
  47     struct {            // This is really a union, discriminated by BaseType!
  48       SDValue Reg;
  49       int FrameIndex;
  50     } Base;
  51
  52     SDValue IndexReg;
  53     int64_t Disp;
  54     bool isRI;
  55
  56     SystemZRRIAddressMode(bool RI = false)
  57       : BaseType(RegBase), IndexReg(), Disp(0), isRI(RI) {
  58     }
  59
  60     void dump() {
  61       cerr << "SystemZRRIAddressMode " << this << '\n';
  62       if (BaseType == RegBase) {
  63         cerr << "Base.Reg ";
  64         if (Base.Reg.getNode() != 0) Base.Reg.getNode()->dump();
  65         else cerr << "nul";
  66         cerr << '\n';
  67       } else {
  68         cerr << " Base.FrameIndex " << Base.FrameIndex << '\n';
  69       }
  70       if (!isRI) {
  71         cerr << "IndexReg ";
  72         if (IndexReg.getNode() != 0) IndexReg.getNode()->dump();
  73         else cerr << "nul";
  74       }
  75       cerr << " Disp " << Disp << '\n';
  76     }
  77   };
  78 }
  79
  80 /// SystemZDAGToDAGISel - SystemZ specific code to select SystemZ machine
  81 /// instructions for SelectionDAG operations.
  82 ///
  83 namespace {
  84   class SystemZDAGToDAGISel : public SelectionDAGISel {
  85     SystemZTargetLowering &Lowering;
  86     const SystemZSubtarget &Subtarget;
  87
  88     void getAddressOperandsRI(const SystemZRRIAddressMode &AM,
  89                             SDValue &Base, SDValue &Disp);
  90     void getAddressOperands(const SystemZRRIAddressMode &AM,
  91                             SDValue &Base, SDValue &Disp,
  92                             SDValue &Index);
  93
  94   public:
  95     SystemZDAGToDAGISel(SystemZTargetMachine &TM, CodeGenOpt::Level OptLevel)
  96       : SelectionDAGISel(TM, OptLevel),
  97         Lowering(*TM.getTargetLowering()),
  98         Subtarget(*TM.getSubtargetImpl()) { }
  99
 100     virtual void InstructionSelect();
 101
 102     virtual const char *getPassName() const {
 103       return "SystemZ DAG->DAG Pattern Instruction Selection";
 104     }
 105
 106     /// getI16Imm - Return a target constant with the specified value, of type
 107     /// i16.
 108     inline SDValue getI16Imm(uint64_t Imm) {
 109       return CurDAG->getTargetConstant(Imm, MVT::i16);
 110     }
 111
 112     /// getI32Imm - Return a target constant with the specified value, of type
 113     /// i32.
 114     inline SDValue getI32Imm(uint64_t Imm) {
 115       return CurDAG->getTargetConstant(Imm, MVT::i32);
 116     }
 117
 118     // Include the pieces autogenerated from the target description.
 119     #include "SystemZGenDAGISel.inc"
 120
 121   private:
 122     bool SelectAddrRI12Only(SDValue Op, SDValue& Addr,
 123                             SDValue &Base, SDValue &Disp);
 124     bool SelectAddrRI12(SDValue Op, SDValue& Addr,
 125                         SDValue &Base, SDValue &Disp,
 126                         bool is12BitOnly = false);
 127     bool SelectAddrRI(SDValue Op, SDValue& Addr,
 128                       SDValue &Base, SDValue &Disp);
 129     bool SelectAddrRRI12(SDValue Op, SDValue Addr,
 130                          SDValue &Base, SDValue &Disp, SDValue &Index);
 131     bool SelectAddrRRI20(SDValue Op, SDValue Addr,
 132                          SDValue &Base, SDValue &Disp, SDValue &Index);
 133     bool SelectLAAddr(SDValue Op, SDValue Addr,
 134                       SDValue &Base, SDValue &Disp, SDValue &Index);
 135
 136     SDNode *Select(SDValue Op);
 137
 138     bool TryFoldLoad(SDValue P, SDValue N,
 139                      SDValue &Base, SDValue &Disp, SDValue &Index);
 140
 141     bool MatchAddress(SDValue N, SystemZRRIAddressMode &AM,
 142                       bool is12Bit, unsigned Depth = 0);
 143     bool MatchAddressBase(SDValue N, SystemZRRIAddressMode &AM);
 144     bool MatchAddressRI(SDValue N, SystemZRRIAddressMode &AM,
 145                         bool is12Bit);
 146
 147   #ifndef NDEBUG
 148     unsigned Indent;
 149   #endif
 150   };
 151 }  // end anonymous namespace
 152
 153 /// createSystemZISelDag - This pass converts a legalized DAG into a
 154 /// SystemZ-specific DAG, ready for instruction scheduling.
 155 ///
 156 FunctionPass *llvm::createSystemZISelDag(SystemZTargetMachine &TM,
 157                                         CodeGenOpt::Level OptLevel) {
 158   return new SystemZDAGToDAGISel(TM, OptLevel);
 159 }
 160
 161 /// isImmSExt20 - This method tests to see if the node is either a 32-bit
 162 /// or 64-bit immediate, and if the value can be accurately represented as a
 163 /// sign extension from a 20-bit value. If so, this returns true and the
 164 /// immediate.
 165 static bool isImmSExt20(int64_t Val, int64_t &Imm) {
 166   if (Val >= -524288 && Val <= 524287) {
 167     Imm = Val;
 168     return true;
 169   }
 170   return false;
 171 }
 172
 173 /// isImmZExt12 - This method tests to see if the node is either a 32-bit
 174 /// or 64-bit immediate, and if the value can be accurately represented as a
 175 /// zero extension from a 12-bit value. If so, this returns true and the
 176 /// immediate.
 177 static bool isImmZExt12(int64_t Val, int64_t &Imm) {
 178   if (Val >= 0 && Val <= 0xFFF) {
 179     Imm = Val;
 180     return true;
 181   }
 182   return false;
 183 }
 184
 185 /// MatchAddress - Add the specified node to the specified addressing mode,
 186 /// returning true if it cannot be done.  This just pattern matches for the
 187 /// addressing mode.
 188 bool SystemZDAGToDAGISel::MatchAddress(SDValue N, SystemZRRIAddressMode &AM,
 189                                        bool is12Bit, unsigned Depth) {
 190   DebugLoc dl = N.getDebugLoc();
 191   DOUT << "MatchAddress: "; DEBUG(AM.dump());
 192   // Limit recursion.
 193   if (Depth > 5)
 194     return MatchAddressBase(N, AM);
 195
 196   // FIXME: We can perform better here. If we have something like
 197   // (shift (add A, imm), N), we can try to reassociate stuff and fold shift of
 198   // imm into addressing mode.
 199   switch (N.getOpcode()) {
 200   default: break;
 201   case ISD::Constant: {
 202     int64_t Val = cast<ConstantSDNode>(N)->getSExtValue();
 203     int64_t Imm;
 204     bool Match = (is12Bit ?
 205                   isImmZExt12(AM.Disp + Val, Imm) :
 206                   isImmSExt20(AM.Disp + Val, Imm));
 207     if (Match) {
 208       AM.Disp = Imm;
 209       return false;
 210     }
 211     break;
 212   }
 213
 214   case ISD::FrameIndex:
 215     if (AM.BaseType == SystemZRRIAddressMode::RegBase &&
 216         AM.Base.Reg.getNode() == 0) {
 217       AM.BaseType = SystemZRRIAddressMode::FrameIndexBase;
 218       AM.Base.FrameIndex = cast<FrameIndexSDNode>(N)->getIndex();
 219       return false;
 220     }
 221     break;
 222
 223   case ISD::SUB: {
 224     // Given A-B, if A can be completely folded into the address and
 225     // the index field with the index field unused, use -B as the index.
 226     // This is a win if a has multiple parts that can be folded into
 227     // the address. Also, this saves a mov if the base register has
 228     // other uses, since it avoids a two-address sub instruction, however
 229     // it costs an additional mov if the index register has other uses.
 230
 231     // Test if the LHS of the sub can be folded.
 232     SystemZRRIAddressMode Backup = AM;
 233     if (MatchAddress(N.getNode()->getOperand(0), AM, is12Bit, Depth+1)) {
 234       AM = Backup;
 235       break;
 236     }
 237     // Test if the index field is free for use.
 238     if (AM.IndexReg.getNode() && !AM.isRI) {
 239       AM = Backup;
 240       break;
 241     }
 242
 243     // If the base is a register with multiple uses, this transformation may
 244     // save a mov. Otherwise it's probably better not to do it.
 245     if (AM.BaseType == SystemZRRIAddressMode::RegBase &&
 246         (!AM.Base.Reg.getNode() || AM.Base.Reg.getNode()->hasOneUse())) {
 247       AM = Backup;
 248       break;
 249     }
 250
 251     // Ok, the transformation is legal and appears profitable. Go for it.
 252     SDValue RHS = N.getNode()->getOperand(1);
 253     SDValue Zero = CurDAG->getConstant(0, N.getValueType());
 254     SDValue Neg = CurDAG->getNode(ISD::SUB, dl, N.getValueType(), Zero, RHS);
 255     AM.IndexReg = Neg;
 256
 257     // Insert the new nodes into the topological ordering.
 258     if (Zero.getNode()->getNodeId() == -1 ||
 259         Zero.getNode()->getNodeId() > N.getNode()->getNodeId()) {
 260       CurDAG->RepositionNode(N.getNode(), Zero.getNode());
 261       Zero.getNode()->setNodeId(N.getNode()->getNodeId());
 262     }
 263     if (Neg.getNode()->getNodeId() == -1 ||
 264         Neg.getNode()->getNodeId() > N.getNode()->getNodeId()) {
 265       CurDAG->RepositionNode(N.getNode(), Neg.getNode());
 266       Neg.getNode()->setNodeId(N.getNode()->getNodeId());
 267     }
 268     return false;
 269   }
 270
 271   case ISD::ADD: {
 272     SystemZRRIAddressMode Backup = AM;
 273     if (!MatchAddress(N.getNode()->getOperand(0), AM, is12Bit, Depth+1) &&
 274         !MatchAddress(N.getNode()->getOperand(1), AM, is12Bit, Depth+1))
 275       return false;
 276     AM = Backup;
 277     if (!MatchAddress(N.getNode()->getOperand(1), AM, is12Bit, Depth+1) &&
 278         !MatchAddress(N.getNode()->getOperand(0), AM, is12Bit, Depth+1))
 279       return false;
 280     AM = Backup;
 281
 282     // If we couldn't fold both operands into the address at the same time,
 283     // see if we can just put each operand into a register and fold at least
 284     // the add.
 285     if (!AM.isRI &&
 286         AM.BaseType == SystemZRRIAddressMode::RegBase &&
 287         !AM.Base.Reg.getNode() && !AM.IndexReg.getNode()) {
 288       AM.Base.Reg = N.getNode()->getOperand(0);
 289       AM.IndexReg = N.getNode()->getOperand(1);
 290       return false;
 291     }
 292     break;
 293   }
 294
 295   case ISD::OR:
 296     // Handle "X | C" as "X + C" iff X is known to have C bits clear.
 297     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
 298       SystemZRRIAddressMode Backup = AM;
 299       int64_t Offset = CN->getSExtValue();
 300       int64_t Imm;
 301       bool MatchOffset = (is12Bit ?
 302                           isImmZExt12(AM.Disp + Offset, Imm) :
 303                           isImmSExt20(AM.Disp + Offset, Imm));
 304       // The resultant disp must fit in 12 or 20-bits.
 305       if (MatchOffset &&
 306           // LHS should be an addr mode.
 307           !MatchAddress(N.getOperand(0), AM, is12Bit, Depth+1) &&
 308           // Check to see if the LHS & C is zero.
 309           CurDAG->MaskedValueIsZero(N.getOperand(0), CN->getAPIntValue())) {
 310         AM.Disp = Imm;
 311         return false;
 312       }
 313       AM = Backup;
 314     }
 315     break;
 316   }
 317
 318   return MatchAddressBase(N, AM);
 319 }
 320
 321 /// MatchAddressBase - Helper for MatchAddress. Add the specified node to the
 322 /// specified addressing mode without any further recursion.
 323 bool SystemZDAGToDAGISel::MatchAddressBase(SDValue N,
 324                                            SystemZRRIAddressMode &AM) {
 325   // Is the base register already occupied?
 326   if (AM.BaseType != SystemZRRIAddressMode::RegBase || AM.Base.Reg.getNode()) {
 327     // If so, check to see if the index register is set.
 328     if (AM.IndexReg.getNode() == 0 && !AM.isRI) {
 329       AM.IndexReg = N;
 330       return false;
 331     }
 332
 333     // Otherwise, we cannot select it.
 334     return true;
 335   }
 336
 337   // Default, generate it as a register.
 338   AM.BaseType = SystemZRRIAddressMode::RegBase;
 339   AM.Base.Reg = N;
 340   return false;
 341 }
 342
 343 void SystemZDAGToDAGISel::getAddressOperandsRI(const SystemZRRIAddressMode &AM,
 344                                                SDValue &Base, SDValue &Disp) {
 345   if (AM.BaseType == SystemZRRIAddressMode::RegBase)
 346     Base = AM.Base.Reg;
 347   else
 348     Base = CurDAG->getTargetFrameIndex(AM.Base.FrameIndex, TLI.getPointerTy());
 349   Disp = CurDAG->getTargetConstant(AM.Disp, MVT::i64);
 350 }
 351
 352 void SystemZDAGToDAGISel::getAddressOperands(const SystemZRRIAddressMode &AM,
 353                                              SDValue &Base, SDValue &Disp,
 354                                              SDValue &Index) {
 355   getAddressOperandsRI(AM, Base, Disp);
 356   Index = AM.IndexReg;
 357 }
 358
 359 /// Returns true if the address can be represented by a base register plus
 360 /// an unsigned 12-bit displacement [r+imm].
 361 bool SystemZDAGToDAGISel::SelectAddrRI12Only(SDValue Op, SDValue& Addr,
 362                                              SDValue &Base, SDValue &Disp) {
 363   return SelectAddrRI12(Op, Addr, Base, Disp, /*is12BitOnly*/true);
 364 }
 365
 366 bool SystemZDAGToDAGISel::SelectAddrRI12(SDValue Op, SDValue& Addr,
 367                                          SDValue &Base, SDValue &Disp,
 368                                          bool is12BitOnly) {
 369   SystemZRRIAddressMode AM20(/*isRI*/true), AM12(/*isRI*/true);
 370   bool Done = false;
 371
 372   if (!Addr.hasOneUse()) {
 373     unsigned Opcode = Addr.getOpcode();
 374     if (Opcode != ISD::Constant && Opcode != ISD::FrameIndex) {
 375       // If we are able to fold N into addressing mode, then we'll allow it even
 376       // if N has multiple uses. In general, addressing computation is used as
 377       // addresses by all of its uses. But watch out for CopyToReg uses, that
 378       // means the address computation is liveout. It will be computed by a LA
 379       // so we want to avoid computing the address twice.
 380       for (SDNode::use_iterator UI = Addr.getNode()->use_begin(),
 381              UE = Addr.getNode()->use_end(); UI != UE; ++UI) {
 382         if (UI->getOpcode() == ISD::CopyToReg) {
 383           MatchAddressBase(Addr, AM12);
 384           Done = true;
 385           break;
 386         }
 387       }
 388     }
 389   }
 390   if (!Done && MatchAddress(Addr, AM12, /* is12Bit */ true))
 391     return false;
 392
 393   // Check, whether we can match stuff using 20-bit displacements
 394   if (!Done && !is12BitOnly &&
 395       !MatchAddress(Addr, AM20, /* is12Bit */ false))
 396     if (AM12.Disp == 0 && AM20.Disp != 0)
 397       return false;
 398
 399   DOUT << "MatchAddress (final): "; DEBUG(AM12.dump());
 400
 401   MVT VT = Addr.getValueType();
 402   if (AM12.BaseType == SystemZRRIAddressMode::RegBase) {
 403     if (!AM12.Base.Reg.getNode())
 404       AM12.Base.Reg = CurDAG->getRegister(0, VT);
 405   }
 406
 407   assert(AM12.IndexReg.getNode() == 0 && "Invalid reg-imm address mode!");
 408
 409   getAddressOperandsRI(AM12, Base, Disp);
 410
 411   return true;
 412 }
 413
 414 /// Returns true if the address can be represented by a base register plus
 415 /// a signed 20-bit displacement [r+imm].
 416 bool SystemZDAGToDAGISel::SelectAddrRI(SDValue Op, SDValue& Addr,
 417                                        SDValue &Base, SDValue &Disp) {
 418   SystemZRRIAddressMode AM(/*isRI*/true);
 419   bool Done = false;
 420
 421   if (!Addr.hasOneUse()) {
 422     unsigned Opcode = Addr.getOpcode();
 423     if (Opcode != ISD::Constant && Opcode != ISD::FrameIndex) {
 424       // If we are able to fold N into addressing mode, then we'll allow it even
 425       // if N has multiple uses. In general, addressing computation is used as
 426       // addresses by all of its uses. But watch out for CopyToReg uses, that
 427       // means the address computation is liveout. It will be computed by a LA
 428       // so we want to avoid computing the address twice.
 429       for (SDNode::use_iterator UI = Addr.getNode()->use_begin(),
 430              UE = Addr.getNode()->use_end(); UI != UE; ++UI) {
 431         if (UI->getOpcode() == ISD::CopyToReg) {
 432           MatchAddressBase(Addr, AM);
 433           Done = true;
 434           break;
 435         }
 436       }
 437     }
 438   }
 439   if (!Done && MatchAddress(Addr, AM, /* is12Bit */ false))
 440     return false;
 441
 442   DOUT << "MatchAddress (final): "; DEBUG(AM.dump());
 443
 444   MVT VT = Addr.getValueType();
 445   if (AM.BaseType == SystemZRRIAddressMode::RegBase) {
 446     if (!AM.Base.Reg.getNode())
 447       AM.Base.Reg = CurDAG->getRegister(0, VT);
 448   }
 449
 450   assert(AM.IndexReg.getNode() == 0 && "Invalid reg-imm address mode!");
 451
 452   getAddressOperandsRI(AM, Base, Disp);
 453
 454   return true;
 455 }
 456
 457 /// Returns true if the address can be represented by a base register plus
 458 /// index register plus an unsigned 12-bit displacement [base + idx + imm].
 459 bool SystemZDAGToDAGISel::SelectAddrRRI12(SDValue Op, SDValue Addr,
 460                                 SDValue &Base, SDValue &Disp, SDValue &Index) {
 461   SystemZRRIAddressMode AM20, AM12;
 462   bool Done = false;
 463
 464   if (!Addr.hasOneUse()) {
 465     unsigned Opcode = Addr.getOpcode();
 466     if (Opcode != ISD::Constant && Opcode != ISD::FrameIndex) {
 467       // If we are able to fold N into addressing mode, then we'll allow it even
 468       // if N has multiple uses. In general, addressing computation is used as
 469       // addresses by all of its uses. But watch out for CopyToReg uses, that
 470       // means the address computation is liveout. It will be computed by a LA
 471       // so we want to avoid computing the address twice.
 472       for (SDNode::use_iterator UI = Addr.getNode()->use_begin(),
 473              UE = Addr.getNode()->use_end(); UI != UE; ++UI) {
 474         if (UI->getOpcode() == ISD::CopyToReg) {
 475           MatchAddressBase(Addr, AM12);
 476           Done = true;
 477           break;
 478         }
 479       }
 480     }
 481   }
 482   if (!Done && MatchAddress(Addr, AM12, /* is12Bit */ true))
 483     return false;
 484
 485   // Check, whether we can match stuff using 20-bit displacements
 486   if (!Done && !MatchAddress(Addr, AM20, /* is12Bit */ false))
 487     if (AM12.Disp == 0 && AM20.Disp != 0)
 488       return false;
 489
 490   DOUT << "MatchAddress (final): "; DEBUG(AM12.dump());
 491
 492   MVT VT = Addr.getValueType();
 493   if (AM12.BaseType == SystemZRRIAddressMode::RegBase) {
 494     if (!AM12.Base.Reg.getNode())
 495       AM12.Base.Reg = CurDAG->getRegister(0, VT);
 496   }
 497
 498   if (!AM12.IndexReg.getNode())
 499     AM12.IndexReg = CurDAG->getRegister(0, VT);
 500
 501   getAddressOperands(AM12, Base, Disp, Index);
 502
 503   return true;
 504 }
 505
 506 /// Returns true if the address can be represented by a base register plus
 507 /// index register plus a signed 20-bit displacement [base + idx + imm].
 508 bool SystemZDAGToDAGISel::SelectAddrRRI20(SDValue Op, SDValue Addr,
 509                                 SDValue &Base, SDValue &Disp, SDValue &Index) {
 510   SystemZRRIAddressMode AM;
 511   bool Done = false;
 512
 513   if (!Addr.hasOneUse()) {
 514     unsigned Opcode = Addr.getOpcode();
 515     if (Opcode != ISD::Constant && Opcode != ISD::FrameIndex) {
 516       // If we are able to fold N into addressing mode, then we'll allow it even
 517       // if N has multiple uses. In general, addressing computation is used as
 518       // addresses by all of its uses. But watch out for CopyToReg uses, that
 519       // means the address computation is liveout. It will be computed by a LA
 520       // so we want to avoid computing the address twice.
 521       for (SDNode::use_iterator UI = Addr.getNode()->use_begin(),
 522              UE = Addr.getNode()->use_end(); UI != UE; ++UI) {
 523         if (UI->getOpcode() == ISD::CopyToReg) {
 524           MatchAddressBase(Addr, AM);
 525           Done = true;
 526           break;
 527         }
 528       }
 529     }
 530   }
 531   if (!Done && MatchAddress(Addr, AM, /* is12Bit */ false))
 532     return false;
 533
 534   DOUT << "MatchAddress (final): "; DEBUG(AM.dump());
 535
 536   MVT VT = Addr.getValueType();
 537   if (AM.BaseType == SystemZRRIAddressMode::RegBase) {
 538     if (!AM.Base.Reg.getNode())
 539       AM.Base.Reg = CurDAG->getRegister(0, VT);
 540   }
 541
 542   if (!AM.IndexReg.getNode())
 543     AM.IndexReg = CurDAG->getRegister(0, VT);
 544
 545   getAddressOperands(AM, Base, Disp, Index);
 546
 547   return true;
 548 }
 549
 550 /// SelectLAAddr - it calls SelectAddr and determines if the maximal addressing
 551 /// mode it matches can be cost effectively emitted as an LA/LAY instruction.
 552 bool SystemZDAGToDAGISel::SelectLAAddr(SDValue Op, SDValue Addr,
 553                                   SDValue &Base, SDValue &Disp, SDValue &Index) {
 554   SystemZRRIAddressMode AM;
 555
 556   if (MatchAddress(Addr, AM, false))
 557     return false;
 558
 559   MVT VT = Addr.getValueType();
 560   unsigned Complexity = 0;
 561   if (AM.BaseType == SystemZRRIAddressMode::RegBase)
 562     if (AM.Base.Reg.getNode())
 563       Complexity = 1;
 564     else
 565       AM.Base.Reg = CurDAG->getRegister(0, VT);
 566   else if (AM.BaseType == SystemZRRIAddressMode::FrameIndexBase)
 567     Complexity = 4;
 568
 569   if (AM.IndexReg.getNode())
 570     Complexity += 1;
 571   else
 572     AM.IndexReg = CurDAG->getRegister(0, VT);
 573
 574   if (AM.Disp && (AM.Base.Reg.getNode() || AM.IndexReg.getNode()))
 575     Complexity += 1;
 576
 577   if (Complexity > 2) {
 578     getAddressOperands(AM, Base, Disp, Index);
 579     return true;
 580   }
 581
 582   return false;
 583 }
 584
 585 bool SystemZDAGToDAGISel::TryFoldLoad(SDValue P, SDValue N,
 586                                  SDValue &Base, SDValue &Disp, SDValue &Index) {
 587   if (ISD::isNON_EXTLoad(N.getNode()) &&
 588       N.hasOneUse() &&
 589       IsLegalAndProfitableToFold(N.getNode(), P.getNode(), P.getNode()))
 590     return SelectAddrRRI20(P, N.getOperand(1), Base, Disp, Index);
 591   return false;
 592 }
 593
 594 /// InstructionSelect - This callback is invoked by
 595 /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
 596 void SystemZDAGToDAGISel::InstructionSelect() {
 597   DEBUG(BB->dump());
 598
 599   // Codegen the basic block.
 600 #ifndef NDEBUG
 601   DOUT << "===== Instruction selection begins:\n";
 602   Indent = 0;
 603 #endif
 604   SelectRoot(*CurDAG);
 605 #ifndef NDEBUG
 606   DOUT << "===== Instruction selection ends:\n";
 607 #endif
 608
 609   CurDAG->RemoveDeadNodes();
 610 }
 611
 612 SDNode *SystemZDAGToDAGISel::Select(SDValue Op) {
 613   SDNode *Node = Op.getNode();
 614   MVT NVT = Node->getValueType(0);
 615   DebugLoc dl = Op.getDebugLoc();
 616   unsigned Opcode = Node->getOpcode();
 617
 618   // Dump information about the Node being selected
 619   #ifndef NDEBUG
 620   DOUT << std::string(Indent, ' ') << "Selecting: ";
 621   DEBUG(Node->dump(CurDAG));
 622   DOUT << "\n";
 623   Indent += 2;
 624   #endif
 625
 626   // If we have a custom node, we already have selected!
 627   if (Node->isMachineOpcode()) {
 628     #ifndef NDEBUG
 629     DOUT << std::string(Indent-2, ' ') << "== ";
 630     DEBUG(Node->dump(CurDAG));
 631     DOUT << "\n";
 632     Indent -= 2;
 633     #endif
 634     return NULL; // Already selected.
 635   }
 636
 637   switch (Opcode) {
 638   default: break;
 639   case ISD::SDIVREM: {
 640     unsigned Opc, MOpc;
 641     SDValue N0 = Node->getOperand(0);
 642     SDValue N1 = Node->getOperand(1);
 643
 644     MVT ResVT;
 645     bool is32Bit = false;
 646     switch (NVT.getSimpleVT()) {
 647       default: assert(0 && "Unsupported VT!");
 648       case MVT::i32:
 649         Opc = SystemZ::SDIVREM32r; MOpc = SystemZ::SDIVREM32m;
 650         ResVT = MVT::v2i64;
 651         is32Bit = true;
 652         break;
 653       case MVT::i64:
 654         Opc = SystemZ::SDIVREM64r; MOpc = SystemZ::SDIVREM64m;
 655         ResVT = MVT::v2i64;
 656         break;
 657     }
 658
 659     SDValue Tmp0, Tmp1, Tmp2;
 660     bool foldedLoad = TryFoldLoad(Op, N1, Tmp0, Tmp1, Tmp2);
 661
 662     // Prepare the dividend
 663     SDNode *Dividend;
 664     if (is32Bit)
 665       Dividend = CurDAG->getTargetNode(SystemZ::MOVSX64rr32, dl, MVT::i64, N0);
 666     else
 667       Dividend = N0.getNode();
 668
 669     // Insert prepared dividend into suitable 'subreg'
 670     SDNode *Tmp = CurDAG->getTargetNode(TargetInstrInfo::IMPLICIT_DEF,
 671                                         dl, ResVT);
 672     Dividend =
 673       CurDAG->getTargetNode(TargetInstrInfo::INSERT_SUBREG, dl, ResVT,
 674                             SDValue(Tmp, 0), SDValue(Dividend, 0),
 675                             CurDAG->getTargetConstant(subreg_odd, MVT::i32));
 676
 677     SDNode *Result;
 678     SDValue DivVal = SDValue(Dividend, 0);
 679     if (foldedLoad) {
 680       SDValue Ops[] = { DivVal, Tmp0, Tmp1, Tmp2, N1.getOperand(0) };
 681       Result = CurDAG->getTargetNode(MOpc, dl, ResVT, Ops, array_lengthof(Ops));
 682       // Update the chain.
 683       ReplaceUses(N1.getValue(1), SDValue(Result, 0));
 684     } else {
 685       Result = CurDAG->getTargetNode(Opc, dl, ResVT, SDValue(Dividend, 0), N1);
 686     }
 687
 688     // Copy the division (odd subreg) result, if it is needed.
 689     if (!Op.getValue(0).use_empty()) {
 690       unsigned SubRegIdx = (is32Bit ? subreg_odd32 : subreg_odd);
 691       SDNode *Div = CurDAG->getTargetNode(TargetInstrInfo::EXTRACT_SUBREG,
 692                                           dl, NVT,
 693                                           SDValue(Result, 0),
 694                                           CurDAG->getTargetConstant(SubRegIdx,
 695                                                                     MVT::i32));
 696
 697       ReplaceUses(Op.getValue(0), SDValue(Div, 0));
 698       #ifndef NDEBUG
 699       DOUT << std::string(Indent-2, ' ') << "=> ";
 700       DEBUG(Result->dump(CurDAG));
 701       DOUT << "\n";
 702       #endif
 703     }
 704
 705     // Copy the remainder (even subreg) result, if it is needed.
 706     if (!Op.getValue(1).use_empty()) {
 707       unsigned SubRegIdx = (is32Bit ? subreg_even32 : subreg_even);
 708       SDNode *Rem = CurDAG->getTargetNode(TargetInstrInfo::EXTRACT_SUBREG,
 709                                           dl, NVT,
 710                                           SDValue(Result, 0),
 711                                           CurDAG->getTargetConstant(SubRegIdx,
 712                                                                     MVT::i32));
 713
 714       ReplaceUses(Op.getValue(1), SDValue(Rem, 0));
 715       #ifndef NDEBUG
 716       DOUT << std::string(Indent-2, ' ') << "=> ";
 717       DEBUG(Result->dump(CurDAG));
 718       DOUT << "\n";
 719       #endif
 720     }
 721
 722 #ifndef NDEBUG
 723     Indent -= 2;
 724 #endif
 725
 726     return NULL;
 727   }
 728   case ISD::UDIVREM: {
 729     unsigned Opc, MOpc, ClrOpc;
 730     SDValue N0 = Node->getOperand(0);
 731     SDValue N1 = Node->getOperand(1);
 732     MVT ResVT;
 733
 734     bool is32Bit = false;
 735     switch (NVT.getSimpleVT()) {
 736       default: assert(0 && "Unsupported VT!");
 737       case MVT::i32:
 738         Opc = SystemZ::UDIVREM32r; MOpc = SystemZ::UDIVREM32m;
 739         ClrOpc = SystemZ::MOV64Pr0_even;
 740         ResVT = MVT::v2i32;
 741         is32Bit = true;
 742         break;
 743       case MVT::i64:
 744         Opc = SystemZ::UDIVREM64r; MOpc = SystemZ::UDIVREM64m;
 745         ClrOpc = SystemZ::MOV128r0_even;
 746         ResVT = MVT::v2i64;
 747         break;
 748     }
 749
 750     SDValue Tmp0, Tmp1, Tmp2;
 751     bool foldedLoad = TryFoldLoad(Op, N1, Tmp0, Tmp1, Tmp2);
 752
 753     // Prepare the dividend
 754     SDNode *Dividend = N0.getNode();
 755
 756     // Insert prepared dividend into suitable 'subreg'
 757     SDNode *Tmp = CurDAG->getTargetNode(TargetInstrInfo::IMPLICIT_DEF,
 758                                         dl, ResVT);
 759     {
 760       unsigned SubRegIdx = (is32Bit ? subreg_odd32 : subreg_odd);
 761       Dividend =
 762         CurDAG->getTargetNode(TargetInstrInfo::INSERT_SUBREG, dl, ResVT,
 763                               SDValue(Tmp, 0), SDValue(Dividend, 0),
 764                               CurDAG->getTargetConstant(SubRegIdx, MVT::i32));
 765     }
 766
 767     // Zero out even subreg
 768     Dividend = CurDAG->getTargetNode(ClrOpc, dl, ResVT, SDValue(Dividend, 0));
 769
 770     SDValue DivVal = SDValue(Dividend, 0);
 771     SDNode *Result;
 772     if (foldedLoad) {
 773       SDValue Ops[] = { DivVal, Tmp0, Tmp1, Tmp2, N1.getOperand(0) };
 774       Result = CurDAG->getTargetNode(MOpc, dl,ResVT,
 775                                      Ops, array_lengthof(Ops));
 776       // Update the chain.
 777       ReplaceUses(N1.getValue(1), SDValue(Result, 0));
 778     } else {
 779       Result = CurDAG->getTargetNode(Opc, dl, ResVT, DivVal, N1);
 780     }
 781
 782     // Copy the division (odd subreg) result, if it is needed.
 783     if (!Op.getValue(0).use_empty()) {
 784       unsigned SubRegIdx = (is32Bit ? subreg_odd32 : subreg_odd);
 785       SDNode *Div = CurDAG->getTargetNode(TargetInstrInfo::EXTRACT_SUBREG,
 786                                           dl, NVT,
 787                                           SDValue(Result, 0),
 788                                           CurDAG->getTargetConstant(SubRegIdx,
 789                                                                     MVT::i32));
 790       ReplaceUses(Op.getValue(0), SDValue(Div, 0));
 791       #ifndef NDEBUG
 792       DOUT << std::string(Indent-2, ' ') << "=> ";
 793       DEBUG(Result->dump(CurDAG));
 794       DOUT << "\n";
 795       #endif
 796     }
 797
 798     // Copy the remainder (even subreg) result, if it is needed.
 799     if (!Op.getValue(1).use_empty()) {
 800       unsigned SubRegIdx = (is32Bit ? subreg_even32 : subreg_even);
 801       SDNode *Rem = CurDAG->getTargetNode(TargetInstrInfo::EXTRACT_SUBREG,
 802                                           dl, NVT,
 803                                           SDValue(Result, 0),
 804                                           CurDAG->getTargetConstant(SubRegIdx,
 805                                                                     MVT::i32));
 806       ReplaceUses(Op.getValue(1), SDValue(Rem, 0));
 807       #ifndef NDEBUG
 808       DOUT << std::string(Indent-2, ' ') << "=> ";
 809       DEBUG(Result->dump(CurDAG));
 810       DOUT << "\n";
 811       #endif
 812     }
 813
 814 #ifndef NDEBUG
 815     Indent -= 2;
 816 #endif
 817
 818     return NULL;
 819   }
 820   }
 821
 822   // Select the default instruction
 823   SDNode *ResNode = SelectCode(Op);
 824
 825   #ifndef NDEBUG
 826   DOUT << std::string(Indent-2, ' ') << "=> ";
 827   if (ResNode == NULL || ResNode == Op.getNode())
 828     DEBUG(Op.getNode()->dump(CurDAG));
 829   else
 830     DEBUG(ResNode->dump(CurDAG));
 831   DOUT << "\n";
 832   Indent -= 2;
 833   #endif
 834
 835   return ResNode;
 836 }