LoopExtractor.cpp Source File (original) (raw)

29using namespace llvm;

31#define DEBUG_TYPE "loop-extract"

33 STATISTIC(NumExtracted, "Number of loops extracted");

35namespace {

36struct LoopExtractorLegacyPass : public ModulePass {

37 static char ID;

39 unsigned NumLoops;

41 explicit LoopExtractorLegacyPass(unsigned NumLoops = ~0)

44 }

46 bool runOnModule(Module &M) override;

48 void getAnalysisUsage(AnalysisUsage &AU) const override {

50 AU.addRequired();

55 }

56};

58struct LoopExtractor {

59 explicit LoopExtractor(

60 unsigned NumLoops,

61 function_ref<DominatorTree &(Function &)> LookupDomTree,

62 function_ref<LoopInfo &(Function &)> LookupLoopInfo,

63 function_ref<AssumptionCache *(Function &)> LookupAssumptionCache)

64 : NumLoops(NumLoops), LookupDomTree(LookupDomTree),

65 LookupLoopInfo(LookupLoopInfo),

66 LookupAssumptionCache(LookupAssumptionCache) {}

67 bool runOnModule(Module &M);

69private:

71 unsigned NumLoops;

73 function_ref<DominatorTree &(Function &)> LookupDomTree;

74 function_ref<LoopInfo &(Function &)> LookupLoopInfo;

75 function_ref<AssumptionCache *(Function &)> LookupAssumptionCache;

79 bool extractLoops(Loop::iterator From, Loop::iterator To, LoopInfo &LI,

80 DominatorTree &DT);

81 bool extractLoop(Loop *L, LoopInfo &LI, DominatorTree &DT);

82};

83}

85char LoopExtractorLegacyPass::ID = 0;

87 "Extract loops into new functions", false, false)

93 "Extract loops into new functions", false, false)

95namespace {

101}

102

103char SingleLoopExtractor::ID = 0;

105 "Extract at most one loop into a new function", false, false)

106

107

108

109

111

112bool LoopExtractorLegacyPass::runOnModule(Module &M) {

113 if (skipModule(M))

114 return false;

115

117 auto LookupDomTree = [this](Function &F) -> DominatorTree & {

118 return this->getAnalysis(F).getDomTree();

119 };

120 auto LookupLoopInfo = [this, &Changed](Function &F) -> LoopInfo & {

121 return this->getAnalysis(F, &Changed).getLoopInfo();

122 };

123 auto LookupACT = [this](Function &F) -> AssumptionCache * {

124 if (auto *ACT = this->getAnalysisIfAvailable())

125 return ACT->lookupAssumptionCache(F);

126 return nullptr;

127 };

128 return LoopExtractor(NumLoops, LookupDomTree, LookupLoopInfo, LookupACT)

129 .runOnModule(M) ||

131}

132

133bool LoopExtractor::runOnModule(Module &M) {

134 if (M.empty())

135 return false;

136

137 if (!NumLoops)

138 return false;

139

141

142

143

144 auto I = M.begin(), E = --M.end();

145 while (true) {

147

149 if (!NumLoops)

150 break;

151

152

153 if (I == E)

154 break;

155

156 ++I;

157 }

159}

160

161bool LoopExtractor::runOnFunction(Function &F) {

162

163 if (F.hasOptNone())

164 return false;

165

166 if (F.empty())

167 return false;

168

170 LoopInfo &LI = LookupLoopInfo(F);

171

172

175

176 DominatorTree &DT = LookupDomTree(F);

177

178

179

180 if (std::next(LI.begin()) != LI.end())

181 return Changed | extractLoops(LI.begin(), LI.end(), LI, DT);

182

183

184 Loop *TLL = *LI.begin();

185

186

187

189 bool ShouldExtractLoop = false;

190

191

192 Instruction *EntryTI = F.getEntryBlock().getTerminator();

196 ShouldExtractLoop = true;

197 } else {

198

199

200 SmallVector<BasicBlock *, 8> ExitBlocks;

202 for (auto *ExitBlock : ExitBlocks)

204 ShouldExtractLoop = true;

205 break;

206 }

207 }

208

209 if (ShouldExtractLoop)

210 return Changed | extractLoop(TLL, LI, DT);

211 }

212

213

214

215

216

217 return Changed | extractLoops(TLL->begin(), TLL->end(), LI, DT);

218}

219

