Update prebuilt Clang to match Android kernel.
Bug: 132428451
Change-Id: I8f6e2cb23f381fc0c02ddea99b867e58e925e5be
diff --git a/linux-x64/clang/include/llvm/Analysis/VectorUtils.h b/linux-x64/clang/include/llvm/Analysis/VectorUtils.h
index 622d932..60ef633 100644
--- a/linux-x64/clang/include/llvm/Analysis/VectorUtils.h
+++ b/linux-x64/clang/include/llvm/Analysis/VectorUtils.h
@@ -1,9 +1,8 @@
//===- llvm/Analysis/VectorUtils.h - Vector utilities -----------*- C++ -*-===//
//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
+// 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
//
//===----------------------------------------------------------------------===//
//
@@ -24,6 +23,7 @@
template <typename T> class ArrayRef;
class DemandedBits;
class GetElementPtrInst;
+template <typename InstTy> class InterleaveGroup;
class Loop;
class ScalarEvolution;
class TargetTransformInfo;
@@ -116,8 +116,24 @@
DemandedBits &DB,
const TargetTransformInfo *TTI=nullptr);
+/// Compute the union of two access-group lists.
+///
+/// If the list contains just one access group, it is returned directly. If the
+/// list is empty, returns nullptr.
+MDNode *uniteAccessGroups(MDNode *AccGroups1, MDNode *AccGroups2);
+
+/// Compute the access-group list of access groups that @p Inst1 and @p Inst2
+/// are both in. If either instruction does not access memory at all, it is
+/// considered to be in every list.
+///
+/// If the list contains just one access group, it is returned directly. If the
+/// list is empty, returns nullptr.
+MDNode *intersectAccessGroups(const Instruction *Inst1,
+ const Instruction *Inst2);
+
/// Specifically, let Kinds = [MD_tbaa, MD_alias_scope, MD_noalias, MD_fpmath,
-/// MD_nontemporal]. For K in Kinds, we get the MDNode for K from each of the
+/// MD_nontemporal, MD_access_group].
+/// For K in Kinds, we get the MDNode for K from each of the
/// elements of VL, compute their "intersection" (i.e., the most generic
/// metadata value that covers all of the individual values), and set I's
/// metadata for M equal to the intersection value.
@@ -125,6 +141,35 @@
/// This function always sets a (possibly null) value for each K in Kinds.
Instruction *propagateMetadata(Instruction *I, ArrayRef<Value *> VL);
+/// Create a mask that filters the members of an interleave group where there
+/// are gaps.
+///
+/// For example, the mask for \p Group with interleave-factor 3
+/// and \p VF 4, that has only its first member present is:
+///
+/// <1,0,0,1,0,0,1,0,0,1,0,0>
+///
+/// Note: The result is a mask of 0's and 1's, as opposed to the other
+/// create[*]Mask() utilities which create a shuffle mask (mask that
+/// consists of indices).
+Constant *createBitMaskForGaps(IRBuilder<> &Builder, unsigned VF,
+ const InterleaveGroup<Instruction> &Group);
+
+/// Create a mask with replicated elements.
+///
+/// This function creates a shuffle mask for replicating each of the \p VF
+/// elements in a vector \p ReplicationFactor times. It can be used to
+/// transform a mask of \p VF elements into a mask of
+/// \p VF * \p ReplicationFactor elements used by a predicated
+/// interleaved-group of loads/stores whose Interleaved-factor ==
+/// \p ReplicationFactor.
+///
+/// For example, the mask for \p ReplicationFactor=3 and \p VF=4 is:
+///
+/// <0,0,0,1,1,1,2,2,2,3,3,3>
+Constant *createReplicatedMask(IRBuilder<> &Builder, unsigned ReplicationFactor,
+ unsigned VF);
+
/// Create an interleave shuffle mask.
///
/// This function creates a shuffle mask for interleaving \p NumVecs vectors of
@@ -203,9 +248,12 @@
///
/// Note: the interleaved load group could have gaps (missing members), but
/// the interleaved store group doesn't allow gaps.
-class InterleaveGroup {
+template <typename InstTy> class InterleaveGroup {
public:
- InterleaveGroup(Instruction *Instr, int Stride, unsigned Align)
+ InterleaveGroup(unsigned Factor, bool Reverse, unsigned Align)
+ : Factor(Factor), Reverse(Reverse), Align(Align), InsertPos(nullptr) {}
+
+ InterleaveGroup(InstTy *Instr, int Stride, unsigned Align)
: Align(Align), InsertPos(Instr) {
assert(Align && "The alignment should be non-zero");
@@ -226,7 +274,7 @@
/// 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) {
+ bool insertMember(InstTy *Instr, int Index, unsigned NewAlign) {
assert(NewAlign && "The new member's alignment should be non-zero");
int Key = Index + SmallestKey;
@@ -258,7 +306,7 @@
/// Get the member with the given index \p Index
///
/// \returns nullptr if contains no such member.
- Instruction *getMember(unsigned Index) const {
+ InstTy *getMember(unsigned Index) const {
int Key = SmallestKey + Index;
auto Member = Members.find(Key);
if (Member == Members.end())
@@ -269,16 +317,17 @@
/// 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)
+ unsigned getIndex(const InstTy *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; }
+ InstTy *getInsertPos() const { return InsertPos; }
+ void setInsertPos(InstTy *Inst) { InsertPos = Inst; }
/// Add metadata (e.g. alias info) from the instructions in this group to \p
/// NewInst.
@@ -286,18 +335,30 @@
/// 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);
+ void addMetadata(InstTy *NewInst) const;
+
+ /// Returns true if this Group requires a scalar iteration to handle gaps.
+ bool requiresScalarEpilogue() const {
+ // If the last member of the Group exists, then a scalar epilog is not
+ // needed for this group.
+ if (getMember(getFactor() - 1))
+ return false;
+
+ // We have a group with gaps. It therefore cannot be a group of stores,
+ // and it can't be a reversed access, because such groups get invalidated.
+ assert(!getMember(0)->mayWriteToMemory() &&
+ "Group should have been invalidated");
+ assert(!isReverse() && "Group should have been invalidated");
+
+ // This is a group of loads, with gaps, and without a last-member
+ return true;
}
private:
unsigned Factor; // Interleave Factor.
bool Reverse;
unsigned Align;
- DenseMap<int, Instruction *> Members;
+ DenseMap<int, InstTy *> Members;
int SmallestKey = 0;
int LargestKey = 0;
@@ -312,7 +373,7 @@
// store i32 %even
// %odd = add i32 // Def of %odd
// store i32 %odd // Insert Position
- Instruction *InsertPos;
+ InstTy *InsertPos;
};
/// Drive the analysis of interleaved memory accesses in the loop.
@@ -328,20 +389,31 @@
InterleavedAccessInfo(PredicatedScalarEvolution &PSE, Loop *L,
DominatorTree *DT, LoopInfo *LI,
const LoopAccessInfo *LAI)
- : PSE(PSE), TheLoop(L), DT(DT), LI(LI), LAI(LAI) {}
+ : PSE(PSE), TheLoop(L), DT(DT), LI(LI), LAI(LAI) {}
- ~InterleavedAccessInfo() {
- SmallPtrSet<InterleaveGroup *, 4> DelSet;
+ ~InterleavedAccessInfo() { reset(); }
+
+ /// Analyze the interleaved accesses and collect them in interleave
+ /// groups. Substitute symbolic strides using \p Strides.
+ /// Consider also predicated loads/stores in the analysis if
+ /// \p EnableMaskedInterleavedGroup is true.
+ void analyzeInterleaving(bool EnableMaskedInterleavedGroup);
+
+ /// Invalidate groups, e.g., in case all blocks in loop will be predicated
+ /// contrary to original assumption. Although we currently prevent group
+ /// formation for predicated accesses, we may be able to relax this limitation
+ /// in the future once we handle more complicated blocks.
+ void reset() {
+ SmallPtrSet<InterleaveGroup<Instruction> *, 4> DelSet;
// Avoid releasing a pointer twice.
for (auto &I : InterleaveGroupMap)
DelSet.insert(I.second);
for (auto *Ptr : DelSet)
delete Ptr;
+ InterleaveGroupMap.clear();
+ RequiresScalarEpilogue = false;
}
- /// 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 {
@@ -351,17 +423,27 @@
/// 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;
+ InterleaveGroup<Instruction> *
+ getInterleaveGroup(const Instruction *Instr) const {
+ if (InterleaveGroupMap.count(Instr))
+ return InterleaveGroupMap.find(Instr)->second;
+ return nullptr;
+ }
+
+ iterator_range<SmallPtrSetIterator<llvm::InterleaveGroup<Instruction> *>>
+ getInterleaveGroups() {
+ return make_range(InterleaveGroups.begin(), InterleaveGroups.end());
}
/// 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; }
+ /// Invalidate groups that require a scalar epilogue (due to gaps). This can
+ /// happen when optimizing for size forbids a scalar epilogue, and the gap
+ /// cannot be filtered by masking the load/store.
+ void invalidateGroupsRequiringScalarEpilogue();
+
private:
/// A wrapper around ScalarEvolution, used to add runtime SCEV checks.
/// Simplifies SCEV expressions in the context of existing SCEV assumptions.
@@ -380,7 +462,9 @@
bool RequiresScalarEpilogue = false;
/// Holds the relationships between the members and the interleave group.
- DenseMap<Instruction *, InterleaveGroup *> InterleaveGroupMap;
+ DenseMap<Instruction *, InterleaveGroup<Instruction> *> InterleaveGroupMap;
+
+ SmallPtrSet<InterleaveGroup<Instruction> *, 4> InterleaveGroups;
/// Holds dependences among the memory accesses in the loop. It maps a source
/// access to a set of dependent sink accesses.
@@ -413,19 +497,23 @@
/// 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);
+ InterleaveGroup<Instruction> *
+ createInterleaveGroup(Instruction *Instr, int Stride, unsigned Align) {
+ assert(!InterleaveGroupMap.count(Instr) &&
+ "Already in an interleaved access group");
+ InterleaveGroupMap[Instr] =
+ new InterleaveGroup<Instruction>(Instr, Stride, Align);
+ InterleaveGroups.insert(InterleaveGroupMap[Instr]);
return InterleaveGroupMap[Instr];
}
/// Release the group and remove all the relationships.
- void releaseGroup(InterleaveGroup *Group) {
+ void releaseGroup(InterleaveGroup<Instruction> *Group) {
for (unsigned i = 0; i < Group->getFactor(); i++)
if (Instruction *Member = Group->getMember(i))
InterleaveGroupMap.erase(Member);
+ InterleaveGroups.erase(Group);
delete Group;
}