Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- StackLifetime.h - Alloca Lifetime Analysis --------------*- C++ -*--===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_STACKLIFETIME_H

#define LLVM_ANALYSIS_STACKLIFETIME_H

#include "llvm/ADT/ArrayRef.h"

#include "llvm/ADT/BitVector.h"

#include "llvm/ADT/DenseMap.h"

#include "llvm/ADT/SmallVector.h"

#include "llvm/ADT/StringExtras.h"

#include "llvm/IR/PassManager.h"

#include "llvm/Support/raw_ostream.h"

#include <utility>

namespace llvm {

class AllocaInst;

class BasicBlock;

class Function;

class Instruction;

class IntrinsicInst;

/// Compute live ranges of allocas.

/// Live ranges are represented as sets of "interesting" instructions, which are

/// defined as instructions that may start or end an alloca's lifetime. These

/// are:

/// * lifetime.start and lifetime.end intrinsics

/// * first instruction of any basic block

/// Interesting instructions are numbered in the depth-first walk of the CFG,

/// and in the program order inside each basic block.

class StackLifetime {

  /// A class representing liveness information for a single basic block.

  /// Each bit in the BitVector represents the liveness property

  /// for a different stack slot.

  struct BlockLifetimeInfo {

    explicit BlockLifetimeInfo(unsigned Size)

        : Begin(Size), End(Size), LiveIn(Size), LiveOut(Size) {}

    /// Which slots BEGINs in each basic block.

    BitVector Begin;

    /// Which slots ENDs in each basic block.

    BitVector End;

    /// Which slots are marked as LIVE_IN, coming into each basic block.

    BitVector LiveIn;

    /// Which slots are marked as LIVE_OUT, coming out of each basic block.

    BitVector LiveOut;

  };

public:

  class LifetimeAnnotationWriter;

  /// This class represents a set of interesting instructions where an alloca is

  /// live.

  class LiveRange {

    BitVector Bits;

    friend raw_ostream &operator<<(raw_ostream &OS,

                                   const StackLifetime::LiveRange &R);

  public:

    LiveRange(unsigned Size, bool Set = false) : Bits(Size, Set) {}

    void addRange(unsigned Start, unsigned End) { Bits.set(Start, End); }

    bool overlaps(const LiveRange &Other) const {

      return Bits.anyCommon(Other.Bits);

    }

    void join(const LiveRange &Other) { Bits |= Other.Bits; }

    bool test(unsigned Idx) const { return Bits.test(Idx); }

  };

  // Controls what is "alive" if control flow may reach the instruction

  // with a different liveness of the alloca.

  enum class LivenessType {

    May,  // May be alive on some path.

    Must, // Must be alive on every path.

  };

private:

  const Function &F;

  LivenessType Type;

  /// Maps active slots (per bit) for each basic block.

  using LivenessMap = DenseMap<const BasicBlock *, BlockLifetimeInfo>;

  LivenessMap BlockLiveness;

  /// Interesting instructions. Instructions of the same block are adjustent

  /// preserve in-block order.

  SmallVector<const IntrinsicInst *, 64> Instructions;

  /// A range [Start, End) of instruction ids for each basic block.

  /// Instructions inside each BB have monotonic and consecutive ids.

  DenseMap<const BasicBlock *, std::pair<unsigned, unsigned>> BlockInstRange;

  ArrayRef<const AllocaInst *> Allocas;

  unsigned NumAllocas;

  DenseMap<const AllocaInst *, unsigned> AllocaNumbering;

  /// LiveRange for allocas.

  SmallVector<LiveRange, 8> LiveRanges;

  /// The set of allocas that have at least one lifetime.start. All other

  /// allocas get LiveRange that corresponds to the entire function.

  BitVector InterestingAllocas;

  struct Marker {

    unsigned AllocaNo;

    bool IsStart;

  };

  /// List of {InstNo, {AllocaNo, IsStart}} for each BB, ordered by InstNo.

  DenseMap<const BasicBlock *, SmallVector<std::pair<unsigned, Marker>, 4>>

      BBMarkers;

  bool HasUnknownLifetimeStartOrEnd = false;

  void dumpAllocas() const;

  void dumpBlockLiveness() const;

  void dumpLiveRanges() const;

  void collectMarkers();

  void calculateLocalLiveness();

  void calculateLiveIntervals();

public:

  StackLifetime(const Function &F, ArrayRef<const AllocaInst *> Allocas,

                LivenessType Type);

  void run();

  iterator_range<

      filter_iterator<ArrayRef<const IntrinsicInst *>::const_iterator,

                      std::function<bool(const IntrinsicInst *)>>>

  getMarkers() const {

    std::function<bool(const IntrinsicInst *)> NotNull(

        [](const IntrinsicInst *I) -> bool { return I; });

    return make_filter_range(Instructions, NotNull);

  }

  /// Returns a set of "interesting" instructions where the given alloca is

  /// live. Not all instructions in a function are interesting: we pick a set

  /// that is large enough for LiveRange::Overlaps to be correct.

  const LiveRange &getLiveRange(const AllocaInst *AI) const;

  /// Returns true if instruction is reachable from entry.

  bool isReachable(const Instruction *I) const;

  /// Returns true if the alloca is alive after the instruction.

  bool isAliveAfter(const AllocaInst *AI, const Instruction *I) const;

  /// Returns a live range that represents an alloca that is live throughout the

  /// entire function.

  LiveRange getFullLiveRange() const {

    return LiveRange(Instructions.size(), true);

  }

  void print(raw_ostream &O);

};

static inline raw_ostream &operator<<(raw_ostream &OS, const BitVector &V) {

  OS << "{";

  ListSeparator LS;

  for (int Idx = V.find_first(); Idx >= 0; Idx = V.find_next(Idx))

    OS << LS << Idx;

  OS << "}";

  return OS;

}

inline raw_ostream &operator<<(raw_ostream &OS,

                               const StackLifetime::LiveRange &R) {

  return OS << R.Bits;

}

/// Printer pass for testing.

class StackLifetimePrinterPass

    : public PassInfoMixin<StackLifetimePrinterPass> {

  StackLifetime::LivenessType Type;

  raw_ostream &OS;

public:

  StackLifetimePrinterPass(raw_ostream &OS, StackLifetime::LivenessType Type)

      : Type(Type), OS(OS) {}

  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);

  void printPipeline(raw_ostream &OS,

                     function_ref<StringRef(StringRef)> MapClassName2PassName);

};

} // end namespace llvm

#endif // LLVM_ANALYSIS_STACKLIFETIME_H