adde/addc

My target doesn't support 64 bit arithmetic, so I'd like to supply definitions for adde/addc. The problem is I can't seem to figure out the magic. Here's an example of what I need to generate:

# two i64s in r5/r6 and r7/r8
# result in r1/r2, carry in r3

# adde
    add r2, r6, r8
    cmpltu r3, r2, r6 # compute carry

# addc
     add r1, r5, r7
     add r1, zero, r3

Is this possible given the current code generation stuff? Is there another approach that I should consider?

-Rich

Richard Pennington wrote:

My target doesn't support 64 bit arithmetic, so I'd like to supply definitions for adde/addc. The problem is I can't seem to figure out the magic. Here's an example of what I need to generate:

# two i64s in r5/r6 and r7/r8
# result in r1/r2, carry in r3

# adde
    add r2, r6, r8
    cmpltu r3, r2, r6 # compute carry

# addc
     add r1, r5, r7
     add r1, zero, r3

Oops! I meant:

     add r1, r1, r3

Richard Pennington wrote:

My target doesn't support 64 bit arithmetic, so I'd like to supply definitions for adde/addc. The problem is I can't seem to figure out the magic. Here's an example of what I need to generate:

# two i64s in r5/r6 and r7/r8
# result in r1/r2, carry in r3

# adde
    add r2, r6, r8
    cmpltu r3, r2, r6 # compute carry

# addc
     add r1, r5, r7
     add r1, zero, r3

Is this possible given the current code generation stuff? Is there another approach that I should consider?

-Rich

_______________________________________________
LLVM Developers mailing list
LLVMdev@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
  

I needed to do exactly the same for my target. I set ISD::ADD to be custom expanded (setOperationAction(ISD::ADD, MVT::i64, Custom)) and the same for ISD::SUB. I then added the following code to my target to do the expansion:

ExpandADDSUB(SDNode *N, SelectionDAG &DAG)
{
assert(N->getValueType(0) == MVT::i64 &&
(N->getOpcode() == ISD::ADD || N->getOpcode() == ISD::SUB) &&
"Unknown operand to lower!");

// Extract components
SDOperand LHSL = DAG.getNode(ISD::EXTRACT_ELEMENT, MVT::i32, N->getOperand(0),
DAG.getConstant(0, MVT::i32));
SDOperand LHSH = DAG.getNode(ISD::EXTRACT_ELEMENT, MVT::i32, N->getOperand(0),
DAG.getConstant(1, MVT::i32));
SDOperand RHSL = DAG.getNode(ISD::EXTRACT_ELEMENT, MVT::i32, N->getOperand(1),
DAG.getConstant(0, MVT::i32));
SDOperand RHSH = DAG.getNode(ISD::EXTRACT_ELEMENT, MVT::i32, N->getOperand(1),
DAG.getConstant(1, MVT::i32));

// Expand
SDOperand Lo = DAG.getNode(N->getOpcode(), MVT::i32, LHSL, RHSL);

ISD::CondCode CarryCC = (N->getOpcode() == ISD::ADD) ? ISD::SETULT : ISD::SETUGT;
SDOperand Carry = DAG.getSetCC(MVT::i32, Lo, LHSL, CarryCC);

SDOperand Hi = DAG.getNode(N->getOpcode(), MVT::i32, LHSH, Carry);
Hi = DAG.getNode(N->getOpcode(), MVT::i32, Hi, RHSH);
// Merge the pieces
return DAG.getNode(ISD::BUILD_PAIR, MVT::i64, Lo, Hi).Val;
}

In LowerOperation I lower add and sub using:

case ISD::ADD:
case ISD::SUB: return SDOperand(ExpandADDSUB(Op.Val, DAG),0);

This is for LLVM 2.3. I've haven't updated to the head recently so there might be additional changes needed for the new legalize types infrastructure. Hope this helps,

Richard

Legalizer will expand arithmetics using addc and adde. Is it not working for you? It works fine on x86, you can take a look how it's done.

Evan

Yes, but it silently assumes that addc/adde are legal! (See the
ISD::ADDC case in SelectionDAGLegalize::LegalizeOp.)

-Eli

Evan Cheng wrote:

