Start committing working test cases for CellSPU.
[oota-llvm.git] / lib / Target / CellSPU / SPUISelDAGToDAG.cpp
1 //===-- SPUISelDAGToDAG.cpp - CellSPU -pattern matching inst selector -----===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file was developed by a team from the Computer Systems Research
6 // Department at The Aerospace Corporation and is distributed under the
7 // University of Illinois Open Source License. See LICENSE.TXT for details.
8 //
9 //===----------------------------------------------------------------------===//
10 //
11 // This file defines a pattern matching instruction selector for the Cell SPU,
12 // converting from a legalized dag to a SPU-target dag.
13 //
14 //===----------------------------------------------------------------------===//
15
16 #include "SPU.h"
17 #include "SPUTargetMachine.h"
18 #include "SPUISelLowering.h"
19 #include "SPUHazardRecognizers.h"
20 #include "SPUFrameInfo.h"
21 #include "llvm/CodeGen/MachineConstantPool.h"
22 #include "llvm/CodeGen/MachineInstrBuilder.h"
23 #include "llvm/CodeGen/MachineFunction.h"
24 #include "llvm/CodeGen/SSARegMap.h"
25 #include "llvm/CodeGen/SelectionDAG.h"
26 #include "llvm/CodeGen/SelectionDAGISel.h"
27 #include "llvm/Target/TargetOptions.h"
28 #include "llvm/ADT/Statistic.h"
29 #include "llvm/Constants.h"
30 #include "llvm/GlobalValue.h"
31 #include "llvm/Intrinsics.h"
32 #include "llvm/Support/Debug.h"
33 #include "llvm/Support/MathExtras.h"
34 #include "llvm/Support/Compiler.h"
35 #include <iostream>
36 #include <queue>
37 #include <set>
38
39 using namespace llvm;
40
41 namespace {
42   //! ConstantSDNode predicate for i32 sign-extended, 10-bit immediates
43   bool
44   isI64IntS10Immediate(ConstantSDNode *CN)
45   {
46     return isS10Constant(CN->getValue());
47   }
48
49   //! ConstantSDNode predicate for i32 sign-extended, 10-bit immediates
50   bool
51   isI32IntS10Immediate(ConstantSDNode *CN)
52   {
53     return isS10Constant((int) CN->getValue());
54   }
55
56 #if 0
57   //! SDNode predicate for sign-extended, 10-bit immediate values
58   bool
59   isI32IntS10Immediate(SDNode *N)
60   {
61     return (N->getOpcode() == ISD::Constant
62             && isI32IntS10Immediate(cast<ConstantSDNode>(N)));
63   }
64 #endif
65
66   //! ConstantSDNode predicate for i16 sign-extended, 10-bit immediate values
67   bool
68   isI16IntS10Immediate(ConstantSDNode *CN)
69   {
70     return isS10Constant((short) CN->getValue());
71   }
72
73   //! SDNode predicate for i16 sign-extended, 10-bit immediate values
74   bool
75   isI16IntS10Immediate(SDNode *N)
76   {
77     return (N->getOpcode() == ISD::Constant
78             && isI16IntS10Immediate(cast<ConstantSDNode>(N)));
79   }
80
81   //! ConstantSDNode predicate for i16 unsigned 10-bit immediate values
82   bool
83   isI16IntU10Immediate(ConstantSDNode *CN)
84   {
85     return isU10Constant((short) CN->getValue());
86   }
87
88   //! SDNode predicate for i16 sign-extended, 10-bit immediate values
89   bool
90   isI16IntU10Immediate(SDNode *N)
91   {
92     return (N->getOpcode() == ISD::Constant
93             && isI16IntU10Immediate(cast<ConstantSDNode>(N)));
94   }
95
96   //! ConstantSDNode predicate for signed 16-bit values
97   /*!
98     \arg CN The constant SelectionDAG node holding the value
99     \arg Imm The returned 16-bit value, if returning true
100
101     This predicate tests the value in \a CN to see whether it can be
102     represented as a 16-bit, sign-extended quantity. Returns true if
103     this is the case.
104    */
105   bool
106   isIntS16Immediate(ConstantSDNode *CN, short &Imm)
107   {
108     MVT::ValueType vt = CN->getValueType(0);
109     Imm = (short) CN->getValue();
110     if (vt >= MVT::i1 && vt <= MVT::i16) {
111       return true;
112     } else if (vt == MVT::i32) {
113       int32_t i_val = (int32_t) CN->getValue();
114       short s_val = (short) i_val;
115       return i_val == s_val;
116     } else {
117       int64_t i_val = (int64_t) CN->getValue();
118       short s_val = (short) i_val;
119       return i_val == s_val;
120     }
121
122     return false;
123   }
124
125   //! SDNode predicate for signed 16-bit values.
126   bool
127   isIntS16Immediate(SDNode *N, short &Imm)
128   {
129     return (N->getOpcode() == ISD::Constant
130             && isIntS16Immediate(cast<ConstantSDNode>(N), Imm));
131   }
132
133   //! ConstantFPSDNode predicate for representing floats as 16-bit sign ext.
134   static bool
135   isFPS16Immediate(ConstantFPSDNode *FPN, short &Imm)
136   {
137     MVT::ValueType vt = FPN->getValueType(0);
138     if (vt == MVT::f32) {
139       const APFloat &apf = FPN->getValueAPF();
140       float fval = apf.convertToFloat();
141       int val = *((int *) &fval);
142       int sval = (int) ((val << 16) >> 16);
143       Imm = (short) val;
144       return val == sval;
145     }
146
147     return false;
148   }
149
150   //===------------------------------------------------------------------===//
151   //! MVT::ValueType to useful stuff structure:
152
153   struct valtype_map_s {
154     MVT::ValueType VT;
155     unsigned ldresult_ins;      /// LDRESULT instruction (0 = undefined)
156     int prefslot_byte;          /// Byte offset of the "preferred" slot
157     unsigned brcc_eq_ins;       /// br_cc equal instruction
158     unsigned brcc_neq_ins;      /// br_cc not equal instruction
159   };
160
161   const valtype_map_s valtype_map[] = {
162     { MVT::i1,   0,            3, 0,         0 },
163     { MVT::i8,   0,            3, 0,         0 },
164     { MVT::i16,  SPU::ORHIr16, 2, SPU::BRHZ, SPU::BRHNZ },
165     { MVT::i32,  SPU::ORIr32,  0, SPU::BRZ,  SPU::BRNZ },
166     { MVT::i64,  SPU::ORIr64,  0, 0,         0 },
167     { MVT::f32,  SPU::ORIf32,  0, 0,         0 },
168     { MVT::f64,  SPU::ORIf64,  0, 0,         0 }
169   };
170
171   const size_t n_valtype_map = sizeof(valtype_map) / sizeof(valtype_map[0]);
172
173   const valtype_map_s *getValueTypeMapEntry(MVT::ValueType VT)
174   {
175     const valtype_map_s *retval = 0;
176     for (size_t i = 0; i < n_valtype_map; ++i) {
177       if (valtype_map[i].VT == VT) {
178         retval = valtype_map + i;
179         break;
180       }
181     }
182
183
184 #ifndef NDEBUG
185     if (retval == 0) {
186       cerr << "SPUISelDAGToDAG.cpp: getValueTypeMapEntry returns NULL for "
187            << MVT::getValueTypeString(VT)
188            << "\n";
189       abort();
190     }
191 #endif
192
193     return retval;
194   }
195 }
196
197 //===--------------------------------------------------------------------===//
198 /// SPUDAGToDAGISel - Cell SPU-specific code to select SPU machine
199 /// instructions for SelectionDAG operations.
200 ///
201 class SPUDAGToDAGISel :
202   public SelectionDAGISel
203 {
204   SPUTargetMachine &TM;
205   SPUTargetLowering &SPUtli;
206   unsigned GlobalBaseReg;
207
208 public:
209   SPUDAGToDAGISel(SPUTargetMachine &tm) :
210     SelectionDAGISel(*tm.getTargetLowering()),
211     TM(tm),
212     SPUtli(*tm.getTargetLowering())
213   {}
214     
215   virtual bool runOnFunction(Function &Fn) {
216     // Make sure we re-emit a set of the global base reg if necessary
217     GlobalBaseReg = 0;
218     SelectionDAGISel::runOnFunction(Fn);
219     return true;
220   }
221    
222   /// getI32Imm - Return a target constant with the specified value, of type
223   /// i32.
224   inline SDOperand getI32Imm(uint32_t Imm) {
225     return CurDAG->getTargetConstant(Imm, MVT::i32);
226   }
227
228   /// getI64Imm - Return a target constant with the specified value, of type
229   /// i64.
230   inline SDOperand getI64Imm(uint64_t Imm) {
231     return CurDAG->getTargetConstant(Imm, MVT::i64);
232   }
233     
234   /// getSmallIPtrImm - Return a target constant of pointer type.
235   inline SDOperand getSmallIPtrImm(unsigned Imm) {
236     return CurDAG->getTargetConstant(Imm, SPUtli.getPointerTy());
237   }
238
239   /// Select - Convert the specified operand from a target-independent to a
240   /// target-specific node if it hasn't already been changed.
241   SDNode *Select(SDOperand Op);
242
243   /// Return true if the address N is a RI7 format address [r+imm]
244   bool SelectDForm2Addr(SDOperand Op, SDOperand N, SDOperand &Disp,
245                         SDOperand &Base);
246
247   //! Returns true if the address N is an A-form (local store) address
248   bool SelectAFormAddr(SDOperand Op, SDOperand N, SDOperand &Base,
249                        SDOperand &Index);
250
251   //! D-form address predicate
252   bool SelectDFormAddr(SDOperand Op, SDOperand N, SDOperand &Base,
253                        SDOperand &Index);
254
255   //! Address predicate if N can be expressed as an indexed [r+r] operation.
256   bool SelectXFormAddr(SDOperand Op, SDOperand N, SDOperand &Base,
257                        SDOperand &Index);
258
259   /// SelectInlineAsmMemoryOperand - Implement addressing mode selection for
260   /// inline asm expressions.
261   virtual bool SelectInlineAsmMemoryOperand(const SDOperand &Op,
262                                             char ConstraintCode,
263                                             std::vector<SDOperand> &OutOps,
264                                             SelectionDAG &DAG) {
265     SDOperand Op0, Op1;
266     switch (ConstraintCode) {
267     default: return true;
268     case 'm':   // memory
269       if (!SelectDFormAddr(Op, Op, Op0, Op1) 
270           && !SelectAFormAddr(Op, Op, Op0, Op1))
271         SelectXFormAddr(Op, Op, Op0, Op1);
272       break;
273     case 'o':   // offsetable
274       if (!SelectDFormAddr(Op, Op, Op0, Op1)
275           && !SelectAFormAddr(Op, Op, Op0, Op1)) {
276         Op0 = Op;
277         AddToISelQueue(Op0);     // r+0.
278         Op1 = getSmallIPtrImm(0);
279       }
280       break;
281     case 'v':   // not offsetable
282 #if 1
283       assert(0 && "InlineAsmMemoryOperand 'v' constraint not handled.");
284 #else
285       SelectAddrIdxOnly(Op, Op, Op0, Op1);
286 #endif
287       break;
288     }
289       
290     OutOps.push_back(Op0);
291     OutOps.push_back(Op1);
292     return false;
293   }
294
295   /// InstructionSelectBasicBlock - This callback is invoked by
296   /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
297   virtual void InstructionSelectBasicBlock(SelectionDAG &DAG);
298
299   virtual const char *getPassName() const {
300     return "Cell SPU DAG->DAG Pattern Instruction Selection";
301   } 
302     
303   /// CreateTargetHazardRecognizer - Return the hazard recognizer to use for
304   /// this target when scheduling the DAG.
305   virtual HazardRecognizer *CreateTargetHazardRecognizer() {
306     const TargetInstrInfo *II = SPUtli.getTargetMachine().getInstrInfo();
307     assert(II && "No InstrInfo?");
308     return new SPUHazardRecognizer(*II); 
309   }
310
311   // Include the pieces autogenerated from the target description.
312 #include "SPUGenDAGISel.inc"
313 };
314
315 /// InstructionSelectBasicBlock - This callback is invoked by
316 /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
317 void
318 SPUDAGToDAGISel::InstructionSelectBasicBlock(SelectionDAG &DAG)
319 {
320   DEBUG(BB->dump());
321
322   // Select target instructions for the DAG.
323   DAG.setRoot(SelectRoot(DAG.getRoot()));
324   DAG.RemoveDeadNodes();
325   
326   // Emit machine code to BB.
327   ScheduleAndEmitDAG(DAG);
328 }
329
330 bool 
331 SPUDAGToDAGISel::SelectDForm2Addr(SDOperand Op, SDOperand N, SDOperand &Disp,
332                                   SDOperand &Base) {
333   unsigned Opc = N.getOpcode();
334   unsigned VT = N.getValueType();
335   MVT::ValueType PtrVT = SPUtli.getPointerTy();
336   ConstantSDNode *CN = 0;
337   int Imm;
338
339   if (Opc == ISD::ADD) {
340     SDOperand Op0 = N.getOperand(0);
341     SDOperand Op1 = N.getOperand(1);
342     if (Op1.getOpcode() == ISD::Constant ||
343         Op1.getOpcode() == ISD::TargetConstant) {
344       CN = cast<ConstantSDNode>(Op1);
345       Imm = int(CN->getValue());
346       if (Imm <= 0xff) {
347         Disp = CurDAG->getTargetConstant(Imm, SPUtli.getPointerTy());
348         Base = Op0;
349         return true;
350       }
351     }
352   } else if (Opc == ISD::GlobalAddress
353              || Opc == ISD::TargetGlobalAddress
354              || Opc == ISD::Register) {
355     // Plain old local store address: 
356     Disp = CurDAG->getTargetConstant(0, VT);
357     Base = N;
358     return true;
359   } else if (Opc == SPUISD::DFormAddr) {
360     // D-Form address: This is pretty straightforward, naturally...
361     CN = cast<ConstantSDNode>(N.getOperand(1));
362     assert(CN != 0 && "SelectDFormAddr/SPUISD::DForm2Addr expecting constant");
363     Imm = unsigned(CN->getValue());
364     if (Imm < 0xff) {
365       Disp = CurDAG->getTargetConstant(CN->getValue(), PtrVT);
366       Base = N.getOperand(0);
367       return true;
368     }
369   }
370
371   return false;
372 }
373
374 /*!
375  \arg Op The ISD instructio operand
376  \arg N The address to be tested
377  \arg Base The base address
378  \arg Index The base address index
379  */
380 bool
381 SPUDAGToDAGISel::SelectAFormAddr(SDOperand Op, SDOperand N, SDOperand &Base,
382                     SDOperand &Index) {
383   // These match the addr256k operand type:
384   MVT::ValueType PtrVT = SPUtli.getPointerTy();
385   MVT::ValueType OffsVT = MVT::i16;
386
387   switch (N.getOpcode()) {
388   case ISD::Constant:
389   case ISD::TargetConstant: {
390     // Loading from a constant address.
391     ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N);
392     int Imm = (int)CN->getValue();
393     if (Imm < 0x3ffff && (Imm & 0x3) == 0) {
394       Base = CurDAG->getTargetConstant(Imm, PtrVT);
395       // Note that this operand will be ignored by the assembly printer...
396       Index = CurDAG->getTargetConstant(0, OffsVT);
397       return true;
398     }
399   }
400   case ISD::ConstantPool:
401   case ISD::TargetConstantPool: {
402     // The constant pool address is N. Base is a dummy that will be ignored by
403     // the assembly printer.
404     Base = N;
405     Index = CurDAG->getTargetConstant(0, OffsVT);
406     return true;
407   }
408
409   case ISD::GlobalAddress:
410   case ISD::TargetGlobalAddress: {
411     // The global address is N. Base is a dummy that is ignored by the
412     // assembly printer.
413     Base = N;
414     Index = CurDAG->getTargetConstant(0, OffsVT);
415     return true;
416   }
417   }
418
419   return false;
420 }
421
422 /*!
423   \arg Op The ISD instruction (ignored)
424   \arg N The address to be tested
425   \arg Base Base address register/pointer
426   \arg Index Base address index
427
428   Examine the input address by a base register plus a signed 10-bit
429   displacement, [r+I10] (D-form address).
430
431   \return true if \a N is a D-form address with \a Base and \a Index set
432   to non-empty SDOperand instances.
433 */
434 bool
435 SPUDAGToDAGISel::SelectDFormAddr(SDOperand Op, SDOperand N, SDOperand &Base,
436                                  SDOperand &Index) {
437   unsigned Opc = N.getOpcode();
438   unsigned PtrTy = SPUtli.getPointerTy();
439
440   if (Opc == ISD::Register) {
441     Base = N;
442     Index = CurDAG->getTargetConstant(0, PtrTy);
443     return true;
444   } else if (Opc == ISD::FrameIndex) {
445     // Stack frame index must be less than 512 (divided by 16):
446     FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(N);
447     DEBUG(cerr << "SelectDFormAddr: ISD::FrameIndex = "
448           << FI->getIndex() << "\n");
449     if (FI->getIndex() < SPUFrameInfo::maxFrameOffset()) {
450       Base = CurDAG->getTargetConstant(0, PtrTy);
451       Index = CurDAG->getTargetFrameIndex(FI->getIndex(), PtrTy);
452       return true;
453     }
454   } else if (Opc == ISD::ADD) {
455     // Generated by getelementptr
456     const SDOperand Op0 = N.getOperand(0); // Frame index/base
457     const SDOperand Op1 = N.getOperand(1); // Offset within base
458     ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Op1);
459
460     // Not a constant?
461     if (CN == 0)
462       return false;
463
464     int32_t offset = (int32_t) CN->getSignExtended();
465     unsigned Opc0 = Op0.getOpcode();
466
467     if ((offset & 0xf) != 0) {
468       cerr << "SelectDFormAddr: unaligned offset = " << offset << "\n";
469       abort();
470       /*NOTREACHED*/
471     }
472
473     if (Opc0 == ISD::FrameIndex) {
474       FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Op0);
475       DEBUG(cerr << "SelectDFormAddr: ISD::ADD offset = " << offset
476             << " frame index = " << FI->getIndex() << "\n");
477
478       if (FI->getIndex() < SPUFrameInfo::maxFrameOffset()) {
479         Base = CurDAG->getTargetConstant(offset, PtrTy);
480         Index = CurDAG->getTargetFrameIndex(FI->getIndex(), PtrTy);
481         return true;
482       }
483     } else if (offset > SPUFrameInfo::minFrameOffset()
484                && offset < SPUFrameInfo::maxFrameOffset()) {
485       Base = CurDAG->getTargetConstant(offset, PtrTy);
486       if (Opc0 == ISD::GlobalAddress) {
487         // Convert global address to target global address
488         GlobalAddressSDNode *GV = dyn_cast<GlobalAddressSDNode>(Op0);
489         Index = CurDAG->getTargetGlobalAddress(GV->getGlobal(), PtrTy);
490         return true;
491       } else {
492         // Otherwise, just take operand 0
493         Index = Op0;
494         return true;
495       }
496     }
497   } else if (Opc == SPUISD::DFormAddr) {
498     // D-Form address: This is pretty straightforward, naturally...
499     ConstantSDNode *CN = cast<ConstantSDNode>(N.getOperand(1));
500     assert(CN != 0 && "SelectDFormAddr/SPUISD::DFormAddr expecting constant"); 
501     Base = CurDAG->getTargetConstant(CN->getValue(), PtrTy);
502     Index = N.getOperand(0);
503     return true;
504   }
505
506   return false;
507 }
508
509 /*!
510   \arg Op The ISD instruction operand
511   \arg N The address operand
512   \arg Base The base pointer operand
513   \arg Index The offset/index operand
514
515   If the address \a N can be expressed as a [r + s10imm] address, returns false.
516   Otherwise, creates two operands, Base and Index that will become the [r+r]
517   address.
518 */
519 bool
520 SPUDAGToDAGISel::SelectXFormAddr(SDOperand Op, SDOperand N, SDOperand &Base,
521                                  SDOperand &Index) {
522   if (SelectAFormAddr(Op, N, Base, Index)
523       || SelectDFormAddr(Op, N, Base, Index))
524     return false;
525
526   unsigned Opc = N.getOpcode();
527
528   if (Opc == ISD::ADD) {
529     SDOperand N1 = N.getOperand(0);
530     SDOperand N2 = N.getOperand(1);
531     unsigned N1Opc = N1.getOpcode();
532     unsigned N2Opc = N2.getOpcode();
533
534     if ((N1Opc == SPUISD::Hi && N2Opc == SPUISD::Lo)
535          || (N1Opc == SPUISD::Lo && N2Opc == SPUISD::Hi)) {
536       Base = N.getOperand(0);
537       Index = N.getOperand(1);
538       return true;
539     } else {
540       cerr << "SelectXFormAddr: Unhandled ADD operands:\n";
541       N1.Val->dump();
542       cerr << "\n";
543       N2.Val->dump();
544       cerr << "\n";
545       abort();
546       /*UNREACHED*/
547     }
548   } else if (N.getNumOperands() == 2) {
549     SDOperand N1 = N.getOperand(0);
550     SDOperand N2 = N.getOperand(1);
551     unsigned N1Opc = N1.getOpcode();
552     unsigned N2Opc = N2.getOpcode();
553
554     if ((N1Opc == ISD::CopyToReg || N1Opc == ISD::Register)
555         && (N2Opc == ISD::CopyToReg || N2Opc == ISD::Register)) {
556       Base = N.getOperand(0);
557       Index = N.getOperand(1);
558       return true;
559       /*UNREACHED*/
560     } else {
561       cerr << "SelectXFormAddr: 2-operand unhandled operand:\n";
562       N.Val->dump();
563       cerr << "\n";
564       abort();
565     /*UNREACHED*/
566     }
567   } else {
568     cerr << "SelectXFormAddr: Unhandled operand type:\n";
569     N.Val->dump();
570     cerr << "\n";
571     abort();
572     /*UNREACHED*/
573   }
574
575   return false;
576 }
577
578 //! Convert the operand from a target-independent to a target-specific node
579 /*!
580  */
581 SDNode *
582 SPUDAGToDAGISel::Select(SDOperand Op) {
583   SDNode *N = Op.Val;
584   unsigned Opc = N->getOpcode();
585
586   if (Opc >= ISD::BUILTIN_OP_END && Opc < SPUISD::FIRST_NUMBER) {
587     return NULL;   // Already selected.
588   } else if (Opc == ISD::FrameIndex) {
589     // Selects to AIr32 FI, 0 which in turn will become AIr32 SP, imm.
590     int FI = cast<FrameIndexSDNode>(N)->getIndex();
591     SDOperand TFI = CurDAG->getTargetFrameIndex(FI, SPUtli.getPointerTy());
592
593     DEBUG(cerr << "SPUDAGToDAGISel: Replacing FrameIndex with AI32 TFI, 0\n");
594     return CurDAG->SelectNodeTo(N, SPU::AIr32, Op.getValueType(), TFI,
595                                 CurDAG->getTargetConstant(0, MVT::i32));
596   } else if (Opc == SPUISD::LDRESULT) {
597     // Custom select instructions for LDRESULT
598     unsigned VT = N->getValueType(0);
599     SDOperand Arg = N->getOperand(0);
600     SDOperand Chain = N->getOperand(1);
601     SDOperand Zero = CurDAG->getTargetConstant(0, VT);
602     SDNode *Result;
603     const valtype_map_s *vtm = getValueTypeMapEntry(VT);
604
605     if (vtm->ldresult_ins == 0) {
606       cerr << "LDRESULT for unsupported type: "
607            << MVT::getValueTypeString(VT)
608            << "\n";
609       abort();
610     } else
611       Opc = vtm->ldresult_ins;
612
613     AddToISelQueue(Arg);
614     AddToISelQueue(Zero);
615     AddToISelQueue(Chain);
616     Result = CurDAG->SelectNodeTo(N, Opc, VT, MVT::Other, Arg, Zero, Chain);
617     Chain = SDOperand(Result, 1);
618     return Result;
619   }
620   
621   return SelectCode(Op);
622 }
623
624 /// createPPCISelDag - This pass converts a legalized DAG into a 
625 /// SPU-specific DAG, ready for instruction scheduling.
626 ///
627 FunctionPass *llvm::createSPUISelDag(SPUTargetMachine &TM) {
628   return new SPUDAGToDAGISel(TM);
629 }