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