LLVM API Documentation

SystemZISelDAGToDAG.cpp

Go to the documentation of this file.
00001 //==-- SystemZISelDAGToDAG.cpp - A dag to dag inst selector for SystemZ ---===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines an instruction selector for the SystemZ target.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #include "SystemZ.h"
00015 #include "SystemZISelLowering.h"
00016 #include "SystemZTargetMachine.h"
00017 #include "llvm/DerivedTypes.h"
00018 #include "llvm/Function.h"
00019 #include "llvm/Intrinsics.h"
00020 #include "llvm/CallingConv.h"
00021 #include "llvm/Constants.h"
00022 #include "llvm/CodeGen/MachineFrameInfo.h"
00023 #include "llvm/CodeGen/MachineFunction.h"
00024 #include "llvm/CodeGen/MachineInstrBuilder.h"
00025 #include "llvm/CodeGen/MachineRegisterInfo.h"
00026 #include "llvm/CodeGen/SelectionDAG.h"
00027 #include "llvm/CodeGen/SelectionDAGISel.h"
00028 #include "llvm/Target/TargetLowering.h"
00029 #include "llvm/Support/Compiler.h"
00030 #include "llvm/Support/Debug.h"
00031 #include "llvm/Support/raw_ostream.h"
00032 using namespace llvm;
00033 
00034 static const unsigned subreg_even32 = 1;
00035 static const unsigned subreg_odd32  = 2;
00036 static const unsigned subreg_even   = 3;
00037 static const unsigned subreg_odd    = 4;
00038 
00039 namespace {
00040   /// SystemZRRIAddressMode - This corresponds to rriaddr, but uses SDValue's
00041   /// instead of register numbers for the leaves of the matched tree.
00042   struct SystemZRRIAddressMode {
00043     enum {
00044       RegBase,
00045       FrameIndexBase
00046     } BaseType;
00047 
00048     struct {            // This is really a union, discriminated by BaseType!
00049       SDValue Reg;
00050       int FrameIndex;
00051     } Base;
00052 
00053     SDValue IndexReg;
00054     int64_t Disp;
00055     bool isRI;
00056 
00057     SystemZRRIAddressMode(bool RI = false)
00058       : BaseType(RegBase), IndexReg(), Disp(0), isRI(RI) {
00059     }
00060 
00061     void dump() {
00062       cerr << "SystemZRRIAddressMode " << this << '\n';
00063       if (BaseType == RegBase) {
00064         cerr << "Base.Reg ";
00065         if (Base.Reg.getNode() != 0) Base.Reg.getNode()->dump();
00066         else cerr << "nul";
00067         cerr << '\n';
00068       } else {
00069         cerr << " Base.FrameIndex " << Base.FrameIndex << '\n';
00070       }
00071       if (!isRI) {
00072         cerr << "IndexReg ";
00073         if (IndexReg.getNode() != 0) IndexReg.getNode()->dump();
00074         else cerr << "nul";
00075       }
00076       cerr << " Disp " << Disp << '\n';
00077     }
00078   };
00079 }
00080 
00081 /// SystemZDAGToDAGISel - SystemZ specific code to select SystemZ machine
00082 /// instructions for SelectionDAG operations.
00083 ///
00084 namespace {
00085   class SystemZDAGToDAGISel : public SelectionDAGISel {
00086     SystemZTargetLowering &Lowering;
00087     const SystemZSubtarget &Subtarget;
00088 
00089     void getAddressOperandsRI(const SystemZRRIAddressMode &AM,
00090                             SDValue &Base, SDValue &Disp);
00091     void getAddressOperands(const SystemZRRIAddressMode &AM,
00092                             SDValue &Base, SDValue &Disp,
00093                             SDValue &Index);
00094 
00095   public:
00096     SystemZDAGToDAGISel(SystemZTargetMachine &TM, CodeGenOpt::Level OptLevel)
00097       : SelectionDAGISel(TM, OptLevel),
00098         Lowering(*TM.getTargetLowering()),
00099         Subtarget(*TM.getSubtargetImpl()) { }
00100 
00101     virtual void InstructionSelect();
00102 
00103     virtual const char *getPassName() const {
00104       return "SystemZ DAG->DAG Pattern Instruction Selection";
00105     }
00106 
00107     /// getI8Imm - Return a target constant with the specified value, of type
00108     /// i8.
00109     inline SDValue getI8Imm(uint64_t Imm) {
00110       return CurDAG->getTargetConstant(Imm, MVT::i8);
00111     }
00112 
00113     /// getI16Imm - Return a target constant with the specified value, of type
00114     /// i16.
00115     inline SDValue getI16Imm(uint64_t Imm) {
00116       return CurDAG->getTargetConstant(Imm, MVT::i16);
00117     }
00118 
00119     /// getI32Imm - Return a target constant with the specified value, of type
00120     /// i32.
00121     inline SDValue getI32Imm(uint64_t Imm) {
00122       return CurDAG->getTargetConstant(Imm, MVT::i32);
00123     }
00124 
00125     // Include the pieces autogenerated from the target description.
00126     #include "SystemZGenDAGISel.inc"
00127 
00128   private:
00129     bool SelectAddrRI12Only(SDValue Op, SDValue& Addr,
00130                             SDValue &Base, SDValue &Disp);
00131     bool SelectAddrRI12(SDValue Op, SDValue& Addr,
00132                         SDValue &Base, SDValue &Disp,
00133                         bool is12BitOnly = false);
00134     bool SelectAddrRI(SDValue Op, SDValue& Addr,
00135                       SDValue &Base, SDValue &Disp);
00136     bool SelectAddrRRI12(SDValue Op, SDValue Addr,
00137                          SDValue &Base, SDValue &Disp, SDValue &Index);
00138     bool SelectAddrRRI20(SDValue Op, SDValue Addr,
00139                          SDValue &Base, SDValue &Disp, SDValue &Index);
00140     bool SelectLAAddr(SDValue Op, SDValue Addr,
00141                       SDValue &Base, SDValue &Disp, SDValue &Index);
00142 
00143     SDNode *Select(SDValue Op);
00144 
00145     bool TryFoldLoad(SDValue P, SDValue N,
00146                      SDValue &Base, SDValue &Disp, SDValue &Index);
00147 
00148     bool MatchAddress(SDValue N, SystemZRRIAddressMode &AM,
00149                       bool is12Bit, unsigned Depth = 0);
00150     bool MatchAddressBase(SDValue N, SystemZRRIAddressMode &AM);
00151     bool MatchAddressRI(SDValue N, SystemZRRIAddressMode &AM,
00152                         bool is12Bit);
00153 
00154   #ifndef NDEBUG
00155     unsigned Indent;
00156   #endif
00157   };
00158 }  // end anonymous namespace
00159 
00160 /// createSystemZISelDag - This pass converts a legalized DAG into a
00161 /// SystemZ-specific DAG, ready for instruction scheduling.
00162 ///
00163 FunctionPass *llvm::createSystemZISelDag(SystemZTargetMachine &TM,
00164                                         CodeGenOpt::Level OptLevel) {
00165   return new SystemZDAGToDAGISel(TM, OptLevel);
00166 }
00167 
00168 /// isImmSExt20 - This method tests to see if the node is either a 32-bit
00169 /// or 64-bit immediate, and if the value can be accurately represented as a
00170 /// sign extension from a 20-bit value. If so, this returns true and the
00171 /// immediate.
00172 static bool isImmSExt20(int64_t Val, int64_t &Imm) {
00173   if (Val >= -524288 && Val <= 524287) {
00174     Imm = Val;
00175     return true;
00176   }
00177   return false;
00178 }
00179 
00180 /// isImmZExt12 - This method tests to see if the node is either a 32-bit
00181 /// or 64-bit immediate, and if the value can be accurately represented as a
00182 /// zero extension from a 12-bit value. If so, this returns true and the
00183 /// immediate.
00184 static bool isImmZExt12(int64_t Val, int64_t &Imm) {
00185   if (Val >= 0 && Val <= 0xFFF) {
00186     Imm = Val;
00187     return true;
00188   }
00189   return false;
00190 }
00191 
00192 /// MatchAddress - Add the specified node to the specified addressing mode,
00193 /// returning true if it cannot be done.  This just pattern matches for the
00194 /// addressing mode.
00195 bool SystemZDAGToDAGISel::MatchAddress(SDValue N, SystemZRRIAddressMode &AM,
00196                                        bool is12Bit, unsigned Depth) {
00197   DebugLoc dl = N.getDebugLoc();
00198   DOUT << "MatchAddress: "; DEBUG(AM.dump());
00199   // Limit recursion.
00200   if (Depth > 5)
00201     return MatchAddressBase(N, AM);
00202 
00203   // FIXME: We can perform better here. If we have something like
00204   // (shift (add A, imm), N), we can try to reassociate stuff and fold shift of
00205   // imm into addressing mode.
00206   switch (N.getOpcode()) {
00207   default: break;
00208   case ISD::Constant: {
00209     int64_t Val = cast<ConstantSDNode>(N)->getSExtValue();
00210     int64_t Imm = 0;
00211     bool Match = (is12Bit ?
00212                   isImmZExt12(AM.Disp + Val, Imm) :
00213                   isImmSExt20(AM.Disp + Val, Imm));
00214     if (Match) {
00215       AM.Disp = Imm;
00216       return false;
00217     }
00218     break;
00219   }
00220 
00221   case ISD::FrameIndex:
00222     if (AM.BaseType == SystemZRRIAddressMode::RegBase &&
00223         AM.Base.Reg.getNode() == 0) {
00224       AM.BaseType = SystemZRRIAddressMode::FrameIndexBase;
00225       AM.Base.FrameIndex = cast<FrameIndexSDNode>(N)->getIndex();
00226       return false;
00227     }
00228     break;
00229 
00230   case ISD::SUB: {
00231     // Given A-B, if A can be completely folded into the address and
00232     // the index field with the index field unused, use -B as the index.
00233     // This is a win if a has multiple parts that can be folded into
00234     // the address. Also, this saves a mov if the base register has
00235     // other uses, since it avoids a two-address sub instruction, however
00236     // it costs an additional mov if the index register has other uses.
00237 
00238     // Test if the LHS of the sub can be folded.
00239     SystemZRRIAddressMode Backup = AM;
00240     if (MatchAddress(N.getNode()->getOperand(0), AM, is12Bit, Depth+1)) {
00241       AM = Backup;
00242       break;
00243     }
00244     // Test if the index field is free for use.
00245     if (AM.IndexReg.getNode() || AM.isRI) {
00246       AM = Backup;
00247       break;
00248     }
00249 
00250     // If the base is a register with multiple uses, this transformation may
00251     // save a mov. Otherwise it's probably better not to do it.
00252     if (AM.BaseType == SystemZRRIAddressMode::RegBase &&
00253         (!AM.Base.Reg.getNode() || AM.Base.Reg.getNode()->hasOneUse())) {
00254       AM = Backup;
00255       break;
00256     }
00257 
00258     // Ok, the transformation is legal and appears profitable. Go for it.
00259     SDValue RHS = N.getNode()->getOperand(1);
00260     SDValue Zero = CurDAG->getConstant(0, N.getValueType());
00261     SDValue Neg = CurDAG->getNode(ISD::SUB, dl, N.getValueType(), Zero, RHS);
00262     AM.IndexReg = Neg;
00263 
00264     // Insert the new nodes into the topological ordering.
00265     if (Zero.getNode()->getNodeId() == -1 ||
00266         Zero.getNode()->getNodeId() > N.getNode()->getNodeId()) {
00267       CurDAG->RepositionNode(N.getNode(), Zero.getNode());
00268       Zero.getNode()->setNodeId(N.getNode()->getNodeId());
00269     }
00270     if (Neg.getNode()->getNodeId() == -1 ||
00271         Neg.getNode()->getNodeId() > N.getNode()->getNodeId()) {
00272       CurDAG->RepositionNode(N.getNode(), Neg.getNode());
00273       Neg.getNode()->setNodeId(N.getNode()->getNodeId());
00274     }
00275     return false;
00276   }
00277 
00278   case ISD::ADD: {
00279     SystemZRRIAddressMode Backup = AM;
00280     if (!MatchAddress(N.getNode()->getOperand(0), AM, is12Bit, Depth+1) &&
00281         !MatchAddress(N.getNode()->getOperand(1), AM, is12Bit, Depth+1))
00282       return false;
00283     AM = Backup;
00284     if (!MatchAddress(N.getNode()->getOperand(1), AM, is12Bit, Depth+1) &&
00285         !MatchAddress(N.getNode()->getOperand(0), AM, is12Bit, Depth+1))
00286       return false;
00287     AM = Backup;
00288 
00289     // If we couldn't fold both operands into the address at the same time,
00290     // see if we can just put each operand into a register and fold at least
00291     // the add.
00292     if (!AM.isRI &&
00293         AM.BaseType == SystemZRRIAddressMode::RegBase &&
00294         !AM.Base.Reg.getNode() && !AM.IndexReg.getNode()) {
00295       AM.Base.Reg = N.getNode()->getOperand(0);
00296       AM.IndexReg = N.getNode()->getOperand(1);
00297       return false;
00298     }
00299     break;
00300   }
00301 
00302   case ISD::OR:
00303     // Handle "X | C" as "X + C" iff X is known to have C bits clear.
00304     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
00305       SystemZRRIAddressMode Backup = AM;
00306       int64_t Offset = CN->getSExtValue();
00307       int64_t Imm = 0;
00308       bool MatchOffset = (is12Bit ?
00309                           isImmZExt12(AM.Disp + Offset, Imm) :
00310                           isImmSExt20(AM.Disp + Offset, Imm));
00311       // The resultant disp must fit in 12 or 20-bits.
00312       if (MatchOffset &&
00313           // LHS should be an addr mode.
00314           !MatchAddress(N.getOperand(0), AM, is12Bit, Depth+1) &&
00315           // Check to see if the LHS & C is zero.
00316           CurDAG->MaskedValueIsZero(N.getOperand(0), CN->getAPIntValue())) {
00317         AM.Disp = Imm;
00318         return false;
00319       }
00320       AM = Backup;
00321     }
00322     break;
00323   }
00324 
00325   return MatchAddressBase(N, AM);
00326 }
00327 
00328 /// MatchAddressBase - Helper for MatchAddress. Add the specified node to the
00329 /// specified addressing mode without any further recursion.
00330 bool SystemZDAGToDAGISel::MatchAddressBase(SDValue N,
00331                                            SystemZRRIAddressMode &AM) {
00332   // Is the base register already occupied?
00333   if (AM.BaseType != SystemZRRIAddressMode::RegBase || AM.Base.Reg.getNode()) {
00334     // If so, check to see if the index register is set.
00335     if (AM.IndexReg.getNode() == 0 && !AM.isRI) {
00336       AM.IndexReg = N;
00337       return false;
00338     }
00339 
00340     // Otherwise, we cannot select it.
00341     return true;
00342   }
00343 
00344   // Default, generate it as a register.
00345   AM.BaseType = SystemZRRIAddressMode::RegBase;
00346   AM.Base.Reg = N;
00347   return false;
00348 }
00349 
00350 void SystemZDAGToDAGISel::getAddressOperandsRI(const SystemZRRIAddressMode &AM,
00351                                                SDValue &Base, SDValue &Disp) {
00352   if (AM.BaseType == SystemZRRIAddressMode::RegBase)
00353     Base = AM.Base.Reg;
00354   else
00355     Base = CurDAG->getTargetFrameIndex(AM.Base.FrameIndex, TLI.getPointerTy());
00356   Disp = CurDAG->getTargetConstant(AM.Disp, MVT::i64);
00357 }
00358 
00359 void SystemZDAGToDAGISel::getAddressOperands(const SystemZRRIAddressMode &AM,
00360                                              SDValue &Base, SDValue &Disp,
00361                                              SDValue &Index) {
00362   getAddressOperandsRI(AM, Base, Disp);
00363   Index = AM.IndexReg;
00364 }
00365 
00366 /// Returns true if the address can be represented by a base register plus
00367 /// an unsigned 12-bit displacement [r+imm].
00368 bool SystemZDAGToDAGISel::SelectAddrRI12Only(SDValue Op, SDValue& Addr,
00369                                              SDValue &Base, SDValue &Disp) {
00370   return SelectAddrRI12(Op, Addr, Base, Disp, /*is12BitOnly*/true);
00371 }
00372 
00373 bool SystemZDAGToDAGISel::SelectAddrRI12(SDValue Op, SDValue& Addr,
00374                                          SDValue &Base, SDValue &Disp,
00375                                          bool is12BitOnly) {
00376   SystemZRRIAddressMode AM20(/*isRI*/true), AM12(/*isRI*/true);
00377   bool Done = false;
00378 
00379   if (!Addr.hasOneUse()) {
00380     unsigned Opcode = Addr.getOpcode();
00381     if (Opcode != ISD::Constant && Opcode != ISD::FrameIndex) {
00382       // If we are able to fold N into addressing mode, then we'll allow it even
00383       // if N has multiple uses. In general, addressing computation is used as
00384       // addresses by all of its uses. But watch out for CopyToReg uses, that
00385       // means the address computation is liveout. It will be computed by a LA
00386       // so we want to avoid computing the address twice.
00387       for (SDNode::use_iterator UI = Addr.getNode()->use_begin(),
00388              UE = Addr.getNode()->use_end(); UI != UE; ++UI) {
00389         if (UI->getOpcode() == ISD::CopyToReg) {
00390           MatchAddressBase(Addr, AM12);
00391           Done = true;
00392           break;
00393         }
00394       }
00395     }
00396   }
00397   if (!Done && MatchAddress(Addr, AM12, /* is12Bit */ true))
00398     return false;
00399 
00400   // Check, whether we can match stuff using 20-bit displacements
00401   if (!Done && !is12BitOnly &&
00402       !MatchAddress(Addr, AM20, /* is12Bit */ false))
00403     if (AM12.Disp == 0 && AM20.Disp != 0)
00404       return false;
00405 
00406   DOUT << "MatchAddress (final): "; DEBUG(AM12.dump());
00407 
00408   EVT VT = Addr.getValueType();
00409   if (AM12.BaseType == SystemZRRIAddressMode::RegBase) {
00410     if (!AM12.Base.Reg.getNode())
00411       AM12.Base.Reg = CurDAG->getRegister(0, VT);
00412   }
00413 
00414   assert(AM12.IndexReg.getNode() == 0 && "Invalid reg-imm address mode!");
00415 
00416   getAddressOperandsRI(AM12, Base, Disp);
00417 
00418   return true;
00419 }
00420 
00421 /// Returns true if the address can be represented by a base register plus
00422 /// a signed 20-bit displacement [r+imm].
00423 bool SystemZDAGToDAGISel::SelectAddrRI(SDValue Op, SDValue& Addr,
00424                                        SDValue &Base, SDValue &Disp) {
00425   SystemZRRIAddressMode AM(/*isRI*/true);
00426   bool Done = false;
00427 
00428   if (!Addr.hasOneUse()) {
00429     unsigned Opcode = Addr.getOpcode();
00430     if (Opcode != ISD::Constant && Opcode != ISD::FrameIndex) {
00431       // If we are able to fold N into addressing mode, then we'll allow it even
00432       // if N has multiple uses. In general, addressing computation is used as
00433       // addresses by all of its uses. But watch out for CopyToReg uses, that
00434       // means the address computation is liveout. It will be computed by a LA
00435       // so we want to avoid computing the address twice.
00436       for (SDNode::use_iterator UI = Addr.getNode()->use_begin(),
00437              UE = Addr.getNode()->use_end(); UI != UE; ++UI) {
00438         if (UI->getOpcode() == ISD::CopyToReg) {
00439           MatchAddressBase(Addr, AM);
00440           Done = true;
00441           break;
00442         }
00443       }
00444     }
00445   }
00446   if (!Done && MatchAddress(Addr, AM, /* is12Bit */ false))
00447     return false;
00448 
00449   DOUT << "MatchAddress (final): "; DEBUG(AM.dump());
00450 
00451   EVT VT = Addr.getValueType();
00452   if (AM.BaseType == SystemZRRIAddressMode::RegBase) {
00453     if (!AM.Base.Reg.getNode())
00454       AM.Base.Reg = CurDAG->getRegister(0, VT);
00455   }
00456 
00457   assert(AM.IndexReg.getNode() == 0 && "Invalid reg-imm address mode!");
00458 
00459   getAddressOperandsRI(AM, Base, Disp);
00460 
00461   return true;
00462 }
00463 
00464 /// Returns true if the address can be represented by a base register plus
00465 /// index register plus an unsigned 12-bit displacement [base + idx + imm].
00466 bool SystemZDAGToDAGISel::SelectAddrRRI12(SDValue Op, SDValue Addr,
00467                                 SDValue &Base, SDValue &Disp, SDValue &Index) {
00468   SystemZRRIAddressMode AM20, AM12;
00469   bool Done = false;
00470 
00471   if (!Addr.hasOneUse()) {
00472     unsigned Opcode = Addr.getOpcode();
00473     if (Opcode != ISD::Constant && Opcode != ISD::FrameIndex) {
00474       // If we are able to fold N into addressing mode, then we'll allow it even
00475       // if N has multiple uses. In general, addressing computation is used as
00476       // addresses by all of its uses. But watch out for CopyToReg uses, that
00477       // means the address computation is liveout. It will be computed by a LA
00478       // so we want to avoid computing the address twice.
00479       for (SDNode::use_iterator UI = Addr.getNode()->use_begin(),
00480              UE = Addr.getNode()->use_end(); UI != UE; ++UI) {
00481         if (UI->getOpcode() == ISD::CopyToReg) {
00482           MatchAddressBase(Addr, AM12);
00483           Done = true;
00484           break;
00485         }
00486       }
00487     }
00488   }
00489   if (!Done && MatchAddress(Addr, AM12, /* is12Bit */ true))
00490     return false;
00491 
00492   // Check, whether we can match stuff using 20-bit displacements
00493   if (!Done && !MatchAddress(Addr, AM20, /* is12Bit */ false))
00494     if (AM12.Disp == 0 && AM20.Disp != 0)
00495       return false;
00496 
00497   DOUT << "MatchAddress (final): "; DEBUG(AM12.dump());
00498 
00499   EVT VT = Addr.getValueType();
00500   if (AM12.BaseType == SystemZRRIAddressMode::RegBase) {
00501     if (!AM12.Base.Reg.getNode())
00502       AM12.Base.Reg = CurDAG->getRegister(0, VT);
00503   }
00504 
00505   if (!AM12.IndexReg.getNode())
00506     AM12.IndexReg = CurDAG->getRegister(0, VT);
00507 
00508   getAddressOperands(AM12, Base, Disp, Index);
00509 
00510   return true;
00511 }
00512 
00513 /// Returns true if the address can be represented by a base register plus
00514 /// index register plus a signed 20-bit displacement [base + idx + imm].
00515 bool SystemZDAGToDAGISel::SelectAddrRRI20(SDValue Op, SDValue Addr,
00516                                 SDValue &Base, SDValue &Disp, SDValue &Index) {
00517   SystemZRRIAddressMode AM;
00518   bool Done = false;
00519 
00520   if (!Addr.hasOneUse()) {
00521     unsigned Opcode = Addr.getOpcode();
00522     if (Opcode != ISD::Constant && Opcode != ISD::FrameIndex) {
00523       // If we are able to fold N into addressing mode, then we'll allow it even
00524       // if N has multiple uses. In general, addressing computation is used as
00525       // addresses by all of its uses. But watch out for CopyToReg uses, that
00526       // means the address computation is liveout. It will be computed by a LA
00527       // so we want to avoid computing the address twice.
00528       for (SDNode::use_iterator UI = Addr.getNode()->use_begin(),
00529              UE = Addr.getNode()->use_end(); UI != UE; ++UI) {
00530         if (UI->getOpcode() == ISD::CopyToReg) {
00531           MatchAddressBase(Addr, AM);
00532           Done = true;
00533           break;
00534         }
00535       }
00536     }
00537   }
00538   if (!Done && MatchAddress(Addr, AM, /* is12Bit */ false))
00539     return false;
00540 
00541   DOUT << "MatchAddress (final): "; DEBUG(AM.dump());
00542 
00543   EVT VT = Addr.getValueType();
00544   if (AM.BaseType == SystemZRRIAddressMode::RegBase) {
00545     if (!AM.Base.Reg.getNode())
00546       AM.Base.Reg = CurDAG->getRegister(0, VT);
00547   }
00548 
00549   if (!AM.IndexReg.getNode())
00550     AM.IndexReg = CurDAG->getRegister(0, VT);
00551 
00552   getAddressOperands(AM, Base, Disp, Index);
00553 
00554   return true;
00555 }
00556 
00557 /// SelectLAAddr - it calls SelectAddr and determines if the maximal addressing
00558 /// mode it matches can be cost effectively emitted as an LA/LAY instruction.
00559 bool SystemZDAGToDAGISel::SelectLAAddr(SDValue Op, SDValue Addr,
00560                                   SDValue &Base, SDValue &Disp, SDValue &Index) {
00561   SystemZRRIAddressMode AM;
00562 
00563   if (MatchAddress(Addr, AM, false))
00564     return false;
00565 
00566   EVT VT = Addr.getValueType();
00567   unsigned Complexity = 0;
00568   if (AM.BaseType == SystemZRRIAddressMode::RegBase)
00569     if (AM.Base.Reg.getNode())
00570       Complexity = 1;
00571     else
00572       AM.Base.Reg = CurDAG->getRegister(0, VT);
00573   else if (AM.BaseType == SystemZRRIAddressMode::FrameIndexBase)
00574     Complexity = 4;
00575 
00576   if (AM.IndexReg.getNode())
00577     Complexity += 1;
00578   else
00579     AM.IndexReg = CurDAG->getRegister(0, VT);
00580 
00581   if (AM.Disp && (AM.Base.Reg.getNode() || AM.IndexReg.getNode()))
00582     Complexity += 1;
00583 
00584   if (Complexity > 2) {
00585     getAddressOperands(AM, Base, Disp, Index);
00586     return true;
00587   }
00588 
00589   return false;
00590 }
00591 
00592 bool SystemZDAGToDAGISel::TryFoldLoad(SDValue P, SDValue N,
00593                                  SDValue &Base, SDValue &Disp, SDValue &Index) {
00594   if (ISD::isNON_EXTLoad(N.getNode()) &&
00595       N.hasOneUse() &&
00596       IsLegalAndProfitableToFold(N.getNode(), P.getNode(), P.getNode()))
00597     return SelectAddrRRI20(P, N.getOperand(1), Base, Disp, Index);
00598   return false;
00599 }
00600 
00601 /// InstructionSelect - This callback is invoked by
00602 /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
00603 void SystemZDAGToDAGISel::InstructionSelect() {
00604   DEBUG(BB->dump());
00605 
00606   // Codegen the basic block.
00607 #ifndef NDEBUG
00608   DOUT << "===== Instruction selection begins:\n";
00609   Indent = 0;
00610 #endif
00611   SelectRoot(*CurDAG);
00612 #ifndef NDEBUG
00613   DOUT << "===== Instruction selection ends:\n";
00614 #endif
00615 
00616   CurDAG->RemoveDeadNodes();
00617 }
00618 
00619 SDNode *SystemZDAGToDAGISel::Select(SDValue Op) {
00620   SDNode *Node = Op.getNode();
00621   EVT NVT = Node->getValueType(0);
00622   DebugLoc dl = Op.getDebugLoc();
00623   unsigned Opcode = Node->getOpcode();
00624 
00625   // Dump information about the Node being selected
00626   #ifndef NDEBUG
00627   DOUT << std::string(Indent, ' ') << "Selecting: ";
00628   DEBUG(Node->dump(CurDAG));
00629   DOUT << "\n";
00630   Indent += 2;
00631   #endif
00632 
00633   // If we have a custom node, we already have selected!
00634   if (Node->isMachineOpcode()) {
00635     #ifndef NDEBUG
00636     DOUT << std::string(Indent-2, ' ') << "== ";
00637     DEBUG(Node->dump(CurDAG));
00638     DOUT << "\n";
00639     Indent -= 2;
00640     #endif
00641     return NULL; // Already selected.
00642   }
00643 
00644   switch (Opcode) {
00645   default: break;
00646   case ISD::SDIVREM: {
00647     unsigned Opc, MOpc;
00648     SDValue N0 = Node->getOperand(0);
00649     SDValue N1 = Node->getOperand(1);
00650 
00651     EVT ResVT;
00652     bool is32Bit = false;
00653     switch (NVT.getSimpleVT().SimpleTy) {
00654       default: assert(0 && "Unsupported VT!");
00655       case MVT::i32:
00656         Opc = SystemZ::SDIVREM32r; MOpc = SystemZ::SDIVREM32m;
00657         ResVT = MVT::v2i64;
00658         is32Bit = true;
00659         break;
00660       case MVT::i64:
00661         Opc = SystemZ::SDIVREM64r; MOpc = SystemZ::SDIVREM64m;
00662         ResVT = MVT::v2i64;
00663         break;
00664     }
00665 
00666     SDValue Tmp0, Tmp1, Tmp2;
00667     bool foldedLoad = TryFoldLoad(Op, N1, Tmp0, Tmp1, Tmp2);
00668 
00669     // Prepare the dividend
00670     SDNode *Dividend;
00671     if (is32Bit)
00672       Dividend = CurDAG->getTargetNode(SystemZ::MOVSX64rr32, dl, MVT::i64, N0);
00673     else
00674       Dividend = N0.getNode();
00675 
00676     // Insert prepared dividend into suitable 'subreg'
00677     SDNode *Tmp = CurDAG->getTargetNode(TargetInstrInfo::IMPLICIT_DEF,
00678                                         dl, ResVT);
00679     Dividend =
00680       CurDAG->getTargetNode(TargetInstrInfo::INSERT_SUBREG, dl, ResVT,
00681                             SDValue(Tmp, 0), SDValue(Dividend, 0),
00682                             CurDAG->getTargetConstant(subreg_odd, MVT::i32));
00683 
00684     SDNode *Result;
00685     SDValue DivVal = SDValue(Dividend, 0);
00686     if (foldedLoad) {
00687       SDValue Ops[] = { DivVal, Tmp0, Tmp1, Tmp2, N1.getOperand(0) };
00688       Result = CurDAG->getTargetNode(MOpc, dl, ResVT, Ops, array_lengthof(Ops));
00689       // Update the chain.
00690       ReplaceUses(N1.getValue(1), SDValue(Result, 0));
00691     } else {
00692       Result = CurDAG->getTargetNode(Opc, dl, ResVT, SDValue(Dividend, 0), N1);
00693     }
00694 
00695     // Copy the division (odd subreg) result, if it is needed.
00696     if (!Op.getValue(0).use_empty()) {
00697       unsigned SubRegIdx = (is32Bit ? subreg_odd32 : subreg_odd);
00698       SDNode *Div = CurDAG->getTargetNode(TargetInstrInfo::EXTRACT_SUBREG,
00699                                           dl, NVT,
00700                                           SDValue(Result, 0),
00701                                           CurDAG->getTargetConstant(SubRegIdx,
00702                                                                     MVT::i32));
00703 
00704       ReplaceUses(Op.getValue(0), SDValue(Div, 0));
00705       #ifndef NDEBUG
00706       DOUT << std::string(Indent-2, ' ') << "=> ";
00707       DEBUG(Result->dump(CurDAG));
00708       DOUT << "\n";
00709       #endif
00710     }
00711 
00712     // Copy the remainder (even subreg) result, if it is needed.
00713     if (!Op.getValue(1).use_empty()) {
00714       unsigned SubRegIdx = (is32Bit ? subreg_even32 : subreg_even);
00715       SDNode *Rem = CurDAG->getTargetNode(TargetInstrInfo::EXTRACT_SUBREG,
00716                                           dl, NVT,
00717                                           SDValue(Result, 0),
00718                                           CurDAG->getTargetConstant(SubRegIdx,
00719                                                                     MVT::i32));
00720 
00721       ReplaceUses(Op.getValue(1), SDValue(Rem, 0));
00722       #ifndef NDEBUG
00723       DOUT << std::string(Indent-2, ' ') << "=> ";
00724       DEBUG(Result->dump(CurDAG));
00725       DOUT << "\n";
00726       #endif
00727     }
00728 
00729 #ifndef NDEBUG
00730     Indent -= 2;
00731 #endif
00732 
00733     return NULL;
00734   }
00735   case ISD::UDIVREM: {
00736     unsigned Opc, MOpc, ClrOpc;
00737     SDValue N0 = Node->getOperand(0);
00738     SDValue N1 = Node->getOperand(1);
00739     EVT ResVT;
00740 
00741     bool is32Bit = false;
00742     switch (NVT.getSimpleVT().SimpleTy) {
00743       default: assert(0 && "Unsupported VT!");
00744       case MVT::i32:
00745         Opc = SystemZ::UDIVREM32r; MOpc = SystemZ::UDIVREM32m;
00746         ClrOpc = SystemZ::MOV64Pr0_even;
00747         ResVT = MVT::v2i32;
00748         is32Bit = true;
00749         break;
00750       case MVT::i64:
00751         Opc = SystemZ::UDIVREM64r; MOpc = SystemZ::UDIVREM64m;
00752         ClrOpc = SystemZ::MOV128r0_even;
00753         ResVT = MVT::v2i64;
00754         break;
00755     }
00756 
00757     SDValue Tmp0, Tmp1, Tmp2;
00758     bool foldedLoad = TryFoldLoad(Op, N1, Tmp0, Tmp1, Tmp2);
00759 
00760     // Prepare the dividend
00761     SDNode *Dividend = N0.getNode();
00762 
00763     // Insert prepared dividend into suitable 'subreg'
00764     SDNode *Tmp = CurDAG->getTargetNode(TargetInstrInfo::IMPLICIT_DEF,
00765                                         dl, ResVT);
00766     {
00767       unsigned SubRegIdx = (is32Bit ? subreg_odd32 : subreg_odd);
00768       Dividend =
00769         CurDAG->getTargetNode(TargetInstrInfo::INSERT_SUBREG, dl, ResVT,
00770                               SDValue(Tmp, 0), SDValue(Dividend, 0),
00771                               CurDAG->getTargetConstant(SubRegIdx, MVT::i32));
00772     }
00773 
00774     // Zero out even subreg
00775     Dividend = CurDAG->getTargetNode(ClrOpc, dl, ResVT, SDValue(Dividend, 0));
00776 
00777     SDValue DivVal = SDValue(Dividend, 0);
00778     SDNode *Result;
00779     if (foldedLoad) {
00780       SDValue Ops[] = { DivVal, Tmp0, Tmp1, Tmp2, N1.getOperand(0) };
00781       Result = CurDAG->getTargetNode(MOpc, dl,ResVT,
00782                                      Ops, array_lengthof(Ops));
00783       // Update the chain.
00784       ReplaceUses(N1.getValue(1), SDValue(Result, 0));
00785     } else {
00786       Result = CurDAG->getTargetNode(Opc, dl, ResVT, DivVal, N1);
00787     }
00788 
00789     // Copy the division (odd subreg) result, if it is needed.
00790     if (!Op.getValue(0).use_empty()) {
00791       unsigned SubRegIdx = (is32Bit ? subreg_odd32 : subreg_odd);
00792       SDNode *Div = CurDAG->getTargetNode(TargetInstrInfo::EXTRACT_SUBREG,
00793                                           dl, NVT,
00794                                           SDValue(Result, 0),
00795                                           CurDAG->getTargetConstant(SubRegIdx,
00796                                                                     MVT::i32));
00797       ReplaceUses(Op.getValue(0), SDValue(Div, 0));
00798       #ifndef NDEBUG
00799       DOUT << std::string(Indent-2, ' ') << "=> ";
00800       DEBUG(Result->dump(CurDAG));
00801       DOUT << "\n";
00802       #endif
00803     }
00804 
00805     // Copy the remainder (even subreg) result, if it is needed.
00806     if (!Op.getValue(1).use_empty()) {
00807       unsigned SubRegIdx = (is32Bit ? subreg_even32 : subreg_even);
00808       SDNode *Rem = CurDAG->getTargetNode(TargetInstrInfo::EXTRACT_SUBREG,
00809                                           dl, NVT,
00810                                           SDValue(Result, 0),
00811                                           CurDAG->getTargetConstant(SubRegIdx,
00812                                                                     MVT::i32));
00813       ReplaceUses(Op.getValue(1), SDValue(Rem, 0));
00814       #ifndef NDEBUG
00815       DOUT << std::string(Indent-2, ' ') << "=> ";
00816       DEBUG(Result->dump(CurDAG));
00817       DOUT << "\n";
00818       #endif
00819     }
00820 
00821 #ifndef NDEBUG
00822     Indent -= 2;
00823 #endif
00824 
00825     return NULL;
00826   }
00827   }
00828 
00829   // Select the default instruction
00830   SDNode *ResNode = SelectCode(Op);
00831 
00832   #ifndef NDEBUG
00833   DOUT << std::string(Indent-2, ' ') << "=> ";
00834   if (ResNode == NULL || ResNode == Op.getNode())
00835     DEBUG(Op.getNode()->dump(CurDAG));
00836   else
00837     DEBUG(ResNode->dump(CurDAG));
00838   DOUT << "\n";
00839   Indent -= 2;
00840   #endif
00841 
00842   return ResNode;
00843 }