X86ISelDAGToDAG.cpp revision 0114e949034dd3032599799fda9dc9d62aa60088 
1//===- X86ISelDAGToDAG.cpp - A DAG pattern matching inst selector for X86 -===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file was developed by the Evan Cheng and is distributed under
6// the University of Illinois Open Source License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines a DAG pattern matching instruction selector for X86,
11// converting from a legalized dag to a X86 dag.
12//
13//===----------------------------------------------------------------------===//
14
15#include "X86.h"
16#include "X86Subtarget.h"
17#include "X86ISelLowering.h"
18#include "llvm/GlobalValue.h"
19#include "llvm/CodeGen/MachineConstantPool.h"
20#include "llvm/CodeGen/MachineFunction.h"
21#include "llvm/CodeGen/SelectionDAGISel.h"
22#include "llvm/Target/TargetMachine.h"
23#include "llvm/Support/Debug.h"
24#include "llvm/ADT/Statistic.h"
25using namespace llvm;
26
27//===----------------------------------------------------------------------===//
28//                      Pattern Matcher Implementation
29//===----------------------------------------------------------------------===//
30
31namespace {
32  /// X86ISelAddressMode - This corresponds to X86AddressMode, but uses
33  /// SDOperand's instead of register numbers for the leaves of the matched
34  /// tree.
35  struct X86ISelAddressMode {
36    enum {
37      RegBase,
38      FrameIndexBase,
39      ConstantPoolBase
40    } BaseType;
41
42    struct {            // This is really a union, discriminated by BaseType!
43      SDOperand Reg;
44      int FrameIndex;
45    } Base;
46
47    unsigned Scale;
48    SDOperand IndexReg;
49    unsigned Disp;
50    GlobalValue *GV;
51
52    X86ISelAddressMode()
53      : BaseType(RegBase), Scale(1), IndexReg(), Disp(0), GV(0) {
54    }
55  };
56}
57
58namespace {
59  Statistic<>
60  NumFPKill("x86-codegen", "Number of FP_REG_KILL instructions added");
61
62  //===--------------------------------------------------------------------===//
63  /// ISel - X86 specific code to select X86 machine instructions for
64  /// SelectionDAG operations.
65  ///
66  class X86DAGToDAGISel : public SelectionDAGISel {
67    /// ContainsFPCode - Every instruction we select that uses or defines a FP
68    /// register should set this to true.
69    bool ContainsFPCode;
70
71    /// X86Lowering - This object fully describes how to lower LLVM code to an
72    /// X86-specific SelectionDAG.
73    X86TargetLowering X86Lowering;
74
75    /// Subtarget - Keep a pointer to the X86Subtarget around so that we can
76    /// make the right decision when generating code for different targets.
77    const X86Subtarget *Subtarget;
78  public:
79    X86DAGToDAGISel(TargetMachine &TM)
80      : SelectionDAGISel(X86Lowering), X86Lowering(TM) {
81      Subtarget = &TM.getSubtarget<X86Subtarget>();
82    }
83
84    virtual const char *getPassName() const {
85      return "X86 DAG->DAG Instruction Selection";
86    }
87
88    /// InstructionSelectBasicBlock - This callback is invoked by
89    /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
90    virtual void InstructionSelectBasicBlock(SelectionDAG &DAG);
91
92// Include the pieces autogenerated from the target description.
93#include "X86GenDAGISel.inc"
94
95  private:
96    SDOperand Select(SDOperand N);
97
98    bool MatchAddress(SDOperand N, X86ISelAddressMode &AM);
99    bool SelectAddr(SDOperand N, SDOperand &Base, SDOperand &Scale,
100                    SDOperand &Index, SDOperand &Disp);
101    bool SelectLEAAddr(SDOperand N, SDOperand &Base, SDOperand &Scale,
102                       SDOperand &Index, SDOperand &Disp);
103    bool TryFoldLoad(SDOperand N, SDOperand &Base, SDOperand &Scale,
104                     SDOperand &Index, SDOperand &Disp);
105
106    inline void getAddressOperands(X86ISelAddressMode &AM, SDOperand &Base,
107                                   SDOperand &Scale, SDOperand &Index,
108                                   SDOperand &Disp) {
109      Base  = (AM.BaseType == X86ISelAddressMode::FrameIndexBase) ?
110        CurDAG->getTargetFrameIndex(AM.Base.FrameIndex, MVT::i32) : AM.Base.Reg;
111      Scale = getI8Imm(AM.Scale);
112      Index = AM.IndexReg;
113      Disp  = AM.GV ? CurDAG->getTargetGlobalAddress(AM.GV, MVT::i32, AM.Disp)
114        : getI32Imm(AM.Disp);
115    }
116
117    /// getI8Imm - Return a target constant with the specified value, of type
118    /// i8.
119    inline SDOperand getI8Imm(unsigned Imm) {
120      return CurDAG->getTargetConstant(Imm, MVT::i8);
121    }
122
123    /// getI16Imm - Return a target constant with the specified value, of type
124    /// i16.
125    inline SDOperand getI16Imm(unsigned Imm) {
126      return CurDAG->getTargetConstant(Imm, MVT::i16);
127    }
128
129    /// getI32Imm - Return a target constant with the specified value, of type
130    /// i32.
131    inline SDOperand getI32Imm(unsigned Imm) {
132      return CurDAG->getTargetConstant(Imm, MVT::i32);
133    }
134  };
135}
136
137/// InstructionSelectBasicBlock - This callback is invoked by SelectionDAGISel
138/// when it has created a SelectionDAG for us to codegen.
139void X86DAGToDAGISel::InstructionSelectBasicBlock(SelectionDAG &DAG) {
140  DEBUG(BB->dump());
141
142  // Codegen the basic block.
143  DAG.setRoot(Select(DAG.getRoot()));
144  CodeGenMap.clear();
145  DAG.RemoveDeadNodes();
146
147  // Emit machine code to BB.
148  ScheduleAndEmitDAG(DAG);
149}
150
151/// FIXME: copied from X86ISelPattern.cpp
152/// MatchAddress - Add the specified node to the specified addressing mode,
153/// returning true if it cannot be done.  This just pattern matches for the
154/// addressing mode
155bool X86DAGToDAGISel::MatchAddress(SDOperand N, X86ISelAddressMode &AM) {
156  switch (N.getOpcode()) {
157  default: break;
158  case ISD::FrameIndex:
159    if (AM.BaseType == X86ISelAddressMode::RegBase && AM.Base.Reg.Val == 0) {
160      AM.BaseType = X86ISelAddressMode::FrameIndexBase;
161      AM.Base.FrameIndex = cast<FrameIndexSDNode>(N)->getIndex();
162      return false;
163    }
164    break;
165
166  case ISD::ConstantPool:
167    if (AM.BaseType == X86ISelAddressMode::RegBase && AM.Base.Reg.Val == 0) {
168      if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(N)) {
169        AM.BaseType = X86ISelAddressMode::ConstantPoolBase;
170        AM.Base.Reg = CurDAG->getTargetConstantPool(CP->get(), MVT::i32);
171        return false;
172      }
173    }
174    break;
175
176  case ISD::GlobalAddress:
177  case ISD::TargetGlobalAddress:
178    if (AM.GV == 0) {
179      AM.GV = cast<GlobalAddressSDNode>(N)->getGlobal();
180      return false;
181    }
182    break;
183
184  case ISD::Constant:
185    AM.Disp += cast<ConstantSDNode>(N)->getValue();
186    return false;
187
188  case ISD::SHL:
189    if (AM.IndexReg.Val == 0 && AM.Scale == 1)
190      if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(1))) {
191        unsigned Val = CN->getValue();
192        if (Val == 1 || Val == 2 || Val == 3) {
193          AM.Scale = 1 << Val;
194          SDOperand ShVal = N.Val->getOperand(0);
195
196          // Okay, we know that we have a scale by now.  However, if the scaled
197          // value is an add of something and a constant, we can fold the
198          // constant into the disp field here.
199          if (ShVal.Val->getOpcode() == ISD::ADD && ShVal.hasOneUse() &&
200              isa<ConstantSDNode>(ShVal.Val->getOperand(1))) {
201            AM.IndexReg = ShVal.Val->getOperand(0);
202            ConstantSDNode *AddVal =
203              cast<ConstantSDNode>(ShVal.Val->getOperand(1));
204            AM.Disp += AddVal->getValue() << Val;
205          } else {
206            AM.IndexReg = ShVal;
207          }
208          return false;
209        }
210      }
211    break;
212
213  case ISD::MUL:
214    // X*[3,5,9] -> X+X*[2,4,8]
215    if (AM.IndexReg.Val == 0 && AM.BaseType == X86ISelAddressMode::RegBase &&
216        AM.Base.Reg.Val == 0)
217      if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(1)))
218        if (CN->getValue() == 3 || CN->getValue() == 5 || CN->getValue() == 9) {
219          AM.Scale = unsigned(CN->getValue())-1;
220
221          SDOperand MulVal = N.Val->getOperand(0);
222          SDOperand Reg;
223
224          // Okay, we know that we have a scale by now.  However, if the scaled
225          // value is an add of something and a constant, we can fold the
226          // constant into the disp field here.
227          if (MulVal.Val->getOpcode() == ISD::ADD && MulVal.hasOneUse() &&
228              isa<ConstantSDNode>(MulVal.Val->getOperand(1))) {
229            Reg = MulVal.Val->getOperand(0);
230            ConstantSDNode *AddVal =
231              cast<ConstantSDNode>(MulVal.Val->getOperand(1));
232            AM.Disp += AddVal->getValue() * CN->getValue();
233          } else {
234            Reg = N.Val->getOperand(0);
235          }
236
237          AM.IndexReg = AM.Base.Reg = Reg;
238          return false;
239        }
240    break;
241
242  case ISD::ADD: {
243    X86ISelAddressMode Backup = AM;
244    if (!MatchAddress(N.Val->getOperand(0), AM) &&
245        !MatchAddress(N.Val->getOperand(1), AM))
246      return false;
247    AM = Backup;
248    if (!MatchAddress(N.Val->getOperand(1), AM) &&
249        !MatchAddress(N.Val->getOperand(0), AM))
250      return false;
251    AM = Backup;
252    break;
253  }
254  }
255
256  // Is the base register already occupied?
257  if (AM.BaseType != X86ISelAddressMode::RegBase || AM.Base.Reg.Val) {
258    // If so, check to see if the scale index register is set.
259    if (AM.IndexReg.Val == 0) {
260      AM.IndexReg = N;
261      AM.Scale = 1;
262      return false;
263    }
264
265    // Otherwise, we cannot select it.
266    return true;
267  }
268
269  // Default, generate it as a register.
270  AM.BaseType = X86ISelAddressMode::RegBase;
271  AM.Base.Reg = N;
272  return false;
273}
274
275/// SelectAddr - returns true if it is able pattern match an addressing mode.
276/// It returns the operands which make up the maximal addressing mode it can
277/// match by reference.
278bool X86DAGToDAGISel::SelectAddr(SDOperand N, SDOperand &Base, SDOperand &Scale,
279                                 SDOperand &Index, SDOperand &Disp) {
280  X86ISelAddressMode AM;
281  if (!MatchAddress(N, AM)) {
282    if (AM.BaseType == X86ISelAddressMode::RegBase) {
283      if (AM.Base.Reg.Val)
284        AM.Base.Reg = Select(AM.Base.Reg);
285      else
286        AM.Base.Reg = CurDAG->getRegister(0, MVT::i32);
287    }
288    if (AM.IndexReg.Val)
289      AM.IndexReg = Select(AM.IndexReg);
290    else
291      AM.IndexReg = CurDAG->getRegister(0, MVT::i32);
292
293    getAddressOperands(AM, Base, Scale, Index, Disp);
294    return true;
295  }
296  return false;
297}
298
299bool X86DAGToDAGISel::TryFoldLoad(SDOperand N, SDOperand &Base,
300                                  SDOperand &Scale, SDOperand &Index,
301                                  SDOperand &Disp) {
302  if (N.getOpcode() == ISD::LOAD && N.hasOneUse() &&
303      CodeGenMap.count(N.getValue(1)))
304    return SelectAddr(N.getOperand(1), Base, Scale, Index, Disp);
305  return false;
306}
307
308static bool isRegister0(SDOperand Op) {
309  if (RegisterSDNode *R = dyn_cast<RegisterSDNode>(Op))
310    return (R->getReg() == 0);
311  return false;
312}
313
314/// SelectLEAAddr - it calls SelectAddr and determines if the maximal addressing
315/// mode it matches can be cost effectively emitted as an LEA instruction.
316/// For X86, it always is unless it's just a (Reg + const).
317bool X86DAGToDAGISel::SelectLEAAddr(SDOperand N, SDOperand &Base, SDOperand &Scale,
318                                    SDOperand &Index, SDOperand &Disp) {
319  X86ISelAddressMode AM;
320  if (!MatchAddress(N, AM)) {
321    bool SelectBase  = false;
322    bool SelectIndex = false;
323    bool Check       = false;
324    if (AM.BaseType == X86ISelAddressMode::RegBase) {
325      if (AM.Base.Reg.Val) {
326        Check      = true;
327        SelectBase = true;
328      } else {
329        AM.Base.Reg = CurDAG->getRegister(0, MVT::i32);
330      }
331    }
332
333    if (AM.IndexReg.Val) {
334      SelectIndex = true;
335    } else {
336      AM.IndexReg = CurDAG->getRegister(0, MVT::i32);
337    }
338
339    if (Check) {
340      unsigned Complexity = 0;
341      if (AM.Scale > 1)
342        Complexity++;
343      if (SelectIndex)
344        Complexity++;
345      if (AM.GV)
346        Complexity++;
347      else if (AM.Disp > 1)
348        Complexity++;
349      if (Complexity <= 1)
350        return false;
351    }
352
353    if (SelectBase)
354      AM.Base.Reg = Select(AM.Base.Reg);
355    if (SelectIndex)
356      AM.IndexReg = Select(AM.IndexReg);
357
358    getAddressOperands(AM, Base, Scale, Index, Disp);
359    return true;
360  }
361  return false;
362}
363
364SDOperand X86DAGToDAGISel::Select(SDOperand N) {
365  SDNode *Node = N.Val;
366  MVT::ValueType NVT = Node->getValueType(0);
367  unsigned Opc, MOpc;
368  unsigned Opcode = Node->getOpcode();
369
370  if (Opcode >= ISD::BUILTIN_OP_END && Opcode < X86ISD::FIRST_NUMBER)
371    return N;   // Already selected.
372
373  switch (Opcode) {
374    default: break;
375    case ISD::MULHU:
376    case ISD::MULHS: {
377      if (Opcode == ISD::MULHU)
378        switch (NVT) {
379        default: assert(0 && "Unsupported VT!");
380        case MVT::i8:  Opc = X86::MUL8r;  MOpc = X86::MUL8m;  break;
381        case MVT::i16: Opc = X86::MUL16r; MOpc = X86::MUL16m; break;
382        case MVT::i32: Opc = X86::MUL32r; MOpc = X86::MUL32m; break;
383        }
384      else
385        switch (NVT) {
386        default: assert(0 && "Unsupported VT!");
387        case MVT::i8:  Opc = X86::IMUL8r;  MOpc = X86::IMUL8m;  break;
388        case MVT::i16: Opc = X86::IMUL16r; MOpc = X86::IMUL16m; break;
389        case MVT::i32: Opc = X86::IMUL32r; MOpc = X86::IMUL32m; break;
390        }
391
392      unsigned LoReg, HiReg;
393      switch (NVT) {
394      default: assert(0 && "Unsupported VT!");
395      case MVT::i8:  LoReg = X86::AL;  HiReg = X86::AH;  break;
396      case MVT::i16: LoReg = X86::AX;  HiReg = X86::DX;  break;
397      case MVT::i32: LoReg = X86::EAX; HiReg = X86::EDX; break;
398      }
399
400      SDOperand N0 = Node->getOperand(0);
401      SDOperand N1 = Node->getOperand(1);
402
403      bool foldedLoad = false;
404      SDOperand Tmp0, Tmp1, Tmp2, Tmp3;
405      foldedLoad = TryFoldLoad(N1, Tmp0, Tmp1, Tmp2, Tmp3);
406      SDOperand Chain = foldedLoad ? Select(N1.getOperand(0))
407                                   : CurDAG->getEntryNode();
408
409      SDOperand InFlag;
410      Chain  = CurDAG->getCopyToReg(Chain, CurDAG->getRegister(LoReg, NVT),
411                                    Select(N0), InFlag);
412      InFlag = Chain.getValue(1);
413
414      if (foldedLoad) {
415        Chain  = CurDAG->getTargetNode(MOpc, MVT::Other, MVT::Flag, Tmp0, Tmp1,
416                                       Tmp2, Tmp3, Chain, InFlag);
417        InFlag = Chain.getValue(1);
418      } else {
419        InFlag = CurDAG->getTargetNode(Opc, MVT::Flag, Select(N1), InFlag);
420      }
421
422      SDOperand Result = CurDAG->getCopyFromReg(Chain, HiReg, NVT, InFlag);
423      CodeGenMap[N.getValue(0)] = Result;
424      CodeGenMap[N.getValue(1)] = Result.getValue(1);
425      CodeGenMap[N.getValue(2)] = Result.getValue(2);
426      return Result.getValue(N.ResNo);
427    }
428
429    case ISD::TRUNCATE: {
430      unsigned Reg;
431      MVT::ValueType VT;
432      switch (Node->getOperand(0).getValueType()) {
433        default: assert(0 && "Unknown truncate!");
434        case MVT::i16: Reg = X86::AX;  Opc = X86::MOV16rr; VT = MVT::i16; break;
435        case MVT::i32: Reg = X86::EAX; Opc = X86::MOV32rr; VT = MVT::i32; break;
436      }
437      SDOperand Tmp0 = Select(Node->getOperand(0));
438      SDOperand Tmp1 = CurDAG->getTargetNode(Opc, VT, Tmp0);
439      SDOperand InFlag = SDOperand(0,0);
440      SDOperand Result = CurDAG->getCopyToReg(CurDAG->getEntryNode(),
441                                              Reg, Tmp1, InFlag).getValue(1);
442      SDOperand Chain = Result.getValue(0);
443      InFlag = Result.getValue(1);
444
445      switch (NVT) {
446        default: assert(0 && "Unknown truncate!");
447        case MVT::i8:  Reg = X86::AL;  Opc = X86::MOV8rr;  VT = MVT::i8;  break;
448        case MVT::i16: Reg = X86::AX;  Opc = X86::MOV16rr; VT = MVT::i16; break;
449      }
450
451      Result = CurDAG->getCopyFromReg(Chain,
452                                      Reg, VT, InFlag);
453      if (N.Val->hasOneUse())
454        return CurDAG->SelectNodeTo(N.Val, Opc, VT, Result);
455      else
456        return CodeGenMap[N] = CurDAG->getTargetNode(Opc, VT, Result);
457      break;
458    }
459
460    case ISD::UNDEF: {
461      Opc = (NVT == MVT::f64) ? (X86Vector >= SSE2 ? X86::FLD0SD : X86::FpLD0)
462                              : X86::IMPLICIT_DEF;
463      if (N.Val->hasOneUse())
464        return CurDAG->SelectNodeTo(N.Val, Opc, NVT);
465      else
466        return CodeGenMap[N] = CurDAG->getTargetNode(Opc, NVT);
467    }
468  }
469
470  return SelectCode(N);
471}
472
473/// createX86ISelDag - This pass converts a legalized DAG into a
474/// X86-specific DAG, ready for instruction scheduling.
475///
476FunctionPass *llvm::createX86ISelDag(TargetMachine &TM) {
477  return new X86DAGToDAGISel(TM);
478}
479