LoopVersioning.cpp Source File (original) (raw)

32using namespace llvm;

34#define DEBUG_TYPE "loop-versioning"

39 cl::desc("Add no-alias annotation for instructions that "

40 "are disambiguated by memchecks"));

46 : VersionedLoop(L), AliasChecks(Checks), Preds(LAI.getPSE().getPredicate()),

47 LAI(LAI), LI(LI), DT(DT), SE(SE) {}

53 "Loop is not in loop-simplify form");

55 Value *MemRuntimeCheck;

56 Value *SCEVRuntimeCheck;

57 Value *RuntimeCheck = nullptr;

65 "induction");

67 VersionedLoop, AliasChecks, Exp2);

70 "scev.check");

71 SCEVRuntimeCheck =

72 Exp.expandCodeForPredicate(&Preds, RuntimeCheckBB->getTerminator());

77 if (MemRuntimeCheck && SCEVRuntimeCheck) {

79 RuntimeCheck =

80 Builder.CreateOr(MemRuntimeCheck, SCEVRuntimeCheck, "lver.safe");

81 } else

82 RuntimeCheck = MemRuntimeCheck ? MemRuntimeCheck : SCEVRuntimeCheck;

84 assert(RuntimeCheck && "called even though we don't need "

85 "any runtime checks");

89 ".lver.check");

100

102 NonVersionedLoop =

104 ".lver.orig", LI, DT, NonVersionedLoopBlocks);

106

107

113

114

115

117

118

119

120 addPHINodes(DefsUsedOutside);

125 "The versioned loops should be in simplify form.");

126}

127

128void LoopVersioning::addPHINodes(

131 assert(PHIBlock && "No single successor to loop exit block");

133

134

135

136 for (auto *Inst : DefsUsedOutside) {

137

138

139 for (auto I = PHIBlock->begin(); (PN = dyn_cast(I)); ++I) {

142 break;

143 }

144 }

145

146 if (!PN) {

147 PN = PHINode::Create(Inst->getType(), 2, Inst->getName() + ".lver");

151 if (!VersionedLoop->contains(cast(U)->getParent()))

153 for (User *U : UsersToUpdate)

154 U->replaceUsesOfWith(Inst, PN);

156 }

157 }

158

159

160 for (auto I = PHIBlock->begin(); (PN = dyn_cast(I)); ++I) {

162 "Exit block should only have on predecessor");

163

164

166 auto Mapped = VMap.find(ClonedValue);

167 if (Mapped != VMap.end())

168 ClonedValue = Mapped->second;

169

171 }

172}

173

175

176

177

178

179

180

181

184

185

186

187

188

189

192

193 for (const auto &Group : RtPtrChecking->CheckingGroups) {

195

196 for (unsigned PtrIdx : Group.Members)

198 }

199

200

201

203 GroupToNonAliasingScopes;

204

205 for (const auto &Check : AliasChecks)

206 GroupToNonAliasingScopes[Check.first].push_back(GroupToScope[Check.second]);

207

208

209

210

211 for (const auto &Pair : GroupToNonAliasingScopes)

212 GroupToNonAliasingScopeList[Pair.first] = MDNode::get(Context, Pair.second);

213}

214

217 return;

218

219

221

222

225 }

226}

227

231 return;

232

234 const Value *Ptr = isa(OrigInst)

235 ? cast(OrigInst)->getPointerOperand()

236 : cast(OrigInst)->getPointerOperand();

237

238

239 auto Group = PtrToGroup.find(Ptr);

240 if (Group != PtrToGroup.end()) {

242 LLVMContext::MD_alias_scope,

244 VersionedInst->getMetadata(LLVMContext::MD_alias_scope),

245 MDNode::get(Context, GroupToScope[Group->second])));

246

247

248 auto NonAliasingScopeList = GroupToNonAliasingScopeList.find(Group->second);

249 if (NonAliasingScopeList != GroupToNonAliasingScopeList.end())

251 LLVMContext::MD_noalias,

