On Sat, Oct 06, 2018 at 12:38:49AM +0900, Akira Yokosawa wrote:
> >From 89be258c86a41713c327995d8ed46c12c3fba736 Mon Sep 17 00:00:00 2001
> From: Akira Yokosawa <akiyks@xxxxxxxxx>
> Date: Sat, 6 Oct 2018 00:11:04 +0900
> Subject: [PATCH] toolsoftrade: Employ new scheme for snippet in newly added sections
>
> These code snippets don't have corresponding code under CodeSamples.
> Embed them in the "VerbatimL" environment with labels to lines
> referenced from the text.
>
> A few trivial typos are fixed as well.
>
> Signed-off-by: Akira Yokosawa <akiyks@xxxxxxxxx>
> ---
> Hi Paul,
>
> I see you have used verbbox for new code snippets. VerbatimL can be used
> instead as shown in this patch. Hopefully this can provide a few
> templates for you to use the new scheme without putting actual code
> under CodeSamples. In these snippets, labelbase has the same string as
> the listing's label, give or take the leading prefix ("lst:" -> "ln:").
>
> If you don't feel like using the new scheme for the moment, I'd be happy
> to do the conversion on behalf of you.
>
> BTW, the expansion on accessing shared variable makes a lot of sense
> to me. I'm a bit afraid of possible conflict with your ongoing expansion
> in toolsoftrade, but I thought it is better rather than later.
Good catch, applied and queued, thank you!
What can I say? Force of habit and all that. But I have nearby
examples now, at least. ;-)
Thanx, Paul
> Thanks, Akira
> --
> toolsoftrade/toolsoftrade.tex | 224 ++++++++++++++++++++++--------------------
> 1 file changed, 117 insertions(+), 107 deletions(-)
>
> diff --git a/toolsoftrade/toolsoftrade.tex b/toolsoftrade/toolsoftrade.tex
> index 53c69b2..5216054 100644
> --- a/toolsoftrade/toolsoftrade.tex
> +++ b/toolsoftrade/toolsoftrade.tex
> @@ -1661,29 +1661,25 @@ in long-past pre-C11 days.
> A short answer to this question is ``they lived dangerously''.
>
> \begin{listing}[tbp]
> -{ \scriptsize
> -\begin{verbbox}
> - 1 ptr = global_ptr;
> - 2 if (ptr != NULL && ptr < high_address)
> - 3 do_low(ptr);
> -\end{verbbox}
> -}
> -\centering
> -\theverbbox
> +\begin{linelabel}[ln:toolsoftrade:Living Dangerously Early 1990s Style]
> +\begin{VerbatimL}[commandchars=\\\{\}]
> +ptr = global_ptr;\lnlbl{temp}
> +if (ptr != NULL && ptr < high_address)
> + do_low(ptr);
> +\end{VerbatimL}
> +\end{linelabel}
> \caption{Living Dangerously Early 1990s Style}
> \label{lst:toolsoftrade:Living Dangerously Early 1990s Style}
> \end{listing}
>
> \begin{listing}[tbp]
> -{ \scriptsize
> -\begin{verbbox}
> - 1 if (global_ptr != NULL &&
> - 2 global_ptr < high_address)
> - 3 do_low(global_ptr);
> -\end{verbbox}
> -}
> -\centering
> -\theverbbox
> +\begin{linelabel}[ln:toolsoftrade:C Compilers Can Invent Loads]
> +\begin{VerbatimL}[commandchars=\\\{\}]
> +if (global_ptr != NULL &&\lnlbl{if:a}
> + global_ptr < high_address)\lnlbl{if:b}
> + do_low(global_ptr);\lnlbl{do_low}
> +\end{VerbatimL}
> +\end{linelabel}
> \caption{C Compilers Can Invent Loads}
> \label{lst:toolsoftrade:C Compilers Can Invent Loads}
> \end{listing}
> @@ -1696,7 +1692,8 @@ Nevertheless, problems did arise, as shown in
> Listing~\ref{lst:toolsoftrade:Living Dangerously Early 1990s Style},
> which the compiler is within its rights to transform into
> Listing~\ref{lst:toolsoftrade:C Compilers Can Invent Loads}.
> -As you can, the temporary on line~1 of
> +As you can, the temporary on
> +line~\ref{ln:toolsoftrade:Living Dangerously Early 1990s Style:temp} of
> Listing~\ref{lst:toolsoftrade:Living Dangerously Early 1990s Style}
> has been optimized away, so that \co{global_ptr} will been loaded
> up to three times.
> @@ -1708,14 +1705,18 @@ up to three times.
> \QuickQuizAnswer{
> Suppose that \co{global_ptr} is initially non-\co{NULL},
> but that some other thread sets \co{global_ptr} to \co{NULL}.
> - Suppose further that line~1 of the transformed code
> + \begin{lineref}[ln:toolsoftrade:C Compilers Can Invent Loads]
> + Suppose further that line~\lnref{if:a} of the transformed code
> (Listing~\ref{lst:toolsoftrade:C Compilers Can Invent Loads})
> executes just before \co{global_ptr} is set to \co{NULL} and
> - line~2 just after.
> - Then line~1 will conclude that \co{global_ptr} is non-\co{NULL},
> - line~2 will conclude that it is less than \co{high_address},
> - so that line~3 passes \co{do_low()} a \co{NULL} pointer,
> + line~\lnref{if:b} just after.
> + Then line~\lnref{if:a} will conclude that
> + \co{global_ptr} is non-\co{NULL},
> + line~\lnref{if:b} will conclude that it is less than
> + \co{high_address},
> + so that line~\lnref{do_low} passes \co{do_low()} a \co{NULL} pointer,
> which \co{do_low()} just might not be prepared to deal with.
> + \end{lineref}
> } \QuickQuizEnd
>
> Section~\ref{sec:toolsoftrade:Shared-Variable Shenanigans}
> @@ -1750,7 +1751,8 @@ or shared-variable shenanigans, as described below.
> {\bf Load tearing} occurs when the compiler uses multiple load
> instructions for a single access.
> For example, the compiler could in theory compile the load from
> -\co{global_ptr} (see line~1 of
> +\co{global_ptr} (see
> +line~\ref{ln:toolsoftrade:Living Dangerously Early 1990s Style:temp} of
> Listing~\ref{lst:toolsoftrade:Living Dangerously Early 1990s Style})
> as a series of one-byte loads.
> If some other thread was concurrently setting \co{global_ptr} to
> @@ -1776,31 +1778,29 @@ Again, the C standard simply has no choice in the general case, given
> the possibility of code using 32-bit integers running on a 16-bit system.
>
> \begin{listing}[tbp]
> -{ \scriptsize
> -\begin{verbbox}
> - 1 if (!need_to_stop)
> - 2 for (;;) {
> - 3 do_something_quickly();
> - 4 do_something_quickly();
> - 5 do_something_quickly();
> - 6 do_something_quickly();
> - 7 do_something_quickly();
> - 8 do_something_quickly();
> - 9 do_something_quickly();
> -10 do_something_quickly();
> -11 do_something_quickly();
> -12 do_something_quickly();
> -13 do_something_quickly();
> -14 do_something_quickly();
> -15 do_something_quickly();
> -16 do_something_quickly();
> -17 do_something_quickly();
> -18 do_something_quickly();
> -19 }
> -\end{verbbox}
> -}
> -\centering
> -\theverbbox
> +\begin{linelabel}[ln:toolsoftrade:C Compilers Can Fuse Loads]
> +\begin{VerbatimL}[commandchars=\\\[\]]
> +if (!need_to_stop)
> + for (;;) {\lnlbl[loop:b]
> + do_something_quickly();
> + do_something_quickly();
> + do_something_quickly();
> + do_something_quickly();
> + do_something_quickly();
> + do_something_quickly();
> + do_something_quickly();
> + do_something_quickly();
> + do_something_quickly();
> + do_something_quickly();
> + do_something_quickly();
> + do_something_quickly();
> + do_something_quickly();
> + do_something_quickly();
> + do_something_quickly();
> + do_something_quickly();
> + }\lnlbl[loop:e]
> +\end{VerbatimL}
> +\end{linelabel}
> \caption{C Compilers Can Fuse Loads}
> \label{lst:toolsoftrade:C Compilers Can Fuse Loads}
> \end{listing}
> @@ -1822,8 +1822,11 @@ Worse yet, because the compiler knows that \co{do_something_quickly()}
> does not store to \co{need_to_stop}, the compiler could quite reasonably
> decide to check this variable only once, resulting in the code shown in
> Listing~\ref{lst:toolsoftrade:C Compilers Can Fuse Loads}.
> -Once entered, the loop on lines~2-19 will never stop, regardless of how
> +\begin{lineref}[ln:toolsoftrade:C Compilers Can Fuse Loads]
> +Once entered, the loop on
> +lines~\lnref{loop:b}-\lnref{loop:e} will never stop, regardless of how
> many times some other thread stores a non-zero value to \co{need_to_stop}.
> +\end{lineref}
> The result will at best be disappointment, and might well also
> include severe physical damage.
>
> @@ -1837,46 +1840,48 @@ very little chance that some other thread could load the value from the
> first store.
>
> \begin{listing}[tbp]
> -{ \scriptsize
> -\begin{verbbox}
> - 1 void shut_it_down(void)
> - 2 {
> - 3 status = SHUTTING_DOWN; /* BUGGY!!! */
> - 4 start_shutdown();
> - 5 while (!other_task_ready)
> - 6 continue;
> - 7 finish_shutdown();
> - 8 status = SHUT_DOWN;
> - 9 do_something_else();
> -10 }
> -11
> -12 void work_until_shut_down(void)
> -13 {
> -14 while (status != SHUTTING_DOWN)
> -15 do_more_work();
> -16 other_task_ready = 1; /* BUGGY!!! */
> -17 }
> -\end{verbbox}
> +\begin{linelabel}[ln:toolsoftrade:C Compilers Can Fuse Stores]
> +\begin{VerbatimL}[commandchars=\\\[\]]
> +void shut_it_down(void)
> +{
> + status = SHUTTING_DOWN; /* BUGGY!!! */\lnlbl[store:a]
> + start_shutdown();
> + while (!other_task_ready)\lnlbl[loop:b]
> + continue;\lnlbl[loop:e]
> + finish_shutdown();\lnlbl[finish]
> + status = SHUT_DOWN;\lnlbl[store:b]
> + do_something_else();
> }
> -\centering
> -\theverbbox
> +
> +void work_until_shut_down(void)
> +{
> + while (status != SHUTTING_DOWN)\lnlbl[until:loop:b]
> + do_more_work();\lnlbl[until:loop:e]
> + other_task_ready = 1; /* BUGGY!!! */\lnlbl[other:store]
> +}
> +\end{VerbatimL}
> +\end{linelabel}
> \caption{C Compilers Can Fuse Stores}
> \label{lst:toolsoftrade:C Compilers Can Fuse Stores}
> \end{listing}
>
> However, there are exceptions, for example as shown in
> Listing~\ref{lst:toolsoftrade:C Compilers Can Fuse Stores}.
> +\begin{lineref}[ln:toolsoftrade:C Compilers Can Fuse Stores]
> The function \co{shut_it_down(void)()} stores to the shared
> -variable \co{status} on lines~3 and~8, and so assuming that neither
> +variable \co{status} on lines~\lnref{store:a} and~\lnref{store:b},
> +and so assuming that neither
> \co{start_shutdown()} nor \co{finish_shutdown()} access \co{status},
> the compiler could reasonably remove the store to \co{status} on
> -line~3.
> +line~\lnref{store:a}.
> Unfortunately, this would mean that \co{work_until_shut_down()} would
> -never exit its loop spanning lines~14 and~15, and thus would never set
> +never exit its loop spanning
> +lines~\lnref{until:loop:b} and~\lnref{until:loop:e}, and thus would never set
> \co{other_task_ready}, which would in turn mean that \co{shut_it_down()}
> -would never exit its loop spanning lines~5 and~6, even if
> +would never exit its loop spanning
> +lines~\lnref{loop:b} and~\lnref{loop:e}, even if
> the compiler chooses not to fuse the successive loads from
> -\co{(!other_task_ready} on line~5.
> +\co{(!other_task_ready)} on line~\lnref{loop:b}.
>
> And there are more problems with the code in
> Listing~\ref{lst:toolsoftrade:C Compilers Can Fuse Stores},
> @@ -1889,16 +1894,19 @@ modern superscalar microprocessors.
> It is also another reason why the code in
> Listing~\ref{lst:toolsoftrade:C Compilers Can Fuse Stores}
> is buggy.
> -For example, suppose that the \co{do_more_work()} function on line~15
> +For example, suppose that the \co{do_more_work()} function on
> +line~\lnref{until:loop:e}
> does not access \co{other_task_ready}.
> Then the compiler would be within its rights to move the assignment
> -to \co{other_task_ready} on line~16 to precede line~14, which might
> +to \co{other_task_ready} on
> +line~\lnref{other:store} to precede line~\lnref{until:loop:b}, which might
> be a great disappointment for anyone hoping that the last call to
> -\co{do_more_work()} on line~15 happens before the call to
> -\co{finish_shutdown()} on line~7.
> +\co{do_more_work()} on line~\lnref{until:loop:e} happens before the call to
> +\co{finish_shutdown()} on line~\lnref{finish}.
> +\end{lineref}
>
> {\bf Invented loads} were illustrated by the code in
> -Listings~\ref{lst:toolsoftrade:Living Dangerously Early 1990s Style})
> +Listings~\ref{lst:toolsoftrade:Living Dangerously Early 1990s Style}
> and~\ref{lst:toolsoftrade:C Compilers Can Invent Loads},
> in which the compiler optimized away a temporary variable,
> thus loading from a shared variable more often than intended.
> @@ -1910,50 +1918,49 @@ These hoisting optimizations are not uncommon, and can cause significant
> increases in cache misses, and thus significant degradation of
> both performance and scalability.
>
> +\begin{lineref}[ln:toolsoftrade:C Compilers Can Fuse Stores]
> {\bf Invented stores} can occur in a number of situations.
> For example, a compiler emitting code for \co{work_until_shut_down()} in
> Listing~\ref{lst:toolsoftrade:C Compilers Can Fuse Stores}
> might notice that \co{other_task_ready} is not accessed by
> -\co{do_more_work()}, and stored to on line~16.
> +\co{do_more_work()}, and stored to on line~\lnref{other:store}.
> If \co{do_more_work()} was a complex inline function, it might be
> necessary to do a register spill, in which case one attractive
> place to use for temporary storage is \co{other_task_ready}.
> After all, there are no accesses to it, so what is the harm?
>
> Of course, a non-zero store to this variable at just the wrong time
> -would result in the \co{while} loop on line~5 terminating
> +would result in the \co{while} loop on
> +line~\lnref{loop:b} terminating
> prematurely, again allowing \co{finish_shutdown()} to run
> concurrently with \co{do_more_work()}.
> Given that the entire point of this \co{while} appears to be to
> prevent such concurrency, this is not a good thing.
> +\end{lineref}
>
> \begin{listing}[tbp]
> -{ \scriptsize
> -\begin{verbbox}
> - 1 if (condition)
> - 2 a = 1;
> - 3 else
> - 4 do_a_bunch_of_stuff();
> -\end{verbbox}
> -}
> -\centering
> -\theverbbox
> +\begin{linelabel}[ln:toolsoftrade:Inviting an Invented Store]
> +\begin{VerbatimL}[commandchars=\\\{\}]
> +if (condition)
> + a = 1;
> +else
> + do_a_bunch_of_stuff();
> +\end{VerbatimL}
> +\end{linelabel}
> \caption{Inviting an Invented Store}
> \label{lst:toolsoftrade:Inviting an Invented Store}
> \end{listing}
>
> \begin{listing}[tbp]
> -{ \scriptsize
> -\begin{verbbox}
> - 1 a = 1;
> - 2 if (!condition) {
> - 3 a = 0;
> - 4 do_a_bunch_of_stuff();
> - 5 }
> -\end{verbbox}
> +\begin{linelabel}[ln:toolsoftrade:Compiler Invents an Invited Store]
> +\begin{VerbatimL}[commandchars=\\\[\]]
> +a = 1;\lnlbl[store:uncond]
> +if (!condition) {
> + a = 0;\lnlbl[store:cond]
> + do_a_bunch_of_stuff();
> }
> -\centering
> -\theverbbox
> +\end{VerbatimL}
> +\end{linelabel}
> \caption{Compiler Invents an Invited Store}
> \label{lst:toolsoftrade:Compiler Invents an Invited Store}
> \end{listing}
> @@ -1971,9 +1978,12 @@ might know that the value of \co{a} is initially zero,
> which might be a strong temptation to optimize away one branch
> by transforming this code to that in
> Listing~\ref{lst:toolsoftrade:Compiler Invents an Invited Store}.
> -Here, line~1 unconditionally stores \co{1} to \co{1}, then
> -resets the value back to zero on line~3 if \co{condition} was not set.
> +\begin{lineref}[ln:toolsoftrade:Compiler Invents an Invited Store]
> +Here, line~\lnref{store:uncond} unconditionally stores \co{1} to \co{a}, then
> +resets the value back to zero on
> +line~\lnref{store:cond} if \co{condition} was not set.
> This transforms the if-then-else into an if-then, saving one branch.
> +\end{lineref}
>
> Finally, pre-C11 compilers could invent writes to unrelated
> variables that happened to be adjacent to written-to
> --
> 2.7.4
>
