Update prebuilt Clang to r416183b from Android.
https://android.googlesource.com/platform/prebuilts/clang/host/
linux-x86/+/06a71ddac05c22edb2d10b590e1769b3f8619bef
clang 12.0.5 (based on r416183b) from build 7284624.
Change-Id: I277a316abcf47307562d8b748b84870f31a72866
Signed-off-by: Olivier Deprez <olivier.deprez@arm.com>
diff --git a/linux-x64/clang/include/polly/CodeGen/BlockGenerators.h b/linux-x64/clang/include/polly/CodeGen/BlockGenerators.h
new file mode 100644
index 0000000..f2c52c8
--- /dev/null
+++ b/linux-x64/clang/include/polly/CodeGen/BlockGenerators.h
@@ -0,0 +1,973 @@
+//===-BlockGenerators.h - Helper to generate code for statements-*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the BlockGenerator and VectorBlockGenerator classes, which
+// generate sequential code and vectorized code for a polyhedral statement,
+// respectively.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef POLLY_BLOCK_GENERATORS_H
+#define POLLY_BLOCK_GENERATORS_H
+
+#include "polly/CodeGen/IRBuilder.h"
+#include "polly/Support/ScopHelper.h"
+#include "llvm/Analysis/ScalarEvolutionExpressions.h"
+#include "isl/isl-noexceptions.h"
+
+namespace polly {
+using namespace llvm;
+class MemoryAccess;
+class ScopArrayInfo;
+class IslExprBuilder;
+
+/// Generate a new basic block for a polyhedral statement.
+class BlockGenerator {
+public:
+ typedef llvm::SmallVector<ValueMapT, 8> VectorValueMapT;
+
+ /// Map types to resolve scalar dependences.
+ ///
+ ///@{
+ using AllocaMapTy = DenseMap<const ScopArrayInfo *, AssertingVH<AllocaInst>>;
+
+ /// Simple vector of instructions to store escape users.
+ using EscapeUserVectorTy = SmallVector<Instruction *, 4>;
+
+ /// Map type to resolve escaping users for scalar instructions.
+ ///
+ /// @see The EscapeMap member.
+ using EscapeUsersAllocaMapTy =
+ MapVector<Instruction *,
+ std::pair<AssertingVH<Value>, EscapeUserVectorTy>>;
+
+ ///@}
+
+ /// Create a generator for basic blocks.
+ ///
+ /// @param Builder The LLVM-IR Builder used to generate the statement. The
+ /// code is generated at the location, the Builder points
+ /// to.
+ /// @param LI The loop info for the current function
+ /// @param SE The scalar evolution info for the current function
+ /// @param DT The dominator tree of this function.
+ /// @param ScalarMap Map from scalars to their demoted location.
+ /// @param EscapeMap Map from scalars to their escape users and locations.
+ /// @param GlobalMap A mapping from llvm::Values used in the original scop
+ /// region to a new set of llvm::Values. Each reference to
+ /// an original value appearing in this mapping is replaced
+ /// with the new value it is mapped to.
+ /// @param ExprBuilder An expression builder to generate new access functions.
+ /// @param StartBlock The first basic block after the RTC.
+ BlockGenerator(PollyIRBuilder &Builder, LoopInfo &LI, ScalarEvolution &SE,
+ DominatorTree &DT, AllocaMapTy &ScalarMap,
+ EscapeUsersAllocaMapTy &EscapeMap, ValueMapT &GlobalMap,
+ IslExprBuilder *ExprBuilder, BasicBlock *StartBlock);
+
+ /// Copy the basic block.
+ ///
+ /// This copies the entire basic block and updates references to old values
+ /// with references to new values, as defined by GlobalMap.
+ ///
+ /// @param Stmt The block statement to code generate.
+ /// @param LTS A map from old loops to new induction variables as
+ /// SCEVs.
+ /// @param NewAccesses A map from memory access ids to new ast expressions,
+ /// which may contain new access expressions for certain
+ /// memory accesses.
+ void copyStmt(ScopStmt &Stmt, LoopToScevMapT <S,
+ isl_id_to_ast_expr *NewAccesses);
+
+ /// Remove a ScopArrayInfo's allocation from the ScalarMap.
+ ///
+ /// This function allows to remove values from the ScalarMap. This is useful
+ /// if the corresponding alloca instruction will be deleted (or moved into
+ /// another module), as without removing these values the underlying
+ /// AssertingVH will trigger due to us still keeping reference to this
+ /// scalar.
+ ///
+ /// @param Array The array for which the alloca was generated.
+ void freeScalarAlloc(ScopArrayInfo *Array) { ScalarMap.erase(Array); }
+
+ /// Return the alloca for @p Access.
+ ///
+ /// If no alloca was mapped for @p Access a new one is created.
+ ///
+ /// @param Access The memory access for which to generate the alloca.
+ ///
+ /// @returns The alloca for @p Access or a replacement value taken from
+ /// GlobalMap.
+ Value *getOrCreateAlloca(const MemoryAccess &Access);
+
+ /// Return the alloca for @p Array.
+ ///
+ /// If no alloca was mapped for @p Array a new one is created.
+ ///
+ /// @param Array The array for which to generate the alloca.
+ ///
+ /// @returns The alloca for @p Array or a replacement value taken from
+ /// GlobalMap.
+ Value *getOrCreateAlloca(const ScopArrayInfo *Array);
+
+ /// Finalize the code generation for the SCoP @p S.
+ ///
+ /// This will initialize and finalize the scalar variables we demoted during
+ /// the code generation.
+ ///
+ /// @see createScalarInitialization(Scop &)
+ /// @see createScalarFinalization(Region &)
+ void finalizeSCoP(Scop &S);
+
+ /// An empty destructor
+ virtual ~BlockGenerator() {}
+
+ BlockGenerator(const BlockGenerator &) = default;
+
+protected:
+ PollyIRBuilder &Builder;
+ LoopInfo &LI;
+ ScalarEvolution &SE;
+ IslExprBuilder *ExprBuilder;
+
+ /// The dominator tree of this function.
+ DominatorTree &DT;
+
+ /// The entry block of the current function.
+ BasicBlock *EntryBB;
+
+ /// Map to resolve scalar dependences for PHI operands and scalars.
+ ///
+ /// When translating code that contains scalar dependences as they result from
+ /// inter-block scalar dependences (including the use of data carrying PHI
+ /// nodes), we do not directly regenerate in-register SSA code, but instead
+ /// allocate some stack memory through which these scalar values are passed.
+ /// Only a later pass of -mem2reg will then (re)introduce in-register
+ /// computations.
+ ///
+ /// To keep track of the memory location(s) used to store the data computed by
+ /// a given SSA instruction, we use the map 'ScalarMap'. ScalarMap maps a
+ /// given ScopArrayInfo to the junk of stack allocated memory, that is
+ /// used for code generation.
+ ///
+ /// Up to two different ScopArrayInfo objects are associated with each
+ /// llvm::Value:
+ ///
+ /// MemoryType::Value objects are used for normal scalar dependences that go
+ /// from a scalar definition to its use. Such dependences are lowered by
+ /// directly writing the value an instruction computes into the corresponding
+ /// chunk of memory and reading it back from this chunk of memory right before
+ /// every use of this original scalar value. The memory allocations for
+ /// MemoryType::Value objects end with '.s2a'.
+ ///
+ /// MemoryType::PHI (and MemoryType::ExitPHI) objects are used to model PHI
+ /// nodes. For each PHI nodes we introduce, besides the Array of type
+ /// MemoryType::Value, a second chunk of memory into which we write at the end
+ /// of each basic block preceding the PHI instruction the value passed
+ /// through this basic block. At the place where the PHI node is executed, we
+ /// replace the PHI node with a load from the corresponding MemoryType::PHI
+ /// memory location. The memory allocations for MemoryType::PHI end with
+ /// '.phiops'.
+ ///
+ /// Example:
+ ///
+ /// Input C Code
+ /// ============
+ ///
+ /// S1: x1 = ...
+ /// for (i=0...N) {
+ /// S2: x2 = phi(x1, add)
+ /// S3: add = x2 + 42;
+ /// }
+ /// S4: print(x1)
+ /// print(x2)
+ /// print(add)
+ ///
+ ///
+ /// Unmodified IR IR After expansion
+ /// ============= ==================
+ ///
+ /// S1: x1 = ... S1: x1 = ...
+ /// x1.s2a = s1
+ /// x2.phiops = s1
+ /// | |
+ /// | <--<--<--<--< | <--<--<--<--<
+ /// | / \ | / \ .
+ /// V V \ V V \ .
+ /// S2: x2 = phi (x1, add) | S2: x2 = x2.phiops |
+ /// | x2.s2a = x2 |
+ /// | |
+ /// S3: add = x2 + 42 | S3: add = x2 + 42 |
+ /// | add.s2a = add |
+ /// | x2.phiops = add |
+ /// | \ / | \ /
+ /// | \ / | \ /
+ /// | >-->-->-->--> | >-->-->-->-->
+ /// V V
+ ///
+ /// S4: x1 = x1.s2a
+ /// S4: ... = x1 ... = x1
+ /// x2 = x2.s2a
+ /// ... = x2 ... = x2
+ /// add = add.s2a
+ /// ... = add ... = add
+ ///
+ /// ScalarMap = { x1:Value -> x1.s2a, x2:Value -> x2.s2a,
+ /// add:Value -> add.s2a, x2:PHI -> x2.phiops }
+ ///
+ /// ??? Why does a PHI-node require two memory chunks ???
+ ///
+ /// One may wonder why a PHI node requires two memory chunks and not just
+ /// all data is stored in a single location. The following example tries
+ /// to store all data in .s2a and drops the .phiops location:
+ ///
+ /// S1: x1 = ...
+ /// x1.s2a = s1
+ /// x2.s2a = s1 // use .s2a instead of .phiops
+ /// |
+ /// | <--<--<--<--<
+ /// | / \ .
+ /// V V \ .
+ /// S2: x2 = x2.s2a | // value is same as above, but read
+ /// | // from .s2a
+ /// |
+ /// x2.s2a = x2 | // store into .s2a as normal
+ /// |
+ /// S3: add = x2 + 42 |
+ /// add.s2a = add |
+ /// x2.s2a = add | // use s2a instead of .phiops
+ /// | \ / // !!! This is wrong, as x2.s2a now
+ /// | >-->-->-->--> // contains add instead of x2.
+ /// V
+ ///
+ /// S4: x1 = x1.s2a
+ /// ... = x1
+ /// x2 = x2.s2a // !!! We now read 'add' instead of
+ /// ... = x2 // 'x2'
+ /// add = add.s2a
+ /// ... = add
+ ///
+ /// As visible in the example, the SSA value of the PHI node may still be
+ /// needed _after_ the basic block, which could conceptually branch to the
+ /// PHI node, has been run and has overwritten the PHI's old value. Hence, a
+ /// single memory location is not enough to code-generate a PHI node.
+ ///
+ /// Memory locations used for the special PHI node modeling.
+ AllocaMapTy &ScalarMap;
+
+ /// Map from instructions to their escape users as well as the alloca.
+ EscapeUsersAllocaMapTy &EscapeMap;
+
+ /// A map from llvm::Values referenced in the old code to a new set of
+ /// llvm::Values, which is used to replace these old values during
+ /// code generation.
+ ValueMapT &GlobalMap;
+
+ /// The first basic block after the RTC.
+ BasicBlock *StartBlock;
+
+ /// Split @p BB to create a new one we can use to clone @p BB in.
+ BasicBlock *splitBB(BasicBlock *BB);
+
+ /// Copy the given basic block.
+ ///
+ /// @param Stmt The statement to code generate.
+ /// @param BB The basic block to code generate.
+ /// @param BBMap A mapping from old values to their new values in this
+ /// block.
+ /// @param LTS A map from old loops to new induction variables as
+ /// SCEVs.
+ /// @param NewAccesses A map from memory access ids to new ast expressions,
+ /// which may contain new access expressions for certain
+ /// memory accesses.
+ ///
+ /// @returns The copy of the basic block.
+ BasicBlock *copyBB(ScopStmt &Stmt, BasicBlock *BB, ValueMapT &BBMap,
+ LoopToScevMapT <S, isl_id_to_ast_expr *NewAccesses);
+
+ /// Copy the given basic block.
+ ///
+ /// @param Stmt The statement to code generate.
+ /// @param BB The basic block to code generate.
+ /// @param BBCopy The new basic block to generate code in.
+ /// @param BBMap A mapping from old values to their new values in this
+ /// block.
+ /// @param LTS A map from old loops to new induction variables as
+ /// SCEVs.
+ /// @param NewAccesses A map from memory access ids to new ast expressions,
+ /// which may contain new access expressions for certain
+ /// memory accesses.
+ void copyBB(ScopStmt &Stmt, BasicBlock *BB, BasicBlock *BBCopy,
+ ValueMapT &BBMap, LoopToScevMapT <S,
+ isl_id_to_ast_expr *NewAccesses);
+
+ /// Generate reload of scalars demoted to memory and needed by @p Stmt.
+ ///
+ /// @param Stmt The statement we generate code for.
+ /// @param LTS A mapping from loops virtual canonical induction
+ /// variable to their new values.
+ /// @param BBMap A mapping from old values to their new values in this block.
+ /// @param NewAccesses A map from memory access ids to new ast expressions.
+ void generateScalarLoads(ScopStmt &Stmt, LoopToScevMapT <S,
+ ValueMapT &BBMap,
+ __isl_keep isl_id_to_ast_expr *NewAccesses);
+
+ /// When statement tracing is enabled, build the print instructions for
+ /// printing the current statement instance.
+ ///
+ /// The printed output looks like:
+ ///
+ /// Stmt1(0)
+ ///
+ /// If printing of scalars is enabled, it also appends the value of each
+ /// scalar to the line:
+ ///
+ /// Stmt1(0) %i=1 %sum=5
+ ///
+ /// @param Stmt The statement we generate code for.
+ /// @param LTS A mapping from loops virtual canonical induction
+ /// variable to their new values.
+ /// @param BBMap A mapping from old values to their new values in this block.
+ void generateBeginStmtTrace(ScopStmt &Stmt, LoopToScevMapT <S,
+ ValueMapT &BBMap);
+
+ /// Generate instructions that compute whether one instance of @p Set is
+ /// executed.
+ ///
+ /// @param Stmt The statement we generate code for.
+ /// @param Subdomain A set in the space of @p Stmt's domain. Elements not in
+ /// @p Stmt's domain are ignored.
+ ///
+ /// @return An expression of type i1, generated into the current builder
+ /// position, that evaluates to 1 if the executed instance is part of
+ /// @p Set.
+ Value *buildContainsCondition(ScopStmt &Stmt, const isl::set &Subdomain);
+
+ /// Generate code that executes in a subset of @p Stmt's domain.
+ ///
+ /// @param Stmt The statement we generate code for.
+ /// @param Subdomain The condition for some code to be executed.
+ /// @param Subject A name for the code that is executed
+ /// conditionally. Used to name new basic blocks and
+ /// instructions.
+ /// @param GenThenFunc Callback which generates the code to be executed
+ /// when the current executed instance is in @p Set. The
+ /// IRBuilder's position is moved to within the block that
+ /// executes conditionally for this callback.
+ void generateConditionalExecution(ScopStmt &Stmt, const isl::set &Subdomain,
+ StringRef Subject,
+ const std::function<void()> &GenThenFunc);
+
+ /// Generate the scalar stores for the given statement.
+ ///
+ /// After the statement @p Stmt was copied all inner-SCoP scalar dependences
+ /// starting in @p Stmt (hence all scalar write accesses in @p Stmt) need to
+ /// be demoted to memory.
+ ///
+ /// @param Stmt The statement we generate code for.
+ /// @param LTS A mapping from loops virtual canonical induction
+ /// variable to their new values
+ /// (for values recalculated in the new ScoP, but not
+ /// within this basic block)
+ /// @param BBMap A mapping from old values to their new values in this block.
+ /// @param NewAccesses A map from memory access ids to new ast expressions.
+ virtual void generateScalarStores(ScopStmt &Stmt, LoopToScevMapT <S,
+ ValueMapT &BBMap,
+ __isl_keep isl_id_to_ast_expr *NewAccesses);
+
+ /// Handle users of @p Array outside the SCoP.
+ ///
+ /// @param S The current SCoP.
+ /// @param Inst The ScopArrayInfo to handle.
+ void handleOutsideUsers(const Scop &S, ScopArrayInfo *Array);
+
+ /// Find scalar statements that have outside users.
+ ///
+ /// We register these scalar values to later update subsequent scalar uses of
+ /// these values to either use the newly computed value from within the scop
+ /// (if the scop was executed) or the unchanged original code (if the run-time
+ /// check failed).
+ ///
+ /// @param S The scop for which to find the outside users.
+ void findOutsideUsers(Scop &S);
+
+ /// Initialize the memory of demoted scalars.
+ ///
+ /// @param S The scop for which to generate the scalar initializers.
+ void createScalarInitialization(Scop &S);
+
+ /// Create exit PHI node merges for PHI nodes with more than two edges
+ /// from inside the scop.
+ ///
+ /// For scops which have a PHI node in the exit block that has more than two
+ /// incoming edges from inside the scop region, we require some special
+ /// handling to understand which of the possible values will be passed to the
+ /// PHI node from inside the optimized version of the scop. To do so ScopInfo
+ /// models the possible incoming values as write accesses of the ScopStmts.
+ ///
+ /// This function creates corresponding code to reload the computed outgoing
+ /// value from the stack slot it has been stored into and to pass it on to the
+ /// PHI node in the original exit block.
+ ///
+ /// @param S The scop for which to generate the exiting PHI nodes.
+ void createExitPHINodeMerges(Scop &S);
+
+ /// Promote the values of demoted scalars after the SCoP.
+ ///
+ /// If a scalar value was used outside the SCoP we need to promote the value
+ /// stored in the memory cell allocated for that scalar and combine it with
+ /// the original value in the non-optimized SCoP.
+ void createScalarFinalization(Scop &S);
+
+ /// Try to synthesize a new value
+ ///
+ /// Given an old value, we try to synthesize it in a new context from its
+ /// original SCEV expression. We start from the original SCEV expression,
+ /// then replace outdated parameter and loop references, and finally
+ /// expand it to code that computes this updated expression.
+ ///
+ /// @param Stmt The statement to code generate
+ /// @param Old The old Value
+ /// @param BBMap A mapping from old values to their new values
+ /// (for values recalculated within this basic block)
+ /// @param LTS A mapping from loops virtual canonical induction
+ /// variable to their new values
+ /// (for values recalculated in the new ScoP, but not
+ /// within this basic block)
+ /// @param L The loop that surrounded the instruction that referenced
+ /// this value in the original code. This loop is used to
+ /// evaluate the scalar evolution at the right scope.
+ ///
+ /// @returns o A newly synthesized value.
+ /// o NULL, if synthesizing the value failed.
+ Value *trySynthesizeNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap,
+ LoopToScevMapT <S, Loop *L) const;
+
+ /// Get the new version of a value.
+ ///
+ /// Given an old value, we first check if a new version of this value is
+ /// available in the BBMap or GlobalMap. In case it is not and the value can
+ /// be recomputed using SCEV, we do so. If we can not recompute a value
+ /// using SCEV, but we understand that the value is constant within the scop,
+ /// we return the old value. If the value can still not be derived, this
+ /// function will assert.
+ ///
+ /// @param Stmt The statement to code generate.
+ /// @param Old The old Value.
+ /// @param BBMap A mapping from old values to their new values
+ /// (for values recalculated within this basic block).
+ /// @param LTS A mapping from loops virtual canonical induction
+ /// variable to their new values
+ /// (for values recalculated in the new ScoP, but not
+ /// within this basic block).
+ /// @param L The loop that surrounded the instruction that referenced
+ /// this value in the original code. This loop is used to
+ /// evaluate the scalar evolution at the right scope.
+ ///
+ /// @returns o The old value, if it is still valid.
+ /// o The new value, if available.
+ /// o NULL, if no value is found.
+ Value *getNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap,
+ LoopToScevMapT <S, Loop *L) const;
+
+ void copyInstScalar(ScopStmt &Stmt, Instruction *Inst, ValueMapT &BBMap,
+ LoopToScevMapT <S);
+
+ /// Get the innermost loop that surrounds the statement @p Stmt.
+ Loop *getLoopForStmt(const ScopStmt &Stmt) const;
+
+ /// Generate the operand address
+ /// @param NewAccesses A map from memory access ids to new ast expressions,
+ /// which may contain new access expressions for certain
+ /// memory accesses.
+ Value *generateLocationAccessed(ScopStmt &Stmt, MemAccInst Inst,
+ ValueMapT &BBMap, LoopToScevMapT <S,
+ isl_id_to_ast_expr *NewAccesses);
+
+ /// Generate the operand address.
+ ///
+ /// @param Stmt The statement to generate code for.
+ /// @param L The innermost loop that surrounds the statement.
+ /// @param Pointer If the access expression is not changed (ie. not found
+ /// in @p LTS), use this Pointer from the original code
+ /// instead.
+ /// @param BBMap A mapping from old values to their new values.
+ /// @param LTS A mapping from loops virtual canonical induction
+ /// variable to their new values.
+ /// @param NewAccesses Ahead-of-time generated access expressions.
+ /// @param Id Identifier of the MemoryAccess to generate.
+ /// @param ExpectedType The type the returned value should have.
+ ///
+ /// @return The generated address.
+ Value *generateLocationAccessed(ScopStmt &Stmt, Loop *L, Value *Pointer,
+ ValueMapT &BBMap, LoopToScevMapT <S,
+ isl_id_to_ast_expr *NewAccesses,
+ __isl_take isl_id *Id, Type *ExpectedType);
+
+ /// Generate the pointer value that is accesses by @p Access.
+ ///
+ /// For write accesses, generate the target address. For read accesses,
+ /// generate the source address.
+ /// The access can be either an array access or a scalar access. In the first
+ /// case, the returned address will point to an element into that array. In
+ /// the scalar case, an alloca is used.
+ /// If a new AccessRelation is set for the MemoryAccess, the new relation will
+ /// be used.
+ ///
+ /// @param Access The access to generate a pointer for.
+ /// @param L The innermost loop that surrounds the statement.
+ /// @param LTS A mapping from loops virtual canonical induction
+ /// variable to their new values.
+ /// @param BBMap A mapping from old values to their new values.
+ /// @param NewAccesses A map from memory access ids to new ast expressions.
+ ///
+ /// @return The generated address.
+ Value *getImplicitAddress(MemoryAccess &Access, Loop *L, LoopToScevMapT <S,
+ ValueMapT &BBMap,
+ __isl_keep isl_id_to_ast_expr *NewAccesses);
+
+ /// @param NewAccesses A map from memory access ids to new ast expressions,
+ /// which may contain new access expressions for certain
+ /// memory accesses.
+ Value *generateArrayLoad(ScopStmt &Stmt, LoadInst *load, ValueMapT &BBMap,
+ LoopToScevMapT <S,
+ isl_id_to_ast_expr *NewAccesses);
+
+ /// @param NewAccesses A map from memory access ids to new ast expressions,
+ /// which may contain new access expressions for certain
+ /// memory accesses.
+ void generateArrayStore(ScopStmt &Stmt, StoreInst *store, ValueMapT &BBMap,
+ LoopToScevMapT <S, isl_id_to_ast_expr *NewAccesses);
+
+ /// Copy a single PHI instruction.
+ ///
+ /// The implementation in the BlockGenerator is trivial, however it allows
+ /// subclasses to handle PHIs different.
+ virtual void copyPHIInstruction(ScopStmt &, PHINode *, ValueMapT &,
+ LoopToScevMapT &) {}
+
+ /// Copy a single Instruction.
+ ///
+ /// This copies a single Instruction and updates references to old values
+ /// with references to new values, as defined by GlobalMap and BBMap.
+ ///
+ /// @param Stmt The statement to code generate.
+ /// @param Inst The instruction to copy.
+ /// @param BBMap A mapping from old values to their new values
+ /// (for values recalculated within this basic block).
+ /// @param GlobalMap A mapping from old values to their new values
+ /// (for values recalculated in the new ScoP, but not
+ /// within this basic block).
+ /// @param LTS A mapping from loops virtual canonical induction
+ /// variable to their new values
+ /// (for values recalculated in the new ScoP, but not
+ /// within this basic block).
+ /// @param NewAccesses A map from memory access ids to new ast expressions,
+ /// which may contain new access expressions for certain
+ /// memory accesses.
+ void copyInstruction(ScopStmt &Stmt, Instruction *Inst, ValueMapT &BBMap,
+ LoopToScevMapT <S, isl_id_to_ast_expr *NewAccesses);
+
+ /// Helper to determine if @p Inst can be synthesized in @p Stmt.
+ ///
+ /// @returns false, iff @p Inst can be synthesized in @p Stmt.
+ bool canSyntheziseInStmt(ScopStmt &Stmt, Instruction *Inst);
+
+ /// Remove dead instructions generated for BB
+ ///
+ /// @param BB The basic block code for which code has been generated.
+ /// @param BBMap A local map from old to new instructions.
+ void removeDeadInstructions(BasicBlock *BB, ValueMapT &BBMap);
+
+ /// Invalidate the scalar evolution expressions for a scop.
+ ///
+ /// This function invalidates the scalar evolution results for all
+ /// instructions that are part of a given scop, and the loops
+ /// surrounding the users of merge blocks. This is necessary to ensure that
+ /// later scops do not obtain scalar evolution expressions that reference
+ /// values that earlier dominated the later scop, but have been moved in the
+ /// conditional part of an earlier scop and consequently do not any more
+ /// dominate the later scop.
+ ///
+ /// @param S The scop to invalidate.
+ void invalidateScalarEvolution(Scop &S);
+};
+
+/// Generate a new vector basic block for a polyhedral statement.
+///
+/// The only public function exposed is generate().
+class VectorBlockGenerator : BlockGenerator {
+public:
+ /// Generate a new vector basic block for a ScoPStmt.
+ ///
+ /// This code generation is similar to the normal, scalar code generation,
+ /// except that each instruction is code generated for several vector lanes
+ /// at a time. If possible instructions are issued as actual vector
+ /// instructions, but e.g. for address calculation instructions we currently
+ /// generate scalar instructions for each vector lane.
+ ///
+ /// @param BlockGen A block generator object used as parent.
+ /// @param Stmt The statement to code generate.
+ /// @param VLTS A mapping from loops virtual canonical induction
+ /// variable to their new values
+ /// (for values recalculated in the new ScoP, but not
+ /// within this basic block), one for each lane.
+ /// @param Schedule A map from the statement to a schedule where the
+ /// innermost dimension is the dimension of the innermost
+ /// loop containing the statement.
+ /// @param NewAccesses A map from memory access ids to new ast expressions,
+ /// which may contain new access expressions for certain
+ /// memory accesses.
+ static void generate(BlockGenerator &BlockGen, ScopStmt &Stmt,
+ std::vector<LoopToScevMapT> &VLTS,
+ __isl_keep isl_map *Schedule,
+ __isl_keep isl_id_to_ast_expr *NewAccesses) {
+ VectorBlockGenerator Generator(BlockGen, VLTS, Schedule);
+ Generator.copyStmt(Stmt, NewAccesses);
+ }
+
+private:
+ // This is a vector of loop->scev maps. The first map is used for the first
+ // vector lane, ...
+ // Each map, contains information about Instructions in the old ScoP, which
+ // are recalculated in the new SCoP. When copying the basic block, we replace
+ // all references to the old instructions with their recalculated values.
+ //
+ // For example, when the code generator produces this AST:
+ //
+ // for (int c1 = 0; c1 <= 1023; c1 += 1)
+ // for (int c2 = 0; c2 <= 1023; c2 += VF)
+ // for (int lane = 0; lane <= VF; lane += 1)
+ // Stmt(c2 + lane + 3, c1);
+ //
+ // VLTS[lane] contains a map:
+ // "outer loop in the old loop nest" -> SCEV("c2 + lane + 3"),
+ // "inner loop in the old loop nest" -> SCEV("c1").
+ std::vector<LoopToScevMapT> &VLTS;
+
+ // A map from the statement to a schedule where the innermost dimension is the
+ // dimension of the innermost loop containing the statement.
+ isl_map *Schedule;
+
+ VectorBlockGenerator(BlockGenerator &BlockGen,
+ std::vector<LoopToScevMapT> &VLTS,
+ __isl_keep isl_map *Schedule);
+
+ int getVectorWidth();
+
+ Value *getVectorValue(ScopStmt &Stmt, Value *Old, ValueMapT &VectorMap,
+ VectorValueMapT &ScalarMaps, Loop *L);
+
+ Type *getVectorPtrTy(const Value *V, int Width);
+
+ /// Load a vector from a set of adjacent scalars
+ ///
+ /// In case a set of scalars is known to be next to each other in memory,
+ /// create a vector load that loads those scalars
+ ///
+ /// %vector_ptr= bitcast double* %p to <4 x double>*
+ /// %vec_full = load <4 x double>* %vector_ptr
+ ///
+ /// @param Stmt The statement to code generate.
+ /// @param NegativeStride This is used to indicate a -1 stride. In such
+ /// a case we load the end of a base address and
+ /// shuffle the accesses in reverse order into the
+ /// vector. By default we would do only positive
+ /// strides.
+ ///
+ /// @param NewAccesses A map from memory access ids to new ast
+ /// expressions, which may contain new access
+ /// expressions for certain memory accesses.
+ Value *generateStrideOneLoad(ScopStmt &Stmt, LoadInst *Load,
+ VectorValueMapT &ScalarMaps,
+ __isl_keep isl_id_to_ast_expr *NewAccesses,
+ bool NegativeStride);
+
+ /// Load a vector initialized from a single scalar in memory
+ ///
+ /// In case all elements of a vector are initialized to the same
+ /// scalar value, this value is loaded and shuffled into all elements
+ /// of the vector.
+ ///
+ /// %splat_one = load <1 x double>* %p
+ /// %splat = shufflevector <1 x double> %splat_one, <1 x
+ /// double> %splat_one, <4 x i32> zeroinitializer
+ ///
+ /// @param NewAccesses A map from memory access ids to new ast expressions,
+ /// which may contain new access expressions for certain
+ /// memory accesses.
+ Value *generateStrideZeroLoad(ScopStmt &Stmt, LoadInst *Load,
+ ValueMapT &BBMap,
+ __isl_keep isl_id_to_ast_expr *NewAccesses);
+
+ /// Load a vector from scalars distributed in memory
+ ///
+ /// In case some scalars a distributed randomly in memory. Create a vector
+ /// by loading each scalar and by inserting one after the other into the
+ /// vector.
+ ///
+ /// %scalar_1= load double* %p_1
+ /// %vec_1 = insertelement <2 x double> undef, double %scalar_1, i32 0
+ /// %scalar 2 = load double* %p_2
+ /// %vec_2 = insertelement <2 x double> %vec_1, double %scalar_1, i32 1
+ ///
+ /// @param NewAccesses A map from memory access ids to new ast expressions,
+ /// which may contain new access expressions for certain
+ /// memory accesses.
+ Value *generateUnknownStrideLoad(ScopStmt &Stmt, LoadInst *Load,
+ VectorValueMapT &ScalarMaps,
+ __isl_keep isl_id_to_ast_expr *NewAccesses);
+
+ /// @param NewAccesses A map from memory access ids to new ast expressions,
+ /// which may contain new access expressions for certain
+ /// memory accesses.
+ void generateLoad(ScopStmt &Stmt, LoadInst *Load, ValueMapT &VectorMap,
+ VectorValueMapT &ScalarMaps,
+ __isl_keep isl_id_to_ast_expr *NewAccesses);
+
+ void copyUnaryInst(ScopStmt &Stmt, UnaryInstruction *Inst,
+ ValueMapT &VectorMap, VectorValueMapT &ScalarMaps);
+
+ void copyBinaryInst(ScopStmt &Stmt, BinaryOperator *Inst,
+ ValueMapT &VectorMap, VectorValueMapT &ScalarMaps);
+
+ /// @param NewAccesses A map from memory access ids to new ast expressions,
+ /// which may contain new access expressions for certain
+ /// memory accesses.
+ void copyStore(ScopStmt &Stmt, StoreInst *Store, ValueMapT &VectorMap,
+ VectorValueMapT &ScalarMaps,
+ __isl_keep isl_id_to_ast_expr *NewAccesses);
+
+ /// @param NewAccesses A map from memory access ids to new ast expressions,
+ /// which may contain new access expressions for certain
+ /// memory accesses.
+ void copyInstScalarized(ScopStmt &Stmt, Instruction *Inst,
+ ValueMapT &VectorMap, VectorValueMapT &ScalarMaps,
+ __isl_keep isl_id_to_ast_expr *NewAccesses);
+
+ bool extractScalarValues(const Instruction *Inst, ValueMapT &VectorMap,
+ VectorValueMapT &ScalarMaps);
+
+ bool hasVectorOperands(const Instruction *Inst, ValueMapT &VectorMap);
+
+ /// Generate vector loads for scalars.
+ ///
+ /// @param Stmt The scop statement for which to generate the loads.
+ /// @param VectorBlockMap A map that will be updated to relate the original
+ /// values with the newly generated vector loads.
+ void generateScalarVectorLoads(ScopStmt &Stmt, ValueMapT &VectorBlockMap);
+
+ /// Verify absence of scalar stores.
+ ///
+ /// @param Stmt The scop statement to check for scalar stores.
+ void verifyNoScalarStores(ScopStmt &Stmt);
+
+ /// @param NewAccesses A map from memory access ids to new ast expressions,
+ /// which may contain new access expressions for certain
+ /// memory accesses.
+ void copyInstruction(ScopStmt &Stmt, Instruction *Inst, ValueMapT &VectorMap,
+ VectorValueMapT &ScalarMaps,
+ __isl_keep isl_id_to_ast_expr *NewAccesses);
+
+ /// @param NewAccesses A map from memory access ids to new ast expressions,
+ /// which may contain new access expressions for certain
+ /// memory accesses.
+ void copyStmt(ScopStmt &Stmt, __isl_keep isl_id_to_ast_expr *NewAccesses);
+};
+
+/// Generator for new versions of polyhedral region statements.
+class RegionGenerator : public BlockGenerator {
+public:
+ /// Create a generator for regions.
+ ///
+ /// @param BlockGen A generator for basic blocks.
+ RegionGenerator(BlockGenerator &BlockGen) : BlockGenerator(BlockGen) {}
+
+ virtual ~RegionGenerator() {}
+
+ /// Copy the region statement @p Stmt.
+ ///
+ /// This copies the entire region represented by @p Stmt and updates
+ /// references to old values with references to new values, as defined by
+ /// GlobalMap.
+ ///
+ /// @param Stmt The statement to code generate.
+ /// @param LTS A map from old loops to new induction variables as SCEVs.
+ void copyStmt(ScopStmt &Stmt, LoopToScevMapT <S,
+ __isl_keep isl_id_to_ast_expr *IdToAstExp);
+
+private:
+ /// A map from old to the first new block in the region, that was created to
+ /// model the old basic block.
+ DenseMap<BasicBlock *, BasicBlock *> StartBlockMap;
+
+ /// A map from old to the last new block in the region, that was created to
+ /// model the old basic block.
+ DenseMap<BasicBlock *, BasicBlock *> EndBlockMap;
+
+ /// The "BBMaps" for the whole region (one for each block). In case a basic
+ /// block is code generated to multiple basic blocks (e.g., for partial
+ /// writes), the StartBasic is used as index for the RegionMap.
+ DenseMap<BasicBlock *, ValueMapT> RegionMaps;
+
+ /// Mapping to remember PHI nodes that still need incoming values.
+ using PHINodePairTy = std::pair<PHINode *, PHINode *>;
+ DenseMap<BasicBlock *, SmallVector<PHINodePairTy, 4>> IncompletePHINodeMap;
+
+ /// Repair the dominance tree after we created a copy block for @p BB.
+ ///
+ /// @returns The immediate dominator in the DT for @p BBCopy if in the region.
+ BasicBlock *repairDominance(BasicBlock *BB, BasicBlock *BBCopy);
+
+ /// Add the new operand from the copy of @p IncomingBB to @p PHICopy.
+ ///
+ /// PHI nodes, which may have (multiple) edges that enter from outside the
+ /// non-affine subregion and even from outside the scop, are code generated as
+ /// follows:
+ ///
+ /// # Original
+ ///
+ /// Region: %A-> %exit
+ /// NonAffine Stmt: %nonaffB -> %D (includes %nonaffB, %nonaffC)
+ ///
+ /// pre:
+ /// %val = add i64 1, 1
+ ///
+ /// A:
+ /// br label %nonaff
+ ///
+ /// nonaffB:
+ /// %phi = phi i64 [%val, %A], [%valC, %nonAffC], [%valD, %D]
+ /// %cmp = <nonaff>
+ /// br i1 %cmp, label %C, label %nonaffC
+ ///
+ /// nonaffC:
+ /// %valC = add i64 1, 1
+ /// br i1 undef, label %D, label %nonaffB
+ ///
+ /// D:
+ /// %valD = ...
+ /// %exit_cond = <loopexit>
+ /// br i1 %exit_cond, label %nonaffB, label %exit
+ ///
+ /// exit:
+ /// ...
+ ///
+ /// - %start and %C enter from outside the non-affine region.
+ /// - %nonaffC enters from within the non-affine region.
+ ///
+ /// # New
+ ///
+ /// polly.A:
+ /// store i64 %val, i64* %phi.phiops
+ /// br label %polly.nonaffA.entry
+ ///
+ /// polly.nonaffB.entry:
+ /// %phi.phiops.reload = load i64, i64* %phi.phiops
+ /// br label %nonaffB
+ ///
+ /// polly.nonaffB:
+ /// %polly.phi = [%phi.phiops.reload, %nonaffB.entry],
+ /// [%p.valC, %polly.nonaffC]
+ ///
+ /// polly.nonaffC:
+ /// %p.valC = add i64 1, 1
+ /// br i1 undef, label %polly.D, label %polly.nonaffB
+ ///
+ /// polly.D:
+ /// %p.valD = ...
+ /// store i64 %p.valD, i64* %phi.phiops
+ /// %p.exit_cond = <loopexit>
+ /// br i1 %p.exit_cond, label %polly.nonaffB, label %exit
+ ///
+ /// Values that enter the PHI from outside the non-affine region are stored
+ /// into the stack slot %phi.phiops by statements %polly.A and %polly.D and
+ /// reloaded in %polly.nonaffB.entry, a basic block generated before the
+ /// actual non-affine region.
+ ///
+ /// When generating the PHI node of the non-affine region in %polly.nonaffB,
+ /// incoming edges from outside the region are combined into a single branch
+ /// from %polly.nonaffB.entry which has as incoming value the value reloaded
+ /// from the %phi.phiops stack slot. Incoming edges from within the region
+ /// refer to the copied instructions (%p.valC) and basic blocks
+ /// (%polly.nonaffC) of the non-affine region.
+ ///
+ /// @param Stmt The statement to code generate.
+ /// @param PHI The original PHI we copy.
+ /// @param PHICopy The copy of @p PHI.
+ /// @param IncomingBB An incoming block of @p PHI.
+ /// @param LTS A map from old loops to new induction variables as
+ /// SCEVs.
+ void addOperandToPHI(ScopStmt &Stmt, PHINode *PHI, PHINode *PHICopy,
+ BasicBlock *IncomingBB, LoopToScevMapT <S);
+
+ /// Create a PHI that combines the incoming values from all incoming blocks
+ /// that are in the subregion.
+ ///
+ /// PHIs in the subregion's exit block can have incoming edges from within and
+ /// outside the subregion. This function combines the incoming values from
+ /// within the subregion to appear as if there is only one incoming edge from
+ /// the subregion (an additional exit block is created by RegionGenerator).
+ /// This is to avoid that a value is written to the .phiops location without
+ /// leaving the subregion because the exiting block as an edge back into the
+ /// subregion.
+ ///
+ /// @param MA The WRITE of MemoryKind::PHI/MemoryKind::ExitPHI for a PHI in
+ /// the subregion's exit block.
+ /// @param LTS Virtual induction variable mapping.
+ /// @param BBMap A mapping from old values to their new values in this block.
+ /// @param L Loop surrounding this region statement.
+ ///
+ /// @returns The constructed PHI node.
+ PHINode *buildExitPHI(MemoryAccess *MA, LoopToScevMapT <S, ValueMapT &BBMap,
+ Loop *L);
+
+ /// @param Return the new value of a scalar write, creating a PHINode if
+ /// necessary.
+ ///
+ /// @param MA A scalar WRITE MemoryAccess.
+ /// @param LTS Virtual induction variable mapping.
+ /// @param BBMap A mapping from old values to their new values in this block.
+ ///
+ /// @returns The effective value of @p MA's written value when leaving the
+ /// subregion.
+ /// @see buildExitPHI
+ Value *getExitScalar(MemoryAccess *MA, LoopToScevMapT <S, ValueMapT &BBMap);
+
+ /// Generate the scalar stores for the given statement.
+ ///
+ /// After the statement @p Stmt was copied all inner-SCoP scalar dependences
+ /// starting in @p Stmt (hence all scalar write accesses in @p Stmt) need to
+ /// be demoted to memory.
+ ///
+ /// @param Stmt The statement we generate code for.
+ /// @param LTS A mapping from loops virtual canonical induction variable to
+ /// their new values (for values recalculated in the new ScoP,
+ /// but not within this basic block)
+ /// @param BBMap A mapping from old values to their new values in this block.
+ /// @param LTS A mapping from loops virtual canonical induction variable to
+ /// their new values.
+ virtual void
+ generateScalarStores(ScopStmt &Stmt, LoopToScevMapT <S, ValueMapT &BBMAp,
+ __isl_keep isl_id_to_ast_expr *NewAccesses) override;
+
+ /// Copy a single PHI instruction.
+ ///
+ /// This copies a single PHI instruction and updates references to old values
+ /// with references to new values, as defined by GlobalMap and BBMap.
+ ///
+ /// @param Stmt The statement to code generate.
+ /// @param PHI The PHI instruction to copy.
+ /// @param BBMap A mapping from old values to their new values
+ /// (for values recalculated within this basic block).
+ /// @param LTS A map from old loops to new induction variables as SCEVs.
+ virtual void copyPHIInstruction(ScopStmt &Stmt, PHINode *Inst,
+ ValueMapT &BBMap,
+ LoopToScevMapT <S) override;
+};
+} // namespace polly
+#endif