removeAndReleaseArray from DeadObjectElimination is very tightly coupled to Array internals

carlos42421 · July 26, 2020, 3:34pm

I'm compiling a trimmed down standard library with an alternative implementation of Array.

Instead of using the standard array buffer containing an array storage class instance with allocated tail elements, I'm using an UnsafeMutableBufferPointer and managing it's lifetime externally. (I don't have reference counting in my runtime due to a lack of threading API on bare metal.)

My code compiles to AST fine, but when optimising the module, it traps in dead object elimination...

* thread #1, queue = 'com.apple.main-thread', stop reason = signal SIGABRT
  * frame #0: 0x00007fff70bd133a libsystem_kernel.dylib`__pthread_kill + 10
    frame #1: 0x00007fff70c8de60 libsystem_pthread.dylib`pthread_kill + 430
    frame #2: 0x00007fff70b58808 libsystem_c.dylib`abort + 120
    frame #3: 0x00007fff70b57ac6 libsystem_c.dylib`__assert_rtn + 314
    frame #4: 0x000000010109d8f0 swift`removeAndReleaseArray(NewArrayValue=0x0000000122ef7240, DEBlocks=0x00007ffeefbfa140) at DeadObjectElimination.cpp:571:3
    frame #5: 0x000000010109b9d0 swift`(anonymous namespace)::DeadObjectElimination::processAllocApply(this=0x000000012963f4a0, AI=0x0000000122ef7240, DEBlocks=0x00007ffeefbfa140) at DeadObjectElimination.cpp:807:8
    frame #6: 0x000000010109b161 swift`(anonymous namespace)::DeadObjectElimination::processFunction(this=0x000000012963f4a0, Fn=0x0000000128b1a490) at DeadObjectElimination.cpp:674:20
    frame #7: 0x000000010109aeb1 swift`(anonymous namespace)::DeadObjectElimination::run(this=0x000000012963f4a0) at DeadObjectElimination.cpp:684:9
    frame #8: 0x0000000100f3c78c swift`swift::SILPassManager::runPassOnFunction(this=0x00007ffeefbfa990, TransIdx=2, F=0x0000000128b1a490) at PassManager.cpp:410:8
    frame #9: 0x0000000100f3eda7 swift`swift::SILPassManager::runFunctionPasses(this=0x00007ffeefbfa990, FromTransIdx=2, ToTransIdx=3) at PassManager.cpp:499:5
    frame #10: 0x0000000100f404af swift`swift::SILPassManager::execute(this=0x00007ffeefbfa990) at PassManager.cpp:619:5
    frame #11: 0x00000001004cddc4 swift`swift::SILPassManager::executePassPipelinePlan(this=0x00007ffeefbfa990, Plan=0x00007ffeefbfa948) at PassManager.h:269:7
    frame #12: 0x0000000100f6a6dc swift`swift::runSILOptimizationPasses(Module=0x0000000129886e00) at Passes.cpp:103:6
    frame #13: 0x00000001006e1660 swift`performSILOptimizations(Invocation=0x0000000121824e00, SM=0x0000000129886e00) at Frontend.cpp:1142:5
    frame #14: 0x00000001006e132d swift`swift::CompilerInstance::performSILProcessing(this=0x0000000121824e00, silModule=0x0000000129886e00, stats=0x0000000000000000) at Frontend.cpp:1172:3
    frame #15: 0x0000000100128a9e swift`performCompileStepsPostSILGen(Instance=0x0000000121824e00, Invocation=0x00007ffeefbfbb68, SM=unique_ptr<swift::SILModule, std::__1::default_delete<swift::SILModule> > @ 0x00007ffeefbfb348, astGuaranteedToCorrespondToSIL=true, MSF=swift::ModuleOrSourceFile @ 0x00007ffeefbfb1f0, PSPs=0x00007ffeefbfb368, moduleIsPublic=true, ReturnValue=0x00007ffeefbfb89c, observer=0x0000000000000000, Stats=0x0000000000000000) at FrontendTool.cpp:1289:16
    frame #16: 0x000000010011e1a0 swift`performCompile(Instance=0x0000000121824e00, Invocation=0x00007ffeefbfbb68, Args=ArrayRef<const char *> @ 0x00007ffeefbfb720, ReturnValue=0x00007ffeefbfb89c, observer=0x0000000000000000, Stats=0x0000000000000000) at FrontendTool.cpp:1079:9
    frame #17: 0x000000010011cc11 swift`swift::performFrontend(Args=ArrayRef<const char *> @ 0x00007ffeefbfbad8, Argv0="/Users/carlpeto/compilers/avr-swift/build/Ninja-DebugAssert/swift-macosx-x86_64/bin/swift", MainAddr=0x0000000100003050, observer=0x0000000000000000) at FrontendTool.cpp:1819:5
    frame #18: 0x0000000100005205 swift`run_driver(ExecName=(Data = "swift", Length = 5), argv=const llvm::ArrayRef<const char *> @ 0x00007ffeefbfc950) at driver.cpp:125:14
    frame #19: 0x0000000100003b24 swift`main(argc_=86, argv_=0x00007ffeefbfefe8) at driver.cpp:270:12
    frame #20: 0x00007fff70a89cc9 libdyld.dylib`start + 1
    frame #21: 0x00007fff70a89cc9 libdyld.dylib`start + 1

The assertion is in this function...

// Attempt to remove the array allocated at NewAddrValue and release its
// refcounted elements.
//
// This is tightly coupled with the implementation of array.uninitialized.
// The call to allocate an uninitialized array returns two values:
// (Array<E> ArrayBase, UnsafeMutable<E> ArrayElementStorage)
//
// TODO: This relies on the lowest level array.uninitialized not being
// inlined. To do better we could either run this pass before semantic inlining,
// or we could also handle calls to array.init.
static bool removeAndReleaseArray(SingleValueInstruction *NewArrayValue,
                                  DeadEndBlocks &DEBlocks) {
  TupleExtractInst *ArrayDef = nullptr;
  TupleExtractInst *StorageAddress = nullptr;
  for (auto *Op : NewArrayValue->getUses()) {
    auto *TupleElt = dyn_cast<TupleExtractInst>(Op->getUser());
    if (!TupleElt)
      return false;
    if (TupleElt->getFieldNo() == 0 && !ArrayDef) {
      ArrayDef = TupleElt;
    } else if (TupleElt->getFieldNo() == 1 && !StorageAddress) {
      StorageAddress = TupleElt;
    } else {
      return false;
    }
  }
  if (!ArrayDef)
    return false; // No Array object to delete.

  assert(!ArrayDef->getType().isTrivial(*ArrayDef->getFunction()) &&
         "Array initialization should produce the proper tuple type.");

  // Analyze the array object uses.
  DeadObjectAnalysis DeadArray(ArrayDef);
  if (!DeadArray.analyze())
    return false;

  // Require all stores to be into the array storage not the array object,
  // otherwise bail.
  bool HasStores = false;
  DeadArray.visitStoreLocations([&](ArrayRef<StoreInst*>){ HasStores = true; });
  if (HasStores)
    return false;

  // Remove references to empty arrays.
  if (!StorageAddress) {
    removeInstructions(DeadArray.getAllUsers());
    return true;
  }
  assert(StorageAddress->getType().isTrivial(*ArrayDef->getFunction()) &&
         "Array initialization should produce the proper tuple type.");

  // Analyze the array storage uses.
  DeadObjectAnalysis DeadStorage(StorageAddress);
  if (!DeadStorage.analyze())
    return false;

  // Find array object lifetime.
  ValueLifetimeAnalysis VLA(NewArrayValue, DeadArray.getAllUsers());

  // Check that all storage users are in the Array's live blocks.
  for (auto *User : DeadStorage.getAllUsers()) {
    if (!VLA.isWithinLifetime(User))
      return false;
  }
  // For each store location, insert releases.
  SILSSAUpdater SSAUp;
  ValueLifetimeAnalysis::Frontier ArrayFrontier;
  if (!VLA.computeFrontier(ArrayFrontier,
                           ValueLifetimeAnalysis::UsersMustPostDomDef,
                           &DEBlocks)) {
    // In theory the allocated object must be released on all paths in which
    // some object initialization occurs. If not (for some reason) we bail.
    return false;
  }

  DeadStorage.visitStoreLocations([&] (ArrayRef<StoreInst*> Stores) {
      insertReleases(Stores, ArrayFrontier, SSAUp);
    });

  // Delete all uses of the dead array and its storage address.
  removeInstructions(DeadArray.getAllUsers());
  removeInstructions(DeadStorage.getAllUsers());

  return true;
}

ArrayDef->getType().isTrivial returns true in my case because my array type is just a struct with no nested class instances...

@frozen
public struct Array<Element>: _DestructorSafeContainer {
  @usableFromInline
  internal typealias _Buffer = _AVRArrayBuffer<Element>

  @usableFromInline
  internal var _buffer: _Buffer

  @inlinable
  internal init(_buffer: _Buffer) {
    self._buffer = _buffer
  }
}
@usableFromInline
@frozen
internal struct _AVRArrayBuffer<Element> : _ArrayBufferProtocol {
  public var _countAndCapacity: _ArrayBody

  @usableFromInline
  internal var _storage: UnsafeMutableBufferPointer<Element>

  // this is a temporary hack, we will get rid of this later
  internal func deallocate() {
    _storage.deallocate()
  }
...
}

So the first assert fails with "Array initialization should produce the proper tuple type."

My questions are twofold...

I'm not quite sure of the purpose of this assert, or the message is misleading. If for some reason it's essential that the array type contains class instances then shouldn't it be checked during Sema with a suitable error message, rather than a cryptic assert during optimisation? Or if something about the structure of this optimisation function would break unless the assert was true, then can we change the assert message to something more descriptive?
Which leads me on to... the comment says "This is tightly coupled with the implementation of array.uninitialized." But from what I can see, the implementation of this optimisation is very heavily tied to both the methods mentioned and to the structure of the array memory internals. Should the comment be clarified? And instead of trapping, should this optimisation just short circuit and not be applied if it's tied to Array internals that don't seem to exist?

jrose · July 26, 2020, 6:56pm

It hasn’t really been a goal to decouple the compiler and stdlib, other than what’s needed for ABI stability. I /can/ say, however, that you can’t implement arbitrary-sized arrays without classes, because the compiler does not expose alloca or cleanups as primitives, to the best of my knowledge. You could change this behavior, but I think you’d have far better luck changing heap-to-stack promotion to always kick in, as that would still let you assert that an object’s refcount is zero when it comes time to destroy it.

carlos42421 · July 26, 2020, 9:24pm

Yes, makes sense. In my version, the Array will malloc a fixed size heap at initialisation, arrays cannot be resized, appended, etc. (they're like C arrays) and the caller/user of an Array will be responsible for cleanup. It's very much an alpha. When stable/working and i'm sure it's lowering to efficient and correct assembly, I am planning to figure out a way to switch to alloca/stack. Like you say, I think the only approach that makes sense is changing heap-to-stack promotion to always kick in. But that's a different project!

I think for now, I've just got to figure out what to do with this optimisation. I'm not very familiar with optimisations.

Do you think it's OK if I change the assert to something like...

if (ArrayDef->getType().isTrivial(*ArrayDef->getFunction()))
    return false;

?

At least just in my own patched version of the compiler. It doesn't have to be an upstream patch.

jrose · July 26, 2020, 9:35pm

I mean, you could just remove that part of DeadObjectElimination for now. It's "just" an optimization…albeit an important one for staying under your fixed heap size limit in the long run.

(I don't know much about this pass.)

carlos42421 · July 26, 2020, 9:38pm

ok, sounds good, thanks @jrose

Andrew_Trick · July 29, 2020, 6:50am

It looks like this assert did what it was supposed to do--tell you that this pass depends on the implementation of Array. It's normal for optimization to reason about array semantics, but unusual that we don't have a first-class representation of arrays in our high-level IR. So SIL passes embed information about the array implementation in various places. That dependence is expressed in asserts. Expressing it as a bail-out would be wrong because there's no way to test that bail-out and it would communicate to someone reading the code that the optimization is expected to fail on certain user input. The assert says "there's no possible user input that should trigger this".

carlos42421 · August 1, 2020, 6:17pm

OK, I'm not going to follow up on it, as it's really a super super edge case, my 1c worth is the asserts are slightly opaque. If I'd seen an asserts throw saying "Array initialization did not produce expected tuple type, this optimization cannot proceed", then I would know exactly what had happened. Or maybe a code comment saying // array initialization should produce expected tuple type for this optimization to work correctly and safely.

But it is such an edge case that it is not even worth creating a pull request to change it. If anyone ever in the history of the world has the same issue they will probably stumble on this discussion and see all they need to know.

Thanks guys for clearing it all up.

Andrew_Trick · August 2, 2020, 2:41am

Thank you. Anytime someone wastes time being confused it’s worth clarifying.