The WorkList of LLVMContextImpl::dropTriviallyDeadConstantArrays

Hi,

I looked into LLVMContextImpl::dropTriviallyDeadConstantArrays (https://llvm.org/doxygen/LLVMContextImpl_8cpp_source.html#l00131) for performance purpose, and have some questions

////////////////////////////////////////////////////////////////////////////
1) How the WorkList ensures no double-release.

////////////////////////////////////////////////////////////////////////////

In the worklist loop, it inserts operands of a ConstantArray to delete back to the worklist. Is it possible that the operand to insert was already deleted?
This seems possible if the element order in the worklist is changed. For example, if we change its code like the following, recycled is 0 in my test case.

SmallSetVector<ConstantArray *, 4> WorkList(ArrayConstants.begin(),
ArrayConstants.end());SmallPtrSet<ConstantArray *, 4> D;
int recycled = 0;

while (!WorkList.empty()) {
ConstantArray *C = WorkList.pop_back_val();
if (D.contains(C)) {
++recycled;
continue;
}
if (C->use_empty()) {
for (const Use &Op : C->operands()) {
if (auto *COp = dyn_cast(Op))
WorkList.insert(COp);
}
D.insert(C);
C->destroyConstant();
}
}

However, if I changed the code like the following, then recycled could be > 0 in the same test case.

SmallSetVector<ConstantArray *, 4> WorkList;

SmallPtrSet<ConstantArray *, 4> D;

int recycled = 0;

for (auto I = ArrayConstants.begin(), E = ArrayConstants.end(); I != E;) {
auto *C = *I++;
if (C->use_empty()) {
for (const Use &Op : C->operands()) {
if (auto *COp = dyn_cast(Op)) {
WorkList.insert(COp);
}
}
D.insert(C);
C->destroyConstant();
}
}
while (!WorkList.empty()) {
ConstantArray *C = WorkList.pop_back_val();
if (D.contains(C)) {
++recycled;
continue;
}
if (C->use_empty()) {
for (const Use &Op : C->operands()) {
if (auto *COp = dyn_cast(Op)) {
WorkList.insert(COp);
}
}
D.insert(C);
C->destroyConstant();
}
}

The difference is that the first code (the same as the current code at HEAD) processes the worklist sorted by SmallVector, while the second one processes the ConstrantArray first by the order of ArrayConstants, then in the order sorted by SmallVector.

Maybe I miss anything. Is the current code always safe?

////////////////////////////////////////////////////////////////////////////

2) The insertion of SmallSetVector is slow
////////////////////////////////////////////////////////////////////////////

I saw the current version was to address the performance issue of the previous version (https://reviews.llvm.org/rG81f385b0c6ea37dd7195a65be162c75bbdef29d2).

In many of my test cases, I found the most time cost of dropTriviallyDeadConstantArrays is by the SetVector::insert caused by constructing the worklist from ConstantArray with size >50k. And in practice, a very few new operands are added into WorkList by the worklist loop.

If this is the case, the code above, which is like a combination of the previous and the current versions of dropTriviallyDeadConstantArrays, could be a trade-off, because 1) worklist can still resolve the n^2 loop issue 2) worklist is only used when necessary, and its length is usually small with less insertion overhead. In my case this reduced the time cost of dropTriviallyDeadConstantArrays from 17% to 4%.

Thank you, s