[NFC] Replace a linked list in LiveDebugVariables pass with a DenseMap
authorOrlando Cazalet-Hyams <orlando.hyams@sony.com>
Wed, 16 Oct 2019 08:36:00 +0000 (08:36 +0000)
committerOrlando Cazalet-Hyams <orlando.hyams@sony.com>
Wed, 16 Oct 2019 08:36:00 +0000 (08:36 +0000)
commit8af5ada09319e5a021d57a1a03715b2fd022e415
treeaad38556604ffff181ce12e5f89d01f2cf7de4fd
parent8a5bfbe6db2824642bf9a1d27a24c5b6132b244f
[NFC] Replace a linked list in LiveDebugVariables pass with a DenseMap

In LiveDebugVariables.cpp:
Prior to this patch, UserValues were grouped into linked list chains. Each
chain was the union of two sets: { A: Matching Source variable } or
{ B: Matching virtual register }. A ptr to the heads (or 'leaders')
of each of these chains were kept in a map with the { Source variable } used
as the key (set A predicate) and another with { Virtual register } as key
(set B predicate).

There was a search through the chains in the function getUserValue looking for
UserValues with matching { Source variable, Complex expression, Inlined-at
location }. Essentially searching for a subset of A through two interleaved
linked lists of set A and B. Importantly, by design, the subset will only
contain one or zero elements here. That is to say a UserValue can be uniquely
identified by the tuple { Source variable, Complex expression, Inlined-at
 location } if it exists.

This patch removes the linked list and instead uses a DenseMap to map
the tuple { Source variable, Complex expression, Inlined-at location }
to UserValue ptrs so that the getUserValue search predicate is this map key.
The virtual register map now maps a vreg to a SmallVector<UserVal *> so that
set B is still available for quick searches.

Reviewers: aprantl, probinson, vsk, dblaikie

Reviewed By: aprantl

Subscribers: russell.gallop, gbedwell, bjope, hiraditya, llvm-commits

Tags: #debug-info, #llvm

Differential Revision: https://reviews.llvm.org/D68816

llvm-svn: 374979
llvm/lib/CodeGen/LiveDebugVariables.cpp