1 //===-- SystemZISelDAGToDAG.cpp - A dag to dag inst selector for SystemZ --===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines an instruction selector for the SystemZ target.
12 //===----------------------------------------------------------------------===//
14 #include "SystemZTargetMachine.h"
15 #include "llvm/CodeGen/SelectionDAGISel.h"
16 #include "llvm/Support/Debug.h"
17 #include "llvm/Support/raw_ostream.h"
22 // Used to build addressing modes.
23 struct SystemZAddressingMode {
24 // The shape of the address.
29 // base+displacement+index for load and store operands
32 // base+displacement+index for load address operands
35 // base+displacement+index+ADJDYNALLOC
40 // The type of displacement. The enum names here correspond directly
41 // to the definitions in SystemZOperand.td. We could split them into
42 // flags -- single/pair, 128-bit, etc. -- but it hardly seems worth it.
52 // The parts of the address. The address is equivalent to:
54 // Base + Disp + Index + (IncludesDynAlloc ? ADJDYNALLOC : 0)
58 bool IncludesDynAlloc;
60 SystemZAddressingMode(AddrForm form, DispRange dr)
61 : Form(form), DR(dr), Base(), Disp(0), Index(),
62 IncludesDynAlloc(false) {}
64 // True if the address can have an index register.
65 bool hasIndexField() { return Form != FormBD; }
67 // True if the address can (and must) include ADJDYNALLOC.
68 bool isDynAlloc() { return Form == FormBDXDynAlloc; }
71 errs() << "SystemZAddressingMode " << this << '\n';
74 if (Base.getNode() != 0)
75 Base.getNode()->dump();
79 if (hasIndexField()) {
81 if (Index.getNode() != 0)
82 Index.getNode()->dump();
87 errs() << " Disp " << Disp;
89 errs() << " + ADJDYNALLOC";
94 class SystemZDAGToDAGISel : public SelectionDAGISel {
95 const SystemZTargetLowering &Lowering;
96 const SystemZSubtarget &Subtarget;
98 // Used by SystemZOperands.td to create integer constants.
99 inline SDValue getImm(const SDNode *Node, uint64_t Imm) {
100 return CurDAG->getTargetConstant(Imm, Node->getValueType(0));
103 // Try to fold more of the base or index of AM into AM, where IsBase
104 // selects between the base and index.
105 bool expandAddress(SystemZAddressingMode &AM, bool IsBase);
107 // Try to describe N in AM, returning true on success.
108 bool selectAddress(SDValue N, SystemZAddressingMode &AM);
110 // Extract individual target operands from matched address AM.
111 void getAddressOperands(const SystemZAddressingMode &AM, EVT VT,
112 SDValue &Base, SDValue &Disp);
113 void getAddressOperands(const SystemZAddressingMode &AM, EVT VT,
114 SDValue &Base, SDValue &Disp, SDValue &Index);
116 // Try to match Addr as a FormBD address with displacement type DR.
117 // Return true on success, storing the base and displacement in
118 // Base and Disp respectively.
119 bool selectBDAddr(SystemZAddressingMode::DispRange DR, SDValue Addr,
120 SDValue &Base, SDValue &Disp);
122 // Try to match Addr as a FormBDX* address of form Form with
123 // displacement type DR. Return true on success, storing the base,
124 // displacement and index in Base, Disp and Index respectively.
125 bool selectBDXAddr(SystemZAddressingMode::AddrForm Form,
126 SystemZAddressingMode::DispRange DR, SDValue Addr,
127 SDValue &Base, SDValue &Disp, SDValue &Index);
129 // PC-relative address matching routines used by SystemZOperands.td.
130 bool selectPCRelAddress(SDValue Addr, SDValue &Target) {
131 if (Addr.getOpcode() == SystemZISD::PCREL_WRAPPER) {
132 Target = Addr.getOperand(0);
138 // BD matching routines used by SystemZOperands.td.
139 bool selectBDAddr12Only(SDValue Addr, SDValue &Base, SDValue &Disp) {
140 return selectBDAddr(SystemZAddressingMode::Disp12Only, Addr, Base, Disp);
142 bool selectBDAddr12Pair(SDValue Addr, SDValue &Base, SDValue &Disp) {
143 return selectBDAddr(SystemZAddressingMode::Disp12Pair, Addr, Base, Disp);
145 bool selectBDAddr20Only(SDValue Addr, SDValue &Base, SDValue &Disp) {
146 return selectBDAddr(SystemZAddressingMode::Disp20Only, Addr, Base, Disp);
148 bool selectBDAddr20Pair(SDValue Addr, SDValue &Base, SDValue &Disp) {
149 return selectBDAddr(SystemZAddressingMode::Disp20Pair, Addr, Base, Disp);
152 // BDX matching routines used by SystemZOperands.td.
153 bool selectBDXAddr12Only(SDValue Addr, SDValue &Base, SDValue &Disp,
155 return selectBDXAddr(SystemZAddressingMode::FormBDXNormal,
156 SystemZAddressingMode::Disp12Only,
157 Addr, Base, Disp, Index);
159 bool selectBDXAddr12Pair(SDValue Addr, SDValue &Base, SDValue &Disp,
161 return selectBDXAddr(SystemZAddressingMode::FormBDXNormal,
162 SystemZAddressingMode::Disp12Pair,
163 Addr, Base, Disp, Index);
165 bool selectDynAlloc12Only(SDValue Addr, SDValue &Base, SDValue &Disp,
167 return selectBDXAddr(SystemZAddressingMode::FormBDXDynAlloc,
168 SystemZAddressingMode::Disp12Only,
169 Addr, Base, Disp, Index);
171 bool selectBDXAddr20Only(SDValue Addr, SDValue &Base, SDValue &Disp,
173 return selectBDXAddr(SystemZAddressingMode::FormBDXNormal,
174 SystemZAddressingMode::Disp20Only,
175 Addr, Base, Disp, Index);
177 bool selectBDXAddr20Only128(SDValue Addr, SDValue &Base, SDValue &Disp,
179 return selectBDXAddr(SystemZAddressingMode::FormBDXNormal,
180 SystemZAddressingMode::Disp20Only128,
181 Addr, Base, Disp, Index);
183 bool selectBDXAddr20Pair(SDValue Addr, SDValue &Base, SDValue &Disp,
185 return selectBDXAddr(SystemZAddressingMode::FormBDXNormal,
186 SystemZAddressingMode::Disp20Pair,
187 Addr, Base, Disp, Index);
189 bool selectLAAddr12Pair(SDValue Addr, SDValue &Base, SDValue &Disp,
191 return selectBDXAddr(SystemZAddressingMode::FormBDXLA,
192 SystemZAddressingMode::Disp12Pair,
193 Addr, Base, Disp, Index);
195 bool selectLAAddr20Pair(SDValue Addr, SDValue &Base, SDValue &Disp,
197 return selectBDXAddr(SystemZAddressingMode::FormBDXLA,
198 SystemZAddressingMode::Disp20Pair,
199 Addr, Base, Disp, Index);
202 // If Op0 is null, then Node is a constant that can be loaded using:
204 // (Opcode UpperVal LowerVal)
206 // If Op0 is nonnull, then Node can be implemented using:
208 // (Opcode (Opcode Op0 UpperVal) LowerVal)
209 SDNode *splitLargeImmediate(unsigned Opcode, SDNode *Node, SDValue Op0,
210 uint64_t UpperVal, uint64_t LowerVal);
213 SystemZDAGToDAGISel(SystemZTargetMachine &TM, CodeGenOpt::Level OptLevel)
214 : SelectionDAGISel(TM, OptLevel),
215 Lowering(*TM.getTargetLowering()),
216 Subtarget(*TM.getSubtargetImpl()) { }
218 // Override MachineFunctionPass.
219 virtual const char *getPassName() const LLVM_OVERRIDE {
220 return "SystemZ DAG->DAG Pattern Instruction Selection";
223 // Override SelectionDAGISel.
224 virtual SDNode *Select(SDNode *Node) LLVM_OVERRIDE;
225 virtual bool SelectInlineAsmMemoryOperand(const SDValue &Op,
227 std::vector<SDValue> &OutOps)
230 // Include the pieces autogenerated from the target description.
231 #include "SystemZGenDAGISel.inc"
233 } // end anonymous namespace
235 FunctionPass *llvm::createSystemZISelDag(SystemZTargetMachine &TM,
236 CodeGenOpt::Level OptLevel) {
237 return new SystemZDAGToDAGISel(TM, OptLevel);
240 // Return true if Val should be selected as a displacement for an address
241 // with range DR. Here we're interested in the range of both the instruction
242 // described by DR and of any pairing instruction.
243 static bool selectDisp(SystemZAddressingMode::DispRange DR, int64_t Val) {
245 case SystemZAddressingMode::Disp12Only:
246 return isUInt<12>(Val);
248 case SystemZAddressingMode::Disp12Pair:
249 case SystemZAddressingMode::Disp20Only:
250 case SystemZAddressingMode::Disp20Pair:
251 return isInt<20>(Val);
253 case SystemZAddressingMode::Disp20Only128:
254 return isInt<20>(Val) && isInt<20>(Val + 8);
256 llvm_unreachable("Unhandled displacement range");
259 // Change the base or index in AM to Value, where IsBase selects
260 // between the base and index.
261 static void changeComponent(SystemZAddressingMode &AM, bool IsBase,
269 // The base or index of AM is equivalent to Value + ADJDYNALLOC,
270 // where IsBase selects between the base and index. Try to fold the
271 // ADJDYNALLOC into AM.
272 static bool expandAdjDynAlloc(SystemZAddressingMode &AM, bool IsBase,
274 if (AM.isDynAlloc() && !AM.IncludesDynAlloc) {
275 changeComponent(AM, IsBase, Value);
276 AM.IncludesDynAlloc = true;
282 // The base of AM is equivalent to Base + Index. Try to use Index as
283 // the index register.
284 static bool expandIndex(SystemZAddressingMode &AM, SDValue Base,
286 if (AM.hasIndexField() && !AM.Index.getNode()) {
294 // The base or index of AM is equivalent to Op0 + Op1, where IsBase selects
295 // between the base and index. Try to fold Op1 into AM's displacement.
296 static bool expandDisp(SystemZAddressingMode &AM, bool IsBase,
297 SDValue Op0, ConstantSDNode *Op1) {
298 // First try adjusting the displacement.
299 int64_t TestDisp = AM.Disp + Op1->getSExtValue();
300 if (selectDisp(AM.DR, TestDisp)) {
301 changeComponent(AM, IsBase, Op0);
306 // We could consider forcing the displacement into a register and
307 // using it as an index, but it would need to be carefully tuned.
311 bool SystemZDAGToDAGISel::expandAddress(SystemZAddressingMode &AM,
313 SDValue N = IsBase ? AM.Base : AM.Index;
314 unsigned Opcode = N.getOpcode();
315 if (Opcode == ISD::TRUNCATE) {
317 Opcode = N.getOpcode();
319 if (Opcode == ISD::ADD || CurDAG->isBaseWithConstantOffset(N)) {
320 SDValue Op0 = N.getOperand(0);
321 SDValue Op1 = N.getOperand(1);
323 unsigned Op0Code = Op0->getOpcode();
324 unsigned Op1Code = Op1->getOpcode();
326 if (Op0Code == SystemZISD::ADJDYNALLOC)
327 return expandAdjDynAlloc(AM, IsBase, Op1);
328 if (Op1Code == SystemZISD::ADJDYNALLOC)
329 return expandAdjDynAlloc(AM, IsBase, Op0);
331 if (Op0Code == ISD::Constant)
332 return expandDisp(AM, IsBase, Op1, cast<ConstantSDNode>(Op0));
333 if (Op1Code == ISD::Constant)
334 return expandDisp(AM, IsBase, Op0, cast<ConstantSDNode>(Op1));
336 if (IsBase && expandIndex(AM, Op0, Op1))
342 // Return true if an instruction with displacement range DR should be
343 // used for displacement value Val. selectDisp(DR, Val) must already hold.
344 static bool isValidDisp(SystemZAddressingMode::DispRange DR, int64_t Val) {
345 assert(selectDisp(DR, Val) && "Invalid displacement");
347 case SystemZAddressingMode::Disp12Only:
348 case SystemZAddressingMode::Disp20Only:
349 case SystemZAddressingMode::Disp20Only128:
352 case SystemZAddressingMode::Disp12Pair:
353 // Use the other instruction if the displacement is too large.
354 return isUInt<12>(Val);
356 case SystemZAddressingMode::Disp20Pair:
357 // Use the other instruction if the displacement is small enough.
358 return !isUInt<12>(Val);
360 llvm_unreachable("Unhandled displacement range");
363 // Return true if Base + Disp + Index should be performed by LA(Y).
364 static bool shouldUseLA(SDNode *Base, int64_t Disp, SDNode *Index) {
365 // Don't use LA(Y) for constants.
369 // Always use LA(Y) for frame addresses, since we know that the destination
370 // register is almost always (perhaps always) going to be different from
371 // the frame register.
372 if (Base->getOpcode() == ISD::FrameIndex)
376 // Always use LA(Y) if there is a base, displacement and index.
380 // Always use LA if the displacement is small enough. It should always
381 // be no worse than AGHI (and better if it avoids a move).
382 if (isUInt<12>(Disp))
385 // For similar reasons, always use LAY if the constant is too big for AGHI.
386 // LAY should be no worse than AGFI.
387 if (!isInt<16>(Disp))
390 // Don't use LA for plain registers.
394 // Don't use LA for plain addition if the index operand is only used
395 // once. It should be a natural two-operand addition in that case.
396 if (Index->hasOneUse())
399 // Prefer addition if the second operation is sign-extended, in the
400 // hope of using AGF.
401 unsigned IndexOpcode = Index->getOpcode();
402 if (IndexOpcode == ISD::SIGN_EXTEND ||
403 IndexOpcode == ISD::SIGN_EXTEND_INREG)
407 // Don't use LA for two-operand addition if either operand is only
408 // used once. The addition instructions are better in that case.
409 if (Base->hasOneUse())
415 // Return true if Addr is suitable for AM, updating AM if so.
416 bool SystemZDAGToDAGISel::selectAddress(SDValue Addr,
417 SystemZAddressingMode &AM) {
418 // Start out assuming that the address will need to be loaded separately,
419 // then try to extend it as much as we can.
422 // First try treating the address as a constant.
423 if (Addr.getOpcode() == ISD::Constant &&
424 expandDisp(AM, true, SDValue(), cast<ConstantSDNode>(Addr)))
427 // Otherwise try expanding each component.
428 while (expandAddress(AM, true) ||
429 (AM.Index.getNode() && expandAddress(AM, false)))
432 // Reject cases where it isn't profitable to use LA(Y).
433 if (AM.Form == SystemZAddressingMode::FormBDXLA &&
434 !shouldUseLA(AM.Base.getNode(), AM.Disp, AM.Index.getNode()))
437 // Reject cases where the other instruction in a pair should be used.
438 if (!isValidDisp(AM.DR, AM.Disp))
441 // Make sure that ADJDYNALLOC is included where necessary.
442 if (AM.isDynAlloc() && !AM.IncludesDynAlloc)
449 // Insert a node into the DAG at least before Pos. This will reposition
450 // the node as needed, and will assign it a node ID that is <= Pos's ID.
451 // Note that this does *not* preserve the uniqueness of node IDs!
452 // The selection DAG must no longer depend on their uniqueness when this
454 static void insertDAGNode(SelectionDAG *DAG, SDNode *Pos, SDValue N) {
455 if (N.getNode()->getNodeId() == -1 ||
456 N.getNode()->getNodeId() > Pos->getNodeId()) {
457 DAG->RepositionNode(Pos, N.getNode());
458 N.getNode()->setNodeId(Pos->getNodeId());
462 void SystemZDAGToDAGISel::getAddressOperands(const SystemZAddressingMode &AM,
463 EVT VT, SDValue &Base,
467 // Register 0 means "no base". This is mostly useful for shifts.
468 Base = CurDAG->getRegister(0, VT);
469 else if (Base.getOpcode() == ISD::FrameIndex) {
470 // Lower a FrameIndex to a TargetFrameIndex.
471 int64_t FrameIndex = cast<FrameIndexSDNode>(Base)->getIndex();
472 Base = CurDAG->getTargetFrameIndex(FrameIndex, VT);
473 } else if (Base.getValueType() != VT) {
474 // Truncate values from i64 to i32, for shifts.
475 assert(VT == MVT::i32 && Base.getValueType() == MVT::i64 &&
476 "Unexpected truncation");
477 DebugLoc DL = Base.getDebugLoc();
478 SDValue Trunc = CurDAG->getNode(ISD::TRUNCATE, DL, VT, Base);
479 insertDAGNode(CurDAG, Base.getNode(), Trunc);
483 // Lower the displacement to a TargetConstant.
484 Disp = CurDAG->getTargetConstant(AM.Disp, VT);
487 void SystemZDAGToDAGISel::getAddressOperands(const SystemZAddressingMode &AM,
488 EVT VT, SDValue &Base,
489 SDValue &Disp, SDValue &Index) {
490 getAddressOperands(AM, VT, Base, Disp);
493 if (!Index.getNode())
494 // Register 0 means "no index".
495 Index = CurDAG->getRegister(0, VT);
498 bool SystemZDAGToDAGISel::selectBDAddr(SystemZAddressingMode::DispRange DR,
499 SDValue Addr, SDValue &Base,
501 SystemZAddressingMode AM(SystemZAddressingMode::FormBD, DR);
502 if (!selectAddress(Addr, AM))
505 getAddressOperands(AM, Addr.getValueType(), Base, Disp);
509 bool SystemZDAGToDAGISel::selectBDXAddr(SystemZAddressingMode::AddrForm Form,
510 SystemZAddressingMode::DispRange DR,
511 SDValue Addr, SDValue &Base,
512 SDValue &Disp, SDValue &Index) {
513 SystemZAddressingMode AM(Form, DR);
514 if (!selectAddress(Addr, AM))
517 getAddressOperands(AM, Addr.getValueType(), Base, Disp, Index);
521 SDNode *SystemZDAGToDAGISel::splitLargeImmediate(unsigned Opcode, SDNode *Node,
522 SDValue Op0, uint64_t UpperVal,
524 EVT VT = Node->getValueType(0);
525 DebugLoc DL = Node->getDebugLoc();
526 SDValue Upper = CurDAG->getConstant(UpperVal, VT);
528 Upper = CurDAG->getNode(Opcode, DL, VT, Op0, Upper);
529 Upper = SDValue(Select(Upper.getNode()), 0);
531 SDValue Lower = CurDAG->getConstant(LowerVal, VT);
532 SDValue Or = CurDAG->getNode(Opcode, DL, VT, Upper, Lower);
536 SDNode *SystemZDAGToDAGISel::Select(SDNode *Node) {
537 // Dump information about the Node being selected
538 DEBUG(errs() << "Selecting: "; Node->dump(CurDAG); errs() << "\n");
540 // If we have a custom node, we already have selected!
541 if (Node->isMachineOpcode()) {
542 DEBUG(errs() << "== "; Node->dump(CurDAG); errs() << "\n");
547 unsigned Opcode = Node->getOpcode();
551 // If this is a 64-bit operation in which both 32-bit halves are nonzero,
552 // split the operation into two.
553 if (Node->getValueType(0) == MVT::i64)
554 if (ConstantSDNode *Op1 = dyn_cast<ConstantSDNode>(Node->getOperand(1))) {
555 uint64_t Val = Op1->getZExtValue();
556 if (!SystemZ::isImmLF(Val) && !SystemZ::isImmHF(Val))
557 Node = splitLargeImmediate(Opcode, Node, Node->getOperand(0),
558 Val - uint32_t(Val), uint32_t(Val));
563 // If this is a 64-bit constant that is out of the range of LLILF,
564 // LLIHF and LGFI, split it into two 32-bit pieces.
565 if (Node->getValueType(0) == MVT::i64) {
566 uint64_t Val = cast<ConstantSDNode>(Node)->getZExtValue();
567 if (!SystemZ::isImmLF(Val) && !SystemZ::isImmHF(Val) && !isInt<32>(Val))
568 Node = splitLargeImmediate(ISD::OR, Node, SDValue(),
569 Val - uint32_t(Val), uint32_t(Val));
573 case ISD::ATOMIC_LOAD_SUB:
574 // Try to convert subtractions of constants to additions.
575 if (ConstantSDNode *Op2 = dyn_cast<ConstantSDNode>(Node->getOperand(2))) {
576 uint64_t Value = -Op2->getZExtValue();
577 EVT VT = Node->getValueType(0);
578 if (VT == MVT::i32 || isInt<32>(Value)) {
579 SDValue Ops[] = { Node->getOperand(0), Node->getOperand(1),
580 CurDAG->getConstant(int32_t(Value), VT) };
581 Node = CurDAG->MorphNodeTo(Node, ISD::ATOMIC_LOAD_ADD,
582 Node->getVTList(), Ops, array_lengthof(Ops));
588 // Select the default instruction
589 SDNode *ResNode = SelectCode(Node);
591 DEBUG(errs() << "=> ";
592 if (ResNode == NULL || ResNode == Node)
595 ResNode->dump(CurDAG);
601 bool SystemZDAGToDAGISel::
602 SelectInlineAsmMemoryOperand(const SDValue &Op,
604 std::vector<SDValue> &OutOps) {
605 assert(ConstraintCode == 'm' && "Unexpected constraint code");
606 // Accept addresses with short displacements, which are compatible
607 // with Q, R, S and T. But keep the index operand for future expansion.
608 SDValue Base, Disp, Index;
609 if (!selectBDXAddr(SystemZAddressingMode::FormBD,
610 SystemZAddressingMode::Disp12Only,
611 Op, Base, Disp, Index))
613 OutOps.push_back(Base);
614 OutOps.push_back(Disp);
615 OutOps.push_back(Index);