Update prebuilt Clang to r416183b from Android.
https://android.googlesource.com/platform/prebuilts/clang/host/
linux-x86/+/06a71ddac05c22edb2d10b590e1769b3f8619bef
clang 12.0.5 (based on r416183b) from build 7284624.
Change-Id: I277a316abcf47307562d8b748b84870f31a72866
Signed-off-by: Olivier Deprez <olivier.deprez@arm.com>
diff --git a/linux-x64/clang/include/llvm/Analysis/StackLifetime.h b/linux-x64/clang/include/llvm/Analysis/StackLifetime.h
new file mode 100644
index 0000000..1c0e103
--- /dev/null
+++ b/linux-x64/clang/include/llvm/Analysis/StackLifetime.h
@@ -0,0 +1,204 @@
+//===- 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/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 << "{";
+ int Idx = V.find_first();
+ bool First = true;
+ while (Idx >= 0) {
+ if (!First) {
+ OS << ", ";
+ }
+ First = false;
+ OS << Idx;
+ Idx = V.find_next(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