#ifndef LLVM_CODEGEN_SPLITKIT_H
#define LLVM_CODEGEN_SPLITKIT_H
+#include "LiveRangeCalc.h"
#include "llvm/ADT/ArrayRef.h"
-#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/IndexedMap.h"
#include "llvm/ADT/IntervalMap.h"
#include "llvm/ADT/SmallPtrSet.h"
-#include "llvm/CodeGen/SlotIndexes.h"
namespace llvm {
class VNInfo;
class raw_ostream;
-/// At some point we should just include MachineDominators.h:
-class MachineDominatorTree;
-template <class NodeT> class DomTreeNodeBase;
-typedef DomTreeNodeBase<MachineBasicBlock> MachineDomTreeNode;
-
-
/// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting
/// opportunities.
class SplitAnalysis {
const TargetInstrInfo &TII;
const TargetRegisterInfo &TRI;
+public:
+
+ /// ComplementSpillMode - Select how the complement live range should be
+ /// created. SplitEditor automatically creates interval 0 to contain
+ /// anything that isn't added to another interval. This complement interval
+ /// can get quite complicated, and it can sometimes be an advantage to allow
+ /// it to overlap the other intervals. If it is going to spill anyway, no
+ /// registers are wasted by keeping a value in two places at the same time.
+ enum ComplementSpillMode {
+ /// SM_Partition(Default) - Try to create the complement interval so it
+ /// doesn't overlap any other intervals, and the original interval is
+ /// partitioned. This may require a large number of back copies and extra
+ /// PHI-defs. Only segments marked with overlapIntv will be overlapping.
+ SM_Partition,
+
+ /// SM_Size - Overlap intervals to minimize the number of inserted COPY
+ /// instructions. Copies to the complement interval are hoisted to their
+ /// common dominator, so only one COPY is required per value in the
+ /// complement interval. This also means that no extra PHI-defs need to be
+ /// inserted in the complement interval.
+ SM_Size,
+
+ /// SM_Speed - Overlap intervals to minimize the expected execution
+ /// frequency of the inserted copies. This is very similar to SM_Size, but
+ /// the complement interval may get some extra PHI-defs.
+ SM_Speed
+ };
+
+private:
+
/// Edit - The current parent register and new intervals created.
LiveRangeEdit *Edit;
/// openIntv will be 1.
unsigned OpenIdx;
+ /// The current spill mode, selected by reset().
+ ComplementSpillMode SpillMode;
+
+ /// Parent interval values where the complement interval may be overlapping
+ /// other intervals.
+ SmallPtrSet<const VNInfo*, 8> OverlappedComplement;
+
typedef IntervalMap<SlotIndex, unsigned> RegAssignMap;
/// Allocator for the interval map. This will eventually be shared with
/// The new value has no live ranges anywhere.
ValueMap Values;
- typedef std::pair<VNInfo*, MachineDomTreeNode*> LiveOutPair;
- typedef IndexedMap<LiveOutPair, MBB2NumberFunctor> LiveOutMap;
-
- // LiveOutCache - Map each basic block where a new register is live out to the
- // live-out value and its defining block.
- // One of these conditions shall be true:
- //
- // 1. !LiveOutCache.count(MBB)
- // 2. LiveOutCache[MBB].second.getNode() == MBB
- // 3. forall P in preds(MBB): LiveOutCache[P] == LiveOutCache[MBB]
- //
- // This is only a cache, the values can be computed as:
- //
- // VNI = Edit.get(RegIdx)->getVNInfoAt(LIS.getMBBEndIdx(MBB))
- // Node = mbt_[LIS.getMBBFromIndex(VNI->def)]
- //
- // The cache is also used as a visited set by extendRange(). It can be shared
- // by all the new registers because at most one is live out of each block.
- LiveOutMap LiveOutCache;
-
- // LiveOutSeen - Indexed by MBB->getNumber(), a bit is set for each valid
- // entry in LiveOutCache.
- BitVector LiveOutSeen;
-
- /// LiveInBlock - Info for updateSSA() about a block where a register is
- /// live-in.
- /// The updateSSA caller provides DomNode and Kill inside MBB, updateSSA()
- /// adds the computed live-in value.
- struct LiveInBlock {
- // Dominator tree node for the block.
- // Cleared by updateSSA when the final value has been determined.
- MachineDomTreeNode *DomNode;
-
- // Live-in value filled in by updateSSA once it is known.
- VNInfo *Value;
-
- // Position in block where the live-in range ends, or SlotIndex() if the
- // range passes through the block.
- SlotIndex Kill;
-
- LiveInBlock(MachineDomTreeNode *node) : DomNode(node), Value(0) {}
- };
+ /// LRCalc - Cache for computing live ranges and SSA update. Each instance
+ /// can only handle non-overlapping live ranges, so use a separate
+ /// LiveRangeCalc instance for the complement interval when in spill mode.
+ LiveRangeCalc LRCalc[2];
- /// LiveInBlocks - List of live-in blocks used by findReachingDefs() and
- /// updateSSA(). This list is usually empty, it exists here to avoid frequent
- /// reallocations.
- SmallVector<LiveInBlock, 16> LiveInBlocks;
+ /// getLRCalc - Return the LRCalc to use for RegIdx. In spill mode, the
+ /// complement interval can overlap the other intervals, so it gets its own
+ /// LRCalc instance. When not in spill mode, all intervals can share one.
+ LiveRangeCalc &getLRCalc(unsigned RegIdx) {
+ return LRCalc[SpillMode != SM_Partition && RegIdx != 0];
+ }
/// defValue - define a value in RegIdx from ParentVNI at Idx.
/// Idx does not have to be ParentVNI->def, but it must be contained within
/// of the number of defs.
void markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI);
+ /// markOverlappedComplement - Mark ParentVNI as being overlapped in the
+ /// complement interval. The complement interval may overlap other intervals
+ /// after overlapIntv has been called, or when in spill mode.
+ void markOverlappedComplement(const VNInfo *ParentVNI);
+
+ /// needsRecompute - Returns true if the live range of ParentVNI needs to be
+ /// recomputed in RegIdx using LiveRangeCalc::extend. This is the case if
+ /// the value has been rematerialized, or when back-copies have been hoisted
+ /// in spill mode.
+ bool needsRecompute(unsigned RegIdx, const VNInfo *ParentVNI);
+
/// defFromParent - Define Reg from ParentVNI at UseIdx using either
/// rematerialization or a COPY from parent. Return the new value.
VNInfo *defFromParent(unsigned RegIdx,
MachineBasicBlock &MBB,
MachineBasicBlock::iterator I);
- /// extendRange - Extend the live range of Edit.get(RegIdx) so it reaches Idx.
- /// Insert PHIDefs as needed to preserve SSA form.
- void extendRange(unsigned RegIdx, SlotIndex Idx);
-
- /// findReachingDefs - Starting from MBB, add blocks to LiveInBlocks until all
- /// reaching defs for LI are found.
- /// @param LI Live interval whose value is needed.
- /// @param MBB Block where LI should be live-in.
- /// @param Kill Kill point in MBB.
- /// @return Unique value seen, or NULL.
- VNInfo *findReachingDefs(LiveInterval *LI, MachineBasicBlock *MBB,
- SlotIndex Kill);
-
- /// updateSSA - Compute and insert PHIDefs such that all blocks in
- // LiveInBlocks get a known live-in value. Add live ranges to the blocks.
- void updateSSA();
-
/// transferValues - Transfer values to the new ranges.
/// Return true if any ranges were skipped.
bool transferValues();
MachineDominatorTree&);
/// reset - Prepare for a new split.
- void reset(LiveRangeEdit&);
+ void reset(LiveRangeEdit&, ComplementSpillMode = SM_Partition);
/// Create a new virtual register and live interval.
/// Return the interval index, starting from 1. Interval index 0 is the
projects / oota-llvm.git / blobdiff