Legalizer will expand arithmetics using addc and adde. Is it not working for you? It works fine on x86, you can take a look how it's done.

Evan

The x86 has a carry bit, my target doesn't.

It's not clear to me how I would specify the use of a general purpose register to contain the calculated carry in the current adde/addc scheme.

-Rich

You may have to custom lower i64 arithmetics. You can make use of "flag" outputs to ensure the instructions are generated in the order you want. The instruction which produces a flag value and the user of the flag are "glued" together. They are scheduled as a single unit and nothing else can be scheduled in between.

Evan

Richard Osborne wrote:
[snip]

ExpandADDSUB(SDNode *N, SelectionDAG &DAG)
{
assert(N->getValueType(0) == MVT::i64 &&
(N->getOpcode() == ISD::ADD || N->getOpcode() == ISD::SUB) &&
"Unknown operand to lower!");

// Extract components
SDOperand LHSL = DAG.getNode(ISD::EXTRACT_ELEMENT, MVT::i32, N->getOperand(0),
DAG.getConstant(0, MVT::i32));
SDOperand LHSH = DAG.getNode(ISD::EXTRACT_ELEMENT, MVT::i32, N->getOperand(0),
DAG.getConstant(1, MVT::i32));
SDOperand RHSL = DAG.getNode(ISD::EXTRACT_ELEMENT, MVT::i32, N->getOperand(1),
DAG.getConstant(0, MVT::i32));
SDOperand RHSH = DAG.getNode(ISD::EXTRACT_ELEMENT, MVT::i32, N->getOperand(1),
DAG.getConstant(1, MVT::i32));

// Expand
SDOperand Lo = DAG.getNode(N->getOpcode(), MVT::i32, LHSL, RHSL);

ISD::CondCode CarryCC = (N->getOpcode() == ISD::ADD) ? ISD::SETULT : ISD::SETUGT;
SDOperand Carry = DAG.getSetCC(MVT::i32, Lo, LHSL, CarryCC);

SDOperand Hi = DAG.getNode(N->getOpcode(), MVT::i32, LHSH, Carry);
Hi = DAG.getNode(N->getOpcode(), MVT::i32, Hi, RHSH);
// Merge the pieces
return DAG.getNode(ISD::BUILD_PAIR, MVT::i64, Lo, Hi).Val;
}

Thanks for the help!

For me (with current LLVM) it became:

SDValue Nios2TargetLowering::
ExpandADDSUB(SDValue Op, SelectionDAG &DAG)
{
   assert(Op.getValueType() == MVT::i64 &&
          (Op.getOpcode() == ISD::ADD || Op.getOpcode() == ISD::SUB) &&
          "Unknown operand to lower!");

   // Extract components
   SDValue LHSL = DAG.getNode(ISD::EXTRACT_ELEMENT, MVT::i32,
                              Op.getOperand(0),
                              DAG.getConstant(0, MVT::i32));
   SDValue LHSH = DAG.getNode(ISD::EXTRACT_ELEMENT, MVT::i32,
                              Op.getOperand(0),
                              DAG.getConstant(1, MVT::i32));
   SDValue RHSL = DAG.getNode(ISD::EXTRACT_ELEMENT, MVT::i32,
                              Op.getOperand(1),
                              DAG.getConstant(0, MVT::i32));
   SDValue RHSH = DAG.getNode(ISD::EXTRACT_ELEMENT, MVT::i32,
                              Op.getOperand(1),
                              DAG.getConstant(1, MVT::i32));

   // Expand
   SDValue Lo = DAG.getNode(Op.getOpcode(), MVT::i32, LHSL, RHSL);

   ISD::CondCode CarryCC = (Op.getOpcode() == ISD::ADD) ? ISD::SETULT :
                           ISD::SETUGT;
   SDValue Carry = DAG.getSetCC(MVT::i32, Lo, LHSL, CarryCC);

   SDValue Hi = DAG.getNode(Op.getOpcode(), MVT::i32, LHSH, Carry);
   Hi = DAG.getNode(Op.getOpcode(), MVT::i32, Hi, RHSH);
   // Merge the pieces
   return DAG.getNode(ISD::BUILD_PAIR, MVT::i64, Lo, Hi);
}

-Rich