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();

65 VersionedLoop->getHeader()->getDataLayout(),

66 "induction");

68 VersionedLoop, AliasChecks, Exp2);

71 "scev.check");

72 SCEVRuntimeCheck =

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

78 if (MemRuntimeCheck && SCEVRuntimeCheck) {

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

80 RuntimeCheck =

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

82 } else

83 RuntimeCheck = MemRuntimeCheck ? MemRuntimeCheck : SCEVRuntimeCheck;

85 Exp.eraseDeadInstructions(SCEVRuntimeCheck);

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

88 "any runtime checks");

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

92 ".lver.check");

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

100

101

102

103

105 NonVersionedLoop =

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

109

110

112 Builder.SetInsertPoint(OrigTerm);

113 auto *BI =

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

115 VersionedLoop->getLoopPreheader());

116

117

120

121

122

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

124

125

126

127 addPHINodes(DefsUsedOutside);

130 assert(NonVersionedLoop->isLoopSimplifyForm() &&

131 VersionedLoop->isLoopSimplifyForm() &&

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

133}

134

135void LoopVersioning::addPHINodes(

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

140

141

142

143 for (auto *Inst : DefsUsedOutside) {

144

145

149 break;

150 }

151 }

152

153 if (!PN) {

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

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

160 for (User *U : UsersToUpdate)

161 U->replaceUsesOfWith(Inst, PN);

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

163 }

164 }

165

166

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

170

171

173 auto Mapped = VMap.find(ClonedValue);

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

175 ClonedValue = Mapped->second;

176

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

178 }

179}

180

182

183

184

185

186

187

188

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

191

192

193

194

195

196

199

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

202

203 for (unsigned PtrIdx : Group.Members)

205 }

206

207

208

210 GroupToNonAliasingScopes;

211

212 for (const auto &Check : AliasChecks)

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

214

215

216

217

218 for (const auto &Pair : GroupToNonAliasingScopes)

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

220}

221

224 return;

225

226

228

229

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

232 }

233}

234

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

238 return {nullptr, nullptr};

239

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

244

245 MDNode *AliasScope = nullptr;

246 MDNode *NoAlias = nullptr;

247

248 auto Group = PtrToGroup.find(Ptr);

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

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

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

253

254

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

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

257 NoAlias =

259 NonAliasingScopeList->second);

260 }

261 return {AliasScope, NoAlias};

262}

263

267 if (AliasScopeMD)

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

269

270 if (NoAliasMD)

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

272}

273

274namespace {

277

278

279

281

282 for (Loop *TopLevelLoop : *LI)

284

285 if (L->isInnermost())

287

288

290 for (Loop *L : Worklist) {

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

292 !L->getExitingBlock())

293 continue;

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

300

302 LI, DT, SE);

303 LVer.versionLoop();

304 LVer.annotateLoopWithNoAlias();

307 }

308 }

309

311}

312}

313

320

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

324}

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:314

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:222

void prepareNoAliasMetadata()

Set up the aliasing scopes based on the memchecks.

Definition LoopVersioning.cpp:181

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

Add the noalias annotations to VersionedInst.

Definition LoopVersioning.cpp:264

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:236

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.