lib/CodeGen/SplitKit.h

   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 #include "llvm/ADT/SmallPtrSet.h"
  16 #include "llvm/ADT/DenseMap.h"
  17 #include "llvm/CodeGen/SlotIndexes.h"
  18
  19 namespace llvm {
  20
  21 class LiveInterval;
  22 class LiveIntervals;
  23 class MachineDominatorTree;
  24 class MachineInstr;
  25 class MachineLoop;
  26 class MachineLoopInfo;
  27 class MachineRegisterInfo;
  28 class TargetInstrInfo;
  29 class VirtRegMap;
  30 class VNInfo;
  31
  32 /// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting
  33 /// opportunities.
  34 class SplitAnalysis {
  35 public:
  36   const MachineFunction &mf_;
  37   const LiveIntervals &lis_;
  38   const MachineLoopInfo &loops_;
  39   const TargetInstrInfo &tii_;
  40
  41   // Instructions using the the current register.
  42   typedef SmallPtrSet<const MachineInstr*, 16> InstrPtrSet;
  43   InstrPtrSet usingInstrs_;
  44
  45   // The number of instructions using curli in each basic block.
  46   typedef DenseMap<const MachineBasicBlock*, unsigned> BlockCountMap;
  47   BlockCountMap usingBlocks_;
  48
  49   // The number of basic block using curli in each loop.
  50   typedef DenseMap<const MachineLoop*, unsigned> LoopCountMap;
  51   LoopCountMap usingLoops_;
  52
  53 private:
  54   // Current live interval.
  55   const LiveInterval *curli_;
  56
  57   // Sumarize statistics by counting instructions using curli_.
  58   void analyzeUses();
  59
  60   /// canAnalyzeBranch - Return true if MBB ends in a branch that can be
  61   /// analyzed.
  62   bool canAnalyzeBranch(const MachineBasicBlock *MBB);
  63
  64 public:
  65   SplitAnalysis(const MachineFunction &mf, const LiveIntervals &lis,
  66                 const MachineLoopInfo &mli);
  67
  68   /// analyze - set curli to the specified interval, and analyze how it may be
  69   /// split.
  70   void analyze(const LiveInterval *li);
  71
  72   /// removeUse - Update statistics by noting that mi no longer uses curli.
  73   void removeUse(const MachineInstr *mi);
  74
  75   const LiveInterval *getCurLI() { return curli_; }
  76
  77   /// clear - clear all data structures so SplitAnalysis is ready to analyze a
  78   /// new interval.
  79   void clear();
  80
  81   typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet;
  82   typedef SmallPtrSet<const MachineLoop*, 16> LoopPtrSet;
  83
  84   // Sets of basic blocks surrounding a machine loop.
  85   struct LoopBlocks {
  86     BlockPtrSet Loop;  // Blocks in the loop.
  87     BlockPtrSet Preds; // Loop predecessor blocks.
  88     BlockPtrSet Exits; // Loop exit blocks.
  89
  90     void clear() {
  91       Loop.clear();
  92       Preds.clear();
  93       Exits.clear();
  94     }
  95   };
  96
  97   // Calculate the block sets surrounding the loop.
  98   void getLoopBlocks(const MachineLoop *Loop, LoopBlocks &Blocks);
  99
 100   /// LoopPeripheralUse - how is a variable used in and around a loop?
 101   /// Peripheral blocks are the loop predecessors and exit blocks.
 102   enum LoopPeripheralUse {
 103     ContainedInLoop,  // All uses are inside the loop.
 104     SinglePeripheral, // At most one instruction per peripheral block.
 105     MultiPeripheral,  // Multiple instructions in some peripheral blocks.
 106     OutsideLoop       // Uses outside loop periphery.
 107   };
 108
 109   /// analyzeLoopPeripheralUse - Return an enum describing how curli_ is used in
 110   /// and around the Loop.
 111   LoopPeripheralUse analyzeLoopPeripheralUse(const LoopBlocks&);
 112
 113   /// getCriticalExits - It may be necessary to partially break critical edges
 114   /// leaving the loop if an exit block has phi uses of curli. Collect the exit
 115   /// blocks that need special treatment into CriticalExits.
 116   void getCriticalExits(const LoopBlocks &Blocks, BlockPtrSet &CriticalExits);
 117
 118   /// canSplitCriticalExits - Return true if it is possible to insert new exit
 119   /// blocks before the blocks in CriticalExits.
 120   bool canSplitCriticalExits(const LoopBlocks &Blocks,
 121                              BlockPtrSet &CriticalExits);
 122
 123   /// getBestSplitLoop - Return the loop where curli may best be split to a
 124   /// separate register, or NULL.
 125   const MachineLoop *getBestSplitLoop();
 126
 127   /// getMultiUseBlocks - Add basic blocks to Blocks that may benefit from
 128   /// having curli split to a new live interval. Return true if Blocks can be
 129   /// passed to SplitEditor::splitSingleBlocks.
 130   bool getMultiUseBlocks(BlockPtrSet &Blocks);
 131
 132   /// getBlockForInsideSplit - If curli is contained inside a single basic block,
 133   /// and it wou pay to subdivide the interval inside that block, return it.
 134   /// Otherwise return NULL. The returned block can be passed to
 135   /// SplitEditor::splitInsideBlock.
 136   const MachineBasicBlock *getBlockForInsideSplit();
 137 };
 138
 139
 140 /// LiveIntervalMap - Map values from a large LiveInterval into a small
 141 /// interval that is a subset. Insert phi-def values as needed. This class is
 142 /// used by SplitEditor to create new smaller LiveIntervals.
 143 ///
 144 /// parentli_ is the larger interval, li_ is the subset interval. Every value
 145 /// in li_ corresponds to exactly one value in parentli_, and the live range
 146 /// of the value is contained within the live range of the parentli_ value.
 147 /// Values in parentli_ may map to any number of openli_ values, including 0.
 148 class LiveIntervalMap {
 149   LiveIntervals &lis_;
 150   MachineDominatorTree &dt_;
 151
 152   // The parent interval is never changed.
 153   const LiveInterval &parentli_;
 154
 155   // The child interval's values are fully contained inside parentli_ values.
 156   LiveInterval &li_;
 157
 158   typedef DenseMap<const VNInfo*, VNInfo*> ValueMap;
 159
 160   // Map parentli_ values to simple values in li_ that are defined at the same
 161   // SlotIndex, or NULL for parentli_ values that have complex li_ defs.
 162   // Note there is a difference between values mapping to NULL (complex), and
 163   // values not present (unknown/unmapped).
 164   ValueMap valueMap_;
 165
 166   // extendTo - Find the last li_ value defined in MBB at or before Idx. The
 167   // parentli_ is assumed to be live at Idx. Extend the live range to Idx.
 168   // Return the found VNInfo, or NULL.
 169   VNInfo *extendTo(MachineBasicBlock *MBB, SlotIndex Idx);
 170
 171   // addSimpleRange - Add a simple range from parentli_ to li_.
 172   // ParentVNI must be live in the [Start;End) interval.
 173   void addSimpleRange(SlotIndex Start, SlotIndex End, const VNInfo *ParentVNI);
 174
 175 public:
 176   LiveIntervalMap(LiveIntervals &lis,
 177                   MachineDominatorTree &dt,
 178                   const LiveInterval &parentli,
 179                   LiveInterval &li)
 180     : lis_(lis), dt_(dt), parentli_(parentli), li_(li) {}
 181
 182   /// defValue - define a value in li_ from the parentli_ value VNI and Idx.
 183   /// Idx does not have to be ParentVNI->def, but it must be contained within
 184   /// ParentVNI's live range in parentli_.
 185   /// Return the new li_ value.
 186   VNInfo *defValue(const VNInfo *ParentVNI, SlotIndex Idx);
 187
 188   /// mapValue - map ParentVNI to the corresponding li_ value at Idx. It is
 189   /// assumed that ParentVNI is live at Idx.
 190   /// If ParentVNI has not been defined by defValue, it is assumed that
 191   /// ParentVNI->def dominates Idx.
 192   /// If ParentVNI has been defined by defValue one or more times, a value that
 193   /// dominates Idx will be returned. This may require creating extra phi-def
 194   /// values and adding live ranges to li_.
 195   VNInfo *mapValue(const VNInfo *ParentVNI, SlotIndex Idx);
 196
 197   /// addRange - Add live ranges to li_ where [Start;End) intersects parentli_.
 198   /// All needed values whose def is not inside [Start;End) must be defined
 199   /// beforehand so mapValue will work.
 200   void addRange(SlotIndex Start, SlotIndex End);
 201 };
 202
 203
 204 /// SplitEditor - Edit machine code and LiveIntervals for live range
 205 /// splitting.
 206 ///
 207 /// - Create a SplitEditor from a SplitAnalysis.
 208 /// - Start a new live interval with openIntv.
 209 /// - Mark the places where the new interval is entered using enterIntv*
 210 /// - Mark the ranges where the new interval is used with useIntv*
 211 /// - Mark the places where the interval is exited with exitIntv*.
 212 /// - Finish the current interval with closeIntv and repeat from 2.
 213 /// - Rewrite instructions with rewrite().
 214 ///
 215 class SplitEditor {
 216   SplitAnalysis &sa_;
 217   LiveIntervals &lis_;
 218   VirtRegMap &vrm_;
 219   MachineRegisterInfo &mri_;
 220   const TargetInstrInfo &tii_;
 221
 222   /// curli_ - The immutable interval we are currently splitting.
 223   const LiveInterval *const curli_;
 224
 225   /// dupli_ - Created as a copy of curli_, ranges are carved out as new
 226   /// intervals get added through openIntv / closeIntv. This is used to avoid
 227   /// editing curli_.
 228   LiveInterval *dupli_;
 229
 230   /// Currently open LiveInterval.
 231   LiveInterval *openli_;
 232
 233   /// createInterval - Create a new virtual register and LiveInterval with same
 234   /// register class and spill slot as curli.
 235   LiveInterval *createInterval();
 236
 237   /// getDupLI - Ensure dupli is created and return it.
 238   LiveInterval *getDupLI();
 239
 240   /// valueMap_ - Map values in cupli to values in openli. These are direct 1-1
 241   /// mappings, and do not include values created by inserted copies.
 242   DenseMap<const VNInfo*, VNInfo*> valueMap_;
 243
 244   /// mapValue - Return the openIntv value that corresponds to the given curli
 245   /// value.
 246   VNInfo *mapValue(const VNInfo *curliVNI);
 247
 248   /// A dupli value is live through openIntv.
 249   bool liveThrough_;
 250
 251   /// All the new intervals created for this split are added to intervals_.
 252   SmallVectorImpl<LiveInterval*> &intervals_;
 253
 254   /// The index into intervals_ of the first interval we added. There may be
 255   /// others from before we got it.
 256   unsigned firstInterval;
 257
 258   /// Insert a COPY instruction curli -> li. Allocate a new value from li
 259   /// defined by the COPY
 260   VNInfo *insertCopy(LiveInterval &LI,
 261                      MachineBasicBlock &MBB,
 262                      MachineBasicBlock::iterator I);
 263
 264 public:
 265   /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
 266   /// Newly created intervals will be appended to newIntervals.
 267   SplitEditor(SplitAnalysis &SA, LiveIntervals&, VirtRegMap&,
 268               SmallVectorImpl<LiveInterval*> &newIntervals);
 269
 270   /// getAnalysis - Get the corresponding analysis.
 271   SplitAnalysis &getAnalysis() { return sa_; }
 272
 273   /// Create a new virtual register and live interval.
 274   void openIntv();
 275
 276   /// enterIntvBefore - Enter openli before the instruction at Idx. If curli is
 277   /// not live before Idx, a COPY is not inserted.
 278   void enterIntvBefore(SlotIndex Idx);
 279
 280   /// enterIntvAtEnd - Enter openli at the end of MBB.
 281   /// PhiMBB is a successor inside openli where a PHI value is created.
 282   /// Currently, all entries must share the same PhiMBB.
 283   void enterIntvAtEnd(MachineBasicBlock &MBB, MachineBasicBlock &PhiMBB);
 284
 285   /// useIntv - indicate that all instructions in MBB should use openli.
 286   void useIntv(const MachineBasicBlock &MBB);
 287
 288   /// useIntv - indicate that all instructions in range should use openli.
 289   void useIntv(SlotIndex Start, SlotIndex End);
 290
 291   /// leaveIntvAfter - Leave openli after the instruction at Idx.
 292   void leaveIntvAfter(SlotIndex Idx);
 293
 294   /// leaveIntvAtTop - Leave the interval at the top of MBB.
 295   /// Currently, only one value can leave the interval.
 296   void leaveIntvAtTop(MachineBasicBlock &MBB);
 297
 298   /// closeIntv - Indicate that we are done editing the currently open
 299   /// LiveInterval, and ranges can be trimmed.
 300   void closeIntv();
 301
 302   /// rewrite - after all the new live ranges have been created, rewrite
 303   /// instructions using curli to use the new intervals.
 304   void rewrite();
 305
 306   // ===--- High level methods ---===
 307
 308   /// splitAroundLoop - Split curli into a separate live interval inside
 309   /// the loop. Return true if curli has been completely replaced, false if
 310   /// curli is still intact, and needs to be spilled or split further.
 311   bool splitAroundLoop(const MachineLoop*);
 312
 313   /// splitSingleBlocks - Split curli into a separate live interval inside each
 314   /// basic block in Blocks. Return true if curli has been completely replaced,
 315   /// false if curli is still intact, and needs to be spilled or split further.
 316   bool splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks);
 317
 318   /// splitInsideBlock - Split curli into multiple intervals inside MBB. Return
 319   /// true if curli has been completely replaced, false if curli is still
 320   /// intact, and needs to be spilled or split further.
 321   bool splitInsideBlock(const MachineBasicBlock *);
 322 };
 323
 324 }