[ConstraintSystem] Use sparse representation for constraints. (NFC)
authorFlorian Hahn <flo@fhahn.com>
Thu, 16 Feb 2023 14:44:49 +0000 (14:44 +0000)
committerFlorian Hahn <flo@fhahn.com>
Thu, 16 Feb 2023 14:44:49 +0000 (14:44 +0000)
commitb32b7068ef8e6e9b34e7e85f5c1b76b01b28755a
tree36d9b8d3e0a5bbd58b276de150f80d41125501b8
parent66749ce92707b578a17b36cb479ae44cdc314640
[ConstraintSystem] Use sparse representation for constraints. (NFC)

Update ConstraintSystem to use a sparse representation for entries in a
row. Most rows only contain a small number of variables, so the sparse
representation can result in significant speedups.

For a large test case from D135915, it halves the time spent in
ConstraintElimination.

To ensure this returns the same results as the old implementation in all
cases, I built a large set of projects with an extra assertion that it
produces the same result as the old implementation.
llvm/include/llvm/Analysis/ConstraintSystem.h
llvm/lib/Analysis/ConstraintSystem.cpp