1 //===------ ZoneAlgo.h ------------------------------------------*- 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 // Derive information about array elements between statements ("Zones"). 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef POLLY_ZONEALGO_H 14 #define POLLY_ZONEALGO_H 15 16 #include "llvm/ADT/DenseMap.h" 17 #include "llvm/ADT/DenseSet.h" 18 #include "llvm/ADT/SmallPtrSet.h" 19 #include "isl/isl-noexceptions.h" 20 #include <memory> 21 22 namespace llvm { 23 class Value; 24 class LoopInfo; 25 class Loop; 26 class PHINode; 27 class raw_ostream; 28 } // namespace llvm 29 30 namespace polly { 31 class Scop; 32 class ScopStmt; 33 class MemoryAccess; 34 class ScopArrayInfo; 35 36 /// Return only the mappings that map to known values. 37 /// 38 /// @param UMap { [] -> ValInst[] } 39 /// 40 /// @return { [] -> ValInst[] } 41 isl::union_map filterKnownValInst(const isl::union_map &UMap); 42 43 /// Base class for algorithms based on zones, like DeLICM. 44 class ZoneAlgorithm { 45 protected: 46 /// The name of the pass this is used from. Used for optimization remarks. 47 const char *PassName; 48 49 /// Hold a reference to the isl_ctx to avoid it being freed before we released 50 /// all of the isl objects. 51 /// 52 /// This must be declared before any other member that holds an isl object. 53 /// This guarantees that the shared_ptr and its isl_ctx is destructed last, 54 /// after all other members free'd the isl objects they were holding. 55 std::shared_ptr<isl_ctx> IslCtx; 56 57 /// Cached reaching definitions for each ScopStmt. 58 /// 59 /// Use getScalarReachingDefinition() to get its contents. 60 llvm::DenseMap<ScopStmt *, isl::map> ScalarReachDefZone; 61 62 /// The analyzed Scop. 63 Scop *S; 64 65 /// LoopInfo analysis used to determine whether values are synthesizable. 66 llvm::LoopInfo *LI; 67 68 /// Parameter space that does not need realignment. 69 isl::space ParamSpace; 70 71 /// Space the schedule maps to. 72 isl::space ScatterSpace; 73 74 /// Cached version of the schedule and domains. 75 isl::union_map Schedule; 76 77 /// Combined access relations of all MemoryKind::Array READ accesses. 78 /// { DomainRead[] -> Element[] } 79 isl::union_map AllReads; 80 81 /// The loaded values (llvm::LoadInst) of all reads. 82 /// { [Element[] -> DomainRead[]] -> ValInst[] } 83 isl::union_map AllReadValInst; 84 85 /// Combined access relations of all MemoryKind::Array, MAY_WRITE accesses. 86 /// { DomainMayWrite[] -> Element[] } 87 isl::union_map AllMayWrites; 88 89 /// Combined access relations of all MemoryKind::Array, MUST_WRITE accesses. 90 /// { DomainMustWrite[] -> Element[] } 91 isl::union_map AllMustWrites; 92 93 /// Combined access relations of all MK_Array write accesses (union of 94 /// AllMayWrites and AllMustWrites). 95 /// { DomainWrite[] -> Element[] } 96 isl::union_map AllWrites; 97 98 /// The value instances written to array elements of all write accesses. 99 /// { [Element[] -> DomainWrite[]] -> ValInst[] } 100 isl::union_map AllWriteValInst; 101 102 /// All reaching definitions for MemoryKind::Array writes. 103 /// { [Element[] -> Zone[]] -> DomainWrite[] } 104 isl::union_map WriteReachDefZone; 105 106 /// Map llvm::Values to an isl identifier. 107 /// Used with -polly-use-llvm-names=false as an alternative method to get 108 /// unique ids that do not depend on pointer values. 109 llvm::DenseMap<llvm::Value *, isl::id> ValueIds; 110 111 /// Set of array elements that can be reliably used for zone analysis. 112 /// { Element[] } 113 isl::union_set CompatibleElts; 114 115 /// List of PHIs that may transitively refer to themselves. 116 /// 117 /// Computing them would require a polyhedral transitive closure operation, 118 /// for which isl may only return an approximation. For correctness, we always 119 /// require an exact result. Hence, we exclude such PHIs. 120 llvm::SmallPtrSet<llvm::PHINode *, 4> RecursivePHIs; 121 122 /// PHIs that have been computed. 123 /// 124 /// Computed PHIs are replaced by their incoming values using #NormalizeMap. 125 llvm::DenseSet<llvm::PHINode *> ComputedPHIs; 126 127 /// For computed PHIs, contains the ValInst they stand for. 128 /// 129 /// To show an example, assume the following PHINode: 130 /// 131 /// Stmt: 132 /// %phi = phi double [%val1, %bb1], [%val2, %bb2] 133 /// 134 /// It's ValInst is: 135 /// 136 /// { [Stmt[i] -> phi[]] } 137 /// 138 /// The value %phi will be either %val1 or %val2, depending on whether in 139 /// iteration i %bb1 or %bb2 has been executed before. In SCoPs, this can be 140 /// determined at compile-time, and the result stored in #NormalizeMap. For 141 /// the previous example, it could be: 142 /// 143 /// { [Stmt[i] -> phi[]] -> [Stmt[0] -> val1[]]; 144 /// [Stmt[i] -> phi[]] -> [Stmt[i] -> val2[]] : i > 0 } 145 /// 146 /// Only ValInsts in #ComputedPHIs are present in this map. Other values are 147 /// assumed to represent themselves. This is to avoid adding lots of identity 148 /// entries to this map. 149 /// 150 /// { PHIValInst[] -> IncomingValInst[] } 151 isl::union_map NormalizeMap; 152 153 /// Cache for computePerPHI(const ScopArrayInfo *) 154 llvm::SmallDenseMap<llvm::PHINode *, isl::union_map> PerPHIMaps; 155 156 /// A cache for getDefToTarget(). 157 llvm::DenseMap<std::pair<ScopStmt *, ScopStmt *>, isl::map> DefToTargetCache; 158 159 /// Prepare the object before computing the zones of @p S. 160 /// 161 /// @param PassName Name of the pass using this analysis. 162 /// @param S The SCoP to process. 163 /// @param LI LoopInfo analysis used to determine synthesizable values. 164 ZoneAlgorithm(const char *PassName, Scop *S, llvm::LoopInfo *LI); 165 166 private: 167 /// Find the array elements that violate the zone analysis assumptions. 168 /// 169 /// What violates our assumptions: 170 /// - A load after a write of the same location; we assume that all reads 171 /// occur before the writes. 172 /// - Two writes to the same location; we cannot model the order in which 173 /// these occur. 174 /// 175 /// Scalar reads implicitly always occur before other accesses therefore never 176 /// violate the first condition. There is also at most one write to a scalar, 177 /// satisfying the second condition. 178 /// 179 /// @param Stmt The statement to be analyzed. 180 /// @param[out] IncompatibleElts Receives the elements that are not 181 /// zone-analysis compatible. 182 /// @param[out] AllElts receives all encountered elements. 183 void collectIncompatibleElts(ScopStmt *Stmt, isl::union_set &IncompatibleElts, 184 isl::union_set &AllElts); 185 186 void addArrayReadAccess(MemoryAccess *MA); 187 188 /// Return the ValInst write by a (must-)write access. Returns the 'unknown' 189 /// ValInst if there is no single ValInst[] the array element written to will 190 /// have. 191 /// 192 /// @return { ValInst[] } 193 isl::union_map getWrittenValue(MemoryAccess *MA, isl::map AccRel); 194 195 void addArrayWriteAccess(MemoryAccess *MA); 196 197 /// For an llvm::Value defined in @p DefStmt, compute the RAW dependency for a 198 /// use in every instance of @p UseStmt. 199 /// 200 /// @param UseStmt Statement a scalar is used in. 201 /// @param DefStmt Statement a scalar is defined in. 202 /// 203 /// @return { DomainUse[] -> DomainDef[] } 204 isl::map computeUseToDefFlowDependency(ScopStmt *UseStmt, ScopStmt *DefStmt); 205 206 protected: 207 isl::union_set makeEmptyUnionSet() const; 208 209 isl::union_map makeEmptyUnionMap() const; 210 211 /// For each 'execution' of a PHINode, get the incoming block that was 212 /// executed before. 213 /// 214 /// For each PHI instance we can directly determine which was the incoming 215 /// block, and hence derive which value the PHI has. 216 /// 217 /// @param SAI The ScopArrayInfo representing the PHI's storage. 218 /// 219 /// @return { DomainPHIRead[] -> DomainPHIWrite[] } 220 isl::union_map computePerPHI(const polly::ScopArrayInfo *SAI); 221 222 /// Find the array elements that can be used for zone analysis. 223 void collectCompatibleElts(); 224 225 /// Get the schedule for @p Stmt. 226 /// 227 /// The domain of the result is as narrow as possible. 228 isl::map getScatterFor(ScopStmt *Stmt) const; 229 230 /// Get the schedule of @p MA's parent statement. 231 isl::map getScatterFor(MemoryAccess *MA) const; 232 233 /// Get the schedule for the statement instances of @p Domain. 234 isl::union_map getScatterFor(isl::union_set Domain) const; 235 236 /// Get the schedule for the statement instances of @p Domain. 237 isl::map getScatterFor(isl::set Domain) const; 238 239 /// Get the domain of @p Stmt. 240 isl::set getDomainFor(ScopStmt *Stmt) const; 241 242 /// Get the domain @p MA's parent statement. 243 isl::set getDomainFor(MemoryAccess *MA) const; 244 245 /// Get the access relation of @p MA. 246 /// 247 /// The domain of the result is as narrow as possible. 248 isl::map getAccessRelationFor(MemoryAccess *MA) const; 249 250 /// Get a domain translation map from a (scalar) definition to the statement 251 /// where the definition is being moved to. 252 /// 253 /// @p TargetStmt can also be seen at an llvm::Use of an llvm::Value in 254 /// @p DefStmt. In addition, we allow transitive uses: 255 /// 256 /// DefStmt -> MiddleStmt -> TargetStmt 257 /// 258 /// where an operand tree of instructions in DefStmt and MiddleStmt are to be 259 /// moved to TargetStmt. To be generally correct, we also need to know all the 260 /// intermediate statements. However, we make use of the fact that 261 /// ForwardOpTree currently does not support a move from a loop body across 262 /// its header such that only the first definition and the target statement 263 /// are relevant. 264 /// 265 /// @param DefStmt Statement from where a definition might be moved from. 266 /// @param TargetStmt Statement where the definition is potentially being 267 /// moved to (should contain a use of that definition). 268 /// 269 /// @return { DomainDef[] -> DomainTarget[] } 270 isl::map getDefToTarget(ScopStmt *DefStmt, ScopStmt *TargetStmt); 271 272 /// Get the reaching definition of a scalar defined in @p Stmt. 273 /// 274 /// Note that this does not depend on the llvm::Instruction, only on the 275 /// statement it is defined in. Therefore the same computation can be reused. 276 /// 277 /// @param Stmt The statement in which a scalar is defined. 278 /// 279 /// @return { Scatter[] -> DomainDef[] } 280 isl::map getScalarReachingDefinition(ScopStmt *Stmt); 281 282 /// Get the reaching definition of a scalar defined in @p DefDomain. 283 /// 284 /// @param DomainDef { DomainDef[] } 285 /// The write statements to get the reaching definition for. 286 /// 287 /// @return { Scatter[] -> DomainDef[] } 288 isl::map getScalarReachingDefinition(isl::set DomainDef); 289 290 /// Create a statement-to-unknown value mapping. 291 /// 292 /// @param Stmt The statement whose instances are mapped to unknown. 293 /// 294 /// @return { Domain[] -> ValInst[] } 295 isl::map makeUnknownForDomain(ScopStmt *Stmt) const; 296 297 /// Create an isl_id that represents @p V. 298 isl::id makeValueId(llvm::Value *V); 299 300 /// Create the space for an llvm::Value that is available everywhere. 301 isl::space makeValueSpace(llvm::Value *V); 302 303 /// Create a set with the llvm::Value @p V which is available everywhere. 304 isl::set makeValueSet(llvm::Value *V); 305 306 /// Create a mapping from a statement instance to the instance of an 307 /// llvm::Value that can be used in there. 308 /// 309 /// Although LLVM IR uses single static assignment, llvm::Values can have 310 /// different contents in loops, when they get redefined in the last 311 /// iteration. This function tries to get the statement instance of the 312 /// previous definition, relative to a user. 313 /// 314 /// Example: 315 /// for (int i = 0; i < N; i += 1) { 316 /// DEF: 317 /// int v = A[i]; 318 /// USE: 319 /// use(v); 320 /// } 321 /// 322 /// The value instance used by statement instance USE[i] is DEF[i]. Hence, 323 /// makeValInst returns: 324 /// 325 /// { USE[i] -> [DEF[i] -> v[]] : 0 <= i < N } 326 /// 327 /// @param Val The value to get the instance of. 328 /// @param UserStmt The statement that uses @p Val. Can be nullptr. 329 /// @param Scope Loop the using instruction resides in. 330 /// @param IsCertain Pass true if the definition of @p Val is a 331 /// MUST_WRITE or false if the write is conditional. 332 /// 333 /// @return { DomainUse[] -> ValInst[] } 334 isl::map makeValInst(llvm::Value *Val, ScopStmt *UserStmt, llvm::Loop *Scope, 335 bool IsCertain = true); 336 337 /// Create and normalize a ValInst. 338 /// 339 /// @see makeValInst 340 /// @see normalizeValInst 341 /// @see #NormalizedPHI 342 isl::union_map makeNormalizedValInst(llvm::Value *Val, ScopStmt *UserStmt, 343 llvm::Loop *Scope, 344 bool IsCertain = true); 345 346 /// Return whether @p MA can be used for transformations (e.g. OpTree load 347 /// forwarding, DeLICM mapping). 348 bool isCompatibleAccess(MemoryAccess *MA); 349 350 /// Compute the different zones. 351 void computeCommon(); 352 353 /// Compute the normalization map that replaces PHIs by their incoming 354 /// values. 355 /// 356 /// @see #NormalizeMap 357 void computeNormalizedPHIs(); 358 359 /// Print the current state of all MemoryAccesses to @p. 360 void printAccesses(llvm::raw_ostream &OS, int Indent = 0) const; 361 362 /// Is @p MA a PHI READ access that can be normalized? 363 /// 364 /// @see #NormalizeMap 365 bool isNormalizable(MemoryAccess *MA); 366 367 /// @{ 368 /// Determine whether the argument does not map to any computed PHI. Those 369 /// should have been replaced by their incoming values. 370 /// 371 /// @see #NormalizedPHI 372 isl::boolean isNormalized(isl::map Map); 373 isl::boolean isNormalized(isl::union_map Map); 374 /// @} 375 376 public: 377 /// Return the SCoP this object is analyzing. getScop()378 Scop *getScop() const { return S; } 379 380 /// A reaching definition zone is known to have the definition's written value 381 /// if the definition is a MUST_WRITE. 382 /// 383 /// @return { [Element[] -> Zone[]] -> ValInst[] } 384 isl::union_map computeKnownFromMustWrites() const; 385 386 /// A reaching definition zone is known to be the same value as any load that 387 /// reads from that array element in that period. 388 /// 389 /// @return { [Element[] -> Zone[]] -> ValInst[] } 390 isl::union_map computeKnownFromLoad() const; 391 392 /// Compute which value an array element stores at every instant. 393 /// 394 /// @param FromWrite Use stores as source of information. 395 /// @param FromRead Use loads as source of information. 396 /// 397 /// @return { [Element[] -> Zone[]] -> ValInst[] } 398 isl::union_map computeKnown(bool FromWrite, bool FromRead) const; 399 }; 400 401 /// Create a domain-to-unknown value mapping. 402 /// 403 /// Value instances that do not represent a specific value are represented by an 404 /// unnamed tuple of 0 dimensions. Its meaning depends on the context. It can 405 /// either mean a specific but unknown value which cannot be represented by 406 /// other means. It conflicts with itself because those two unknown ValInsts may 407 /// have different concrete values at runtime. 408 /// 409 /// The other meaning is an arbitrary or wildcard value that can be chosen 410 /// freely, like LLVM's undef. If matched with an unknown ValInst, there is no 411 /// conflict. 412 /// 413 /// @param Domain { Domain[] } 414 /// 415 /// @return { Domain[] -> ValInst[] } 416 isl::union_map makeUnknownForDomain(isl::union_set Domain); 417 } // namespace polly 418 419 #endif /* POLLY_ZONEALGO_H */ 420