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/LoopNestAnalysis.h b/linux-x64/clang/include/llvm/Analysis/LoopNestAnalysis.h
new file mode 100644
index 0000000..9c4fb4d
--- /dev/null
+++ b/linux-x64/clang/include/llvm/Analysis/LoopNestAnalysis.h
@@ -0,0 +1,175 @@
+//===- llvm/Analysis/LoopNestAnalysis.h -------------------------*- 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
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// This file defines the interface for the loop nest analysis.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_LOOPNESTANALYSIS_H
+#define LLVM_ANALYSIS_LOOPNESTANALYSIS_H
+
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Analysis/LoopAnalysisManager.h"
+#include "llvm/Analysis/LoopInfo.h"
+
+namespace llvm {
+
+using LoopVectorTy = SmallVector<Loop *, 8>;
+class LPMUpdater;
+
+/// This class represents a loop nest and can be used to query its properties.
+class LoopNest {
+public:
+ /// Construct a loop nest rooted by loop \p Root.
+ LoopNest(Loop &Root, ScalarEvolution &SE);
+
+ LoopNest() = delete;
+ LoopNest &operator=(const LoopNest &) = delete;
+
+ /// Construct a LoopNest object.
+ static std::unique_ptr<LoopNest> getLoopNest(Loop &Root, ScalarEvolution &SE);
+
+ /// Return true if the given loops \p OuterLoop and \p InnerLoop are
+ /// perfectly nested with respect to each other, and false otherwise.
+ /// Example:
+ /// \code
+ /// for(i)
+ /// for(j)
+ /// for(k)
+ /// \endcode
+ /// arePerfectlyNested(loop_i, loop_j, SE) would return true.
+ /// arePerfectlyNested(loop_j, loop_k, SE) would return true.
+ /// arePerfectlyNested(loop_i, loop_k, SE) would return false.
+ static bool arePerfectlyNested(const Loop &OuterLoop, const Loop &InnerLoop,
+ ScalarEvolution &SE);
+
+ /// Return the maximum nesting depth of the loop nest rooted by loop \p Root.
+ /// For example given the loop nest:
+ /// \code
+ /// for(i) // loop at level 1 and Root of the nest
+ /// for(j) // loop at level 2
+ /// <code>
+ /// for(k) // loop at level 3
+ /// \endcode
+ /// getMaxPerfectDepth(Loop_i) would return 2.
+ static unsigned getMaxPerfectDepth(const Loop &Root, ScalarEvolution &SE);
+
+ /// Recursivelly traverse all empty 'single successor' basic blocks of \p From
+ /// (if there are any). Return the last basic block found or \p End if it was
+ /// reached during the search.
+ static const BasicBlock &skipEmptyBlockUntil(const BasicBlock *From,
+ const BasicBlock *End);
+
+ /// Return the outermost loop in the loop nest.
+ Loop &getOutermostLoop() const { return *Loops.front(); }
+
+ /// Return the innermost loop in the loop nest if the nest has only one
+ /// innermost loop, and a nullptr otherwise.
+ /// Note: the innermost loop returned is not necessarily perfectly nested.
+ Loop *getInnermostLoop() const {
+ if (Loops.size() == 1)
+ return Loops.back();
+
+ // The loops in the 'Loops' vector have been collected in breadth first
+ // order, therefore if the last 2 loops in it have the same nesting depth
+ // there isn't a unique innermost loop in the nest.
+ Loop *LastLoop = Loops.back();
+ auto SecondLastLoopIter = ++Loops.rbegin();
+ return (LastLoop->getLoopDepth() == (*SecondLastLoopIter)->getLoopDepth())
+ ? nullptr
+ : LastLoop;
+ }
+
+ /// Return the loop at the given \p Index.
+ Loop *getLoop(unsigned Index) const {
+ assert(Index < Loops.size() && "Index is out of bounds");
+ return Loops[Index];
+ }
+
+ /// Return the number of loops in the nest.
+ size_t getNumLoops() const { return Loops.size(); }
+
+ /// Get the loops in the nest.
+ ArrayRef<Loop *> getLoops() const { return Loops; }
+
+ /// Retrieve a vector of perfect loop nests contained in the current loop
+ /// nest. For example, given the following nest containing 4 loops, this
+ /// member function would return {{L1,L2},{L3,L4}}.
+ /// \code
+ /// for(i) // L1
+ /// for(j) // L2
+ /// <code>
+ /// for(k) // L3
+ /// for(l) // L4
+ /// \endcode
+ SmallVector<LoopVectorTy, 4> getPerfectLoops(ScalarEvolution &SE) const;
+
+ /// Return the loop nest depth (i.e. the loop depth of the 'deepest' loop)
+ /// For example given the loop nest:
+ /// \code
+ /// for(i) // loop at level 1 and Root of the nest
+ /// for(j1) // loop at level 2
+ /// for(k) // loop at level 3
+ /// for(j2) // loop at level 2
+ /// \endcode
+ /// getNestDepth() would return 3.
+ unsigned getNestDepth() const {
+ int NestDepth =
+ Loops.back()->getLoopDepth() - Loops.front()->getLoopDepth() + 1;
+ assert(NestDepth > 0 && "Expecting NestDepth to be at least 1");
+ return NestDepth;
+ }
+
+ /// Return the maximum perfect nesting depth.
+ unsigned getMaxPerfectDepth() const { return MaxPerfectDepth; }
+
+ /// Return true if all loops in the loop nest are in simplify form.
+ bool areAllLoopsSimplifyForm() const {
+ return all_of(Loops, [](const Loop *L) { return L->isLoopSimplifyForm(); });
+ }
+
+ /// Return true if all loops in the loop nest are in rotated form.
+ bool areAllLoopsRotatedForm() const {
+ return all_of(Loops, [](const Loop *L) { return L->isRotatedForm(); });
+ }
+
+ StringRef getName() const { return Loops.front()->getName(); }
+
+protected:
+ const unsigned MaxPerfectDepth; // maximum perfect nesting depth level.
+ LoopVectorTy Loops; // the loops in the nest (in breadth first order).
+};
+
+raw_ostream &operator<<(raw_ostream &, const LoopNest &);
+
+/// This analysis provides information for a loop nest. The analysis runs on
+/// demand and can be initiated via AM.getResult<LoopNestAnalysis>.
+class LoopNestAnalysis : public AnalysisInfoMixin<LoopNestAnalysis> {
+ friend AnalysisInfoMixin<LoopNestAnalysis>;
+ static AnalysisKey Key;
+
+public:
+ using Result = LoopNest;
+ Result run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR);
+};
+
+/// Printer pass for the \c LoopNest results.
+class LoopNestPrinterPass : public PassInfoMixin<LoopNestPrinterPass> {
+ raw_ostream &OS;
+
+public:
+ explicit LoopNestPrinterPass(raw_ostream &OS) : OS(OS) {}
+
+ PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
+ LoopStandardAnalysisResults &AR, LPMUpdater &U);
+};
+
+} // namespace llvm
+
+#endif // LLVM_ANALYSIS_LOOPNESTANALYSIS_H