Add support for sdiv by 2^k and -2^k. Producing code like:
[oota-llvm.git] / lib / Target / PowerPC / PPCISelDAGToDAG.cpp
index 8e3e9f73d11128e3bc028b8de47bb73d6fb7c2d2..57dc1604f4a52da6c2c6fcf6302937424c822847 100644 (file)
@@ -15,6 +15,7 @@
 #include "PowerPC.h"
 #include "PPC32TargetMachine.h"
 #include "PPC32ISelLowering.h"
+#include "llvm/CodeGen/MachineConstantPool.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/SSARegMap.h"
@@ -22,6 +23,7 @@
 #include "llvm/CodeGen/SelectionDAGISel.h"
 #include "llvm/Target/TargetOptions.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/Constants.h"
 #include "llvm/GlobalValue.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/MathExtras.h"
@@ -141,12 +143,15 @@ static bool isRunOfOnes(unsigned Val, unsigned &MB, unsigned &ME) {
     // look for the first zero bit after the run of ones
     ME = CountLeadingZeros_32((Val - 1) ^ Val);
     return true;
-  } else if (isShiftedMask_32(Val = ~Val)) { // invert mask
-                                             // effectively look for the first zero bit
-    ME = CountLeadingZeros_32(Val) - 1;
-    // effectively look for the first one bit after the run of zeros
-    MB = CountLeadingZeros_32((Val - 1) ^ Val) + 1;
-    return true;
+  } else {
+    Val = ~Val; // invert mask
+    if (isShiftedMask_32(Val)) {
+      // effectively look for the first zero bit
+      ME = CountLeadingZeros_32(Val) - 1;
+      // effectively look for the first one bit after the run of zeros
+      MB = CountLeadingZeros_32((Val - 1) ^ Val) + 1;
+      return true;
+    }
   }
   // no run present
   return false;
