1 //===- LoopVersioning.h - Utility to version a loop -------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines a utility class to perform loop versioning. The versioned
11 // loop speculates that otherwise may-aliasing memory accesses don't overlap and
12 // emits checks to prove this.
14 //===----------------------------------------------------------------------===//
16 #ifndef LLVM_TRANSFORMS_UTILS_LOOPVERSIONING_H
17 #define LLVM_TRANSFORMS_UTILS_LOOPVERSIONING_H
19 #include "llvm/Transforms/Utils/ValueMapper.h"
27 /// \brief This class emits a version of the loop where run-time checks ensure
28 /// that may-alias pointers can't overlap.
30 /// It currently only supports single-exit loops and assumes that the loop
31 /// already has a preheader.
32 class LoopVersioning {
34 LoopVersioning(const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI,
36 const SmallVector<int, 8> *PtrToPartition = nullptr);
38 /// \brief Returns true if we need memchecks to disambiguate may-aliasing
40 bool needsRuntimeChecks() const;
42 /// \brief Performs the CFG manipulation part of versioning the loop including
43 /// the DominatorTree and LoopInfo updates.
45 /// The loop that was used to construct the class will be the "versioned" loop
46 /// i.e. the loop that will receive control if all the memchecks pass.
48 /// This allows the loop transform pass to operate on the same loop regardless
49 /// of whether versioning was necessary or not:
53 /// if versioning is necessary version L
55 void versionLoop(Pass *P);
57 /// \brief Adds the necessary PHI nodes for the versioned loops based on the
58 /// loop-defined values used outside of the loop.
60 /// This needs to be called after versionLoop if there are defs in the loop
61 /// that are used outside the loop. FIXME: this should be invoked internally
62 /// by versionLoop and made private.
63 void addPHINodes(const SmallVectorImpl<Instruction *> &DefsUsedOutside);
65 /// \brief Returns the versioned loop. Control flows here if pointers in the
66 /// loop don't alias (i.e. all memchecks passed). (This loop is actually the
67 /// same as the original loop that we got constructed with.)
68 Loop *getVersionedLoop() { return VersionedLoop; }
70 /// \brief Returns the fall-back loop. Control flows here if pointers in the
71 /// loop may alias (i.e. one of the memchecks failed).
72 Loop *getNonVersionedLoop() { return NonVersionedLoop; }
75 /// \brief The original loop. This becomes the "versioned" one. I.e.,
76 /// control flows here if pointers in the loop don't alias.
78 /// \brief The fall-back loop. I.e. control flows here if pointers in the
79 /// loop may alias (memchecks failed).
80 Loop *NonVersionedLoop;
82 /// \brief For each memory pointer it contains the partitionId it is used in.
83 /// If nullptr, no partitioning is used.
85 /// The I-th entry corresponds to I-th entry in LAI.getRuntimePointerCheck().
86 /// If the pointer is used in multiple partitions the entry is set to -1.
87 const SmallVector<int, 8> *PtrToPartition;
89 /// \brief This maps the instructions from VersionedLoop to their counterpart
90 /// in NonVersionedLoop.
91 ValueToValueMapTy VMap;
93 /// \brief Analyses used.
94 const LoopAccessInfo &LAI;