mirror of
https://github.com/apple/swift.git
synced 2025-12-14 20:36:38 +01:00
8d231d20c6
The previous algorithm was doing an iterative forward data flow analysis followed by a reverse data flow analysis. I suspect the history here is that it was a reverse analysis, and that didn't really work for infinite loops, and so complexity accumulated. The new algorithm is quite straightforward and relies on the allocations being properly jointly post-dominated, just not nested. We simply walk forward through the blocks in consistent-with-dominance order, maintaining the stack of active allocations and deferring deallocations that are improperly nested until we deallocate the allocations above it. The only real subtlety is that we have to delay walking into dead-end regions until we've seen all of the edges into them, so that we can know whether we have a coherent stack state in them. If the state is incoherent, we need to remove any deallocations of previous allocations because we cannot talk correctly about what's on top of the stack. The reason I'm doing this, besides it just being a simpler and hopefully faster algorithm, is that modeling some of the uses of the async stack allocator properly requires builtins that cannot just be semantically reordered. That should be somewhat easier to handle with the new approach, although really (1) we should not have runtime functions that need this and (2) we're going to need a conservatively-correct solution that's different from this anyway because hoisting allocations is *also* limited in its own way. I've attached a rather pedantic proof of the correctness of the algorithm. The thing that concerns me most about the rewritten pass is that it isn't actually validating joint post-dominance on input, so if you give it bad input, it might be a little mystifying to debug the verifier failures.
77 lines
2.2 KiB
C++
77 lines
2.2 KiB
C++
//===--- StackNesting.h - Utility for stack nesting -------------*- C++ -*-===//
|
|
//
|
|
// This source file is part of the Swift.org open source project
|
|
//
|
|
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
|
|
// Licensed under Apache License v2.0 with Runtime Library Exception
|
|
//
|
|
// See https://swift.org/LICENSE.txt for license information
|
|
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
#ifndef SWIFT_SILOPTIMIZER_UTILS_STACKNESTING_H
|
|
#define SWIFT_SILOPTIMIZER_UTILS_STACKNESTING_H
|
|
|
|
#include "swift/SIL/SILFunction.h"
|
|
#include "swift/SIL/BasicBlockData.h"
|
|
#include "llvm/ADT/SmallBitVector.h"
|
|
|
|
namespace swift {
|
|
|
|
/// A utility to correct the nesting of stack allocating/deallocating
|
|
/// instructions.
|
|
///
|
|
/// This utility is useful for optimizations which create stack allocations
|
|
/// without caring about correct nesting with existing allocations. This may
|
|
/// result in code like
|
|
/// \code
|
|
/// %1 = alloc_stack
|
|
/// ...
|
|
/// %2 = alloc_stack
|
|
/// ...
|
|
/// dealloc_stack %1
|
|
/// ...
|
|
/// dealloc_stack %2
|
|
/// \endcode
|
|
///
|
|
/// The StackNesting utility is able to correct the code:
|
|
/// \code
|
|
/// %1 = alloc_stack
|
|
/// ...
|
|
/// %2 = alloc_stack
|
|
/// ...
|
|
/// dealloc_stack %2
|
|
/// dealloc_stack %1
|
|
/// \endcode
|
|
///
|
|
/// Each allocation must still be properly jointly post-dominated by
|
|
/// its deallocations. StackNesting only fixes the nesting of allocations
|
|
/// deallocations; it does not insert required deallocations that are
|
|
/// missing entirely.
|
|
class StackNesting {
|
|
public:
|
|
|
|
/// The possible return values of fixNesting().
|
|
enum class Changes {
|
|
/// No changes are made.
|
|
None,
|
|
|
|
/// Only instructions were inserted or deleted.
|
|
Instructions,
|
|
|
|
/// Instructions were inserted or deleted and new blocks were inserted.
|
|
CFG
|
|
};
|
|
|
|
/// Performs correction of stack nesting by moving stack-deallocation
|
|
/// instructions down the control flow.
|
|
///
|
|
/// Returns the status of what changes were made.
|
|
static Changes fixNesting(SILFunction *F);
|
|
};
|
|
|
|
} // end namespace swift
|
|
|
|
#endif // SWIFT_SILOPTIMIZER_UTILS_STACKNESTING_H
|