@@ -369,9 +374,10 @@ bool PPC32DAGToDAGISel::SelectAddr(SDOperand Addr, SDOperand &Op1,
   if (Addr.getOpcode() == ISD::ADD) {
     if (isIntImmediate(Addr.getOperand(1), imm) && isInt16(imm)) {
       Op1 = getI32Imm(Lo16(imm));
-      if (isa<FrameIndexSDNode>(Addr.getOperand(0))) {
+      if (FrameIndexSDNode *FI =
+            dyn_cast<FrameIndexSDNode>(Addr.getOperand(0))) {
         ++FrameOff;
-        Op2 = Addr.getOperand(0);
+        Op2 = CurDAG->getTargetFrameIndex(FI->getIndex(), MVT::i32);
       } else {
         Op2 = Select(Addr.getOperand(0));
       }
@@ -396,9 +402,9 @@ bool PPC32DAGToDAGISel::SelectAddr(SDOperand Addr, SDOperand &Op1,
         Op2 = CurDAG->getTargetNode(PPC::LIS, MVT::i32, Op1);
       return false;
     }
-  } else if (isa<FrameIndexSDNode>(Addr)) {
+  } else if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Addr)) {
     Op1 = getI32Imm(0);
-    Op2 = Addr;
+    Op2 = CurDAG->getTargetFrameIndex(FI->getIndex(), MVT::i32);
     return false;
   } else if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(Addr)) {
     Op1 = Addr;
@@ -469,7 +475,6 @@ SDOperand PPC32DAGToDAGISel::Select(SDOperand Op) {
     std::cerr << "\n";
     abort();
   case ISD::EntryToken:       // These leaves remain the same.
-  case ISD::UNDEF:
     return Op;
   case ISD::TokenFactor: {
     SDOperand New;
@@ -525,6 +530,43 @@ SDOperand PPC32DAGToDAGISel::Select(SDOperand Op) {
     }
     break;
   }
+  case ISD::ConstantFP: {  // FIXME: this should get sucked into the legalizer
+    MachineConstantPool *CP = CurDAG->getMachineFunction().getConstantPool();
+    Constant *CFP = ConstantFP::get(Type::FloatTy,
+                                    cast<ConstantFPSDNode>(N)->getValue());
+    SDOperand CPN = CurDAG->getConstantPool(CP->getConstantPoolIndex(CFP),
+                                            MVT::i32);
+    SDOperand Tmp;
+    if (PICEnabled)
+      Tmp = CurDAG->getTargetNode(PPC::ADDIS, MVT::i32, getGlobalBaseReg(),CPN);
+    else
+      Tmp = CurDAG->getTargetNode(PPC::LIS, MVT::i32, CPN);
+    CurDAG->SelectNodeTo(N, N->getValueType(0), PPC::LFS, CPN, Tmp);
+    break;
+  }
+  case ISD::UNDEF:
+    if (N->getValueType(0) == MVT::i32)
+      CurDAG->SelectNodeTo(N, MVT::i32, PPC::IMPLICIT_DEF_GPR);
+    else
+      CurDAG->SelectNodeTo(N, N->getValueType(0), PPC::IMPLICIT_DEF_FP);
+    break;
+  case ISD::FrameIndex: {
+    int FI = cast<FrameIndexSDNode>(N)->getIndex();
+    CurDAG->SelectNodeTo(N, MVT::i32, PPC::ADDI,
+                         CurDAG->getTargetFrameIndex(FI, MVT::i32),
+                         getI32Imm(0));
+    break;
+  }
+  case ISD::ConstantPool: {
+    unsigned CPIIdx = cast<ConstantPoolSDNode>(N)->getIndex();
+    SDOperand Tmp, CPI = CurDAG->getTargetConstantPool(CPIIdx, MVT::i32);
+    if (PICEnabled)
+      Tmp = CurDAG->getTargetNode(PPC::ADDIS, MVT::i32, getGlobalBaseReg(),CPI);
+    else
+      Tmp = CurDAG->getTargetNode(PPC::LIS, MVT::i32, CPI);
+    CurDAG->SelectNodeTo(N, MVT::i32, PPC::LA, Tmp, CPI);
+    break;
+  }
   case ISD::GlobalAddress: {
     GlobalValue *GV = cast<GlobalAddressSDNode>(N)->getGlobal();
     SDOperand Tmp;
@@ -653,10 +695,36 @@ SDOperand PPC32DAGToDAGISel::Select(SDOperand Op) {
       case MVT::f32: Opc = PPC::FMULS; break;
       case MVT::f64: Opc = PPC::FMUL;  break;
     }
-    CurDAG->SelectNodeTo(N, N->getValueType(0), Opc, Select(N->getOperand(0)), 
+    CurDAG->SelectNodeTo(N, MVT::i32, Opc, Select(N->getOperand(0)), 
                          Select(N->getOperand(1)));
     break;
   }
+  case ISD::SDIV: {
+    unsigned Imm;
+    if (isIntImmediate(N->getOperand(1), Imm)) {
+      if ((signed)Imm > 0 && isPowerOf2_32(Imm)) {
+        SDOperand Op =
+          CurDAG->getTargetNode(PPC::SRAWI, MVT::i32, MVT::Flag,
+                                Select(N->getOperand(0)),
+                                getI32Imm(Log2_32(Imm)));
+        CurDAG->SelectNodeTo(N, MVT::i32, PPC::ADDZE,
+                             Op.getValue(0), Op.getValue(1));
+        break;
+      } else if ((signed)Imm < 0 && isPowerOf2_32(-Imm)) {
+        SDOperand Op =
+          CurDAG->getTargetNode(PPC::SRAWI, MVT::Flag, MVT::i32,
+                                Select(N->getOperand(0)),
+                                getI32Imm(Log2_32(-Imm)));
+        SDOperand PT =
+          CurDAG->getTargetNode(PPC::ADDZE, MVT::i32, Op.getValue(1),
+                                Op.getValue(0));
+        CurDAG->SelectNodeTo(N, MVT::i32, PPC::NEG, PT);
+        break;
+      }
+    }
+    assert(0 && "SDIV not implemented yet!");
+    abort();
+  }    
   case ISD::MULHS:
     assert(N->getValueType(0) == MVT::i32);
     CurDAG->SelectNodeTo(N, MVT::i32, PPC::MULHW, Select(N->getOperand(0)), 
@@ -917,7 +985,7 @@ SDOperand PPC32DAGToDAGISel::Select(SDOperand Op) {
       case MVT::i16: Opc = isIdx ? PPC::STHX : PPC::STH; break;
       }
     }
-
+    
     CurDAG->SelectNodeTo(N, MVT::Other, Opc, Select(N->getOperand(1)),
                          AddrOp1, AddrOp2, Select(N->getOperand(0)));
     break;
@@ -928,10 +996,106 @@ SDOperand PPC32DAGToDAGISel::Select(SDOperand Op) {
     unsigned Amt = cast<ConstantSDNode>(N->getOperand(1))->getValue();
     unsigned Opc = N->getOpcode() == ISD::CALLSEQ_START ?
                        PPC::ADJCALLSTACKDOWN : PPC::ADJCALLSTACKUP;
-    CurDAG->SelectNodeTo(N, MVT::Other, Opc, Select(N->getOperand(0)),
-                         getI32Imm(Amt));
+    CurDAG->SelectNodeTo(N, MVT::Other, Opc, 
+                         getI32Imm(Amt), Select(N->getOperand(0)));
     break;
   }
+  case ISD::CALL:
+  case ISD::TAILCALL: {
+    SDOperand Chain = Select(N->getOperand(0));
+
+    unsigned CallOpcode;
+    std::vector<SDOperand> CallOperands;
+    
+    if (GlobalAddressSDNode *GASD =
+        dyn_cast<GlobalAddressSDNode>(N->getOperand(1))) {
+      CallOpcode = PPC::CALLpcrel;
+      CallOperands.push_back(CurDAG->getTargetGlobalAddress(GASD->getGlobal(),
+                                                            MVT::i32));
+    } else if (ExternalSymbolSDNode *ESSDN =
+               dyn_cast<ExternalSymbolSDNode>(N->getOperand(1))) {
+      CallOpcode = PPC::CALLpcrel;
+      CallOperands.push_back(N->getOperand(1));
+    } else {
+      // Copy the callee address into the CTR register.
+      SDOperand Callee = Select(N->getOperand(1));
+      Chain = CurDAG->getTargetNode(PPC::MTCTR, MVT::Other, Callee, Chain);
+
+      // Copy the callee address into R12 on darwin.
+      SDOperand R12 = CurDAG->getRegister(PPC::R12, MVT::i32);
+      Chain = CurDAG->getNode(ISD::CopyToReg, MVT::Other, R12, Callee, Chain);
+      
+      CallOperands.push_back(getI32Imm(20));  // Information to encode indcall
+      CallOperands.push_back(getI32Imm(0));   // Information to encode indcall
+      CallOperands.push_back(R12);
+      CallOpcode = PPC::CALLindirect;
+    }
+    
+    unsigned GPR_idx = 0, FPR_idx = 0;
+    static const unsigned GPR[] = {
+      PPC::R3, PPC::R4, PPC::R5, PPC::R6,
+      PPC::R7, PPC::R8, PPC::R9, PPC::R10,
+    };
+    static const unsigned FPR[] = {
+      PPC::F1, PPC::F2, PPC::F3, PPC::F4, PPC::F5, PPC::F6, PPC::F7,
+      PPC::F8, PPC::F9, PPC::F10, PPC::F11, PPC::F12, PPC::F13
+    };
+    
+    for (unsigned i = 2, e = N->getNumOperands(); i != e; ++i)
+      if (N->getOperand(i).getOpcode() != ISD::UNDEF) {
+        unsigned DestReg = 0;
+        MVT::ValueType RegTy;
+        if (N->getOperand(i).getValueType() == MVT::i32) {
+          assert(GPR_idx < 8 && "Too many int args");
+          DestReg = GPR[GPR_idx++];
+          RegTy = MVT::i32;
+        } else {
+          assert(MVT::isFloatingPoint(N->getOperand(i).getValueType()) &&
+                 "Unpromoted integer arg?");
+          assert(FPR_idx < 13 && "Too many fp args");
+          DestReg = FPR[FPR_idx++];
+          RegTy = MVT::f64;   // Even if this is really f32!
+        }
+        
+        SDOperand Reg = CurDAG->getRegister(DestReg, RegTy);
+        Chain = CurDAG->getNode(ISD::CopyToReg, MVT::Other, Chain, Reg,
+                                Select(N->getOperand(i)));
+        CallOperands.push_back(Reg);
+      }
+
+    // Finally, once everything is in registers to pass to the call, emit the
+    // call itself.
+    CallOperands.push_back(Chain);
+    Chain = CurDAG->getTargetNode(CallOpcode, MVT::Other, CallOperands);
+    
+    std::vector<SDOperand> CallResults;
+    
+    // If the call has results, copy the values out of the ret val registers.
+    switch (N->getValueType(0)) {
+    default: assert(0 && "Unexpected ret value!");
+    case MVT::Other: break;
+    case MVT::i32:
+      if (N->getValueType(1) == MVT::i32) {
+        Chain = CurDAG->getCopyFromReg(Chain, PPC::R4, MVT::i32).getValue(1);
+        CallResults.push_back(Chain.getValue(0));
+        Chain = CurDAG->getCopyFromReg(Chain, PPC::R3, MVT::i32).getValue(1);
+        CallResults.push_back(Chain.getValue(0));
+      } else {
+        Chain = CurDAG->getCopyFromReg(Chain, PPC::R3, MVT::i32).getValue(1);
+        CallResults.push_back(Chain.getValue(0));
+      }
+      break;
+    case MVT::f32:
+    case MVT::f64:
+      Chain = CurDAG->getCopyFromReg(Chain, PPC::F1, MVT::f64).getValue(1);
+      CallResults.push_back(Chain.getValue(0));
+      break;
+    }
+    
+    CallResults.push_back(Chain);
+    CurDAG->ReplaceAllUsesWith(N, CallResults);
+    return CallResults[Op.ResNo];
+  }
   case ISD::RET: {
     SDOperand Chain = Select(N->getOperand(0));     // Token chain.
 
@@ -961,7 +1125,10 @@ SDOperand PPC32DAGToDAGISel::Select(SDOperand Op) {
     CurDAG->SelectNodeTo(N, MVT::Other, PPC::BLR, Chain);
     break;
   }
-
+  case ISD::BR:
+    CurDAG->SelectNodeTo(N, MVT::Other, PPC::B, N->getOperand(1),
+                         Select(N->getOperand(0)));
+    break;
   case ISD::BR_CC:
   case ISD::BRTWOWAY_CC: {
     SDOperand Chain = Select(N->getOperand(0));