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