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 29 /// Helper class to annotate newly generated SCoPs with metadata. 30 /// 31 /// The annotations are twofold: 32 /// 1) Loops are stored in a stack-like structure in the order they are 33 /// constructed and the LoopID metadata node is added to the backedge. 34 /// Contained memory instructions and loop headers are annotated according 35 /// to all parallel surrounding loops. 36 /// 2) The new SCoP is assumed alias free (either due to the result of 37 /// AliasAnalysis queries or runtime alias checks). We annotate therefore 38 /// all memory instruction with alias scopes to indicate that fact to 39 /// later optimizations. 40 /// These alias scopes live in a new alias domain only used in this SCoP. 41 /// Each base pointer has its own alias scope and is annotated to not 42 /// alias with any access to different base pointers. 43 class ScopAnnotator { 44 public: 45 ScopAnnotator(); 46 47 /// Build all alias scopes for the given SCoP. 48 void buildAliasScopes(Scop &S); 49 50 /// Add a new loop @p L which is parallel if @p IsParallel is true. 51 void pushLoop(llvm::Loop *L, bool IsParallel); 52 53 /// Remove the last added loop. 54 void popLoop(bool isParallel); 55 56 /// Annotate the new instruction @p I for all parallel loops. 57 void annotate(llvm::Instruction *I); 58 59 /// Annotate the loop latch @p B wrt. @p L. 60 void annotateLoopLatch(llvm::BranchInst *B, llvm::Loop *L, bool IsParallel, 61 bool IsLoopVectorizerDisabled) const; 62 63 /// Add alternative alias based pointers 64 /// 65 /// When annotating instructions with alias scope metadata, the right metadata 66 /// is identified through the base pointer of the memory access. In some cases 67 /// (e.g. OpenMP code generation), the base pointer of the memory accesses is 68 /// not the original base pointer, but was changed when passing the original 69 /// base pointer over a function boundary. This function allows to provide a 70 /// map that maps from these new base pointers to the original base pointers 71 /// to allow the ScopAnnotator to still find the right alias scop annotations. 72 /// 73 /// @param NewMap A map from new base pointers to original base pointers. addAlternativeAliasBases(llvm::DenseMap<llvm::AssertingVH<llvm::Value>,llvm::AssertingVH<llvm::Value>> & NewMap)74 void addAlternativeAliasBases( 75 llvm::DenseMap<llvm::AssertingVH<llvm::Value>, 76 llvm::AssertingVH<llvm::Value>> &NewMap) { 77 AlternativeAliasBases.insert(NewMap.begin(), NewMap.end()); 78 } 79 80 /// Delete the set of alternative alias bases resetAlternativeAliasBases()81 void resetAlternativeAliasBases() { AlternativeAliasBases.clear(); } 82 83 /// Add inter iteration alias-free base pointer @p BasePtr. 84 void addInterIterationAliasFreeBasePtr(llvm::Value *BasePtr); 85 86 private: 87 /// Annotate with the second level alias metadata 88 /// 89 /// Annotate the instruction @p I with the second level alias metadata 90 /// to distinguish the individual non-aliasing accesses that have inter 91 /// iteration alias-free base pointers. 92 /// 93 /// @param I The instruction to be annotated. 94 /// @param BasePtr The base pointer of @p I. 95 void annotateSecondLevel(llvm::Instruction *I, llvm::Value *BasePtr); 96 97 /// The ScalarEvolution analysis we use to find base pointers. 98 llvm::ScalarEvolution *SE; 99 100 /// All loops currently under construction. 101 llvm::SmallVector<llvm::Loop *, 8> ActiveLoops; 102 103 /// Metadata pointing to parallel loops currently under construction. 104 llvm::SmallVector<llvm::MDNode *, 8> ParallelLoops; 105 106 /// The alias scope domain for the current SCoP. 107 llvm::MDNode *AliasScopeDomain; 108 109 /// A map from base pointers to its alias scope. 110 llvm::MapVector<llvm::AssertingVH<llvm::Value>, llvm::MDNode *> AliasScopeMap; 111 112 /// A map from base pointers to an alias scope list of other pointers. 113 llvm::DenseMap<llvm::AssertingVH<llvm::Value>, llvm::MDNode *> 114 OtherAliasScopeListMap; 115 116 /// A map from pointers to second level alias scopes. 117 llvm::DenseMap<const llvm::SCEV *, llvm::MDNode *> SecondLevelAliasScopeMap; 118 119 /// A map from pointers to second level alias scope list of other pointers. 120 llvm::DenseMap<const llvm::SCEV *, llvm::MDNode *> 121 SecondLevelOtherAliasScopeListMap; 122 123 /// Inter iteration alias-free base pointers. 124 llvm::SmallPtrSet<llvm::Value *, 4> InterIterationAliasFreeBasePtrs; 125 126 llvm::DenseMap<llvm::AssertingVH<llvm::Value>, llvm::AssertingVH<llvm::Value>> 127 AlternativeAliasBases; 128 }; 129 130 /// Add Polly specifics when running IRBuilder. 131 /// 132 /// This is used to add additional items such as e.g. the llvm.loop.parallel 133 /// metadata. 134 class IRInserter final : public llvm::IRBuilderDefaultInserter { 135 public: 136 IRInserter() = default; IRInserter(class ScopAnnotator & A)137 IRInserter(class ScopAnnotator &A) : Annotator(&A) {} 138 InsertHelper(llvm::Instruction * I,const llvm::Twine & Name,llvm::BasicBlock * BB,llvm::BasicBlock::iterator InsertPt)139 void InsertHelper(llvm::Instruction *I, const llvm::Twine &Name, 140 llvm::BasicBlock *BB, 141 llvm::BasicBlock::iterator InsertPt) const override { 142 llvm::IRBuilderDefaultInserter::InsertHelper(I, Name, BB, InsertPt); 143 if (Annotator) 144 Annotator->annotate(I); 145 } 146 147 private: 148 class ScopAnnotator *Annotator = nullptr; 149 }; 150 151 // TODO: We should not name instructions in NDEBUG builds. 152 // 153 // We currently always name instructions, as the polly test suite currently 154 // matches for certain names. 155 typedef llvm::IRBuilder<llvm::ConstantFolder, IRInserter> PollyIRBuilder; 156 157 } // namespace polly 158 #endif 159