23a0513015
The basic register allocator's priority queue exhibited
non-deterministic behavior when multiple LiveIntervals had identical
spill weights. This caused different register allocation decisions
between ASAN and non-ASAN builds, leading to spurious test failures on
some internal tests.
Root Cause:
The CompSpillWeight comparator only compared spill weights:
```
return A->weight() < B->weight();
```
When two LiveIntervals had equal weights, the comparator returned false
for both comp(A,B) and comp(B,A), making them equivalent in the heap
ordering. The C++ standard does not specify the relative order of
equivalent elements in a heap. In practice, the heap's internal
structure for equivalent elements depends on implementation details and
memory layout. ASAN changes memory layout, leading to different valid
heap configurations and thus different dequeue order.
Fix:
Add an explicit stable tie-breaker using virtual register numbers:
```
return std::tuple(A->weight(), A->reg()) <
std::tuple(B->weight(), B->reg());
```
Register numbers are stable integers independent of memory layout,
ensuring deterministic behavior across all build configurations. When
spill weights are equal, higher-numbered virtual registers are allocated
first, which is equally valid and deterministic.
Test Updates:
Updated test expectations in
CodeGen/AMDGPU/register-killed-error-after-alloc-failure0.mir to reflect
the new deterministic allocation order. When LiveIntervals have equal
spill weights, the allocator now consistently processes them in register
number order rather than in an implementation-defined order.
109 lines
3.8 KiB
C++
109 lines
3.8 KiB
C++
//===-- RegAllocBasic.h - Basic Register Allocator Header -----------------===//
|
|
//
|
|
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
|
|
// See https://llvm.org/LICENSE.txt for license information.
|
|
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
///
|
|
/// \file
|
|
/// This file declares the RABasic class, which provides a minimal
|
|
/// implementation of the basic register allocator.
|
|
///
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
#ifndef LLVM_CODEGEN_REGALLOCBASIC_H
|
|
#define LLVM_CODEGEN_REGALLOCBASIC_H
|
|
|
|
#include "RegAllocBase.h"
|
|
#include "llvm/CodeGen/LiveRangeEdit.h"
|
|
#include "llvm/CodeGen/MachineFunctionPass.h"
|
|
#include "llvm/CodeGen/Spiller.h"
|
|
#include <queue>
|
|
#include <tuple>
|
|
|
|
namespace llvm {
|
|
|
|
struct CompSpillWeight {
|
|
bool operator()(const LiveInterval *A, const LiveInterval *B) const {
|
|
// Compare by weight first, then use register number as a stable tie-breaker
|
|
// to ensure deterministic ordering when the weights are equal.
|
|
return std::tuple(A->weight(), A->reg()) <
|
|
std::tuple(B->weight(), B->reg());
|
|
}
|
|
};
|
|
|
|
/// RABasic provides a minimal implementation of the basic register allocation
|
|
/// algorithm. It prioritizes live virtual registers by spill weight and spills
|
|
/// whenever a register is unavailable. This is not practical in production but
|
|
/// provides a useful baseline both for measuring other allocators and comparing
|
|
/// the speed of the basic algorithm against other styles of allocators.
|
|
class LLVM_LIBRARY_VISIBILITY RABasic : public MachineFunctionPass,
|
|
public RegAllocBase,
|
|
private LiveRangeEdit::Delegate {
|
|
// context
|
|
MachineFunction *MF = nullptr;
|
|
|
|
// state
|
|
std::unique_ptr<Spiller> SpillerInstance;
|
|
std::priority_queue<const LiveInterval *, std::vector<const LiveInterval *>,
|
|
CompSpillWeight>
|
|
Queue;
|
|
|
|
// Scratch space. Allocated here to avoid repeated malloc calls in
|
|
// selectOrSplit().
|
|
BitVector UsableRegs;
|
|
|
|
bool LRE_CanEraseVirtReg(Register) override;
|
|
void LRE_WillShrinkVirtReg(Register) override;
|
|
|
|
public:
|
|
RABasic(const RegAllocFilterFunc F = nullptr);
|
|
|
|
/// Return the pass name.
|
|
StringRef getPassName() const override { return "Basic Register Allocator"; }
|
|
|
|
/// RABasic analysis usage.
|
|
void getAnalysisUsage(AnalysisUsage &AU) const override;
|
|
|
|
void releaseMemory() override;
|
|
|
|
Spiller &spiller() override { return *SpillerInstance; }
|
|
|
|
void enqueueImpl(const LiveInterval *LI) override { Queue.push(LI); }
|
|
|
|
const LiveInterval *dequeue() override {
|
|
if (Queue.empty())
|
|
return nullptr;
|
|
const LiveInterval *LI = Queue.top();
|
|
Queue.pop();
|
|
return LI;
|
|
}
|
|
|
|
MCRegister selectOrSplit(const LiveInterval &VirtReg,
|
|
SmallVectorImpl<Register> &SplitVRegs) override;
|
|
|
|
/// Perform register allocation.
|
|
bool runOnMachineFunction(MachineFunction &mf) override;
|
|
|
|
MachineFunctionProperties getRequiredProperties() const override {
|
|
return MachineFunctionProperties().set(
|
|
MachineFunctionProperties::Property::NoPHIs);
|
|
}
|
|
|
|
MachineFunctionProperties getClearedProperties() const override {
|
|
return MachineFunctionProperties().set(
|
|
MachineFunctionProperties::Property::IsSSA);
|
|
}
|
|
|
|
// Helper for spilling all live virtual registers currently unified under preg
|
|
// that interfere with the most recently queried lvr. Return true if spilling
|
|
// was successful, and append any new spilled/split intervals to splitLVRs.
|
|
bool spillInterferences(const LiveInterval &VirtReg, MCRegister PhysReg,
|
|
SmallVectorImpl<Register> &SplitVRegs);
|
|
|
|
static char ID;
|
|
};
|
|
} // namespace llvm
|
|
#endif
|