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