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     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.
 139 void 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
 155 bool 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.
 278 bool 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
 299 bool 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
 308 static 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).
 317 bool 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
 364 SDOperand 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 ///
 476 FunctionPass *llvm::createX86ISelDag(TargetMachine &TM) {
 477   return new X86DAGToDAGISel(TM);
 478 }