lib/Target/SystemZ/SystemZISelDAGToDAG.cpp

   1 //==-- SystemZISelDAGToDAG.cpp - A dag to dag inst selector for SystemZ ---===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines an instruction selector for the SystemZ target.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "SystemZ.h"
  15 #include "SystemZISelLowering.h"
  16 #include "SystemZTargetMachine.h"
  17 #include "llvm/DerivedTypes.h"
  18 #include "llvm/Function.h"
  19 #include "llvm/Intrinsics.h"
  20 #include "llvm/CallingConv.h"
  21 #include "llvm/Constants.h"
  22 #include "llvm/CodeGen/MachineFrameInfo.h"
  23 #include "llvm/CodeGen/MachineFunction.h"
  24 #include "llvm/CodeGen/MachineInstrBuilder.h"
  25 #include "llvm/CodeGen/MachineRegisterInfo.h"
  26 #include "llvm/CodeGen/SelectionDAG.h"
  27 #include "llvm/CodeGen/SelectionDAGISel.h"
  28 #include "llvm/Target/TargetLowering.h"
  29 #include "llvm/Support/Compiler.h"
  30 #include "llvm/Support/Debug.h"
  31 using namespace llvm;
  32
  33 namespace {
  34   /// SystemZRRIAddressMode - This corresponds to rriaddr, but uses SDValue's
  35   /// instead of register numbers for the leaves of the matched tree.
  36   struct SystemZRRIAddressMode {
  37     enum {
  38       RegBase,
  39       FrameIndexBase
  40     } BaseType;
  41
  42     struct {            // This is really a union, discriminated by BaseType!
  43       SDValue Reg;
  44       int FrameIndex;
  45     } Base;
  46
  47     SDValue IndexReg;
  48     int32_t Disp;
  49
  50     SystemZRRIAddressMode()
  51       : BaseType(RegBase), IndexReg(), Disp(0) {
  52     }
  53
  54     void dump() {
  55       cerr << "SystemZRRIAddressMode " << this << "\n";
  56       if (BaseType == RegBase) {
  57         cerr << "Base.Reg ";
  58         if (Base.Reg.getNode() != 0) Base.Reg.getNode()->dump();
  59         else cerr << "nul";
  60       } else {
  61         cerr << " Base.FrameIndex " << Base.FrameIndex << "\n";
  62       }
  63       cerr << "IndexReg ";
  64       if (IndexReg.getNode() != 0) IndexReg.getNode()->dump();
  65       else cerr << "nul";
  66       cerr << " Disp " << Disp << "\n";
  67     }
  68   };
  69 }
  70
  71 /// SystemZDAGToDAGISel - SystemZ specific code to select SystemZ machine
  72 /// instructions for SelectionDAG operations.
  73 ///
  74 namespace {
  75   class SystemZDAGToDAGISel : public SelectionDAGISel {
  76     SystemZTargetLowering &Lowering;
  77     const SystemZSubtarget &Subtarget;
  78
  79   public:
  80     SystemZDAGToDAGISel(SystemZTargetMachine &TM, CodeGenOpt::Level OptLevel)
  81       : SelectionDAGISel(TM, OptLevel),
  82         Lowering(*TM.getTargetLowering()),
  83         Subtarget(*TM.getSubtargetImpl()) { }
  84
  85     virtual void InstructionSelect();
  86
  87     virtual const char *getPassName() const {
  88       return "SystemZ DAG->DAG Pattern Instruction Selection";
  89     }
  90
  91     /// getI16Imm - Return a target constant with the specified value, of type
  92     /// i16.
  93     inline SDValue getI16Imm(uint64_t Imm) {
  94       return CurDAG->getTargetConstant(Imm, MVT::i16);
  95     }
  96
  97     /// getI32Imm - Return a target constant with the specified value, of type
  98     /// i32.
  99     inline SDValue getI32Imm(uint64_t Imm) {
 100       return CurDAG->getTargetConstant(Imm, MVT::i32);
 101     }
 102
 103     // Include the pieces autogenerated from the target description.
 104     #include "SystemZGenDAGISel.inc"
 105
 106   private:
 107     bool SelectAddrRRI(SDValue Op, SDValue Addr,
 108                        SDValue &Base, SDValue &Index, SDValue &Disp);
 109     SDNode *Select(SDValue Op);
 110     bool SelectAddrRI(const SDValue& Op, SDValue& Addr,
 111                       SDValue &Base, SDValue &Disp);
 112     bool MatchAddress(SDValue N, SystemZRRIAddressMode &AM, unsigned Depth = 0);
 113     bool MatchAddressBase(SDValue N, SystemZRRIAddressMode &AM);
 114
 115   #ifndef NDEBUG
 116     unsigned Indent;
 117   #endif
 118   };
 119 }  // end anonymous namespace
 120
 121 /// createSystemZISelDag - This pass converts a legalized DAG into a
 122 /// SystemZ-specific DAG, ready for instruction scheduling.
 123 ///
 124 FunctionPass *llvm::createSystemZISelDag(SystemZTargetMachine &TM,
 125                                         CodeGenOpt::Level OptLevel) {
 126   return new SystemZDAGToDAGISel(TM, OptLevel);
 127 }
 128
 129 /// isImmSExt20 - This method tests to see if the node is either a 32-bit
 130 /// or 64-bit immediate, and if the value can be accurately represented as a
 131 /// sign extension from a 20-bit value. If so, this returns true and the
 132 /// immediate.
 133 static bool isImmSExt20(int64_t Val, int32_t &Imm) {
 134   if (Val >= -524288 && Val <= 524287) {
 135     Imm = (int32_t)Val;
 136     return true;
 137   }
 138   return false;
 139 }
 140
 141 static bool isImmSExt20(SDNode *N, int32_t &Imm) {
 142   if (N->getOpcode() != ISD::Constant)
 143     return false;
 144
 145   return isImmSExt20(cast<ConstantSDNode>(N)->getSExtValue(), Imm);
 146 }
 147
 148 static bool isImmSExt20(SDValue Op, int32_t &Imm) {
 149   return isImmSExt20(Op.getNode(), Imm);
 150 }
 151
 152 /// Returns true if the address can be represented by a base register plus
 153 /// a signed 20-bit displacement [r+imm].
 154 bool SystemZDAGToDAGISel::SelectAddrRI(const SDValue& Op, SDValue& Addr,
 155                                        SDValue &Base, SDValue &Disp) {
 156   // FIXME dl should come from parent load or store, not from address
 157   DebugLoc dl = Addr.getDebugLoc();
 158   MVT VT = Addr.getValueType();
 159
 160   if (Addr.getOpcode() == ISD::ADD) {
 161     int32_t Imm = 0;
 162     if (isImmSExt20(Addr.getOperand(1), Imm)) {
 163       Disp = CurDAG->getTargetConstant(Imm, MVT::i32);
 164       if (FrameIndexSDNode *FI =
 165           dyn_cast<FrameIndexSDNode>(Addr.getOperand(0))) {
 166         Base = CurDAG->getTargetFrameIndex(FI->getIndex(), VT);
 167       } else {
 168         Base = Addr.getOperand(0);
 169       }
 170       return true; // [r+i]
 171     }
 172   } else if (Addr.getOpcode() == ISD::OR) {
 173     int32_t Imm = 0;
 174     if (isImmSExt20(Addr.getOperand(1), Imm)) {
 175       // If this is an or of disjoint bitfields, we can codegen this as an add
 176       // (for better address arithmetic) if the LHS and RHS of the OR are
 177       // provably disjoint.
 178       APInt LHSKnownZero, LHSKnownOne;
 179       CurDAG->ComputeMaskedBits(Addr.getOperand(0),
 180                                 APInt::getAllOnesValue(Addr.getOperand(0)
 181                                                        .getValueSizeInBits()),
 182                                 LHSKnownZero, LHSKnownOne);
 183
 184       if ((LHSKnownZero.getZExtValue()|~(uint64_t)Imm) == ~0ULL) {
 185         // If all of the bits are known zero on the LHS or RHS, the add won't
 186         // carry.
 187         Base = Addr.getOperand(0);
 188         Disp = CurDAG->getTargetConstant(Imm, MVT::i32);
 189         return true;
 190       }
 191     }
 192   } else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Addr)) {
 193     // Loading from a constant address.
 194
 195     // If this address fits entirely in a 20-bit sext immediate field, codegen
 196     // this as "d(r0)"
 197     int32_t Imm;
 198     if (isImmSExt20(CN, Imm)) {
 199       Disp = CurDAG->getTargetConstant(Imm, MVT::i32);
 200       Base = CurDAG->getRegister(0, VT);
 201       return true;
 202     }
 203   }
 204
 205   Disp = CurDAG->getTargetConstant(0, MVT::i32);
 206   if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Addr))
 207     Base = CurDAG->getTargetFrameIndex(FI->getIndex(), VT);
 208   else
 209     Base = Addr;
 210   return true;      // [r+0]
 211 }
 212
 213 /// MatchAddress - Add the specified node to the specified addressing mode,
 214 /// returning true if it cannot be done.  This just pattern matches for the
 215 /// addressing mode.
 216 bool SystemZDAGToDAGISel::MatchAddress(SDValue N, SystemZRRIAddressMode &AM,
 217                                        unsigned Depth) {
 218   DebugLoc dl = N.getDebugLoc();
 219   DOUT << "MatchAddress: "; DEBUG(AM.dump());
 220   // Limit recursion.
 221   if (Depth > 5)
 222     return MatchAddressBase(N, AM);
 223
 224   // FIXME: We can perform better here. If we have something like
 225   // (shift (add A, imm), N), we can try to reassociate stuff and fold shift of
 226   // imm into addressing mode.
 227   switch (N.getOpcode()) {
 228   default: break;
 229   case ISD::Constant: {
 230     uint64_t Val = cast<ConstantSDNode>(N)->getSExtValue();
 231     int32_t Imm;
 232     if (isImmSExt20(AM.Disp + Val, Imm)) {
 233       AM.Disp = Imm;
 234       return false;
 235     }
 236     break;
 237   }
 238
 239   case ISD::FrameIndex:
 240     if (AM.BaseType == SystemZRRIAddressMode::RegBase
 241         && AM.Base.Reg.getNode() == 0) {
 242       AM.BaseType = SystemZRRIAddressMode::FrameIndexBase;
 243       AM.Base.FrameIndex = cast<FrameIndexSDNode>(N)->getIndex();
 244       return false;
 245     }
 246     break;
 247
 248   case ISD::SUB: {
 249     // Given A-B, if A can be completely folded into the address and
 250     // the index field with the index field unused, use -B as the index.
 251     // This is a win if a has multiple parts that can be folded into
 252     // the address. Also, this saves a mov if the base register has
 253     // other uses, since it avoids a two-address sub instruction, however
 254     // it costs an additional mov if the index register has other uses.
 255
 256     // Test if the LHS of the sub can be folded.
 257     SystemZRRIAddressMode Backup = AM;
 258     if (MatchAddress(N.getNode()->getOperand(0), AM, Depth+1)) {
 259       AM = Backup;
 260       break;
 261     }
 262     // Test if the index field is free for use.
 263     if (AM.IndexReg.getNode()) {
 264       AM = Backup;
 265       break;
 266     }
 267
 268     // If the base is a register with multiple uses, this transformation may
 269     // save a mov. Otherwise it's probably better not to do it.
 270     if (AM.BaseType == SystemZRRIAddressMode::RegBase &&
 271         (!AM.Base.Reg.getNode() || AM.Base.Reg.getNode()->hasOneUse())) {
 272       AM = Backup;
 273       break;
 274     }
 275
 276     // Ok, the transformation is legal and appears profitable. Go for it.
 277     SDValue RHS = N.getNode()->getOperand(1);
 278     SDValue Zero = CurDAG->getConstant(0, N.getValueType());
 279     SDValue Neg = CurDAG->getNode(ISD::SUB, dl, N.getValueType(), Zero, RHS);
 280     AM.IndexReg = Neg;
 281
 282     // Insert the new nodes into the topological ordering.
 283     if (Zero.getNode()->getNodeId() == -1 ||
 284         Zero.getNode()->getNodeId() > N.getNode()->getNodeId()) {
 285       CurDAG->RepositionNode(N.getNode(), Zero.getNode());
 286       Zero.getNode()->setNodeId(N.getNode()->getNodeId());
 287     }
 288     if (Neg.getNode()->getNodeId() == -1 ||
 289         Neg.getNode()->getNodeId() > N.getNode()->getNodeId()) {
 290       CurDAG->RepositionNode(N.getNode(), Neg.getNode());
 291       Neg.getNode()->setNodeId(N.getNode()->getNodeId());
 292     }
 293     return false;
 294   }
 295
 296   case ISD::ADD: {
 297     SystemZRRIAddressMode Backup = AM;
 298     if (!MatchAddress(N.getNode()->getOperand(0), AM, Depth+1) &&
 299         !MatchAddress(N.getNode()->getOperand(1), AM, Depth+1))
 300       return false;
 301     AM = Backup;
 302     if (!MatchAddress(N.getNode()->getOperand(1), AM, Depth+1) &&
 303         !MatchAddress(N.getNode()->getOperand(0), AM, Depth+1))
 304       return false;
 305     AM = Backup;
 306
 307     // If we couldn't fold both operands into the address at the same time,
 308     // see if we can just put each operand into a register and fold at least
 309     // the add.
 310     if (AM.BaseType == SystemZRRIAddressMode::RegBase &&
 311         !AM.Base.Reg.getNode() && !AM.IndexReg.getNode()) {
 312       AM.Base.Reg = N.getNode()->getOperand(0);
 313       AM.IndexReg = N.getNode()->getOperand(1);
 314       return false;
 315     }
 316     break;
 317   }
 318
 319   case ISD::OR:
 320     // Handle "X | C" as "X + C" iff X is known to have C bits clear.
 321     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
 322       SystemZRRIAddressMode Backup = AM;
 323       uint64_t Offset = CN->getSExtValue();
 324       int32_t Imm;
 325       // Start with the LHS as an addr mode.
 326       if (!MatchAddress(N.getOperand(0), AM, Depth+1) &&
 327           // The resultant disp must fit in 20-bits.
 328           isImmSExt20(AM.Disp + Offset, Imm) &&
 329           // Check to see if the LHS & C is zero.
 330           CurDAG->MaskedValueIsZero(N.getOperand(0), CN->getAPIntValue())) {
 331         AM.Disp = Imm;
 332         return false;
 333       }
 334       AM = Backup;
 335     }
 336     break;
 337   }
 338
 339   return MatchAddressBase(N, AM);
 340 }
 341
 342 /// MatchAddressBase - Helper for MatchAddress. Add the specified node to the
 343 /// specified addressing mode without any further recursion.
 344 bool SystemZDAGToDAGISel::MatchAddressBase(SDValue N,
 345                                            SystemZRRIAddressMode &AM) {
 346   // Is the base register already occupied?
 347   if (AM.BaseType != SystemZRRIAddressMode::RegBase || AM.Base.Reg.getNode()) {
 348     // If so, check to see if the scale index register is set.
 349     if (AM.IndexReg.getNode() == 0) {
 350       AM.IndexReg = N;
 351       return false;
 352     }
 353
 354     // Otherwise, we cannot select it.
 355     return true;
 356   }
 357
 358   // Default, generate it as a register.
 359   AM.BaseType = SystemZRRIAddressMode::RegBase;
 360   AM.Base.Reg = N;
 361   return false;
 362 }
 363
 364 /// Returns true if the address can be represented by a base register plus
 365 /// index register plus a signed 20-bit displacement [base + idx + imm].
 366 bool SystemZDAGToDAGISel::SelectAddrRRI(SDValue Op, SDValue Addr,
 367                                 SDValue &Base, SDValue &Index, SDValue &Disp) {
 368   SystemZRRIAddressMode AM;
 369   bool Done = false;
 370
 371   // FIXME: Should we better use lay instruction for non-single uses?
 372
 373   if (!Done && MatchAddress(Addr, AM))
 374     return false;
 375
 376   MVT VT = Addr.getValueType();
 377   if (AM.BaseType == SystemZRRIAddressMode::RegBase) {
 378     if (!AM.Base.Reg.getNode())
 379       AM.Base.Reg = CurDAG->getRegister(0, VT);
 380   }
 381
 382   if (!AM.IndexReg.getNode())
 383     AM.IndexReg = CurDAG->getRegister(0, VT);
 384
 385   if (AM.BaseType == SystemZRRIAddressMode::RegBase)
 386     Base = AM.Base.Reg;
 387   else
 388     Base = CurDAG->getTargetFrameIndex(AM.Base.FrameIndex, TLI.getPointerTy());
 389   Index = AM.IndexReg;
 390   Disp = Disp = CurDAG->getTargetConstant(AM.Disp, MVT::i32);
 391
 392   return true;
 393 }
 394
 395 /// InstructionSelect - This callback is invoked by
 396 /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
 397 void SystemZDAGToDAGISel::InstructionSelect() {
 398   DEBUG(BB->dump());
 399
 400   // Codegen the basic block.
 401 #ifndef NDEBUG
 402   DOUT << "===== Instruction selection begins:\n";
 403   Indent = 0;
 404 #endif
 405   SelectRoot(*CurDAG);
 406 #ifndef NDEBUG
 407   DOUT << "===== Instruction selection ends:\n";
 408 #endif
 409
 410   CurDAG->RemoveDeadNodes();
 411 }
 412
 413 SDNode *SystemZDAGToDAGISel::Select(SDValue Op) {
 414   SDNode *Node = Op.getNode();
 415   DebugLoc dl = Op.getDebugLoc();
 416
 417   // Dump information about the Node being selected
 418   #ifndef NDEBUG
 419   DOUT << std::string(Indent, ' ') << "Selecting: ";
 420   DEBUG(Node->dump(CurDAG));
 421   DOUT << "\n";
 422   Indent += 2;
 423   #endif
 424
 425   // If we have a custom node, we already have selected!
 426   if (Node->isMachineOpcode()) {
 427     #ifndef NDEBUG
 428     DOUT << std::string(Indent-2, ' ') << "== ";
 429     DEBUG(Node->dump(CurDAG));
 430     DOUT << "\n";
 431     Indent -= 2;
 432     #endif
 433     return NULL;
 434   }
 435
 436   // Select the default instruction
 437   SDNode *ResNode = SelectCode(Op);
 438
 439   #ifndef NDEBUG
 440   DOUT << std::string(Indent-2, ' ') << "=> ";
 441   if (ResNode == NULL || ResNode == Op.getNode())
 442     DEBUG(Op.getNode()->dump(CurDAG));
 443   else
 444     DEBUG(ResNode->dump(CurDAG));
 445   DOUT << "\n";
 446   Indent -= 2;
 447   #endif
 448
 449   return ResNode;
 450 }