253 VersionedInst->getMetadata(LLVMContext::MD_noalias),

254 NonAliasingScopeList->second));

255 }

256}

257

258namespace {

261

262

263

265

266 for (Loop *TopLevelLoop : *LI)

268

269 if (L->isInnermost())

271

272

273 bool Changed = false;

274 for (Loop *L : Worklist) {

275 if (!L->isLoopSimplifyForm() || !L->isRotatedForm() ||

276 !L->getExitingBlock())

277 continue;

282 if (!L->isLCSSAForm(*DT))

284

286 LI, DT, SE);

287 LVer.versionLoop();

288 LVer.annotateLoopWithNoAlias();

289 Changed = true;

291 }

292 }

293

294 return Changed;

295}

296}

297

304

305 if (runImpl(&LI, LAIs, &DT, &SE))

308}

static bool runImpl(Function &F, const TargetLowering &TLI)

This header defines various interfaces for pass management in LLVM.

static cl::opt< bool > AnnotateNoAlias("loop-version-annotate-no-alias", cl::init(true), cl::Hidden, cl::desc("Add no-alias annotation for instructions that " "are disambiguated by memchecks"))

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

A container for analyses that lazily runs them and caches their results.

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

LLVM Basic Block Representation.

iterator begin()

Instruction iterator methods.

const DataLayout & getDataLayout() const

Get the data layout of the module this basic block belongs to.

LLVMContext & getContext() const

Get the context in which this basic block lives.

const Instruction * getTerminator() const LLVM_READONLY

Returns the terminator instruction if the block is well formed or null if the block is not well forme...

Analysis pass which computes a DominatorTree.

void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)

changeImmediateDominator - This method is used to update the dominator tree information when a node's...

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)

Create a conditional 'br Cond, TrueDest, FalseDest' instruction.

Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")

void SetInsertPoint(BasicBlock *TheBB)

This specifies that created instructions should be appended to the end of the specified block.

This provides a uniform API for creating instructions and inserting them into a basic block: either a...

InstSimplifyFolder - Use InstructionSimplify to fold operations to existing values.

void insertBefore(Instruction *InsertPos)

Insert an unlinked instruction into a basic block immediately before the specified instruction.

InstListType::iterator eraseFromParent()

This method unlinks 'this' from the containing basic block and deletes it.

MDNode * getMetadata(unsigned KindID) const

Get the metadata of given kind attached to this Instruction.

void setMetadata(unsigned KindID, MDNode *Node)

Set the metadata of the specified kind to the specified node.

This is an important class for using LLVM in a threaded context.

This analysis provides dependence information for the memory accesses of a loop.

const LoopAccessInfo & getInfo(Loop &L)

Drive the analysis of memory accesses in the loop.

const MemoryDepChecker & getDepChecker() const

the Memory Dependence Checker which can determine the loop-independent and loop-carried dependences b...

const RuntimePointerChecking * getRuntimePointerChecking() const

unsigned getNumRuntimePointerChecks() const

Number of memchecks required to prove independence of otherwise may-alias pointers.

const PredicatedScalarEvolution & getPSE() const

Used to add runtime SCEV checks.

bool hasConvergentOp() const

Return true if there is a convergent operation in the loop.

Analysis pass that exposes the LoopInfo for a function.

bool contains(const LoopT *L) const

Return true if the specified loop is contained within in this loop.

BlockT * getHeader() const

BlockT * getExitBlock() const

If getExitBlocks would return exactly one block, return that block.

BlockT * getLoopPreheader() const

If there is a preheader for this loop, return it.

BlockT * getExitingBlock() const

If getExitingBlocks would return exactly one block, return that block.

BlockT * getUniqueExitBlock() const

If getUniqueExitBlocks would return exactly one block, return that block.

PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)

This class emits a version of the loop where run-time checks ensure that may-alias pointers can't ove...

void annotateLoopWithNoAlias()

Annotate memory instructions in the versioned loop with no-alias metadata based on the memchecks issu...

