Lowering operations to 8-bit!

I am trying to lower all llvm operations to 8-bit. So far I was trying to have llvm do all that for me using things like:

setOperationAction(ISD::ADD, MVT::ii,Promote);

setOperationAction(ISD::ADD, MVT::i8,Legal);

setOperationAction(ISD::ADD, MVT::i16,Expand);

setOperationAction(ISD::ADD, MVT::i32,Expand);

However, I keep getting an assertion failure that operation can not be expanded.

Now I am thinking maybe LLVM does not lower all operations and value types.

Before going ahead and write new DAGs for all LLVM operations, I would like to make sure that I am doing the right thing.

Am I doing it right?

Do I have to write new DAGs for all of the LLVM operations? Or some of them already do it for me?

Thanks,

Alireza Moshtaghi

Senior Software Engineer

Development Systems, Microchip Technology

I am trying to lower all llvm operations to 8-bit. So far I was trying
to have llvm do all that for me using things like:

ok

setOperationAction(ISD::ADD, MVT::ii,Promote);
setOperationAction(ISD::ADD, MVT::i8,Legal);
setOperationAction(ISD::ADD, MVT::i16,Expand);
setOperationAction(ISD::ADD, MVT::i32,Expand);

This should work.

However, I keep getting an assertion failure that operation can not be
expanded.

On which operation, of which types?

Now I am thinking maybe LLVM does not lower all operations and value
types.

Things are typically added to LegalizeDAG on demand, so you may run into some corner cases that other targets haven't hit yet.

Before going ahead and write new DAGs for all LLVM operations, I would
like to make sure that I am doing the right thing.

In theory, you should just have to add code to LegalizeDAG.cpp to expand the operation. With information about which operation is the problem we can give you more guidance.

-Chris

I'm working on version 2.0
The assertion at line 2380 of LegalizeDAG.cpp fails when it is trying to
lower the add with i16.

assertion reads:
assert(MVT::isVector(Node->getValueType(0)) &&
  "Cannot expand this binary operation!");

I am trying to compile a very simple program as follows:

short var;
void foo(void)
{
  Var++;
}

