include/polly/Support/ISLTools.h

   1 //===------ ISLTools.h ------------------------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Tools, utilities, helpers and extensions useful in conjunction with the
  11 // Integer Set Library (isl).
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef POLLY_ISLTOOLS_H
  16 #define POLLY_ISLTOOLS_H
  17
  18 #include "polly/Support/GICHelper.h"
  19
  20 namespace polly {
  21
  22 /// Return the range elements that are lexicographically smaller.
  23 ///
  24 /// @param Map    { Space[] -> Scatter[] }
  25 /// @param Strict True for strictly lexicographically smaller elements (exclude
  26 ///               same timepoints from the result).
  27 ///
  28 /// @return { Space[] -> Scatter[] }
  29 ///         A map to all timepoints that happen before the timepoints the input
  30 ///         mapped to.
  31 isl::map beforeScatter(isl::map Map, bool Strict);
  32
  33 /// Piecewise beforeScatter(isl::map,bool).
  34 isl::union_map beforeScatter(isl::union_map UMap, bool Strict);
  35
  36 /// Return the range elements that are lexicographically larger.
  37 ///
  38 /// @param Map    { Space[] -> Scatter[] }
  39 /// @param Strict True for strictly lexicographically larger elements (exclude
  40 ///               same timepoints from the result).
  41 ///
  42 /// @return { Space[] -> Scatter[] }
  43 ///         A map to all timepoints that happen after the timepoints the input
  44 ///         map originally mapped to.
  45 isl::map afterScatter(isl::map Map, bool Strict);
  46
  47 /// Piecewise afterScatter(isl::map,bool).
  48 isl::union_map afterScatter(const isl::union_map &UMap, bool Strict);
  49
  50 /// Construct a range of timepoints between two timepoints.
  51 ///
  52 /// Example:
  53 /// From := { A[] -> [0]; B[] -> [0] }
  54 /// To   := {             B[] -> [10]; C[] -> [20] }
  55 ///
  56 /// Result:
  57 /// { B[] -> [i] : 0 < i < 10 }
  58 ///
  59 /// Note that A[] and C[] are not in the result because they do not have a start
  60 /// or end timepoint. If a start (or end) timepoint is not unique, the first
  61 /// (respectively last) is chosen.
  62 ///
  63 /// @param From     { Space[] -> Scatter[] }
  64 ///                 Map to start timepoints.
  65 /// @param To       { Space[] -> Scatter[] }
  66 ///                 Map to end timepoints.
  67 /// @param InclFrom Whether to include the start timepoints in the result. In
  68 ///                 the example, this would add { B[] -> [0] }
  69 /// @param InclTo   Whether to include the end timepoints in the result. In this
  70 ///                 example, this would add { B[] -> [10] }
  71 ///
  72 /// @return { Space[] -> Scatter[] }
  73 ///         A map for each domain element of timepoints between two extreme
  74 ///         points, or nullptr if @p From or @p To is nullptr, or the isl max
  75 ///         operations is exceeded.
  76 isl::map betweenScatter(isl::map From, isl::map To, bool InclFrom, bool InclTo);
  77
  78 /// Piecewise betweenScatter(isl::map,isl::map,bool,bool).
  79 isl::union_map betweenScatter(isl::union_map From, isl::union_map To,
  80                               bool InclFrom, bool InclTo);
  81
  82 /// If by construction a union map is known to contain only a single map, return
  83 /// it.
  84 ///
  85 /// This function combines isl_map_from_union_map() and
  86 /// isl_union_map_extract_map(). isl_map_from_union_map() fails if the map is
  87 /// empty because it does not know which space it would be in.
  88 /// isl_union_map_extract_map() on the other hand does not check whether there
  89 /// is (at most) one isl_map in the union, i.e. how it has been constructed is
  90 /// probably wrong.
  91 isl::map singleton(isl::union_map UMap, isl::space ExpectedSpace);
  92
  93 /// If by construction an isl_union_set is known to contain only a single
  94 /// isl_set, return it.
  95 ///
  96 /// This function combines isl_set_from_union_set() and
  97 /// isl_union_set_extract_set(). isl_map_from_union_set() fails if the set is
  98 /// empty because it does not know which space it would be in.
  99 /// isl_union_set_extract_set() on the other hand does not check whether there
 100 /// is (at most) one isl_set in the union, i.e. how it has been constructed is
 101 /// probably wrong.
 102 isl::set singleton(isl::union_set USet, isl::space ExpectedSpace);
 103
 104 /// Determine how many dimensions the scatter space of @p Schedule has.
 105 ///
 106 /// The schedule must not be empty and have equal number of dimensions of any
 107 /// subspace it contains.
 108 ///
 109 /// The implementation currently returns the maximum number of dimensions it
 110 /// encounters, if different, and 0 if none is encountered. However, most other
 111 /// code will most likely fail if one of these happen.
 112 unsigned getNumScatterDims(const isl::union_map &Schedule);
 113
 114 /// Return the scatter space of a @p Schedule.
 115 ///
 116 /// This is basically the range space of the schedule map, but harder to
 117 /// determine because it is an isl_union_map.
 118 isl::space getScatterSpace(const isl::union_map &Schedule);
 119
 120 /// Construct an identity map for the given domain values.
 121 ///
 122 /// There is no type resembling isl_union_space, hence we have to pass an
 123 /// isl_union_set as the map's domain and range space.
 124 ///
 125 /// @param USet           { Space[] }
 126 ///                       The returned map's domain and range.
 127 /// @param RestrictDomain If true, the returned map only maps elements contained
 128 ///                       in @p USet and no other. If false, it returns an
 129 ///                       overapproximation with the identity maps of any space
 130 ///                       in @p USet, not just the elements in it.
 131 ///
 132 /// @return { Space[] -> Space[] }
 133 ///         A map that maps each value of @p USet to itself.
 134 isl::union_map makeIdentityMap(const isl::union_set &USet, bool RestrictDomain);
 135
 136 /// Reverse the nested map tuple in @p Map's domain.
 137 ///
 138 /// @param Map { [Space1[] -> Space2[]] -> Space3[] }
 139 ///
 140 /// @return { [Space2[] -> Space1[]] -> Space3[] }
 141 isl::map reverseDomain(isl::map Map);
 142
 143 /// Piecewise reverseDomain(isl::map).
 144 isl::union_map reverseDomain(const isl::union_map &UMap);
 145
 146 /// Add a constant to one dimension of a set.
 147 ///
 148 /// @param Map    The set to shift a dimension in.
 149 /// @param Pos    The dimension to shift. If negative, the dimensions are
 150 ///               counted from the end instead from the beginning. E.g. -1 is
 151 ///               the last dimension in the tuple.
 152 /// @param Amount The offset to add to the specified dimension.
 153 ///
 154 /// @return The modified set.
 155 isl::set shiftDim(isl::set Set, int Pos, int Amount);
 156
 157 /// Piecewise shiftDim(isl::set,int,int).
 158 isl::union_set shiftDim(isl::union_set USet, int Pos, int Amount);
 159
 160 /// Add a constant to one dimension of a map.
 161 ///
 162 /// @param Map    The map to shift a dimension in.
 163 /// @param Type   A tuple of @p Map which contains the dimension to shift.
 164 /// @param Pos    The dimension to shift. If negative, the dimensions are
 165 /// counted from the end instead from the beginning. Eg. -1 is the last
 166 /// dimension in the tuple.
 167 /// @param Amount The offset to add to the specified dimension.
 168 ///
 169 /// @return The modified map.
 170 isl::map shiftDim(isl::map Map, isl::dim Dim, int Pos, int Amount);
 171
 172 /// Add a constant to one dimension of a each map in a union map.
 173 ///
 174 /// @param UMap   The maps to shift a dimension in.
 175 /// @param Type   The tuple which contains the dimension to shift.
 176 /// @param Pos    The dimension to shift. If negative, the dimensions are
 177 ///               counted from the ends of each map of union instead from their
 178 ///               beginning. E.g. -1 is the last dimension of any map.
 179 /// @param Amount The offset to add to the specified dimension.
 180 ///
 181 /// @return The union of all modified maps.
 182 isl::union_map shiftDim(isl::union_map UMap, isl::dim Dim, int Pos, int Amount);
 183
 184 /// Simplify a set inplace.
 185 void simplify(isl::set &Set);
 186
 187 /// Simplify a union set inplace.
 188 void simplify(isl::union_set &USet);
 189
 190 /// Simplify a map inplace.
 191 void simplify(isl::map &Map);
 192
 193 /// Simplify a union map inplace.
 194 void simplify(isl::union_map &UMap);
 195
 196 /// Compute the reaching definition statement or the next overwrite for each
 197 /// definition of an array element.
 198 ///
 199 /// The reaching definition of an array element at a specific timepoint is the
 200 /// statement instance that has written the current element's content.
 201 /// Alternatively, this function determines for each timepoint and element which
 202 /// write is going to overwrite an element at a future timepoint. This can be
 203 /// seen as "reaching definition in reverse" where definitions are found in the
 204 /// past.
 205 ///
 206 /// For example:
 207 ///
 208 /// Schedule := { Write[] -> [0]; Overwrite[] -> [10] }
 209 /// Defs := { Write[] -> A[5]; Overwrite[] -> A[5] }
 210 ///
 211 /// If index 5 of array A is written at timepoint 0 and 10, the resulting
 212 /// reaching definitions are:
 213 ///
 214 /// { [A[5] -> [i]] -> Write[] : 0 < i < 10;
 215 ///   [A[5] -> [i]] -> Overwrite[] : 10 < i }
 216 ///
 217 /// Between timepoint 0 (Write[]) and timepoint 10 (Overwrite[]), the
 218 /// content of A[5] is written by statement instance Write[] and after
 219 /// timepoint 10 by Overwrite[]. Values not defined in the map have no known
 220 /// definition. This includes the statement instance timepoints themselves,
 221 /// because reads at those timepoints could either read the old or the new
 222 /// value, defined only by the statement itself. But this can be changed by @p
 223 /// InclPrevDef and @p InclNextDef. InclPrevDef=false and InclNextDef=true
 224 /// returns a zone. Unless @p InclPrevDef and @p InclNextDef are both true,
 225 /// there is only one unique definition per element and timepoint.
 226 ///
 227 /// @param Schedule    { DomainWrite[] -> Scatter[] }
 228 ///                    Schedule of (at least) all array writes. Instances not in
 229 ///                    @p Writes are ignored.
 230 /// @param Writes      { DomainWrite[] -> Element[] }
 231 ///                    Elements written to by the statement instances.
 232 /// @param Reverse     If true, look for definitions in the future. That is,
 233 ///                    find the write that is overwrites the current value.
 234 /// @param InclPrevDef Include the definition's timepoint to the set of
 235 ///                    well-defined elements (any load at that timepoint happen
 236 ///                    at the writes). In the example, enabling this option adds
 237 ///                    {[A[5] -> [0]] -> Write[]; [A[5] -> [10]] -> Overwrite[]}
 238 ///                    to the result.
 239 /// @param InclNextDef Whether to assume that at the timepoint where an element
 240 ///                    is overwritten, it still contains the old value (any load
 241 ///                    at that timepoint would happen before the overwrite). In
 242 ///                    this example, enabling this adds
 243 ///                    { [A[] -> [10]] -> Write[] } to the result.
 244 ///
 245 /// @return { [Element[] -> Scatter[]] -> DomainWrite[] }
 246 ///         The reaching definitions or future overwrite as described above, or
 247 ///         nullptr if either @p Schedule or @p Writes is nullptr, or the isl
 248 ///         max operations count has exceeded.
 249 isl::union_map computeReachingWrite(isl::union_map Schedule,
 250                                     isl::union_map Writes, bool Reverse,
 251                                     bool InclPrevDef, bool InclNextDef);
 252
 253 /// Compute the timepoints where the contents of an array element are not used.
 254 ///
 255 /// An element is unused at a timepoint when the element is overwritten in
 256 /// the future, but it is not read in between. Another way to express this: the
 257 /// time from when the element is written, to the most recent read before it, or
 258 /// infinitely into the past if there is no read before. Such unused elements
 259 /// can be overwritten by any value without changing the scop's semantics. An
 260 /// example:
 261 ///
 262 /// Schedule := { Read[] -> [0]; Write[] -> [10]; Def[] -> [20] }
 263 /// Writes := { Write[] -> A[5]; Def[] -> A[6] }
 264 /// Reads := { Read[] -> A[5] }
 265 ///
 266 /// The result is:
 267 ///
 268 /// { A[5] -> [i] : 0 < i < 10;
 269 ///   A[6] -> [i] : i < 20 }
 270 ///
 271 /// That is, A[5] is unused between timepoint 0 (the read) and timepoint 10 (the
 272 /// write). A[6] is unused before timepoint 20, but might be used after the
 273 /// scop's execution (A[5] and any other A[i] as well). Use InclLastRead=false
 274 /// and InclWrite=true to interpret the result as zone.
 275 ///
 276 /// @param Schedule          { Domain[] -> Scatter[] }
 277 ///                          The schedule of (at least) all statement instances
 278 ///                          occurring in @p Writes or @p Reads. All other
 279 ///                          instances are ignored.
 280 /// @param Writes            { DomainWrite[] -> Element[] }
 281 ///                          Elements written to by the statement instances.
 282 /// @param Reads             { DomainRead[] -> Element[] }
 283 ///                          Elements read from by the statement instances.
 284 /// @param ReadEltInSameInst Whether a load reads the value from a write
 285 ///                          that is scheduled at the same timepoint (Writes
 286 ///                          happen before reads). Otherwise, loads use the
 287 ///                          value of an element that it had before the
 288 ///                          timepoint (Reads before writes). For example:
 289 ///                          { Read[] -> [0]; Write[] -> [0] }
 290 ///                          With ReadEltInSameInst=false it is assumed that the
 291 ///                          read happens before the write, such that the
 292 ///                          element is never unused, or just at timepoint 0,
 293 ///                          depending on InclLastRead/InclWrite.
 294 ///                          With ReadEltInSameInst=false it assumes that the
 295 ///                          value just written is used. Anything before
 296 ///                          timepoint 0 is considered unused.
 297 /// @param InclLastRead      Whether a timepoint where an element is last read
 298 ///                          counts as unused (the read happens at the beginning
 299 ///                          of its timepoint, and nothing (else) can use it
 300 ///                          during the timepoint). In the example, this option
 301 ///                          adds { A[5] -> [0] } to the result.
 302 /// @param InclWrite         Whether the timepoint where an element is written
 303 ///                          itself counts as unused (the write happens at the
 304 ///                          end of its timepoint; no (other) operations uses
 305 ///                          the element during the timepoint). In this example,
 306 ///                          this adds
 307 ///                          { A[5] -> [10]; A[6] -> [20] } to the result.
 308 ///
 309 /// @return { Element[] -> Scatter[] }
 310 ///         The unused timepoints as defined above, or nullptr if either @p
 311 ///         Schedule, @p Writes are @p Reads is nullptr, or the ISL max
 312 ///         operations count is exceeded.
 313 isl::union_map computeArrayUnused(isl::union_map Schedule,
 314                                   isl::union_map Writes, isl::union_map Reads,
 315                                   bool ReadEltInSameInst, bool InclLastRead,
 316                                   bool InclWrite);
 317
 318 /// Convert a zone (range between timepoints) to timepoints.
 319 ///
 320 /// A zone represents the time between (integer) timepoints, but not the
 321 /// timepoints themselves. This function can be used to determine whether a
 322 /// timepoint lies within a zone.
 323 ///
 324 /// For instance, the range (1,3), representing the time between 1 and 3, is
 325 /// represented by the zone
 326 ///
 327 /// { [i] : 1 < i <= 3 }
 328 ///
 329 /// The set of timepoints that lie completely within this range is
 330 ///
 331 /// { [i] : 1 < i < 3 }
 332 ///
 333 /// A typical use-case is the range in which a value written by a store is
 334 /// available until it is overwritten by another value. If the write is at
 335 /// timepoint 1 and its value is overwritten by another value at timepoint 3,
 336 /// the value is available between those timepoints: timepoint 2 in this
 337 /// example.
 338 ///
 339 ///
 340 /// When InclStart is true, the range is interpreted left-inclusive, i.e. adds
 341 /// the timepoint 1 to the result:
 342 ///
 343 /// { [i] : 1 <= i < 3 }
 344 ///
 345 /// In the use-case mentioned above that means that the value written at
 346 /// timepoint 1 is already available in timepoint 1 (write takes place before
 347 /// any read of it even if executed at the same timepoint)
 348 ///
 349 /// When InclEnd is true, the range is interpreted right-inclusive, i.e. adds
 350 /// the timepoint 3 to the result:
 351 ///
 352 /// { [i] : 1 < i <= 3 }
 353 ///
 354 /// In the use-case mentioned above that means that although the value is
 355 /// overwritten in timepoint 3, the old value is still available at timepoint 3
 356 /// (write takes place after any read even if executed at the same timepoint)
 357 ///
 358 /// @param Zone      { Zone[] }
 359 /// @param InclStart Include timepoints adjacent to the beginning of a zone.
 360 /// @param InclEnd   Include timepoints adjacent to the ending of a zone.
 361 ///
 362 /// @return { Scatter[] }
 363 isl::union_set convertZoneToTimepoints(isl::union_set Zone, bool InclStart,
 364                                        bool InclEnd);
 365
 366 /// Like convertZoneToTimepoints(isl::union_set,InclStart,InclEnd), but convert
 367 /// either the domain or the range of a map.
 368 isl::union_map convertZoneToTimepoints(isl::union_map Zone, isl::dim Dim,
 369                                        bool InclStart, bool InclEnd);
 370
 371 /// Overload of convertZoneToTimepoints(isl::map,InclStart,InclEnd) to process
 372 /// only a single map.
 373 isl::map convertZoneToTimepoints(isl::map Zone, isl::dim Dim, bool InclStart,
 374                                  bool InclEnd);
 375
 376 /// Distribute the domain to the tuples of a wrapped range map.
 377 ///
 378 /// @param Map { Domain[] -> [Range1[] -> Range2[]] }
 379 ///
 380 /// @return { [Domain[] -> Range1[]] -> [Domain[] -> Range2[]] }
 381 isl::map distributeDomain(isl::map Map);
 382
 383 /// Apply distributeDomain(isl::map) to each map in the union.
 384 isl::union_map distributeDomain(isl::union_map UMap);
 385
 386 /// Prepend a space to the tuples of a map.
 387 ///
 388 /// @param UMap   { Domain[] -> Range[] }
 389 /// @param Factor { Factor[] }
 390 ///
 391 /// @return { [Factor[] -> Domain[]] -> [Factor[] -> Range[]] }
 392 isl::union_map liftDomains(isl::union_map UMap, isl::union_set Factor);
 393
 394 /// Apply a map to the 'middle' of another relation.
 395 ///
 396 /// @param UMap { [DomainDomain[] -> DomainRange[]] -> Range[] }
 397 /// @param Func { DomainRange[] -> NewDomainRange[] }
 398 ///
 399 /// @return { [DomainDomain[] -> NewDomainRange[]] -> Range[] }
 400 isl::union_map applyDomainRange(isl::union_map UMap, isl::union_map Func);
 401 } // namespace polly
 402
 403 #endif /* POLLY_ISLTOOLS_H */