tree 16fd447977385d81ea0c41810cb3a38e3736a12a
parent fe4190f809fe26698d1a071cc6a8c5f9a26669c0
author Justin Lebar <jlebar@google.com> 1640214035 -0800
committer TensorFlower Gardener <gardener@tensorflow.org> 1640214910 -0800

Fix O(n^2) behavior in HLO parser.

This issue was introduced by my previous change to allow nested instructions in
HLO text.

Previously, we tried to parse each operand as an instruction.  If that failed,
it would generate an error, which we'd discard.  We'd then try parsing as a
normal operand.

The issue is that generating an error calls HLoLexer::GetLineAndColumn(), which
is O(n) in the length of the input text.  Therefore generating n "normal"
operands is O(n^2).  Oops.

We fix this by switching the order that we try things in.  First we try as a
normal instruction name, and only if that fails do we try as a nested
instruction.

Careful readers will observe that this doesn't actually fix the O(n^2)
behavior, it just changes it: Now we're O(n^2) in the number of nested
instructions we have, instead of the number of traditional operands.

But our HLO dumping doesn't generate nested instructions -- and probably never
will, because you can't while being strictly isomorphic to an HloModule's
contents.  In practice, you only get nested HLOs when writing text by hand.
Such inputs will be small enough that the O(n^2) behavior shouldn't be a
problem.

While we're here, we also fix a TODO and generate better error messages.  Now
if parsing fails, we tell the user why it failed as both a vanilla operand and
a nested instruction.

PiperOrigin-RevId: 417891461
Change-Id: Icfe7fe510c4edbfd5ee35c688d94127f43c67b24