//===--- 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/SILInstruction.h"
#include "llvm/ADT/SmallBitVector.h"

#include <vector>

namespace swift {

struct InstructionMatchResult {
  /// The instruction matches.
  bool matches;

  /// The search should be halted.
  bool halt;
};

using InstructionMatcher =
  llvm::function_ref<InstructionMatchResult(SILInstruction *i)>;

/// Given a predicate defining interesting instructions, check whether
/// the stack is different at any of them from how it stood at the start
/// of the search.
///
/// The matcher function must halt the search before any edges which would
/// lead back to before the start point.
bool hasStackDifferencesAt(SILInstruction *start, InstructionMatcher matcher);

/// 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
///
class StackNesting {

  typedef SmallBitVector BitVector;

  /// Data stored for each block (actually for each block which is not dead).
  struct BlockInfo {

    /// Back-link to the block.
    SILBasicBlock *Block;

    /// The cached list of successors.
    llvm::SmallVector<BlockInfo *, 8> Successors;

    /// The list of stack allocating/deallocating instructions in the block.
    llvm::SmallVector<SILInstruction *, 8> StackInsts;

    /// The bit-set of alive stack locations at the block entry.
    BitVector AliveStackLocsAtEntry;

    /// True if there is a path from this block to a function-exit.
    ///
    /// In other words: this block does not end in an unreachable-instruction.
    /// This flag is only used for verifying that the lifetime of a stack
    /// location does not end at the end of a block.
    bool ExitReachable = false;

    BlockInfo(SILBasicBlock *Block) : Block(Block) { }
  };

  /// Data stored for each stack location (= allocation).
  ///
  /// Each stack location is allocated by a single allocation instruction.
  struct StackLoc {
    StackLoc(AllocationInst *Alloc) : Alloc(Alloc) { }

    /// Back-link to the allocation instruction.
    AllocationInst *Alloc;

    /// Bit-set which represents all alive locations at this allocation.
    /// It obviously includes this location itself. And it includes all "outer"
    /// locations which surround this location.
    BitVector AliveLocs;
  };

  /// Mapping from stack allocations (= locations) to bit numbers.
  llvm::DenseMap<SingleValueInstruction *, unsigned> StackLoc2BitNumbers;

  /// The list of stack locations. The index into this array is also the bit
  /// number in the bit-sets.
  llvm::SmallVector<StackLoc, 8> StackLocs;

  /// Block data for all (non-dead) blocks.
  std::vector<BlockInfo> BlockInfos;

public:

  /// The possible return values of correctStackNesting().
  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
  };

  StackNesting() { }

  /// Performs correction of stack nesting by moving stack-deallocation
  /// instructions down the control flow.
  ///
  /// Returns the status of what changes were made.
  Changes correctStackNesting(SILFunction *F);
  
  /// For debug dumping.
  void dump() const;

  static void dumpBits(const BitVector &Bits);

private:
  /// Initializes the data structures.
  void setup(SILFunction *F);

  /// Solves the dataflow problem.
  ///
  /// Returns true if there is a nesting of locations in any way, which can
  /// potentially in the wrong order.
  bool solve();

  /// Insert deallocation instructions for all locations which are alive before
  /// the InsertionPoint (AliveBefore) but not alive after the InsertionPoint
  /// (AliveAfter).
  ///
  /// Returns true if any deallocations were inserted.
  bool insertDeallocs(const BitVector &AliveBefore, const BitVector &AliveAfter,
                      SILInstruction *InsertionPoint,
                      Optional<SILLocation> Location);

  /// Modifies the SIL to end up with a correct stack nesting.
  ///
  /// Returns the status of what changes were made.
  Changes adaptDeallocs();
};

} // end namespace swift

#endif // SWIFT_SILOPTIMIZER_UTILS_STACKNESTING_H