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