220bool LoopExtractor::extractLoops(Loop::iterator From, Loop::iterator To,

221 LoopInfo &LI, DominatorTree &DT) {

223 SmallVector<Loop *, 8> Loops;

224

225

226 Loops.assign(From, To);

227 for (Loop *L : Loops) {

228

229 if (->isLoopSimplifyForm())

230 continue;

231

232 Changed |= extractLoop(L, LI, DT);

233 if (!NumLoops)

234 break;

235 }

237}

238

239bool LoopExtractor::extractLoop(Loop *L, LoopInfo &LI, DominatorTree &DT) {

240 assert(NumLoops != 0);

242 AssumptionCache *AC = LookupAssumptionCache(Func);

243 CodeExtractorAnalysisCache CEAC(Func);

244 CodeExtractor Extractor(L->getBlocks(), &DT, false, nullptr, nullptr, AC);

245 if (Extractor.extractCodeRegion(CEAC)) {

247 --NumLoops;

248 ++NumExtracted;

249 return true;

250 }

251 return false;

252}

253

254

255

256

258 return new SingleLoopExtractor();

259}

260

265 };

268 };

271 };

272 if (!LoopExtractor(NumLoops, LookupDomTree, LookupLoopInfo,

273 LookupAssumptionCache)

274 .runOnModule(M))

276

279 return PA;

280}

281

285 OS, MapClassName2PassName);

286 OS << '<';

287 if (NumLoops == 1)

288 OS << "single";

289 OS << '>';

290}

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

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

static bool runOnFunction(Function &F, bool PostInlining)

Module.h This file contains the declarations for the Module class.

This header defines various interfaces for pass management in LLVM.

Machine Check Debug Module

FunctionAnalysisManager FAM

#define INITIALIZE_PASS_DEPENDENCY(depName)

#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)

#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)

#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

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

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

LLVM_ABI AnalysisUsage & addRequiredID(const void *ID)

AnalysisUsage & addUsedIfAvailable()

Add the specified Pass class to the set of analyses used by this pass.

AnalysisUsage & addRequired()

AnalysisUsage & addPreserved()

Add the specified Pass class to the set of analyses preserved by this pass.

A function analysis which provides an AssumptionCache.

A cache of @llvm.assume calls within a function.

Analysis pass which computes a DominatorTree.

Legacy analysis pass which computes a DominatorTree.

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

LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY

Return the specified successor. This instruction must be a terminator.

Analysis pass that exposes the LoopInfo for a function.

void getExitBlocks(SmallVectorImpl< BlockT * > &ExitBlocks) const

Return all of the successor blocks of this loop.

BlockT * getHeader() const

The legacy pass manager's analysis pass to compute loop information.

LLVM_ABI void erase(Loop *L)

Update LoopInfo after removing the last backedge from a loop.

bool isLoopSimplifyForm() const

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

ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...

A Module instance is used to store all the information related to an LLVM module.

static LLVM_ABI PassRegistry * getPassRegistry()

getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...

Pass interface - Implemented by all 'passes'.

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

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

PreservedAnalyses & preserve()

Mark an analysis as preserved.

StringRef - Represent a constant reference to a string, i.e.

An efficient, type-erasing, non-owning reference to a callable.

This class implements an extremely fast bulk output stream that can only output to a stream.

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

NodeAddr< FuncNode * > Func

friend class Instruction

Iterator for Instructions in a `BasicBlock.

This is an optimization pass for GlobalISel generic memory operations.

InnerAnalysisManagerProxy< FunctionAnalysisManager, Module > FunctionAnalysisManagerModuleProxy

Provide the FunctionAnalysisManager to Module proxy.

LLVM_ABI char & LoopSimplifyID

LLVM_ABI Pass * createLoopExtractorPass()

createLoopExtractorPass - This pass extracts all natural loops from the program into a function if it...

LLVM_ABI char & BreakCriticalEdgesID

LLVM_ABI Pass * createSingleLoopExtractorPass()

createSingleLoopExtractorPass - This pass extracts one natural loop from the program into a function ...

Definition LoopExtractor.cpp:257

bool isa(const From &Val)

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

decltype(auto) cast(const From &Val)

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

LLVM_ABI void initializeLoopExtractorLegacyPassPass(PassRegistry &)

AnalysisManager< Module > ModuleAnalysisManager

Convenience typedef for the Module analysis manager.

A CRTP mix-in to automatically provide informational APIs needed for passes.