| //===- 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); |
| void printPipeline(raw_ostream &OS, |
| function_ref<StringRef(StringRef)> MapClassName2PassName); |
| }; |
| |
| } // end namespace llvm |
| |
| #endif // LLVM_ANALYSIS_STACKLIFETIME_H |