lib/Target/X86/X86ISelDAGToDAG.cpp

   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"
  25 using namespace llvm;
  26
  27 //===----------------------------------------------------------------------===//
  28 //                      Pattern Matcher Implementation
  29 //===----------------------------------------------------------------------===//
  30
  31 namespace {
  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
  58 namespace {
  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
 104     inline void getAddressOperands(X86ISelAddressMode &AM, SDOperand &Base,
 105                                    SDOperand &Scale, SDOperand &Index,
 106                                    SDOperand &Disp) {
 107       Base  = (AM.BaseType == X86ISelAddressMode::FrameIndexBase) ?
 108         CurDAG->getTargetFrameIndex(AM.Base.FrameIndex, MVT::i32) : AM.Base.Reg;
 109       Scale = getI8Imm(AM.Scale);
 110       Index = AM.IndexReg;
 111       Disp  = AM.GV ? CurDAG->getTargetGlobalAddress(AM.GV, MVT::i32, AM.Disp)
 112         : getI32Imm(AM.Disp);
 113     }
 114
 115     /// getI8Imm - Return a target constant with the specified value, of type
 116     /// i8.
 117     inline SDOperand getI8Imm(unsigned Imm) {
 118       return CurDAG->getTargetConstant(Imm, MVT::i8);
 119     }
 120
 121     /// getI16Imm - Return a target constant with the specified value, of type
 122     /// i16.
 123     inline SDOperand getI16Imm(unsigned Imm) {
 124       return CurDAG->getTargetConstant(Imm, MVT::i16);
 125     }
 126
 127     /// getI32Imm - Return a target constant with the specified value, of type
 128     /// i32.
 129     inline SDOperand getI32Imm(unsigned Imm) {
 130       return CurDAG->getTargetConstant(Imm, MVT::i32);
 131     }
 132   };
 133 }
 134
 135 /// InstructionSelectBasicBlock - This callback is invoked by SelectionDAGISel
 136 /// when it has created a SelectionDAG for us to codegen.
 137 void X86DAGToDAGISel::InstructionSelectBasicBlock(SelectionDAG &DAG) {
 138   DEBUG(BB->dump());
 139
 140   // Codegen the basic block.
 141   DAG.setRoot(Select(DAG.getRoot()));
 142   CodeGenMap.clear();
 143   DAG.RemoveDeadNodes();
 144
 145   // Emit machine code to BB.
 146   ScheduleAndEmitDAG(DAG);
 147 }
 148
 149 /// FIXME: copied from X86ISelPattern.cpp
 150 /// MatchAddress - Add the specified node to the specified addressing mode,
 151 /// returning true if it cannot be done.  This just pattern matches for the
 152 /// addressing mode
 153 bool X86DAGToDAGISel::MatchAddress(SDOperand N, X86ISelAddressMode &AM) {
 154   switch (N.getOpcode()) {
 155   default: break;
 156   case ISD::FrameIndex:
 157     if (AM.BaseType == X86ISelAddressMode::RegBase && AM.Base.Reg.Val == 0) {
 158       AM.BaseType = X86ISelAddressMode::FrameIndexBase;
 159       AM.Base.FrameIndex = cast<FrameIndexSDNode>(N)->getIndex();
 160       return false;
 161     }
 162     break;
 163
 164   case ISD::ConstantPool:
 165     if (AM.BaseType == X86ISelAddressMode::RegBase && AM.Base.Reg.Val == 0) {
 166       if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(N)) {
 167         AM.BaseType = X86ISelAddressMode::ConstantPoolBase;
 168         AM.Base.Reg = CurDAG->getTargetConstantPool(CP->get(), MVT::i32);
 169         return false;
 170       }
 171     }
 172     break;
 173
 174   case ISD::GlobalAddress:
 175   case ISD::TargetGlobalAddress:
 176     if (AM.GV == 0) {
 177       AM.GV = cast<GlobalAddressSDNode>(N)->getGlobal();
 178       return false;
 179     }
 180     break;
 181
 182   case ISD::Constant:
 183     AM.Disp += cast<ConstantSDNode>(N)->getValue();
 184     return false;
 185
 186   case ISD::SHL:
 187     if (AM.IndexReg.Val == 0 && AM.Scale == 1)
 188       if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(1))) {
 189         unsigned Val = CN->getValue();
 190         if (Val == 1 || Val == 2 || Val == 3) {
 191           AM.Scale = 1 << Val;
 192           SDOperand ShVal = N.Val->getOperand(0);
 193
 194           // Okay, we know that we have a scale by now.  However, if the scaled
 195           // value is an add of something and a constant, we can fold the
 196           // constant into the disp field here.
 197           if (ShVal.Val->getOpcode() == ISD::ADD && ShVal.hasOneUse() &&
 198               isa<ConstantSDNode>(ShVal.Val->getOperand(1))) {
 199             AM.IndexReg = ShVal.Val->getOperand(0);
 200             ConstantSDNode *AddVal =
 201               cast<ConstantSDNode>(ShVal.Val->getOperand(1));
 202             AM.Disp += AddVal->getValue() << Val;
 203           } else {
 204             AM.IndexReg = ShVal;
 205           }
 206           return false;
 207         }
 208       }
 209     break;
 210
 211   case ISD::MUL:
 212     // X*[3,5,9] -> X+X*[2,4,8]
 213     if (AM.IndexReg.Val == 0 && AM.BaseType == X86ISelAddressMode::RegBase &&
 214         AM.Base.Reg.Val == 0)
 215       if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(1)))
 216         if (CN->getValue() == 3 || CN->getValue() == 5 || CN->getValue() == 9) {
 217           AM.Scale = unsigned(CN->getValue())-1;
 218
 219           SDOperand MulVal = N.Val->getOperand(0);
 220           SDOperand Reg;
 221
 222           // Okay, we know that we have a scale by now.  However, if the scaled
 223           // value is an add of something and a constant, we can fold the
 224           // constant into the disp field here.
 225           if (MulVal.Val->getOpcode() == ISD::ADD && MulVal.hasOneUse() &&
 226               isa<ConstantSDNode>(MulVal.Val->getOperand(1))) {
 227             Reg = MulVal.Val->getOperand(0);
 228             ConstantSDNode *AddVal =
 229               cast<ConstantSDNode>(MulVal.Val->getOperand(1));
 230             AM.Disp += AddVal->getValue() * CN->getValue();
 231           } else {
 232             Reg = N.Val->getOperand(0);
 233           }
 234
 235           AM.IndexReg = AM.Base.Reg = Reg;
 236           return false;
 237         }
 238     break;
 239
 240   case ISD::ADD: {
 241     X86ISelAddressMode Backup = AM;
 242     if (!MatchAddress(N.Val->getOperand(0), AM) &&
 243         !MatchAddress(N.Val->getOperand(1), AM))
 244       return false;
 245     AM = Backup;
 246     if (!MatchAddress(N.Val->getOperand(1), AM) &&
 247         !MatchAddress(N.Val->getOperand(0), AM))
 248       return false;
 249     AM = Backup;
 250     break;
 251   }
 252   }
 253
 254   // Is the base register already occupied?
 255   if (AM.BaseType != X86ISelAddressMode::RegBase || AM.Base.Reg.Val) {
 256     // If so, check to see if the scale index register is set.
 257     if (AM.IndexReg.Val == 0) {
 258       AM.IndexReg = N;
 259       AM.Scale = 1;
 260       return false;
 261     }
 262
 263     // Otherwise, we cannot select it.
 264     return true;
 265   }
 266
 267   // Default, generate it as a register.
 268   AM.BaseType = X86ISelAddressMode::RegBase;
 269   AM.Base.Reg = N;
 270   return false;
 271 }
 272
 273 /// SelectAddr - returns true if it is able pattern match an addressing mode.
 274 /// It returns the operands which make up the maximal addressing mode it can
 275 /// match by reference.
 276 bool X86DAGToDAGISel::SelectAddr(SDOperand N, SDOperand &Base, SDOperand &Scale,
 277                                  SDOperand &Index, SDOperand &Disp) {
 278   X86ISelAddressMode AM;
 279   if (!MatchAddress(N, AM)) {
 280     if (AM.BaseType == X86ISelAddressMode::RegBase) {
 281       if (AM.Base.Reg.Val)
 282         AM.Base.Reg = Select(AM.Base.Reg);
 283       else
 284         AM.Base.Reg = CurDAG->getRegister(0, MVT::i32);
 285     }
 286     if (AM.IndexReg.Val)
 287       AM.IndexReg = Select(AM.IndexReg);
 288     else
 289       AM.IndexReg = CurDAG->getRegister(0, MVT::i32);
 290
 291     getAddressOperands(AM, Base, Scale, Index, Disp);
 292     return true;
 293   }
 294   return false;
 295 }
 296
 297 static bool isRegister0(SDOperand Op)
 298 {
 299   if (RegisterSDNode *R = dyn_cast<RegisterSDNode>(Op))
 300     return (R->getReg() == 0);
 301   return false;
 302 }
 303
 304 /// SelectLEAAddr - it calls SelectAddr and determines if the maximal addressing
 305 /// mode it matches can be cost effectively emitted as an LEA instruction.
 306 /// For X86, it always is unless it's just a (Reg + const).
 307 bool X86DAGToDAGISel::SelectLEAAddr(SDOperand N, SDOperand &Base, SDOperand &Scale,
 308                                     SDOperand &Index, SDOperand &Disp) {
 309   X86ISelAddressMode AM;
 310   if (!MatchAddress(N, AM)) {
 311     bool SelectBase  = false;
 312     bool SelectIndex = false;
 313     bool Check       = false;
 314     if (AM.BaseType == X86ISelAddressMode::RegBase) {
 315       if (AM.Base.Reg.Val) {
 316         Check      = true;
 317         SelectBase = true;
 318       } else {
 319         AM.Base.Reg = CurDAG->getRegister(0, MVT::i32);
 320       }
 321     }
 322
 323     if (AM.IndexReg.Val) {
 324       SelectIndex = true;
 325     } else {
 326       AM.IndexReg = CurDAG->getRegister(0, MVT::i32);
 327     }
 328
 329     if (Check) {
 330       unsigned Complexity = 0;
 331       if (AM.Scale > 1)
 332         Complexity++;
 333       if (SelectIndex)
 334         Complexity++;
 335       if (AM.GV)
 336         Complexity++;
 337       else if (AM.Disp > 1)
 338         Complexity++;
 339       if (Complexity <= 1)
 340         return false;
 341     }
 342
 343     if (SelectBase)
 344       AM.Base.Reg = Select(AM.Base.Reg);
 345     if (SelectIndex)
 346       AM.IndexReg = Select(AM.IndexReg);
 347
 348     getAddressOperands(AM, Base, Scale, Index, Disp);
 349     return true;
 350   }
 351   return false;
 352 }
 353
 354 SDOperand X86DAGToDAGISel::Select(SDOperand N) {
 355   SDNode *Node = N.Val;
 356   MVT::ValueType NVT = Node->getValueType(0);
 357   unsigned Opc;
 358
 359   if (Node->getOpcode() >= ISD::BUILTIN_OP_END &&
 360       Node->getOpcode() < X86ISD::FIRST_NUMBER)
 361     return N;   // Already selected.
 362
 363   switch (Node->getOpcode()) {
 364     default: break;
 365
 366     case ISD::SHL:
 367       if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Node->getOperand(1))) {
 368         if (CN->getValue() == 1) {
 369           // X = SHL Y, 1  -> X = ADD Y, Y
 370           switch (NVT) {
 371             default: assert(0 && "Cannot shift this type!");
 372             case MVT::i8:  Opc = X86::ADD8rr; break;
 373             case MVT::i16: Opc = X86::ADD16rr; break;
 374             case MVT::i32: Opc = X86::ADD32rr; break;
 375           }
 376           SDOperand Tmp0 = Select(Node->getOperand(0));
 377           if (Node->hasOneUse())
 378             return CurDAG->SelectNodeTo(Node, Opc, NVT, Tmp0, Tmp0);
 379           else
 380             return CodeGenMap[N] =
 381               CurDAG->getTargetNode(Opc, NVT, Tmp0, Tmp0);
 382         }
 383       }
 384       break;
 385
 386     case ISD::TRUNCATE: {
 387       unsigned Reg;
 388       MVT::ValueType VT;
 389       switch (Node->getOperand(0).getValueType()) {
 390         default: assert(0 && "Unknown truncate!");
 391         case MVT::i16: Reg = X86::AX;  Opc = X86::MOV16rr; VT = MVT::i16; break;
 392         case MVT::i32: Reg = X86::EAX; Opc = X86::MOV32rr; VT = MVT::i32; break;
 393       }
 394       SDOperand Tmp0 = Select(Node->getOperand(0));
 395       SDOperand Tmp1 = CurDAG->getTargetNode(Opc, VT, Tmp0);
 396       SDOperand InFlag = SDOperand(0,0);
 397       SDOperand Result = CurDAG->getCopyToReg(CurDAG->getEntryNode(),
 398                                               Reg, Tmp1, InFlag).getValue(1);
 399       SDOperand Chain = Result.getValue(0);
 400       InFlag = Result.getValue(1);
 401
 402       switch (NVT) {
 403         default: assert(0 && "Unknown truncate!");
 404         case MVT::i8:  Reg = X86::AL;  Opc = X86::MOV8rr;  VT = MVT::i8;  break;
 405         case MVT::i16: Reg = X86::AX;  Opc = X86::MOV16rr; VT = MVT::i16; break;
 406       }
 407
 408       Result = CurDAG->getCopyFromReg(Chain,
 409                                       Reg, VT, InFlag);
 410       return CodeGenMap[N] = CurDAG->getTargetNode(Opc, VT, Result);
 411       break;
 412     }
 413   }
 414
 415   return SelectCode(N);
 416 }
 417
 418 /// createX86ISelDag - This pass converts a legalized DAG into a
 419 /// X86-specific DAG, ready for instruction scheduling.
 420 ///
 421 FunctionPass *llvm::createX86ISelDag(TargetMachine &TM) {
 422   return new X86DAGToDAGISel(TM);
 423 }