The input bytecode, (in addition to the debug stuff) contains:

  %tmp = load i16* @var ;<i16> [#uses=1]
  %tmp1 = add i16 %tmp, 1 ;<i16> [#uses=1]
  store i16 %tmp1, i16* @var
  br label %return
return: ;preds = %entry

Is the above giving any clue, or you need more info?

Thanks
A.

I'd suggest trying mainline or LLVM 2.1. In 2.1 (but not 2.0) it is possible to implement 128-bit addition on a 32-bit cpu. This seems similar to your situation.

-Chris

I moved my code to 2.1 but still the same.
If I make ADD i16 legal, then it goes through, but it has problem
expanding it to i8.
Should I go ahead and customize it and do the same for all instructions?
Or there is a more general thing that I can do?

A.

I really can't tell without more information. How is it failing? Can you add a stack trace and pdf of the dump of the dag being legalized when it crashes?

-Chris

Attached please find the gdb backtrace dump and the postscript file of
the DAG right before assertion.
The red Node is the current Node in LegalizeOp()
The only thing that I am customizing before we get here is the
FORMAL_ARGUMENTS. At this time I don't really care about the arguments,
just want to get some global values working. When I trace the program,
it is well passed the legalizing of formal arguments when it crashes so
I'm not sure if I may be breaking something in there.
Here is my code in the formalizing arguments (copied ISD::MERGE_VALUES
from PowerPC implementation, not sure if it is really needed)

static SDOperand LowerFORMAL_ARGUMENTS(SDOperand Op, SelectionDAG &DAG){
  SmallVector<SDOperand, 8> ArgValues;
  SDOperand Root = Op.getOperand(0);
  // Return the new list of results.
  std::vector<MVT::ValueType> RetVT(Op.Val->value_begin(),
                                    Op.Val->value_end());
  const Function* Fn = DAG.getMachineFunction().getFunction();
  std::cout<<Op.Val->getNumValues();
  std::cout<<"----------------- "<<__FUNCTION__<<" handling
FORMAL_ARGUMENTS of"<<Fn->getName()<<std::endl;std::cout.flush();
  for (unsigned ArgNo = 0, e = Op.Val->getNumValues()-1; ArgNo != e;
++ArgNo) {
    
    MVT::ValueType ObjectVT = Op.getValue(ArgNo).getValueType();
    
    switch (ObjectVT){
    default: assert(0 && "Unhandled argument type!");
    case MVT::i32: cout<<"------------ i32"<<std::endl;break;
    case MVT::i64: cout<<"------------ i64"<<std::endl;break;
    case MVT::f32: cout<<"------------ f32"<<std::endl;break;
    case MVT::f64: cout<<"------------ f64"<<std::endl;break;
    case MVT::v4f32: cout<<"------------ v4f32"<<std::endl;break;
    case MVT::v4i32: cout<<"------------ v4i32"<<std::endl;break;
    case MVT::v8i16: cout<<"------------ v8i16"<<std::endl;break;
    case MVT::v16i8: cout<<"------------ v16i8"<<std::endl;break;
      break;
    } //end switch
  } //end for
  
  ArgValues.push_back(Root);
  return DAG.getNode(ISD::MERGE_VALUES, RetVT, &ArgValues[0],
ArgValues.size());
}

stacktrace.txt (2.37 KB)

dag.ps (22.9 KB)

Attached please find the gdb backtrace dump and the postscript file of
the DAG right before assertion.
The red Node is the current Node in LegalizeOp()

Okay, this is the problem. LegalizeOp should only be called on a node if the VT is valid for the target. In this case, ExpandOp should have been called to split the register up. I'd suggest going up the stack to figure out who called LegalizeOp instead of ExpandOp.

Here is my code in the formalizing arguments (copied ISD::MERGE_VALUES
from PowerPC implementation, not sure if it is really needed)

MergeValues is required because the FORMAL_ARGUMENTs node returns one value for each argument input to the function, and also a chain value. These have to match up correctly.

-Chris

ExpandOp is not called at all.
In SelectionDAGLegalize::HandleOp() only the ValueType is considered in
the switch statement to decide if it is legal or promote or expand.
As I trace back (correct me if I'm wrong) these values are set in
TargetLowering::computeRegisterProperties() and it is based on the
largest register class (in my case the smallest possible pointer size,
16-bit)
So it reduces everything down to 16-bit and pretty much ignores the fact
that ADD of i16 is supposed to be expanded.

Am I doing the right analysis?

Ali.

Yes. It sounds like the codegen is assuming the pointer type is valid in computeRegisterProperties or something. Somehow i16 is getting marked as legal.

-Chris

So does that mean that LLVM can't lower automatically to 8-bit values?
I tried defining 8-bit pointers in the subtarget using "p:8:8:8" but it
asserts at line 566 of TargetData.cpp in the default case of
TargetData::getIntPtrType()

Is it difficult to add 8-bit support?

A.

So does that mean that LLVM can't lower automatically to 8-bit values?

There is no inherent reason. LLVM should be able to lower to 8-bit values. It's probably a bug somewhere.

In TargetLowering.h:

bool isTypeLegal(MVT::ValueType VT) const {
     return !MVT::isExtendedVT(VT) && RegClassForVT[VT] != 0;
   }

Is there a 16-bit register class?

I tried defining 8-bit pointers in the subtarget using "p:8:8:8" but it
asserts at line 566 of TargetData.cpp in the default case of
TargetData::getIntPtrType()

Dunno why it's like this. Can you add case 1: return Type::Int8Ty? Does it work / help?

Evan

Thank you Evan,
I added the return Type::Int8Ty to the switch statement to get it to
work.
I don't know if this can have other consequences, I haven't yet verified
if the generated Legalized DAG is correct though.

A.

Thank you Evan,
I added the return Type::Int8Ty to the switch statement to get it to
work.
I don't know if this can have other consequences, I haven't yet verified
if the generated Legalized DAG is correct though.

If this works, please submit a patch. Otherwise please submit a bug report with as much information as possible.

Thanks,

Evan

I am trying to verify the generated DAG after converting from llvm to
DAG, however I'm not sure if this is correct or not.
Here is the situation:
In order to get LLVM to lower to 8-bit I have to define only 8-bit
registers and the pointer size also to be 8-bit.
Doing so, the attached DAG is generated for a load:i16.

I have problem understanding this DAG in two places:

1)As you can see the UNDEF node is of type i8, however, we want it to be
of type i16 because load is of type i16
As I trace llvm to see how it lowers, I see that it is basing the type
of UNDEF on the type of its address which is i8 :
SelectionDAG.cpp:2250
SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType())
The question is why is it doing this? Shouldn't it use Ty instead of
Ptr.getValueType()?

2)Ok it is using an 8-bit GlobalAddress because I told it that pointers
are 8-bit, however, what if my memory is bigger? I can cascade 2
registers and address more larger memory than only a 256-byte long.
The question is how can I make it generate GlobalAddress:i16 and later
break it down to two 8-bit values?

