LoopVersioning.cpp Source File (original) (raw)

33using namespace llvm;

35#define DEBUG_TYPE "loop-versioning"

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

41 "are disambiguated by memchecks"));

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

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

52 assert(VersionedLoop->getUniqueExitBlock() && "No single exit block");

53 assert(VersionedLoop->isLoopSimplifyForm() &&

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

56 Value *MemRuntimeCheck;

57 Value *SCEVRuntimeCheck;

58 Value *RuntimeCheck = nullptr;

61 BasicBlock *RuntimeCheckBB = VersionedLoop->getLoopPreheader();

62 const auto &RtPtrChecking = *LAI.getRuntimePointerChecking();

64 SCEVExpander Exp2(*RtPtrChecking.getSE(), "induction");

66 VersionedLoop, AliasChecks, Exp2);

69 SCEVRuntimeCheck =

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

75 if (MemRuntimeCheck && SCEVRuntimeCheck) {

76 Builder.SetInsertPoint(RuntimeCheckBB->getTerminator());

77 RuntimeCheck =

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

79 } else

80 RuntimeCheck = MemRuntimeCheck ? MemRuntimeCheck : SCEVRuntimeCheck;

82 Exp.eraseDeadInstructions(SCEVRuntimeCheck);

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

85 "any runtime checks");

88 RuntimeCheckBB->setName(VersionedLoop->getHeader()->getName() +

89 ".lver.check");

95 nullptr, VersionedLoop->getHeader()->getName() + ".ph");

100

102 NonVersionedLoop =

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

106

107

109 Builder.SetInsertPoint(OrigTerm);

110 auto *BI =

111 Builder.CreateCondBr(RuntimeCheck, NonVersionedLoop->getLoopPreheader(),

112 VersionedLoop->getLoopPreheader());

113

114

117

118

119

120 DT->changeImmediateDominator(VersionedLoop->getExitBlock(), RuntimeCheckBB);

121

122

123

124 addPHINodes(DefsUsedOutside);

127 assert(NonVersionedLoop->isLoopSimplifyForm() &&

128 VersionedLoop->isLoopSimplifyForm() &&

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

130}

131

132void LoopVersioning::addPHINodes(

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

137

138

139

140 for (auto *Inst : DefsUsedOutside) {

141

142

146 break;

147 }

148 }

149

150 if (!PN) {

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

154 for (User *U : Inst->users())

157 for (User *U : UsersToUpdate)

158 U->replaceUsesOfWith(Inst, PN);

159 PN->addIncoming(Inst, VersionedLoop->getExitingBlock());

160 }

161 }

162

163

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

167

168

170 auto Mapped = VMap.find(ClonedValue);

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

172 ClonedValue = Mapped->second;

173

174 PN->addIncoming(ClonedValue, NonVersionedLoop->getExitingBlock());

175 }

176}

177

179

180

181

182

183

184

185

187 LLVMContext &Context = VersionedLoop->getHeader()->getContext();

188

189

190

191

192

193

196

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

199

200 for (unsigned PtrIdx : Group.Members)

202 }

203

204

205

207 GroupToNonAliasingScopes;

208

209 for (const auto &Check : AliasChecks)

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

211

212

213

214

215 for (const auto &Pair : GroupToNonAliasingScopes)

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

217}

218

221 return;

222

223

225

226

227 for (Instruction *I : LAI.getDepChecker().getMemoryInstructions()) {

229 }

230}

231

232std::pair<MDNode *, MDNode *>

235 return {nullptr, nullptr};

236

237 LLVMContext &Context = VersionedLoop->getHeader()->getContext();

241

242 MDNode *AliasScope = nullptr;

243 MDNode *NoAlias = nullptr;

244

245 auto Group = PtrToGroup.find(Ptr);

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

248 OrigInst->getMetadata(LLVMContext::MD_alias_scope),

249 MDNode::get(Context, GroupToScope.lookup(Group->second)));

250

251

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

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

254 NoAlias =

256 NonAliasingScopeList->second);

257 }

258 return {AliasScope, NoAlias};

259}

260

264 if (AliasScopeMD)

265 VersionedInst->setMetadata(LLVMContext::MD_alias_scope, AliasScopeMD);

266

267 if (NoAliasMD)

268 VersionedInst->setMetadata(LLVMContext::MD_noalias, NoAliasMD);

269}

270

271namespace {

274

275

276

278

279 for (Loop *TopLevelLoop : *LI)

281

282 if (L->isInnermost())

284

285

287 for (Loop *L : Worklist) {

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

289 !L->getExitingBlock())

290 continue;

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

297

299 LI, DT, SE);

300 LVer.versionLoop();

301 LVer.annotateLoopWithNoAlias();

304 }

305 }

306

308}

309}

310

317

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

321}

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

static bool runImpl(Function &F, const TargetLowering &TLI, const LibcallLoweringInfo &Libcalls, AssumptionCache *AC)

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"))

This file contains the declarations for profiling metadata utility functions.

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.

LLVM_ABI const DataLayout & getDataLayout() const

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

LLVM_ABI 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.

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

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.

LLVM_ABI void insertBefore(InstListType::iterator InsertPos)

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

LLVM_ABI 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.

LLVM_ABI 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.

LLVM_ABI const LoopAccessInfo & getInfo(Loop &L, bool AllowPartial=false)

Drive the analysis of memory accesses in the loop.

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.

BlockT * getExitBlock() const

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

PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)

Definition LoopVersioning.cpp:311

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...

Definition LoopVersioning.cpp:219

void prepareNoAliasMetadata()

Set up the aliasing scopes based on the memchecks.

Definition LoopVersioning.cpp:178

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

Add the noalias annotations to VersionedInst.

Definition LoopVersioning.cpp:261

void versionLoop()

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

std::pair< MDNode *, MDNode * > getNoAliasMetadataFor(const Instruction *OrigInst) const

Returns a pair containing the alias_scope and noalias metadata nodes for OrigInst,...

Definition LoopVersioning.cpp:233

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

Expects LoopAccessInfo, Loop, LoopInfo, DominatorTree as input.

Definition LoopVersioning.cpp:43

Represents a single loop in the control flow graph.

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 LLVM_ABI MDNode * concatenate(MDNode *A, MDNode *B)

Methods for metadata merging.

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

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...

LLVM_ABI 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.

LLVM_ABI 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

LLVM Value Representation.

LLVM_ABI void setName(const Twine &Name)

Change the name of the value.

LLVM_ABI 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.

FunctionAddr VTableAddr Value

LLVM_ABI 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.

LLVM_ABI void setExplicitlyUnknownBranchWeightsIfProfiled(Instruction &I, StringRef PassName, const Function *F=nullptr)

Like setExplicitlyUnknownBranchWeights(...), but only sets unknown branch weights in the new instruct...

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

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

Put a loop nest into LCSSA form.

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

Clones a loop OrigLoop.

class LLVM_GSL_OWNER SmallVector

Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

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

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

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

Remaps instructions in Blocks using the mapping in VMap.

decltype(auto) cast(const From &Val)

cast - Return the argument parameter cast to the specified type.

LLVM_ABI 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)

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

TrackingVH< Value > PointerValue

Holds the pointer value that we need to check.