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;
38 unsigned GlobalBaseReg;
39 bool GlobalBaseInitialized;
41 PPC32DAGToDAGISel(TargetMachine &TM)
42 : SelectionDAGISel(PPC32Lowering), PPC32Lowering(TM) {}
44 /// runOnFunction - Override this function in order to reset our
45 /// per-function variables.
46 virtual bool runOnFunction(Function &Fn) {
47 // Make sure we re-emit a set of the global base reg if necessary
48 GlobalBaseInitialized = false;
49 return SelectionDAGISel::runOnFunction(Fn);
52 /// getI32Imm - Return a target constant with the specified value, of type
54 inline SDOperand getI32Imm(unsigned Imm) {
55 return CurDAG->getTargetConstant(Imm, MVT::i32);
58 // Select - Convert the specified operand from a target-independent to a
59 // target-specific node if it hasn't already been changed.
60 SDOperand Select(SDOperand Op);
62 SDNode *SelectIntImmediateExpr(SDOperand LHS, SDOperand RHS,
63 unsigned OCHi, unsigned OCLo,
64 bool IsArithmetic = false,
67 /// InstructionSelectBasicBlock - This callback is invoked by
68 /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
69 virtual void InstructionSelectBasicBlock(SelectionDAG &DAG) {
71 // Codegen the basic block.
72 Select(DAG.getRoot());
73 DAG.RemoveDeadNodes();
77 virtual const char *getPassName() const {
78 return "PowerPC DAG->DAG Pattern Instruction Selection";
83 // isIntImmediate - This method tests to see if a constant operand.
84 // If so Imm will receive the 32 bit value.
85 static bool isIntImmediate(SDNode *N, unsigned& Imm) {
86 if (N->getOpcode() == ISD::Constant) {
87 Imm = cast<ConstantSDNode>(N)->getValue();
93 // isOprShiftImm - Returns true if the specified operand is a shift opcode with
94 // a immediate shift count less than 32.
95 static bool isOprShiftImm(SDNode *N, unsigned& Opc, unsigned& SH) {
97 return (Opc == ISD::SHL || Opc == ISD::SRL || Opc == ISD::SRA) &&
98 isIntImmediate(N->getOperand(1).Val, SH) && SH < 32;
101 // isRunOfOnes - Returns true iff Val consists of one contiguous run of 1s with
102 // any number of 0s on either side. The 1s are allowed to wrap from LSB to
103 // MSB, so 0x000FFF0, 0x0000FFFF, and 0xFF0000FF are all runs. 0x0F0F0000 is
104 // not, since all 1s are not contiguous.
105 static bool isRunOfOnes(unsigned Val, unsigned &MB, unsigned &ME) {
106 if (isShiftedMask_32(Val)) {
107 // look for the first non-zero bit
108 MB = CountLeadingZeros_32(Val);
109 // look for the first zero bit after the run of ones
110 ME = CountLeadingZeros_32((Val - 1) ^ Val);
112 } else if (isShiftedMask_32(Val = ~Val)) { // invert mask
113 // effectively look for the first zero bit
114 ME = CountLeadingZeros_32(Val) - 1;
115 // effectively look for the first one bit after the run of zeros
116 MB = CountLeadingZeros_32((Val - 1) ^ Val) + 1;
123 // isRotateAndMask - Returns true if Mask and Shift can be folded in to a rotate
124 // and mask opcode and mask operation.
125 static bool isRotateAndMask(SDNode *N, unsigned Mask, bool IsShiftMask,
126 unsigned &SH, unsigned &MB, unsigned &ME) {
128 unsigned Indeterminant = ~0; // bit mask marking indeterminant results
129 unsigned Opcode = N->getOpcode();
130 if (!isIntImmediate(N->getOperand(1).Val, Shift) || (Shift > 31))
133 if (Opcode == ISD::SHL) {
134 // apply shift left to mask if it comes first
135 if (IsShiftMask) Mask = Mask << Shift;
136 // determine which bits are made indeterminant by shift
137 Indeterminant = ~(0xFFFFFFFFu << Shift);
138 } else if (Opcode == ISD::SRA || Opcode == ISD::SRL) {
139 // apply shift right to mask if it comes first
140 if (IsShiftMask) Mask = Mask >> Shift;
141 // determine which bits are made indeterminant by shift
142 Indeterminant = ~(0xFFFFFFFFu >> Shift);
143 // adjust for the left rotate
149 // if the mask doesn't intersect any Indeterminant bits
150 if (Mask && !(Mask & Indeterminant)) {
152 // make sure the mask is still a mask (wrap arounds may not be)
153 return isRunOfOnes(Mask, MB, ME);
158 // isOpcWithIntImmediate - This method tests to see if the node is a specific
159 // opcode and that it has a immediate integer right operand.
160 // If so Imm will receive the 32 bit value.
161 static bool isOpcWithIntImmediate(SDNode *N, unsigned Opc, unsigned& Imm) {
162 return N->getOpcode() == Opc && isIntImmediate(N->getOperand(1).Val, Imm);
165 // isOprNot - Returns true if the specified operand is an xor with immediate -1.
166 static bool isOprNot(SDNode *N) {
168 return isOpcWithIntImmediate(N, ISD::XOR, Imm) && (signed)Imm == -1;
171 // Immediate constant composers.
172 // Lo16 - grabs the lo 16 bits from a 32 bit constant.
173 // Hi16 - grabs the hi 16 bits from a 32 bit constant.
174 // HA16 - computes the hi bits required if the lo bits are add/subtracted in
176 static unsigned Lo16(unsigned x) { return x & 0x0000FFFF; }
177 static unsigned Hi16(unsigned x) { return Lo16(x >> 16); }
178 static unsigned HA16(unsigned x) { return Hi16((signed)x - (signed short)x); }
180 // isIntImmediate - This method tests to see if a constant operand.
181 // If so Imm will receive the 32 bit value.
182 static bool isIntImmediate(SDOperand N, unsigned& Imm) {
183 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N)) {
184 Imm = (unsigned)CN->getSignExtended();
190 // SelectIntImmediateExpr - Choose code for integer operations with an immediate
192 SDNode *PPC32DAGToDAGISel::SelectIntImmediateExpr(SDOperand LHS, SDOperand RHS,
193 unsigned OCHi, unsigned OCLo,
196 // Check to make sure this is a constant.
197 ConstantSDNode *CN = dyn_cast<ConstantSDNode>(RHS);
198 // Exit if not a constant.
200 // Extract immediate.
201 unsigned C = (unsigned)CN->getValue();
202 // Negate if required (ISD::SUB).
204 // Get the hi and lo portions of constant.
205 unsigned Hi = IsArithmetic ? HA16(C) : Hi16(C);
206 unsigned Lo = Lo16(C);
208 // If two instructions are needed and usage indicates it would be better to
209 // load immediate into a register, bail out.
210 if (Hi && Lo && CN->use_size() > 2) return false;
212 // Select the first operand.
213 SDOperand Opr0 = Select(LHS);
215 if (Lo) // Add in the lo-part.
216 Opr0 = CurDAG->getTargetNode(OCLo, MVT::i32, Opr0, getI32Imm(Lo));
217 if (Hi) // Add in the hi-part.
218 Opr0 = CurDAG->getTargetNode(OCHi, MVT::i32, Opr0, getI32Imm(Hi));
223 // Select - Convert the specified operand from a target-independent to a
224 // target-specific node if it hasn't already been changed.
225 SDOperand PPC32DAGToDAGISel::Select(SDOperand Op) {
227 if (N->getOpcode() >= ISD::BUILTIN_OP_END)
228 return Op; // Already selected.
230 switch (N->getOpcode()) {
232 std::cerr << "Cannot yet select: ";
236 case ISD::EntryToken: // These leaves remain the same.
239 case ISD::TokenFactor: {
241 if (N->getNumOperands() == 2) {
242 SDOperand Op0 = Select(N->getOperand(0));
243 SDOperand Op1 = Select(N->getOperand(1));
244 New = CurDAG->getNode(ISD::TokenFactor, MVT::Other, Op0, Op1);
246 std::vector<SDOperand> Ops;
247 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
248 Ops.push_back(Select(N->getOperand(0)));
249 New = CurDAG->getNode(ISD::TokenFactor, MVT::Other, Ops);
253 CurDAG->ReplaceAllUsesWith(N, New.Val);
258 case ISD::CopyFromReg: {
259 SDOperand Chain = Select(N->getOperand(0));
260 if (Chain == N->getOperand(0)) return Op; // No change
261 SDOperand New = CurDAG->getCopyFromReg(Chain,
262 cast<RegisterSDNode>(N->getOperand(1))->getReg(), N->getValueType(0));
263 return New.getValue(Op.ResNo);
265 case ISD::CopyToReg: {
266 SDOperand Chain = Select(N->getOperand(0));
267 SDOperand Reg = N->getOperand(1);
268 SDOperand Val = Select(N->getOperand(2));
269 if (Chain != N->getOperand(0) || Val != N->getOperand(2)) {
270 SDOperand New = CurDAG->getNode(ISD::CopyToReg, MVT::Other,
272 CurDAG->ReplaceAllUsesWith(N, New.Val);
277 case ISD::Constant: {
278 assert(N->getValueType(0) == MVT::i32);
279 unsigned v = (unsigned)cast<ConstantSDNode>(N)->getValue();
280 unsigned Hi = HA16(v);
281 unsigned Lo = Lo16(v);
283 SDOperand Top = CurDAG->getTargetNode(PPC::LIS, MVT::i32,
285 CurDAG->SelectNodeTo(N, MVT::i32, PPC::ORI, Top, getI32Imm(v & 0xFFFF));
287 CurDAG->SelectNodeTo(N, MVT::i32, PPC::LI, getI32Imm(v));
289 CurDAG->SelectNodeTo(N, MVT::i32, PPC::LIS, getI32Imm(v >> 16));
293 case ISD::SIGN_EXTEND_INREG:
294 switch(cast<VTSDNode>(N->getOperand(1))->getVT()) {
295 default: assert(0 && "Illegal type in SIGN_EXTEND_INREG"); break;
297 CurDAG->SelectNodeTo(N, MVT::i32, PPC::EXTSH, Select(N->getOperand(0)));
300 CurDAG->SelectNodeTo(N, MVT::i32, PPC::EXTSB, Select(N->getOperand(0)));
305 assert(N->getValueType(0) == MVT::i32);
306 CurDAG->SelectNodeTo(N, MVT::i32, PPC::CNTLZW, Select(N->getOperand(0)));
309 MVT::ValueType Ty = N->getValueType(0);
310 if (Ty == MVT::i32) {
311 if (SDNode *I = SelectIntImmediateExpr(N->getOperand(0), N->getOperand(1),
312 PPC::ADDIS, PPC::ADDI, true)) {
313 CurDAG->ReplaceAllUsesWith(N, I);
316 CurDAG->SelectNodeTo(N, Ty, PPC::ADD, Select(N->getOperand(0)),
317 Select(N->getOperand(1)));
322 if (!NoExcessFPPrecision) { // Match FMA ops
323 if (N->getOperand(0).getOpcode() == ISD::MUL &&
324 N->getOperand(0).Val->hasOneUse()) {
325 ++FusedFP; // Statistic
326 CurDAG->SelectNodeTo(N, Ty, Ty == MVT::f64 ? PPC::FMADD : PPC::FMADDS,
327 Select(N->getOperand(0).getOperand(0)),
328 Select(N->getOperand(0).getOperand(1)),
329 Select(N->getOperand(1)));
331 } else if (N->getOperand(1).getOpcode() == ISD::MUL &&
332 N->getOperand(1).hasOneUse()) {
333 ++FusedFP; // Statistic
334 CurDAG->SelectNodeTo(N, Ty, Ty == MVT::f64 ? PPC::FMADD : PPC::FMADDS,
335 Select(N->getOperand(1).getOperand(0)),
336 Select(N->getOperand(1).getOperand(1)),
337 Select(N->getOperand(0)));
342 CurDAG->SelectNodeTo(N, Ty, Ty == MVT::f64 ? PPC::FADD : PPC::FADDS,
343 Select(N->getOperand(0)), Select(N->getOperand(1)));
347 MVT::ValueType Ty = N->getValueType(0);
348 if (Ty == MVT::i32) {
350 if (isIntImmediate(N->getOperand(0), Imm) && isInt16(Imm)) {
351 CurDAG->SelectNodeTo(N, Ty, PPC::SUBFIC, Select(N->getOperand(1)),
352 getI32Imm(Lo16(Imm)));
355 if (SDNode *I = SelectIntImmediateExpr(N->getOperand(0), N->getOperand(1),
356 PPC::ADDIS, PPC::ADDI, true, true)) {
357 CurDAG->ReplaceAllUsesWith(N, I);
360 CurDAG->SelectNodeTo(N, Ty, PPC::SUBF, Select(N->getOperand(1)),
361 Select(N->getOperand(0)));
366 if (!NoExcessFPPrecision) { // Match FMA ops
367 if (N->getOperand(0).getOpcode() == ISD::MUL &&
368 N->getOperand(0).Val->hasOneUse()) {
369 ++FusedFP; // Statistic
370 CurDAG->SelectNodeTo(N, Ty, Ty == MVT::f64 ? PPC::FMSUB : PPC::FMSUBS,
371 Select(N->getOperand(0).getOperand(0)),
372 Select(N->getOperand(0).getOperand(1)),
373 Select(N->getOperand(1)));
375 } else if (N->getOperand(1).getOpcode() == ISD::MUL &&
376 N->getOperand(1).Val->hasOneUse()) {
377 ++FusedFP; // Statistic
378 CurDAG->SelectNodeTo(N, Ty, Ty == MVT::f64 ? PPC::FNMSUB : PPC::FNMSUBS,
379 Select(N->getOperand(1).getOperand(0)),
380 Select(N->getOperand(1).getOperand(1)),
381 Select(N->getOperand(0)));
385 CurDAG->SelectNodeTo(N, Ty, Ty == MVT::f64 ? PPC::FSUB : PPC::FSUBS,
386 Select(N->getOperand(0)),
387 Select(N->getOperand(1)));
392 if (isIntImmediate(N->getOperand(1), Imm) && isInt16(Imm)) {
393 CurDAG->SelectNodeTo(N, N->getValueType(0), PPC::MULLI,
394 Select(N->getOperand(0)), getI32Imm(Lo16(Imm)));
397 switch (N->getValueType(0)) {
398 default: assert(0 && "Unhandled multiply type!");
399 case MVT::i32: Opc = PPC::MULLW; break;
400 case MVT::f32: Opc = PPC::FMULS; break;
401 case MVT::f64: Opc = PPC::FMUL; break;
403 CurDAG->SelectNodeTo(N, N->getValueType(0), Opc, Select(N->getOperand(0)),
404 Select(N->getOperand(1)));
408 assert(N->getValueType(0) == MVT::i32);
409 CurDAG->SelectNodeTo(N, MVT::i32, PPC::MULHW, Select(N->getOperand(0)),
410 Select(N->getOperand(1)));
413 assert(N->getValueType(0) == MVT::i32);
414 CurDAG->SelectNodeTo(N, MVT::i32, PPC::MULHWU, Select(N->getOperand(0)),
415 Select(N->getOperand(1)));
419 // If this is an and of a value rotated between 0 and 31 bits and then and'd
420 // with a mask, emit rlwinm
421 if (isIntImmediate(N->getOperand(1), Imm) && (isShiftedMask_32(Imm) ||
422 isShiftedMask_32(~Imm))) {
425 if (isRotateAndMask(N->getOperand(0).Val, Imm, false, SH, MB, ME)) {
426 Val = Select(N->getOperand(0).getOperand(0));
428 Val = Select(N->getOperand(0));
429 isRunOfOnes(Imm, MB, ME);
432 CurDAG->SelectNodeTo(N, MVT::i32, PPC::RLWINM, Val, getI32Imm(SH),
433 getI32Imm(MB), getI32Imm(ME));
436 // If this is an and with an immediate that isn't a mask, then codegen it as
437 // high and low 16 bit immediate ands.
438 if (SDNode *I = SelectIntImmediateExpr(N->getOperand(0),
440 PPC::ANDISo, PPC::ANDIo)) {
441 CurDAG->ReplaceAllUsesWith(N, I);
445 // Finally, check for the case where we are being asked to select
446 // and (not(a), b) or and (a, not(b)) which can be selected as andc.
447 if (isOprNot(N->getOperand(0).Val))
448 CurDAG->SelectNodeTo(N, MVT::i32, PPC::ANDC, Select(N->getOperand(1)),
449 Select(N->getOperand(0).getOperand(0)));
450 else if (isOprNot(N->getOperand(1).Val))
451 CurDAG->SelectNodeTo(N, MVT::i32, PPC::ANDC, Select(N->getOperand(0)),
452 Select(N->getOperand(1).getOperand(0)));
454 CurDAG->SelectNodeTo(N, MVT::i32, PPC::AND, Select(N->getOperand(0)),
455 Select(N->getOperand(1)));
459 // Check whether or not this node is a logical 'not'. This is represented
460 // by llvm as a xor with the constant value -1 (all bits set). If this is a
461 // 'not', then fold 'or' into 'nor', and so forth for the supported ops.
464 SDOperand Val = Select(N->getOperand(0));
465 switch (Val.getTargetOpcode()) {
466 default: Opc = 0; break;
467 case PPC::OR: Opc = PPC::NOR; break;
468 case PPC::AND: Opc = PPC::NAND; break;
469 case PPC::XOR: Opc = PPC::EQV; break;
472 CurDAG->SelectNodeTo(N, MVT::i32, Opc, Val.getOperand(0),
475 CurDAG->SelectNodeTo(N, MVT::i32, PPC::NOR, Val, Val);
478 // If this is a xor with an immediate other than -1, then codegen it as high
479 // and low 16 bit immediate xors.
480 if (SDNode *I = SelectIntImmediateExpr(N->getOperand(0),
482 PPC::XORIS, PPC::XORI)) {
483 CurDAG->ReplaceAllUsesWith(N, I);
487 // Finally, check for the case where we are being asked to select
488 // xor (not(a), b) which is equivalent to not(xor a, b), which is eqv
489 if (isOprNot(N->getOperand(0).Val))
490 CurDAG->SelectNodeTo(N, MVT::i32, PPC::EQV,
491 Select(N->getOperand(0).getOperand(0)),
492 Select(N->getOperand(1)));
494 CurDAG->SelectNodeTo(N, MVT::i32, PPC::XOR, Select(N->getOperand(0)),
495 Select(N->getOperand(1)));
498 CurDAG->SelectNodeTo(N, N->getValueType(0), PPC::FABS,
499 Select(N->getOperand(0)));
502 assert(MVT::f64 == N->getValueType(0) &&
503 MVT::f32 == N->getOperand(0).getValueType() && "Illegal FP_EXTEND");
504 CurDAG->SelectNodeTo(N, MVT::f64, PPC::FMR, Select(N->getOperand(0)));
507 assert(MVT::f32 == N->getValueType(0) &&
508 MVT::f64 == N->getOperand(0).getValueType() && "Illegal FP_ROUND");
509 CurDAG->SelectNodeTo(N, MVT::f32, PPC::FRSP, Select(N->getOperand(0)));
512 SDOperand Val = Select(N->getOperand(0));
513 MVT::ValueType Ty = N->getValueType(0);
514 if (Val.Val->hasOneUse()) {
516 switch (Val.getTargetOpcode()) {
517 default: Opc = 0; break;
518 case PPC::FABS: Opc = PPC::FNABS; break;
519 case PPC::FMADD: Opc = PPC::FNMADD; break;
520 case PPC::FMADDS: Opc = PPC::FNMADDS; break;
521 case PPC::FMSUB: Opc = PPC::FNMSUB; break;
522 case PPC::FMSUBS: Opc = PPC::FNMSUBS; break;
524 // If we inverted the opcode, then emit the new instruction with the
525 // inverted opcode and the original instruction's operands. Otherwise,
526 // fall through and generate a fneg instruction.
528 if (PPC::FNABS == Opc)
529 CurDAG->SelectNodeTo(N, Ty, Opc, Val.getOperand(0));
531 CurDAG->SelectNodeTo(N, Ty, Opc, Val.getOperand(0),
532 Val.getOperand(1), Val.getOperand(2));
536 CurDAG->SelectNodeTo(N, Ty, PPC::FNEG, Val);
540 MVT::ValueType Ty = N->getValueType(0);
541 CurDAG->SelectNodeTo(N, Ty, Ty == MVT::f64 ? PPC::FSQRT : PPC::FSQRTS,
542 Select(N->getOperand(0)));
546 SDOperand Chain = Select(N->getOperand(0)); // Token chain.
548 if (N->getNumOperands() > 1) {
549 SDOperand Val = Select(N->getOperand(1));
550 switch (N->getOperand(1).getValueType()) {
551 default: assert(0 && "Unknown return type!");
554 Chain = CurDAG->getCopyToReg(Chain, PPC::F1, Val);
557 Chain = CurDAG->getCopyToReg(Chain, PPC::R3, Val);
561 if (N->getNumOperands() > 2) {
562 assert(N->getOperand(1).getValueType() == MVT::i32 &&
563 N->getOperand(2).getValueType() == MVT::i32 &&
564 N->getNumOperands() == 2 && "Unknown two-register ret value!");
565 Val = Select(N->getOperand(2));
566 Chain = CurDAG->getCopyToReg(Chain, PPC::R4, Val);
570 // Finally, select this to a blr (return) instruction.
571 CurDAG->SelectNodeTo(N, MVT::Other, PPC::BLR, Chain);
575 return SDOperand(N, 0);
579 /// createPPC32ISelDag - This pass converts a legalized DAG into a
580 /// PowerPC-specific DAG, ready for instruction scheduling.
582 FunctionPass *llvm::createPPC32ISelDag(TargetMachine &TM) {
583 return new PPC32DAGToDAGISel(TM);