blob: 85fd3207888b0f19cbd3d5b540162bd01b9f6010 [file] [log] [blame]
//===- RegAllocEvictionAdvisor.h - Interference resolution ------*- C++ -*-===//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
#include "AllocationOrder.h"
#include "llvm/ADT/IndexedMap.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/CodeGen/LiveInterval.h"
#include "llvm/CodeGen/LiveIntervals.h"
#include "llvm/CodeGen/LiveRegMatrix.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Register.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/Pass.h"
namespace llvm {
using SmallVirtRegSet = SmallSet<Register, 16>;
// Live ranges pass through a number of stages as we try to allocate them.
// Some of the stages may also create new live ranges:
// - Region splitting.
// - Per-block splitting.
// - Local splitting.
// - Spilling.
// Ranges produced by one of the stages skip the previous stages when they are
// dequeued. This improves performance because we can skip interference checks
// that are unlikely to give any results. It also guarantees that the live
// range splitting algorithm terminates, something that is otherwise hard to
// ensure.
enum LiveRangeStage {
/// Newly created live range that has never been queued.
/// Only attempt assignment and eviction. Then requeue as RS_Split.
/// Attempt live range splitting if assignment is impossible.
/// Attempt more aggressive live range splitting that is guaranteed to make
/// progress. This is used for split products that may not be making
/// progress.
/// Live range will be spilled. No more splitting will be attempted.
/// Live range is in memory. Because of other evictions, it might get moved
/// in a register in the end.
/// There is nothing more we can do to this live range. Abort compilation
/// if it can't be assigned.
/// Cost of evicting interference - used by default advisor, and the eviction
/// chain heuristic in RegAllocGreedy.
// FIXME: this can be probably made an implementation detail of the default
// advisor, if the eviction chain logic can be refactored.
struct EvictionCost {
unsigned BrokenHints = 0; ///< Total number of broken hints.
float MaxWeight = 0; ///< Maximum spill weight evicted.
EvictionCost() = default;
bool isMax() const { return BrokenHints == ~0u; }
void setMax() { BrokenHints = ~0u; }
void setBrokenHints(unsigned NHints) { BrokenHints = NHints; }
bool operator<(const EvictionCost &O) const {
return std::tie(BrokenHints, MaxWeight) <
std::tie(O.BrokenHints, O.MaxWeight);
} // namespace llvm