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.
95 lines
3.5 KiB
C++
95 lines
3.5 KiB
C++
//===- RegAllocBasicTest.cpp - Tests for basic register allocator --------===//
|
|
//
|
|
// 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
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
#include "../../lib/CodeGen/RegAllocBasic.h"
|
|
#include "llvm/CodeGen/LiveInterval.h"
|
|
#include "gtest/gtest.h"
|
|
#include <queue>
|
|
|
|
using namespace llvm;
|
|
|
|
namespace {
|
|
|
|
TEST(RegAllocBasicTest, CompSpillWeightDeterminism) {
|
|
// Test that CompSpillWeight provides deterministic ordering by testing
|
|
// all valid combinations of weight and register number comparisons.
|
|
//
|
|
// This is a regression test for non-deterministic behavior that occurred
|
|
// when ASAN changed memory layout, causing different heap configurations
|
|
// for LiveIntervals with identical spill weights.
|
|
//
|
|
// Comparison has two components: (weight, register number)
|
|
// Each can be <, =, or > resulting in 9 total combinations, but the case
|
|
// where register is equal and weight is different is impossible because each
|
|
// virtual register has exactly one LiveInterval with one weight.
|
|
|
|
// Create 3 LiveIntervals to test all 7 valid comparison combinations.
|
|
// Layout: W{weight}R{register}
|
|
LiveInterval W1R10(Register::index2VirtReg(10), 1.0f);
|
|
LiveInterval W1R30(Register::index2VirtReg(30), 1.0f);
|
|
LiveInterval W2R20(Register::index2VirtReg(20), 2.0f);
|
|
|
|
CompSpillWeight IsLessThan;
|
|
|
|
// Test all meaningful combinations of (weight comparison, register
|
|
// comparison). IsLessThan(A, B) returns true if A has lower priority than B
|
|
// (A < B in max-heap)
|
|
|
|
// Case 1: weight <, reg < : A has lower priority (weight dominates)
|
|
EXPECT_TRUE(IsLessThan(&W1R10, &W2R20));
|
|
EXPECT_FALSE(IsLessThan(&W2R20, &W1R10));
|
|
|
|
// Case 2: weight <, reg > : A has lower priority (weight dominates)
|
|
EXPECT_TRUE(IsLessThan(&W1R30, &W2R20));
|
|
EXPECT_FALSE(IsLessThan(&W2R20, &W1R30));
|
|
|
|
// Case 3: weight =, reg < : A has lower priority (register breaks tie)
|
|
EXPECT_TRUE(IsLessThan(&W1R10, &W1R30));
|
|
EXPECT_FALSE(IsLessThan(&W1R30, &W1R10));
|
|
|
|
// Case 4: weight =, reg = : equal (both comparisons return false)
|
|
EXPECT_FALSE(IsLessThan(&W1R10, &W1R10));
|
|
|
|
// Case 5: weight =, reg > : A has higher priority (register breaks tie)
|
|
EXPECT_FALSE(IsLessThan(&W1R30, &W1R10));
|
|
EXPECT_TRUE(IsLessThan(&W1R10, &W1R30));
|
|
|
|
// Case 6: weight >, reg < : A has higher priority (weight dominates)
|
|
EXPECT_FALSE(IsLessThan(&W2R20, &W1R30));
|
|
EXPECT_TRUE(IsLessThan(&W1R30, &W2R20));
|
|
|
|
// Case 7: weight >, reg > : A has higher priority (weight dominates)
|
|
EXPECT_FALSE(IsLessThan(&W2R20, &W1R10));
|
|
EXPECT_TRUE(IsLessThan(&W1R10, &W2R20));
|
|
|
|
// Test priority_queue ordering with all intervals
|
|
std::priority_queue<const LiveInterval *, std::vector<const LiveInterval *>,
|
|
CompSpillWeight>
|
|
PQ;
|
|
|
|
// Insert all intervals in arbitrary order
|
|
PQ.push(&W1R30);
|
|
PQ.push(&W2R20);
|
|
PQ.push(&W1R10);
|
|
|
|
// Expected order: highest weight first, then descending register within ties
|
|
// Weight 2.0: R20
|
|
EXPECT_EQ(PQ.top()->reg(), Register::index2VirtReg(20));
|
|
EXPECT_EQ(PQ.top()->weight(), 2.0f);
|
|
PQ.pop();
|
|
|
|
// Weight 1.0: R30, R10 (descending register order)
|
|
EXPECT_EQ(PQ.top()->reg(), Register::index2VirtReg(30));
|
|
EXPECT_EQ(PQ.top()->weight(), 1.0f);
|
|
PQ.pop();
|
|
EXPECT_EQ(PQ.top()->reg(), Register::index2VirtReg(10));
|
|
EXPECT_EQ(PQ.top()->weight(), 1.0f);
|
|
}
|
|
|
|
} // anonymous namespace
|