/// 1. | o---x | Internal to block. Variable is only live in this block.
/// 2. |---x | Live-in, kill.
/// 3. | o---| Def, live-out.
- /// 4. |---x o---| Live-in, kill, def, live-out.
+ /// 4. |---x o---| Live-in, kill, def, live-out. Counted by NumGapBlocks.
/// 5. |---o---o---| Live-through with uses or defs.
- /// 6. |-----------| Live-through without uses. Transparent.
+ /// 6. |-----------| Live-through without uses. Counted by NumThroughBlocks.
+ ///
+ /// Two BlockInfo entries are created for template 4. One for the live-in
+ /// segment, and one for the live-out segment. These entries look as if the
+ /// block were split in the middle where the live range isn't live.
+ ///
+ /// Live-through blocks without any uses don't get BlockInfo entries. They
+ /// are simply listed in ThroughBlocks instead.
///
struct BlockInfo {
MachineBasicBlock *MBB;
- SlotIndex FirstUse; ///< First instr using current reg.
- SlotIndex LastUse; ///< Last instr using current reg.
- SlotIndex Kill; ///< Interval end point inside block.
- SlotIndex Def; ///< Interval start point inside block.
- bool LiveThrough; ///< Live in whole block (Templ 5. or 6. above).
+ SlotIndex FirstInstr; ///< First instr accessing current reg.
+ SlotIndex LastInstr; ///< Last instr accessing current reg.
+ SlotIndex FirstDef; ///< First non-phi valno->def, or SlotIndex().
bool LiveIn; ///< Current reg is live in.
bool LiveOut; ///< Current reg is live out.
+
+ /// isOneInstr - Returns true when this BlockInfo describes a single
+ /// instruction.
+ bool isOneInstr() const {
+ return SlotIndex::isSameInstr(FirstInstr, LastInstr);
+ }
};
private:
/// UseBlocks - Blocks where CurLI has uses.
SmallVector<BlockInfo, 8> UseBlocks;
+ /// NumGapBlocks - Number of duplicate entries in UseBlocks for blocks where
+ /// the live range has a gap.
+ unsigned NumGapBlocks;
+
/// ThroughBlocks - Block numbers where CurLI is live through without uses.
BitVector ThroughBlocks;
/// NumThroughBlocks - Number of live-through blocks.
unsigned NumThroughBlocks;
+ /// DidRepairRange - analyze was forced to shrinkToUses().
+ bool DidRepairRange;
+
SlotIndex computeLastSplitPoint(unsigned Num);
// Sumarize statistics by counting instructions using CurLI.
/// split.
void analyze(const LiveInterval *li);
+ /// didRepairRange() - Returns true if CurLI was invalid and has been repaired
+ /// by analyze(). This really shouldn't happen, but sometimes the coalescer
+ /// can create live ranges that end in mid-air.
+ bool didRepairRange() const { return DidRepairRange; }
+
/// clear - clear all data structures so SplitAnalysis is ready to analyze a
/// new interval.
void clear();
/// getUseBlocks - Return an array of BlockInfo objects for the basic blocks
/// where CurLI has uses.
- ArrayRef<BlockInfo> getUseBlocks() { return UseBlocks; }
+ ArrayRef<BlockInfo> getUseBlocks() const { return UseBlocks; }
/// getNumThroughBlocks - Return the number of through blocks.
unsigned getNumThroughBlocks() const { return NumThroughBlocks; }
/// getThroughBlocks - Return the set of through blocks.
const BitVector &getThroughBlocks() const { return ThroughBlocks; }
- /// countLiveBlocks - Return the number of blocks where li is live.
- /// This is guaranteed to return the same number as getNumThroughBlocks() +
- /// getUseBlocks().size() after calling analyze(li).
+ /// getNumLiveBlocks - Return the number of blocks where CurLI is live.
+ unsigned getNumLiveBlocks() const {
+ return getUseBlocks().size() - NumGapBlocks + getNumThroughBlocks();
+ }
+
+ /// countLiveBlocks - Return the number of blocks where li is live. This is
+ /// guaranteed to return the same number as getNumLiveBlocks() after calling
+ /// analyze(li).
unsigned countLiveBlocks(const LiveInterval *li) const;
typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet;
- /// getMultiUseBlocks - Add basic blocks to Blocks that may benefit from
- /// having CurLI split to a new live interval. Return true if Blocks can be
- /// passed to SplitEditor::splitSingleBlocks.
- bool getMultiUseBlocks(BlockPtrSet &Blocks);
+ /// shouldSplitSingleBlock - Returns true if it would help to create a local
+ /// live range for the instructions in BI. There is normally no benefit to
+ /// creating a live range for a single instruction, but it does enable
+ /// register class inflation if the instruction has a restricted register
+ /// class.
+ ///
+ /// @param BI The block to be isolated.
+ /// @param SingleInstrs True when single instructions should be isolated.
+ bool shouldSplitSingleBlock(const BlockInfo &BI, bool SingleInstrs) const;
};
/// Return the beginning of the new live range.
SlotIndex enterIntvBefore(SlotIndex Idx);
+ /// enterIntvAfter - Enter the open interval after the instruction at Idx.
+ /// Return the beginning of the new live range.
+ SlotIndex enterIntvAfter(SlotIndex Idx);
+
/// enterIntvAtEnd - Enter the open interval at the end of MBB.
/// Use the open interval from he inserted copy to the MBB end.
/// Return the beginning of the new live range.
/// split, and doesn't call finish().
void splitSingleBlock(const SplitAnalysis::BlockInfo &BI);
- /// splitSingleBlocks - Split CurLI into a separate live interval inside each
- /// basic block in Blocks.
- void splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks);
+ /// splitLiveThroughBlock - Split CurLI in the given block such that it
+ /// enters the block in IntvIn and leaves it in IntvOut. There may be uses in
+ /// the block, but they will be ignored when placing split points.
+ ///
+ /// @param MBBNum Block number.
+ /// @param IntvIn Interval index entering the block.
+ /// @param LeaveBefore When set, leave IntvIn before this point.
+ /// @param IntvOut Interval index leaving the block.
+ /// @param EnterAfter When set, enter IntvOut after this point.
+ void splitLiveThroughBlock(unsigned MBBNum,
+ unsigned IntvIn, SlotIndex LeaveBefore,
+ unsigned IntvOut, SlotIndex EnterAfter);
+
+ /// splitRegInBlock - Split CurLI in the given block such that it enters the
+ /// block in IntvIn and leaves it on the stack (or not at all). Split points
+ /// are placed in a way that avoids putting uses in the stack interval. This
+ /// may require creating a local interval when there is interference.
+ ///
+ /// @param BI Block descriptor.
+ /// @param IntvIn Interval index entering the block. Not 0.
+ /// @param LeaveBefore When set, leave IntvIn before this point.
+ void splitRegInBlock(const SplitAnalysis::BlockInfo &BI,
+ unsigned IntvIn, SlotIndex LeaveBefore);
+
+ /// splitRegOutBlock - Split CurLI in the given block such that it enters the
+ /// block on the stack (or isn't live-in at all) and leaves it in IntvOut.
+ /// Split points are placed to avoid interference and such that the uses are
+ /// not in the stack interval. This may require creating a local interval
+ /// when there is interference.
+ ///
+ /// @param BI Block descriptor.
+ /// @param IntvOut Interval index leaving the block.
+ /// @param EnterAfter When set, enter IntvOut after this point.
+ void splitRegOutBlock(const SplitAnalysis::BlockInfo &BI,
+ unsigned IntvOut, SlotIndex EnterAfter);
};
}