LoopExtractor.cpp revision fdded9f95ae6233ec553fd54acc11f2dac1aee9d 
1//===- LoopExtractor.cpp - Extract each loop into a new function ----------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file was developed by the LLVM research group and is distributed under
6// the University of Illinois Open Source License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// A pass wrapper around the ExtractLoop() scalar transformation to extract each
11// top-level loop into its own new function. If the loop is the ONLY loop in a
12// given function, it is not touched. This is a pass most useful for debugging
13// via bugpoint.
14//
15//===----------------------------------------------------------------------===//
16
17#include "llvm/Transforms/IPO.h"
18#include "llvm/iTerminators.h"
19#include "llvm/Module.h"
20#include "llvm/Pass.h"
21#include "llvm/Analysis/Dominators.h"
22#include "llvm/Analysis/LoopInfo.h"
23#include "llvm/Transforms/Scalar.h"
24#include "llvm/Transforms/Utils/FunctionUtils.h"
25using namespace llvm;
26
27namespace {
28  // FIXME: This is not a function pass, but the PassManager doesn't allow
29  // Module passes to require FunctionPasses, so we can't get loop info if we're
30  // not a function pass.
31  struct LoopExtractor : public FunctionPass {
32    unsigned NumLoops;
33
34    LoopExtractor(unsigned numLoops = ~0) : NumLoops(numLoops) {}
35
36    virtual bool runOnFunction(Function &F);
37
38    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
39      AU.addRequiredID(BreakCriticalEdgesID);
40      AU.addRequiredID(LoopSimplifyID);
41      AU.addRequired<DominatorSet>();
42      AU.addRequired<LoopInfo>();
43    }
44  };
45
46  RegisterOpt<LoopExtractor>
47  X("loop-extract", "Extract loops into new functions");
48
49  /// SingleLoopExtractor - For bugpoint.
50  struct SingleLoopExtractor : public LoopExtractor {
51    SingleLoopExtractor() : LoopExtractor(1) {}
52  };
53
54  RegisterOpt<SingleLoopExtractor>
55  Y("loop-extract-single", "Extract at most one loop into a new function");
56} // End anonymous namespace
57
58bool LoopExtractor::runOnFunction(Function &F) {
59  LoopInfo &LI = getAnalysis<LoopInfo>();
60
61  // If this function has no loops, there is nothing to do.
62  if (LI.begin() == LI.end())
63    return false;
64
65  DominatorSet &DS = getAnalysis<DominatorSet>();
66
67  // If there is more than one top-level loop in this function, extract all of
68  // the loops.
69  bool Changed = false;
70  if (LI.end()-LI.begin() > 1) {
71    for (LoopInfo::iterator i = LI.begin(), e = LI.end(); i != e; ++i) {
72      if (NumLoops == 0) return Changed;
73      --NumLoops;
74      Changed |= ExtractLoop(DS, *i) != 0;
75    }
76  } else {
77    // Otherwise there is exactly one top-level loop.  If this function is more
78    // than a minimal wrapper around the loop, extract the loop.
79    Loop *TLL = *LI.begin();
80    bool ShouldExtractLoop = false;
81
82    // Extract the loop if the entry block doesn't branch to the loop header.
83    TerminatorInst *EntryTI = F.getEntryBlock().getTerminator();
84    if (!isa<BranchInst>(EntryTI) ||
85        !cast<BranchInst>(EntryTI)->isUnconditional() ||
86        EntryTI->getSuccessor(0) != TLL->getHeader())
87      ShouldExtractLoop = true;
88    else {
89      // Check to see if any exits from the loop are more than just return
90      // blocks.
91      for (unsigned i = 0, e = TLL->getExitBlocks().size(); i != e; ++i)
92        if (!isa<ReturnInst>(TLL->getExitBlocks()[i]->getTerminator())) {
93          ShouldExtractLoop = true;
94          break;
95        }
96    }
97
98    if (ShouldExtractLoop) {
99      if (NumLoops == 0) return Changed;
100      --NumLoops;
101      Changed |= ExtractLoop(DS, TLL) != 0;
102    } else {
103      // Okay, this function is a minimal container around the specified loop.
104      // If we extract the loop, we will continue to just keep extracting it
105      // infinitely... so don't extract it.  However, if the loop contains any
106      // subloops, extract them.
107      for (Loop::iterator i = TLL->begin(), e = TLL->end(); i != e; ++i) {
108        if (NumLoops == 0) return Changed;
109        --NumLoops;
110        Changed |= ExtractLoop(DS, *i) != 0;
111      }
112    }
113  }
114
115  return Changed;
116}
117
118// createSingleLoopExtractorPass - This pass extracts one natural loop from the
119// program into a function if it can.  This is used by bugpoint.
120//
121Pass *llvm::createSingleLoopExtractorPass() {
122  return new SingleLoopExtractor();
123}
124