util/ra: use adjacency matrix for undirected graph
authorKostiantyn Lazukin <kostiantyn.lazukin@globallogic.com>
Wed, 10 Nov 2021 16:01:09 +0000 (18:01 +0200)
committerMarge Bot <emma+marge@anholt.net>
Tue, 14 Dec 2021 09:19:01 +0000 (09:19 +0000)
commitd4a4cd20d529b4988c55a8b47dc841dae98eb002
tree36bc323b219628f323d28a4a6860647862eb289e
parentf71713d43c08f3b6cc85a304d2fc4bf996a04025
util/ra: use adjacency matrix for undirected graph

Since this graph is actually not oriented, its adjacency matrix can be
represented using less than half bits required by full adjacency matrix.
It reduces memory consumption and number of cache misses. It also simplifies
logic of growing this matrix - no need to touch adjacency bits for previously
allocated number of nodes.

Move adjacency bits from nodes to graph to reduce the number of allocations.

No changes to shader-db.

Reviewed-by: Emma Anholt <emma@anholt.net>
Reviewed-by: Ian Romanick <ian.d.romanick@intel.com>
Signed-off-by: Kostiantyn Lazukin <kostiantyn.lazukin@globallogic.com>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/14189>
src/util/register_allocate.c
src/util/register_allocate_internal.h