1 //===-- PPC32ISelDAGToDAG.cpp - PPC32 pattern matching inst selector ------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by Chris Lattner and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines a pattern matching instruction selector for 32 bit PowerPC,
11 // converting from a legalized dag to a PPC dag.
13 //===----------------------------------------------------------------------===//
16 #include "PPC32TargetMachine.h"
17 #include "PPC32ISelLowering.h"
18 #include "llvm/CodeGen/SelectionDAG.h"
19 #include "llvm/CodeGen/SelectionDAGISel.h"
20 #include "llvm/Target/TargetOptions.h"
21 #include "llvm/ADT/Statistic.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Support/MathExtras.h"
27 Statistic<> Recorded("ppc-codegen", "Number of recording ops emitted");
28 Statistic<> FusedFP ("ppc-codegen", "Number of fused fp operations");
29 Statistic<> FrameOff("ppc-codegen", "Number of frame idx offsets collapsed");
31 //===--------------------------------------------------------------------===//
32 /// PPC32DAGToDAGISel - PPC32 specific code to select PPC32 machine
33 /// instructions for SelectionDAG operations.
35 class PPC32DAGToDAGISel : public SelectionDAGISel {
36 PPC32TargetLowering PPC32Lowering;
39 PPC32DAGToDAGISel(TargetMachine &TM)
40 : SelectionDAGISel(PPC32Lowering), PPC32Lowering(TM) {}
42 /// getI32Imm - Return a target constant with the specified value, of type
44 inline SDOperand getI32Imm(unsigned Imm) {
45 return CurDAG->getTargetConstant(Imm, MVT::i32);
48 // Select - Convert the specified operand from a target-independent to a
49 // target-specific node if it hasn't already been changed.
50 SDOperand Select(SDOperand Op);
52 SDNode *SelectIntImmediateExpr(SDOperand LHS, SDOperand RHS,
53 unsigned OCHi, unsigned OCLo,
54 bool IsArithmetic = false,
57 /// InstructionSelectBasicBlock - This callback is invoked by
58 /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
59 virtual void InstructionSelectBasicBlock(SelectionDAG &DAG) {
61 // Select target instructions for the DAG.
62 Select(DAG.getRoot());
63 DAG.RemoveDeadNodes();
65 // Emit machine code to BB.
66 ScheduleAndEmitDAG(DAG);
69 virtual const char *getPassName() const {
70 return "PowerPC DAG->DAG Pattern Instruction Selection";
75 // isIntImmediate - This method tests to see if a constant operand.
76 // If so Imm will receive the 32 bit value.
77 static bool isIntImmediate(SDNode *N, unsigned& Imm) {
78 if (N->getOpcode() == ISD::Constant) {
79 Imm = cast<ConstantSDNode>(N)->getValue();
85 // isOprShiftImm - Returns true if the specified operand is a shift opcode with
86 // a immediate shift count less than 32.
87 static bool isOprShiftImm(SDNode *N, unsigned& Opc, unsigned& SH) {
89 return (Opc == ISD::SHL || Opc == ISD::SRL || Opc == ISD::SRA) &&
90 isIntImmediate(N->getOperand(1).Val, SH) && SH < 32;
93 // isRunOfOnes - Returns true iff Val consists of one contiguous run of 1s with
94 // any number of 0s on either side. The 1s are allowed to wrap from LSB to
95 // MSB, so 0x000FFF0, 0x0000FFFF, and 0xFF0000FF are all runs. 0x0F0F0000 is
96 // not, since all 1s are not contiguous.
97 static bool isRunOfOnes(unsigned Val, unsigned &MB, unsigned &ME) {
98 if (isShiftedMask_32(Val)) {
99 // look for the first non-zero bit
100 MB = CountLeadingZeros_32(Val);
101 // look for the first zero bit after the run of ones
102 ME = CountLeadingZeros_32((Val - 1) ^ Val);
104 } else if (isShiftedMask_32(Val = ~Val)) { // invert mask
105 // effectively look for the first zero bit
106 ME = CountLeadingZeros_32(Val) - 1;
107 // effectively look for the first one bit after the run of zeros
108 MB = CountLeadingZeros_32((Val - 1) ^ Val) + 1;
115 // isRotateAndMask - Returns true if Mask and Shift can be folded in to a rotate
116 // and mask opcode and mask operation.
117 static bool isRotateAndMask(SDNode *N, unsigned Mask, bool IsShiftMask,
118 unsigned &SH, unsigned &MB, unsigned &ME) {
120 unsigned Indeterminant = ~0; // bit mask marking indeterminant results
121 unsigned Opcode = N->getOpcode();
122 if (!isIntImmediate(N->getOperand(1).Val, Shift) || (Shift > 31))
125 if (Opcode == ISD::SHL) {
126 // apply shift left to mask if it comes first
127 if (IsShiftMask) Mask = Mask << Shift;
128 // determine which bits are made indeterminant by shift
129 Indeterminant = ~(0xFFFFFFFFu << Shift);
130 } else if (Opcode == ISD::SRA || Opcode == ISD::SRL) {
131 // apply shift right to mask if it comes first
132 if (IsShiftMask) Mask = Mask >> Shift;
133 // determine which bits are made indeterminant by shift
134 Indeterminant = ~(0xFFFFFFFFu >> Shift);
135 // adjust for the left rotate
141 // if the mask doesn't intersect any Indeterminant bits
142 if (Mask && !(Mask & Indeterminant)) {
144 // make sure the mask is still a mask (wrap arounds may not be)
145 return isRunOfOnes(Mask, MB, ME);
150 // isOpcWithIntImmediate - This method tests to see if the node is a specific
151 // opcode and that it has a immediate integer right operand.
152 // If so Imm will receive the 32 bit value.
153 static bool isOpcWithIntImmediate(SDNode *N, unsigned Opc, unsigned& Imm) {
154 return N->getOpcode() == Opc && isIntImmediate(N->getOperand(1).Val, Imm);
157 // isOprNot - Returns true if the specified operand is an xor with immediate -1.
158 static bool isOprNot(SDNode *N) {
160 return isOpcWithIntImmediate(N, ISD::XOR, Imm) && (signed)Imm == -1;
163 // Immediate constant composers.
164 // Lo16 - grabs the lo 16 bits from a 32 bit constant.
165 // Hi16 - grabs the hi 16 bits from a 32 bit constant.
166 // HA16 - computes the hi bits required if the lo bits are add/subtracted in
168 static unsigned Lo16(unsigned x) { return x & 0x0000FFFF; }
169 static unsigned Hi16(unsigned x) { return Lo16(x >> 16); }
170 static unsigned HA16(unsigned x) { return Hi16((signed)x - (signed short)x); }
172 // isIntImmediate - This method tests to see if a constant operand.
173 // If so Imm will receive the 32 bit value.
174 static bool isIntImmediate(SDOperand N, unsigned& Imm) {
175 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N)) {
176 Imm = (unsigned)CN->getSignExtended();
182 // SelectIntImmediateExpr - Choose code for integer operations with an immediate
184 SDNode *PPC32DAGToDAGISel::SelectIntImmediateExpr(SDOperand LHS, SDOperand RHS,
185 unsigned OCHi, unsigned OCLo,
188 // Check to make sure this is a constant.
189 ConstantSDNode *CN = dyn_cast<ConstantSDNode>(RHS);
190 // Exit if not a constant.
192 // Extract immediate.
193 unsigned C = (unsigned)CN->getValue();
194 // Negate if required (ISD::SUB).
196 // Get the hi and lo portions of constant.
197 unsigned Hi = IsArithmetic ? HA16(C) : Hi16(C);
198 unsigned Lo = Lo16(C);
200 // If two instructions are needed and usage indicates it would be better to
201 // load immediate into a register, bail out.
202 if (Hi && Lo && CN->use_size() > 2) return false;
204 // Select the first operand.
205 SDOperand Opr0 = Select(LHS);
207 if (Lo) // Add in the lo-part.
208 Opr0 = CurDAG->getTargetNode(OCLo, MVT::i32, Opr0, getI32Imm(Lo));
209 if (Hi) // Add in the hi-part.
210 Opr0 = CurDAG->getTargetNode(OCHi, MVT::i32, Opr0, getI32Imm(Hi));
215 // Select - Convert the specified operand from a target-independent to a
216 // target-specific node if it hasn't already been changed.
217 SDOperand PPC32DAGToDAGISel::Select(SDOperand Op) {
219 if (N->getOpcode() >= ISD::BUILTIN_OP_END)
220 return Op; // Already selected.
222 switch (N->getOpcode()) {
224 std::cerr << "Cannot yet select: ";
228 case ISD::EntryToken: // These leaves remain the same.
231 case ISD::TokenFactor: {
233 if (N->getNumOperands() == 2) {
234 SDOperand Op0 = Select(N->getOperand(0));
235 SDOperand Op1 = Select(N->getOperand(1));
236 New = CurDAG->getNode(ISD::TokenFactor, MVT::Other, Op0, Op1);
238 std::vector<SDOperand> Ops;
239 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
240 Ops.push_back(Select(N->getOperand(0)));
241 New = CurDAG->getNode(ISD::TokenFactor, MVT::Other, Ops);
245 CurDAG->ReplaceAllUsesWith(N, New.Val);
250 case ISD::CopyFromReg: {
251 SDOperand Chain = Select(N->getOperand(0));
252 if (Chain == N->getOperand(0)) return Op; // No change
253 SDOperand New = CurDAG->getCopyFromReg(Chain,
254 cast<RegisterSDNode>(N->getOperand(1))->getReg(), N->getValueType(0));
255 return New.getValue(Op.ResNo);
257 case ISD::CopyToReg: {
258 SDOperand Chain = Select(N->getOperand(0));
259 SDOperand Reg = N->getOperand(1);
260 SDOperand Val = Select(N->getOperand(2));
261 if (Chain != N->getOperand(0) || Val != N->getOperand(2)) {
262 SDOperand New = CurDAG->getNode(ISD::CopyToReg, MVT::Other,
264 CurDAG->ReplaceAllUsesWith(N, New.Val);
269 case ISD::Constant: {
270 assert(N->getValueType(0) == MVT::i32);
271 unsigned v = (unsigned)cast<ConstantSDNode>(N)->getValue();
272 unsigned Hi = HA16(v);
273 unsigned Lo = Lo16(v);
275 SDOperand Top = CurDAG->getTargetNode(PPC::LIS, MVT::i32,
277 CurDAG->SelectNodeTo(N, MVT::i32, PPC::ORI, Top, getI32Imm(v & 0xFFFF));
279 CurDAG->SelectNodeTo(N, MVT::i32, PPC::LI, getI32Imm(v));
281 CurDAG->SelectNodeTo(N, MVT::i32, PPC::LIS, getI32Imm(v >> 16));
285 case ISD::SIGN_EXTEND_INREG:
286 switch(cast<VTSDNode>(N->getOperand(1))->getVT()) {
287 default: assert(0 && "Illegal type in SIGN_EXTEND_INREG"); break;
289 CurDAG->SelectNodeTo(N, MVT::i32, PPC::EXTSH, Select(N->getOperand(0)));
292 CurDAG->SelectNodeTo(N, MVT::i32, PPC::EXTSB, Select(N->getOperand(0)));
297 assert(N->getValueType(0) == MVT::i32);
298 CurDAG->SelectNodeTo(N, MVT::i32, PPC::CNTLZW, Select(N->getOperand(0)));
301 MVT::ValueType Ty = N->getValueType(0);
302 if (Ty == MVT::i32) {
303 if (SDNode *I = SelectIntImmediateExpr(N->getOperand(0), N->getOperand(1),
304 PPC::ADDIS, PPC::ADDI, true)) {
305 CurDAG->ReplaceAllUsesWith(N, I);
308 CurDAG->SelectNodeTo(N, Ty, PPC::ADD, Select(N->getOperand(0)),
309 Select(N->getOperand(1)));
314 if (!NoExcessFPPrecision) { // Match FMA ops
315 if (N->getOperand(0).getOpcode() == ISD::MUL &&
316 N->getOperand(0).Val->hasOneUse()) {
317 ++FusedFP; // Statistic
318 CurDAG->SelectNodeTo(N, Ty, Ty == MVT::f64 ? PPC::FMADD : PPC::FMADDS,
319 Select(N->getOperand(0).getOperand(0)),
320 Select(N->getOperand(0).getOperand(1)),
321 Select(N->getOperand(1)));
323 } else if (N->getOperand(1).getOpcode() == ISD::MUL &&
324 N->getOperand(1).hasOneUse()) {
325 ++FusedFP; // Statistic
326 CurDAG->SelectNodeTo(N, Ty, Ty == MVT::f64 ? PPC::FMADD : PPC::FMADDS,
327 Select(N->getOperand(1).getOperand(0)),
328 Select(N->getOperand(1).getOperand(1)),
329 Select(N->getOperand(0)));
334 CurDAG->SelectNodeTo(N, Ty, Ty == MVT::f64 ? PPC::FADD : PPC::FADDS,
335 Select(N->getOperand(0)), Select(N->getOperand(1)));
339 MVT::ValueType Ty = N->getValueType(0);
340 if (Ty == MVT::i32) {
342 if (isIntImmediate(N->getOperand(0), Imm) && isInt16(Imm)) {
343 CurDAG->SelectNodeTo(N, Ty, PPC::SUBFIC, Select(N->getOperand(1)),
344 getI32Imm(Lo16(Imm)));
347 if (SDNode *I = SelectIntImmediateExpr(N->getOperand(0), N->getOperand(1),
348 PPC::ADDIS, PPC::ADDI, true, true)) {
349 CurDAG->ReplaceAllUsesWith(N, I);
352 CurDAG->SelectNodeTo(N, Ty, PPC::SUBF, Select(N->getOperand(1)),
353 Select(N->getOperand(0)));
358 if (!NoExcessFPPrecision) { // Match FMA ops
359 if (N->getOperand(0).getOpcode() == ISD::MUL &&
360 N->getOperand(0).Val->hasOneUse()) {
361 ++FusedFP; // Statistic
362 CurDAG->SelectNodeTo(N, Ty, Ty == MVT::f64 ? PPC::FMSUB : PPC::FMSUBS,
363 Select(N->getOperand(0).getOperand(0)),
364 Select(N->getOperand(0).getOperand(1)),
365 Select(N->getOperand(1)));
367 } else if (N->getOperand(1).getOpcode() == ISD::MUL &&
368 N->getOperand(1).Val->hasOneUse()) {
369 ++FusedFP; // Statistic
370 CurDAG->SelectNodeTo(N, Ty, Ty == MVT::f64 ? PPC::FNMSUB : PPC::FNMSUBS,
371 Select(N->getOperand(1).getOperand(0)),
372 Select(N->getOperand(1).getOperand(1)),
373 Select(N->getOperand(0)));
377 CurDAG->SelectNodeTo(N, Ty, Ty == MVT::f64 ? PPC::FSUB : PPC::FSUBS,
378 Select(N->getOperand(0)),
379 Select(N->getOperand(1)));
384 if (isIntImmediate(N->getOperand(1), Imm) && isInt16(Imm)) {
385 CurDAG->SelectNodeTo(N, N->getValueType(0), PPC::MULLI,
386 Select(N->getOperand(0)), getI32Imm(Lo16(Imm)));
389 switch (N->getValueType(0)) {
390 default: assert(0 && "Unhandled multiply type!");
391 case MVT::i32: Opc = PPC::MULLW; break;
392 case MVT::f32: Opc = PPC::FMULS; break;
393 case MVT::f64: Opc = PPC::FMUL; break;
395 CurDAG->SelectNodeTo(N, N->getValueType(0), Opc, Select(N->getOperand(0)),
396 Select(N->getOperand(1)));
400 assert(N->getValueType(0) == MVT::i32);
401 CurDAG->SelectNodeTo(N, MVT::i32, PPC::MULHW, Select(N->getOperand(0)),
402 Select(N->getOperand(1)));
405 assert(N->getValueType(0) == MVT::i32);
406 CurDAG->SelectNodeTo(N, MVT::i32, PPC::MULHWU, Select(N->getOperand(0)),
407 Select(N->getOperand(1)));
411 // If this is an and of a value rotated between 0 and 31 bits and then and'd
412 // with a mask, emit rlwinm
413 if (isIntImmediate(N->getOperand(1), Imm) && (isShiftedMask_32(Imm) ||
414 isShiftedMask_32(~Imm))) {
417 if (isRotateAndMask(N->getOperand(0).Val, Imm, false, SH, MB, ME)) {
418 Val = Select(N->getOperand(0).getOperand(0));
420 Val = Select(N->getOperand(0));
421 isRunOfOnes(Imm, MB, ME);
424 CurDAG->SelectNodeTo(N, MVT::i32, PPC::RLWINM, Val, getI32Imm(SH),
425 getI32Imm(MB), getI32Imm(ME));
428 // If this is an and with an immediate that isn't a mask, then codegen it as
429 // high and low 16 bit immediate ands.
430 if (SDNode *I = SelectIntImmediateExpr(N->getOperand(0),
432 PPC::ANDISo, PPC::ANDIo)) {
433 CurDAG->ReplaceAllUsesWith(N, I);
437 // Finally, check for the case where we are being asked to select
438 // and (not(a), b) or and (a, not(b)) which can be selected as andc.
439 if (isOprNot(N->getOperand(0).Val))
440 CurDAG->SelectNodeTo(N, MVT::i32, PPC::ANDC, Select(N->getOperand(1)),
441 Select(N->getOperand(0).getOperand(0)));
442 else if (isOprNot(N->getOperand(1).Val))
443 CurDAG->SelectNodeTo(N, MVT::i32, PPC::ANDC, Select(N->getOperand(0)),
444 Select(N->getOperand(1).getOperand(0)));
446 CurDAG->SelectNodeTo(N, MVT::i32, PPC::AND, Select(N->getOperand(0)),
447 Select(N->getOperand(1)));
451 // Check whether or not this node is a logical 'not'. This is represented
452 // by llvm as a xor with the constant value -1 (all bits set). If this is a
453 // 'not', then fold 'or' into 'nor', and so forth for the supported ops.
456 SDOperand Val = Select(N->getOperand(0));
457 switch (Val.getTargetOpcode()) {
458 default: Opc = 0; break;
459 case PPC::OR: Opc = PPC::NOR; break;
460 case PPC::AND: Opc = PPC::NAND; break;
461 case PPC::XOR: Opc = PPC::EQV; break;
464 CurDAG->SelectNodeTo(N, MVT::i32, Opc, Val.getOperand(0),
467 CurDAG->SelectNodeTo(N, MVT::i32, PPC::NOR, Val, Val);
470 // If this is a xor with an immediate other than -1, then codegen it as high
471 // and low 16 bit immediate xors.
472 if (SDNode *I = SelectIntImmediateExpr(N->getOperand(0),
474 PPC::XORIS, PPC::XORI)) {
475 CurDAG->ReplaceAllUsesWith(N, I);
479 // Finally, check for the case where we are being asked to select
480 // xor (not(a), b) which is equivalent to not(xor a, b), which is eqv
481 if (isOprNot(N->getOperand(0).Val))
482 CurDAG->SelectNodeTo(N, MVT::i32, PPC::EQV,
483 Select(N->getOperand(0).getOperand(0)),
484 Select(N->getOperand(1)));
486 CurDAG->SelectNodeTo(N, MVT::i32, PPC::XOR, Select(N->getOperand(0)),
487 Select(N->getOperand(1)));
490 CurDAG->SelectNodeTo(N, N->getValueType(0), PPC::FABS,
491 Select(N->getOperand(0)));
494 assert(MVT::f64 == N->getValueType(0) &&
495 MVT::f32 == N->getOperand(0).getValueType() && "Illegal FP_EXTEND");
496 CurDAG->SelectNodeTo(N, MVT::f64, PPC::FMR, Select(N->getOperand(0)));
499 assert(MVT::f32 == N->getValueType(0) &&
500 MVT::f64 == N->getOperand(0).getValueType() && "Illegal FP_ROUND");
501 CurDAG->SelectNodeTo(N, MVT::f32, PPC::FRSP, Select(N->getOperand(0)));
504 SDOperand Val = Select(N->getOperand(0));
505 MVT::ValueType Ty = N->getValueType(0);
506 if (Val.Val->hasOneUse()) {
508 switch (Val.getTargetOpcode()) {
509 default: Opc = 0; break;
510 case PPC::FABS: Opc = PPC::FNABS; break;
511 case PPC::FMADD: Opc = PPC::FNMADD; break;
512 case PPC::FMADDS: Opc = PPC::FNMADDS; break;
513 case PPC::FMSUB: Opc = PPC::FNMSUB; break;
514 case PPC::FMSUBS: Opc = PPC::FNMSUBS; break;
516 // If we inverted the opcode, then emit the new instruction with the
517 // inverted opcode and the original instruction's operands. Otherwise,
518 // fall through and generate a fneg instruction.
520 if (PPC::FNABS == Opc)
521 CurDAG->SelectNodeTo(N, Ty, Opc, Val.getOperand(0));
523 CurDAG->SelectNodeTo(N, Ty, Opc, Val.getOperand(0),
524 Val.getOperand(1), Val.getOperand(2));
528 CurDAG->SelectNodeTo(N, Ty, PPC::FNEG, Val);
532 MVT::ValueType Ty = N->getValueType(0);
533 CurDAG->SelectNodeTo(N, Ty, Ty == MVT::f64 ? PPC::FSQRT : PPC::FSQRTS,
534 Select(N->getOperand(0)));
538 SDOperand Chain = Select(N->getOperand(0)); // Token chain.
540 if (N->getNumOperands() > 1) {
541 SDOperand Val = Select(N->getOperand(1));
542 switch (N->getOperand(1).getValueType()) {
543 default: assert(0 && "Unknown return type!");
546 Chain = CurDAG->getCopyToReg(Chain, PPC::F1, Val);
549 Chain = CurDAG->getCopyToReg(Chain, PPC::R3, Val);
553 if (N->getNumOperands() > 2) {
554 assert(N->getOperand(1).getValueType() == MVT::i32 &&
555 N->getOperand(2).getValueType() == MVT::i32 &&
556 N->getNumOperands() == 2 && "Unknown two-register ret value!");
557 Val = Select(N->getOperand(2));
558 Chain = CurDAG->getCopyToReg(Chain, PPC::R4, Val);
562 // Finally, select this to a blr (return) instruction.
563 CurDAG->SelectNodeTo(N, MVT::Other, PPC::BLR, Chain);
567 return SDOperand(N, 0);
571 /// createPPC32ISelDag - This pass converts a legalized DAG into a
572 /// PowerPC-specific DAG, ready for instruction scheduling.
574 FunctionPass *llvm::createPPC32ISelDag(TargetMachine &TM) {
575 return new PPC32DAGToDAGISel(TM);