tree c6e64ebc99a0e8105c8834f45dfe6cda29f4283c
parent 0eba519ccf10df43efabec254e26daf96b3d0541
author Orlando Cazalet-Hyams <orlando.hyams@sony.com> 1571214960 +0000
committer Orlando Cazalet-Hyams <orlando.hyams@sony.com> 1571214960 +0000

[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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@374979 91177308-0d34-0410-b5e6-96231b3b80d8