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
  18 namespace llvm {
  19
  20 class LiveInterval;
  21 class LiveIntervals;
  22 class MachineBasicBlock;
  23 class MachineInstr;
  24 class MachineFunction;
  25 class MachineFunctionPass;
  26 class MachineLoop;
  27 class MachineLoopInfo;
  28 class TargetInstrInfo;
  29
  30 class SplitAnalysis {
  31   const MachineFunction &mf_;
  32   const LiveIntervals &lis_;
  33   const MachineLoopInfo &loops_;
  34   const TargetInstrInfo &tii_;
  35
  36   // Current live interval.
  37   const LiveInterval *curli_;
  38
  39   // Instructions using the the current register.
  40   typedef SmallPtrSet<const MachineInstr*, 16> InstrPtrSet;
  41   InstrPtrSet usingInstrs_;
  42
  43   // The number of instructions using curli in each basic block.
  44   typedef DenseMap<const MachineBasicBlock*, unsigned> BlockCountMap;
  45   BlockCountMap usingBlocks_;
  46
  47   // Loops where the curent interval is used.
  48   typedef SmallPtrSet<const MachineLoop*, 16> LoopPtrSet;
  49   LoopPtrSet usingLoops_;
  50
  51   // Sumarize statistics by counting instructions using curli_.
  52   void analyzeUses();
  53
  54   /// canAnalyzeBranch - Return true if MBB ends in a branch that can be
  55   /// analyzed.
  56   bool canAnalyzeBranch(const MachineBasicBlock *MBB);
  57
  58 public:
  59   SplitAnalysis(const MachineFunction *mf, const LiveIntervals *lis,
  60                 const MachineLoopInfo *mli);
  61
  62   /// analyze - set curli to the specified interval, and analyze how it may be
  63   /// split.
  64   void analyze(const LiveInterval *li);
  65
  66   /// clear - clear all data structures so SplitAnalysis is ready to analyze a
  67   /// new interval.
  68   void clear();
  69
  70   typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet;
  71
  72   // Sets of basic blocks surrounding a machine loop.
  73   struct LoopBlocks {
  74     BlockPtrSet Loop;  // Blocks in the loop.
  75     BlockPtrSet Preds; // Loop predecessor blocks.
  76     BlockPtrSet Exits; // Loop exit blocks.
  77
  78     void clear() {
  79       Loop.clear();
  80       Preds.clear();
  81       Exits.clear();
  82     }
  83   };
  84
  85   // Calculate the block sets surrounding the loop.
  86   void getLoopBlocks(const MachineLoop *Loop, LoopBlocks &Blocks);
  87
  88   /// LoopPeripheralUse - how is a variable used in and around a loop?
  89   /// Peripheral blocks are the loop predecessors and exit blocks.
  90   enum LoopPeripheralUse {
  91     ContainedInLoop,  // All uses are inside the loop.
  92     SinglePeripheral, // At most one instruction per peripheral block.
  93     MultiPeripheral,  // Multiple instructions in some peripheral blocks.
  94     OutsideLoop       // Uses outside loop periphery.
  95   };
  96
  97   /// analyzeLoopPeripheralUse - Return an enum describing how curli_ is used in
  98   /// and around the Loop.
  99   LoopPeripheralUse analyzeLoopPeripheralUse(const LoopBlocks&);
 100
 101   /// getCriticalExits - It may be necessary to partially break critical edges
 102   /// leaving the loop if an exit block has phi uses of curli. Collect the exit
 103   /// blocks that need special treatment into CriticalExits.
 104   void getCriticalExits(const LoopBlocks &Blocks, BlockPtrSet &CriticalExits);
 105
 106   /// canSplitCriticalExits - Return true if it is possible to insert new exit
 107   /// blocks before the blocks in CriticalExits.
 108   bool canSplitCriticalExits(const LoopBlocks &Blocks,
 109                              BlockPtrSet &CriticalExits);
 110
 111   /// getBestSplitLoop - Return the loop where curli may best be split to a
 112   /// separate register, or NULL.
 113   const MachineLoop *getBestSplitLoop();
 114 };
 115
 116 /// splitAroundLoop - Try to split curli into a separate live interval inside
 117 /// the loop. Retun true on success.
 118 bool splitAroundLoop(SplitAnalysis&, const MachineLoop*);
 119
 120 }