void prepareNoAliasMetadata()

Set up the aliasing scopes based on the memchecks.

void annotateInstWithNoAlias(Instruction *VersionedInst, const Instruction *OrigInst)

Add the noalias annotations to VersionedInst.

void versionLoop()

Performs the CFG manipulation part of versioning the loop including the DominatorTree and LoopInfo up...

LoopVersioning(const LoopAccessInfo &LAI, ArrayRef< RuntimePointerCheck > Checks, Loop *L, LoopInfo *LI, DominatorTree *DT, ScalarEvolution *SE)

Expects LoopAccessInfo, Loop, LoopInfo, DominatorTree as input.

Represents a single loop in the control flow graph.

bool isLoopSimplifyForm() const

Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...

MDNode * createAnonymousAliasScope(MDNode *Domain, StringRef Name=StringRef())

Return metadata appropriate for an alias scope root node.

MDNode * createAnonymousAliasScopeDomain(StringRef Name=StringRef())

Return metadata appropriate for an alias scope domain node.

static MDNode * concatenate(MDNode *A, MDNode *B)

Methods for metadata merging.

static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)

const SmallVectorImpl< Instruction * > & getMemoryInstructions() const

The vector of memory access instructions.

void addIncoming(Value *V, BasicBlock *BB)

Add an incoming value to the end of the PHI list.

Value * getIncomingValue(unsigned i) const

Return incoming value number x.

static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)

Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...

const SCEVPredicate & getPredicate() const

A set of analyses that are preserved following a run of a transformation pass.

static PreservedAnalyses none()

Convenience factory function for the empty preserved set.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

Holds information about the memory runtime legality checks to verify that a group of pointers do not ...

SmallVector< RuntimeCheckingPtrGroup, 2 > CheckingGroups

Holds a partitioning of pointers into "check groups".

const SmallVectorImpl< RuntimePointerCheck > & getChecks() const

Returns the checks that generateChecks created.

const PointerInfo & getPointerInfo(unsigned PtrIdx) const

Return PointerInfo for pointer at index PtrIdx.

This class uses information about analyze scalars to rewrite expressions in canonical form.

virtual bool isAlwaysTrue() const =0

Returns true if the predicate is always true.

Analysis pass that exposes the ScalarEvolution for a function.

The main scalar evolution driver.

void forgetLcssaPhiWithNewPredecessor(Loop *L, PHINode *V)

Forget LCSSA phi node V of loop L to which a new predecessor was added, such that it may no longer be...

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

void push_back(const T &Elt)

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

unsigned getNumOperands() const

iterator find(const KeyT &Val)

LLVM Value Representation.

void setName(const Twine &Name)

Change the name of the value.

iterator_range< user_iterator > users()

StringRef getName() const

Return a constant reference to the value's name.

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

Value * addRuntimeChecks(Instruction *Loc, Loop *TheLoop, const SmallVectorImpl< RuntimePointerCheck > &PointerChecks, SCEVExpander &Expander, bool HoistRuntimeChecks=false)

Add code that checks at runtime if the accessed arrays in PointerChecks overlap.

bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)

Put a loop nest into LCSSA form.

Loop * cloneLoopWithPreheader(BasicBlock *Before, BasicBlock *LoopDomBB, Loop *OrigLoop, ValueToValueMapTy &VMap, const Twine &NameSuffix, LoopInfo *LI, DominatorTree *DT, SmallVectorImpl< BasicBlock * > &Blocks)

Clones a loop OrigLoop.

bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)

Ensure that all exit blocks of the loop are dedicated exits.

void remapInstructionsInBlocks(ArrayRef< BasicBlock * > Blocks, ValueToValueMapTy &VMap)

Remaps instructions in Blocks using the mapping in VMap.

BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)

Split the specified block at the specified instruction.

iterator_range< df_iterator< T > > depth_first(const T &G)

TrackingVH< Value > PointerValue

Holds the pointer value that we need to check.