Merge "Update prebuilt Clang to r353983." into p9.0HEADp9.0-backupp9.0

1 files changed, 169 insertions, 0 deletions

diff --git a/clang-r353983/include/llvm/Analysis/MustExecute.h b/clang-r353983/include/llvm/Analysis/MustExecute.h
new file mode 100644
index 00000000..3ef539c8
--- /dev/null
+++ b/clang-r353983/include/llvm/Analysis/MustExecute.h
@@ -0,0 +1,169 @@
+//===- MustExecute.h - Is an instruction known to execute--------*- 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
+/// Contains a collection of routines for determining if a given instruction is
+/// guaranteed to execute if a given point in control flow is reached.  The most
+/// common example is an instruction within a loop being provably executed if we
+/// branch to the header of it's containing loop.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_MUSTEXECUTE_H
+#define LLVM_ANALYSIS_MUSTEXECUTE_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/Analysis/EHPersonalities.h"
+#include "llvm/Analysis/InstructionPrecedenceTracking.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Instruction.h"
+
+namespace llvm {
+
+class Instruction;
+class DominatorTree;
+class Loop;
+
+/// Captures loop safety information.
+/// It keep information for loop blocks may throw exception or otherwise
+/// exit abnormaly on any iteration of the loop which might actually execute
+/// at runtime.  The primary way to consume this infromation is via
+/// isGuaranteedToExecute below, but some callers bailout or fallback to
+/// alternate reasoning if a loop contains any implicit control flow.
+/// NOTE: LoopSafetyInfo contains cached information regarding loops and their
+/// particular blocks. This information is only dropped on invocation of
+/// computeLoopSafetyInfo. If the loop or any of its block is deleted, or if
+/// any thrower instructions have been added or removed from them, or if the
+/// control flow has changed, or in case of other meaningful modifications, the
+/// LoopSafetyInfo needs to be recomputed. If a meaningful modifications to the
+/// loop were made and the info wasn't recomputed properly, the behavior of all
+/// methods except for computeLoopSafetyInfo is undefined.
+class LoopSafetyInfo {
+  // Used to update funclet bundle operands.
+  DenseMap<BasicBlock *, ColorVector> BlockColors;
+
+protected:
+  /// Computes block colors.
+  void computeBlockColors(const Loop *CurLoop);
+
+public:
+  /// Returns block colors map that is used to update funclet operand bundles.
+  const DenseMap<BasicBlock *, ColorVector> &getBlockColors() const;
+
+  /// Copy colors of block \p Old into the block \p New.
+  void copyColors(BasicBlock *New, BasicBlock *Old);
+
+  /// Returns true iff the block \p BB potentially may throw exception. It can
+  /// be false-positive in cases when we want to avoid complex analysis.
+  virtual bool blockMayThrow(const BasicBlock *BB) const = 0;
+
+  /// Returns true iff any block of the loop for which this info is contains an
+  /// instruction that may throw or otherwise exit abnormally.
+  virtual bool anyBlockMayThrow() const = 0;
+
+  /// Return true if we must reach the block \p BB under assumption that the
+  /// loop \p CurLoop is entered.
+  bool allLoopPathsLeadToBlock(const Loop *CurLoop, const BasicBlock *BB,
+                               const DominatorTree *DT) const;
+
+  /// Computes safety information for a loop checks loop body & header for
+  /// the possibility of may throw exception, it takes LoopSafetyInfo and loop
+  /// as argument. Updates safety information in LoopSafetyInfo argument.
+  /// Note: This is defined to clear and reinitialize an already initialized
+  /// LoopSafetyInfo.  Some callers rely on this fact.
+  virtual void computeLoopSafetyInfo(const Loop *CurLoop) = 0;
+
+  /// Returns true if the instruction in a loop is guaranteed to execute at
+  /// least once (under the assumption that the loop is entered).
+  virtual bool isGuaranteedToExecute(const Instruction &Inst,
+                                     const DominatorTree *DT,
+                                     const Loop *CurLoop) const = 0;
+
+  LoopSafetyInfo() = default;
+
+  virtual ~LoopSafetyInfo() = default;
+};
+
+
+/// Simple and conservative implementation of LoopSafetyInfo that can give
+/// false-positive answers to its queries in order to avoid complicated
+/// analysis.
+class SimpleLoopSafetyInfo: public LoopSafetyInfo {
+  bool MayThrow = false;       // The current loop contains an instruction which
+                               // may throw.
+  bool HeaderMayThrow = false; // Same as previous, but specific to loop header
+
+public:
+  virtual bool blockMayThrow(const BasicBlock *BB) const;
+
+  virtual bool anyBlockMayThrow() const;
+
+  virtual void computeLoopSafetyInfo(const Loop *CurLoop);
+
+  virtual bool isGuaranteedToExecute(const Instruction &Inst,
+                                     const DominatorTree *DT,
+                                     const Loop *CurLoop) const;
+
+  SimpleLoopSafetyInfo() : LoopSafetyInfo() {};
+
+  virtual ~SimpleLoopSafetyInfo() {};
+};
+
+/// This implementation of LoopSafetyInfo use ImplicitControlFlowTracking to
+/// give precise answers on "may throw" queries. This implementation uses cache
+/// that should be invalidated by calling the methods insertInstructionTo and
+/// removeInstruction whenever we modify a basic block's contents by adding or
+/// removing instructions.
+class ICFLoopSafetyInfo: public LoopSafetyInfo {
+  bool MayThrow = false;       // The current loop contains an instruction which
+                               // may throw.
+  // Contains information about implicit control flow in this loop's blocks.
+  mutable ImplicitControlFlowTracking ICF;
+  // Contains information about instruction that may possibly write memory.
+  mutable MemoryWriteTracking MW;
+
+public:
+  virtual bool blockMayThrow(const BasicBlock *BB) const;
+
+  virtual bool anyBlockMayThrow() const;
+
+  virtual void computeLoopSafetyInfo(const Loop *CurLoop);
+
+  virtual bool isGuaranteedToExecute(const Instruction &Inst,
+                                     const DominatorTree *DT,
+                                     const Loop *CurLoop) const;
+
+  /// Returns true if we could not execute a memory-modifying instruction before
+  /// we enter \p BB under assumption that \p CurLoop is entered.
+  bool doesNotWriteMemoryBefore(const BasicBlock *BB, const Loop *CurLoop)
+      const;
+
+  /// Returns true if we could not execute a memory-modifying instruction before
+  /// we execute \p I under assumption that \p CurLoop is entered.
+  bool doesNotWriteMemoryBefore(const Instruction &I, const Loop *CurLoop)
+      const;
+
+  /// Inform the safety info that we are planning to insert a new instruction
+  /// \p Inst into the basic block \p BB. It will make all cache updates to keep
+  /// it correct after this insertion.
+  void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB);
+
+  /// Inform safety info that we are planning to remove the instruction \p Inst
+  /// from its block. It will make all cache updates to keep it correct after
+  /// this removal.
+  void removeInstruction(const Instruction *Inst);
+
+  ICFLoopSafetyInfo(DominatorTree *DT) : LoopSafetyInfo(), ICF(DT), MW(DT) {};
+
+  virtual ~ICFLoopSafetyInfo() {};
+};
+
+}
+
+#endif