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 // Codegen the basic block.
62 Select(DAG.getRoot());
63 DAG.RemoveDeadNodes();
67 virtual const char *getPassName() const {
68 return "PowerPC DAG->DAG Pattern Instruction Selection";
73 // isIntImmediate - This method tests to see if a constant operand.
74 // If so Imm will receive the 32 bit value.
75 static bool isIntImmediate(SDNode *N, unsigned& Imm) {
76 if (N->getOpcode() == ISD::Constant) {
77 Imm = cast<ConstantSDNode>(N)->getValue();
83 // isOprShiftImm - Returns true if the specified operand is a shift opcode with
84 // a immediate shift count less than 32.
85 static bool isOprShiftImm(SDNode *N, unsigned& Opc, unsigned& SH) {
87 return (Opc == ISD::SHL || Opc == ISD::SRL || Opc == ISD::SRA) &&
88 isIntImmediate(N->getOperand(1).Val, SH) && SH < 32;
91 // isRunOfOnes - Returns true iff Val consists of one contiguous run of 1s with
92 // any number of 0s on either side. The 1s are allowed to wrap from LSB to
93 // MSB, so 0x000FFF0, 0x0000FFFF, and 0xFF0000FF are all runs. 0x0F0F0000 is
94 // not, since all 1s are not contiguous.
95 static bool isRunOfOnes(unsigned Val, unsigned &MB, unsigned &ME) {
96 if (isShiftedMask_32(Val)) {
97 // look for the first non-zero bit
98 MB = CountLeadingZeros_32(Val);
99 // look for the first zero bit after the run of ones
100 ME = CountLeadingZeros_32((Val - 1) ^ Val);
102 } else if (isShiftedMask_32(Val = ~Val)) { // invert mask
103 // effectively look for the first zero bit
104 ME = CountLeadingZeros_32(Val) - 1;
105 // effectively look for the first one bit after the run of zeros
106 MB = CountLeadingZeros_32((Val - 1) ^ Val) + 1;
113 // isRotateAndMask - Returns true if Mask and Shift can be folded in to a rotate
114 // and mask opcode and mask operation.
115 static bool isRotateAndMask(SDNode *N, unsigned Mask, bool IsShiftMask,
116 unsigned &SH, unsigned &MB, unsigned &ME) {
118 unsigned Indeterminant = ~0; // bit mask marking indeterminant results
119 unsigned Opcode = N->getOpcode();
120 if (!isIntImmediate(N->getOperand(1).Val, Shift) || (Shift > 31))
123 if (Opcode == ISD::SHL) {
124 // apply shift left to mask if it comes first
125 if (IsShiftMask) Mask = Mask << Shift;
126 // determine which bits are made indeterminant by shift
127 Indeterminant = ~(0xFFFFFFFFu << Shift);
128 } else if (Opcode == ISD::SRA || Opcode == ISD::SRL) {
129 // apply shift right to mask if it comes first
130 if (IsShiftMask) Mask = Mask >> Shift;
131 // determine which bits are made indeterminant by shift
132 Indeterminant = ~(0xFFFFFFFFu >> Shift);
133 // adjust for the left rotate
139 // if the mask doesn't intersect any Indeterminant bits
140 if (Mask && !(Mask & Indeterminant)) {
142 // make sure the mask is still a mask (wrap arounds may not be)
143 return isRunOfOnes(Mask, MB, ME);
148 // isOpcWithIntImmediate - This method tests to see if the node is a specific
149 // opcode and that it has a immediate integer right operand.
150 // If so Imm will receive the 32 bit value.
151 static bool isOpcWithIntImmediate(SDNode *N, unsigned Opc, unsigned& Imm) {
152 return N->getOpcode() == Opc && isIntImmediate(N->getOperand(1).Val, Imm);
155 // isOprNot - Returns true if the specified operand is an xor with immediate -1.
156 static bool isOprNot(SDNode *N) {
158 return isOpcWithIntImmediate(N, ISD::XOR, Imm) && (signed)Imm == -1;
161 // Immediate constant composers.
162 // Lo16 - grabs the lo 16 bits from a 32 bit constant.
163 // Hi16 - grabs the hi 16 bits from a 32 bit constant.
164 // HA16 - computes the hi bits required if the lo bits are add/subtracted in
166 static unsigned Lo16(unsigned x) { return x & 0x0000FFFF; }
167 static unsigned Hi16(unsigned x) { return Lo16(x >> 16); }
168 static unsigned HA16(unsigned x) { return Hi16((signed)x - (signed short)x); }
170 // isIntImmediate - This method tests to see if a constant operand.
171 // If so Imm will receive the 32 bit value.
172 static bool isIntImmediate(SDOperand N, unsigned& Imm) {
173 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N)) {
174 Imm = (unsigned)CN->getSignExtended();
180 // SelectIntImmediateExpr - Choose code for integer operations with an immediate
182 SDNode *PPC32DAGToDAGISel::SelectIntImmediateExpr(SDOperand LHS, SDOperand RHS,
183 unsigned OCHi, unsigned OCLo,
186 // Check to make sure this is a constant.
187 ConstantSDNode *CN = dyn_cast<ConstantSDNode>(RHS);
188 // Exit if not a constant.
190 // Extract immediate.
191 unsigned C = (unsigned)CN->getValue();
192 // Negate if required (ISD::SUB).
194 // Get the hi and lo portions of constant.
195 unsigned Hi = IsArithmetic ? HA16(C) : Hi16(C);
196 unsigned Lo = Lo16(C);
198 // If two instructions are needed and usage indicates it would be better to
199 // load immediate into a register, bail out.
200 if (Hi && Lo && CN->use_size() > 2) return false;
202 // Select the first operand.
203 SDOperand Opr0 = Select(LHS);
205 if (Lo) // Add in the lo-part.
206 Opr0 = CurDAG->getTargetNode(OCLo, MVT::i32, Opr0, getI32Imm(Lo));
207 if (Hi) // Add in the hi-part.
208 Opr0 = CurDAG->getTargetNode(OCHi, MVT::i32, Opr0, getI32Imm(Hi));
213 // Select - Convert the specified operand from a target-independent to a
214 // target-specific node if it hasn't already been changed.
215 SDOperand PPC32DAGToDAGISel::Select(SDOperand Op) {
217 if (N->getOpcode() >= ISD::BUILTIN_OP_END)
218 return Op; // Already selected.
220 switch (N->getOpcode()) {
222 std::cerr << "Cannot yet select: ";
226 case ISD::EntryToken: // These leaves remain the same.
229 case ISD::TokenFactor: {
231 if (N->getNumOperands() == 2) {
232 SDOperand Op0 = Select(N->getOperand(0));
233 SDOperand Op1 = Select(N->getOperand(1));
234 New = CurDAG->getNode(ISD::TokenFactor, MVT::Other, Op0, Op1);
236 std::vector<SDOperand> Ops;
237 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
238 Ops.push_back(Select(N->getOperand(0)));
239 New = CurDAG->getNode(ISD::TokenFactor, MVT::Other, Ops);
243 CurDAG->ReplaceAllUsesWith(N, New.Val);
248 case ISD::CopyFromReg: {
249 SDOperand Chain = Select(N->getOperand(0));
250 if (Chain == N->getOperand(0)) return Op; // No change
251 SDOperand New = CurDAG->getCopyFromReg(Chain,
252 cast<RegisterSDNode>(N->getOperand(1))->getReg(), N->getValueType(0));
253 return New.getValue(Op.ResNo);
255 case ISD::CopyToReg: {
256 SDOperand Chain = Select(N->getOperand(0));
257 SDOperand Reg = N->getOperand(1);
258 SDOperand Val = Select(N->getOperand(2));
259 if (Chain != N->getOperand(0) || Val != N->getOperand(2)) {
260 SDOperand New = CurDAG->getNode(ISD::CopyToReg, MVT::Other,
262 CurDAG->ReplaceAllUsesWith(N, New.Val);
267 case ISD::Constant: {
268 assert(N->getValueType(0) == MVT::i32);
269 unsigned v = (unsigned)cast<ConstantSDNode>(N)->getValue();
270 unsigned Hi = HA16(v);
271 unsigned Lo = Lo16(v);
273 SDOperand Top = CurDAG->getTargetNode(PPC::LIS, MVT::i32,
275 CurDAG->SelectNodeTo(N, MVT::i32, PPC::ORI, Top, getI32Imm(v & 0xFFFF));
277 CurDAG->SelectNodeTo(N, MVT::i32, PPC::LI, getI32Imm(v));
279 CurDAG->SelectNodeTo(N, MVT::i32, PPC::LIS, getI32Imm(v >> 16));
283 case ISD::SIGN_EXTEND_INREG:
284 switch(cast<VTSDNode>(N->getOperand(1))->getVT()) {
285 default: assert(0 && "Illegal type in SIGN_EXTEND_INREG"); break;
287 CurDAG->SelectNodeTo(N, MVT::i32, PPC::EXTSH, Select(N->getOperand(0)));
290 CurDAG->SelectNodeTo(N, MVT::i32, PPC::EXTSB, Select(N->getOperand(0)));
295 assert(N->getValueType(0) == MVT::i32);
296 CurDAG->SelectNodeTo(N, MVT::i32, PPC::CNTLZW, Select(N->getOperand(0)));
299 MVT::ValueType Ty = N->getValueType(0);
300 if (Ty == MVT::i32) {
301 if (SDNode *I = SelectIntImmediateExpr(N->getOperand(0), N->getOperand(1),
302 PPC::ADDIS, PPC::ADDI, true)) {
303 CurDAG->ReplaceAllUsesWith(N, I);
306 CurDAG->SelectNodeTo(N, Ty, PPC::ADD, Select(N->getOperand(0)),
307 Select(N->getOperand(1)));
312 if (!NoExcessFPPrecision) { // Match FMA ops
313 if (N->getOperand(0).getOpcode() == ISD::MUL &&
314 N->getOperand(0).Val->hasOneUse()) {
315 ++FusedFP; // Statistic
316 CurDAG->SelectNodeTo(N, Ty, Ty == MVT::f64 ? PPC::FMADD : PPC::FMADDS,
317 Select(N->getOperand(0).getOperand(0)),
318 Select(N->getOperand(0).getOperand(1)),
319 Select(N->getOperand(1)));
321 } else if (N->getOperand(1).getOpcode() == ISD::MUL &&
322 N->getOperand(1).hasOneUse()) {
323 ++FusedFP; // Statistic
324 CurDAG->SelectNodeTo(N, Ty, Ty == MVT::f64 ? PPC::FMADD : PPC::FMADDS,
325 Select(N->getOperand(1).getOperand(0)),
326 Select(N->getOperand(1).getOperand(1)),
327 Select(N->getOperand(0)));
332 CurDAG->SelectNodeTo(N, Ty, Ty == MVT::f64 ? PPC::FADD : PPC::FADDS,
333 Select(N->getOperand(0)), Select(N->getOperand(1)));
337 MVT::ValueType Ty = N->getValueType(0);
338 if (Ty == MVT::i32) {
340 if (isIntImmediate(N->getOperand(0), Imm) && isInt16(Imm)) {
341 CurDAG->SelectNodeTo(N, Ty, PPC::SUBFIC, Select(N->getOperand(1)),
342 getI32Imm(Lo16(Imm)));
345 if (SDNode *I = SelectIntImmediateExpr(N->getOperand(0), N->getOperand(1),
346 PPC::ADDIS, PPC::ADDI, true, true)) {
347 CurDAG->ReplaceAllUsesWith(N, I);
350 CurDAG->SelectNodeTo(N, Ty, PPC::SUBF, Select(N->getOperand(1)),
351 Select(N->getOperand(0)));
356 if (!NoExcessFPPrecision) { // Match FMA ops
357 if (N->getOperand(0).getOpcode() == ISD::MUL &&
358 N->getOperand(0).Val->hasOneUse()) {
359 ++FusedFP; // Statistic
360 CurDAG->SelectNodeTo(N, Ty, Ty == MVT::f64 ? PPC::FMSUB : PPC::FMSUBS,
361 Select(N->getOperand(0).getOperand(0)),
362 Select(N->getOperand(0).getOperand(1)),
363 Select(N->getOperand(1)));
365 } else if (N->getOperand(1).getOpcode() == ISD::MUL &&
366 N->getOperand(1).Val->hasOneUse()) {
367 ++FusedFP; // Statistic
368 CurDAG->SelectNodeTo(N, Ty, Ty == MVT::f64 ? PPC::FNMSUB : PPC::FNMSUBS,
369 Select(N->getOperand(1).getOperand(0)),
370 Select(N->getOperand(1).getOperand(1)),
371 Select(N->getOperand(0)));
375 CurDAG->SelectNodeTo(N, Ty, Ty == MVT::f64 ? PPC::FSUB : PPC::FSUBS,
376 Select(N->getOperand(0)),
377 Select(N->getOperand(1)));
382 if (isIntImmediate(N->getOperand(1), Imm) && isInt16(Imm)) {
383 CurDAG->SelectNodeTo(N, N->getValueType(0), PPC::MULLI,
384 Select(N->getOperand(0)), getI32Imm(Lo16(Imm)));
387 switch (N->getValueType(0)) {
388 default: assert(0 && "Unhandled multiply type!");
389 case MVT::i32: Opc = PPC::MULLW; break;
390 case MVT::f32: Opc = PPC::FMULS; break;
391 case MVT::f64: Opc = PPC::FMUL; break;
393 CurDAG->SelectNodeTo(N, N->getValueType(0), Opc, Select(N->getOperand(0)),
394 Select(N->getOperand(1)));
398 assert(N->getValueType(0) == MVT::i32);
399 CurDAG->SelectNodeTo(N, MVT::i32, PPC::MULHW, Select(N->getOperand(0)),
400 Select(N->getOperand(1)));
403 assert(N->getValueType(0) == MVT::i32);
404 CurDAG->SelectNodeTo(N, MVT::i32, PPC::MULHWU, Select(N->getOperand(0)),
405 Select(N->getOperand(1)));
409 // If this is an and of a value rotated between 0 and 31 bits and then and'd
410 // with a mask, emit rlwinm
411 if (isIntImmediate(N->getOperand(1), Imm) && (isShiftedMask_32(Imm) ||
412 isShiftedMask_32(~Imm))) {
415 if (isRotateAndMask(N->getOperand(0).Val, Imm, false, SH, MB, ME)) {
416 Val = Select(N->getOperand(0).getOperand(0));
418 Val = Select(N->getOperand(0));
419 isRunOfOnes(Imm, MB, ME);
422 CurDAG->SelectNodeTo(N, MVT::i32, PPC::RLWINM, Val, getI32Imm(SH),
423 getI32Imm(MB), getI32Imm(ME));
426 // If this is an and with an immediate that isn't a mask, then codegen it as
427 // high and low 16 bit immediate ands.
428 if (SDNode *I = SelectIntImmediateExpr(N->getOperand(0),
430 PPC::ANDISo, PPC::ANDIo)) {
431 CurDAG->ReplaceAllUsesWith(N, I);
435 // Finally, check for the case where we are being asked to select
436 // and (not(a), b) or and (a, not(b)) which can be selected as andc.
437 if (isOprNot(N->getOperand(0).Val))
438 CurDAG->SelectNodeTo(N, MVT::i32, PPC::ANDC, Select(N->getOperand(1)),
439 Select(N->getOperand(0).getOperand(0)));
440 else if (isOprNot(N->getOperand(1).Val))
441 CurDAG->SelectNodeTo(N, MVT::i32, PPC::ANDC, Select(N->getOperand(0)),
442 Select(N->getOperand(1).getOperand(0)));
444 CurDAG->SelectNodeTo(N, MVT::i32, PPC::AND, Select(N->getOperand(0)),
445 Select(N->getOperand(1)));
449 // Check whether or not this node is a logical 'not'. This is represented
450 // by llvm as a xor with the constant value -1 (all bits set). If this is a
451 // 'not', then fold 'or' into 'nor', and so forth for the supported ops.
454 SDOperand Val = Select(N->getOperand(0));
455 switch (Val.getTargetOpcode()) {
456 default: Opc = 0; break;
457 case PPC::OR: Opc = PPC::NOR; break;
458 case PPC::AND: Opc = PPC::NAND; break;
459 case PPC::XOR: Opc = PPC::EQV; break;
462 CurDAG->SelectNodeTo(N, MVT::i32, Opc, Val.getOperand(0),
465 CurDAG->SelectNodeTo(N, MVT::i32, PPC::NOR, Val, Val);
468 // If this is a xor with an immediate other than -1, then codegen it as high
469 // and low 16 bit immediate xors.
470 if (SDNode *I = SelectIntImmediateExpr(N->getOperand(0),
472 PPC::XORIS, PPC::XORI)) {
473 CurDAG->ReplaceAllUsesWith(N, I);
477 // Finally, check for the case where we are being asked to select
478 // xor (not(a), b) which is equivalent to not(xor a, b), which is eqv
479 if (isOprNot(N->getOperand(0).Val))
480 CurDAG->SelectNodeTo(N, MVT::i32, PPC::EQV,
481 Select(N->getOperand(0).getOperand(0)),
482 Select(N->getOperand(1)));
484 CurDAG->SelectNodeTo(N, MVT::i32, PPC::XOR, Select(N->getOperand(0)),
485 Select(N->getOperand(1)));
488 CurDAG->SelectNodeTo(N, N->getValueType(0), PPC::FABS,
489 Select(N->getOperand(0)));
492 assert(MVT::f64 == N->getValueType(0) &&
493 MVT::f32 == N->getOperand(0).getValueType() && "Illegal FP_EXTEND");
494 CurDAG->SelectNodeTo(N, MVT::f64, PPC::FMR, Select(N->getOperand(0)));
497 assert(MVT::f32 == N->getValueType(0) &&
498 MVT::f64 == N->getOperand(0).getValueType() && "Illegal FP_ROUND");
499 CurDAG->SelectNodeTo(N, MVT::f32, PPC::FRSP, Select(N->getOperand(0)));
502 SDOperand Val = Select(N->getOperand(0));
503 MVT::ValueType Ty = N->getValueType(0);
504 if (Val.Val->hasOneUse()) {
506 switch (Val.getTargetOpcode()) {
507 default: Opc = 0; break;
508 case PPC::FABS: Opc = PPC::FNABS; break;
509 case PPC::FMADD: Opc = PPC::FNMADD; break;
510 case PPC::FMADDS: Opc = PPC::FNMADDS; break;
511 case PPC::FMSUB: Opc = PPC::FNMSUB; break;
512 case PPC::FMSUBS: Opc = PPC::FNMSUBS; break;
514 // If we inverted the opcode, then emit the new instruction with the
515 // inverted opcode and the original instruction's operands. Otherwise,
516 // fall through and generate a fneg instruction.
518 if (PPC::FNABS == Opc)
519 CurDAG->SelectNodeTo(N, Ty, Opc, Val.getOperand(0));
521 CurDAG->SelectNodeTo(N, Ty, Opc, Val.getOperand(0),
522 Val.getOperand(1), Val.getOperand(2));
526 CurDAG->SelectNodeTo(N, Ty, PPC::FNEG, Val);
530 MVT::ValueType Ty = N->getValueType(0);
531 CurDAG->SelectNodeTo(N, Ty, Ty == MVT::f64 ? PPC::FSQRT : PPC::FSQRTS,
532 Select(N->getOperand(0)));
536 SDOperand Chain = Select(N->getOperand(0)); // Token chain.
538 if (N->getNumOperands() > 1) {
539 SDOperand Val = Select(N->getOperand(1));
540 switch (N->getOperand(1).getValueType()) {
541 default: assert(0 && "Unknown return type!");
544 Chain = CurDAG->getCopyToReg(Chain, PPC::F1, Val);
547 Chain = CurDAG->getCopyToReg(Chain, PPC::R3, Val);
551 if (N->getNumOperands() > 2) {
552 assert(N->getOperand(1).getValueType() == MVT::i32 &&
553 N->getOperand(2).getValueType() == MVT::i32 &&
554 N->getNumOperands() == 2 && "Unknown two-register ret value!");
555 Val = Select(N->getOperand(2));
556 Chain = CurDAG->getCopyToReg(Chain, PPC::R4, Val);
560 // Finally, select this to a blr (return) instruction.
561 CurDAG->SelectNodeTo(N, MVT::Other, PPC::BLR, Chain);
565 return SDOperand(N, 0);
569 /// createPPC32ISelDag - This pass converts a legalized DAG into a
570 /// PowerPC-specific DAG, ready for instruction scheduling.
572 FunctionPass *llvm::createPPC32ISelDag(TargetMachine &TM) {
573 return new PPC32DAGToDAGISel(TM);