1 //===- Codegen/IRBuilder.h - The IR builder used by Polly -*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // The Polly IRBuilder file contains Polly specific extensions for the IRBuilder 10 // that are used e.g. to emit the llvm.loop.parallel metadata. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef POLLY_CODEGEN_IRBUILDER_H 15 #define POLLY_CODEGEN_IRBUILDER_H 16 17 #include "llvm/ADT/MapVector.h" 18 #include "llvm/IR/IRBuilder.h" 19 20 namespace llvm { 21 class Loop; 22 class SCEV; 23 class ScalarEvolution; 24 } // namespace llvm 25 26 namespace polly { 27 class Scop; 28 struct BandAttr; 29 30 /// Helper class to annotate newly generated SCoPs with metadata. 31 /// 32 /// The annotations are twofold: 33 /// 1) Loops are stored in a stack-like structure in the order they are 34 /// constructed and the LoopID metadata node is added to the backedge. 35 /// Contained memory instructions and loop headers are annotated according 36 /// to all parallel surrounding loops. 37 /// 2) The new SCoP is assumed alias free (either due to the result of 38 /// AliasAnalysis queries or runtime alias checks). We annotate therefore 39 /// all memory instruction with alias scopes to indicate that fact to 40 /// later optimizations. 41 /// These alias scopes live in a new alias domain only used in this SCoP. 42 /// Each base pointer has its own alias scope and is annotated to not 43 /// alias with any access to different base pointers. 44 class ScopAnnotator { 45 public: 46 ScopAnnotator(); 47 ~ScopAnnotator(); 48 49 /// Build all alias scopes for the given SCoP. 50 void buildAliasScopes(Scop &S); 51 52 /// Add a new loop @p L which is parallel if @p IsParallel is true. 53 void pushLoop(llvm::Loop *L, bool IsParallel); 54 55 /// Remove the last added loop. 56 void popLoop(bool isParallel); 57 58 /// Annotate the new instruction @p I for all parallel loops. 59 void annotate(llvm::Instruction *I); 60 61 /// Annotate the loop latch @p B wrt. @p L. 62 void annotateLoopLatch(llvm::BranchInst *B, llvm::Loop *L, bool IsParallel, 63 bool IsLoopVectorizerDisabled) const; 64 65 /// Add alternative alias based pointers 66 /// 67 /// When annotating instructions with alias scope metadata, the right metadata 68 /// is identified through the base pointer of the memory access. In some cases 69 /// (e.g. OpenMP code generation), the base pointer of the memory accesses is 70 /// not the original base pointer, but was changed when passing the original 71 /// base pointer over a function boundary. This function allows to provide a 72 /// map that maps from these new base pointers to the original base pointers 73 /// to allow the ScopAnnotator to still find the right alias scop annotations. 74 /// 75 /// @param NewMap A map from new base pointers to original base pointers. addAlternativeAliasBases(llvm::DenseMap<llvm::AssertingVH<llvm::Value>,llvm::AssertingVH<llvm::Value>> & NewMap)76 void addAlternativeAliasBases( 77 llvm::DenseMap<llvm::AssertingVH<llvm::Value>, 78 llvm::AssertingVH<llvm::Value>> &NewMap) { 79 AlternativeAliasBases.insert(NewMap.begin(), NewMap.end()); 80 } 81 82 /// Delete the set of alternative alias bases resetAlternativeAliasBases()83 void resetAlternativeAliasBases() { AlternativeAliasBases.clear(); } 84 85 /// Stack for surrounding BandAttr annotations. 86 llvm::SmallVector<BandAttr *, 8> LoopAttrEnv; getStagingAttrEnv()87 BandAttr *&getStagingAttrEnv() { return LoopAttrEnv.back(); } getActiveAttrEnv()88 BandAttr *getActiveAttrEnv() const { 89 return LoopAttrEnv[LoopAttrEnv.size() - 2]; 90 } 91 92 private: 93 /// The ScalarEvolution analysis we use to find base pointers. 94 llvm::ScalarEvolution *SE; 95 96 /// All loops currently under construction. 97 llvm::SmallVector<llvm::Loop *, 8> ActiveLoops; 98 99 /// Access groups for the parallel loops currently under construction. 100 llvm::SmallVector<llvm::MDNode *, 8> ParallelLoops; 101 102 /// The alias scope domain for the current SCoP. 103 llvm::MDNode *AliasScopeDomain; 104 105 /// A map from base pointers to its alias scope. 106 llvm::MapVector<llvm::AssertingVH<llvm::Value>, llvm::MDNode *> AliasScopeMap; 107 108 /// A map from base pointers to an alias scope list of other pointers. 109 llvm::DenseMap<llvm::AssertingVH<llvm::Value>, llvm::MDNode *> 110 OtherAliasScopeListMap; 111 112 llvm::DenseMap<llvm::AssertingVH<llvm::Value>, llvm::AssertingVH<llvm::Value>> 113 AlternativeAliasBases; 114 }; 115 116 /// Add Polly specifics when running IRBuilder. 117 /// 118 /// This is used to add additional items such as e.g. the llvm.loop.parallel 119 /// metadata. 120 class IRInserter final : public llvm::IRBuilderDefaultInserter { 121 public: 122 IRInserter() = default; IRInserter(ScopAnnotator & A)123 IRInserter(ScopAnnotator &A) : Annotator(&A) {} 124 InsertHelper(llvm::Instruction * I,const llvm::Twine & Name,llvm::BasicBlock * BB,llvm::BasicBlock::iterator InsertPt)125 void InsertHelper(llvm::Instruction *I, const llvm::Twine &Name, 126 llvm::BasicBlock *BB, 127 llvm::BasicBlock::iterator InsertPt) const override { 128 llvm::IRBuilderDefaultInserter::InsertHelper(I, Name, BB, InsertPt); 129 if (Annotator) 130 Annotator->annotate(I); 131 } 132 133 private: 134 ScopAnnotator *Annotator = nullptr; 135 }; 136 137 // TODO: We should not name instructions in NDEBUG builds. 138 // 139 // We currently always name instructions, as the polly test suite currently 140 // matches for certain names. 141 typedef llvm::IRBuilder<llvm::ConstantFolder, IRInserter> PollyIRBuilder; 142 143 } // namespace polly 144 #endif 145