SystemZISelDAGToDAG.cpp revision 961bb6f43026964004c0b811bd19fdf1735db5bc 
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"
31using namespace llvm;
32
33namespace {
34  /// SystemZRRIAddressMode - This corresponds to rriaddr, but uses SDValue's
35  /// instead of register numbers for the leaves of the matched tree.
36  struct SystemZRRIAddressMode {
37    enum {
38      RegBase,
39      FrameIndexBase
40    } BaseType;
41
42    struct {            // This is really a union, discriminated by BaseType!
43      SDValue Reg;
44      int FrameIndex;
45    } Base;
46
47    SDValue IndexReg;
48    int32_t Disp;
49
50    SystemZRRIAddressMode()
51      : BaseType(RegBase), IndexReg(), Disp(0) {
52    }
53
54    void dump() {
55      cerr << "SystemZRRIAddressMode " << this << '\n';
56      if (BaseType == RegBase) {
57        cerr << "Base.Reg ";
58        if (Base.Reg.getNode() != 0) Base.Reg.getNode()->dump();
59        else cerr << "nul";
60        cerr << '\n';
61      } else {
62        cerr << " Base.FrameIndex " << Base.FrameIndex << '\n';
63      }
64      cerr << "IndexReg ";
65      if (IndexReg.getNode() != 0) IndexReg.getNode()->dump();
66      else cerr << "nul";
67      cerr << " Disp " << Disp << '\n';
68    }
69  };
70}
71
72/// SystemZDAGToDAGISel - SystemZ specific code to select SystemZ machine
73/// instructions for SelectionDAG operations.
74///
75namespace {
76  class SystemZDAGToDAGISel : public SelectionDAGISel {
77    SystemZTargetLowering &Lowering;
78    const SystemZSubtarget &Subtarget;
79
80  public:
81    SystemZDAGToDAGISel(SystemZTargetMachine &TM, CodeGenOpt::Level OptLevel)
82      : SelectionDAGISel(TM, OptLevel),
83        Lowering(*TM.getTargetLowering()),
84        Subtarget(*TM.getSubtargetImpl()) { }
85
86    virtual void InstructionSelect();
87
88    virtual const char *getPassName() const {
89      return "SystemZ DAG->DAG Pattern Instruction Selection";
90    }
91
92    /// getI16Imm - Return a target constant with the specified value, of type
93    /// i16.
94    inline SDValue getI16Imm(uint64_t Imm) {
95      return CurDAG->getTargetConstant(Imm, MVT::i16);
96    }
97
98    /// getI32Imm - Return a target constant with the specified value, of type
99    /// i32.
100    inline SDValue getI32Imm(uint64_t Imm) {
101      return CurDAG->getTargetConstant(Imm, MVT::i32);
102    }
103
104    // Include the pieces autogenerated from the target description.
105    #include "SystemZGenDAGISel.inc"
106
107  private:
108    bool SelectAddrRRI(SDValue Op, SDValue Addr,
109                       SDValue &Base, SDValue &Index, SDValue &Disp);
110    SDNode *Select(SDValue Op);
111    bool SelectAddrRI(const SDValue& Op, SDValue& Addr,
112                      SDValue &Base, SDValue &Disp);
113    bool MatchAddress(SDValue N, SystemZRRIAddressMode &AM, unsigned Depth = 0);
114    bool MatchAddressBase(SDValue N, SystemZRRIAddressMode &AM);
115
116  #ifndef NDEBUG
117    unsigned Indent;
118  #endif
119  };
120}  // end anonymous namespace
121
122/// createSystemZISelDag - This pass converts a legalized DAG into a
123/// SystemZ-specific DAG, ready for instruction scheduling.
124///
125FunctionPass *llvm::createSystemZISelDag(SystemZTargetMachine &TM,
126                                        CodeGenOpt::Level OptLevel) {
127  return new SystemZDAGToDAGISel(TM, OptLevel);
128}
129
130/// isImmSExt20 - This method tests to see if the node is either a 32-bit
131/// or 64-bit immediate, and if the value can be accurately represented as a
132/// sign extension from a 20-bit value. If so, this returns true and the
133/// immediate.
134static bool isImmSExt20(int64_t Val, int32_t &Imm) {
135  if (Val >= -524288 && Val <= 524287) {
136    Imm = (int32_t)Val;
137    return true;
138  }
139  return false;
140}
141
142static bool isImmSExt20(SDNode *N, int32_t &Imm) {
143  if (N->getOpcode() != ISD::Constant)
144    return false;
145
146  return isImmSExt20(cast<ConstantSDNode>(N)->getSExtValue(), Imm);
147}
148
149static bool isImmSExt20(SDValue Op, int32_t &Imm) {
150  return isImmSExt20(Op.getNode(), Imm);
151}
152
153/// Returns true if the address can be represented by a base register plus
154/// a signed 20-bit displacement [r+imm].
155bool SystemZDAGToDAGISel::SelectAddrRI(const SDValue& Op, SDValue& Addr,
156                                       SDValue &Base, SDValue &Disp) {
157  // FIXME dl should come from parent load or store, not from address
158  DebugLoc dl = Addr.getDebugLoc();
159  MVT VT = Addr.getValueType();
160
161  if (Addr.getOpcode() == ISD::ADD) {
162    int32_t Imm = 0;
163    if (isImmSExt20(Addr.getOperand(1), Imm)) {
164      Disp = CurDAG->getTargetConstant(Imm, MVT::i32);
165      if (FrameIndexSDNode *FI =
166          dyn_cast<FrameIndexSDNode>(Addr.getOperand(0))) {
167        Base = CurDAG->getTargetFrameIndex(FI->getIndex(), VT);
168      } else {
169        Base = Addr.getOperand(0);
170      }
171      return true; // [r+i]
172    }
173  } else if (Addr.getOpcode() == ISD::OR) {
174    int32_t Imm = 0;
175    if (isImmSExt20(Addr.getOperand(1), Imm)) {
176      // If this is an or of disjoint bitfields, we can codegen this as an add
177      // (for better address arithmetic) if the LHS and RHS of the OR are
178      // provably disjoint.
179      APInt LHSKnownZero, LHSKnownOne;
180      CurDAG->ComputeMaskedBits(Addr.getOperand(0),
181                                APInt::getAllOnesValue(Addr.getOperand(0)
182                                                       .getValueSizeInBits()),
183                                LHSKnownZero, LHSKnownOne);
184
185      if ((LHSKnownZero.getZExtValue()|~(uint64_t)Imm) == ~0ULL) {
186        // If all of the bits are known zero on the LHS or RHS, the add won't
187        // carry.
188        Base = Addr.getOperand(0);
189        Disp = CurDAG->getTargetConstant(Imm, MVT::i32);
190        return true;
191      }
192    }
193  } else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Addr)) {
194    // Loading from a constant address.
195
196    // If this address fits entirely in a 20-bit sext immediate field, codegen
197    // this as "d(r0)"
198    int32_t Imm;
199    if (isImmSExt20(CN, Imm)) {
200      Disp = CurDAG->getTargetConstant(Imm, MVT::i32);
201      Base = CurDAG->getRegister(0, VT);
202      return true;
203    }
204  }
205
206  Disp = CurDAG->getTargetConstant(0, MVT::i32);
207  if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Addr))
208    Base = CurDAG->getTargetFrameIndex(FI->getIndex(), VT);
209  else
210    Base = Addr;
211  return true;      // [r+0]
212}
213
214/// MatchAddress - Add the specified node to the specified addressing mode,
215/// returning true if it cannot be done.  This just pattern matches for the
216/// addressing mode.
217bool SystemZDAGToDAGISel::MatchAddress(SDValue N, SystemZRRIAddressMode &AM,
218                                       unsigned Depth) {
219  DebugLoc dl = N.getDebugLoc();
220  DOUT << "MatchAddress: "; DEBUG(AM.dump());
221  // Limit recursion.
222  if (Depth > 5)
223    return MatchAddressBase(N, AM);
224
225  // FIXME: We can perform better here. If we have something like
226  // (shift (add A, imm), N), we can try to reassociate stuff and fold shift of
227  // imm into addressing mode.
228  switch (N.getOpcode()) {
229  default: break;
230  case ISD::Constant: {
231    uint64_t Val = cast<ConstantSDNode>(N)->getSExtValue();
232    int32_t Imm;
233    if (isImmSExt20(AM.Disp + Val, Imm)) {
234      AM.Disp = Imm;
235      return false;
236    }
237    break;
238  }
239
240  case ISD::FrameIndex:
241    if (AM.BaseType == SystemZRRIAddressMode::RegBase
242        && AM.Base.Reg.getNode() == 0) {
243      AM.BaseType = SystemZRRIAddressMode::FrameIndexBase;
244      AM.Base.FrameIndex = cast<FrameIndexSDNode>(N)->getIndex();
245      return false;
246    }
247    break;
248
249  case ISD::SUB: {
250    // Given A-B, if A can be completely folded into the address and
251    // the index field with the index field unused, use -B as the index.
252    // This is a win if a has multiple parts that can be folded into
253    // the address. Also, this saves a mov if the base register has
254    // other uses, since it avoids a two-address sub instruction, however
255    // it costs an additional mov if the index register has other uses.
256
257    // Test if the LHS of the sub can be folded.
258    SystemZRRIAddressMode Backup = AM;
259    if (MatchAddress(N.getNode()->getOperand(0), AM, Depth+1)) {
260      AM = Backup;
261      break;
262    }
263    // Test if the index field is free for use.
264    if (AM.IndexReg.getNode()) {
265      AM = Backup;
266      break;
267    }
268
269    // If the base is a register with multiple uses, this transformation may
270    // save a mov. Otherwise it's probably better not to do it.
271    if (AM.BaseType == SystemZRRIAddressMode::RegBase &&
272        (!AM.Base.Reg.getNode() || AM.Base.Reg.getNode()->hasOneUse())) {
273      AM = Backup;
274      break;
275    }
276
277    // Ok, the transformation is legal and appears profitable. Go for it.
278    SDValue RHS = N.getNode()->getOperand(1);
279    SDValue Zero = CurDAG->getConstant(0, N.getValueType());
280    SDValue Neg = CurDAG->getNode(ISD::SUB, dl, N.getValueType(), Zero, RHS);
281    AM.IndexReg = Neg;
282
283    // Insert the new nodes into the topological ordering.
284    if (Zero.getNode()->getNodeId() == -1 ||
285        Zero.getNode()->getNodeId() > N.getNode()->getNodeId()) {
286      CurDAG->RepositionNode(N.getNode(), Zero.getNode());
287      Zero.getNode()->setNodeId(N.getNode()->getNodeId());
288    }
289    if (Neg.getNode()->getNodeId() == -1 ||
290        Neg.getNode()->getNodeId() > N.getNode()->getNodeId()) {
291      CurDAG->RepositionNode(N.getNode(), Neg.getNode());
292      Neg.getNode()->setNodeId(N.getNode()->getNodeId());
293    }
294    return false;
295  }
296
297  case ISD::ADD: {
298    SystemZRRIAddressMode Backup = AM;
299    if (!MatchAddress(N.getNode()->getOperand(0), AM, Depth+1) &&
300        !MatchAddress(N.getNode()->getOperand(1), AM, Depth+1))
301      return false;
302    AM = Backup;
303    if (!MatchAddress(N.getNode()->getOperand(1), AM, Depth+1) &&
304        !MatchAddress(N.getNode()->getOperand(0), AM, Depth+1))
305      return false;
306    AM = Backup;
307
308    // If we couldn't fold both operands into the address at the same time,
309    // see if we can just put each operand into a register and fold at least
310    // the add.
311    if (AM.BaseType == SystemZRRIAddressMode::RegBase &&
312        !AM.Base.Reg.getNode() && !AM.IndexReg.getNode()) {
313      AM.Base.Reg = N.getNode()->getOperand(0);
314      AM.IndexReg = N.getNode()->getOperand(1);
315      return false;
316    }
317    break;
318  }
319
320  case ISD::OR:
321    // Handle "X | C" as "X + C" iff X is known to have C bits clear.
322    if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
323      SystemZRRIAddressMode Backup = AM;
324      uint64_t Offset = CN->getSExtValue();
325      int32_t Imm;
326      // Start with the LHS as an addr mode.
327      if (!MatchAddress(N.getOperand(0), AM, Depth+1) &&
328          // The resultant disp must fit in 20-bits.
329          isImmSExt20(AM.Disp + Offset, Imm) &&
330          // Check to see if the LHS & C is zero.
331          CurDAG->MaskedValueIsZero(N.getOperand(0), CN->getAPIntValue())) {
332        AM.Disp = Imm;
333        return false;
334      }
335      AM = Backup;
336    }
337    break;
338  }
339
340  return MatchAddressBase(N, AM);
341}
342
343/// MatchAddressBase - Helper for MatchAddress. Add the specified node to the
344/// specified addressing mode without any further recursion.
345bool SystemZDAGToDAGISel::MatchAddressBase(SDValue N,
346                                           SystemZRRIAddressMode &AM) {
347  // Is the base register already occupied?
348  if (AM.BaseType != SystemZRRIAddressMode::RegBase || AM.Base.Reg.getNode()) {
349    // If so, check to see if the scale index register is set.
350    if (AM.IndexReg.getNode() == 0) {
351      AM.IndexReg = N;
352      return false;
353    }
354
355    // Otherwise, we cannot select it.
356    return true;
357  }
358
359  // Default, generate it as a register.
360  AM.BaseType = SystemZRRIAddressMode::RegBase;
361  AM.Base.Reg = N;
362  return false;
363}
364
365/// Returns true if the address can be represented by a base register plus
366/// index register plus a signed 20-bit displacement [base + idx + imm].
367bool SystemZDAGToDAGISel::SelectAddrRRI(SDValue Op, SDValue Addr,
368                                SDValue &Base, SDValue &Index, SDValue &Disp) {
369  SystemZRRIAddressMode AM;
370  bool Done = false;
371
372  // FIXME: Should we better use lay instruction for non-single uses?
373
374  if (!Done && MatchAddress(Addr, AM))
375    return false;
376
377  MVT VT = Addr.getValueType();
378  if (AM.BaseType == SystemZRRIAddressMode::RegBase) {
379    if (!AM.Base.Reg.getNode())
380      AM.Base.Reg = CurDAG->getRegister(0, VT);
381  }
382
383  if (!AM.IndexReg.getNode())
384    AM.IndexReg = CurDAG->getRegister(0, VT);
385
386  if (AM.BaseType == SystemZRRIAddressMode::RegBase)
387    Base = AM.Base.Reg;
388  else
389    Base = CurDAG->getTargetFrameIndex(AM.Base.FrameIndex, TLI.getPointerTy());
390  Index = AM.IndexReg;
391  Disp = Disp = CurDAG->getTargetConstant(AM.Disp, MVT::i32);
392
393  return true;
394}
395
396/// InstructionSelect - This callback is invoked by
397/// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
398void SystemZDAGToDAGISel::InstructionSelect() {
399  DEBUG(BB->dump());
400
401  // Codegen the basic block.
402#ifndef NDEBUG
403  DOUT << "===== Instruction selection begins:\n";
404  Indent = 0;
405#endif
406  SelectRoot(*CurDAG);
407#ifndef NDEBUG
408  DOUT << "===== Instruction selection ends:\n";
409#endif
410
411  CurDAG->RemoveDeadNodes();
412}
413
414SDNode *SystemZDAGToDAGISel::Select(SDValue Op) {
415  SDNode *Node = Op.getNode();
416  DebugLoc dl = Op.getDebugLoc();
417
418  // Dump information about the Node being selected
419  #ifndef NDEBUG
420  DOUT << std::string(Indent, ' ') << "Selecting: ";
421  DEBUG(Node->dump(CurDAG));
422  DOUT << "\n";
423  Indent += 2;
424  #endif
425
426  // If we have a custom node, we already have selected!
427  if (Node->isMachineOpcode()) {
428    #ifndef NDEBUG
429    DOUT << std::string(Indent-2, ' ') << "== ";
430    DEBUG(Node->dump(CurDAG));
431    DOUT << "\n";
432    Indent -= 2;
433    #endif
434    return NULL;
435  }
436
437  // Select the default instruction
438  SDNode *ResNode = SelectCode(Op);
439
440  #ifndef NDEBUG
441  DOUT << std::string(Indent-2, ' ') << "=> ";
442  if (ResNode == NULL || ResNode == Op.getNode())
443    DEBUG(Op.getNode()->dump(CurDAG));
444  else
445    DEBUG(ResNode->dump(CurDAG));
446  DOUT << "\n";
447  Indent -= 2;
448  #endif
449
450  return ResNode;
451}
452