>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.
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