Thanks.
A.

graph.ps (14.5 KB)

When I change SelectionDAG.cpp:2250
from:
SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType())
to:
SDOperand Undef = getNode(ISD::UNDEF, VT)
It behaves as I expect it generates a node of UNDEF:i16 then lowers it
to two 8-bits and the DAG seems to be correct now.

Please let me know if this is a bug in LLVM or I am doing something
wrong.

Thanks.
Ali

I am trying to verify the generated DAG after converting from llvm to
DAG, however I'm not sure if this is correct or not.
Here is the situation:
In order to get LLVM to lower to 8-bit I have to define only 8-bit
registers and the pointer size also to be 8-bit.
Doing so, the attached DAG is generated for a load:i16.

I have problem understanding this DAG in two places:

1)As you can see the UNDEF node is of type i8, however, we want it to be
of type i16 because load is of type i16
As I trace llvm to see how it lowers, I see that it is basing the type
of UNDEF on the type of its address which is i8 :
SelectionDAG.cpp:2250
SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType())
The question is why is it doing this? Shouldn't it use Ty instead of
Ptr.getValueType()?

2)Ok it is using an 8-bit GlobalAddress because I told it that pointers
are 8-bit, however, what if my memory is bigger? I can cascade 2
registers and address more larger memory than only a 256-byte long.
The question is how can I make it generate GlobalAddress:i16 and later
break it down to two 8-bit values?

Hrm. Looks like there is some confusion. What is the size of the addressable space? Setting ptr type to 8-bit means the size of the address is at most 256-byte. That seems awfully small. :slight_smile: Is this a 16-bit machine you are targeting? If so, please try setting pointer type to i16.

Evan

Evan,
The machine is 8 bit, and of course all registers are 8-bit too.
Memory access on this machine is a bit different. The memory is banked
into banks of 256-byte, and you can select the active bank using a bank
select register. All instructions can access the memory with an 8-bit
operand, so in that sense the address space can be viewed as 256-byte
long.
On the other hand, there are three shadowed locations of each bank that
two of them act as index registers, and if you access (read/write) to
the third register, the memory at address pointed to by the first two
registers will be accessed (no banking in this mode)

At first I created a class of 16-bit registers for the two special
registers, but since LLVM only lowers to the largest register class size
(16-bit), it did not lower the rest of the operations to 8-bit.
So I had to get rid of the 16-bit register class and now LLVM lowers to
8-bit operations, but I have ended up with pointer size of 8-bit.
Still I think there are tricks that I may be able to play by customizing
the GlobalAddress DAG and preloading the index registers. However, first
I would like to solicit your input and make sure that this is really
what I want to do.

Regards
Ali.

Evan,
The machine is 8 bit, and of course all registers are 8-bit too.
Memory access on this machine is a bit different. The memory is banked
into banks of 256-byte, and you can select the active bank using a bank
select register. All instructions can access the memory with an 8-bit
operand, so in that sense the address space can be viewed as 256-byte
long.
On the other hand, there are three shadowed locations of each bank that
two of them act as index registers, and if you access (read/write) to
the third register, the memory at address pointed to by the first two
registers will be accessed (no banking in this mode)

At first I created a class of 16-bit registers for the two special
registers, but since LLVM only lowers to the largest register class size
(16-bit), it did not lower the rest of the operations to 8-bit.
So I had to get rid of the 16-bit register class and now LLVM lowers to
8-bit operations, but I have ended up with pointer size of 8-bit.
Still I think there are tricks that I may be able to play by customizing
the GlobalAddress DAG and preloading the index registers. However, first
I would like to solicit your input and make sure that this is really
what I want to do.

It's not clear to me how to express which "bank" to target in LLVM. The target independent LoadSDNode does have a SrcValue field. I suppose if you have a way to map the memory bank to this during selectiondag building you can then use it during instruction selection. Otherwise, like you said, you will have to reload the index registers somehow.

Sorry I can't be of much help. You are in new llvm territory here.

Evan