This patch is a rough prototype of how GCC could offer what I'm calling "rich optimization hints" to the user, focussing on vectorization.
The idea is to provide *actionable* information to the user on how GCC is optimizing their code, and how they could modify their source code (or command-line options) to help GCC generate better assembler. Rich optimization hints can contain a mixture of: * text * diagrams * highlighted source locations/ranges, * proposed patches etc. They can be printed to stderr, or saved as part of the JSON optimization record, so that they can prioritized by code hotness, browsed in an IDE etc. The diagrams are printed as ASCII art when printed to stderr, or serialized in a form from which HTML/SVG can be generated (this last part is a work-in-progress). Rich optimization hints are considerably more verbose than diagnostics, by design. I anticipate the primary UI being via a report or IDE that only shows them for the hottest loops in the user's codebase (via the JSON serialization). For example, given the following code: void my_example (int n, int *a, int *b, int *c) { int i; for (i=0; i<n; i++) { a[i] = b[i] + c[i]; } } the following rich hints are emitted (shown in their print-to-stderr form): ==[Loop vectorized]========================================================= I was able to vectorize this loop, using SIMD instructions to reduce the number of iterations by a factor of 4. ../../src/vect-test.c:6:3: for (i=0; i<n; i++) { ^~~ | +--------------+ +-------------|run-time tests|-----------+ | +--------------+ | +-------------------------+ +--------------------+ |vectorized loop | |scalar loop | | iteration count: n / 4 | | iteration count: n| +-------------------------+ | | | | | +-------------------------+ | | |epilogue | | | | iteration count: [0..3]| | | +-------------------------+ +--------------------+ | | +---------------------+------------------+ | --------------------------------------------------------[gcc.vect.success]-- ==[Run-time aliasing check]================================================= Problem: I couldn't prove that these data references don't alias, so I had to add a run-time test, falling back to a scalar loop for when they do. Details: (1) This read/write pair could alias: ../../src/vect-test.c:7:13: a[i] = b[i] + c[i]; ~^~~ ~^~~ (2) This read/write pair could alias: ../../src/vect-test.c:7:20: a[i] = b[i] + c[i]; ~^~~ ~^~~ Suggestion: If you know that the buffers cannot overlap in memory, marking them with restrict will allow me to assume it when optimizing this loop, and eliminate the run-time test. --- ../../src/vect-test.c +++ ../../src/vect-test.c @@ -1,5 +1,5 @@ void -my_example (int n, int *a, int *b, int *c) +my_example (int n, int * restrict a, int * restrict b, int * restrict c) { int i; -----------------------------[gcc.vect.loop-requires-versioning-for-alias]-- ==[Epilogue required for peeling]=========================================== Problem: I couldn't prove that the number of iterations is a multiple of 4, so I had to add an "epilogue" to cover the final 0-3 iterations. Details: FIXME: add a source code highlight or other visualization here? Suggestion: FIXME: add a suggestion here? -----------------------------[gcc.vect.loop-requires-epilogue-for-peeling]-- ...and so on. Known limitations: * lots of hacks: not all of the above is using real data (I'm currently generating this in try_vectorize_loop_1 after the loop_vinfo has been populated, but before the call to vect_transform_loop; it might make more sense to build it after vect_transform_loop, optionally capturing pertinent extra data if rich hints are enabled). * no i18n yet * diagrams don't yet support non-ASCII text * various FIXMEs identified in the code * this only covers the "loop vectorization succeeded" case (and only a subset of that). It would be good to be able to emit rich hints describing the problem to the user when loop vectorization fails on a hot loop. The "opt_problem" work I've posted elsewhere might be useful for that. I haven't attempted a bootstrap or regrtest yet; this is still at RFC/prototyping stage. Thoughts? gcc/ChangeLog: * Makefile.in (OBJS): Add diagram.o, opt-hint.o, and tree-vect-hints.o. * diagnostic.c (diagnostic_get_location_text): Make non-static. * diagnostic.h (diagnostic_get_location_text): New decl. * diagram.cc: New file. * diagram.h: New file. * json.h (json::value::from_bool): New static member function. * opt-hint.cc: New file. * opt-hint.h: New file. * optinfo-emit-json.cc (optimization_records_record_opt_hint): New function. * optinfo-emit-json.h: Include "optinfo.h" and "json.h". (optimization_records_record_opt_hint): New decl. * selftest-diagram.h: New file. * selftest-run-tests.c (selftest::run_tests): Call selftest::diagram_cc_tests and tree_vect_hints_cc_tests. * selftest.h (selftest::diagram_cc_tests): New decl. (selftest::tree_vect_hints_cc_tests): New decl. * tree-vect-hints.cc: New file. * tree-vectorizer.c (try_vectorize_loop_1): Call emit_vect_loop_hints. * tree-vectorizer.h (emit_vect_loop_hints): New decl. --- gcc/Makefile.in | 3 + gcc/diagnostic.c | 2 +- gcc/diagnostic.h | 2 + gcc/diagram.cc | 739 +++++++++++++++++++++++++++++++++++++++++++++++ gcc/diagram.h | 287 ++++++++++++++++++ gcc/json.h | 5 + gcc/opt-hint.cc | 402 ++++++++++++++++++++++++++ gcc/opt-hint.h | 245 ++++++++++++++++ gcc/optinfo-emit-json.cc | 17 ++ gcc/optinfo-emit-json.h | 8 + gcc/selftest-diagram.h | 67 +++++ gcc/selftest-run-tests.c | 2 + gcc/selftest.h | 2 + gcc/tree-vect-hints.cc | 474 ++++++++++++++++++++++++++++++ gcc/tree-vectorizer.c | 2 + gcc/tree-vectorizer.h | 3 + 16 files changed, 2259 insertions(+), 1 deletion(-) create mode 100644 gcc/diagram.cc create mode 100644 gcc/diagram.h create mode 100644 gcc/opt-hint.cc create mode 100644 gcc/opt-hint.h create mode 100644 gcc/selftest-diagram.h create mode 100644 gcc/tree-vect-hints.cc diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 472ef0e..473290c 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1266,6 +1266,7 @@ OBJS = \ data-streamer.o \ data-streamer-in.o \ data-streamer-out.o \ + diagram.o \ dbxout.o \ dbgcnt.o \ dce.o \ @@ -1424,6 +1425,7 @@ OBJS = \ omp-grid.o \ omp-low.o \ omp-simd-clone.o \ + opt-hint.o \ opt-problem.o \ optabs.o \ optabs-libfuncs.o \ @@ -1579,6 +1581,7 @@ OBJS = \ tree-streamer-out.o \ tree-tailcall.o \ tree-vect-generic.o \ + tree-vect-hints.o \ tree-vect-patterns.o \ tree-vect-data-refs.o \ tree-vect-stmts.o \ diff --git a/gcc/diagnostic.c b/gcc/diagnostic.c index 4848b45..a5d0a02 100644 --- a/gcc/diagnostic.c +++ b/gcc/diagnostic.c @@ -314,7 +314,7 @@ maybe_line_and_column (int line, int col) /* Return a malloc'd string describing a location e.g. "foo.c:42:10". The caller is responsible for freeing the memory. */ -static char * +char * diagnostic_get_location_text (diagnostic_context *context, expanded_location s) { diff --git a/gcc/diagnostic.h b/gcc/diagnostic.h index cf3a610..8e4e7ab 100644 --- a/gcc/diagnostic.h +++ b/gcc/diagnostic.h @@ -305,6 +305,8 @@ extern void diagnostic_set_info_translated (diagnostic_info *, const char *, extern void diagnostic_append_note (diagnostic_context *, location_t, const char *, ...) ATTRIBUTE_GCC_DIAG(3,4); #endif +extern char *diagnostic_get_location_text (diagnostic_context *, + expanded_location); extern char *diagnostic_build_prefix (diagnostic_context *, const diagnostic_info *); void default_diagnostic_starter (diagnostic_context *, diagnostic_info *); void default_diagnostic_start_span_fn (diagnostic_context *, diff --git a/gcc/diagram.cc b/gcc/diagram.cc new file mode 100644 index 0000000..1a11520 --- /dev/null +++ b/gcc/diagram.cc @@ -0,0 +1,739 @@ +/* Classes for building diagrams. + Copyright (C) 2018 Free Software Foundation, Inc. + Contributed by David Malcolm <dmalc...@redhat.com>. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "pretty-print.h" +#include "diagram.h" +#include "selftest.h" +#include "selftest-diagram.h" + +/* class text_buffer. */ + +/* text_buffer's ctor. The buffer is initialized to spaces. */ + +text_buffer::text_buffer (size wh) + : m_wh (wh), + m_area (wh.get_area ()), + m_buffer (new cell[m_area]) +{ + for (int i = 0; i < m_area; i++) + m_buffer[i] = cell (' '); +} + +/* Print the content of this text_buffer to PP, eliding trailing + whitespace on each line. */ + +void +text_buffer::print (pretty_printer *pp) const +{ + for (int y = 0; y < m_wh.h; y++) + { + int x; + for (x = m_wh.w - 1; x >= 0; x--) + if (get_cell (point (x, y)).ch != ' ') + break; + int rightmost_non_ws = x; + for (x = 0; x <= rightmost_non_ws; x++) + pp_character (pp, get_cell (point (x,y)).ch); + pp_newline (pp); + } +} + +/* Get the content of XY. */ + +cell +text_buffer::get_cell (point xy) const +{ + return m_buffer[xy_to_index (xy)]; +} + +/* Set the content of XY to CH. */ + +void +text_buffer::set_cell (point xy, char ch) +{ + m_buffer[xy_to_index (xy)] = cell (ch); +} + +/* Write STR as horizontal left-aligned text at XY, so that the first + character of STR is at XY. The buffer must be large enough. */ + +void +text_buffer::left_aligned_text_at (point xy, const char *str) +{ + while (char ch = *(str++)) + { + set_cell (xy, ch); + ++xy.x; + } +} + +/* Write STR as horizontal right-aligned text at XY, so that the final + character of STR is at XY. The buffer must be large enough. */ + +void +text_buffer::right_aligned_text_at (point xy, const char *str) +{ + size_t len = strlen (str); + left_aligned_text_at (point (xy.x + 1 - len, xy.y), str); +} + +/* Convert XY to an index within the buffer. */ + +int +text_buffer::xy_to_index (point xy) const +{ + gcc_assert (xy.x >= 0); + gcc_assert (xy.y >= 0); + gcc_assert (xy.x < m_wh.w); + gcc_assert (xy.y < m_wh.h); + return (xy.y * m_wh.w) + xy.x; +} + +/* class element. */ + +/* Print this element to a TEXT_BUFFER that's exactly big enough to hold it, + and print the result to PP, eliding trailing whitespace on each line. */ + +void +element::print_to_pp (pretty_printer *pp) +{ + size wh = get_requisition (); + set_allocation (wh); + + text_buffer buf (wh); + print (&buf, point (0,0)); + buf.print (pp); +} + +/* class text_element : public element. */ + +/* text_element's ctor. */ + +text_element::text_element (const char *str) +: m_str (xstrdup (str)), + m_len (strlen (str)) +{} + +/* text_element's dtor. */ + +text_element::~text_element () +{ + free (m_str); +} + +/* Implementation of element::print for text_element. */ + +void +text_element::print (text_buffer *buf, point xy) +{ + buf->left_aligned_text_at (xy, m_str); +} + +/* Implementation of element::get_requisition for text_element. */ + +size +text_element::get_requisition () +{ + return size (m_len, 1); +} + +/* Implementation of element::handle_allocation for text_element. */ + +void +text_element::handle_allocation () +{ + /* Empty. */ +} + +/* Implementation of element::to_json for text_element. */ + +json::value * +text_element::to_json () const +{ + return new json::string (m_str); +} + +/* class grid_layout : public element. */ + +/* grid_layout's ctor. */ + +grid_layout::grid_layout (int w, int h) + : m_w (w), m_h (h), m_children () +{ + for (int i = 0; i < w * h; i++) + m_children.safe_push (NULL); + for (int x = 0; x < w; x++) + m_col_widths.safe_push (0); + for (int y = 0; y < h; y++) + m_row_heights.safe_push (0); +} + +/* grid_layout's dtor. */ + +grid_layout::~grid_layout () +{ + element *child; + unsigned i; + FOR_EACH_VEC_ELT (m_children, i, child) + delete child; +} + +/* Set the child at X, Y to element. */ + +void +grid_layout::set_child (int x, int y, element *element) +{ + delete m_children[child_xy_to_index (x, y)]; + m_children[child_xy_to_index (x, y)] = element; +} + +/* Implementation of element::print for grid_layout. */ + +void +grid_layout::print (text_buffer *buf, point xy) +{ + point row_start = xy; + for (int y = 0; y < m_h; y++) + { + point child_xy = row_start; + for (int x = 0; x < m_w; x++) + { + element *child = get_child (x, y); + if (child) + child->print (buf, child_xy); + child_xy.x += m_col_widths[x]; + } + row_start.y += m_row_heights[y]; + } +} + +/* Implementation of element::get_requisition for grid_layout. */ + +size +grid_layout::get_requisition () +{ + /* Get child requisitions. */ + auto_vec<size> child_reqs (get_num_children ()); + for (int i = 0; i < get_num_children (); i++) + { + element *child = m_children[i]; + if (child) + child_reqs.quick_push (child->get_requisition ()); + else + child_reqs.quick_push (size (0, 0)); + } + + /* Get column widths. */ + int width = 0; + for (int x = 0; x < m_w; x++) + { + /* Get maximum width within column. */ + int max_width = 0; + for (int y = 0; y < m_h; y++) + max_width = MAX (max_width, + child_reqs[child_xy_to_index(x, y)].w); + width += max_width; + m_col_widths[x] = max_width; + } + + /* Get row heights. */ + int height = 0; + for (int y = 0; y < m_h; y++) + { + /* Get maximum height within row. */ + int max_height = 0; + for (int x = 0; x < m_w; x++) + max_height = MAX (max_height, + child_reqs[child_xy_to_index(x, y)].h); + height += max_height; + m_row_heights[y] = max_height; + } + + return size (width, height); +} + +/* Implementation of element::handle_allocation for grid_layout. */ + +void +grid_layout::handle_allocation () +{ + // TODO: hand out surplus allocation + for (int y = 0; y < m_h; y++) + for (int x = 0; x < m_w; x++) + { + element *child = get_child (x, y); + if (child) + child->set_allocation (size (m_col_widths[x], + m_row_heights[y])); + } +} + +/* Implementation of element::to_json for grid_layout. */ + +json::value * +grid_layout::to_json () const +{ + json::object *obj = new json::object (); + obj->set ("kind", new json::string ("grid")); + obj->set ("w", new json::number (m_w)); + obj->set ("h", new json::number (m_h)); + json::array *rows = new json::array (); + for (int y = 0; y < m_h; y++) + { + json::array *row = new json::array (); + for (int x = 0; x < m_w; x++) + { + element *child = get_child (x, y); + if (child) + row->append (child->to_json ()); + else + row->append (new json::literal (json::JSON_NULL)); + } + rows->append (row); + } + obj->set ("rows", rows); + return obj; +} + +/* class wrapper_element : public element. */ + +/* wrapper_element's dtor. */ + +wrapper_element::~wrapper_element () +{ + delete m_child; +} + +/* Implementation of element::print for wrapper_element. */ + +void +wrapper_element::print (text_buffer *buf, point xy) +{ + if (m_child) + return m_child->print (buf, xy); +} + +/* Implementation of element::get_requisition for wrapper_element. */ + +size +wrapper_element::get_requisition () +{ + size child_req (0, 0); + if (m_child) + return m_child->get_requisition (); + else + return size (0,0); +} + +/* Implementation of element::handle_allocation for wrapper_element. */ + +void +wrapper_element::handle_allocation () +{ + if (m_child) + m_child->set_allocation (get_size ()); +} + +/* Implementation of element::to_json for wrapper_element. */ + +json::value * +wrapper_element::to_json () const +{ + if (m_child) + return m_child->to_json (); + else + return new json::literal (json::JSON_NULL); +} + +/* Set the child element of this wrapper. */ + +void +wrapper_element::set_child (element *child) +{ + delete m_child; + m_child = child; +} + +/* class box_element : public wrapper_element. */ + +/* box_element's ctor. */ + +box_element::box_element (element *child) +: wrapper_element (child) +{} + +/* Implementation of element::print for box_element. */ + +void +box_element::print (text_buffer *buf, point xy) +{ + horizontal_border (buf, xy); + vertical_line (buf, point (xy.x, xy.y + 1), get_height () - 2); + vertical_line (buf, point (xy.x + get_width () -1 , xy.y + 1), + get_height () - 2); + horizontal_border (buf, point (xy.x, xy.y + get_height () - 1)); + + if (get_child ()) + get_child ()->print (buf, point (xy.x + 1, xy.y + 1)); +} + +/* Implementation of element::get_requisition for box_element. */ + +size +box_element::get_requisition () +{ + size child_req = wrapper_element::get_requisition (); + return size (child_req.w + 2, child_req.h + 2); +} + +/* Implementation of element::handle_allocation for box_element. */ + +void +box_element::handle_allocation () +{ + if (get_child ()) + get_child ()->set_allocation (size (get_width () - 2, get_height () - 2)); +} + +/* Implementation of element::to_json for box_element. */ + +json::value * +box_element::to_json () const +{ + json::object *obj = new json::object (); + obj->set ("kind", new json::string ("box")); + obj->set ("content", wrapper_element::to_json ()); + return obj; +} + +/* Subroutine of box_element::print. */ + +void +box_element::horizontal_border (text_buffer *buf, point xy) +{ + int w = get_width (); + buf->set_cell (xy, '+'); + for (int x = 1; x < w - 1; x++) + buf->set_cell (point (xy.x + x, xy.y), '-'); + if (w > 0) + buf->set_cell (point (xy.x + w - 1, xy.y), '+'); +} + +/* Subroutine of box_element::print. */ + +void +box_element::vertical_line (text_buffer *buf, point xy, int height) +{ + for (int y = 0; y < height; y++) + buf->set_cell (point (xy.x, xy.y + y), '|'); +} + +/* class wiring_element : public element. */ + +/* wiring_element's ctor. */ + +wiring_element::wiring_element (bool north, bool south, bool east, bool west) + : m_north (north), m_south (south), m_east (east), m_west (west), + m_vert (m_north || m_south), + m_horiz (m_west || m_east) +{ +} + +/* Implementation of element::print for wiring_element. */ + +void +wiring_element::print (text_buffer *buf, point xy) +{ + point centre = point (xy.x + get_width () / 2, + xy.y + get_height () / 2); + + /* Draw centre cell. */ + buf->set_cell (centre, + (m_vert && m_horiz) + ? '+' + : (m_vert + ? '|' + : (m_horiz ? '-' : ' '))); + + /* Draw lines heading from center in each cardinal direction, + as requested. */ + + if (m_north) + for (int y = xy.y; y < centre.y; y++) + buf->set_cell (point (centre.x, y), '|'); + if (m_south) + for (int y = centre.y + 1; y < xy.y + get_height (); y++) + buf->set_cell (point (centre.x, y), '|'); + + if (m_west) + for (int x = xy.x; x < centre.x; x++) + buf->set_cell (point (x, centre.y), '-'); + if (m_east) + for (int x = centre.x + 1; x < xy.x + get_width (); x++) + buf->set_cell (point (x, centre.y), '-'); +} + +/* Implementation of element::get_requisition for wiring_element. */ + +size +wiring_element::get_requisition () +{ + if (m_vert && m_horiz) + return size (3, 3); + else + return size (1, 1); +} + +/* Implementation of element::handle_allocation for wiring_element. */ + +void +wiring_element::handle_allocation () +{ +} + +/* Implementation of element::to_json for wiring_element. */ + +json::value * +wiring_element::to_json () const +{ + json::object *obj = new json::object (); + obj->set ("kind", new json::string ("wiring")); + obj->set ("north", json::literal::from_bool (m_north)); + obj->set ("south", json::literal::from_bool (m_south)); + obj->set ("east", json::literal::from_bool (m_east)); + obj->set ("west", json::literal::from_bool (m_west)); + return obj; +} + +#if CHECKING_P + +namespace selftest { + +/* Implementation detail of ASSERT_TEXT_BUFFER_EQ. + + Assert that BUF->print (&pp) is EXPECTED_TEXT, using LOC as the effective + location on any failure. */ + +void +verify_text_buffer (const location &loc, + text_buffer *buf, + const char *expected_text) +{ + pretty_printer pp; + buf->print (&pp); + ASSERT_STREQ_AT (loc, pp_formatted_text (&pp), expected_text); +} + +/* Implementation detail of ASSERT_ELEMENT_PRINT. + + Assert that ELEMENT->print_to_pp (&pp) is EXPECTED_TEXT, using LOC as + the effective location on any failure. */ + +void +verify_element_print (const location &loc, + element *element, + const char *expected_text) +{ + pretty_printer pp; + element->print_to_pp (&pp); + ASSERT_STREQ_AT (loc, pp_formatted_text (&pp), expected_text); +} + +/* Verify that text_buffer works. */ + +static void +test_text_buffer () +{ + text_buffer buf (size (30, 3)); + buf.left_aligned_text_at (point (0, 0), "012345678901234567890123456789"); + buf.left_aligned_text_at (point (15, 1), "left-aligned"); + buf.right_aligned_text_at (point (15, 2), "right-aligned"); + + ASSERT_TEXT_BUFFER_EQ (&buf, + "012345678901234567890123456789\n" + " left-aligned\n" + " right-aligned\n"); +} + +/* Verify that text_element sizing and printing works. */ + +static void +test_text_element () +{ + text_element el ("hello world"); + size wh = el.get_requisition (); + ASSERT_EQ (wh.w, 11); + ASSERT_EQ (wh.h, 1); + + ASSERT_ELEMENT_PRINT (&el, "hello world\n"); +} + +/* Verify that grid_layout sizing and printing works. */ + +static void +test_grid_layout () +{ + grid_layout grid (3, 3); + grid.set_child (0, 0, new text_element ("top left")); + grid.set_child (1, 0, new text_element ("top middle")); + grid.set_child (2, 0, new text_element ("top right")); + grid.set_child (0, 1, new text_element ("middle left")); + grid.set_child (1, 1, new text_element ("middle middle")); + grid.set_child (2, 1, new text_element ("middle right")); + grid.set_child (0, 2, new text_element ("bottom left")); + grid.set_child (1, 2, new text_element ("bottom middle")); + grid.set_child (2, 2, new text_element ("bottom right")); + + size wh = grid.get_requisition (); + ASSERT_EQ (wh.w, 36); + ASSERT_EQ (wh.h, 3); + + ASSERT_ELEMENT_PRINT (&grid, + "top left top middle top right\n" + "middle leftmiddle middlemiddle right\n" + "bottom leftbottom middlebottom right\n"); +} + +/* Verify that box_element sizing and printing works. */ + +static void +test_box_element () +{ + box_element box (new text_element ("label")); + size wh = box.get_requisition (); + ASSERT_EQ (wh.w, 7); + ASSERT_EQ (wh.h, 3); + + ASSERT_ELEMENT_PRINT (&box, + "+-----+\n" + "|label|\n" + "+-----+\n"); +} + +/* Implementation detail of ASSERT_WIRING_ELEMENT. */ + +static void +verify_wiring_element (const location &loc, + bool north, bool south, bool east, bool west, + const char *expected_text) +{ + wiring_element el (north, south, east, west); + verify_element_print (loc, &el, expected_text); +} + +/* Verify that the given wiring_element prints as EXPECTED_TEXT. */ + +#define ASSERT_WIRING_ELEMENT(NORTH, SOUTH, EAST, WEST, EXPECTED_TEXT) \ + SELFTEST_BEGIN_STMT \ + verify_wiring_element (SELFTEST_LOCATION, \ + (NORTH), (SOUTH), (EAST), (WEST), \ + (EXPECTED_TEXT)); \ + SELFTEST_END_STMT + +/* Verify that wiring_element sizing and printing works. */ + +static void +test_wiring_elements () +{ + /* Vertical. */ + ASSERT_WIRING_ELEMENT(true, true, false, false, + "|\n"); + /* Horizontal. */ + ASSERT_WIRING_ELEMENT(false, false, true, true, + "-\n"); + /* T junction. */ + ASSERT_WIRING_ELEMENT(true, false, true, true, + " |\n" + "-+-\n" + "\n"); + + /* Corner, exits to S and E. */ + ASSERT_WIRING_ELEMENT(false, true, true, false, + "\n" + " +-\n" + " |\n"); +} + +/* Test of printing a non-trivial diagram out of the above components. */ + +static void +test_complex_diagram () +{ + grid_layout grid (3, 3); + grid.set_child (0, 0, wiring_element::make_se ()); + grid.set_child (1, 0, wiring_element::make_new ()); + grid.set_child (2, 0, wiring_element::make_sw ()); + grid.set_child (0, 1, new box_element (new text_element ("scalar"))); + { + grid_layout *vect = new grid_layout (1, 5); + grid.set_child (2, 1, vect); + vect->set_child (0, 0, new box_element (new text_element ("prologue"))); + vect->set_child (0, 1, wiring_element::make_vert ()); + vect->set_child (0, 2, + new box_element (new text_element ("vectorized loop"))); + vect->set_child (0, 3, wiring_element::make_vert ()); + vect->set_child (0, 4, new box_element (new text_element ("epilogue"))); + } + grid.set_child (0, 2, wiring_element::make_ne ()); + grid.set_child (1, 2, wiring_element::make_sew ()); + grid.set_child (2, 2, wiring_element::make_nw ()); + + ASSERT_ELEMENT_PRINT (&grid, + " |\n" + " +----+---------+\n" + " | |\n" + "+------+ +---------------+\n" + "|scalar| |prologue |\n" + "| | +---------------+\n" + "| | |\n" + "| | +---------------+\n" + "| | |vectorized loop|\n" + "| | +---------------+\n" + "| | |\n" + "| | +---------------+\n" + "| | |epilogue |\n" + "+------+ +---------------+\n" + " | |\n" + " +----+---------+\n" + " |\n"); +} + +/* Run all of the selftests within this file. */ + +void +diagram_cc_tests () +{ + test_text_buffer (); + + /* Tests of individual element subclasses. */ + test_text_element (); + test_grid_layout (); + test_box_element (); + test_wiring_elements (); + + test_complex_diagram (); +} + +} // namespace selftest + +#endif /* CHECKING_P */ diff --git a/gcc/diagram.h b/gcc/diagram.h new file mode 100644 index 0000000..cbd4679 --- /dev/null +++ b/gcc/diagram.h @@ -0,0 +1,287 @@ +/* Classes for building diagrams. + Copyright (C) 2018 Free Software Foundation, Inc. + Contributed by David Malcolm <dmalc...@redhat.com>. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#ifndef GCC_DIAGRAM_H +#define GCC_DIAGRAM_H + +#include "json.h" + +/* The size of an element within a diagram, or of the diagram itself. */ + +struct size +{ + int w; + int h; + + size (int width, int height) : w (width), h (height) {} + + int get_area () const { return w * h; } +}; + +/* A coordinate within a diagram. */ + +struct point +{ + int x; + int y; + + point (int x_, int y_) : x (x_) , y (y_) {} +}; + +/* A cell within a text buffer. Currently just a "char", but could be + extended to represent a unicode code point and color information. */ + +struct cell +{ + char ch; + + cell () : ch (' ') {} + cell (char ch_) : ch (ch_) {} +}; + +/* A text buffer, to which a diagram can be rendered. */ + +class text_buffer +{ + public: + text_buffer (size wh); + ~text_buffer () { delete m_buffer; } + + void print (pretty_printer *pp) const; + + cell get_cell (point xy) const; + void set_cell (point xy, char ch); + + void left_aligned_text_at (point xy, const char *str); + void right_aligned_text_at (point xy, const char *str); + + private: + int xy_to_index (point xy) const; + + private: + size m_wh; + int m_area; + cell *m_buffer; +}; + +/* A base class representing an element within a diagram (or the + whole diagram), which can be printed to a location within a + text_buffer via the "print" virtual function. + + Elements can also be serialized to JSON, and thus saved + in optimization records. + TODO: generate HTML and/or SVG from them in (I have this mostly + working, but the wiring_element subclass is problematic). + + Elements support two-phase size negotiation: + + (i) client code uses "get_requisition" to ask the element how + big it needs to be. This recurses through children, generating + a requested size that's big enough for them all + + (ii) client code calls "set_allocation" on the element, which sets + the size, and calls "handle_allocation" to perform any recursive + size-setting on the children. */ + +class element +{ + public: + element () : m_wh (0, 0) {} + virtual ~element () {} + + void set_allocation (size wh) + { + m_wh = wh; + handle_allocation (); + } + + int get_width () const { return m_wh.w; } + int get_height () const { return m_wh.h; } + size get_size () const { return m_wh; } + + virtual void print (text_buffer *buf, point xy) = 0; + virtual size get_requisition () = 0; + virtual void handle_allocation () = 0; + virtual json::value *to_json () const = 0; + + void print_to_pp (pretty_printer *pp); + + private: + size m_wh; +}; + +/* Subclass of element, representing a single line of text. */ + +class text_element : public element +{ + public: + text_element (const char *str); + ~text_element (); + + void print (text_buffer *buf, point xy) OVERRIDE; + size get_requisition () OVERRIDE; + void handle_allocation () OVERRIDE; + json::value *to_json () const OVERRIDE; + + private: + char *m_str; + size_t m_len; +}; + +/* Subclass of element, representing a WxH grid of child elements + (any of which can be NULL). */ + +class grid_layout : public element +{ +public: + grid_layout (int w, int h); + ~grid_layout (); + + void set_child (int x, int y, element *element); + + void print (text_buffer *buf, point xy) OVERRIDE; + size get_requisition () OVERRIDE; + void handle_allocation () OVERRIDE; + json::value *to_json () const OVERRIDE; + +private: + int get_num_children () const { return m_children.length (); } + + element * + get_child (int x, int y) const + { + return m_children[child_xy_to_index (x, y)]; + } + + int + child_xy_to_index (int x, int y) const + { + gcc_assert (x >= 0); + gcc_assert (x < m_w); + gcc_assert (y >= 0); + gcc_assert (y < m_h); + return (m_w * y) + x; + } + +private: + int m_w; + int m_h; + auto_vec<element *> m_children; + + auto_vec<int> m_col_widths; + auto_vec<int> m_row_heights; +}; + +/* Subclass of element: a decorator for a child element (which can + be NULL). */ + +class wrapper_element : public element +{ + public: + wrapper_element (element *child) : m_child (child) {} + ~wrapper_element (); + + void print (text_buffer *buf, point xy) OVERRIDE; + size get_requisition () OVERRIDE; + void handle_allocation () OVERRIDE; + json::value *to_json () const OVERRIDE; + + element *get_child () const { return m_child; } + void set_child (element *child); + +private: + element *m_child; +}; + +/* Subclass of element: a decorator that prints a box around + a child element. */ + +class box_element : public wrapper_element +{ +public: + box_element (element *child); + + void print (text_buffer *buf, point xy) OVERRIDE; + size get_requisition () OVERRIDE; + void handle_allocation () OVERRIDE; + json::value *to_json () const OVERRIDE; + +private: + void horizontal_border (text_buffer *buf, point xy); + void vertical_line (text_buffer *buf, point xy, int height); +}; + +/* Subclass of element: a rectangular area with lines running + from the center to the centre of the edges. Each of the lines + running north, south, east and west can be independently + turned on and off, allowing for simple flow diagrams. */ + +class wiring_element : public element +{ + public: + wiring_element (bool north, bool south, bool east, bool west); + + static wiring_element *make_vert () + { + return new wiring_element (true, true, false, false); + } + static wiring_element *make_horiz () + { + return new wiring_element (false, false, true, true); + } + static wiring_element *make_ne () + { + return new wiring_element (true, false, true, false); + } + static wiring_element *make_nw () + { + return new wiring_element (true, false, false, true); + } + static wiring_element *make_new () + { + return new wiring_element (true, false, true, true); + } + static wiring_element *make_se () + { + return new wiring_element (false, true, true, false); + } + static wiring_element *make_sw () + { + return new wiring_element (false, true, false, true); + } + static wiring_element *make_sew () + { + return new wiring_element (false, true, true, true); + } + void print (text_buffer *buf, point xy) OVERRIDE; + size get_requisition () OVERRIDE; + void handle_allocation () OVERRIDE; + json::value *to_json () const OVERRIDE; + + private: + bool m_north; + bool m_south; + bool m_east; + bool m_west; + bool m_vert; + bool m_horiz; +}; + +#endif /* #ifndef GCC_DIAGRAM_H */ diff --git a/gcc/json.h b/gcc/json.h index 154d9e1..32f9b61 100644 --- a/gcc/json.h +++ b/gcc/json.h @@ -157,6 +157,11 @@ class literal : public value enum kind get_kind () const FINAL OVERRIDE { return m_kind; } void print (pretty_printer *pp) const FINAL OVERRIDE; + static literal *from_bool (bool value) + { + return new literal (value ? JSON_TRUE : JSON_FALSE); + } + private: enum kind m_kind; }; diff --git a/gcc/opt-hint.cc b/gcc/opt-hint.cc new file mode 100644 index 0000000..7212173 --- /dev/null +++ b/gcc/opt-hint.cc @@ -0,0 +1,402 @@ +/* "Rich hints" to the user from the optimizer. + Copyright (C) 2018 Free Software Foundation, Inc. + Contributed by David Malcolm <dmalc...@redhat.com>. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "tree.h" +#include "gimple.h" +#include "opt-hint.h" +#include "diagram.h" +#include "diagnostic.h" +#include "gcc-rich-location.h" +#include "edit-context.h" +#include "optinfo-emit-json.h" +#include "selftest.h" + +/* opt_hint_compound's dtor. */ + +opt_hint_compound::~opt_hint_compound () +{ + unsigned i; + opt_hint_node *child; + FOR_EACH_VEC_ELT (m_children, i, child) + delete child; +} + +/* Add CHILD. */ + +void +opt_hint_compound::add_child (opt_hint_node *child) +{ + m_children.safe_push (child); +} + +/* Add a paragraph containing the formatted text. + FIXME: this doesn't interoperate well with JSON. Probably ought + to have it print (somehow) to an optinfo, and capture those items. */ + +void +opt_hint_compound::add_para (const char *fmt, ...) +{ + pretty_printer pp; + + // FIXME: something of a hack: + pp_show_color (&pp) = pp_show_color (global_dc->printer); + + text_info ti; + va_list ap; + va_start (ap, fmt); + ti.format_spec = fmt; + ti.args_ptr = ≈ + ti.err_no = 0; + ti.x_data = NULL; + ti.m_richloc = NULL; + pp_format (&pp, &ti); + pp_output_formatted_text (&pp); + va_end (ap); + add_child (new opt_hint_para (pp_formatted_text (&pp))); +} + +/* Add a STMT. */ + +void +opt_hint_compound::add_stmt (gimple *stmt) +{ + add_child (new opt_hint_gimple (stmt)); +} + +/* Add LOC. */ + +void +opt_hint_compound::add_location (location_t loc) +{ + add_child (new opt_hint_location (new gcc_rich_location (loc))); +} + +/* Add RICH_LOC, taking ownership. */ + +void +opt_hint_compound::add_location (rich_location *rich_loc) +{ + add_child (new opt_hint_location (rich_loc)); +} + +/* Add DIAGRAM, taking ownership. */ + +void +opt_hint_compound::add_diagram (element *diagram) +{ + add_child (new opt_hint_diagram (diagram)); +} + +/* opt_hint_compound's implementation of write_to_pp. */ + +void +opt_hint_compound::write_to_pp (pretty_printer *pp) const +{ + unsigned i; + opt_hint_node *child; + FOR_EACH_VEC_ELT (m_children, i, child) + { + if (i > 0) + pp_newline (pp); + child->write_to_pp (pp); + } +} + +/* opt_hint_compound's implementation of to_json. */ + +json::value * +opt_hint_compound::to_json () const +{ + json::array *arr = new json::array (); + unsigned i; + opt_hint_node *child; + FOR_EACH_VEC_ELT (m_children, i, child) + arr->append (child->to_json ()); + return arr; +} + +/* opt_hint_root's ctor. */ + +opt_hint_root::opt_hint_root (const char *hint_title, + const char *hint_id) +: m_hint_title (hint_title), m_hint_id (hint_id) +{ +} + +/* Add a "Problem" section, and return it. */ + +opt_hint_section * +opt_hint_root::add_problem () +{ + opt_hint_section *section = new opt_hint_section (SK_PROBLEM); + add_child (section); + return section; +} + +/* Add a "Details" section, and return it. */ + +opt_hint_section * +opt_hint_root::add_details () +{ + opt_hint_section *section = new opt_hint_section (SK_DETAILS); + add_child (section); + return section; +} + +/* Add a "Suggestion" section, and return it. */ + +opt_hint_section * +opt_hint_root::add_suggestion () +{ + opt_hint_section *section = new opt_hint_section (SK_SUGGESTION); + add_child (section); + return section; +} + +/* Emit this hint. Print it to stderr. If optimization records + are enabled, add it to them, using LOC, KIND and PASS. */ + +void +opt_hint_root::emit (const dump_location_t &loc, + enum optinfo_kind kind, + opt_pass *pass) const +{ + pretty_printer pp; + pp_show_color (&pp) = pp_show_color (global_dc->printer); + write_to_pp (&pp); + pp_flush (&pp); + + /* Add to any optimization record. */ + if (optimization_records_enabled_p ()) + { + json::value *jv = to_json (); + json::object *obj = new json::object (); + obj->set ("hint", jv); + obj->set ("id", new json::string (get_hint_id ())); + optimization_records_record_opt_hint (loc, kind, pass, obj); + } +} + +/* opt_hint_root's implementation of write_to_pp. */ + +void +opt_hint_root::write_to_pp (pretty_printer *pp) const +{ + size_t title_width = strlen (m_hint_title); + pp_printf (pp, "==[%r%s%R]", "note", m_hint_title); + for (int i = 0; i < (76 - 4) - title_width; i++) + pp_character (pp, '='); + pp_newline (pp); + pp_newline (pp); + + opt_hint_compound::write_to_pp (pp); + + size_t id_width = strlen (m_hint_id); + for (int i = 0; i < (76 - 4) - id_width; i++) + pp_character (pp, '-'); + pp_printf (pp, "[%r%s%R]--\n\n", "note", m_hint_id); +} + +/* Get a string for an enum opt_hint_section_kind. */ + +const char * +section_kind_as_string (enum opt_hint_section_kind kind) +{ + switch (kind) + { + default: + gcc_unreachable (); + case SK_PROBLEM: return "Problem"; + case SK_DETAILS: return "Details"; + case SK_SUGGESTION: return "Suggestion"; + } +} + +/* opt_hint_section's implementation of write_to_pp. */ + +void +opt_hint_section::write_to_pp (pretty_printer *pp) const +{ + pp_printf (pp, "%r%s: %R\n", "note", + section_kind_as_string (m_kind)); + pp_indentation (pp) += 3; + opt_hint_compound::write_to_pp (pp); + pp_indentation (pp) -= 3; +} + +/* opt_hint_section's implementation of to_json. */ + +json::value * +opt_hint_section::to_json () const +{ + json::object *obj = new json::object (); + obj->set ("content", opt_hint_compound::to_json ()); + obj->set ("kind", new json::string (section_kind_as_string (m_kind))); + return obj; +} + +/* opt_hint_ol's implementation of write_to_pp. */ + +void +opt_hint_ol::write_to_pp (pretty_printer *pp) const +{ + unsigned i; + opt_hint_node *child; + FOR_EACH_VEC_ELT (m_children, i, child) + { + if (i > 0) + pp_newline (pp); + pp_printf (pp, "(%i) ", i + 1); + pp_indentation (pp) += 3; + child->write_to_pp (pp); + pp_indentation (pp) -= 3; + } +} + +/* opt_hint_ol's implementation of to_json. */ + +json::value * +opt_hint_ol::to_json () const +{ + json::object *obj = new json::object (); + obj->set ("items", opt_hint_compound::to_json ()); + obj->set ("kind", new json::string ("ol")); + return obj; +} + +/* opt_hint_para's implementation of write_to_pp. */ + +void +opt_hint_para::write_to_pp (pretty_printer *pp) const +{ + pp_printf (pp, "%s\n", m_text); +} + +/* opt_hint_para's implementation of to_json. */ + +json::value * +opt_hint_para::to_json () const +{ + return new json::string (m_text); +} + +/* Subroutine. */ + +static void +write_location_to_pp (pretty_printer *pp, rich_location *rich_loc) +{ + if (rich_loc->get_loc () != UNKNOWN_LOCATION) + { + expanded_location s = rich_loc->get_expanded_location (0); + char *location_text = diagnostic_get_location_text (global_dc, s); + pp_string (pp, location_text); + free (location_text); + + /* diagnostic_show_locus begins by writing a newline. */ + + diagnostic_context dc; + diagnostic_initialize (&dc, 0); + dc.show_caret = true; + dc.printer = pp; + diagnostic_show_locus (&dc, rich_loc, DK_ERROR); + } + + edit_context ec; + ec.add_fixits (rich_loc); + ec.print_diff (pp, true); +} + +/* opt_hint_gimple's implementation of write_to_pp. */ + +void +opt_hint_gimple::write_to_pp (pretty_printer *pp) const +{ + location_t loc = gimple_location (m_stmt); + if (loc != UNKNOWN_LOCATION) + { + gcc_rich_location rich_loc (loc); + write_location_to_pp (pp, &rich_loc); + } + else + { + // FIXME: maybe print the statement? + } +} + +/* opt_hint_gimple's implementation of to_json. */ + +json::value * +opt_hint_gimple::to_json () const +{ + return new json::string ("FIXME: opt_hint_gimple::to_json"); +} + +/* opt_hint_location's dtor. */ + +opt_hint_location::~opt_hint_location () +{ + delete m_rich_loc; +} + +/* opt_hint_location's implementation of write_to_pp. */ + +void +opt_hint_location::write_to_pp (pretty_printer *pp) const +{ + write_location_to_pp (pp, m_rich_loc); +} + +/* opt_hint_location's implementation of to_json. */ + +json::value * +opt_hint_location::to_json () const +{ + return new json::string ("FIXME: opt_hint_location::to_json"); +} + +/* opt_hint_diagram's dtor. */ + +opt_hint_diagram::~opt_hint_diagram () +{ + delete m_diagram; +} + +/* opt_hint_diagram's implementation of write_to_pp. */ + +void +opt_hint_diagram::write_to_pp (pretty_printer *pp) const +{ + m_diagram->print_to_pp (pp); +} + +/* opt_hint_diagram's implementation of to_json. */ + +json::value * +opt_hint_diagram::to_json () const +{ + json::object *obj = new json::object (); + obj->set ("kind", new json::string ("diagram")); + obj->set ("diagram", m_diagram->to_json ()); + return obj; +} diff --git a/gcc/opt-hint.h b/gcc/opt-hint.h new file mode 100644 index 0000000..8ad4891 --- /dev/null +++ b/gcc/opt-hint.h @@ -0,0 +1,245 @@ +/* "Rich hints" to the user from the optimizer. + Copyright (C) 2018 Free Software Foundation, Inc. + Contributed by David Malcolm <dmalc...@redhat.com>. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#ifndef GCC_OPT_HINT_H +#define GCC_OPT_HINT_H + +#include "json.h" +#include "optinfo.h" // for enum optinfo_kind + +class element; + +/* Classes for emitting "rich hints" to the user about how they might change + their code or their command-line flags to help GCC produce better code. + + We want to be able to emit hints to stderr, or in machine-readable form + that can e.g. be exposed by an IDE, or turned into HTML reports. + + Hints are considerably more verbose than diagnostics. They can contain + multiple sections e.g.: + + Problem: + (description of the problem) + + Details: + (pertinent information for locating the issue e.g. links to source code) + + Suggestion: + (if possible, a suggested way for the user to resolve this problem, ideally + with a fix-it hint). + + e.g. + + "Problem: I couldn't prove that these data accesses were aligned to a + ALIGNMENT-byte boundary, so I had to add a run-time test, falling back + to a scalar loop. + + Details: + (the statements in question, and the decls of the pertinent types) + + Suggestion: If you convert the type of 'arr' from 'int *' to + 'int * __attribute__ ((__aligned__(16)))' I can assume that it is + aligned and remove this test." + + etc etc. Note the use of "I" and "you" in the above. */ + +/* Forward decls; indentation shows inheritance. */ +class opt_hint_node; + class opt_hint_compound; + class opt_hint_root; + class opt_hint_section; + class opt_hint_ol; + class opt_hint_para; + class opt_hint_gimple; + class opt_hint_location; + class opt_hint_diagram; + +/* Base class for a node within a rich hint. Can be written to a + pretty-printer for textual output by GCC, or serialized to JSON. */ + +class opt_hint_node +{ +public: + virtual ~opt_hint_node () {} + + virtual void write_to_pp (pretty_printer *pp) const = 0; + virtual json::value *to_json () const = 0; +}; + +/* Subclass of opt_hint_node for holding a list of child nodes. */ + +class opt_hint_compound : public opt_hint_node +{ +public: + opt_hint_compound () : m_children () {} + ~opt_hint_compound (); + + void add_child (opt_hint_node *child); + + void add_para (const char *text, ...); + void add_stmt (gimple *stmt); + void add_location (location_t loc); + void add_location (rich_location *rich_loc); + void add_diagram (element *diagram); + + void write_to_pp (pretty_printer *pp) const OVERRIDE; + json::value *to_json () const OVERRIDE; + +protected: + auto_vec<opt_hint_node *> m_children; +}; + +/* The top-level node within a user-facing hint. */ + +class opt_hint_root : public opt_hint_compound +{ +public: + opt_hint_root (const char *hint_title, const char *hint_id); + + opt_hint_section *add_problem (); + opt_hint_section *add_details (); + opt_hint_section *add_suggestion (); + + /* A human-readable title for the hint. */ + + const char *get_hint_title () const { return m_hint_title; } + + /* An ID describing the hint, suitable for looking up further information + about the hint (e.g. "gcc.vect.unknown-iteration-count"). */ + + const char *get_hint_id () const { return m_hint_id; } + + void emit (const dump_location_t &loc, + enum optinfo_kind kind, + opt_pass *pass) const; + + void write_to_pp (pretty_printer *pp) const OVERRIDE; + +private: + const char *m_hint_title; + const char *m_hint_id; +}; + +/* The various kinds of opt_hint_section. */ + +enum opt_hint_section_kind +{ + SK_PROBLEM, + SK_DETAILS, + SK_SUGGESTION +}; + +/* A section within a hint. */ + +class opt_hint_section : public opt_hint_compound +{ +public: + opt_hint_section (enum opt_hint_section_kind kind) + : m_kind (kind) + { + } + + void write_to_pp (pretty_printer *pp) const OVERRIDE; + json::value *to_json () const OVERRIDE; + +private: + enum opt_hint_section_kind m_kind; +}; + +/* An ordered list of child nodes, presented as numbered subitems. */ + +class opt_hint_ol : public opt_hint_compound +{ +public: + void write_to_pp (pretty_printer *pp) const OVERRIDE; + json::value *to_json () const OVERRIDE; +}; + +/* A paragraph of text. */ + +class opt_hint_para : public opt_hint_node +{ +public: + opt_hint_para (const char *text) : m_text (xstrdup (text)) + {} + ~opt_hint_para () { free (m_text); } + + void write_to_pp (pretty_printer *pp) const OVERRIDE; + json::value *to_json () const OVERRIDE; + +private: + char *m_text; // FIXME: i18n? +}; + +/* A reference to a statement, to be presented to the user as its source + location. */ + +class opt_hint_gimple : public opt_hint_node +{ +public: + opt_hint_gimple (gimple *stmt) : m_stmt (stmt) + { + } + + void write_to_pp (pretty_printer *pp) const OVERRIDE; + json::value *to_json () const OVERRIDE; + +private: + gimple *m_stmt; // FIXME: interaction with GC? +}; + +/* A rich_location. If not UNKNOWN_LOCATION, it will be presented to the + user as if a diagnostic. + + Any fix-it hints will be presented to the user as a diff. */ + +class opt_hint_location : public opt_hint_node +{ +public: + opt_hint_location (rich_location *rich_loc) : m_rich_loc (rich_loc) + { + } + ~opt_hint_location (); + + void write_to_pp (pretty_printer *pp) const OVERRIDE; + json::value *to_json () const OVERRIDE; + +private: + rich_location *m_rich_loc; +}; + +/* A diagram. */ + +class opt_hint_diagram : public opt_hint_node +{ +public: + opt_hint_diagram (element *diagram) : m_diagram (diagram) + { + } + ~opt_hint_diagram (); + + void write_to_pp (pretty_printer *pp) const OVERRIDE; + json::value *to_json () const OVERRIDE; + +private: + element *m_diagram; +}; + +#endif /* #ifndef GCC_OPT_HINT_H */ diff --git a/gcc/optinfo-emit-json.cc b/gcc/optinfo-emit-json.cc index 2199d52..fab1c5c 100644 --- a/gcc/optinfo-emit-json.cc +++ b/gcc/optinfo-emit-json.cc @@ -527,6 +527,23 @@ optimization_records_maybe_pop_dump_scope () the_json_writer->pop_scope (); } +/* FIXME. */ + +void +optimization_records_record_opt_hint (const dump_location_t &loc, + enum optinfo_kind kind, + opt_pass *pass, + json::object *jv) +{ + /* Assume recording is enabled. */ + gcc_assert (the_json_writer); + + optinfo info (loc, kind, pass); + json::object *optinfo = the_json_writer->optinfo_to_json (&info); + optinfo->set ("hint", jv); + the_json_writer->add_record (optinfo); +} + #if CHECKING_P namespace selftest { diff --git a/gcc/optinfo-emit-json.h b/gcc/optinfo-emit-json.h index 3628d56..ea6d684 100644 --- a/gcc/optinfo-emit-json.h +++ b/gcc/optinfo-emit-json.h @@ -21,6 +21,9 @@ along with GCC; see the file COPYING3. If not see #ifndef GCC_OPTINFO_EMIT_JSON_H #define GCC_OPTINFO_EMIT_JSON_H +#include "optinfo.h" +#include "json.h" + class optinfo; struct opt_pass; @@ -32,5 +35,10 @@ extern bool optimization_records_enabled_p (); extern void optimization_records_maybe_record_optinfo (const optinfo *); extern void optimization_records_maybe_pop_dump_scope (); +extern void optimization_records_maybe_record_optinfo (const optinfo *); +extern void optimization_records_record_opt_hint (const dump_location_t &loc, + enum optinfo_kind kind, + opt_pass *pass, + json::object *jv); #endif /* #ifndef GCC_OPTINFO_EMIT_JSON_H */ diff --git a/gcc/selftest-diagram.h b/gcc/selftest-diagram.h new file mode 100644 index 0000000..8c176b4 --- /dev/null +++ b/gcc/selftest-diagram.h @@ -0,0 +1,67 @@ +/* Selftest support for diagram.h + Copyright (C) 2018 Free Software Foundation, Inc. + Contributed by David Malcolm <dmalc...@redhat.com>. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#ifndef GCC_SELFTEST_DIAGRAM_H +#define GCC_SELFTEST_DIAGRAM_H + +/* The selftest code should entirely disappear in a production + configuration, hence we guard all of it with #if CHECKING_P. */ + +#if CHECKING_P + +class text_buffer; +class element; + +#include "selftest.h" + +namespace selftest { + +/* Implementation detail of ASSERT_TEXT_BUFFER_EQ. */ + +extern void verify_text_buffer (const location &loc, + text_buffer *buf, + const char *expected_text); + +/* Assert that BUF->print is EXPECTED_TEXT. */ + +#define ASSERT_TEXT_BUFFER_EQ(BUF, EXPECTED_TEXT) \ + SELFTEST_BEGIN_STMT \ + verify_text_buffer (SELFTEST_LOCATION, (BUF), (EXPECTED_TEXT)); \ + SELFTEST_END_STMT + +/* Implementation detail of ASSERT_ELEMENT_PRINT. */ + +extern void verify_element_print (const location &loc, + element *element, + const char *expected_text); + +/* Assert that ELEMENT->print_to_pp is EXPECTED_TEXT. */ + +#define ASSERT_ELEMENT_PRINT(ELEMENT, EXPECTED_TEXT) \ + SELFTEST_BEGIN_STMT \ + verify_element_print (SELFTEST_LOCATION, (ELEMENT), \ + (EXPECTED_TEXT)); \ + SELFTEST_END_STMT + +} // namespace selftest + +#endif /* CHECKING_P */ + +#endif /* GCC_SELFTEST_DIAGRAM_H */ diff --git a/gcc/selftest-run-tests.c b/gcc/selftest-run-tests.c index 4a6d559..f79fda2 100644 --- a/gcc/selftest-run-tests.c +++ b/gcc/selftest-run-tests.c @@ -78,6 +78,7 @@ selftest::run_tests () optinfo_emit_json_cc_tests (); /* Mid-level data structures. */ + diagram_cc_tests (); input_c_tests (); vec_perm_indices_c_tests (); tree_c_tests (); @@ -95,6 +96,7 @@ selftest::run_tests () spellcheck_tree_c_tests (); tree_cfg_c_tests (); attribute_c_tests (); + tree_vect_hints_cc_tests (); /* This one relies on most of the above. */ function_tests_c_tests (); diff --git a/gcc/selftest.h b/gcc/selftest.h index 16c8b59..e31b78d 100644 --- a/gcc/selftest.h +++ b/gcc/selftest.h @@ -217,6 +217,7 @@ extern void attribute_c_tests (); extern void bitmap_c_tests (); extern void diagnostic_c_tests (); extern void diagnostic_show_locus_c_tests (); +extern void diagram_cc_tests (); extern void dumpfile_c_tests (); extern void edit_context_c_tests (); extern void et_forest_c_tests (); @@ -245,6 +246,7 @@ extern void sreal_c_tests (); extern void store_merging_c_tests (); extern void tree_c_tests (); extern void tree_cfg_c_tests (); +extern void tree_vect_hints_cc_tests (); extern void typed_splay_tree_c_tests (); extern void unique_ptr_tests_cc_tests (); extern void vec_c_tests (); diff --git a/gcc/tree-vect-hints.cc b/gcc/tree-vect-hints.cc new file mode 100644 index 0000000..ac9f253 --- /dev/null +++ b/gcc/tree-vect-hints.cc @@ -0,0 +1,474 @@ +/* "Rich hints" to the user about vectorization. + Copyright (C) 2018 Free Software Foundation, Inc. + Contributed by David Malcolm <dmalc...@redhat.com>. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "tree.h" +#include "gimple.h" +#include "predict.h" +#include "tree-pass.h" +#include "ssa.h" +#include "cgraph.h" +#include "fold-const.h" +#include "stor-layout.h" +#include "gimple-iterator.h" +#include "gimple-walk.h" +#include "tree-ssa-loop-manip.h" +#include "tree-ssa-loop-niter.h" +#include "tree-cfg.h" +#include "cfgloop.h" +#include "tree-vectorizer.h" + +#include "pretty-print.h" +#include "gcc-rich-location.h" +#include "selftest.h" +#include "selftest-diagram.h" +#include "diagram.h" +#include "opt-hint.h" + +/* Enough information to be able to draw a diagram summarizing how + a loop was vectorized, without requiring the creation of a + _loop_vec_info (which would require actual code). */ + +struct loop_vec_schematic +{ + /* Construct from a loop_vec_info. */ + loop_vec_schematic (loop_vec_info loop_vinfo) + : m_has_scalar_fallback (LOOP_REQUIRES_VERSIONING (loop_vinfo)), + m_has_prolog (false /* FIXME. */), m_has_epilog (true /* FIXME. */), + m_vector_factor (LOOP_VINFO_VECT_FACTOR (loop_vinfo)) + {} + + /* Constructor for use in selftests. */ + loop_vec_schematic (bool has_scalar_fallback, bool has_prolog, + bool has_epilog, int vector_factor) + : m_has_scalar_fallback (has_scalar_fallback), + m_has_prolog (has_prolog), m_has_epilog (has_epilog), + m_vector_factor (vector_factor) + {} + + bool m_has_scalar_fallback; + bool m_has_prolog; + bool m_has_epilog; + poly_uint64 m_vector_factor; +}; + +/* Make a new box_element, containing the given TITLE, and, optionally the + given EXTRA_LINES. */ + +static element * +make_box (const char *title, auto_vec<element *> *extra_lines = NULL) +{ + element *title_element = new text_element (title); + if (extra_lines) + { + grid_layout *grid = new grid_layout (1, 1 + extra_lines->length ()); + grid->set_child (0, 0, title_element); + unsigned i; + element *line; + FOR_EACH_VEC_ELT (*extra_lines, i, line) + grid->set_child (0, i + 1, line); + return new box_element (grid); + } + else + return new box_element (title_element); +} + +/* Subroutine of make_diagram. */ + +static element * +make_element_vectorized_loop (const loop_vec_schematic &schematic) +{ + auto_vec<element *> extra_lines; + pretty_printer pp; + pp_string (&pp, " iteration count: n / "); + pp_wide_integer (&pp, schematic.m_vector_factor); + extra_lines.safe_push (new text_element (pp_formatted_text (&pp))); + return make_box ("vectorized loop", &extra_lines); +} + +/* Subroutine of make_diagram. */ + +static element * +make_element_prolog (const loop_vec_schematic &schematic) +{ + auto_vec<element *> extra_lines; + pretty_printer pp; + pp_string (&pp, " iteration count: [0.."); + pp_wide_integer (&pp, schematic.m_vector_factor - 1); + pp_string (&pp, "]"); + extra_lines.safe_push (new text_element (pp_formatted_text (&pp))); + return make_box ("prologue", &extra_lines); +} + +/* Subroutine of make_diagram. */ + +static element * +make_element_epilog (const loop_vec_schematic &schematic) +{ + auto_vec<element *> extra_lines; + pretty_printer pp; + pp_string (&pp, " iteration count: [0.."); + pp_wide_integer (&pp, schematic.m_vector_factor - 1); + pp_string (&pp, "]"); + extra_lines.safe_push (new text_element (pp_formatted_text (&pp))); + return make_box ("epilogue", &extra_lines); +} + +/* Subroutine of make_diagram. */ + +static element * +make_element_run_time_tests (const loop_vec_schematic &schematic) +{ + return make_box ("run-time tests"); +} + +/* Subroutine of make_diagram. */ + +static element * +make_element_scalar_loop (const loop_vec_schematic &schematic) +{ + auto_vec<element *> extra_lines; + pretty_printer pp; + pp_string (&pp, " iteration count: n"); + extra_lines.safe_push (new text_element (pp_formatted_text (&pp))); + return make_box ("scalar loop", &extra_lines); +} + +/* Generate a diagram from SCHEMATIC, adjusting the diagram based on the + presence of a scalar fallback (with run-time tests), and on the + presence of a prologue and/or epilogue. + Show iteration counts, comparing the scalar vs vectorized (e.g. N vs N/4). + + TODO: show the estimated cost in each part of the diagram + + Caller takes ownership of the returned element. */ + +static element * +make_diagram (const loop_vec_schematic &schematic) +{ + element *vectorized_loop = make_element_vectorized_loop (schematic); + element *vectorized = vectorized_loop; + if (schematic.m_has_prolog || schematic.m_has_epilog) + { + int grid_height = 1; + if (schematic.m_has_prolog) + grid_height += 2; + if (schematic.m_has_epilog) + grid_height += 2; + grid_layout *grid = new grid_layout (1, grid_height); + int y = 0; + if (schematic.m_has_prolog) + { + grid->set_child (0, 0, make_element_prolog (schematic)); + grid->set_child (0, 1, wiring_element::make_vert ()); + y += 2; + } + grid->set_child (0, y, vectorized_loop); + y += 1; + if (schematic.m_has_epilog) + { + grid->set_child (0, y, wiring_element::make_vert ()); + grid->set_child (0, y + 1, make_element_epilog (schematic)); + } + vectorized = grid; + } + + if (schematic.m_has_scalar_fallback) + { + element *run_time_tests = make_element_run_time_tests (schematic); + element *scalar_loop = make_element_scalar_loop (schematic); + grid_layout *grid = new grid_layout (3, 4); + grid->set_child (1, 0, wiring_element::make_vert ()); + grid->set_child (0, 1, wiring_element::make_se ()); + grid->set_child (1, 1, run_time_tests); + grid->set_child (2, 1, wiring_element::make_sw ()); + grid->set_child (2, 2, scalar_loop); + grid->set_child (0, 2, vectorized); + grid->set_child (0, 3, wiring_element::make_ne ()); + grid->set_child (1, 3, wiring_element::make_sew ()); + grid->set_child (2, 3, wiring_element::make_nw ()); + return grid; + } + else + return vectorized; +} + +/* Subroutine of emit_vect_loop_hints. Given BASE_OBJECT within a + data reference, attempt to locate the corresponfing PARM_DECL. + If found, add it to VARS. */ + +static void +find_decl_for_restrict (hash_set<tree> *vars, tree base_object) +{ + if (TREE_CODE (base_object) != MEM_REF) + return; + tree reffed = TREE_OPERAND (base_object, 0); + if (TREE_CODE (reffed) != SSA_NAME) + return; + tree var = SSA_NAME_VAR (reffed); + if (var == NULL_TREE) + return; + if (TREE_CODE (var) != PARM_DECL) + return; + vars->add (var); +} + +/* Emit more details about vectorization, and how the user could help things + be faster. + + Ideas: + "Problem: I don't know how many iterations the loop will have. I + predict that vectorization will help when N > $something, but if + the loop is consistently shorter than that, vectorization may + simply bloat the binary. + Suggestion: use PGO." + + "Problem: I couldn't prove that these data accesses were aligned to a + ALIGNMENT-byte boundary, so I had to add a run-time test, falling back + to a scalar loop. + Details: + statements in question + Suggestion: FIXME." + + "Problem: I couldn't prove that these array accesses don't alias, so + I had to add a run-time test, falling back to a scalar loop. + Details: + statements in question + + Suggestion: FIXME.". */ + +void +emit_vect_loop_hints (loop_vec_info loop_vinfo) +{ + const int factor = 4; // FIXME + + /* Emit a summary of information about the loop. */ + { + opt_hint_root hint ("Loop vectorized", "gcc.vect.success"); + hint.add_para ("I was able to vectorize this loop, using SIMD" + " instructions to reduce the number of iterations" + " by a factor of %i.", + factor); + hint.add_location (vect_location.get_location_t ()); + loop_vec_schematic schematic (loop_vinfo); + hint.add_diagram (make_diagram (schematic)); + hint.emit (vect_location, OPTINFO_KIND_SUCCESS, current_pass); + } + + /* Issue a hint about aliasing. */ + if (LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo)) + { + opt_hint_root hint ("Run-time aliasing check", + "gcc.vect.loop-requires-versioning-for-alias"); + + /* Problem. */ + { + opt_hint_section *problem = hint.add_problem (); + problem->add_para ("I couldn't prove that these data references" + " don't alias, so I had to add a run-time test," + " falling back to a scalar loop for when they" + " do."); + } + + /* Details. */ + { + opt_hint_section *details = hint.add_details (); + unsigned i; + dr_with_seg_len_pair_t *dr_pair; + opt_hint_ol *ol = new opt_hint_ol (); + details->add_child (ol); + FOR_EACH_VEC_ELT (loop_vinfo->comp_alias_ddrs, i, dr_pair) + { + opt_hint_compound *li = new opt_hint_compound (); + ol->add_child (li); + li->add_para ("This read/write pair could alias:"); + location_t first_loc + = EXPR_LOCATION (dr_pair->first.dr->indices.base_object); + location_t second_loc + = EXPR_LOCATION (dr_pair->second.dr->indices.base_object); + rich_location *rich_loc = new gcc_rich_location (first_loc); + rich_loc->add_range (second_loc, true); + li->add_location (rich_loc); + } + } + + /* Suggestions. */ + { + opt_hint_section *suggestion = hint.add_suggestion (); + suggestion->add_para ("If you know that the buffers cannot overlap in" + // FIXME: convert back to %qs + " memory, marking them with %s will" + " allow me to assume it when optimizing this" + " loop, and eliminate the run-time test.", + "restrict"); + hash_set<tree> vars; + unsigned i; + dr_with_seg_len_pair_t *dr_pair; + FOR_EACH_VEC_ELT (loop_vinfo->comp_alias_ddrs, i, dr_pair) + { + find_decl_for_restrict (&vars, + dr_pair->first.dr->indices.base_object); + find_decl_for_restrict (&vars, + dr_pair->second.dr->indices.base_object); + } + rich_location *rich_loc = new gcc_rich_location (UNKNOWN_LOCATION); + suggestion->add_location (rich_loc); + for (hash_set<tree>::iterator it = vars.begin (); + it != vars.end (); ++it) + { + location_t decl_loc = DECL_SOURCE_LOCATION (*it); + if (decl_loc != UNKNOWN_LOCATION) + rich_loc->add_fixit_insert_before + (get_pure_location (decl_loc), " restrict "); + } + } + + hint.emit (vect_location, OPTINFO_KIND_SUCCESS, current_pass); + } + + /* Issue a hint about the epilogue. */ + if (LOOP_VINFO_PEELING_FOR_NITER (loop_vinfo)) + { + opt_hint_root hint ("Epilogue required for peeling", + "gcc.vect.loop-requires-epilogue-for-peeling"); + + /* Problem. */ + { + opt_hint_section *problem = hint.add_problem (); + problem->add_para ("I couldn't prove that the number of iterations is" + " a multiple of %i, so I had to add an \"epilogue\"" + " to cover the final 0-%i iterations. ", + factor, factor - 1); + } + + /* Details. */ + { + opt_hint_section *details = hint.add_details (); + details->add_para ("FIXME: add a source code highlight or other" + " visualization here?"); + } + + /* Suggestions. */ + { + opt_hint_section *suggestion = hint.add_suggestion (); + suggestion->add_para ("FIXME: add a suggestion here?"); + } + + hint.emit (vect_location, OPTINFO_KIND_SUCCESS, current_pass); + } +} + +#if CHECKING_P + +namespace selftest { + +/* Implementation detail of ASSERT_SCHEMATIC_PRINT. */ + +static void +verify_schematic_print (const location &loc, + const loop_vec_schematic &schematic, + const char *expected_text) +{ + element *el = make_diagram (schematic); + verify_element_print (loc, el, expected_text); + delete el; +} + +/* Assert that make_diagram (SCHEMATIC)->print() is EXPECTED_TEXT. */ + +#define ASSERT_SCHEMATIC_PRINT(SCHEMATIC, EXPECTED_TEXT) \ + SELFTEST_BEGIN_STMT \ + verify_schematic_print (SELFTEST_LOCATION, (SCHEMATIC), \ + (EXPECTED_TEXT)); \ + SELFTEST_END_STMT + +/* Verify that make_diagram works as expected. */ + +static void +test_make_diagram () +{ + ASSERT_SCHEMATIC_PRINT (loop_vec_schematic (/*has_scalar_fallback=*/false, + /*has_prolog=*/false, + /*has_epilog=*/false, + /*vector_factor=*/4), + "+------------------------+\n" + "|vectorized loop |\n" + "| iteration count: n / 4|\n" + "+------------------------+\n"); + + ASSERT_SCHEMATIC_PRINT + (loop_vec_schematic (/*has_scalar_fallback=*/true, + /*has_prolog=*/false, + /*has_epilog=*/false, + /*vector_factor=*/4), + " |\n" + " +--------------+\n" + " +------------|run-time tests|-----------+\n" + " | +--------------+ |\n" + "+------------------------+ +--------------------+\n" + "|vectorized loop | |scalar loop |\n" + "| iteration count: n / 4| | iteration count: n|\n" + "+------------------------+ +--------------------+\n" + " | |\n" + " +--------------------+------------------+\n" + " |\n"); + + ASSERT_SCHEMATIC_PRINT + (loop_vec_schematic (/*has_scalar_fallback=*/true, + /*has_prolog=*/true, + /*has_epilog=*/true, + /*vector_factor=*/4), + " |\n" + " +--------------+\n" + " +-------------|run-time tests|-----------+\n" + " | +--------------+ |\n" + "+-------------------------+ +--------------------+\n" + "|prologue | |scalar loop |\n" + "| iteration count: [0..3]| | iteration count: n|\n" + "+-------------------------+ | |\n" + " | | |\n" + "+-------------------------+ | |\n" + "|vectorized loop | | |\n" + "| iteration count: n / 4 | | |\n" + "+-------------------------+ | |\n" + " | | |\n" + "+-------------------------+ | |\n" + "|epilogue | | |\n" + "| iteration count: [0..3]| | |\n" + "+-------------------------+ +--------------------+\n" + " | |\n" + " +---------------------+------------------+\n" + " |\n"); +} + +/* Run all of the selftests within this file. */ + +void +tree_vect_hints_cc_tests () +{ + test_make_diagram (); +} + +} // namespace selftest + +#endif /* CHECKING_P */ diff --git a/gcc/tree-vectorizer.c b/gcc/tree-vectorizer.c index c60d0d9..88365ad 100644 --- a/gcc/tree-vectorizer.c +++ b/gcc/tree-vectorizer.c @@ -805,6 +805,8 @@ try_vectorize_loop_1 (hash_table<simduid_to_vf> *&simduid_to_vf_htab, "loop vectorized using variable length vectors"); } + emit_vect_loop_hints (loop_vinfo); + loop_p new_loop = vect_transform_loop (loop_vinfo); (*num_vectorized_loops)++; /* Now that the loop has been vectorized, allow it to be unrolled diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h index 4673764..e822c08 100644 --- a/gcc/tree-vectorizer.h +++ b/gcc/tree-vectorizer.h @@ -1674,4 +1674,7 @@ unsigned vectorize_loops (void); bool vect_stmt_in_region_p (vec_info *, gimple *); void vect_free_loop_info_assumptions (struct loop *); +/* In tree-vect-hints.cc. */ +extern void emit_vect_loop_hints (loop_vec_info loop_vinfo); + #endif /* GCC_TREE_VECTORIZER_H */ -- 1.8.5.3