How to force the creation of arrays with zeroes?

Hi all. How to force the creation of arrays with zeroes? Or this use-case is not provided?

Stepan Dyatkovskiy wrote:

Hi all. How to force the creation of arrays with zeroes? Or this use-case is not provided?

That is impossible, LLVM will always canonicalize that to a ConstantAggregateZero.

Nick

Hi Stepan,

Hi all. How to force the creation of arrays with zeroes? Or this use-case is not provided?

you can't, you can only get a ConstantAggregateZero. This is actually kind of
annoying, and means that places expecting a ConstantArray have to remember to
also check for ConstantAggregateZero. Perhaps there's a good reason for the
current design, but if not it would be great to eliminate this wart.

Ciao, Duncan.

you can't, you can only get a ConstantAggregateZero. This is actually kind of
annoying, and means that places expecting a ConstantArray have to remember to
also check for ConstantAggregateZero. Perhaps there's a good reason for the
current design, but if not it would be great to eliminate this wart.

Well, I think the main reason it so reduce the size of .ll / .bc when
all operands are zero.
If the array / struct is really big then this can save a lot of space.

Hi Anton,

you can't, you can only get a ConstantAggregateZero. This is actually kind of
annoying, and means that places expecting a ConstantArray have to remember to
also check for ConstantAggregateZero. Perhaps there's a good reason for the
current design, but if not it would be great to eliminate this wart.

Well, I think the main reason it so reduce the size of .ll / .bc when
all operands are zero.
If the array / struct is really big then this can save a lot of space.

isn't this an orthogonal issue? A ConstantVector consisting of only zeros
doesn't have to be represented by storing a vast array of zero values, it
could be special cased internally by setting some kind of flag. If done right,
an all zero ConstantVector would then act exactly the same as every other kind
of ConstantVector as far as users of ConstantVector can tell, but wouldn't take
up a lot of storage. Instead, what we have now is essentially the same system
only with the flag exposed to users (ConstantAggregateZero playing the role of
the flag) so that all users have to worry about it, rather than this flag being
hidden in the implementation of ConstantVector and ConstantStruct.

Ciao, Duncan.

Hi all. I propose to use wrapper for this kind of constant objects.

Consider next code:

Constant* C = reinterpret_cast<Constant*>(I->getOperand(idx));
Constant* ArrayItem;
if (!isa<ConstantAggregateZero>(C))
  ArrayItem = reinterpret_cast<Constant*>(I->getOperand(ArrItemIdx));
else
  ArrayItem = ZeroInt;

Code analog within wrapper:

ConstOrZero C(I->getOperand(idx));
Constant* ArrayItem = C.getOperand(ArrItemIdx); // Unpleasant work with isa<> inside.

Advantages of this approach is that ConstantAggregateZero saves memory and we use it everywhere.
And in the same time we needn't dance with isa<ConstantAggregateZero>.

If you find it fine, please look at the patch in attachment.

-Stepan

const-or-zero.patch (5.81 KB)

I'd really rather not do this. Faking that large zero filled array is represented with ConstantArray means that the compiler will inevitably end up calling getOperand on each of those elements, burning a ton of compile time.

-Chris

Hi Chris. There is no zero arrays created. Probably this patch is not optimal and I'll reworked it today. But the main idea is keep a single zero-item when ConstantAggregateZero was wrapped and return this zero item as result of getOperand call.
Note that wrapper has no parent classes, it has very local and short lifetime (method body), it exists outside the LLVMContext and needed for replacement of isa<ConstantAggregateZero>(C) checks only.

-Stepan

How many times will a typical client call getOperand on your helper when it wraps a 10,000 element ConstantAggregateZero?

With CAZ the client is force to think about this case, and often handles it much much more efficiently. CAZ is a time optimization as well as a space optimization.

-Chris

You right here. If you know how to handle it more efficiently, wrapper will bad idea, since it will invoked 10,000 times. We must think always and select most efficient and clean way.
Though, there is also cases when we really need to transform it to 10,000 zeroes (just look at CBackend.cpp, when we print constant arrays, string #1027). There is also cases when we need to get either operand[i] or zero (SCCP.cpp, str #413). Both for CBackend and for SCCP we can reduce code size keeping performance on the same level.

-Stepan.

Sorry, forgot to reply-all

Hi Anton, in a solution without CAZ, isNullValue can just return true when it
sees the special "this ConstantArray is all zero" flag. So all the places that
now look for CAZ can just use isNullValue instead and there need be no
performance loss. That said, CAZ is more "in your force" so less likely to be
forgotten about. Another interesting possibility is to handle more than just
all zero values: if a constant array has many repeated elements, maybe the
array could be stored in a compressed form. An all zeros array would just be a
special case of this.

Ciao, Duncan.

To Anton:

In these 2 particular cases the changes of the code size can
definitely be neglected. Even more, in SCCP the use of CAZ is a
performance win, since we do not have to check at all operands are
zero, we already (!) know this.

Little fragment from SCCP.cpp, lines 413-418:
      ...
      else if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C))
        LV.markConstant(CS->getOperand(i)); // Constants are constant.
      else if (isa<ConstantAggregateZero>(C)) {
        Type *FieldTy = cast<StructType>(V->getType())->getElementType(i);
        LV.markConstant(Constant::getNullValue(FieldTy));
      } else
      ...
I couldn't found that performance wins here. We can just hide these branches either inside the improved implementation of ConstantVector/Array/Struct or inside the wraper.

I agree with Duncan reasoning. We can just to store single zero item and flag. This changes also allows make code cleaner.

if a constant array has many repeated elements, maybe the
array could be stored in a compressed form.

Did you mean reducing actual number of operands? As I found all repeated values instead a pointers to the same Value in LLVMContext (or I missed something?).

-Stepan.

Yep check out PR1324. Doing something like this would be a great improvement.

-Chris

Hi Chris. The main question is how to implement ConstantAggregateXXXXX::getOperand? Should it be empty collection, or it must return the item aggregated?

-Stepan.

Hi Stephan,

I've been thinking about this a bit and have some more specific ideas, I'll write up a design and maybe implement it over the next few days.

-Chris

Hi Stepan,

FYI, this is now implemented in mainline with the ConstantData* classes.

-Chris