1//===------ Support/ScopHelper.h -- Some Helper Functions for Scop. -------===//
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// Small functions that help with LLVM-IR.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef POLLY_SUPPORT_IRHELPER_H
14#define POLLY_SUPPORT_IRHELPER_H
15
16#include "llvm/ADT/SetVector.h"
17#include "llvm/IR/Instructions.h"
18#include "llvm/IR/IntrinsicInst.h"
19#include "llvm/IR/ValueHandle.h"
20#include "isl/isl-noexceptions.h"
21#include <optional>
22
23namespace llvm {
24class LoopInfo;
25class Loop;
26class ScalarEvolution;
27class SCEV;
28class Region;
29class Pass;
30class DominatorTree;
31class RegionInfo;
32class RegionNode;
33} // namespace llvm
34
35namespace polly {
36class Scop;
37class ScopStmt;
38
39/// Enumeration of assumptions Polly can take.
40enum AssumptionKind {
41 ALIASING,
42 INBOUNDS,
43 WRAPPING,
44 UNSIGNED,
45 PROFITABLE,
46 ERRORBLOCK,
47 COMPLEXITY,
48 INFINITELOOP,
49 INVARIANTLOAD,
50 DELINEARIZATION,
51};
52
53/// Enum to distinguish between assumptions and restrictions.
54enum AssumptionSign { AS_ASSUMPTION, AS_RESTRICTION };
55
56/// Helper struct to remember assumptions.
57struct Assumption {
58 /// The kind of the assumption (e.g., WRAPPING).
59 AssumptionKind Kind;
60
61 /// Flag to distinguish assumptions and restrictions.
62 AssumptionSign Sign;
63
64 /// The valid/invalid context if this is an assumption/restriction.
65 isl::set Set;
66
67 /// The location that caused this assumption.
68 llvm::DebugLoc Loc;
69
70 /// An optional block whose domain can simplify the assumption.
71 llvm::BasicBlock *BB;
72
73 // Whether the assumption must be checked at runtime.
74 bool RequiresRTC;
75};
76
77using RecordedAssumptionsTy = llvm::SmallVector<Assumption, 8>;
78
79/// Record an assumption for later addition to the assumed context.
80///
81/// This function will add the assumption to the RecordedAssumptions. This
82/// collection will be added (@see addAssumption) to the assumed context once
83/// all paramaters are known and the context is fully built.
84///
85/// @param RecordedAssumption container which keeps all recorded assumptions.
86/// @param Kind The assumption kind describing the underlying cause.
87/// @param Set The relations between parameters that are assumed to hold.
88/// @param Loc The location in the source that caused this assumption.
89/// @param Sign Enum to indicate if the assumptions in @p Set are positive
90/// (needed/assumptions) or negative (invalid/restrictions).
91/// @param BB The block in which this assumption was taken. If it is
92/// set, the domain of that block will be used to simplify the
93/// actual assumption in @p Set once it is added. This is useful
94/// if the assumption was created prior to the domain.
95/// @param RTC Does the assumption require a runtime check?
96void recordAssumption(RecordedAssumptionsTy *RecordedAssumptions,
97 AssumptionKind Kind, isl::set Set, llvm::DebugLoc Loc,
98 AssumptionSign Sign, llvm::BasicBlock *BB = nullptr,
99 bool RTC = true);
100
101/// Type to remap values.
102using ValueMapT = llvm::DenseMap<llvm::AssertingVH<llvm::Value>,
103 llvm::AssertingVH<llvm::Value>>;
104
105/// Type for a set of invariant loads.
106using InvariantLoadsSetTy = llvm::SetVector<llvm::AssertingVH<llvm::LoadInst>>;
107
108/// Set type for parameters.
109using ParameterSetTy = llvm::SetVector<const llvm::SCEV *>;
110
111/// Set of loops (used to remember loops in non-affine subregions).
112using BoxedLoopsSetTy = llvm::SetVector<const llvm::Loop *>;
113
114/// Utility proxy to wrap the common members of LoadInst and StoreInst.
115///
116/// This works like the LLVM utility class CallSite, ie. it forwards all calls
117/// to either a LoadInst, StoreInst, MemIntrinsic or MemTransferInst.
118/// It is similar to LLVM's utility classes IntrinsicInst, MemIntrinsic,
119/// MemTransferInst, etc. in that it offers a common interface, but does not act
120/// as a fake base class.
121/// It is similar to StringRef and ArrayRef in that it holds a pointer to the
122/// referenced object and should be passed by-value as it is small enough.
123///
124/// This proxy can either represent a LoadInst instance, a StoreInst instance,
125/// a MemIntrinsic instance (memset, memmove, memcpy), a CallInst instance or a
126/// nullptr (only creatable using the default constructor); never an Instruction
127/// that is neither of the above mentioned. When representing a nullptr, only
128/// the following methods are defined:
129/// isNull(), isInstruction(), isLoad(), isStore(), ..., isMemTransferInst(),
130/// operator bool(), operator!()
131///
132/// The functions isa, cast, cast_or_null, dyn_cast are modeled te resemble
133/// those from llvm/Support/Casting.h. Partial template function specialization
134/// is currently not supported in C++ such that those cannot be used directly.
135/// (llvm::isa could, but then llvm:cast etc. would not have the expected
136/// behavior)
137class MemAccInst final {
138private:
139 llvm::Instruction *I;
140
141public:
142 MemAccInst() : I(nullptr) {}
143 MemAccInst(const MemAccInst &Inst) : I(Inst.I) {}
144 /* implicit */ MemAccInst(llvm::LoadInst &LI) : I(&LI) {}
145 /* implicit */ MemAccInst(llvm::LoadInst *LI) : I(LI) {}
146 /* implicit */ MemAccInst(llvm::StoreInst &SI) : I(&SI) {}
147 /* implicit */ MemAccInst(llvm::StoreInst *SI) : I(SI) {}
148 /* implicit */ MemAccInst(llvm::MemIntrinsic *MI) : I(MI) {}
149 /* implicit */ MemAccInst(llvm::CallInst *CI) : I(CI) {}
150 explicit MemAccInst(llvm::Instruction &I) : I(&I) { assert(isa(I)); }
151 explicit MemAccInst(llvm::Instruction *I) : I(I) { assert(isa(I)); }
152
153 static bool isa(const llvm::Value &V) {
154 return llvm::isa<llvm::LoadInst>(Val: V) || llvm::isa<llvm::StoreInst>(Val: V) ||
155 llvm::isa<llvm::CallInst>(Val: V) || llvm::isa<llvm::MemIntrinsic>(Val: V);
156 }
157 static bool isa(const llvm::Value *V) {
158 return llvm::isa<llvm::LoadInst>(Val: V) || llvm::isa<llvm::StoreInst>(Val: V) ||
159 llvm::isa<llvm::CallInst>(Val: V) || llvm::isa<llvm::MemIntrinsic>(Val: V);
160 }
161 static MemAccInst cast(llvm::Value &V) {
162 return MemAccInst(llvm::cast<llvm::Instruction>(Val&: V));
163 }
164 static MemAccInst cast(llvm::Value *V) {
165 return MemAccInst(llvm::cast<llvm::Instruction>(Val: V));
166 }
167 static MemAccInst cast_or_null(llvm::Value &V) {
168 return MemAccInst(llvm::cast<llvm::Instruction>(Val&: V));
169 }
170 static MemAccInst cast_or_null(llvm::Value *V) {
171 if (!V)
172 return MemAccInst();
173 return MemAccInst(llvm::cast<llvm::Instruction>(Val: V));
174 }
175 static MemAccInst dyn_cast(llvm::Value &V) {
176 if (isa(V))
177 return MemAccInst(llvm::cast<llvm::Instruction>(Val&: V));
178 return MemAccInst();
179 }
180 static MemAccInst dyn_cast(llvm::Value *V) {
181 assert(V);
182 if (isa(V))
183 return MemAccInst(llvm::cast<llvm::Instruction>(Val: V));
184 return MemAccInst();
185 }
186
187 MemAccInst &operator=(const MemAccInst &Inst) {
188 I = Inst.I;
189 return *this;
190 }
191 MemAccInst &operator=(llvm::LoadInst &LI) {
192 I = &LI;
193 return *this;
194 }
195 MemAccInst &operator=(llvm::LoadInst *LI) {
196 I = LI;
197 return *this;
198 }
199 MemAccInst &operator=(llvm::StoreInst &SI) {
200 I = &SI;
201 return *this;
202 }
203 MemAccInst &operator=(llvm::StoreInst *SI) {
204 I = SI;
205 return *this;
206 }
207 MemAccInst &operator=(llvm::MemIntrinsic &MI) {
208 I = &MI;
209 return *this;
210 }
211 MemAccInst &operator=(llvm::MemIntrinsic *MI) {
212 I = MI;
213 return *this;
214 }
215 MemAccInst &operator=(llvm::CallInst &CI) {
216 I = &CI;
217 return *this;
218 }
219 MemAccInst &operator=(llvm::CallInst *CI) {
220 I = CI;
221 return *this;
222 }
223
224 llvm::Instruction *get() const {
225 assert(I && "Unexpected nullptr!");
226 return I;
227 }
228 operator llvm::Instruction *() const { return asInstruction(); }
229 llvm::Instruction *operator->() const { return get(); }
230
231 explicit operator bool() const { return isInstruction(); }
232 bool operator!() const { return isNull(); }
233
234 llvm::Value *getValueOperand() const {
235 if (isLoad())
236 return asLoad();
237 if (isStore())
238 return asStore()->getValueOperand();
239 if (isMemIntrinsic())
240 return nullptr;
241 if (isCallInst())
242 return nullptr;
243 llvm_unreachable("Operation not supported on nullptr");
244 }
245 llvm::Value *getPointerOperand() const {
246 if (isLoad())
247 return asLoad()->getPointerOperand();
248 if (isStore())
249 return asStore()->getPointerOperand();
250 if (isMemIntrinsic())
251 return asMemIntrinsic()->getRawDest();
252 if (isCallInst())
253 return nullptr;
254 llvm_unreachable("Operation not supported on nullptr");
255 }
256 bool isVolatile() const {
257 if (isLoad())
258 return asLoad()->isVolatile();
259 if (isStore())
260 return asStore()->isVolatile();
261 if (isMemIntrinsic())
262 return asMemIntrinsic()->isVolatile();
263 if (isCallInst())
264 return false;
265 llvm_unreachable("Operation not supported on nullptr");
266 }
267 bool isSimple() const {
268 if (isLoad())
269 return asLoad()->isSimple();
270 if (isStore())
271 return asStore()->isSimple();
272 if (isMemIntrinsic())
273 return !asMemIntrinsic()->isVolatile();
274 if (isCallInst())
275 return true;
276 llvm_unreachable("Operation not supported on nullptr");
277 }
278 llvm::AtomicOrdering getOrdering() const {
279 if (isLoad())
280 return asLoad()->getOrdering();
281 if (isStore())
282 return asStore()->getOrdering();
283 if (isMemIntrinsic())
284 return llvm::AtomicOrdering::NotAtomic;
285 if (isCallInst())
286 return llvm::AtomicOrdering::NotAtomic;
287 llvm_unreachable("Operation not supported on nullptr");
288 }
289 bool isUnordered() const {
290 if (isLoad())
291 return asLoad()->isUnordered();
292 if (isStore())
293 return asStore()->isUnordered();
294 // Copied from the Load/Store implementation of isUnordered:
295 if (isMemIntrinsic())
296 return !asMemIntrinsic()->isVolatile();
297 if (isCallInst())
298 return true;
299 llvm_unreachable("Operation not supported on nullptr");
300 }
301
302 bool isNull() const { return !I; }
303 bool isInstruction() const { return I; }
304
305 llvm::Instruction *asInstruction() const { return I; }
306
307 bool isLoad() const { return I && llvm::isa<llvm::LoadInst>(Val: I); }
308 bool isStore() const { return I && llvm::isa<llvm::StoreInst>(Val: I); }
309 bool isCallInst() const { return I && llvm::isa<llvm::CallInst>(Val: I); }
310 bool isMemIntrinsic() const { return I && llvm::isa<llvm::MemIntrinsic>(Val: I); }
311 bool isMemSetInst() const { return I && llvm::isa<llvm::MemSetInst>(Val: I); }
312 bool isMemTransferInst() const {
313 return I && llvm::isa<llvm::MemTransferInst>(Val: I);
314 }
315
316 llvm::LoadInst *asLoad() const { return llvm::cast<llvm::LoadInst>(Val: I); }
317 llvm::StoreInst *asStore() const { return llvm::cast<llvm::StoreInst>(Val: I); }
318 llvm::CallInst *asCallInst() const { return llvm::cast<llvm::CallInst>(Val: I); }
319 llvm::MemIntrinsic *asMemIntrinsic() const {
320 return llvm::cast<llvm::MemIntrinsic>(Val: I);
321 }
322 llvm::MemSetInst *asMemSetInst() const {
323 return llvm::cast<llvm::MemSetInst>(Val: I);
324 }
325 llvm::MemTransferInst *asMemTransferInst() const {
326 return llvm::cast<llvm::MemTransferInst>(Val: I);
327 }
328};
329} // namespace polly
330
331namespace llvm {
332/// Specialize simplify_type for MemAccInst to enable dyn_cast and cast
333/// from a MemAccInst object.
334template <> struct simplify_type<polly::MemAccInst> {
335 typedef Instruction *SimpleType;
336 static SimpleType getSimplifiedValue(polly::MemAccInst &I) {
337 return I.asInstruction();
338 }
339};
340} // namespace llvm
341
342namespace polly {
343
344/// Simplify the region to have a single unconditional entry edge and a
345/// single exit edge.
346///
347/// Although this function allows DT and RI to be null, regions only work
348/// properly if the DominatorTree (for Region::contains) and RegionInfo are kept
349/// up-to-date.
350///
351/// @param R The region to be simplified
352/// @param DT DominatorTree to be updated.
353/// @param LI LoopInfo to be updated.
354/// @param RI RegionInfo to be updated.
355void simplifyRegion(llvm::Region *R, llvm::DominatorTree *DT,
356 llvm::LoopInfo *LI, llvm::RegionInfo *RI);
357
358/// Split the entry block of a function to store the newly inserted
359/// allocations outside of all Scops.
360///
361/// @param EntryBlock The entry block of the current function.
362/// @param P The pass that currently running.
363///
364void splitEntryBlockForAlloca(llvm::BasicBlock *EntryBlock, llvm::Pass *P);
365
366/// Split the entry block of a function to store the newly inserted
367/// allocations outside of all Scops.
368///
369/// @param DT DominatorTree to be updated.
370/// @param LI LoopInfo to be updated.
371/// @param RI RegionInfo to be updated.
372void splitEntryBlockForAlloca(llvm::BasicBlock *EntryBlock,
373 llvm::DominatorTree *DT, llvm::LoopInfo *LI,
374 llvm::RegionInfo *RI);
375
376/// Wrapper for SCEVExpander extended to all Polly features.
377///
378/// This wrapper will internally call the SCEVExpander but also makes sure that
379/// all additional features not represented in SCEV (e.g., SDiv/SRem are not
380/// black boxes but can be part of the function) will be expanded correctly.
381///
382/// The parameters are the same as for the creation of a SCEVExpander as well
383/// as the call to SCEVExpander::expandCodeFor:
384///
385/// @param S The current Scop.
386/// @param SE The Scalar Evolution pass.
387/// @param DL The module data layout.
388/// @param Name The suffix added to the new instruction names.
389/// @param E The expression for which code is actually generated.
390/// @param Ty The type of the resulting code.
391/// @param IP The insertion point for the new code.
392/// @param VMap A remapping of values used in @p E.
393/// @param RTCBB The last block of the RTC. Used to insert loop-invariant
394/// instructions in rare cases.
395llvm::Value *expandCodeFor(Scop &S, llvm::ScalarEvolution &SE,
396 const llvm::DataLayout &DL, const char *Name,
397 const llvm::SCEV *E, llvm::Type *Ty,
398 llvm::Instruction *IP, ValueMapT *VMap,
399 llvm::BasicBlock *RTCBB);
400
401/// Return the condition for the terminator @p TI.
402///
403/// For unconditional branches the "i1 true" condition will be returned.
404///
405/// @param TI The terminator to get the condition from.
406///
407/// @return The condition of @p TI and nullptr if none could be extracted.
408llvm::Value *getConditionFromTerminator(llvm::Instruction *TI);
409
410/// Get the smallest loop that contains @p S but is not in @p S.
411llvm::Loop *getLoopSurroundingScop(Scop &S, llvm::LoopInfo &LI);
412
413/// Get the number of blocks in @p L.
414///
415/// The number of blocks in a loop are the number of basic blocks actually
416/// belonging to the loop, as well as all single basic blocks that the loop
417/// exits to and which terminate in an unreachable instruction. We do not
418/// allow such basic blocks in the exit of a scop, hence they belong to the
419/// scop and represent run-time conditions which we want to model and
420/// subsequently speculate away.
421///
422/// @see getRegionNodeLoop for additional details.
423unsigned getNumBlocksInLoop(llvm::Loop *L);
424
425/// Get the number of blocks in @p RN.
426unsigned getNumBlocksInRegionNode(llvm::RegionNode *RN);
427
428/// Return the smallest loop surrounding @p RN.
429llvm::Loop *getRegionNodeLoop(llvm::RegionNode *RN, llvm::LoopInfo &LI);
430
431/// Check if @p LInst can be hoisted in @p R.
432///
433/// @param LInst The load to check.
434/// @param R The analyzed region.
435/// @param LI The loop info.
436/// @param SE The scalar evolution analysis.
437/// @param DT The dominator tree of the function.
438/// @param KnownInvariantLoads The invariant load set.
439///
440/// @return True if @p LInst can be hoisted in @p R.
441bool isHoistableLoad(llvm::LoadInst *LInst, llvm::Region &R, llvm::LoopInfo &LI,
442 llvm::ScalarEvolution &SE, const llvm::DominatorTree &DT,
443 const InvariantLoadsSetTy &KnownInvariantLoads);
444
445/// Return true iff @p V is an intrinsic that we ignore during code
446/// generation.
447bool isIgnoredIntrinsic(const llvm::Value *V);
448
449/// Check whether a value an be synthesized by the code generator.
450///
451/// Some value will be recalculated only from information that is code generated
452/// from the polyhedral representation. For such instructions we do not need to
453/// ensure that their operands are available during code generation.
454///
455/// @param V The value to check.
456/// @param S The current SCoP.
457/// @param SE The scalar evolution database.
458/// @param Scope Location where the value would by synthesized.
459/// @return If the instruction I can be regenerated from its
460/// scalar evolution representation, return true,
461/// otherwise return false.
462bool canSynthesize(const llvm::Value *V, const Scop &S,
463 llvm::ScalarEvolution *SE, llvm::Loop *Scope);
464
465/// Return the block in which a value is used.
466///
467/// For normal instructions, this is the instruction's parent block. For PHI
468/// nodes, this is the incoming block of that use, because this is where the
469/// operand must be defined (i.e. its definition dominates this block).
470/// Non-instructions do not use operands at a specific point such that in this
471/// case this function returns nullptr.
472llvm::BasicBlock *getUseBlock(const llvm::Use &U);
473
474// If the loop is nonaffine/boxed, return the first non-boxed surrounding loop
475// for Polly. If the loop is affine, return the loop itself.
476//
477// @param L Pointer to the Loop object to analyze.
478// @param LI Reference to the LoopInfo.
479// @param BoxedLoops Set of Boxed Loops we get from the SCoP.
480llvm::Loop *getFirstNonBoxedLoopFor(llvm::Loop *L, llvm::LoopInfo &LI,
481 const BoxedLoopsSetTy &BoxedLoops);
482
483// If the Basic Block belongs to a loop that is nonaffine/boxed, return the
484// first non-boxed surrounding loop for Polly. If the loop is affine, return
485// the loop itself.
486//
487// @param BB Pointer to the Basic Block to analyze.
488// @param LI Reference to the LoopInfo.
489// @param BoxedLoops Set of Boxed Loops we get from the SCoP.
490llvm::Loop *getFirstNonBoxedLoopFor(llvm::BasicBlock *BB, llvm::LoopInfo &LI,
491 const BoxedLoopsSetTy &BoxedLoops);
492
493/// Is the given instruction a call to a debug function?
494///
495/// A debug function can be used to insert output in Polly-optimized code which
496/// normally does not allow function calls with side-effects. For instance, a
497/// printf can be inserted to check whether a value still has the expected value
498/// after Polly generated code:
499///
500/// int sum = 0;
501/// for (int i = 0; i < 16; i+=1) {
502/// sum += i;
503/// printf("The value of sum at i=%d is %d\n", sum, i);
504/// }
505bool isDebugCall(llvm::Instruction *Inst);
506
507/// Does the statement contain a call to a debug function?
508///
509/// Such a statement must not be removed, even if has no side-effects.
510bool hasDebugCall(ScopStmt *Stmt);
511
512/// Find a property value in a LoopID.
513///
514/// Generally, a property MDNode has the format
515///
516/// !{ !"Name", value }
517///
518/// In which case the value is returned.
519///
520/// If the property is just
521///
522/// !{ !"Name" }
523///
524/// Then `nullptr` is set to mark the property is existing, but does not carry
525/// any value. If the property does not exist, `std::nullopt` is returned.
526std::optional<llvm::Metadata *> findMetadataOperand(llvm::MDNode *LoopMD,
527 llvm::StringRef Name);
528
529/// Find a boolean property value in a LoopID. The value not being defined is
530/// interpreted as a false value.
531bool getBooleanLoopAttribute(llvm::MDNode *LoopID, llvm::StringRef Name);
532
533/// Find an integers property value in a LoopID.
534std::optional<int> getOptionalIntLoopAttribute(llvm::MDNode *LoopID,
535 llvm::StringRef Name);
536
537/// Does the loop's LoopID contain a 'llvm.loop.disable_heuristics' property?
538///
539/// This is equivalent to llvm::hasDisableAllTransformsHint(Loop*), but
540/// including the LoopUtils.h header indirectly also declares llvm::MemoryAccess
541/// which clashes with polly::MemoryAccess. Declaring this alias here avoid
542/// having to include LoopUtils.h in other files.
543bool hasDisableAllTransformsHint(llvm::Loop *L);
544bool hasDisableAllTransformsHint(llvm::MDNode *LoopID);
545
546/// Represent the attributes of a loop.
547struct BandAttr {
548 /// LoopID which stores the properties of the loop, such as transformations to
549 /// apply and the metadata of followup-loops.
550 ///
551 /// Cannot be used to identify a loop. Two different loops can have the same
552 /// metadata.
553 llvm::MDNode *Metadata = nullptr;
554
555 /// The LoopInfo reference for this loop.
556 ///
557 /// Only loops from the original IR are represented by LoopInfo. Loops that
558 /// were generated by Polly are not tracked by LoopInfo.
559 llvm::Loop *OriginalLoop = nullptr;
560};
561
562/// Get an isl::id representing a loop.
563///
564/// This takes the ownership of the BandAttr and will be free'd when the
565/// returned isl::Id is free'd.
566isl::id getIslLoopAttr(isl::ctx Ctx, BandAttr *Attr);
567
568/// Create an isl::id that identifies an original loop.
569///
570/// Return nullptr if the loop does not need a BandAttr (i.e. has no
571/// properties);
572///
573/// This creates a BandAttr which must be unique per loop and therefore this
574/// must not be called multiple times on the same loop as their id would be
575/// different.
576isl::id createIslLoopAttr(isl::ctx Ctx, llvm::Loop *L);
577
578/// Is @p Id representing a loop?
579///
580/// Such ids contain a polly::BandAttr as its user pointer.
581bool isLoopAttr(const isl::id &Id);
582
583/// Return the BandAttr of a loop's isl::id.
584BandAttr *getLoopAttr(const isl::id &Id);
585
586} // namespace polly
587#endif
588

source code of polly/include/polly/Support/ScopHelper.h