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     } BaseType;
  40
  41     struct {            // This is really a union, discriminated by BaseType!
  42       SDOperand Reg;
  43       int FrameIndex;
  44     } Base;
  45
  46     unsigned Scale;
  47     SDOperand IndexReg;
  48     unsigned Disp;
  49     GlobalValue *GV;
  50
  51     X86ISelAddressMode()
  52       : BaseType(RegBase), Scale(1), IndexReg(), Disp(0), GV(0) {
  53     }
  54   };
  55 }
  56
  57 namespace {
  58   Statistic<>
  59   NumFPKill("x86-codegen", "Number of FP_REG_KILL instructions added");
  60
  61   //===--------------------------------------------------------------------===//
  62   /// ISel - X86 specific code to select X86 machine instructions for
  63   /// SelectionDAG operations.
  64   ///
  65   class X86DAGToDAGISel : public SelectionDAGISel {
  66     /// ContainsFPCode - Every instruction we select that uses or defines a FP
  67     /// register should set this to true.
  68     bool ContainsFPCode;
  69
  70     /// X86Lowering - This object fully describes how to lower LLVM code to an
  71     /// X86-specific SelectionDAG.
  72     X86TargetLowering X86Lowering;
  73
  74     /// Subtarget - Keep a pointer to the X86Subtarget around so that we can
  75     /// make the right decision when generating code for different targets.
  76     const X86Subtarget *Subtarget;
  77   public:
  78     X86DAGToDAGISel(TargetMachine &TM)
  79       : SelectionDAGISel(X86Lowering), X86Lowering(TM) {
  80       Subtarget = &TM.getSubtarget<X86Subtarget>();
  81     }
  82
  83     virtual const char *getPassName() const {
  84       return "X86 DAG->DAG Instruction Selection";
  85     }
  86
  87     /// InstructionSelectBasicBlock - This callback is invoked by
  88     /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
  89     virtual void InstructionSelectBasicBlock(SelectionDAG &DAG);
  90
  91 // Include the pieces autogenerated from the target description.
  92 #include "X86GenDAGISel.inc"
  93
  94   private:
  95     SDOperand Select(SDOperand N);
  96
  97     void SelectAddress(SDOperand N, X86ISelAddressMode &AM);
  98     bool MatchAddress(SDOperand N, X86ISelAddressMode &AM);
  99
 100     /// getI8Imm - Return a target constant with the specified value, of type
 101     /// i8.
 102     inline SDOperand getI8Imm(unsigned Imm) {
 103       return CurDAG->getTargetConstant(Imm, MVT::i8);
 104     }
 105
 106     /// getI16Imm - Return a target constant with the specified value, of type
 107     /// i16.
 108     inline SDOperand getI16Imm(unsigned Imm) {
 109       return CurDAG->getTargetConstant(Imm, MVT::i16);
 110     }
 111
 112     /// getI32Imm - Return a target constant with the specified value, of type
 113     /// i32.
 114     inline SDOperand getI32Imm(unsigned Imm) {
 115       return CurDAG->getTargetConstant(Imm, MVT::i32);
 116     }
 117   };
 118 }
 119
 120 /// InstructionSelectBasicBlock - This callback is invoked by SelectionDAGISel
 121 /// when it has created a SelectionDAG for us to codegen.
 122 void X86DAGToDAGISel::InstructionSelectBasicBlock(SelectionDAG &DAG) {
 123   DEBUG(BB->dump());
 124
 125   // Codegen the basic block.
 126   DAG.setRoot(Select(DAG.getRoot()));
 127   DAG.RemoveDeadNodes();
 128
 129   // Emit machine code to BB.
 130   ScheduleAndEmitDAG(DAG);
 131 }
 132
 133 /// SelectAddress - Pattern match the maximal addressing mode for this node.
 134 void X86DAGToDAGISel::SelectAddress(SDOperand N, X86ISelAddressMode &AM) {
 135   MatchAddress(N, AM);
 136
 137   if (AM.BaseType == X86ISelAddressMode::RegBase && !AM.Base.Reg.Val) {
 138     AM.Base.Reg = CurDAG->getRegister(0, MVT::i32);
 139   } else {
 140     AM.Base.Reg = Select(AM.Base.Reg);
 141   }
 142   if (!AM.IndexReg.Val) {
 143     AM.IndexReg = CurDAG->getRegister(0, MVT::i32);
 144   } else {
 145     AM.IndexReg = Select(AM.IndexReg);
 146   }
 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   case ISD::GlobalAddress:
 164     if (AM.GV == 0) {
 165       GlobalValue *GV = cast<GlobalAddressSDNode>(N)->getGlobal();
 166       // For Darwin, external and weak symbols are indirect, so we want to load
 167       // the value at address GV, not the value of GV itself.  This means that
 168       // the GlobalAddress must be in the base or index register of the address,
 169       // not the GV offset field.
 170       if (Subtarget->getIndirectExternAndWeakGlobals() &&
 171           (GV->hasWeakLinkage() || GV->isExternal())) {
 172         break;
 173       } else {
 174         AM.GV = GV;
 175         return false;
 176       }
 177     }
 178     break;
 179   case ISD::Constant:
 180     AM.Disp += cast<ConstantSDNode>(N)->getValue();
 181     return false;
 182   case ISD::SHL:
 183     if (AM.IndexReg.Val == 0 && AM.Scale == 1)
 184       if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(1))) {
 185         unsigned Val = CN->getValue();
 186         if (Val == 1 || Val == 2 || Val == 3) {
 187           AM.Scale = 1 << Val;
 188           SDOperand ShVal = N.Val->getOperand(0);
 189
 190           // Okay, we know that we have a scale by now.  However, if the scaled
 191           // value is an add of something and a constant, we can fold the
 192           // constant into the disp field here.
 193           if (ShVal.Val->getOpcode() == ISD::ADD && ShVal.hasOneUse() &&
 194               isa<ConstantSDNode>(ShVal.Val->getOperand(1))) {
 195             AM.IndexReg = ShVal.Val->getOperand(0);
 196             ConstantSDNode *AddVal =
 197               cast<ConstantSDNode>(ShVal.Val->getOperand(1));
 198             AM.Disp += AddVal->getValue() << Val;
 199           } else {
 200             AM.IndexReg = ShVal;
 201           }
 202           return false;
 203         }
 204       }
 205     break;
 206   case ISD::MUL:
 207     // X*[3,5,9] -> X+X*[2,4,8]
 208     if (AM.IndexReg.Val == 0 && AM.BaseType == X86ISelAddressMode::RegBase &&
 209         AM.Base.Reg.Val == 0)
 210       if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.Val->getOperand(1)))
 211         if (CN->getValue() == 3 || CN->getValue() == 5 || CN->getValue() == 9) {
 212           AM.Scale = unsigned(CN->getValue())-1;
 213
 214           SDOperand MulVal = N.Val->getOperand(0);
 215           SDOperand Reg;
 216
 217           // Okay, we know that we have a scale by now.  However, if the scaled
 218           // value is an add of something and a constant, we can fold the
 219           // constant into the disp field here.
 220           if (MulVal.Val->getOpcode() == ISD::ADD && MulVal.hasOneUse() &&
 221               isa<ConstantSDNode>(MulVal.Val->getOperand(1))) {
 222             Reg = MulVal.Val->getOperand(0);
 223             ConstantSDNode *AddVal =
 224               cast<ConstantSDNode>(MulVal.Val->getOperand(1));
 225             AM.Disp += AddVal->getValue() * CN->getValue();
 226           } else {
 227             Reg = N.Val->getOperand(0);
 228           }
 229
 230           AM.IndexReg = AM.Base.Reg = Reg;
 231           return false;
 232         }
 233     break;
 234
 235   case ISD::ADD: {
 236     X86ISelAddressMode Backup = AM;
 237     if (!MatchAddress(N.Val->getOperand(0), AM) &&
 238         !MatchAddress(N.Val->getOperand(1), AM))
 239       return false;
 240     AM = Backup;
 241     if (!MatchAddress(N.Val->getOperand(1), AM) &&
 242         !MatchAddress(N.Val->getOperand(0), AM))
 243       return false;
 244     AM = Backup;
 245     break;
 246   }
 247   }
 248
 249   // Is the base register already occupied?
 250   if (AM.BaseType != X86ISelAddressMode::RegBase || AM.Base.Reg.Val) {
 251     // If so, check to see if the scale index register is set.
 252     if (AM.IndexReg.Val == 0) {
 253       AM.IndexReg = N;
 254       AM.Scale = 1;
 255       return false;
 256     }
 257
 258     // Otherwise, we cannot select it.
 259     return true;
 260   }
 261
 262   // Default, generate it as a register.
 263   AM.BaseType = X86ISelAddressMode::RegBase;
 264   AM.Base.Reg = N;
 265   return false;
 266 }
 267
 268 SDOperand X86DAGToDAGISel::Select(SDOperand Op) {
 269   SDNode *N = Op.Val;
 270   MVT::ValueType OpVT = N->getValueType(0);
 271   unsigned Opc;
 272
 273   if (N->getOpcode() >= ISD::BUILTIN_OP_END)
 274     return Op;   // Already selected.
 275
 276   switch (N->getOpcode()) {
 277     default: break;
 278
 279     case ISD::SHL:
 280     case ISD::SRL:
 281     case ISD::SRA:
 282       if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N->getOperand(1))) {
 283         if (N->getOpcode() == ISD::SHL && CN->getValue() == 1) {
 284           // X = SHL Y, 1  -> X = ADD Y, Y
 285           switch (OpVT) {
 286             default: assert(0 && "Cannot shift this type!");
 287             case MVT::i8:  Opc = X86::ADD8rr; break;
 288             case MVT::i16: Opc = X86::ADD16rr; break;
 289             case MVT::i32: Opc = X86::ADD32rr; break;
 290           }
 291           SDOperand Tmp0 = Select(N->getOperand(0));
 292           CurDAG->SelectNodeTo(N, Opc, MVT::i32, Tmp0, Tmp0);
 293           return SDOperand(N, 0);
 294         }
 295       } else {
 296         static const unsigned SHLTab[] = {
 297           X86::SHL8rCL, X86::SHL16rCL, X86::SHL32rCL
 298         };
 299         static const unsigned SRLTab[] = {
 300           X86::SHR8rCL, X86::SHR16rCL, X86::SHR32rCL
 301         };
 302         static const unsigned SRATab[] = {
 303           X86::SAR8rCL, X86::SAR16rCL, X86::SAR32rCL
 304         };
 305
 306         switch (OpVT) {
 307           default: assert(0 && "Cannot shift this type!");
 308           case MVT::i1:
 309           case MVT::i8:  Opc = 0; break;
 310           case MVT::i16: Opc = 1; break;
 311           case MVT::i32: Opc = 2; break;
 312         }
 313
 314         switch (N->getOpcode()) {
 315           default: assert(0 && "Unreachable!");
 316           case ISD::SHL: Opc = SHLTab[Opc]; break;
 317           case ISD::SRL: Opc = SRLTab[Opc]; break;
 318           case ISD::SRA: Opc = SRATab[Opc]; break;
 319         }
 320
 321         SDOperand Tmp0 = Select(N->getOperand(0));
 322         CurDAG->SelectNodeTo(N, Opc, MVT::i32, Tmp0);
 323         return SDOperand(N, 0);
 324       }
 325       break;
 326
 327     case ISD::RET: {
 328       SDOperand Chain = Select(N->getOperand(0));     // Token chain.
 329       switch (N->getNumOperands()) {
 330         default:
 331           assert(0 && "Unknown return instruction!");
 332         case 3:
 333           assert(0 && "Not yet handled return instruction!");
 334           break;
 335         case 2: {
 336           SDOperand Val = Select(N->getOperand(1));
 337           switch (N->getOperand(1).getValueType()) {
 338             default:
 339               assert(0 && "All other types should have been promoted!!");
 340             case MVT::i32:
 341               Chain = CurDAG->getCopyToReg(Chain, X86::EAX, Val);
 342               break;
 343             case MVT::f32:
 344             case MVT::f64:
 345               assert(0 && "Not yet handled return instruction!");
 346               break;
 347           }
 348         }
 349         case 1:
 350           break;
 351       }
 352       if (X86Lowering.getBytesToPopOnReturn() == 0)
 353         CurDAG->SelectNodeTo(N, X86::RET, MVT::Other, Chain);
 354       else
 355         CurDAG->SelectNodeTo(N, X86::RET, MVT::Other,
 356                              getI16Imm(X86Lowering.getBytesToPopOnReturn()),
 357                              Chain);
 358
 359       return SDOperand(N, 0);
 360     }
 361
 362     case ISD::LOAD: {
 363       switch (OpVT) {
 364         default: assert(0 && "Cannot load this type!");
 365         case MVT::i1:
 366         case MVT::i8:  Opc = X86::MOV8rm; break;
 367         case MVT::i16: Opc = X86::MOV16rm; break;
 368         case MVT::i32: Opc = X86::MOV32rm; break;
 369         case MVT::f32: Opc = X86::MOVSSrm; break;
 370         case MVT::f64: Opc = X86::FLD64m; ContainsFPCode = true; break;
 371       }
 372
 373       if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(N->getOperand(1))){
 374         unsigned CPIdx = BB->getParent()->getConstantPool()->
 375           getConstantPoolIndex(CP->get());
 376         // ???
 377         assert(0 && "Can't handle load from constant pool!");
 378       } else {
 379         X86ISelAddressMode AM;
 380         SDOperand Chain = Select(N->getOperand(0));     // Token chain.
 381
 382         SelectAddress(N->getOperand(1), AM);
 383         SDOperand Scale = getI8Imm (AM.Scale);
 384         SDOperand Disp  = AM.GV
 385           ? CurDAG->getTargetGlobalAddress(AM.GV, MVT::i32, AM.Disp)
 386           : getI32Imm(AM.Disp);
 387         if (AM.BaseType == X86ISelAddressMode::RegBase) {
 388           CurDAG->SelectNodeTo(N, Opc, OpVT, MVT::Other,
 389                                AM.Base.Reg, Scale, AM.IndexReg, Disp, Chain);
 390         } else {
 391           SDOperand Base = CurDAG->getFrameIndex(AM.Base.FrameIndex, MVT::i32);
 392           CurDAG->SelectNodeTo(N, Opc, OpVT, MVT::Other,
 393                                Base, Scale, AM.IndexReg, Disp, Chain);
 394         }
 395       }
 396       return SDOperand(N, Op.ResNo);
 397     }
 398
 399     case ISD::STORE: {
 400       SDOperand Chain = Select(N->getOperand(0));     // Token chain.
 401       SDOperand Tmp1 = Select(N->getOperand(1));
 402       X86ISelAddressMode AM;
 403       SelectAddress(N->getOperand(2), AM);
 404
 405       Opc = 0;
 406       if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N->getOperand(1))) {
 407         switch (CN->getValueType(0)) {
 408           default: assert(0 && "Invalid type for operation!");
 409           case MVT::i1:
 410           case MVT::i8:  Opc = X86::MOV8mi;  break;
 411           case MVT::i16: Opc = X86::MOV16mi; break;
 412           case MVT::i32: Opc = X86::MOV32mi; break;
 413         }
 414       }
 415
 416       if (!Opc) {
 417         switch (N->getOperand(1).getValueType()) {
 418           default: assert(0 && "Cannot store this type!");
 419           case MVT::i1:
 420           case MVT::i8:  Opc = X86::MOV8mr;  break;
 421           case MVT::i16: Opc = X86::MOV16mr; break;
 422           case MVT::i32: Opc = X86::MOV32mr; break;
 423           case MVT::f32: Opc = X86::MOVSSmr; break;
 424           case MVT::f64: Opc = X86::FST64m;  break;
 425         }
 426       }
 427
 428       SDOperand Scale = getI8Imm (AM.Scale);
 429       SDOperand Disp  = AM.GV
 430         ? CurDAG->getTargetGlobalAddress(AM.GV, MVT::i32, AM.Disp)
 431         : getI32Imm(AM.Disp);
 432       if (AM.BaseType == X86ISelAddressMode::RegBase) {
 433         CurDAG->SelectNodeTo(N, Opc, MVT::Other,
 434                              AM.Base.Reg, Scale, AM.IndexReg, Disp, Tmp1,
 435                              Chain);
 436       } else {
 437         SDOperand Base = CurDAG->getFrameIndex(AM.Base.FrameIndex, MVT::i32);
 438         CurDAG->SelectNodeTo(N, Opc, MVT::Other,
 439                              Base, Scale, AM.IndexReg, Disp, Tmp1, Chain);
 440       }
 441     }
 442   }
 443
 444   return SelectCode(Op);
 445 }
 446
 447 /// createX86ISelDag - This pass converts a legalized DAG into a
 448 /// X86-specific DAG, ready for instruction scheduling.
 449 ///
 450 FunctionPass *llvm::createX86ISelDag(TargetMachine &TM) {
 451   return new X86DAGToDAGISel(TM);
 452 }