X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSelectionDAG%2FLegalizeDAG.cpp;h=135045582db63b9ec48516c6bfe786acb6ed5fa3;hb=3becf2026bec881a60cbbe0031d8c51f4d6d4e28;hp=01c88e1a57423b1e3e7fa9ce881dbd52c2491b39;hpb=23993561e24b2a6eaf0e036062522ab825c30d3f;p=oota-llvm.git diff --git a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp index 01c88e1a574..135045582db 100644 --- a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp +++ b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp @@ -1,10 +1,10 @@ //===-- LegalizeDAG.cpp - Implement SelectionDAG::Legalize ----------------===// -// +// // The LLVM Compiler Infrastructure // // This file was developed by the LLVM research group and is distributed under // the University of Illinois Open Source License. See LICENSE.TXT for details. -// +// //===----------------------------------------------------------------------===// // // This file implements the SelectionDAG::Legalize method. @@ -130,6 +130,8 @@ private: void ExpandByParts(unsigned NodeOp, SDOperand LHS, SDOperand RHS, SDOperand &Lo, SDOperand &Hi); + void SpliceCallInto(const SDOperand &CallResult, SDNode *OutChain); + SDOperand getIntPtrConstant(uint64_t Val) { return DAG.getConstant(Val, TLI.getPointerTy()); } @@ -160,12 +162,13 @@ void SelectionDAGLegalize::LegalizeDAG() { SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { assert(getTypeAction(Op.getValueType()) == Legal && "Caller should expand or promote operands that are not legal!"); + SDNode *Node = Op.Val; // If this operation defines any values that cannot be represented in a // register on this target, make sure to expand or promote them. - if (Op.Val->getNumValues() > 1) { - for (unsigned i = 0, e = Op.Val->getNumValues(); i != e; ++i) - switch (getTypeAction(Op.Val->getValueType(i))) { + if (Node->getNumValues() > 1) { + for (unsigned i = 0, e = Node->getNumValues(); i != e; ++i) + switch (getTypeAction(Node->getValueType(i))) { case Legal: break; // Nothing to do. case Expand: { SDOperand T1, T2; @@ -182,13 +185,14 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { } } + // Note that LegalizeOp may be reentered even from single-use nodes, which + // means that we always must cache transformed nodes. std::map::iterator I = LegalizedNodes.find(Op); if (I != LegalizedNodes.end()) return I->second; SDOperand Tmp1, Tmp2, Tmp3; SDOperand Result = Op; - SDNode *Node = Op.Val; switch (Node->getOpcode()) { default: @@ -285,14 +289,15 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { VT = MVT::f32; Extend = true; } - + SDOperand CPIdx = DAG.getConstantPool(CP->getConstantPoolIndex(LLVMC), TLI.getPointerTy()); if (Extend) { Result = DAG.getNode(ISD::EXTLOAD, MVT::f64, DAG.getEntryNode(), CPIdx, - MVT::f32); + DAG.getSrcValue(NULL), MVT::f32); } else { - Result = DAG.getLoad(VT, DAG.getEntryNode(), CPIdx); + Result = DAG.getLoad(VT, DAG.getEntryNode(), CPIdx, + DAG.getSrcValue(NULL)); } } break; @@ -303,6 +308,7 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i) { SDOperand Op = Node->getOperand(i); // Fold single-use TokenFactor nodes into this token factor as we go. + // FIXME: This is something that the DAGCombiner should do!! if (Op.getOpcode() == ISD::TokenFactor && Op.hasOneUse()) { Changed = true; for (unsigned j = 0, e = Op.getNumOperands(); j != e; ++j) @@ -321,9 +327,22 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { case ISD::ADJCALLSTACKUP: Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. // There is no need to legalize the size argument (Operand #1) - if (Tmp1 != Node->getOperand(0)) - Result = DAG.getNode(Node->getOpcode(), MVT::Other, Tmp1, - Node->getOperand(1)); + Tmp2 = Node->getOperand(0); + if (Tmp1 != Tmp2) { + Node->setAdjCallChain(Tmp1); + + // If moving the operand from pointing to Tmp2 dropped its use count to 1, + // this will cause the maps used to memoize results to get confused. + // Create and add a dummy use, just to increase its use count. This will + // be removed at the end of legalize when dead nodes are removed. + if (Tmp2.Val->hasOneUse()) + DAG.getNode(ISD::PCMARKER, MVT::Other, Tmp2, + DAG.getConstant(0, MVT::i32)); + } + // Note that we do not create new ADJCALLSTACK DOWN/UP nodes here. These + // nodes are treated specially and are mutated in place. This makes the dag + // legalization process more efficient and also makes libcall insertion + // easier. break; case ISD::DYNAMIC_STACKALLOC: Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. @@ -428,12 +447,14 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { case ISD::LOAD: Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. + if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) - Result = DAG.getLoad(Node->getValueType(0), Tmp1, Tmp2); + Result = DAG.getLoad(Node->getValueType(0), Tmp1, Tmp2, + Node->getOperand(2)); else Result = SDOperand(Node, 0); - + // Since loads produce two values, make sure to remember that we legalized // both of them. AddLegalizedOperand(SDOperand(Node, 0), Result); @@ -452,18 +473,18 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { case TargetLowering::Promote: assert(SrcVT == MVT::i1 && "Can only promote EXTLOAD from i1 -> i8!"); Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), - Tmp1, Tmp2, MVT::i8); + Tmp1, Tmp2, Node->getOperand(2), MVT::i8); // Since loads produce two values, make sure to remember that we legalized // both of them. AddLegalizedOperand(SDOperand(Node, 0), Result); AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); return Result.getValue(Op.ResNo); - + case TargetLowering::Legal: if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), - Tmp1, Tmp2, SrcVT); + Tmp1, Tmp2, Node->getOperand(2), SrcVT); else Result = SDOperand(Node, 0); @@ -478,7 +499,7 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { // Turn the unsupported load into an EXTLOAD followed by an explicit // zero/sign extend inreg. Result = DAG.getNode(ISD::EXTLOAD, Node->getValueType(0), - Tmp1, Tmp2, SrcVT); + Tmp1, Tmp2, Node->getOperand(2), SrcVT); SDOperand ValRes; if (Node->getOpcode() == ISD::SEXTLOAD) ValRes = DAG.getNode(ISD::SIGN_EXTEND_INREG, Result.getValueType(), @@ -504,7 +525,7 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { case ISD::CopyToReg: Tmp1 = LegalizeOp(Node->getOperand(0)); // Legalize the chain. - + switch (getTypeAction(Node->getOperand(1).getValueType())) { case Legal: // Legalize the incoming value (must be legal). @@ -518,7 +539,7 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { break; case Expand: SDOperand Lo, Hi; - ExpandOp(Node->getOperand(1), Lo, Hi); + ExpandOp(Node->getOperand(1), Lo, Hi); unsigned Reg = cast(Node)->getReg(); Lo = DAG.getCopyToReg(Tmp1, Lo, Reg); Hi = DAG.getCopyToReg(Tmp1, Hi, Reg+1); @@ -544,7 +565,7 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { SDOperand Lo, Hi; ExpandOp(Node->getOperand(1), Lo, Hi); Result = DAG.getNode(ISD::RET, MVT::Other, Tmp1, Lo, Hi); - break; + break; } case Promote: Tmp2 = PromoteOp(Node->getOperand(1)); @@ -569,7 +590,7 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { ExpandOp(Node->getOperand(i), Lo, Hi); NewValues.push_back(Lo); NewValues.push_back(Hi); - break; + break; } case Promote: assert(0 && "Can't promote multiple return value yet!"); @@ -591,8 +612,9 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { float F; } V; V.F = CFP->getValue(); - Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, - DAG.getConstant(V.I, MVT::i32), Tmp2); + Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, + DAG.getConstant(V.I, MVT::i32), Tmp2, + Node->getOperand(3)); } else { assert(CFP->getValueType(0) == MVT::f64 && "Unknown FP type!"); union { @@ -600,8 +622,9 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { double F; } V; V.F = CFP->getValue(); - Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, - DAG.getConstant(V.I, MVT::i64), Tmp2); + Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, + DAG.getConstant(V.I, MVT::i64), Tmp2, + Node->getOperand(3)); } Node = Result.Val; } @@ -611,14 +634,16 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { SDOperand Val = LegalizeOp(Node->getOperand(1)); if (Val != Node->getOperand(1) || Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(2)) - Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Val, Tmp2); + Result = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Val, Tmp2, + Node->getOperand(3)); break; } case Promote: // Truncate the value and store the result. Tmp3 = PromoteOp(Node->getOperand(1)); Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp3, Tmp2, - Node->getOperand(1).getValueType()); + Node->getOperand(3), + Node->getOperand(1).getValueType()); break; case Expand: @@ -628,14 +653,16 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { if (!TLI.isLittleEndian()) std::swap(Lo, Hi); - Lo = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Lo, Tmp2); - + Lo = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Lo, Tmp2, + Node->getOperand(3)); unsigned IncrementSize = MVT::getSizeInBits(Hi.getValueType())/8; Tmp2 = DAG.getNode(ISD::ADD, Tmp2.getValueType(), Tmp2, getIntPtrConstant(IncrementSize)); assert(isTypeLegal(Tmp2.getValueType()) && "Pointers must be legal!"); - Hi = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Hi, Tmp2); + //Again, claiming both parts of the store came form the same Instr + Hi = DAG.getNode(ISD::STORE, MVT::Other, Tmp1, Hi, Tmp2, + Node->getOperand(3)); Result = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo, Hi); break; } @@ -655,6 +682,7 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || Tmp3 != Node->getOperand(2)) Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, Tmp1, Tmp2, Tmp3, + Node->getOperand(3), cast(Node)->getExtraValueType()); break; case Promote: @@ -753,7 +781,7 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { Result = DAG.getSetCC(cast(Node)->getCondition(), Node->getValueType(0), Tmp1, Tmp2); break; - case Expand: + case Expand: SDOperand LHSLo, LHSHi, RHSLo, RHSHi; ExpandOp(Node->getOperand(0), LHSLo, LHSHi); ExpandOp(Node->getOperand(1), RHSLo, RHSHi); @@ -765,15 +793,15 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { if (RHSCST->isAllOnesValue()) { // Comparison to -1. Tmp1 = DAG.getNode(ISD::AND, LHSLo.getValueType(), LHSLo, LHSHi); - Result = DAG.getSetCC(cast(Node)->getCondition(), + Result = DAG.getSetCC(cast(Node)->getCondition(), Node->getValueType(0), Tmp1, RHSLo); - break; + break; } Tmp1 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSLo, RHSLo); Tmp2 = DAG.getNode(ISD::XOR, LHSLo.getValueType(), LHSHi, RHSHi); Tmp1 = DAG.getNode(ISD::OR, Tmp1.getValueType(), Tmp1, Tmp2); - Result = DAG.getSetCC(cast(Node)->getCondition(), + Result = DAG.getSetCC(cast(Node)->getCondition(), Node->getValueType(0), Tmp1, DAG.getConstant(0, Tmp1.getValueType())); break; @@ -781,7 +809,7 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { // If this is a comparison of the sign bit, just look at the top part. // X > -1, x < 0 if (ConstantSDNode *CST = dyn_cast(Node->getOperand(1))) - if ((cast(Node)->getCondition() == ISD::SETLT && + if ((cast(Node)->getCondition() == ISD::SETLT && CST->getValue() == 0) || // X < 0 (cast(Node)->getCondition() == ISD::SETGT && (CST->isAllOnesValue()))) // X > -1 @@ -801,7 +829,7 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { case ISD::SETGE: case ISD::SETUGE: LowCC = ISD::SETUGE; break; } - + // Tmp1 = lo(op1) < lo(op2) // Always unsigned comparison // Tmp2 = hi(op1) < hi(op2) // Signedness depends on operands // dest = hi(op1) == hi(op2) ? Tmp1 : Tmp2; @@ -836,7 +864,7 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { break; } } else { - Tmp3 = LegalizeOp(Node->getOperand(2)); // memcpy/move = pointer, + Tmp3 = LegalizeOp(Node->getOperand(2)); // memcpy/move = pointer, } SDOperand Tmp4; @@ -898,6 +926,7 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { } else { assert(0 && "Unknown op!"); } + std::pair CallResult = TLI.LowerCallTo(Tmp1, Type::VoidTy, false, DAG.getExternalSymbol(FnName, IntPtr), Args, DAG); @@ -915,6 +944,81 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { } break; } + + case ISD::READPORT: + Tmp1 = LegalizeOp(Node->getOperand(0)); + Tmp2 = LegalizeOp(Node->getOperand(1)); + + if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) + Result = DAG.getNode(ISD::READPORT, Node->getValueType(0), Tmp1, Tmp2); + else + Result = SDOperand(Node, 0); + // Since these produce two values, make sure to remember that we legalized + // both of them. + AddLegalizedOperand(SDOperand(Node, 0), Result); + AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); + return Result.getValue(Op.ResNo); + case ISD::WRITEPORT: + Tmp1 = LegalizeOp(Node->getOperand(0)); + Tmp2 = LegalizeOp(Node->getOperand(1)); + Tmp3 = LegalizeOp(Node->getOperand(2)); + if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || + Tmp3 != Node->getOperand(2)) + Result = DAG.getNode(Node->getOpcode(), MVT::Other, Tmp1, Tmp2, Tmp3); + break; + + case ISD::READIO: + Tmp1 = LegalizeOp(Node->getOperand(0)); + Tmp2 = LegalizeOp(Node->getOperand(1)); + + switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) { + case TargetLowering::Custom: + default: assert(0 && "This action not implemented for this operation!"); + case TargetLowering::Legal: + if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) + Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), + Tmp1, Tmp2); + else + Result = SDOperand(Node, 0); + break; + case TargetLowering::Expand: + // Replace this with a load from memory. + Result = DAG.getLoad(Node->getValueType(0), Node->getOperand(0), + Node->getOperand(1), DAG.getSrcValue(NULL)); + Result = LegalizeOp(Result); + break; + } + + // Since these produce two values, make sure to remember that we legalized + // both of them. + AddLegalizedOperand(SDOperand(Node, 0), Result); + AddLegalizedOperand(SDOperand(Node, 1), Result.getValue(1)); + return Result.getValue(Op.ResNo); + + case ISD::WRITEIO: + Tmp1 = LegalizeOp(Node->getOperand(0)); + Tmp2 = LegalizeOp(Node->getOperand(1)); + Tmp3 = LegalizeOp(Node->getOperand(2)); + + switch (TLI.getOperationAction(Node->getOpcode(), + Node->getOperand(1).getValueType())) { + case TargetLowering::Custom: + default: assert(0 && "This action not implemented for this operation!"); + case TargetLowering::Legal: + if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1) || + Tmp3 != Node->getOperand(2)) + Result = DAG.getNode(Node->getOpcode(), MVT::Other, Tmp1, Tmp2, Tmp3); + break; + case TargetLowering::Expand: + // Replace this with a store to memory. + Result = DAG.getNode(ISD::STORE, MVT::Other, Node->getOperand(0), + Node->getOperand(1), Node->getOperand(2), + DAG.getSrcValue(NULL)); + Result = LegalizeOp(Result); + break; + } + break; + case ISD::ADD_PARTS: case ISD::SUB_PARTS: case ISD::SHL_PARTS: @@ -956,7 +1060,7 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { Tmp2 != Node->getOperand(1)) Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1,Tmp2); break; - + case ISD::UREM: case ISD::SREM: Tmp1 = LegalizeOp(Node->getOperand(0)); // LHS @@ -965,7 +1069,7 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { case TargetLowering::Legal: if (Tmp1 != Node->getOperand(0) || Tmp2 != Node->getOperand(1)) - Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1, + Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1, Tmp2); break; case TargetLowering::Promote: @@ -982,9 +1086,129 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { } break; + case ISD::CTPOP: + case ISD::CTTZ: + case ISD::CTLZ: + Tmp1 = LegalizeOp(Node->getOperand(0)); // Op + switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) { + case TargetLowering::Legal: + if (Tmp1 != Node->getOperand(0)) + Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1); + break; + case TargetLowering::Promote: { + MVT::ValueType OVT = Tmp1.getValueType(); + MVT::ValueType NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), OVT); + + // Zero extend the argument. + Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1); + // Perform the larger operation, then subtract if needed. + Tmp1 = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1); + switch(Node->getOpcode()) + { + case ISD::CTPOP: + Result = Tmp1; + break; + case ISD::CTTZ: + //if Tmp1 == sizeinbits(NVT) then Tmp1 = sizeinbits(Old VT) + Tmp2 = DAG.getSetCC(ISD::SETEQ, TLI.getSetCCResultTy(), Tmp1, + DAG.getConstant(getSizeInBits(NVT), NVT)); + Result = DAG.getNode(ISD::SELECT, NVT, Tmp2, + DAG.getConstant(getSizeInBits(OVT),NVT), Tmp1); + break; + case ISD::CTLZ: + //Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT)) + Result = DAG.getNode(ISD::SUB, NVT, Tmp1, + DAG.getConstant(getSizeInBits(NVT) - + getSizeInBits(OVT), NVT)); + break; + } + break; + } + case TargetLowering::Custom: + assert(0 && "Cannot custom handle this yet!"); + case TargetLowering::Expand: + switch(Node->getOpcode()) + { + case ISD::CTPOP: { + static const uint64_t mask[6] = { + 0x5555555555555555ULL, 0x3333333333333333ULL, + 0x0F0F0F0F0F0F0F0FULL, 0x00FF00FF00FF00FFULL, + 0x0000FFFF0000FFFFULL, 0x00000000FFFFFFFFULL + }; + MVT::ValueType VT = Tmp1.getValueType(); + MVT::ValueType ShVT = TLI.getShiftAmountTy(); + unsigned len = getSizeInBits(VT); + for (unsigned i = 0; (1U << i) <= (len / 2); ++i) { + //x = (x & mask[i][len/8]) + (x >> (1 << i) & mask[i][len/8]) + Tmp2 = DAG.getConstant(mask[i], VT); + Tmp3 = DAG.getConstant(1ULL << i, ShVT); + Tmp1 = DAG.getNode(ISD::ADD, VT, + DAG.getNode(ISD::AND, VT, Tmp1, Tmp2), + DAG.getNode(ISD::AND, VT, + DAG.getNode(ISD::SRL, VT, Tmp1, Tmp3), + Tmp2)); + } + Result = Tmp1; + break; + } + case ISD::CTLZ: { + /* for now, we do this: + x = x | (x >> 1); + x = x | (x >> 2); + ... + x = x | (x >>16); + x = x | (x >>32); // for 64-bit input + return popcount(~x); + + but see also: http://www.hackersdelight.org/HDcode/nlz.cc */ + MVT::ValueType VT = Tmp1.getValueType(); + MVT::ValueType ShVT = TLI.getShiftAmountTy(); + unsigned len = getSizeInBits(VT); + for (unsigned i = 0; (1U << i) <= (len / 2); ++i) { + Tmp3 = DAG.getConstant(1ULL << i, ShVT); + Tmp1 = DAG.getNode(ISD::OR, VT, Tmp1, + DAG.getNode(ISD::SRL, VT, Tmp1, Tmp3)); + } + Tmp3 = DAG.getNode(ISD::XOR, VT, Tmp1, DAG.getConstant(~0ULL, VT)); + Result = LegalizeOp(DAG.getNode(ISD::CTPOP, VT, Tmp3)); + break; + } + case ISD::CTTZ: { + // for now, we use: { return popcount(~x & (x - 1)); } + // unless the target has ctlz but not ctpop, in which case we use: + // { return 32 - nlz(~x & (x-1)); } + // see also http://www.hackersdelight.org/HDcode/ntz.cc + MVT::ValueType VT = Tmp1.getValueType(); + Tmp2 = DAG.getConstant(~0ULL, VT); + Tmp3 = DAG.getNode(ISD::AND, VT, + DAG.getNode(ISD::XOR, VT, Tmp1, Tmp2), + DAG.getNode(ISD::SUB, VT, Tmp1, + DAG.getConstant(1, VT))); + // If ISD::CTLZ is legal and CTPOP isn't, then do that instead + if (TLI.getOperationAction(ISD::CTPOP, VT) != TargetLowering::Legal && + TLI.getOperationAction(ISD::CTLZ, VT) == TargetLowering::Legal) { + Result = LegalizeOp(DAG.getNode(ISD::SUB, VT, + DAG.getConstant(getSizeInBits(VT), VT), + DAG.getNode(ISD::CTLZ, VT, Tmp3))); + } else { + Result = LegalizeOp(DAG.getNode(ISD::CTPOP, VT, Tmp3)); + } + break; + } + default: + assert(0 && "Cannot expand this yet!"); + break; + } + break; + } + break; + // Unary operators case ISD::FABS: case ISD::FNEG: + case ISD::FSQRT: + case ISD::FSIN: + case ISD::FCOS: Tmp1 = LegalizeOp(Node->getOperand(0)); switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) { case TargetLowering::Legal: @@ -995,12 +1219,15 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { case TargetLowering::Custom: assert(0 && "Cannot promote/custom handle this yet!"); case TargetLowering::Expand: - if (Node->getOpcode() == ISD::FNEG) { + switch(Node->getOpcode()) { + case ISD::FNEG: { // Expand Y = FNEG(X) -> Y = SUB -0.0, X Tmp2 = DAG.getConstantFP(-0.0, Node->getValueType(0)); Result = LegalizeOp(DAG.getNode(ISD::SUB, Node->getValueType(0), Tmp2, Tmp1)); - } else if (Node->getOpcode() == ISD::FABS) { + break; + } + case ISD::FABS: { // Expand Y = FABS(X) -> Y = (X >u 0.0) ? X : fneg(X). MVT::ValueType VT = Node->getValueType(0); Tmp2 = DAG.getConstantFP(0.0, VT); @@ -1008,7 +1235,30 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { Tmp3 = DAG.getNode(ISD::FNEG, VT, Tmp1); Result = DAG.getNode(ISD::SELECT, VT, Tmp2, Tmp1, Tmp3); Result = LegalizeOp(Result); - } else { + break; + } + case ISD::FSQRT: + case ISD::FSIN: + case ISD::FCOS: { + MVT::ValueType VT = Node->getValueType(0); + Type *T = VT == MVT::f32 ? Type::FloatTy : Type::DoubleTy; + const char *FnName = 0; + switch(Node->getOpcode()) { + case ISD::FSQRT: FnName = VT == MVT::f32 ? "sqrtf" : "sqrt"; break; + case ISD::FSIN: FnName = VT == MVT::f32 ? "sinf" : "sin"; break; + case ISD::FCOS: FnName = VT == MVT::f32 ? "cosf" : "cos"; break; + default: assert(0 && "Unreachable!"); + } + std::vector > Args; + Args.push_back(std::make_pair(Tmp1, T)); + // FIXME: should use ExpandLibCall! + std::pair CallResult = + TLI.LowerCallTo(DAG.getEntryNode(), T, false, + DAG.getExternalSymbol(FnName, VT), Args, DAG); + Result = LegalizeOp(CallResult.first); + break; + } + default: assert(0 && "Unreachable!"); } break; @@ -1036,13 +1286,12 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { Node->getOpcode() == ISD::UINT_TO_FP) { Result = ExpandIntToFP(Node->getOpcode() == ISD::SINT_TO_FP, Node->getValueType(0), Node->getOperand(0)); - Result = LegalizeOp(Result); break; } else if (Node->getOpcode() == ISD::TRUNCATE) { // In the expand case, we must be dealing with a truncate, because // otherwise the result would be larger than the source. ExpandOp(Node->getOperand(0), Tmp1, Tmp2); - + // Since the result is legal, we should just be able to truncate the low // part of the source. Result = DAG.getNode(ISD::TRUNCATE, Node->getValueType(0), Tmp1); @@ -1134,13 +1383,14 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { unsigned TySize = (unsigned)TLI.getTargetData().getTypeSize(Ty); unsigned Align = TLI.getTargetData().getTypeAlignment(Ty); MachineFunction &MF = DAG.getMachineFunction(); - int SSFI = + int SSFI = MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align); SDOperand StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy()); Result = DAG.getNode(ISD::TRUNCSTORE, MVT::Other, DAG.getEntryNode(), - Node->getOperand(0), StackSlot, ExtraVT); + Node->getOperand(0), StackSlot, + DAG.getSrcValue(NULL), ExtraVT); Result = DAG.getNode(ISD::EXTLOAD, Node->getValueType(0), - Result, StackSlot, ExtraVT); + Result, StackSlot, DAG.getSrcValue(NULL), ExtraVT); } else { assert(0 && "Unknown op"); } @@ -1151,9 +1401,9 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) { } } - if (!Op.Val->hasOneUse()) - AddLegalizedOperand(Op, Result); - + // Note that LegalizeOp may be reentered even from single-use nodes, which + // means that we always must cache transformed nodes. + AddLegalizedOperand(Op, Result); return Result; } @@ -1169,14 +1419,18 @@ SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) { assert(NVT > VT && MVT::isInteger(NVT) == MVT::isInteger(VT) && "Cannot promote to smaller type!"); - std::map::iterator I = PromotedNodes.find(Op); - if (I != PromotedNodes.end()) return I->second; - SDOperand Tmp1, Tmp2, Tmp3; SDOperand Result; SDNode *Node = Op.Val; + if (!Node->hasOneUse()) { + std::map::iterator I = PromotedNodes.find(Op); + if (I != PromotedNodes.end()) return I->second; + } else { + assert(!PromotedNodes.count(Op) && "Repromoted this node??"); + } + // Promotion needs an optimization step to clean up after it, and is not // careful to avoid operations the target does not support. Make sure that // all generated operations are legalized in the next iteration. @@ -1231,7 +1485,7 @@ SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) { case Expand: ExpandOp(Node->getOperand(0), Tmp1, Tmp2); // Truncate the low part of the expanded value to the result type - Result = DAG.getNode(ISD::TRUNCATE, VT, Tmp1); + Result = DAG.getNode(ISD::TRUNCATE, VT, Tmp1); } break; case ISD::SIGN_EXTEND: @@ -1294,8 +1548,6 @@ SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) { case Expand: Result = ExpandIntToFP(Node->getOpcode() == ISD::SINT_TO_FP, NVT, Node->getOperand(0)); - Result = LegalizeOp(Result); - // Round if we cannot tolerate excess precision. if (NoExcessFPPrecision) Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT); @@ -1330,6 +1582,16 @@ SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) { // precision, and these operations don't modify precision at all. break; + case ISD::FSQRT: + case ISD::FSIN: + case ISD::FCOS: + Tmp1 = PromoteOp(Node->getOperand(0)); + assert(Tmp1.getValueType() == NVT); + Result = DAG.getNode(Node->getOpcode(), NVT, Tmp1); + if(NoExcessFPPrecision) + Result = DAG.getNode(ISD::FP_ROUND_INREG, NVT, Result, VT); + break; + case ISD::AND: case ISD::OR: case ISD::XOR: @@ -1404,9 +1666,11 @@ SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) { Tmp2 = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. // FIXME: When the DAG combiner exists, change this to use EXTLOAD! if (MVT::isInteger(NVT)) - Result = DAG.getNode(ISD::ZEXTLOAD, NVT, Tmp1, Tmp2, VT); + Result = DAG.getNode(ISD::ZEXTLOAD, NVT, Tmp1, Tmp2, Node->getOperand(2), + VT); else - Result = DAG.getNode(ISD::EXTLOAD, NVT, Tmp1, Tmp2, VT); + Result = DAG.getNode(ISD::EXTLOAD, NVT, Tmp1, Tmp2, Node->getOperand(2), + VT); // Remember that we legalized the chain. AddLegalizedOperand(Op.getValue(1), Result.getValue(1)); @@ -1445,7 +1709,35 @@ SDOperand SelectionDAGLegalize::PromoteOp(SDOperand Op) { // Insert the new chain mapping. AddLegalizedOperand(Op.getValue(1), Result.getValue(1)); break; - } + } + case ISD::CTPOP: + case ISD::CTTZ: + case ISD::CTLZ: + Tmp1 = Node->getOperand(0); + //Zero extend the argument + Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1); + // Perform the larger operation, then subtract if needed. + Tmp1 = DAG.getNode(Node->getOpcode(), NVT, Tmp1); + switch(Node->getOpcode()) + { + case ISD::CTPOP: + Result = Tmp1; + break; + case ISD::CTTZ: + //if Tmp1 == sizeinbits(NVT) then Tmp1 = sizeinbits(Old VT) + Tmp2 = DAG.getSetCC(ISD::SETEQ, MVT::i1, Tmp1, + DAG.getConstant(getSizeInBits(NVT), NVT)); + Result = DAG.getNode(ISD::SELECT, NVT, Tmp2, + DAG.getConstant(getSizeInBits(VT),NVT), Tmp1); + break; + case ISD::CTLZ: + //Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT)) + Result = DAG.getNode(ISD::SUB, NVT, Tmp1, + DAG.getConstant(getSizeInBits(NVT) - + getSizeInBits(VT), NVT)); + break; + } + break; } assert(Result.Val && "Didn't set a result!"); @@ -1568,16 +1860,16 @@ bool SelectionDAGLegalize::ExpandShift(unsigned Opc, SDOperand Op,SDOperand Amt, return true; case ISD::SRA: if (Cst > VTBits) { - Hi = Lo = DAG.getNode(ISD::SRA, NVT, InH, + Hi = Lo = DAG.getNode(ISD::SRA, NVT, InH, DAG.getConstant(NVTBits-1, ShTy)); } else if (Cst > NVTBits) { - Lo = DAG.getNode(ISD::SRA, NVT, InH, + Lo = DAG.getNode(ISD::SRA, NVT, InH, DAG.getConstant(Cst-NVTBits, ShTy)); - Hi = DAG.getNode(ISD::SRA, NVT, InH, + Hi = DAG.getNode(ISD::SRA, NVT, InH, DAG.getConstant(NVTBits-1, ShTy)); } else if (Cst == NVTBits) { Lo = InH; - Hi = DAG.getNode(ISD::SRA, NVT, InH, + Hi = DAG.getNode(ISD::SRA, NVT, InH, DAG.getConstant(NVTBits-1, ShTy)); } else { Lo = DAG.getNode(ISD::OR, NVT, @@ -1620,7 +1912,7 @@ bool SelectionDAGLegalize::ExpandShift(unsigned Opc, SDOperand Op,SDOperand Amt, DAG.getNode(ISD::SHL, NVT, InH, ShAmt), DAG.getNode(ISD::SRL, NVT, InL, NAmt)); SDOperand T2 = DAG.getNode(ISD::SHL, NVT, InL, ShAmt); // T2 = Lo << Amt&31 - + Hi = DAG.getNode(ISD::SELECT, NVT, Cond, T2, T1); Lo = DAG.getNode(ISD::SELECT, NVT, Cond, DAG.getConstant(0, NVT), T2); } else { @@ -1705,14 +1997,14 @@ static SDNode *FindAdjCallStackUp(SDNode *Node) { if (Node->hasOneUse()) // Simple case, only has one user to check. return FindAdjCallStackUp(*Node->use_begin()); - + SDOperand TheChain(Node, Node->getNumValues()-1); assert(TheChain.getValueType() == MVT::Other && "Is not a token chain!"); - - for (SDNode::use_iterator UI = Node->use_begin(), + + for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end(); ; ++UI) { assert(UI != E && "Didn't find a user of the tokchain, no ADJCALLSTACKUP!"); - + // Make sure to only follow users of our token chain. SDNode *User = *UI; for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i) @@ -1723,16 +2015,31 @@ static SDNode *FindAdjCallStackUp(SDNode *Node) { abort(); } +/// FindAdjCallStackDown - Given a chained node that is part of a call sequence, +/// find the ADJCALLSTACKDOWN node that initiates the call sequence. +static SDNode *FindAdjCallStackDown(SDNode *Node) { + assert(Node && "Didn't find adjcallstackdown for a call??"); + if (Node->getOpcode() == ISD::ADJCALLSTACKDOWN) return Node; + + assert(Node->getOperand(0).getValueType() == MVT::Other && + "Node doesn't have a token chain argument!"); + return FindAdjCallStackDown(Node->getOperand(0).Val); +} + + /// FindInputOutputChains - If we are replacing an operation with a call we need /// to find the call that occurs before and the call that occurs after it to -/// properly serialize the calls in the block. +/// properly serialize the calls in the block. The returned operand is the +/// input chain value for the new call (e.g. the entry node or the previous +/// call), and OutChain is set to be the chain node to update to point to the +/// end of the call chain. static SDOperand FindInputOutputChains(SDNode *OpNode, SDNode *&OutChain, SDOperand Entry) { SDNode *LatestAdjCallStackDown = Entry.Val; SDNode *LatestAdjCallStackUp = 0; FindLatestAdjCallStackDown(OpNode, LatestAdjCallStackDown); - //std::cerr << "Found node: "; LatestAdjCallStackDown->dump(); std::cerr <<"\n"; - + //std::cerr<<"Found node: "; LatestAdjCallStackDown->dump(); std::cerr <<"\n"; + // It is possible that no ISD::ADJCALLSTACKDOWN was found because there is no // previous call in the function. LatestCallStackDown may in that case be // the entry node itself. Do not attempt to find a matching ADJCALLSTACKUP @@ -1742,18 +2049,34 @@ static SDOperand FindInputOutputChains(SDNode *OpNode, SDNode *&OutChain, else LatestAdjCallStackUp = Entry.Val; assert(LatestAdjCallStackUp && "NULL return from FindAdjCallStackUp"); - - SDNode *EarliestAdjCallStackUp = 0; - FindEarliestAdjCallStackUp(OpNode, EarliestAdjCallStackUp); - if (EarliestAdjCallStackUp) { - //std::cerr << "Found node: "; - //EarliestAdjCallStackUp->dump(); std::cerr <<"\n"; - } + // Finally, find the first call that this must come before, first we find the + // adjcallstackup that ends the call. + OutChain = 0; + FindEarliestAdjCallStackUp(OpNode, OutChain); + + // If we found one, translate from the adj up to the adjdown. + if (OutChain) + OutChain = FindAdjCallStackDown(OutChain); return SDOperand(LatestAdjCallStackUp, 0); } +/// SpliceCallInto - Given the result chain of a libcall (CallResult), and a +void SelectionDAGLegalize::SpliceCallInto(const SDOperand &CallResult, + SDNode *OutChain) { + // Nothing to splice it into? + if (OutChain == 0) return; + + assert(OutChain->getOperand(0).getValueType() == MVT::Other); + //OutChain->dump(); + + // Form a token factor node merging the old inval and the new inval. + SDOperand InToken = DAG.getNode(ISD::TokenFactor, MVT::Other, CallResult, + OutChain->getOperand(0)); + // Change the node to refer to the new token. + OutChain->setAdjCallChain(InToken); +} // ExpandLibCall - Expand a node into a call to a libcall. If the result value @@ -1775,22 +2098,24 @@ SDOperand SelectionDAGLegalize::ExpandLibCall(const char *Name, SDNode *Node, Args.push_back(std::make_pair(Node->getOperand(i), ArgTy)); } SDOperand Callee = DAG.getExternalSymbol(Name, TLI.getPointerTy()); - - // We don't care about token chains for libcalls. We just use the entry - // node as our input and ignore the output chain. This allows us to place - // calls wherever we need them to satisfy data dependences. + + // Splice the libcall in wherever FindInputOutputChains tells us to. const Type *RetTy = MVT::getTypeForValueType(Node->getValueType(0)); - SDOperand Result = TLI.LowerCallTo(InChain, RetTy, false, Callee, - Args, DAG).first; - switch (getTypeAction(Result.getValueType())) { + std::pair CallInfo = + TLI.LowerCallTo(InChain, RetTy, false, Callee, Args, DAG); + SpliceCallInto(CallInfo.second, OutChain); + + NeedsAnotherIteration = true; + + switch (getTypeAction(CallInfo.first.getValueType())) { default: assert(0 && "Unknown thing"); case Legal: - return Result; + return CallInfo.first; case Promote: assert(0 && "Cannot promote this yet!"); case Expand: SDOperand Lo; - ExpandOp(Result, Lo, Hi); + ExpandOp(CallInfo.first, Lo, Hi); return Lo; } } @@ -1805,39 +2130,80 @@ ExpandIntToFP(bool isSigned, MVT::ValueType DestTy, SDOperand Source) { "This is not an expansion!"); assert(Source.getValueType() == MVT::i64 && "Only handle expand from i64!"); - SDNode *OutChain; - SDOperand InChain = FindInputOutputChains(Source.Val, OutChain, - DAG.getEntryNode()); - - const char *FnName = 0; - if (isSigned) { + if (!isSigned) { + // If this is unsigned, and not supported, first perform the conversion to + // signed, then adjust the result if the sign bit is set. + SDOperand SignedConv = ExpandIntToFP(true, DestTy, Source); + + assert(Source.getValueType() == MVT::i64 && + "This only works for 64-bit -> FP"); + // The 64-bit value loaded will be incorrectly if the 'sign bit' of the + // incoming integer is set. To handle this, we dynamically test to see if + // it is set, and, if so, add a fudge factor. + SDOperand Lo, Hi; + ExpandOp(Source, Lo, Hi); + + SDOperand SignSet = DAG.getSetCC(ISD::SETLT, TLI.getSetCCResultTy(), Hi, + DAG.getConstant(0, Hi.getValueType())); + SDOperand Zero = getIntPtrConstant(0), Four = getIntPtrConstant(4); + SDOperand CstOffset = DAG.getNode(ISD::SELECT, Zero.getValueType(), + SignSet, Four, Zero); + uint64_t FF = 0x5f800000ULL; + if (TLI.isLittleEndian()) FF <<= 32; + static Constant *FudgeFactor = ConstantUInt::get(Type::ULongTy, FF); + + MachineConstantPool *CP = DAG.getMachineFunction().getConstantPool(); + SDOperand CPIdx = DAG.getConstantPool(CP->getConstantPoolIndex(FudgeFactor), + TLI.getPointerTy()); + CPIdx = DAG.getNode(ISD::ADD, TLI.getPointerTy(), CPIdx, CstOffset); + SDOperand FudgeInReg; if (DestTy == MVT::f32) - FnName = "__floatdisf"; + FudgeInReg = DAG.getLoad(MVT::f32, DAG.getEntryNode(), CPIdx, + DAG.getSrcValue(NULL)); else { - assert(DestTy == MVT::f64 && "Unknown fp value type!"); - FnName = "__floatdidf"; + assert(DestTy == MVT::f64 && "Unexpected conversion"); + FudgeInReg = DAG.getNode(ISD::EXTLOAD, MVT::f64, DAG.getEntryNode(), + CPIdx, DAG.getSrcValue(NULL), MVT::f32); } - } else { - // If this is unsigned, and not supported, first perform the conversion to - // signed, then adjust the result if the sign bit is set. - SDOperand SignedConv = ExpandIntToFP(false, DestTy, Source); + return DAG.getNode(ISD::ADD, DestTy, SignedConv, FudgeInReg); + } + + // Expand the source, then glue it back together for the call. We must expand + // the source in case it is shared (this pass of legalize must traverse it). + SDOperand SrcLo, SrcHi; + ExpandOp(Source, SrcLo, SrcHi); + Source = DAG.getNode(ISD::BUILD_PAIR, Source.getValueType(), SrcLo, SrcHi); - assert(0 && "Unsigned casts not supported yet!"); + SDNode *OutChain = 0; + SDOperand InChain = FindInputOutputChains(Source.Val, OutChain, + DAG.getEntryNode()); + const char *FnName = 0; + if (DestTy == MVT::f32) + FnName = "__floatdisf"; + else { + assert(DestTy == MVT::f64 && "Unknown fp value type!"); + FnName = "__floatdidf"; } + SDOperand Callee = DAG.getExternalSymbol(FnName, TLI.getPointerTy()); TargetLowering::ArgListTy Args; const Type *ArgTy = MVT::getTypeForValueType(Source.getValueType()); + Args.push_back(std::make_pair(Source, ArgTy)); // We don't care about token chains for libcalls. We just use the entry // node as our input and ignore the output chain. This allows us to place // calls wherever we need them to satisfy data dependences. const Type *RetTy = MVT::getTypeForValueType(DestTy); - return TLI.LowerCallTo(InChain, RetTy, false, Callee, Args, DAG).first; - + + std::pair CallResult = + TLI.LowerCallTo(InChain, RetTy, false, Callee, Args, DAG); + + SpliceCallInto(CallResult.second, OutChain); + return CallResult.first; } - + /// ExpandOp - Expand the specified SDOperand into its two component pieces @@ -1865,6 +2231,8 @@ void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){ Hi = I->second.second; return; } + } else { + assert(!ExpandedNodes.count(Op) && "Re-expanding a node!"); } // Expanding to multiple registers needs to perform an optimization step, and @@ -1893,7 +2261,7 @@ void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){ // Aggregate register values are always in consequtive pairs. Lo = DAG.getCopyFromReg(Reg, NVT, Node->getOperand(0)); Hi = DAG.getCopyFromReg(Reg+1, NVT, Lo.getValue(1)); - + // Remember that we legalized the chain. AddLegalizedOperand(Op.getValue(1), Hi.getValue(1)); @@ -1909,22 +2277,62 @@ void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){ Hi = LegalizeOp(Node->getOperand(1)); break; + case ISD::CTPOP: + ExpandOp(Node->getOperand(0), Lo, Hi); + Lo = DAG.getNode(ISD::ADD, NVT, // ctpop(HL) -> ctpop(H)+ctpop(L) + DAG.getNode(ISD::CTPOP, NVT, Lo), + DAG.getNode(ISD::CTPOP, NVT, Hi)); + Hi = DAG.getConstant(0, NVT); + break; + + case ISD::CTLZ: { + // ctlz (HL) -> ctlz(H) != 32 ? ctlz(H) : (ctlz(L)+32) + ExpandOp(Node->getOperand(0), Lo, Hi); + SDOperand BitsC = DAG.getConstant(MVT::getSizeInBits(NVT), NVT); + SDOperand HLZ = DAG.getNode(ISD::CTLZ, NVT, Hi); + SDOperand TopNotZero = DAG.getSetCC(ISD::SETNE, TLI.getSetCCResultTy(), + HLZ, BitsC); + SDOperand LowPart = DAG.getNode(ISD::CTLZ, NVT, Lo); + LowPart = DAG.getNode(ISD::ADD, NVT, LowPart, BitsC); + + Lo = DAG.getNode(ISD::SELECT, NVT, TopNotZero, HLZ, LowPart); + Hi = DAG.getConstant(0, NVT); + break; + } + + case ISD::CTTZ: { + // cttz (HL) -> cttz(L) != 32 ? cttz(L) : (cttz(H)+32) + ExpandOp(Node->getOperand(0), Lo, Hi); + SDOperand BitsC = DAG.getConstant(MVT::getSizeInBits(NVT), NVT); + SDOperand LTZ = DAG.getNode(ISD::CTTZ, NVT, Lo); + SDOperand BotNotZero = DAG.getSetCC(ISD::SETNE, TLI.getSetCCResultTy(), + LTZ, BitsC); + SDOperand HiPart = DAG.getNode(ISD::CTTZ, NVT, Hi); + HiPart = DAG.getNode(ISD::ADD, NVT, HiPart, BitsC); + + Lo = DAG.getNode(ISD::SELECT, NVT, BotNotZero, LTZ, HiPart); + Hi = DAG.getConstant(0, NVT); + break; + } + case ISD::LOAD: { SDOperand Ch = LegalizeOp(Node->getOperand(0)); // Legalize the chain. SDOperand Ptr = LegalizeOp(Node->getOperand(1)); // Legalize the pointer. - Lo = DAG.getLoad(NVT, Ch, Ptr); + Lo = DAG.getLoad(NVT, Ch, Ptr, Node->getOperand(2)); // Increment the pointer to the other half. unsigned IncrementSize = MVT::getSizeInBits(Lo.getValueType())/8; Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr, getIntPtrConstant(IncrementSize)); - Hi = DAG.getLoad(NVT, Ch, Ptr); + //Is this safe? declaring that the two parts of the split load + //are from the same instruction? + Hi = DAG.getLoad(NVT, Ch, Ptr, Node->getOperand(2)); // Build a factor node to remember that this load is independent of the // other one. SDOperand TF = DAG.getNode(ISD::TokenFactor, MVT::Other, Lo.getValue(1), Hi.getValue(1)); - + // Remember that we legalized the chain. AddLegalizedOperand(Op.getValue(1), TF); if (!TLI.isLittleEndian()) @@ -2002,7 +2410,7 @@ void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){ // The low part is just a sign extension of the input (which degenerates to // a copy). Lo = DAG.getNode(ISD::SIGN_EXTEND, NVT, In); - + // The high part is obtained by SRA'ing all but one of the bits of the lo // part. unsigned LoSize = MVT::getSizeInBits(Lo.getValueType()); @@ -2025,7 +2433,7 @@ void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){ // The low part is just a zero extension of the input (which degenerates to // a copy). Lo = DAG.getNode(ISD::ZERO_EXTEND, NVT, In); - + // The high part is just a zero. Hi = DAG.getConstant(0, NVT); break; @@ -2092,7 +2500,7 @@ void SelectionDAGLegalize::ExpandOp(SDOperand Op, SDOperand &Lo, SDOperand &Hi){ Lo = ExpandLibCall("__lshrdi3", Node, Hi); break; - case ISD::ADD: + case ISD::ADD: ExpandByParts(ISD::ADD_PARTS, Node->getOperand(0), Node->getOperand(1), Lo, Hi); break;