[llvm-dev] The WorkList of LLVMContextImpl::dropTriviallyDeadConstantArrays

[Stephan Z via llvm-dev]

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<ConstantArray>(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<ConstantArray>(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<ConstantArray>(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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200730/8d0b96d6/attachment.html>