llvm dev - Sep 2008 - [LLVMdev] 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
> 
> Is this possible given the current code generation stuff? Is there 
> another approach that I should consider?
> 
> -Rich
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

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 at 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

On Sep 8, 2008, at 4:03 AM, 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 at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

On Mon, Sep 8, 2008 at 10:24 AM, Evan Cheng <evan.cheng at apple.com>
wrote:
> Legalizer will expand arithmetics using addc and adde.
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

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