Improve the accuracy of the upper-bound of the sum of the size of an
HLO and all its dependencies. The previous implementation computed the
size of an HLO as the sum of dependencies weighted by the number of
paths to the each dependency. In the previous implementation the
"size" of some HLO overflowed an int64 for dependence graphs with a
large number of distinct paths. The new implementation computes the
min of the previous overestimate and the sum of all HLO's
before-and-including the current HLO in a topological sort of the
graph.
Both the current and the previous implementations are linear
time. Since the sum of the size of all HLOs will never overflow, the
"total size" of each HLO will never overflow. The new upper-bound is
the min of the previous upper bound and a new heuristic, so it is
always at least as tight a bound as the old implementation.
RELNOTES: n/a
PiperOrigin-RevId:
187948221