Link-Time Optimization (LTO) is a mechanism that enables the compiler to
optimize across translation unit boundaries. In particular, it enables
cross-file function inlining. This is present and mature in the majority of
contemporary compilers and switching it on has few downsides.
¹ The test case from https://gitlab.com/graphviz/graphviz/-/issues/1652 run as
`neato -Tsvg -o /dev/null 1652.dot`.
² swedish-flat.dot Magnus attached to
https://gitlab.com/graphviz/graphviz/-/issues/1718 run as
`circo -Tsvg -o /dev/null swedish-flag.dot`.
³ The test case from https://gitlab.com/graphviz/graphviz/-/issues/1864 run as
`twopi -Tsvg -o /dev/null 1864.dot`.
⁴ The test case from https://gitlab.com/graphviz/graphviz/-/issues/2064 run as
`dot -Gnslimit=2 -Gnslimit1=2 -Gmaxiter=5000 -Tsvg -o /dev/null 2064.dot`.
⁵ The tests/2095.dot test case from prior to minimization
(3819821ea70fae730dd224936628ed3929b03531). Run as
`dot -Tsvg -o /dev/null 2095.dot`.
pathplan: replace unchecked allocation calls with cgraph wrappers
After the prior UB fixes, the #1999 example bottoms out in this code, failing
the second allocation call while trying to allocate ~938GB. The return values
for neither of these calls were checked, resulting in messy crashes when
scenarios like this occurred. This change swaps them for calls to the cgraph
allocation wrappers that exit gracefully on out-of-memory conditions.
After this change, a ASan+UBSan build of Graphviz can process the #1999 example
without crashing. Graphs with >46341 (⌈√INT_MAX⌉) nodes no longer cause an
integer overflow.
UBSan revealed the graph attached to #1999 was triggering an integer overflow in
this multiplication, later on causing a crash in `twopi`. Any number of nodes
≥⌈√INT_MAX⌉ exceeds INT_MAX during multiplication. This fix still does not
enable the graph to be processed in a reasonable amount of time, and it still
crashes later after several hours due to another integer overflow.
ortho: use zero initialization for 'boxf' variables
This was phrased as `{{0}}` to avoid a compiler warning on CentOS 7 about the
LHS being a nested struct. However it turns out this is a false positive in
older versions of GCC, and this form of zero initialization should be valid for
any aggregate in C99. Accordingly _newer_ versions of GCC warn if you use this
double braced phrasing. This change switches to the more standard C99
initialization, squashing warnings on newer platforms at the expense of
reintroducing some warnings on CentOS 7.
sparse Multilevel_MQ_Clustering_establish: replace linked-list with generic list
Linked-lists are a common option for implementing dynamic arrays in C. However
on contemporary platforms they have poor performance characteristics. The need
to allocate on every element addition and the pointer chasing involved in
traversing the list pollutes caches and degrades branch prediction.
This change swaps the use of a linked-list for a contiguous array that is
expanded on demand in the manner of C++’s `std::vector`. Traversal is cheap and
the amortized element addition cost is low.
The previous code prepended to linked-lists and then traversed them from
beginning to end. The new code flips this and appends to the lists and then
traverses them from end to beginning in order to preserve the ordering.
While making this change, we also replace the use of a common/memory.h
allocation wrapper with a cgraph/alloc.h one.
Qt6 no longer ships with pkg-config (.pc) file(s). So we need to do manual
discovery of the necessary information ourselves.
QMake is called `qtmake6` in Qt6 and the `qtmake` that ships with it is a
symlink to the former. So this change preferences Qt6 if both Qt5 and Qt6 are
installed.
Some notable warts:
1. Discovery uses `AC_CHECK_FILE` rather than
`AC_CHECK_HEADER`/`AC_CHECK_HEADERS`. The latter seems to exclusively call
the C compiler rather than the C++ compiler, and thus cannot be used for
C++ header discovery.¹ A consequence of this choice is that discovery
checks existence only, not whether the headers are usable.
2. Library discovery also uses `AC_CHECK_FILE` rather than `AC_CHECK_LIB`.
Given the above restriction, if we cannot call the C++ compiler, there is
little point in attempting a link check. But this does mean that discovery
here also only checks existence, not whether the libraries are usable.
3. There seems to be no pkg-config-like mechanism for discovering that e.g.
Qt6Widgets and Qt6PrintSupport depend on Qt6Gui and thus `-lQt6Gui.so` must
also be included in the link line. Qt6 has migrated to a CMake-based build
system and their answer to most of these such problems appears to be “move
to CMake.”² This change just hard codes the link lines under the assumption
these will be stable across the Qt6 series.
4. Qt6 requires C++17,³ so we need to switch from C++11 to C++17 mode when
`--with-qt=yes`. The CMake discovery apparently does this automatically.
5. The `QT_SELECT` environment variable does nothing in Qt6. The line using it
in cmd/gvedit/Makefile.am has been left unchanged in this commit. When
using Qt5 it still avoids accidentally picking up Qt4 and when using Qt6 it
is a no-op.
Gitlab: closes #2233
¹ If accurate, this would also explain the difficulty I had in
https://gitlab.com/graphviz/graphviz/-/issues/1835#note_794857735.
² https://www.qt.io/blog/qt-6-build-system
https://doc.qt.io/qt-6/qt6-buildsystem.html
³ https://www.qt.io/blog/2019/08/07/technical-vision-qt-6
https://www.qt.io/blog/qt-6.0-released
Autotools: import C++17 macro from Autoconf archive
This commit imports m4/ax_cxx_compile_stdcxx_17.m4 from commit da89908ef7d82a90fe5dab8904a65869b5a5d996 of
git://git.savannah.gnu.org/autoconf-archive.git. It will be used in an upcoming
change.
Making this a `double` seems to have been a mistake. Only `int` values are ever
stored into this field and it is only ever compared against `int` values.
Autotools: discover libANN manually if ann.pc is missing
On Debian and Debian derivatives (e.g. Ubuntu) the libann and libann-dev
packages ship without an ann.pc file to support `pkg-config`. As a result of
this, `pkg-config` cannot find libANN and concludes it is not installed.
This change teaches the Autotools build system how to discover libANN manually
if the `pkg-config` technique fails. Note that we need to use `AC_CHECK_FILE`
instead of `AC_CHECK_HEADER` because libANN is in C++.
Similar to the prior situation with Windows platforms, the CMake build on macOS
was failing the long chain test due to insufficient stack reservation. This
change applies the same increase there. Note that there is no need to adjust the
Autotools build, which seems to handle this test case fine on all platforms.
This repairs the long chain test after it was previously inadvertently broken.
Technically going to 32MB is not necessary on all platforms; in release mode,
the MS Build built Graphviz can handle this example with only a 16MB stack. But
it seems simpler to uniformly go to 32MB on all Windows platforms. In a 64-bit
address space, 32MB is trivial and we could even adjust this limit higher in
future. Note that this is the reserved size, not the committed size.
fdpgen mkClusters: use cgraph wrappers for allocation
The lib/cgraph/alloc.h wrappers are similar to the older lib/common/memory.h
wrappers except (1) they are header-only and (2) they live in a directory
(cgraph) that is at the root of the dependency tree. The long term plan is to
replace all use of lib/common/memory.h with lib/cgraph/alloc.h.
fdpgen deriveGraph: use cgraph wrapper for allocation
The lib/cgraph/alloc.h wrappers are similar to the older lib/common/memory.h
wrappers except (1) they are header-only and (2) they live in a directory
(cgraph) that is at the root of the dependency tree. The long term plan is to
replace all use of lib/common/memory.h with lib/cgraph/alloc.h.
Without tracing the code, it was challenging to see that `K2` was always being
set consistently to evaluate to `K * K`. We can remove this complexity by
simply removing the parameter entirely and computing it on-demand.
Without tracing the code, it was challenging to see that `Ht2` was always being
set consistently to evaluate to `Ht * Ht`. We can remove this complexity by
simply removing the parameter entirely and computing it on-demand.
Without tracing the code, it was challenging to see that `Wd2` was always being
set consistently to evaluate to `Wd * Wd`. We can remove this complexity by
simply removing the parameter entirely and computing it on-demand.
This parameter was only being set conditionally, based on whether `useGrid` was
set, making it look as if the incorrect default value of `0` was being used in
some cases. By tracing the code, it was possible to see the only usage of
`T_Cell2` was under exactly the same conditions as which it was set, making the
use safe. We can remove this complexity by simply removing the parameter
entirely and computing it on-demand.
When hitting either of the error conditions in the loop, the next iteration
would be begun without clearing or freeing the object list. The next call to
`objectList` would overwrite the still-allocated previous object list and it
would be lost.
circogen circomps: use cgraph wrapper for allocation
The lib/cgraph/alloc.h wrappers are similar to the older lib/common/memory.h
wrappers except (1) they are header-only and (2) they live in a directory
(cgraph) that is at the root of the dependency tree. The long term plan is to
replace all use of lib/common/memory.h with lib/cgraph/alloc.h.
projects / graphviz / log