SplitKit.cpp revision 8ae0263471cc29c5f8278ee1ea5b678042ec6dce 
1//===---------- SplitKit.cpp - Toolkit for splitting live ranges ----------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file contains the SplitAnalysis class as well as mutator functions for
11// live range splitting.
12//
13//===----------------------------------------------------------------------===//
14
15#define DEBUG_TYPE "splitter"
16#include "SplitKit.h"
17#include "llvm/CodeGen/LiveIntervalAnalysis.h"
18#include "llvm/CodeGen/MachineFunctionPass.h"
19#include "llvm/CodeGen/MachineLoopInfo.h"
20#include "llvm/CodeGen/MachineRegisterInfo.h"
21#include "llvm/Support/Debug.h"
22#include "llvm/Support/raw_ostream.h"
23
24using namespace llvm;
25
26
27//===----------------------------------------------------------------------===//
28//                                 Split Analysis
29//===----------------------------------------------------------------------===//
30
31SplitAnalysis::SplitAnalysis(const MachineFunction *mf,
32                             const LiveIntervals *lis,
33                             const MachineLoopInfo *mli)
34  : mf_(*mf),
35    lis_(*lis),
36    loops_(*mli),
37    curli_(0) {}
38
39void SplitAnalysis::clear() {
40  usingInstrs_.clear();
41  usingBlocks_.clear();
42  usingLoops_.clear();
43}
44
45/// analyseUses - Count instructions, basic blocks, and loops using curli.
46void SplitAnalysis::analyseUses() {
47  const MachineRegisterInfo &MRI = mf_.getRegInfo();
48  for (MachineRegisterInfo::reg_iterator I = MRI.reg_begin(curli_->reg);
49       MachineInstr *MI = I.skipInstruction();) {
50    if (MI->isDebugValue() || !usingInstrs_.insert(MI))
51      continue;
52    MachineBasicBlock *MBB = MI->getParent();
53    if (usingBlocks_[MBB]++)
54      continue;
55    if (MachineLoop *Loop = loops_.getLoopFor(MBB))
56      usingLoops_.insert(Loop);
57  }
58  DEBUG(dbgs() << "Counted "
59               << usingInstrs_.size() << " instrs, "
60               << usingBlocks_.size() << " blocks, "
61               << usingLoops_.size()  << " loops in "
62               << *curli_ << "\n");
63}
64
65SplitAnalysis::LoopPeripheralUse
66SplitAnalysis::analyzeLoopPeripheralUse(const MachineLoop *Loop) {
67  // Peripheral blocks.
68  SmallVector<MachineBasicBlock*, 16> Peri;
69  Loop->getExitBlocks(Peri);
70  if (MachineBasicBlock *PredBB = Loop->getLoopPredecessor())
71    Peri.push_back(PredBB);
72  array_pod_sort(Peri.begin(), Peri.end());
73  Peri.erase(std::unique(Peri.begin(), Peri.end()), Peri.end());
74
75  LoopPeripheralUse use = ContainedInLoop;
76  for (BlockCountMap::iterator I = usingBlocks_.begin(), E = usingBlocks_.end();
77       I != E; ++I) {
78    const MachineBasicBlock *MBB = I->first;
79    // Is this a peripheral block?
80    if (use < MultiPeripheral &&
81        std::binary_search(Peri.begin(), Peri.end(), MBB)) {
82      if (I->second > 1) use = MultiPeripheral;
83      else               use = SinglePeripheral;
84      continue;
85    }
86    // Is it a loop block?
87    if (Loop->contains(MBB))
88      continue;
89    // It must be an unrelated block.
90    return OutsideLoop;
91  }
92  return use;
93}
94
95void SplitAnalysis::analyze(const LiveInterval *li) {
96  clear();
97  curli_ = li;
98  analyseUses();
99}
100
101const MachineLoop *SplitAnalysis::getBestSplitLoop() {
102  LoopPtrSet Loops, SecondLoops;
103
104  // Find first-class and second class candidate loops.
105  // We prefer to split around loops where curli is used outside the periphery.
106  for (LoopPtrSet::const_iterator I = usingLoops_.begin(),
107       E = usingLoops_.end(); I != E; ++I)
108    switch(analyzeLoopPeripheralUse(*I)) {
109    case OutsideLoop:
110      Loops.insert(*I);
111      break;
112    case MultiPeripheral:
113      SecondLoops.insert(*I);
114      break;
115    default:
116      continue;
117    }
118
119  // If there are no first class loops available, look at second class loops.
120  if (Loops.empty())
121    Loops = SecondLoops;
122
123  if (Loops.empty())
124    return 0;
125
126  // Pick the earliest loop.
127  // FIXME: Are there other heuristics to consider?
128  // - avoid breaking critical edges.
129  // - avoid impossible loops.
130  const MachineLoop *Best = 0;
131  SlotIndex BestIdx;
132  for (LoopPtrSet::const_iterator I = Loops.begin(), E = Loops.end(); I != E;
133       ++I) {
134    SlotIndex Idx = lis_.getMBBStartIdx((*I)->getHeader());
135    if (!Best || Idx < BestIdx)
136      Best = *I, BestIdx = Idx;
137  }
138  return Best;
139}
140
141//===----------------------------------------------------------------------===//
142//                               Loop Splitting
143//===----------------------------------------------------------------------===//
144
145bool llvm::splitAroundLoop(SplitAnalysis &sa, const MachineLoop *loop) {
146  return false;
147}
148
149