Update clang to r339409b.
Change-Id: Ied8a188bb072c40035320acedc86164b66d920af
diff --git a/linux-x64/clang/include/llvm/Analysis/AliasSetTracker.h b/linux-x64/clang/include/llvm/Analysis/AliasSetTracker.h
index 0e6d229..cf4981d 100644
--- a/linux-x64/clang/include/llvm/Analysis/AliasSetTracker.h
+++ b/linux-x64/clang/include/llvm/Analysis/AliasSetTracker.h
@@ -52,9 +52,13 @@
PointerRec **PrevInList = nullptr;
PointerRec *NextInList = nullptr;
AliasSet *AS = nullptr;
- LocationSize Size = 0;
+ LocationSize Size = LocationSize::mapEmpty();
AAMDNodes AAInfo;
+ // Whether the size for this record has been set at all. This makes no
+ // guarantees about the size being known.
+ bool isSizeSet() const { return Size != LocationSize::mapEmpty(); }
+
public:
PointerRec(Value *V)
: Val(V), AAInfo(DenseMapInfo<AAMDNodes>::getEmptyKey()) {}
@@ -71,9 +75,10 @@
bool updateSizeAndAAInfo(LocationSize NewSize, const AAMDNodes &NewAAInfo) {
bool SizeChanged = false;
- if (NewSize > Size) {
- Size = NewSize;
- SizeChanged = true;
+ if (NewSize != Size) {
+ LocationSize OldSize = Size;
+ Size = isSizeSet() ? Size.unionWith(NewSize) : NewSize;
+ SizeChanged = OldSize != Size;
}
if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey())
@@ -91,7 +96,10 @@
return SizeChanged;
}
- LocationSize getSize() const { return Size; }
+ LocationSize getSize() const {
+ assert(isSizeSet() && "Getting an unset size!");
+ return Size;
+ }
/// Return the AAInfo, or null if there is no information or conflicting
/// information.
@@ -175,9 +183,6 @@
};
unsigned Alias : 1;
- /// True if this alias set contains volatile loads or stores.
- unsigned Volatile : 1;
-
unsigned SetSize = 0;
void addRef() { ++RefCount; }
@@ -203,9 +208,6 @@
bool isMustAlias() const { return Alias == SetMustAlias; }
bool isMayAlias() const { return Alias == SetMayAlias; }
- /// Return true if this alias set contains volatile loads or stores.
- bool isVolatile() const { return Volatile; }
-
/// Return true if this alias set should be ignored as part of the
/// AliasSetTracker object.
bool isForwardingAliasSet() const { return Forward; }
@@ -226,17 +228,7 @@
/// If this alias set is known to contain a single instruction and *only* a
/// single unique instruction, return it. Otherwise, return nullptr.
- Instruction* getUniqueInstruction() {
- if (size() != 0)
- // Can't track source of pointer, might be many instruction
- return nullptr;
- if (AliasAny)
- // May have collapses alias set
- return nullptr;
- if (1 != UnknownInsts.size())
- return nullptr;
- return cast<Instruction>(UnknownInsts[0]);
- }
+ Instruction* getUniqueInstruction();
void print(raw_ostream &OS) const;
void dump() const;
@@ -278,7 +270,7 @@
// Can only be created by AliasSetTracker.
AliasSet()
: PtrListEnd(&PtrList), RefCount(0), AliasAny(false), Access(NoAccess),
- Alias(SetMustAlias), Volatile(false) {}
+ Alias(SetMustAlias) {}
PointerRec *getSomePointer() const {
return PtrList;
@@ -317,8 +309,6 @@
dropRef(AST);
}
- void setVolatile() { Volatile = true; }
-
public:
/// Return true if the specified pointer "may" (or must) alias one of the
/// members in the set.
@@ -393,19 +383,11 @@
/// Return the alias sets that are active.
const ilist<AliasSet> &getAliasSets() const { return AliasSets; }
- /// Return the alias set that the specified pointer lives in. If the New
- /// argument is non-null, this method sets the value to true if a new alias
- /// set is created to contain the pointer (because the pointer didn't alias
- /// anything).
- AliasSet &getAliasSetForPointer(Value *P, LocationSize Size,
- const AAMDNodes &AAInfo);
-
- /// Return the alias set containing the location specified if one exists,
- /// otherwise return null.
- AliasSet *getAliasSetForPointerIfExists(const Value *P, LocationSize Size,
- const AAMDNodes &AAInfo) {
- return mergeAliasSetsForPointer(P, Size, AAInfo);
- }
+ /// Return the alias set which contains the specified memory location. If
+ /// the memory location aliases two or more existing alias sets, will have
+ /// the effect of merging those alias sets before the single resulting alias
+ /// set is returned.
+ AliasSet &getAliasSetFor(const MemoryLocation &MemLoc);
/// Return true if the specified instruction "may" (or must) alias one of the
/// members in any of the sets.
@@ -461,6 +443,10 @@
AliasSet &addPointer(Value *P, LocationSize Size, const AAMDNodes &AAInfo,
AliasSet::AccessLattice E);
+ AliasSet &addPointer(MemoryLocation Loc,
+ AliasSet::AccessLattice E) {
+ return addPointer(const_cast<Value*>(Loc.Ptr), Loc.Size, Loc.AATags, E);
+ }
AliasSet *mergeAliasSetsForPointer(const Value *Ptr, LocationSize Size,
const AAMDNodes &AAInfo);
diff --git a/linux-x64/clang/include/llvm/Analysis/CFGPrinter.h b/linux-x64/clang/include/llvm/Analysis/CFGPrinter.h
index 5786769..a4b642b 100644
--- a/linux-x64/clang/include/llvm/Analysis/CFGPrinter.h
+++ b/linux-x64/clang/include/llvm/Analysis/CFGPrinter.h
@@ -172,8 +172,7 @@
// Prepend a 'W' to indicate that this is a weight rather than the actual
// profile count (due to scaling).
- Twine Attrs = "label=\"W:" + Twine(Weight->getZExtValue()) + "\"";
- return Attrs.str();
+ return ("label=\"W:" + Twine(Weight->getZExtValue()) + "\"").str();
}
};
} // End llvm namespace
diff --git a/linux-x64/clang/include/llvm/Analysis/CGSCCPassManager.h b/linux-x64/clang/include/llvm/Analysis/CGSCCPassManager.h
index 5e83ea2..f150064 100644
--- a/linux-x64/clang/include/llvm/Analysis/CGSCCPassManager.h
+++ b/linux-x64/clang/include/llvm/Analysis/CGSCCPassManager.h
@@ -364,6 +364,10 @@
InvalidSCCSet, nullptr, nullptr,
InlinedInternalEdges};
+ // Request PassInstrumentation from analysis manager, will use it to run
+ // instrumenting callbacks for the passes later.
+ PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(M);
+
PreservedAnalyses PA = PreservedAnalyses::all();
CG.buildRefSCCs();
for (auto RCI = CG.postorder_ref_scc_begin(),
@@ -428,8 +432,17 @@
UR.UpdatedRC = nullptr;
UR.UpdatedC = nullptr;
+
+ // Check the PassInstrumentation's BeforePass callbacks before
+ // running the pass, skip its execution completely if asked to
+ // (callback returns false).
+ if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C))
+ continue;
+
PreservedAnalyses PassPA = Pass.run(*C, CGAM, CG, UR);
+ PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C);
+
// Update the SCC and RefSCC if necessary.
C = UR.UpdatedC ? UR.UpdatedC : C;
RC = UR.UpdatedRC ? UR.UpdatedRC : RC;
@@ -615,12 +628,20 @@
if (CG.lookupSCC(*N) != CurrentC)
continue;
- PreservedAnalyses PassPA = Pass.run(N->getFunction(), FAM);
+ Function &F = N->getFunction();
+
+ PassInstrumentation PI = FAM.getResult<PassInstrumentationAnalysis>(F);
+ if (!PI.runBeforePass<Function>(Pass, F))
+ continue;
+
+ PreservedAnalyses PassPA = Pass.run(F, FAM);
+
+ PI.runAfterPass<Function>(Pass, F);
// We know that the function pass couldn't have invalidated any other
// function's analyses (that's the contract of a function pass), so
// directly handle the function analysis manager's invalidation here.
- FAM.invalidate(N->getFunction(), PassPA);
+ FAM.invalidate(F, PassPA);
// Then intersect the preserved set so that invalidation of module
// analyses will eventually occur when the module pass completes.
@@ -690,6 +711,8 @@
PreservedAnalyses run(LazyCallGraph::SCC &InitialC, CGSCCAnalysisManager &AM,
LazyCallGraph &CG, CGSCCUpdateResult &UR) {
PreservedAnalyses PA = PreservedAnalyses::all();
+ PassInstrumentation PI =
+ AM.getResult<PassInstrumentationAnalysis>(InitialC, CG);
// The SCC may be refined while we are running passes over it, so set up
// a pointer that we can update.
@@ -733,8 +756,14 @@
auto CallCounts = ScanSCC(*C, CallHandles);
for (int Iteration = 0;; ++Iteration) {
+
+ if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C))
+ continue;
+
PreservedAnalyses PassPA = Pass.run(*C, AM, CG, UR);
+ PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C);
+
// If the SCC structure has changed, bail immediately and let the outer
// CGSCC layer handle any iteration to reflect the refined structure.
if (UR.UpdatedC && UR.UpdatedC != C) {
diff --git a/linux-x64/clang/include/llvm/Analysis/GuardUtils.h b/linux-x64/clang/include/llvm/Analysis/GuardUtils.h
new file mode 100644
index 0000000..3b151ee
--- /dev/null
+++ b/linux-x64/clang/include/llvm/Analysis/GuardUtils.h
@@ -0,0 +1,26 @@
+//===-- GuardUtils.h - Utils for work with guards ---------------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// Utils that are used to perform analyzes related to guards and their
+// conditions.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_GUARDUTILS_H
+#define LLVM_ANALYSIS_GUARDUTILS_H
+
+namespace llvm {
+
+class User;
+
+/// Returns true iff \p U has semantics of a guard.
+bool isGuard(const User *U);
+
+} // llvm
+
+#endif // LLVM_ANALYSIS_GUARDUTILS_H
+
diff --git a/linux-x64/clang/include/llvm/Analysis/IVDescriptors.h b/linux-x64/clang/include/llvm/Analysis/IVDescriptors.h
new file mode 100644
index 0000000..d1d7e5e
--- /dev/null
+++ b/linux-x64/clang/include/llvm/Analysis/IVDescriptors.h
@@ -0,0 +1,352 @@
+//===- llvm/Analysis/IVDescriptors.h - IndVar Descriptors -------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file "describes" induction and recurrence variables.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_IVDESCRIPTORS_H
+#define LLVM_ANALYSIS_IVDESCRIPTORS_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/DemandedBits.h"
+#include "llvm/Analysis/EHPersonalities.h"
+#include "llvm/Analysis/MustExecute.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/InstrTypes.h"
+#include "llvm/IR/Operator.h"
+#include "llvm/IR/ValueHandle.h"
+#include "llvm/Support/Casting.h"
+
+namespace llvm {
+
+class AliasSet;
+class AliasSetTracker;
+class BasicBlock;
+class DataLayout;
+class Loop;
+class LoopInfo;
+class OptimizationRemarkEmitter;
+class PredicatedScalarEvolution;
+class PredIteratorCache;
+class ScalarEvolution;
+class SCEV;
+class TargetLibraryInfo;
+class TargetTransformInfo;
+
+/// The RecurrenceDescriptor is used to identify recurrences variables in a
+/// loop. Reduction is a special case of recurrence that has uses of the
+/// recurrence variable outside the loop. The method isReductionPHI identifies
+/// reductions that are basic recurrences.
+///
+/// Basic recurrences are defined as the summation, product, OR, AND, XOR, min,
+/// or max of a set of terms. For example: for(i=0; i<n; i++) { total +=
+/// array[i]; } is a summation of array elements. Basic recurrences are a
+/// special case of chains of recurrences (CR). See ScalarEvolution for CR
+/// references.
+
+/// This struct holds information about recurrence variables.
+class RecurrenceDescriptor {
+public:
+ /// This enum represents the kinds of recurrences that we support.
+ enum RecurrenceKind {
+ RK_NoRecurrence, ///< Not a recurrence.
+ RK_IntegerAdd, ///< Sum of integers.
+ RK_IntegerMult, ///< Product of integers.
+ RK_IntegerOr, ///< Bitwise or logical OR of numbers.
+ RK_IntegerAnd, ///< Bitwise or logical AND of numbers.
+ RK_IntegerXor, ///< Bitwise or logical XOR of numbers.
+ RK_IntegerMinMax, ///< Min/max implemented in terms of select(cmp()).
+ RK_FloatAdd, ///< Sum of floats.
+ RK_FloatMult, ///< Product of floats.
+ RK_FloatMinMax ///< Min/max implemented in terms of select(cmp()).
+ };
+
+ // This enum represents the kind of minmax recurrence.
+ enum MinMaxRecurrenceKind {
+ MRK_Invalid,
+ MRK_UIntMin,
+ MRK_UIntMax,
+ MRK_SIntMin,
+ MRK_SIntMax,
+ MRK_FloatMin,
+ MRK_FloatMax
+ };
+
+ RecurrenceDescriptor() = default;
+
+ RecurrenceDescriptor(Value *Start, Instruction *Exit, RecurrenceKind K,
+ MinMaxRecurrenceKind MK, Instruction *UAI, Type *RT,
+ bool Signed, SmallPtrSetImpl<Instruction *> &CI)
+ : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK),
+ UnsafeAlgebraInst(UAI), RecurrenceType(RT), IsSigned(Signed) {
+ CastInsts.insert(CI.begin(), CI.end());
+ }
+
+ /// This POD struct holds information about a potential recurrence operation.
+ class InstDesc {
+ public:
+ InstDesc(bool IsRecur, Instruction *I, Instruction *UAI = nullptr)
+ : IsRecurrence(IsRecur), PatternLastInst(I), MinMaxKind(MRK_Invalid),
+ UnsafeAlgebraInst(UAI) {}
+
+ InstDesc(Instruction *I, MinMaxRecurrenceKind K, Instruction *UAI = nullptr)
+ : IsRecurrence(true), PatternLastInst(I), MinMaxKind(K),
+ UnsafeAlgebraInst(UAI) {}
+
+ bool isRecurrence() { return IsRecurrence; }
+
+ bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
+
+ Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
+
+ MinMaxRecurrenceKind getMinMaxKind() { return MinMaxKind; }
+
+ Instruction *getPatternInst() { return PatternLastInst; }
+
+ private:
+ // Is this instruction a recurrence candidate.
+ bool IsRecurrence;
+ // The last instruction in a min/max pattern (select of the select(icmp())
+ // pattern), or the current recurrence instruction otherwise.
+ Instruction *PatternLastInst;
+ // If this is a min/max pattern the comparison predicate.
+ MinMaxRecurrenceKind MinMaxKind;
+ // Recurrence has unsafe algebra.
+ Instruction *UnsafeAlgebraInst;
+ };
+
+ /// Returns a struct describing if the instruction 'I' can be a recurrence
+ /// variable of type 'Kind'. If the recurrence is a min/max pattern of
+ /// select(icmp()) this function advances the instruction pointer 'I' from the
+ /// compare instruction to the select instruction and stores this pointer in
+ /// 'PatternLastInst' member of the returned struct.
+ static InstDesc isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
+ InstDesc &Prev, bool HasFunNoNaNAttr);
+
+ /// Returns true if instruction I has multiple uses in Insts
+ static bool hasMultipleUsesOf(Instruction *I,
+ SmallPtrSetImpl<Instruction *> &Insts);
+
+ /// Returns true if all uses of the instruction I is within the Set.
+ static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl<Instruction *> &Set);
+
+ /// Returns a struct describing if the instruction if the instruction is a
+ /// Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y)
+ /// or max(X, Y).
+ static InstDesc isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev);
+
+ /// Returns identity corresponding to the RecurrenceKind.
+ static Constant *getRecurrenceIdentity(RecurrenceKind K, Type *Tp);
+
+ /// Returns the opcode of binary operation corresponding to the
+ /// RecurrenceKind.
+ static unsigned getRecurrenceBinOp(RecurrenceKind Kind);
+
+ /// Returns true if Phi is a reduction of type Kind and adds it to the
+ /// RecurrenceDescriptor. If either \p DB is non-null or \p AC and \p DT are
+ /// non-null, the minimal bit width needed to compute the reduction will be
+ /// computed.
+ static bool AddReductionVar(PHINode *Phi, RecurrenceKind Kind, Loop *TheLoop,
+ bool HasFunNoNaNAttr,
+ RecurrenceDescriptor &RedDes,
+ DemandedBits *DB = nullptr,
+ AssumptionCache *AC = nullptr,
+ DominatorTree *DT = nullptr);
+
+ /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor
+ /// is returned in RedDes. If either \p DB is non-null or \p AC and \p DT are
+ /// non-null, the minimal bit width needed to compute the reduction will be
+ /// computed.
+ static bool isReductionPHI(PHINode *Phi, Loop *TheLoop,
+ RecurrenceDescriptor &RedDes,
+ DemandedBits *DB = nullptr,
+ AssumptionCache *AC = nullptr,
+ DominatorTree *DT = nullptr);
+
+ /// Returns true if Phi is a first-order recurrence. A first-order recurrence
+ /// is a non-reduction recurrence relation in which the value of the
+ /// recurrence in the current loop iteration equals a value defined in the
+ /// previous iteration. \p SinkAfter includes pairs of instructions where the
+ /// first will be rescheduled to appear after the second if/when the loop is
+ /// vectorized. It may be augmented with additional pairs if needed in order
+ /// to handle Phi as a first-order recurrence.
+ static bool
+ isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop,
+ DenseMap<Instruction *, Instruction *> &SinkAfter,
+ DominatorTree *DT);
+
+ RecurrenceKind getRecurrenceKind() { return Kind; }
+
+ MinMaxRecurrenceKind getMinMaxRecurrenceKind() { return MinMaxKind; }
+
+ TrackingVH<Value> getRecurrenceStartValue() { return StartValue; }
+
+ Instruction *getLoopExitInstr() { return LoopExitInstr; }
+
+ /// Returns true if the recurrence has unsafe algebra which requires a relaxed
+ /// floating-point model.
+ bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
+
+ /// Returns first unsafe algebra instruction in the PHI node's use-chain.
+ Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
+
+ /// Returns true if the recurrence kind is an integer kind.
+ static bool isIntegerRecurrenceKind(RecurrenceKind Kind);
+
+ /// Returns true if the recurrence kind is a floating point kind.
+ static bool isFloatingPointRecurrenceKind(RecurrenceKind Kind);
+
+ /// Returns true if the recurrence kind is an arithmetic kind.
+ static bool isArithmeticRecurrenceKind(RecurrenceKind Kind);
+
+ /// Returns the type of the recurrence. This type can be narrower than the
+ /// actual type of the Phi if the recurrence has been type-promoted.
+ Type *getRecurrenceType() { return RecurrenceType; }
+
+ /// Returns a reference to the instructions used for type-promoting the
+ /// recurrence.
+ SmallPtrSet<Instruction *, 8> &getCastInsts() { return CastInsts; }
+
+ /// Returns true if all source operands of the recurrence are SExtInsts.
+ bool isSigned() { return IsSigned; }
+
+private:
+ // The starting value of the recurrence.
+ // It does not have to be zero!
+ TrackingVH<Value> StartValue;
+ // The instruction who's value is used outside the loop.
+ Instruction *LoopExitInstr = nullptr;
+ // The kind of the recurrence.
+ RecurrenceKind Kind = RK_NoRecurrence;
+ // If this a min/max recurrence the kind of recurrence.
+ MinMaxRecurrenceKind MinMaxKind = MRK_Invalid;
+ // First occurrence of unasfe algebra in the PHI's use-chain.
+ Instruction *UnsafeAlgebraInst = nullptr;
+ // The type of the recurrence.
+ Type *RecurrenceType = nullptr;
+ // True if all source operands of the recurrence are SExtInsts.
+ bool IsSigned = false;
+ // Instructions used for type-promoting the recurrence.
+ SmallPtrSet<Instruction *, 8> CastInsts;
+};
+
+/// A struct for saving information about induction variables.
+class InductionDescriptor {
+public:
+ /// This enum represents the kinds of inductions that we support.
+ enum InductionKind {
+ IK_NoInduction, ///< Not an induction variable.
+ IK_IntInduction, ///< Integer induction variable. Step = C.
+ IK_PtrInduction, ///< Pointer induction var. Step = C / sizeof(elem).
+ IK_FpInduction ///< Floating point induction variable.
+ };
+
+public:
+ /// Default constructor - creates an invalid induction.
+ InductionDescriptor() = default;
+
+ /// Get the consecutive direction. Returns:
+ /// 0 - unknown or non-consecutive.
+ /// 1 - consecutive and increasing.
+ /// -1 - consecutive and decreasing.
+ int getConsecutiveDirection() const;
+
+ Value *getStartValue() const { return StartValue; }
+ InductionKind getKind() const { return IK; }
+ const SCEV *getStep() const { return Step; }
+ BinaryOperator *getInductionBinOp() const { return InductionBinOp; }
+ ConstantInt *getConstIntStepValue() const;
+
+ /// Returns true if \p Phi is an induction in the loop \p L. If \p Phi is an
+ /// induction, the induction descriptor \p D will contain the data describing
+ /// this induction. If by some other means the caller has a better SCEV
+ /// expression for \p Phi than the one returned by the ScalarEvolution
+ /// analysis, it can be passed through \p Expr. If the def-use chain
+ /// associated with the phi includes casts (that we know we can ignore
+ /// under proper runtime checks), they are passed through \p CastsToIgnore.
+ static bool
+ isInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE,
+ InductionDescriptor &D, const SCEV *Expr = nullptr,
+ SmallVectorImpl<Instruction *> *CastsToIgnore = nullptr);
+
+ /// Returns true if \p Phi is a floating point induction in the loop \p L.
+ /// If \p Phi is an induction, the induction descriptor \p D will contain
+ /// the data describing this induction.
+ static bool isFPInductionPHI(PHINode *Phi, const Loop *L, ScalarEvolution *SE,
+ InductionDescriptor &D);
+
+ /// Returns true if \p Phi is a loop \p L induction, in the context associated
+ /// with the run-time predicate of PSE. If \p Assume is true, this can add
+ /// further SCEV predicates to \p PSE in order to prove that \p Phi is an
+ /// induction.
+ /// If \p Phi is an induction, \p D will contain the data describing this
+ /// induction.
+ static bool isInductionPHI(PHINode *Phi, const Loop *L,
+ PredicatedScalarEvolution &PSE,
+ InductionDescriptor &D, bool Assume = false);
+
+ /// Returns true if the induction type is FP and the binary operator does
+ /// not have the "fast-math" property. Such operation requires a relaxed FP
+ /// mode.
+ bool hasUnsafeAlgebra() {
+ return InductionBinOp && !cast<FPMathOperator>(InductionBinOp)->isFast();
+ }
+
+ /// Returns induction operator that does not have "fast-math" property
+ /// and requires FP unsafe mode.
+ Instruction *getUnsafeAlgebraInst() {
+ if (!InductionBinOp || cast<FPMathOperator>(InductionBinOp)->isFast())
+ return nullptr;
+ return InductionBinOp;
+ }
+
+ /// Returns binary opcode of the induction operator.
+ Instruction::BinaryOps getInductionOpcode() const {
+ return InductionBinOp ? InductionBinOp->getOpcode()
+ : Instruction::BinaryOpsEnd;
+ }
+
+ /// Returns a reference to the type cast instructions in the induction
+ /// update chain, that are redundant when guarded with a runtime
+ /// SCEV overflow check.
+ const SmallVectorImpl<Instruction *> &getCastInsts() const {
+ return RedundantCasts;
+ }
+
+private:
+ /// Private constructor - used by \c isInductionPHI.
+ InductionDescriptor(Value *Start, InductionKind K, const SCEV *Step,
+ BinaryOperator *InductionBinOp = nullptr,
+ SmallVectorImpl<Instruction *> *Casts = nullptr);
+
+ /// Start value.
+ TrackingVH<Value> StartValue;
+ /// Induction kind.
+ InductionKind IK = IK_NoInduction;
+ /// Step value.
+ const SCEV *Step = nullptr;
+ // Instruction that advances induction variable.
+ BinaryOperator *InductionBinOp = nullptr;
+ // Instructions used for type-casts of the induction variable,
+ // that are redundant when guarded with a runtime SCEV overflow check.
+ SmallVector<Instruction *, 2> RedundantCasts;
+};
+
+} // end namespace llvm
+
+#endif // LLVM_ANALYSIS_IVDESCRIPTORS_H
diff --git a/linux-x64/clang/include/llvm/Analysis/IndirectCallSiteVisitor.h b/linux-x64/clang/include/llvm/Analysis/IndirectCallSiteVisitor.h
index dde56a1..a30b59f 100644
--- a/linux-x64/clang/include/llvm/Analysis/IndirectCallSiteVisitor.h
+++ b/linux-x64/clang/include/llvm/Analysis/IndirectCallSiteVisitor.h
@@ -10,6 +10,9 @@
// This file implements defines a visitor class and a helper function that find
// all indirect call-sites in a function.
+#ifndef LLVM_ANALYSIS_INDIRECTCALLSITEVISITOR_H
+#define LLVM_ANALYSIS_INDIRECTCALLSITEVISITOR_H
+
#include "llvm/IR/InstVisitor.h"
#include <vector>
@@ -33,3 +36,5 @@
return ICV.IndirectCallInsts;
}
}
+
+#endif
diff --git a/linux-x64/clang/include/llvm/Analysis/InstructionPrecedenceTracking.h b/linux-x64/clang/include/llvm/Analysis/InstructionPrecedenceTracking.h
new file mode 100644
index 0000000..5178a33
--- /dev/null
+++ b/linux-x64/clang/include/llvm/Analysis/InstructionPrecedenceTracking.h
@@ -0,0 +1,119 @@
+//===-- InstructionPrecedenceTracking.h -------------------------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// Implements a class that is able to define some instructions as "special"
+// (e.g. as having implicit control flow, or writing memory, or having another
+// interesting property) and then efficiently answers queries of the types:
+// 1. Are there any special instructions in the block of interest?
+// 2. Return first of the special instructions in the given block;
+// 3. Check if the given instruction is preceeded by the first special
+// instruction in the same block.
+// The class provides caching that allows to answer these queries quickly. The
+// user must make sure that the cached data is invalidated properly whenever
+// a content of some tracked block is changed.
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H
+#define LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H
+
+#include "llvm/IR/Dominators.h"
+#include "llvm/Analysis/OrderedInstructions.h"
+
+namespace llvm {
+
+class InstructionPrecedenceTracking {
+ // Maps a block to the topmost special instruction in it. If the value is
+ // nullptr, it means that it is known that this block does not contain any
+ // special instructions.
+ DenseMap<const BasicBlock *, const Instruction *> FirstSpecialInsts;
+ // Allows to answer queries about precedence of instructions within one block.
+ OrderedInstructions OI;
+
+ // Fills information about the given block's special instructions.
+ void fill(const BasicBlock *BB);
+
+#ifndef NDEBUG
+ /// Asserts that the cached info for \p BB is up-to-date. This helps to catch
+ /// the usage error of accessing a block without properly invalidating after a
+ /// previous transform.
+ void validate(const BasicBlock *BB) const;
+
+ /// Asserts whether or not the contents of this tracking is up-to-date. This
+ /// helps to catch the usage error of accessing a block without properly
+ /// invalidating after a previous transform.
+ void validateAll() const;
+#endif
+
+protected:
+ InstructionPrecedenceTracking(DominatorTree *DT)
+ : OI(OrderedInstructions(DT)) {}
+
+ /// Returns the topmost special instruction from the block \p BB. Returns
+ /// nullptr if there is no special instructions in the block.
+ const Instruction *getFirstSpecialInstruction(const BasicBlock *BB);
+
+ /// Returns true iff at least one instruction from the basic block \p BB is
+ /// special.
+ bool hasSpecialInstructions(const BasicBlock *BB);
+
+ /// Returns true iff the first special instruction of \p Insn's block exists
+ /// and dominates \p Insn.
+ bool isPreceededBySpecialInstruction(const Instruction *Insn);
+
+ /// A predicate that defines whether or not the instruction \p Insn is
+ /// considered special and needs to be tracked. Implementing this method in
+ /// children classes allows to implement tracking of implicit control flow,
+ /// memory writing instructions or any other kinds of instructions we might
+ /// be interested in.
+ virtual bool isSpecialInstruction(const Instruction *Insn) const = 0;
+
+ virtual ~InstructionPrecedenceTracking() = default;
+
+public:
+ /// Clears cached information about this particular block.
+ void invalidateBlock(const BasicBlock *BB);
+
+ /// Invalidates all information from this tracking.
+ void clear();
+};
+
+/// This class allows to keep track on instructions with implicit control flow.
+/// These are instructions that may not pass execution to their successors. For
+/// example, throwing calls and guards do not always do this. If we need to know
+/// for sure that some instruction is guaranteed to execute if the given block
+/// is reached, then we need to make sure that there is no implicit control flow
+/// instruction (ICFI) preceeding it. For example, this check is required if we
+/// perform PRE moving non-speculable instruction to other place.
+class ImplicitControlFlowTracking : public InstructionPrecedenceTracking {
+public:
+ ImplicitControlFlowTracking(DominatorTree *DT)
+ : InstructionPrecedenceTracking(DT) {}
+
+ /// Returns the topmost instruction with implicit control flow from the given
+ /// basic block. Returns nullptr if there is no such instructions in the block.
+ const Instruction *getFirstICFI(const BasicBlock *BB) {
+ return getFirstSpecialInstruction(BB);
+ }
+
+ /// Returns true if at least one instruction from the given basic block has
+ /// implicit control flow.
+ bool hasICF(const BasicBlock *BB) {
+ return hasSpecialInstructions(BB);
+ }
+
+ /// Returns true if the first ICFI of Insn's block exists and dominates Insn.
+ bool isDominatedByICFIFromSameBlock(const Instruction *Insn) {
+ return isPreceededBySpecialInstruction(Insn);
+ }
+
+ virtual bool isSpecialInstruction(const Instruction *Insn) const;
+};
+
+} // llvm
+
+#endif // LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H
diff --git a/linux-x64/clang/include/llvm/Analysis/InstructionSimplify.h b/linux-x64/clang/include/llvm/Analysis/InstructionSimplify.h
index 4f896bd..6662e91 100644
--- a/linux-x64/clang/include/llvm/Analysis/InstructionSimplify.h
+++ b/linux-x64/clang/include/llvm/Analysis/InstructionSimplify.h
@@ -32,6 +32,8 @@
#ifndef LLVM_ANALYSIS_INSTRUCTIONSIMPLIFY_H
#define LLVM_ANALYSIS_INSTRUCTIONSIMPLIFY_H
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/Operator.h"
#include "llvm/IR/User.h"
namespace llvm {
@@ -40,7 +42,6 @@
template <class T> class ArrayRef;
class AssumptionCache;
class DominatorTree;
-class Instruction;
class ImmutableCallSite;
class DataLayout;
class FastMathFlags;
@@ -50,6 +51,41 @@
class TargetLibraryInfo;
class Type;
class Value;
+class MDNode;
+class BinaryOperator;
+
+/// InstrInfoQuery provides an interface to query additional information for
+/// instructions like metadata or keywords like nsw, which provides conservative
+/// results if the users specified it is safe to use.
+struct InstrInfoQuery {
+ InstrInfoQuery(bool UMD) : UseInstrInfo(UMD) {}
+ InstrInfoQuery() : UseInstrInfo(true) {}
+ bool UseInstrInfo = true;
+
+ MDNode *getMetadata(const Instruction *I, unsigned KindID) const {
+ if (UseInstrInfo)
+ return I->getMetadata(KindID);
+ return nullptr;
+ }
+
+ template <class InstT> bool hasNoUnsignedWrap(const InstT *Op) const {
+ if (UseInstrInfo)
+ return Op->hasNoUnsignedWrap();
+ return false;
+ }
+
+ template <class InstT> bool hasNoSignedWrap(const InstT *Op) const {
+ if (UseInstrInfo)
+ return Op->hasNoSignedWrap();
+ return false;
+ }
+
+ bool isExact(const BinaryOperator *Op) const {
+ if (UseInstrInfo && isa<PossiblyExactOperator>(Op))
+ return cast<PossiblyExactOperator>(Op)->isExact();
+ return false;
+ }
+};
struct SimplifyQuery {
const DataLayout &DL;
@@ -58,14 +94,19 @@
AssumptionCache *AC = nullptr;
const Instruction *CxtI = nullptr;
+ // Wrapper to query additional information for instructions like metadata or
+ // keywords like nsw, which provides conservative results if those cannot
+ // be safely used.
+ const InstrInfoQuery IIQ;
+
SimplifyQuery(const DataLayout &DL, const Instruction *CXTI = nullptr)
: DL(DL), CxtI(CXTI) {}
SimplifyQuery(const DataLayout &DL, const TargetLibraryInfo *TLI,
const DominatorTree *DT = nullptr,
AssumptionCache *AC = nullptr,
- const Instruction *CXTI = nullptr)
- : DL(DL), TLI(TLI), DT(DT), AC(AC), CxtI(CXTI) {}
+ const Instruction *CXTI = nullptr, bool UseInstrInfo = true)
+ : DL(DL), TLI(TLI), DT(DT), AC(AC), CxtI(CXTI), IIQ(UseInstrInfo) {}
SimplifyQuery getWithInstruction(Instruction *I) const {
SimplifyQuery Copy(*this);
Copy.CxtI = I;
diff --git a/linux-x64/clang/include/llvm/Analysis/IteratedDominanceFrontier.h b/linux-x64/clang/include/llvm/Analysis/IteratedDominanceFrontier.h
index 6b19507..fdebb1b 100644
--- a/linux-x64/clang/include/llvm/Analysis/IteratedDominanceFrontier.h
+++ b/linux-x64/clang/include/llvm/Analysis/IteratedDominanceFrontier.h
@@ -28,6 +28,7 @@
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/CFGDiff.h"
#include "llvm/IR/Dominators.h"
namespace llvm {
@@ -45,17 +46,21 @@
template <class NodeTy, bool IsPostDom>
class IDFCalculator {
public:
- IDFCalculator(DominatorTreeBase<BasicBlock, IsPostDom> &DT)
- : DT(DT), useLiveIn(false) {}
+ IDFCalculator(DominatorTreeBase<BasicBlock, IsPostDom> &DT)
+ : DT(DT), GD(nullptr), useLiveIn(false) {}
- /// Give the IDF calculator the set of blocks in which the value is
- /// defined. This is equivalent to the set of starting blocks it should be
- /// calculating the IDF for (though later gets pruned based on liveness).
- ///
- /// Note: This set *must* live for the entire lifetime of the IDF calculator.
- void setDefiningBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) {
- DefBlocks = &Blocks;
- }
+ IDFCalculator(DominatorTreeBase<BasicBlock, IsPostDom> &DT,
+ const GraphDiff<BasicBlock *, IsPostDom> *GD)
+ : DT(DT), GD(GD), useLiveIn(false) {}
+
+ /// Give the IDF calculator the set of blocks in which the value is
+ /// defined. This is equivalent to the set of starting blocks it should be
+ /// calculating the IDF for (though later gets pruned based on liveness).
+ ///
+ /// Note: This set *must* live for the entire lifetime of the IDF calculator.
+ void setDefiningBlocks(const SmallPtrSetImpl<BasicBlock *> &Blocks) {
+ DefBlocks = &Blocks;
+ }
/// Give the IDF calculator the set of blocks in which the value is
/// live on entry to the block. This is used to prune the IDF calculation to
@@ -85,6 +90,7 @@
private:
DominatorTreeBase<BasicBlock, IsPostDom> &DT;
+ const GraphDiff<BasicBlock *, IsPostDom> *GD;
bool useLiveIn;
const SmallPtrSetImpl<BasicBlock *> *LiveInBlocks;
const SmallPtrSetImpl<BasicBlock *> *DefBlocks;
diff --git a/linux-x64/clang/include/llvm/Analysis/DivergenceAnalysis.h b/linux-x64/clang/include/llvm/Analysis/LegacyDivergenceAnalysis.h
similarity index 72%
rename from linux-x64/clang/include/llvm/Analysis/DivergenceAnalysis.h
rename to linux-x64/clang/include/llvm/Analysis/LegacyDivergenceAnalysis.h
index 328c864..173ca28 100644
--- a/linux-x64/clang/include/llvm/Analysis/DivergenceAnalysis.h
+++ b/linux-x64/clang/include/llvm/Analysis/LegacyDivergenceAnalysis.h
@@ -1,4 +1,4 @@
-//===- llvm/Analysis/DivergenceAnalysis.h - Divergence Analysis -*- C++ -*-===//
+//===- llvm/Analysis/LegacyDivergenceAnalysis.h - KernelDivergence Analysis -*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
@@ -7,14 +7,14 @@
//
//===----------------------------------------------------------------------===//
//
-// The divergence analysis is an LLVM pass which can be used to find out
-// if a branch instruction in a GPU program is divergent or not. It can help
+// The kernel divergence analysis is an LLVM pass which can be used to find out
+// if a branch instruction in a GPU program (kernel) is divergent or not. It can help
// branch optimizations such as jump threading and loop unswitching to make
// better decisions.
//
//===----------------------------------------------------------------------===//
-#ifndef LLVM_ANALYSIS_DIVERGENCE_ANALYSIS_H
-#define LLVM_ANALYSIS_DIVERGENCE_ANALYSIS_H
+#ifndef LLVM_ANALYSIS_LEGACY_DIVERGENCE_ANALYSIS_H
+#define LLVM_ANALYSIS_LEGACY_DIVERGENCE_ANALYSIS_H
#include "llvm/ADT/DenseSet.h"
#include "llvm/IR/Function.h"
@@ -22,12 +22,12 @@
namespace llvm {
class Value;
-class DivergenceAnalysis : public FunctionPass {
+class LegacyDivergenceAnalysis : public FunctionPass {
public:
static char ID;
- DivergenceAnalysis() : FunctionPass(ID) {
- initializeDivergenceAnalysisPass(*PassRegistry::getPassRegistry());
+ LegacyDivergenceAnalysis() : FunctionPass(ID) {
+ initializeLegacyDivergenceAnalysisPass(*PassRegistry::getPassRegistry());
}
void getAnalysisUsage(AnalysisUsage &AU) const override;
@@ -58,4 +58,4 @@
};
} // End llvm namespace
-#endif //LLVM_ANALYSIS_DIVERGENCE_ANALYSIS_H
\ No newline at end of file
+#endif //LLVM_ANALYSIS_LEGACY_DIVERGENCE_ANALYSIS_H
diff --git a/linux-x64/clang/include/llvm/Analysis/LoopAccessAnalysis.h b/linux-x64/clang/include/llvm/Analysis/LoopAccessAnalysis.h
index d27b3e4..86b402b 100644
--- a/linux-x64/clang/include/llvm/Analysis/LoopAccessAnalysis.h
+++ b/linux-x64/clang/include/llvm/Analysis/LoopAccessAnalysis.h
@@ -564,11 +564,10 @@
/// Print the information about the memory accesses in the loop.
void print(raw_ostream &OS, unsigned Depth = 0) const;
- /// Checks existence of store to invariant address inside loop.
- /// If the loop has any store to invariant address, then it returns true,
- /// else returns false.
- bool hasStoreToLoopInvariantAddress() const {
- return StoreToLoopInvariantAddress;
+ /// If the loop has any store of a variant value to an invariant address, then
+ /// return true, else return false.
+ bool hasVariantStoreToLoopInvariantAddress() const {
+ return HasVariantStoreToLoopInvariantAddress;
}
/// Used to add runtime SCEV checks. Simplifies SCEV expressions and converts
@@ -621,9 +620,8 @@
/// Cache the result of analyzeLoop.
bool CanVecMem;
- /// Indicator for storing to uniform addresses.
- /// If a loop has write to a loop invariant address then it should be true.
- bool StoreToLoopInvariantAddress;
+ /// Indicator that there is a store of a variant value to a uniform address.
+ bool HasVariantStoreToLoopInvariantAddress;
/// The diagnostics report generated for the analysis. E.g. why we
/// couldn't analyze the loop.
diff --git a/linux-x64/clang/include/llvm/Analysis/LoopInfoImpl.h b/linux-x64/clang/include/llvm/Analysis/LoopInfoImpl.h
index 9413898..d3054b7 100644
--- a/linux-x64/clang/include/llvm/Analysis/LoopInfoImpl.h
+++ b/linux-x64/clang/include/llvm/Analysis/LoopInfoImpl.h
@@ -640,8 +640,8 @@
template <typename T>
bool compareVectors(std::vector<T> &BB1, std::vector<T> &BB2) {
- llvm::sort(BB1.begin(), BB1.end());
- llvm::sort(BB2.begin(), BB2.end());
+ llvm::sort(BB1);
+ llvm::sort(BB2);
return BB1 == BB2;
}
diff --git a/linux-x64/clang/include/llvm/Analysis/MemoryLocation.h b/linux-x64/clang/include/llvm/Analysis/MemoryLocation.h
index 6b68000..509efa2 100644
--- a/linux-x64/clang/include/llvm/Analysis/MemoryLocation.h
+++ b/linux-x64/clang/include/llvm/Analysis/MemoryLocation.h
@@ -34,8 +34,131 @@
class TargetLibraryInfo;
// Represents the size of a MemoryLocation. Logically, it's an
-// Optional<uint64_t>, with a special UnknownSize value from `MemoryLocation`.
-using LocationSize = uint64_t;
+// Optional<uint63_t> that also carries a bit to represent whether the integer
+// it contains, N, is 'precise'. Precise, in this context, means that we know
+// that the area of storage referenced by the given MemoryLocation must be
+// precisely N bytes. An imprecise value is formed as the union of two or more
+// precise values, and can conservatively represent all of the values unioned
+// into it. Importantly, imprecise values are an *upper-bound* on the size of a
+// MemoryLocation.
+//
+// Concretely, a precise MemoryLocation is (%p, 4) in
+// store i32 0, i32* %p
+//
+// Since we know that %p must be at least 4 bytes large at this point.
+// Otherwise, we have UB. An example of an imprecise MemoryLocation is (%p, 4)
+// at the memcpy in
+//
+// %n = select i1 %foo, i64 1, i64 4
+// call void @llvm.memcpy.p0i8.p0i8.i64(i8* %p, i8* %baz, i64 %n, i32 1,
+// i1 false)
+//
+// ...Since we'll copy *up to* 4 bytes into %p, but we can't guarantee that
+// we'll ever actually do so.
+//
+// If asked to represent a pathologically large value, this will degrade to
+// None.
+class LocationSize {
+ enum : uint64_t {
+ Unknown = ~uint64_t(0),
+ ImpreciseBit = uint64_t(1) << 63,
+ MapEmpty = Unknown - 1,
+ MapTombstone = Unknown - 2,
+
+ // The maximum value we can represent without falling back to 'unknown'.
+ MaxValue = (MapTombstone - 1) & ~ImpreciseBit,
+ };
+
+ uint64_t Value;
+
+ // Hack to support implicit construction. This should disappear when the
+ // public LocationSize ctor goes away.
+ enum DirectConstruction { Direct };
+
+ constexpr LocationSize(uint64_t Raw, DirectConstruction): Value(Raw) {}
+
+ static_assert(Unknown & ImpreciseBit, "Unknown is imprecise by definition.");
+public:
+ // FIXME: Migrate all users to construct via either `precise` or `upperBound`,
+ // to make it more obvious at the callsite the kind of size that they're
+ // providing.
+ //
+ // Since the overwhelming majority of users of this provide precise values,
+ // this assumes the provided value is precise.
+ constexpr LocationSize(uint64_t Raw)
+ : Value(Raw > MaxValue ? Unknown : Raw) {}
+
+ static LocationSize precise(uint64_t Value) { return LocationSize(Value); }
+
+ static LocationSize upperBound(uint64_t Value) {
+ // You can't go lower than 0, so give a precise result.
+ if (LLVM_UNLIKELY(Value == 0))
+ return precise(0);
+ if (LLVM_UNLIKELY(Value > MaxValue))
+ return unknown();
+ return LocationSize(Value | ImpreciseBit, Direct);
+ }
+
+ constexpr static LocationSize unknown() {
+ return LocationSize(Unknown, Direct);
+ }
+
+ // Sentinel values, generally used for maps.
+ constexpr static LocationSize mapTombstone() {
+ return LocationSize(MapTombstone, Direct);
+ }
+ constexpr static LocationSize mapEmpty() {
+ return LocationSize(MapEmpty, Direct);
+ }
+
+ // Returns a LocationSize that can correctly represent either `*this` or
+ // `Other`.
+ LocationSize unionWith(LocationSize Other) const {
+ if (Other == *this)
+ return *this;
+
+ if (!hasValue() || !Other.hasValue())
+ return unknown();
+
+ return upperBound(std::max(getValue(), Other.getValue()));
+ }
+
+ bool hasValue() const { return Value != Unknown; }
+ uint64_t getValue() const {
+ assert(hasValue() && "Getting value from an unknown LocationSize!");
+ return Value & ~ImpreciseBit;
+ }
+
+ // Returns whether or not this value is precise. Note that if a value is
+ // precise, it's guaranteed to not be `unknown()`.
+ bool isPrecise() const {
+ return (Value & ImpreciseBit) == 0;
+ }
+
+ bool operator==(const LocationSize &Other) const {
+ return Value == Other.Value;
+ }
+
+ bool operator!=(const LocationSize &Other) const {
+ return !(*this == Other);
+ }
+
+ // Ordering operators are not provided, since it's unclear if there's only one
+ // reasonable way to compare:
+ // - values that don't exist against values that do, and
+ // - precise values to imprecise values
+
+ void print(raw_ostream &OS) const;
+
+ // Returns an opaque value that represents this LocationSize. Cannot be
+ // reliably converted back into a LocationSize.
+ uint64_t toRaw() const { return Value; }
+};
+
+inline raw_ostream &operator<<(raw_ostream &OS, LocationSize Size) {
+ Size.print(OS);
+ return OS;
+}
/// Representation for a specific memory location.
///
@@ -109,7 +232,11 @@
/// Return a location representing a particular argument of a call.
static MemoryLocation getForArgument(ImmutableCallSite CS, unsigned ArgIdx,
- const TargetLibraryInfo &TLI);
+ const TargetLibraryInfo *TLI);
+ static MemoryLocation getForArgument(ImmutableCallSite CS, unsigned ArgIdx,
+ const TargetLibraryInfo &TLI) {
+ return getForArgument(CS, ArgIdx, &TLI);
+ }
explicit MemoryLocation(const Value *Ptr = nullptr,
LocationSize Size = UnknownSize,
@@ -139,13 +266,30 @@
}
};
-// Specialize DenseMapInfo for MemoryLocation.
+// Specialize DenseMapInfo.
+template <> struct DenseMapInfo<LocationSize> {
+ static inline LocationSize getEmptyKey() {
+ return LocationSize::mapEmpty();
+ }
+ static inline LocationSize getTombstoneKey() {
+ return LocationSize::mapTombstone();
+ }
+ static unsigned getHashValue(const LocationSize &Val) {
+ return DenseMapInfo<uint64_t>::getHashValue(Val.toRaw());
+ }
+ static bool isEqual(const LocationSize &LHS, const LocationSize &RHS) {
+ return LHS == RHS;
+ }
+};
+
template <> struct DenseMapInfo<MemoryLocation> {
static inline MemoryLocation getEmptyKey() {
- return MemoryLocation(DenseMapInfo<const Value *>::getEmptyKey(), 0);
+ return MemoryLocation(DenseMapInfo<const Value *>::getEmptyKey(),
+ DenseMapInfo<LocationSize>::getEmptyKey());
}
static inline MemoryLocation getTombstoneKey() {
- return MemoryLocation(DenseMapInfo<const Value *>::getTombstoneKey(), 0);
+ return MemoryLocation(DenseMapInfo<const Value *>::getTombstoneKey(),
+ DenseMapInfo<LocationSize>::getTombstoneKey());
}
static unsigned getHashValue(const MemoryLocation &Val) {
return DenseMapInfo<const Value *>::getHashValue(Val.Ptr) ^
diff --git a/linux-x64/clang/include/llvm/Analysis/MemorySSA.h b/linux-x64/clang/include/llvm/Analysis/MemorySSA.h
index d445e44..6200837 100644
--- a/linux-x64/clang/include/llvm/Analysis/MemorySSA.h
+++ b/linux-x64/clang/include/llvm/Analysis/MemorySSA.h
@@ -280,9 +280,10 @@
friend class MemorySSAUpdater;
MemoryUseOrDef(LLVMContext &C, MemoryAccess *DMA, unsigned Vty,
- DeleteValueTy DeleteValue, Instruction *MI, BasicBlock *BB)
- : MemoryAccess(C, Vty, DeleteValue, BB, 1), MemoryInstruction(MI),
- OptimizedAccessAlias(MayAlias) {
+ DeleteValueTy DeleteValue, Instruction *MI, BasicBlock *BB,
+ unsigned NumOperands)
+ : MemoryAccess(C, Vty, DeleteValue, BB, NumOperands),
+ MemoryInstruction(MI), OptimizedAccessAlias(MayAlias) {
setDefiningAccess(DMA);
}
@@ -308,11 +309,6 @@
Optional<AliasResult> OptimizedAccessAlias;
};
-template <>
-struct OperandTraits<MemoryUseOrDef>
- : public FixedNumOperandTraits<MemoryUseOrDef, 1> {};
-DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryUseOrDef, MemoryAccess)
-
/// Represents read-only accesses to memory
///
/// In particular, the set of Instructions that will be represented by
@@ -323,7 +319,8 @@
DECLARE_TRANSPARENT_OPERAND_ACCESSORS(MemoryAccess);
MemoryUse(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB)
- : MemoryUseOrDef(C, DMA, MemoryUseVal, deleteMe, MI, BB) {}
+ : MemoryUseOrDef(C, DMA, MemoryUseVal, deleteMe, MI, BB,
+ /*NumOperands=*/1) {}
// allocate space for exactly one operand
void *operator new(size_t s) { return User::operator new(s, 1); }
@@ -381,27 +378,28 @@
MemoryDef(LLVMContext &C, MemoryAccess *DMA, Instruction *MI, BasicBlock *BB,
unsigned Ver)
- : MemoryUseOrDef(C, DMA, MemoryDefVal, deleteMe, MI, BB), ID(Ver) {}
+ : MemoryUseOrDef(C, DMA, MemoryDefVal, deleteMe, MI, BB,
+ /*NumOperands=*/2),
+ ID(Ver) {}
- // allocate space for exactly one operand
- void *operator new(size_t s) { return User::operator new(s, 1); }
+ // allocate space for exactly two operands
+ void *operator new(size_t s) { return User::operator new(s, 2); }
static bool classof(const Value *MA) {
return MA->getValueID() == MemoryDefVal;
}
void setOptimized(MemoryAccess *MA) {
- Optimized = MA;
- OptimizedID = getDefiningAccess()->getID();
+ setOperand(1, MA);
+ OptimizedID = MA->getID();
}
MemoryAccess *getOptimized() const {
- return cast_or_null<MemoryAccess>(Optimized);
+ return cast_or_null<MemoryAccess>(getOperand(1));
}
bool isOptimized() const {
- return getOptimized() && getDefiningAccess() &&
- OptimizedID == getDefiningAccess()->getID();
+ return getOptimized() && OptimizedID == getOptimized()->getID();
}
void resetOptimized() {
@@ -417,13 +415,34 @@
const unsigned ID;
unsigned OptimizedID = INVALID_MEMORYACCESS_ID;
- WeakVH Optimized;
};
template <>
-struct OperandTraits<MemoryDef> : public FixedNumOperandTraits<MemoryDef, 1> {};
+struct OperandTraits<MemoryDef> : public FixedNumOperandTraits<MemoryDef, 2> {};
DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryDef, MemoryAccess)
+template <>
+struct OperandTraits<MemoryUseOrDef> {
+ static Use *op_begin(MemoryUseOrDef *MUD) {
+ if (auto *MU = dyn_cast<MemoryUse>(MUD))
+ return OperandTraits<MemoryUse>::op_begin(MU);
+ return OperandTraits<MemoryDef>::op_begin(cast<MemoryDef>(MUD));
+ }
+
+ static Use *op_end(MemoryUseOrDef *MUD) {
+ if (auto *MU = dyn_cast<MemoryUse>(MUD))
+ return OperandTraits<MemoryUse>::op_end(MU);
+ return OperandTraits<MemoryDef>::op_end(cast<MemoryDef>(MUD));
+ }
+
+ static unsigned operands(const MemoryUseOrDef *MUD) {
+ if (const auto *MU = dyn_cast<MemoryUse>(MUD))
+ return OperandTraits<MemoryUse>::operands(MU);
+ return OperandTraits<MemoryDef>::operands(cast<MemoryDef>(MUD));
+ }
+};
+DEFINE_TRANSPARENT_OPERAND_ACCESSORS(MemoryUseOrDef, MemoryAccess)
+
/// Represents phi nodes for memory accesses.
///
/// These have the same semantic as regular phi nodes, with the exception that
@@ -689,8 +708,13 @@
/// access associated with it. If passed a basic block gets the memory phi
/// node that exists for that block, if there is one. Otherwise, this will get
/// a MemoryUseOrDef.
- MemoryUseOrDef *getMemoryAccess(const Instruction *) const;
- MemoryPhi *getMemoryAccess(const BasicBlock *BB) const;
+ MemoryUseOrDef *getMemoryAccess(const Instruction *I) const {
+ return cast_or_null<MemoryUseOrDef>(ValueToMemoryAccess.lookup(I));
+ }
+
+ MemoryPhi *getMemoryAccess(const BasicBlock *BB) const {
+ return cast_or_null<MemoryPhi>(ValueToMemoryAccess.lookup(cast<Value>(BB)));
+ }
void dump() const;
void print(raw_ostream &) const;
@@ -750,6 +774,9 @@
/// all uses, uses appear in the right places). This is used by unit tests.
void verifyMemorySSA() const;
+ /// Check clobber sanity for an access.
+ void checkClobberSanityAccess(const MemoryAccess *MA) const;
+
/// Used in various insertion functions to specify whether we are talking
/// about the beginning or end of a block.
enum InsertionPlace { Beginning, End };
@@ -764,6 +791,7 @@
void verifyDomination(Function &F) const;
void verifyOrdering(Function &F) const;
void verifyDominationNumbers(const Function &F) const;
+ void verifyClobberSanity(const Function &F) const;
// This is used by the use optimizer and updater.
AccessList *getWritableBlockAccesses(const BasicBlock *BB) const {
@@ -796,7 +824,8 @@
InsertionPlace);
void insertIntoListsBefore(MemoryAccess *, const BasicBlock *,
AccessList::iterator);
- MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *);
+ MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *,
+ const MemoryUseOrDef *Template = nullptr);
private:
class CachingWalker;
@@ -806,6 +835,7 @@
void buildMemorySSA();
void optimizeUses();
+ void prepareForMoveTo(MemoryAccess *, BasicBlock *);
void verifyUseInDefs(MemoryAccess *, MemoryAccess *) const;
using AccessMap = DenseMap<const BasicBlock *, std::unique_ptr<AccessList>>;
@@ -816,7 +846,8 @@
void markUnreachableAsLiveOnEntry(BasicBlock *BB);
bool dominatesUse(const MemoryAccess *, const MemoryAccess *) const;
MemoryPhi *createMemoryPhi(BasicBlock *BB);
- MemoryUseOrDef *createNewAccess(Instruction *);
+ MemoryUseOrDef *createNewAccess(Instruction *,
+ const MemoryUseOrDef *Template = nullptr);
MemoryAccess *findDominatingDef(BasicBlock *, enum InsertionPlace);
void placePHINodes(const SmallPtrSetImpl<BasicBlock *> &);
MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *, bool);
diff --git a/linux-x64/clang/include/llvm/Analysis/MemorySSAUpdater.h b/linux-x64/clang/include/llvm/Analysis/MemorySSAUpdater.h
index 38f08c1..098876e 100644
--- a/linux-x64/clang/include/llvm/Analysis/MemorySSAUpdater.h
+++ b/linux-x64/clang/include/llvm/Analysis/MemorySSAUpdater.h
@@ -35,8 +35,10 @@
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
+#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/CFGDiff.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/OperandTraits.h"
@@ -45,6 +47,7 @@
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/ValueHandle.h"
+#include "llvm/IR/ValueMap.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/ErrorHandling.h"
@@ -57,6 +60,12 @@
class LLVMContext;
class raw_ostream;
+using ValueToValueMapTy = ValueMap<const Value *, WeakTrackingVH>;
+using PhiToDefMap = SmallDenseMap<MemoryPhi *, MemoryAccess *>;
+using CFGUpdate = cfg::Update<BasicBlock *>;
+using GraphDiffInvBBPair =
+ std::pair<const GraphDiff<BasicBlock *> *, Inverse<BasicBlock *>>;
+
class MemorySSAUpdater {
private:
MemorySSA *MSSA;
@@ -70,6 +79,7 @@
public:
MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {}
+
/// Insert a definition into the MemorySSA IR. RenameUses will rename any use
/// below the new def block (and any inserted phis). RenameUses should be set
/// to true if the definition may cause new aliases for loads below it. This
@@ -89,15 +99,48 @@
/// Where a mayalias b, *does* require RenameUses be set to true.
void insertDef(MemoryDef *Def, bool RenameUses = false);
void insertUse(MemoryUse *Use);
+ /// Update the MemoryPhi in `To` following an edge deletion between `From` and
+ /// `To`. If `To` becomes unreachable, a call to removeBlocks should be made.
+ void removeEdge(BasicBlock *From, BasicBlock *To);
+ /// Update the MemoryPhi in `To` to have a single incoming edge from `From`,
+ /// following a CFG change that replaced multiple edges (switch) with a direct
+ /// branch.
+ void removeDuplicatePhiEdgesBetween(BasicBlock *From, BasicBlock *To);
+ /// Update MemorySSA after a loop was cloned, given the blocks in RPO order,
+ /// the exit blocks and a 1:1 mapping of all blocks and instructions
+ /// cloned. This involves duplicating all defs and uses in the cloned blocks
+ /// Updating phi nodes in exit block successors is done separately.
+ void updateForClonedLoop(const LoopBlocksRPO &LoopBlocks,
+ ArrayRef<BasicBlock *> ExitBlocks,
+ const ValueToValueMapTy &VM,
+ bool IgnoreIncomingWithNoClones = false);
+ // Block BB was fully or partially cloned into its predecessor P1. Map
+ // contains the 1:1 mapping of instructions cloned and VM[BB]=P1.
+ void updateForClonedBlockIntoPred(BasicBlock *BB, BasicBlock *P1,
+ const ValueToValueMapTy &VM);
+ /// Update phi nodes in exit block successors following cloning. Exit blocks
+ /// that were not cloned don't have additional predecessors added.
+ void updateExitBlocksForClonedLoop(ArrayRef<BasicBlock *> ExitBlocks,
+ const ValueToValueMapTy &VMap,
+ DominatorTree &DT);
+ void updateExitBlocksForClonedLoop(
+ ArrayRef<BasicBlock *> ExitBlocks,
+ ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps, DominatorTree &DT);
+
+ /// Apply CFG updates, analogous with the DT edge updates.
+ void applyUpdates(ArrayRef<CFGUpdate> Updates, DominatorTree &DT);
+ /// Apply CFG insert updates, analogous with the DT edge updates.
+ void applyInsertUpdates(ArrayRef<CFGUpdate> Updates, DominatorTree &DT);
+
void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where);
void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where);
void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB,
MemorySSA::InsertionPlace Where);
- /// `From` block was spliced into `From` and `To`.
- /// Move all accesses from `From` to `To` starting at instruction `Start`.
- /// `To` is newly created BB, so empty of MemorySSA::MemoryAccesses.
- /// Edges are already updated, so successors of `To` with MPhi nodes need to
- /// update incoming block.
+ /// `From` block was spliced into `From` and `To`. There is a CFG edge from
+ /// `From` to `To`. Move all accesses from `From` to `To` starting at
+ /// instruction `Start`. `To` is newly created BB, so empty of
+ /// MemorySSA::MemoryAccesses. Edges are already updated, so successors of
+ /// `To` with MPhi nodes need to update incoming block.
/// |------| |------|
/// | From | | From |
/// | | |------|
@@ -108,12 +151,12 @@
/// |------| |------|
void moveAllAfterSpliceBlocks(BasicBlock *From, BasicBlock *To,
Instruction *Start);
- /// `From` block was merged into `To`. All instructions were moved and
- /// `From` is an empty block with successor edges; `From` is about to be
- /// deleted. Move all accesses from `From` to `To` starting at instruction
- /// `Start`. `To` may have multiple successors, `From` has a single
- /// predecessor. `From` may have successors with MPhi nodes, replace their
- /// incoming block with `To`.
+ /// `From` block was merged into `To`. There is a CFG edge from `To` to
+ /// `From`.`To` still branches to `From`, but all instructions were moved and
+ /// `From` is now an empty block; `From` is about to be deleted. Move all
+ /// accesses from `From` to `To` starting at instruction `Start`. `To` may
+ /// have multiple successors, `From` has a single predecessor. `From` may have
+ /// successors with MPhi nodes, replace their incoming block with `To`.
/// |------| |------|
/// | To | | To |
/// |------| | |
@@ -124,15 +167,14 @@
/// |------| |------|
void moveAllAfterMergeBlocks(BasicBlock *From, BasicBlock *To,
Instruction *Start);
- /// BasicBlock Old had New, an empty BasicBlock, added directly before it,
- /// and the predecessors in Preds that used to point to Old, now point to
- /// New. If New is the only predecessor, move Old's Phi, if present, to New.
+ /// A new empty BasicBlock (New) now branches directly to Old. Some of
+ /// Old's predecessors (Preds) are now branching to New instead of Old.
+ /// If New is the only predecessor, move Old's Phi, if present, to New.
/// Otherwise, add a new Phi in New with appropriate incoming values, and
/// update the incoming values in Old's Phi node too, if present.
- void
- wireOldPredecessorsToNewImmediatePredecessor(BasicBlock *Old, BasicBlock *New,
- ArrayRef<BasicBlock *> Preds);
-
+ void wireOldPredecessorsToNewImmediatePredecessor(
+ BasicBlock *Old, BasicBlock *New, ArrayRef<BasicBlock *> Preds,
+ bool IdenticalEdgesWereMerged = true);
// The below are utility functions. Other than creation of accesses to pass
// to insertDef, and removeAccess to remove accesses, you should generally
// not attempt to update memoryssa yourself. It is very non-trivial to get
@@ -220,6 +262,23 @@
template <class RangeType>
MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands);
void fixupDefs(const SmallVectorImpl<WeakVH> &);
+ // Clone all uses and defs from BB to NewBB given a 1:1 map of all
+ // instructions and blocks cloned, and a map of MemoryPhi : Definition
+ // (MemoryAccess Phi or Def). VMap maps old instructions to cloned
+ // instructions and old blocks to cloned blocks. MPhiMap, is created in the
+ // caller of this private method, and maps existing MemoryPhis to new
+ // definitions that new MemoryAccesses must point to. These definitions may
+ // not necessarily be MemoryPhis themselves, they may be MemoryDefs. As such,
+ // the map is between MemoryPhis and MemoryAccesses, where the MemoryAccesses
+ // may be MemoryPhis or MemoryDefs and not MemoryUses.
+ void cloneUsesAndDefs(BasicBlock *BB, BasicBlock *NewBB,
+ const ValueToValueMapTy &VMap, PhiToDefMap &MPhiMap);
+ template <typename Iter>
+ void privateUpdateExitBlocksForClonedLoop(ArrayRef<BasicBlock *> ExitBlocks,
+ Iter ValuesBegin, Iter ValuesEnd,
+ DominatorTree &DT);
+ void applyInsertUpdates(ArrayRef<CFGUpdate>, DominatorTree &DT,
+ const GraphDiff<BasicBlock *> *GD);
};
} // end namespace llvm
diff --git a/linux-x64/clang/include/llvm/Analysis/MustExecute.h b/linux-x64/clang/include/llvm/Analysis/MustExecute.h
index 97ad76d..40a0273 100644
--- a/linux-x64/clang/include/llvm/Analysis/MustExecute.h
+++ b/linux-x64/clang/include/llvm/Analysis/MustExecute.h
@@ -31,28 +31,60 @@
class Loop;
/// Captures loop safety information.
-/// It keep information for loop & its header may throw exception or otherwise
+/// 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.
-struct LoopSafetyInfo {
+/// 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 {
bool MayThrow = false; // The current loop contains an instruction which
// may throw.
bool HeaderMayThrow = false; // Same as previous, but specific to loop header
+
+ /// Collect all blocks from \p CurLoop which lie on all possible paths from
+ /// the header of \p CurLoop (inclusive) to BB (exclusive) into the set
+ /// \p Predecessors. If \p BB is the header, \p Predecessors will be empty.
+ void collectTransitivePredecessors(
+ const Loop *CurLoop, const BasicBlock *BB,
+ SmallPtrSetImpl<const BasicBlock *> &Predecessors) const;
+
+public:
// Used to update funclet bundle operands.
DenseMap<BasicBlock *, ColorVector> BlockColors;
+ /// Returns true iff the header block of the loop for which this info is
+ /// calculated contains an instruction that may throw or otherwise exit
+ /// abnormally.
+ bool headerMayThrow() const;
+
+ /// Returns true iff any block of the loop for which this info is contains an
+ /// instruction that may throw or otherwise exit abnormally.
+ bool anyBlockMayThrow() const;
+
+ /// Return true if we must reach the block \p BB under assumption that the
+ /// loop \p CurLoop is entered and no instruction throws or otherwise exits
+ /// abnormally.
+ 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.
+ void computeLoopSafetyInfo(Loop *);
+
LoopSafetyInfo() = default;
};
-/// 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.
-void computeLoopSafetyInfo(LoopSafetyInfo *, Loop *);
-
/// Returns true if the instruction in a loop is guaranteed to execute at least
/// once (under the assumption that the loop is entered).
bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT,
diff --git a/linux-x64/clang/include/llvm/Analysis/OrderedInstructions.h b/linux-x64/clang/include/llvm/Analysis/OrderedInstructions.h
new file mode 100644
index 0000000..7e3850b
--- /dev/null
+++ b/linux-x64/clang/include/llvm/Analysis/OrderedInstructions.h
@@ -0,0 +1,65 @@
+//===- llvm/Transforms/Utils/OrderedInstructions.h -------------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines an efficient way to check for dominance relation between 2
+// instructions.
+//
+// This interface dispatches to appropriate dominance check given 2
+// instructions, i.e. in case the instructions are in the same basic block,
+// OrderedBasicBlock (with instruction numbering and caching) are used.
+// Otherwise, dominator tree is used.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_ORDEREDINSTRUCTIONS_H
+#define LLVM_ANALYSIS_ORDEREDINSTRUCTIONS_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/Analysis/OrderedBasicBlock.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Operator.h"
+
+namespace llvm {
+
+class OrderedInstructions {
+ /// Used to check dominance for instructions in same basic block.
+ mutable DenseMap<const BasicBlock *, std::unique_ptr<OrderedBasicBlock>>
+ OBBMap;
+
+ /// The dominator tree of the parent function.
+ DominatorTree *DT;
+
+ /// Return true if the first instruction comes before the second in the
+ /// same basic block. It will create an ordered basic block, if it does
+ /// not yet exist in OBBMap.
+ bool localDominates(const Instruction *, const Instruction *) const;
+
+public:
+ /// Constructor.
+ OrderedInstructions(DominatorTree *DT) : DT(DT) {}
+
+ /// Return true if first instruction dominates the second.
+ bool dominates(const Instruction *, const Instruction *) const;
+
+ /// Return true if the first instruction comes before the second in the
+ /// dominator tree DFS traversal if they are in different basic blocks,
+ /// or if the first instruction comes before the second in the same basic
+ /// block.
+ bool dfsBefore(const Instruction *, const Instruction *) const;
+
+ /// Invalidate the OrderedBasicBlock cache when its basic block changes.
+ /// i.e. If an instruction is deleted or added to the basic block, the user
+ /// should call this function to invalidate the OrderedBasicBlock cache for
+ /// this basic block.
+ void invalidateBlock(const BasicBlock *BB) { OBBMap.erase(BB); }
+};
+
+} // end namespace llvm
+
+#endif // LLVM_ANALYSIS_ORDEREDINSTRUCTIONS_H
diff --git a/linux-x64/clang/include/llvm/Analysis/Passes.h b/linux-x64/clang/include/llvm/Analysis/Passes.h
index 09b28a0..081dd50 100644
--- a/linux-x64/clang/include/llvm/Analysis/Passes.h
+++ b/linux-x64/clang/include/llvm/Analysis/Passes.h
@@ -61,10 +61,10 @@
//===--------------------------------------------------------------------===//
//
- // createDivergenceAnalysisPass - This pass determines which branches in a GPU
+ // createLegacyDivergenceAnalysisPass - This pass determines which branches in a GPU
// program are divergent.
//
- FunctionPass *createDivergenceAnalysisPass();
+ FunctionPass *createLegacyDivergenceAnalysisPass();
//===--------------------------------------------------------------------===//
//
diff --git a/linux-x64/clang/include/llvm/Analysis/PhiValues.h b/linux-x64/clang/include/llvm/Analysis/PhiValues.h
index 6607b32..76204ac 100644
--- a/linux-x64/clang/include/llvm/Analysis/PhiValues.h
+++ b/linux-x64/clang/include/llvm/Analysis/PhiValues.h
@@ -88,6 +88,22 @@
/// All values reachable from each component.
DenseMap<unsigned int, ConstValueSet> ReachableMap;
+ /// A CallbackVH to notify PhiValues when a value is deleted or replaced, so
+ /// that the cached information for that value can be cleared to avoid
+ /// dangling pointers to invalid values.
+ class PhiValuesCallbackVH final : public CallbackVH {
+ PhiValues *PV;
+ void deleted() override;
+ void allUsesReplacedWith(Value *New) override;
+
+ public:
+ PhiValuesCallbackVH(Value *V, PhiValues *PV = nullptr)
+ : CallbackVH(V), PV(PV) {}
+ };
+
+ /// A set of callbacks to the values that processPhi has seen.
+ DenseSet<PhiValuesCallbackVH, DenseMapInfo<Value *>> TrackedValues;
+
/// The function that the PhiValues is for.
const Function &F;
diff --git a/linux-x64/clang/include/llvm/Analysis/SparsePropagation.h b/linux-x64/clang/include/llvm/Analysis/SparsePropagation.h
index defcf96..04e94f7 100644
--- a/linux-x64/clang/include/llvm/Analysis/SparsePropagation.h
+++ b/linux-x64/clang/include/llvm/Analysis/SparsePropagation.h
@@ -330,7 +330,7 @@
return;
}
- if (TI.isExceptional()) {
+ if (TI.isExceptionalTerminator()) {
Succs.assign(Succs.size(), true);
return;
}
diff --git a/linux-x64/clang/include/llvm/Analysis/TargetTransformInfo.h b/linux-x64/clang/include/llvm/Analysis/TargetTransformInfo.h
index 59657cc..18b5a5c 100644
--- a/linux-x64/clang/include/llvm/Analysis/TargetTransformInfo.h
+++ b/linux-x64/clang/include/llvm/Analysis/TargetTransformInfo.h
@@ -289,7 +289,7 @@
/// Returns whether V is a source of divergence.
///
/// This function provides the target-dependent information for
- /// the target-independent DivergenceAnalysis. DivergenceAnalysis first
+ /// the target-independent LegacyDivergenceAnalysis. LegacyDivergenceAnalysis first
/// builds the dependency graph, and then runs the reachability algorithm
/// starting with the sources of divergence.
bool isSourceOfDivergence(const Value *V) const;
@@ -739,6 +739,10 @@
/// and the number of execution units in the CPU.
unsigned getMaxInterleaveFactor(unsigned VF) const;
+ /// Collect properties of V used in cost analyzis, e.g. OP_PowerOf2.
+ OperandValueKind getOperandInfo(Value *V,
+ OperandValueProperties &OpProps) const;
+
/// This is an approximation of reciprocal throughput of a math/logic op.
/// A higher cost indicates less expected throughput.
/// From Agner Fog's guides, reciprocal throughput is "the average number of
diff --git a/linux-x64/clang/include/llvm/Analysis/TargetTransformInfoImpl.h b/linux-x64/clang/include/llvm/Analysis/TargetTransformInfoImpl.h
index d80ae1d..e39fe66 100644
--- a/linux-x64/clang/include/llvm/Analysis/TargetTransformInfoImpl.h
+++ b/linux-x64/clang/include/llvm/Analysis/TargetTransformInfoImpl.h
@@ -158,6 +158,8 @@
case Intrinsic::dbg_label:
case Intrinsic::invariant_start:
case Intrinsic::invariant_end:
+ case Intrinsic::launder_invariant_group:
+ case Intrinsic::strip_invariant_group:
case Intrinsic::lifetime_start:
case Intrinsic::lifetime_end:
case Intrinsic::objectsize:
diff --git a/linux-x64/clang/include/llvm/Analysis/TypeMetadataUtils.h b/linux-x64/clang/include/llvm/Analysis/TypeMetadataUtils.h
index 6764563..3bf9c5d 100644
--- a/linux-x64/clang/include/llvm/Analysis/TypeMetadataUtils.h
+++ b/linux-x64/clang/include/llvm/Analysis/TypeMetadataUtils.h
@@ -20,6 +20,8 @@
namespace llvm {
+class DominatorTree;
+
/// The type of CFI jumptable needed for a function.
enum CfiFunctionLinkage {
CFL_Definition = 0,
@@ -39,7 +41,8 @@
/// call sites based on the call and return them in DevirtCalls.
void findDevirtualizableCallsForTypeTest(
SmallVectorImpl<DevirtCallSite> &DevirtCalls,
- SmallVectorImpl<CallInst *> &Assumes, const CallInst *CI);
+ SmallVectorImpl<CallInst *> &Assumes, const CallInst *CI,
+ DominatorTree &DT);
/// Given a call to the intrinsic \@llvm.type.checked.load, find all
/// devirtualizable call sites based on the call and return them in DevirtCalls.
@@ -47,7 +50,7 @@
SmallVectorImpl<DevirtCallSite> &DevirtCalls,
SmallVectorImpl<Instruction *> &LoadedPtrs,
SmallVectorImpl<Instruction *> &Preds, bool &HasNonCallUses,
- const CallInst *CI);
+ const CallInst *CI, DominatorTree &DT);
}
#endif
diff --git a/linux-x64/clang/include/llvm/Analysis/ValueTracking.h b/linux-x64/clang/include/llvm/Analysis/ValueTracking.h
index 99b47fb..a92ba8e 100644
--- a/linux-x64/clang/include/llvm/Analysis/ValueTracking.h
+++ b/linux-x64/clang/include/llvm/Analysis/ValueTracking.h
@@ -55,14 +55,16 @@
AssumptionCache *AC = nullptr,
const Instruction *CxtI = nullptr,
const DominatorTree *DT = nullptr,
- OptimizationRemarkEmitter *ORE = nullptr);
+ OptimizationRemarkEmitter *ORE = nullptr,
+ bool UseInstrInfo = true);
/// Returns the known bits rather than passing by reference.
KnownBits computeKnownBits(const Value *V, const DataLayout &DL,
unsigned Depth = 0, AssumptionCache *AC = nullptr,
const Instruction *CxtI = nullptr,
const DominatorTree *DT = nullptr,
- OptimizationRemarkEmitter *ORE = nullptr);
+ OptimizationRemarkEmitter *ORE = nullptr,
+ bool UseInstrInfo = true);
/// Compute known bits from the range metadata.
/// \p KnownZero the set of bits that are known to be zero
@@ -75,7 +77,8 @@
const DataLayout &DL,
AssumptionCache *AC = nullptr,
const Instruction *CxtI = nullptr,
- const DominatorTree *DT = nullptr);
+ const DominatorTree *DT = nullptr,
+ bool UseInstrInfo = true);
/// Return true if the given value is known to have exactly one bit set when
/// defined. For vectors return true if every element is known to be a power
@@ -86,7 +89,8 @@
bool OrZero = false, unsigned Depth = 0,
AssumptionCache *AC = nullptr,
const Instruction *CxtI = nullptr,
- const DominatorTree *DT = nullptr);
+ const DominatorTree *DT = nullptr,
+ bool UseInstrInfo = true);
bool isOnlyUsedInZeroEqualityComparison(const Instruction *CxtI);
@@ -99,7 +103,8 @@
bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth = 0,
AssumptionCache *AC = nullptr,
const Instruction *CxtI = nullptr,
- const DominatorTree *DT = nullptr);
+ const DominatorTree *DT = nullptr,
+ bool UseInstrInfo = true);
/// Return true if the two given values are negation.
/// Currently can recoginze Value pair:
@@ -112,28 +117,32 @@
unsigned Depth = 0,
AssumptionCache *AC = nullptr,
const Instruction *CxtI = nullptr,
- const DominatorTree *DT = nullptr);
+ const DominatorTree *DT = nullptr,
+ bool UseInstrInfo = true);
/// Returns true if the given value is known be positive (i.e. non-negative
/// and non-zero).
bool isKnownPositive(const Value *V, const DataLayout &DL, unsigned Depth = 0,
AssumptionCache *AC = nullptr,
const Instruction *CxtI = nullptr,
- const DominatorTree *DT = nullptr);
+ const DominatorTree *DT = nullptr,
+ bool UseInstrInfo = true);
/// Returns true if the given value is known be negative (i.e. non-positive
/// and non-zero).
bool isKnownNegative(const Value *V, const DataLayout &DL, unsigned Depth = 0,
AssumptionCache *AC = nullptr,
const Instruction *CxtI = nullptr,
- const DominatorTree *DT = nullptr);
+ const DominatorTree *DT = nullptr,
+ bool UseInstrInfo = true);
/// Return true if the given values are known to be non-equal when defined.
/// Supports scalar integer types only.
bool isKnownNonEqual(const Value *V1, const Value *V2, const DataLayout &DL,
- AssumptionCache *AC = nullptr,
- const Instruction *CxtI = nullptr,
- const DominatorTree *DT = nullptr);
+ AssumptionCache *AC = nullptr,
+ const Instruction *CxtI = nullptr,
+ const DominatorTree *DT = nullptr,
+ bool UseInstrInfo = true);
/// Return true if 'V & Mask' is known to be zero. We use this predicate to
/// simplify operations downstream. Mask is known to be zero for bits that V
@@ -148,7 +157,8 @@
const DataLayout &DL,
unsigned Depth = 0, AssumptionCache *AC = nullptr,
const Instruction *CxtI = nullptr,
- const DominatorTree *DT = nullptr);
+ const DominatorTree *DT = nullptr,
+ bool UseInstrInfo = true);
/// Return the number of times the sign bit of the register is replicated into
/// the other bits. We know that at least 1 bit is always equal to the sign
@@ -160,7 +170,8 @@
unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL,
unsigned Depth = 0, AssumptionCache *AC = nullptr,
const Instruction *CxtI = nullptr,
- const DominatorTree *DT = nullptr);
+ const DominatorTree *DT = nullptr,
+ bool UseInstrInfo = true);
/// This function computes the integer multiple of Base that equals V. If
/// successful, it returns true and returns the multiple in Multiple. If
@@ -210,7 +221,8 @@
/// return the i8 value that it is represented with. This is true for all i8
/// values obviously, but is also true for i32 0, i32 -1, i16 0xF0F0, double
/// 0.0 etc. If the value can't be handled with a repeated byte store (e.g.
- /// i16 0x1234), return null.
+ /// i16 0x1234), return null. If the value is entirely undef and padding,
+ /// return undef.
Value *isBytewiseValue(Value *V);
/// Given an aggregrate and an sequence of indices, see if the scalar value
@@ -406,18 +418,21 @@
const DataLayout &DL,
AssumptionCache *AC,
const Instruction *CxtI,
- const DominatorTree *DT);
+ const DominatorTree *DT,
+ bool UseInstrInfo = true);
OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS,
const DataLayout &DL,
AssumptionCache *AC,
const Instruction *CxtI,
- const DominatorTree *DT);
+ const DominatorTree *DT,
+ bool UseInstrInfo = true);
OverflowResult computeOverflowForUnsignedAdd(const Value *LHS,
const Value *RHS,
const DataLayout &DL,
AssumptionCache *AC,
const Instruction *CxtI,
- const DominatorTree *DT);
+ const DominatorTree *DT,
+ bool UseInstrInfo = true);
OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS,
const DataLayout &DL,
AssumptionCache *AC = nullptr,
diff --git a/linux-x64/clang/include/llvm/Analysis/VectorUtils.h b/linux-x64/clang/include/llvm/Analysis/VectorUtils.h
index 9fde36d..622d932 100644
--- a/linux-x64/clang/include/llvm/Analysis/VectorUtils.h
+++ b/linux-x64/clang/include/llvm/Analysis/VectorUtils.h
@@ -15,6 +15,7 @@
#define LLVM_ANALYSIS_VECTORUTILS_H
#include "llvm/ADT/MapVector.h"
+#include "llvm/Analysis/LoopAccessAnalysis.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/IR/IRBuilder.h"
@@ -176,6 +177,338 @@
/// elements, it will be padded with undefs.
Value *concatenateVectors(IRBuilder<> &Builder, ArrayRef<Value *> Vecs);
+/// The group of interleaved loads/stores sharing the same stride and
+/// close to each other.
+///
+/// Each member in this group has an index starting from 0, and the largest
+/// index should be less than interleaved factor, which is equal to the absolute
+/// value of the access's stride.
+///
+/// E.g. An interleaved load group of factor 4:
+/// for (unsigned i = 0; i < 1024; i+=4) {
+/// a = A[i]; // Member of index 0
+/// b = A[i+1]; // Member of index 1
+/// d = A[i+3]; // Member of index 3
+/// ...
+/// }
+///
+/// An interleaved store group of factor 4:
+/// for (unsigned i = 0; i < 1024; i+=4) {
+/// ...
+/// A[i] = a; // Member of index 0
+/// A[i+1] = b; // Member of index 1
+/// A[i+2] = c; // Member of index 2
+/// A[i+3] = d; // Member of index 3
+/// }
+///
+/// Note: the interleaved load group could have gaps (missing members), but
+/// the interleaved store group doesn't allow gaps.
+class InterleaveGroup {
+public:
+ InterleaveGroup(Instruction *Instr, int Stride, unsigned Align)
+ : Align(Align), InsertPos(Instr) {
+ assert(Align && "The alignment should be non-zero");
+
+ Factor = std::abs(Stride);
+ assert(Factor > 1 && "Invalid interleave factor");
+
+ Reverse = Stride < 0;
+ Members[0] = Instr;
+ }
+
+ bool isReverse() const { return Reverse; }
+ unsigned getFactor() const { return Factor; }
+ unsigned getAlignment() const { return Align; }
+ unsigned getNumMembers() const { return Members.size(); }
+
+ /// Try to insert a new member \p Instr with index \p Index and
+ /// alignment \p NewAlign. The index is related to the leader and it could be
+ /// negative if it is the new leader.
+ ///
+ /// \returns false if the instruction doesn't belong to the group.
+ bool insertMember(Instruction *Instr, int Index, unsigned NewAlign) {
+ assert(NewAlign && "The new member's alignment should be non-zero");
+
+ int Key = Index + SmallestKey;
+
+ // Skip if there is already a member with the same index.
+ if (Members.find(Key) != Members.end())
+ return false;
+
+ if (Key > LargestKey) {
+ // The largest index is always less than the interleave factor.
+ if (Index >= static_cast<int>(Factor))
+ return false;
+
+ LargestKey = Key;
+ } else if (Key < SmallestKey) {
+ // The largest index is always less than the interleave factor.
+ if (LargestKey - Key >= static_cast<int>(Factor))
+ return false;
+
+ SmallestKey = Key;
+ }
+
+ // It's always safe to select the minimum alignment.
+ Align = std::min(Align, NewAlign);
+ Members[Key] = Instr;
+ return true;
+ }
+
+ /// Get the member with the given index \p Index
+ ///
+ /// \returns nullptr if contains no such member.
+ Instruction *getMember(unsigned Index) const {
+ int Key = SmallestKey + Index;
+ auto Member = Members.find(Key);
+ if (Member == Members.end())
+ return nullptr;
+
+ return Member->second;
+ }
+
+ /// Get the index for the given member. Unlike the key in the member
+ /// map, the index starts from 0.
+ unsigned getIndex(Instruction *Instr) const {
+ for (auto I : Members)
+ if (I.second == Instr)
+ return I.first - SmallestKey;
+
+ llvm_unreachable("InterleaveGroup contains no such member");
+ }
+
+ Instruction *getInsertPos() const { return InsertPos; }
+ void setInsertPos(Instruction *Inst) { InsertPos = Inst; }
+
+ /// Add metadata (e.g. alias info) from the instructions in this group to \p
+ /// NewInst.
+ ///
+ /// FIXME: this function currently does not add noalias metadata a'la
+ /// addNewMedata. To do that we need to compute the intersection of the
+ /// noalias info from all members.
+ void addMetadata(Instruction *NewInst) const {
+ SmallVector<Value *, 4> VL;
+ std::transform(Members.begin(), Members.end(), std::back_inserter(VL),
+ [](std::pair<int, Instruction *> p) { return p.second; });
+ propagateMetadata(NewInst, VL);
+ }
+
+private:
+ unsigned Factor; // Interleave Factor.
+ bool Reverse;
+ unsigned Align;
+ DenseMap<int, Instruction *> Members;
+ int SmallestKey = 0;
+ int LargestKey = 0;
+
+ // To avoid breaking dependences, vectorized instructions of an interleave
+ // group should be inserted at either the first load or the last store in
+ // program order.
+ //
+ // E.g. %even = load i32 // Insert Position
+ // %add = add i32 %even // Use of %even
+ // %odd = load i32
+ //
+ // store i32 %even
+ // %odd = add i32 // Def of %odd
+ // store i32 %odd // Insert Position
+ Instruction *InsertPos;
+};
+
+/// Drive the analysis of interleaved memory accesses in the loop.
+///
+/// Use this class to analyze interleaved accesses only when we can vectorize
+/// a loop. Otherwise it's meaningless to do analysis as the vectorization
+/// on interleaved accesses is unsafe.
+///
+/// The analysis collects interleave groups and records the relationships
+/// between the member and the group in a map.
+class InterleavedAccessInfo {
+public:
+ InterleavedAccessInfo(PredicatedScalarEvolution &PSE, Loop *L,
+ DominatorTree *DT, LoopInfo *LI,
+ const LoopAccessInfo *LAI)
+ : PSE(PSE), TheLoop(L), DT(DT), LI(LI), LAI(LAI) {}
+
+ ~InterleavedAccessInfo() {
+ SmallPtrSet<InterleaveGroup *, 4> DelSet;
+ // Avoid releasing a pointer twice.
+ for (auto &I : InterleaveGroupMap)
+ DelSet.insert(I.second);
+ for (auto *Ptr : DelSet)
+ delete Ptr;
+ }
+
+ /// Analyze the interleaved accesses and collect them in interleave
+ /// groups. Substitute symbolic strides using \p Strides.
+ void analyzeInterleaving();
+
+ /// Check if \p Instr belongs to any interleave group.
+ bool isInterleaved(Instruction *Instr) const {
+ return InterleaveGroupMap.find(Instr) != InterleaveGroupMap.end();
+ }
+
+ /// Get the interleave group that \p Instr belongs to.
+ ///
+ /// \returns nullptr if doesn't have such group.
+ InterleaveGroup *getInterleaveGroup(Instruction *Instr) const {
+ auto Group = InterleaveGroupMap.find(Instr);
+ if (Group == InterleaveGroupMap.end())
+ return nullptr;
+ return Group->second;
+ }
+
+ /// Returns true if an interleaved group that may access memory
+ /// out-of-bounds requires a scalar epilogue iteration for correctness.
+ bool requiresScalarEpilogue() const { return RequiresScalarEpilogue; }
+
+private:
+ /// A wrapper around ScalarEvolution, used to add runtime SCEV checks.
+ /// Simplifies SCEV expressions in the context of existing SCEV assumptions.
+ /// The interleaved access analysis can also add new predicates (for example
+ /// by versioning strides of pointers).
+ PredicatedScalarEvolution &PSE;
+
+ Loop *TheLoop;
+ DominatorTree *DT;
+ LoopInfo *LI;
+ const LoopAccessInfo *LAI;
+
+ /// True if the loop may contain non-reversed interleaved groups with
+ /// out-of-bounds accesses. We ensure we don't speculatively access memory
+ /// out-of-bounds by executing at least one scalar epilogue iteration.
+ bool RequiresScalarEpilogue = false;
+
+ /// Holds the relationships between the members and the interleave group.
+ DenseMap<Instruction *, InterleaveGroup *> InterleaveGroupMap;
+
+ /// Holds dependences among the memory accesses in the loop. It maps a source
+ /// access to a set of dependent sink accesses.
+ DenseMap<Instruction *, SmallPtrSet<Instruction *, 2>> Dependences;
+
+ /// The descriptor for a strided memory access.
+ struct StrideDescriptor {
+ StrideDescriptor() = default;
+ StrideDescriptor(int64_t Stride, const SCEV *Scev, uint64_t Size,
+ unsigned Align)
+ : Stride(Stride), Scev(Scev), Size(Size), Align(Align) {}
+
+ // The access's stride. It is negative for a reverse access.
+ int64_t Stride = 0;
+
+ // The scalar expression of this access.
+ const SCEV *Scev = nullptr;
+
+ // The size of the memory object.
+ uint64_t Size = 0;
+
+ // The alignment of this access.
+ unsigned Align = 0;
+ };
+
+ /// A type for holding instructions and their stride descriptors.
+ using StrideEntry = std::pair<Instruction *, StrideDescriptor>;
+
+ /// Create a new interleave group with the given instruction \p Instr,
+ /// stride \p Stride and alignment \p Align.
+ ///
+ /// \returns the newly created interleave group.
+ InterleaveGroup *createInterleaveGroup(Instruction *Instr, int Stride,
+ unsigned Align) {
+ assert(!isInterleaved(Instr) && "Already in an interleaved access group");
+ InterleaveGroupMap[Instr] = new InterleaveGroup(Instr, Stride, Align);
+ return InterleaveGroupMap[Instr];
+ }
+
+ /// Release the group and remove all the relationships.
+ void releaseGroup(InterleaveGroup *Group) {
+ for (unsigned i = 0; i < Group->getFactor(); i++)
+ if (Instruction *Member = Group->getMember(i))
+ InterleaveGroupMap.erase(Member);
+
+ delete Group;
+ }
+
+ /// Collect all the accesses with a constant stride in program order.
+ void collectConstStrideAccesses(
+ MapVector<Instruction *, StrideDescriptor> &AccessStrideInfo,
+ const ValueToValueMap &Strides);
+
+ /// Returns true if \p Stride is allowed in an interleaved group.
+ static bool isStrided(int Stride);
+
+ /// Returns true if \p BB is a predicated block.
+ bool isPredicated(BasicBlock *BB) const {
+ return LoopAccessInfo::blockNeedsPredication(BB, TheLoop, DT);
+ }
+
+ /// Returns true if LoopAccessInfo can be used for dependence queries.
+ bool areDependencesValid() const {
+ return LAI && LAI->getDepChecker().getDependences();
+ }
+
+ /// Returns true if memory accesses \p A and \p B can be reordered, if
+ /// necessary, when constructing interleaved groups.
+ ///
+ /// \p A must precede \p B in program order. We return false if reordering is
+ /// not necessary or is prevented because \p A and \p B may be dependent.
+ bool canReorderMemAccessesForInterleavedGroups(StrideEntry *A,
+ StrideEntry *B) const {
+ // Code motion for interleaved accesses can potentially hoist strided loads
+ // and sink strided stores. The code below checks the legality of the
+ // following two conditions:
+ //
+ // 1. Potentially moving a strided load (B) before any store (A) that
+ // precedes B, or
+ //
+ // 2. Potentially moving a strided store (A) after any load or store (B)
+ // that A precedes.
+ //
+ // It's legal to reorder A and B if we know there isn't a dependence from A
+ // to B. Note that this determination is conservative since some
+ // dependences could potentially be reordered safely.
+
+ // A is potentially the source of a dependence.
+ auto *Src = A->first;
+ auto SrcDes = A->second;
+
+ // B is potentially the sink of a dependence.
+ auto *Sink = B->first;
+ auto SinkDes = B->second;
+
+ // Code motion for interleaved accesses can't violate WAR dependences.
+ // Thus, reordering is legal if the source isn't a write.
+ if (!Src->mayWriteToMemory())
+ return true;
+
+ // At least one of the accesses must be strided.
+ if (!isStrided(SrcDes.Stride) && !isStrided(SinkDes.Stride))
+ return true;
+
+ // If dependence information is not available from LoopAccessInfo,
+ // conservatively assume the instructions can't be reordered.
+ if (!areDependencesValid())
+ return false;
+
+ // If we know there is a dependence from source to sink, assume the
+ // instructions can't be reordered. Otherwise, reordering is legal.
+ return Dependences.find(Src) == Dependences.end() ||
+ !Dependences.lookup(Src).count(Sink);
+ }
+
+ /// Collect the dependences from LoopAccessInfo.
+ ///
+ /// We process the dependences once during the interleaved access analysis to
+ /// enable constant-time dependence queries.
+ void collectDependences() {
+ if (!areDependencesValid())
+ return;
+ auto *Deps = LAI->getDepChecker().getDependences();
+ for (auto Dep : *Deps)
+ Dependences[Dep.getSource(*LAI)].insert(Dep.getDestination(*LAI));
+ }
+};
+
} // llvm namespace
#endif