intermediate changes

ref:cde9a383711a11544ce7e107a78147fb96cc4029

1 files changed, 209 insertions, 0 deletions

diff --git a/contrib/libs/llvm12/include/llvm/Analysis/StackLifetime.h b/contrib/libs/llvm12/include/llvm/Analysis/StackLifetime.h
new file mode 100644
index 0000000000..c17d154b19
--- /dev/null
+++ b/contrib/libs/llvm12/include/llvm/Analysis/StackLifetime.h
@@ -0,0 +1,209 @@
+#pragma once
+
+#ifdef __GNUC__
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wunused-parameter"
+#endif
+
+//===- 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/IntrinsicInst.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/Support/raw_ostream.h"
+#include <cassert>
+#include <utility>
+
+namespace llvm {
+
+class AllocaInst;
+class BasicBlock;
+class Function;
+class Instruction;
+
+/// 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);
+};
+
+} // end namespace llvm
+
+#endif // LLVM_ANALYSIS_STACKLIFETIME_H
+
+#ifdef __GNUC__
+#pragma GCC diagnostic pop
+#endif