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 LiveRangeEdit;
  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   const LiveInterval *getCurLI() { return curli_; }
  73
  74   /// clear - clear all data structures so SplitAnalysis is ready to analyze a
  75   /// new interval.
  76   void clear();
  77
  78   typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet;
  79   typedef SmallPtrSet<const MachineLoop*, 16> LoopPtrSet;
  80
  81   // Sets of basic blocks surrounding a machine loop.
  82   struct LoopBlocks {
  83     BlockPtrSet Loop;  // Blocks in the loop.
  84     BlockPtrSet Preds; // Loop predecessor blocks.
  85     BlockPtrSet Exits; // Loop exit blocks.
  86
  87     void clear() {
  88       Loop.clear();
  89       Preds.clear();
  90       Exits.clear();
  91     }
  92   };
  93
  94   // Calculate the block sets surrounding the loop.
  95   void getLoopBlocks(const MachineLoop *Loop, LoopBlocks &Blocks);
  96
  97   /// LoopPeripheralUse - how is a variable used in and around a loop?
  98   /// Peripheral blocks are the loop predecessors and exit blocks.
  99   enum LoopPeripheralUse {
 100     ContainedInLoop,  // All uses are inside the loop.
 101     SinglePeripheral, // At most one instruction per peripheral block.
 102     MultiPeripheral,  // Multiple instructions in some peripheral blocks.
 103     OutsideLoop       // Uses outside loop periphery.
 104   };
 105
 106   /// analyzeLoopPeripheralUse - Return an enum describing how curli_ is used in
 107   /// and around the Loop.
 108   LoopPeripheralUse analyzeLoopPeripheralUse(const LoopBlocks&);
 109
 110   /// getCriticalExits - It may be necessary to partially break critical edges
 111   /// leaving the loop if an exit block has phi uses of curli. Collect the exit
 112   /// blocks that need special treatment into CriticalExits.
 113   void getCriticalExits(const LoopBlocks &Blocks, BlockPtrSet &CriticalExits);
 114
 115   /// canSplitCriticalExits - Return true if it is possible to insert new exit
 116   /// blocks before the blocks in CriticalExits.
 117   bool canSplitCriticalExits(const LoopBlocks &Blocks,
 118                              BlockPtrSet &CriticalExits);
 119
 120   /// getBestSplitLoop - Return the loop where curli may best be split to a
 121   /// separate register, or NULL.
 122   const MachineLoop *getBestSplitLoop();
 123
 124   /// getMultiUseBlocks - Add basic blocks to Blocks that may benefit from
 125   /// having curli split to a new live interval. Return true if Blocks can be
 126   /// passed to SplitEditor::splitSingleBlocks.
 127   bool getMultiUseBlocks(BlockPtrSet &Blocks);
 128
 129   /// getBlockForInsideSplit - If curli is contained inside a single basic block,
 130   /// and it wou pay to subdivide the interval inside that block, return it.
 131   /// Otherwise return NULL. The returned block can be passed to
 132   /// SplitEditor::splitInsideBlock.
 133   const MachineBasicBlock *getBlockForInsideSplit();
 134 };
 135
 136
 137 /// LiveIntervalMap - Map values from a large LiveInterval into a small
 138 /// interval that is a subset. Insert phi-def values as needed. This class is
 139 /// used by SplitEditor to create new smaller LiveIntervals.
 140 ///
 141 /// parentli_ is the larger interval, li_ is the subset interval. Every value
 142 /// in li_ corresponds to exactly one value in parentli_, and the live range
 143 /// of the value is contained within the live range of the parentli_ value.
 144 /// Values in parentli_ may map to any number of openli_ values, including 0.
 145 class LiveIntervalMap {
 146   LiveIntervals &lis_;
 147
 148   // The parent interval is never changed.
 149   const LiveInterval &parentli_;
 150
 151   // The child interval's values are fully contained inside parentli_ values.
 152   LiveInterval *li_;
 153
 154   typedef DenseMap<const VNInfo*, VNInfo*> ValueMap;
 155
 156   // Map parentli_ values to simple values in li_ that are defined at the same
 157   // SlotIndex, or NULL for parentli_ values that have complex li_ defs.
 158   // Note there is a difference between values mapping to NULL (complex), and
 159   // values not present (unknown/unmapped).
 160   ValueMap valueMap_;
 161
 162 public:
 163   LiveIntervalMap(LiveIntervals &lis,
 164                   const LiveInterval &parentli)
 165     : lis_(lis), parentli_(parentli), li_(0) {}
 166
 167   /// reset - clear all data structures and start a new live interval.
 168   void reset(LiveInterval *);
 169
 170   /// getLI - return the current live interval.
 171   LiveInterval *getLI() const { return li_; }
 172
 173   /// defValue - define a value in li_ from the parentli_ value VNI and Idx.
 174   /// Idx does not have to be ParentVNI->def, but it must be contained within
 175   /// ParentVNI's live range in parentli_.
 176   /// Return the new li_ value.
 177   VNInfo *defValue(const VNInfo *ParentVNI, SlotIndex Idx);
 178
 179   /// mapValue - map ParentVNI to the corresponding li_ value at Idx. It is
 180   /// assumed that ParentVNI is live at Idx.
 181   /// If ParentVNI has not been defined by defValue, it is assumed that
 182   /// ParentVNI->def dominates Idx.
 183   /// If ParentVNI has been defined by defValue one or more times, a value that
 184   /// dominates Idx will be returned. This may require creating extra phi-def
 185   /// values and adding live ranges to li_.
 186   /// If simple is not NULL, *simple will indicate if ParentVNI is a simply
 187   /// mapped value.
 188   VNInfo *mapValue(const VNInfo *ParentVNI, SlotIndex Idx, bool *simple = 0);
 189
 190   // extendTo - Find the last li_ value defined in MBB at or before Idx. The
 191   // parentli is assumed to be live at Idx. Extend the live range to include
 192   // Idx. Return the found VNInfo, or NULL.
 193   VNInfo *extendTo(MachineBasicBlock *MBB, SlotIndex Idx);
 194
 195   /// isMapped - Return true is ParentVNI is a known mapped value. It may be a
 196   /// simple 1-1 mapping or a complex mapping to later defs.
 197   bool isMapped(const VNInfo *ParentVNI) const {
 198     return valueMap_.count(ParentVNI);
 199   }
 200
 201   /// isComplexMapped - Return true if ParentVNI has received new definitions
 202   /// with defValue.
 203   bool isComplexMapped(const VNInfo *ParentVNI) const;
 204
 205   // addSimpleRange - Add a simple range from parentli_ to li_.
 206   // ParentVNI must be live in the [Start;End) interval.
 207   void addSimpleRange(SlotIndex Start, SlotIndex End, const VNInfo *ParentVNI);
 208
 209   /// addRange - Add live ranges to li_ where [Start;End) intersects parentli_.
 210   /// All needed values whose def is not inside [Start;End) must be defined
 211   /// beforehand so mapValue will work.
 212   void addRange(SlotIndex Start, SlotIndex End);
 213
 214   /// defByCopyFrom - Insert a copy from Reg to li, assuming that Reg carries
 215   /// ParentVNI. Add a minimal live range for the new value and return it.
 216   VNInfo *defByCopyFrom(unsigned Reg,
 217                         const VNInfo *ParentVNI,
 218                         MachineBasicBlock &MBB,
 219                         MachineBasicBlock::iterator I);
 220
 221 };
 222
 223
 224 /// SplitEditor - Edit machine code and LiveIntervals for live range
 225 /// splitting.
 226 ///
 227 /// - Create a SplitEditor from a SplitAnalysis.
 228 /// - Start a new live interval with openIntv.
 229 /// - Mark the places where the new interval is entered using enterIntv*
 230 /// - Mark the ranges where the new interval is used with useIntv*
 231 /// - Mark the places where the interval is exited with exitIntv*.
 232 /// - Finish the current interval with closeIntv and repeat from 2.
 233 /// - Rewrite instructions with finish().
 234 ///
 235 class SplitEditor {
 236   SplitAnalysis &sa_;
 237   LiveIntervals &lis_;
 238   VirtRegMap &vrm_;
 239   MachineRegisterInfo &mri_;
 240   const TargetInstrInfo &tii_;
 241
 242   /// edit_ - The current parent register and new intervals created.
 243   LiveRangeEdit &edit_;
 244
 245   /// curli_ - The immutable interval we are currently splitting.
 246   const LiveInterval *const curli_;
 247
 248   /// dupli_ - Created as a copy of curli_, ranges are carved out as new
 249   /// intervals get added through openIntv / closeIntv. This is used to avoid
 250   /// editing curli_.
 251   LiveIntervalMap dupli_;
 252
 253   /// Currently open LiveInterval.
 254   LiveIntervalMap openli_;
 255
 256   /// intervalsLiveAt - Return true if any member of intervals_ is live at Idx.
 257   bool intervalsLiveAt(SlotIndex Idx) const;
 258
 259   /// Values in curli whose live range has been truncated when entering an open
 260   /// li.
 261   SmallPtrSet<const VNInfo*, 8> truncatedValues;
 262
 263   /// addTruncSimpleRange - Add the given simple range to dupli_ after
 264   /// truncating any overlap with intervals_.
 265   void addTruncSimpleRange(SlotIndex Start, SlotIndex End, VNInfo *VNI);
 266
 267   /// computeRemainder - Compute the dupli liveness as the complement of all the
 268   /// new intervals.
 269   void computeRemainder();
 270
 271   /// rewrite - Rewrite all uses of reg to use the new registers.
 272   void rewrite(unsigned reg);
 273
 274 public:
 275   /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
 276   /// Newly created intervals will be appended to newIntervals.
 277   SplitEditor(SplitAnalysis &SA, LiveIntervals&, VirtRegMap&, LiveRangeEdit&);
 278
 279   /// getAnalysis - Get the corresponding analysis.
 280   SplitAnalysis &getAnalysis() { return sa_; }
 281
 282   /// Create a new virtual register and live interval.
 283   void openIntv();
 284
 285   /// enterIntvBefore - Enter openli before the instruction at Idx. If curli is
 286   /// not live before Idx, a COPY is not inserted.
 287   void enterIntvBefore(SlotIndex Idx);
 288
 289   /// enterIntvAtEnd - Enter openli at the end of MBB.
 290   void enterIntvAtEnd(MachineBasicBlock &MBB);
 291
 292   /// useIntv - indicate that all instructions in MBB should use openli.
 293   void useIntv(const MachineBasicBlock &MBB);
 294
 295   /// useIntv - indicate that all instructions in range should use openli.
 296   void useIntv(SlotIndex Start, SlotIndex End);
 297
 298   /// leaveIntvAfter - Leave openli after the instruction at Idx.
 299   void leaveIntvAfter(SlotIndex Idx);
 300
 301   /// leaveIntvAtTop - Leave the interval at the top of MBB.
 302   /// Currently, only one value can leave the interval.
 303   void leaveIntvAtTop(MachineBasicBlock &MBB);
 304
 305   /// closeIntv - Indicate that we are done editing the currently open
 306   /// LiveInterval, and ranges can be trimmed.
 307   void closeIntv();
 308
 309   /// finish - after all the new live ranges have been created, compute the
 310   /// remaining live range, and rewrite instructions to use the new registers.
 311   void finish();
 312
 313   // ===--- High level methods ---===
 314
 315   /// splitAroundLoop - Split curli into a separate live interval inside
 316   /// the loop.
 317   void splitAroundLoop(const MachineLoop*);
 318
 319   /// splitSingleBlocks - Split curli into a separate live interval inside each
 320   /// basic block in Blocks.
 321   void splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks);
 322
 323   /// splitInsideBlock - Split curli into multiple intervals inside MBB.
 324   void splitInsideBlock(const MachineBasicBlock *);
 325 };
 326
 327 }