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