Changeset 7db4836


Ignore:
Timestamp:
Feb 28, 2019, 2:54:05 PM (3 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr
Children:
5934c5f, 6e4411f
Parents:
58732d1
Message:

thesis: modify conversion graphs to use subfigures

Location:
doc/theses/aaron_moss_PhD/phd
Files:
4 added
3 edited

Legend:

Unmodified
Added
Removed
  • doc/theses/aaron_moss_PhD/phd/resolution-heuristics.tex

    r58732d1 r7db4836  
    3636With more specificity, the cost is a lexicographically-ordered tuple, where each element corresponds to a particular kind of conversion.
    3737In Bilson's design, conversion cost is a 3-tuple, $(unsafe, poly, safe)$, where $unsafe$ is the count of unsafe (narrowing) conversions, $poly$ is the count of polymorphic type bindings, and $safe$ is the sum of the degree of safe (widening) conversions.
    38 Degree of safe conversion is calculated as path weight in a directed graph of safe conversions between types; both Bilson's version and the current version of this graph are in Figure~\ref{safe-conv-graph-fig}.
     38Degree of safe conversion is calculated as path weight in a directed graph of safe conversions between types; Bilson's version and the current version of this graph are in Figures~\ref{bilson-conv-fig} and~\ref{extended-conv-fig}, respectively.
    3939The safe conversion graph is designed such that the common type $c$ of two types $u$ and $v$ is compatible with the C standard definitions from \cite[\S{}6.3.1.8]{C11} and can be calculated as the unique type minimizing the sum of the path weights of $\overrightarrow{uc}$ and $\overrightarrow{vc}$.
    4040The following example lists the cost in the Bilson model of calling each of the following functions with two !int! parameters:
     
    5151Note that safe and unsafe conversions are handled differently; \CFA{} counts distance of safe conversions (\eg{} !int! to !long! is cheaper than !int! to !unsigned long!), while only counting the number of unsafe conversions (\eg{} !int! to !char! and !int! to !short! both have unsafe cost 1, as in the first two declarations above).
    5252These costs are summed over the parameters in a call; in the example above, the cost of the two !int! to !long! conversions for the fourth declaration sum equal to the one !int! to !unsigned long! conversion in the fifth.
     53
     54\begin{figure}
     55        \centering
     56        \begin{subfigure}[h]{3in}
     57                \includegraphics{figures/bilson-conv-graph}
     58                \caption{Bilson} \label{bilson-conv-fig}
     59        \end{subfigure}~\begin{subfigure}[h]{3in}
     60                \includegraphics{figures/extended-conv-graph}
     61                \caption{Extended} \label{extended-conv-fig}
     62        \end{subfigure}
     63        % \includegraphics{figures/safe-conv-graph}
     64        \caption[Safe conversion graphs.]{Safe conversion graphs. In both graphs, plain arcs have cost $safe = 1, sign = 0$ while dashed sign-conversion arcs have cost $safe = 1, sign = 1$. As per \cite[\S{}6.3.1.8]{C11}, types promote to types of the same signedness with greater rank, from \lstinline{signed} to \lstinline{unsigned} with the same rank, and from \lstinline{unsigned} to \lstinline{signed} with greater size. The arc from \lstinline{unsigned long} to \lstinline{long long} (highlighted in red in \ref{bilson-conv-fig}) is deliberately omitted in \ref{extended-conv-fig}, as on the presented system \lstinline{sizeof(long) == sizeof(long long)}.}
     65        \label{safe-conv-fig}
     66\end{figure}
    5367
    5468As part of adding reference types to \CFA{} (see Section~\ref{type-features-sec}), Schluntz added a new $reference$ element to the cost tuple, which counts the number of implicit reference-to-rvalue conversions performed so that candidate interpretations can be distinguished by how closely they match the nesting of reference types; since references are meant to act almost indistinguishably from lvalues, this $reference$ element is the least significant in the lexicographic comparison of cost tuples.
     
    95109A final refinement I have made to the \CFA{} cost model is with regard to choosing among arithmetic conversions.
    96110The C standard \cite[\S{}6.3.1.8]{C11} states that the common type of !int! and !unsigned int! is !unsigned int! and that the common type of !int! and !long! is !long!, but does not provide guidance for making a choice among conversions.
    97 Bilson's \CFACC{} uses conversion costs based off the left graph in Figure~\ref{safe-conv-graph-fig}.
     111Bilson's \CFACC{} uses conversion costs based off Figure~\ref{bilson-conv-fig}.
    98112However, Bilson's design results in inconsistent and somewhat surprising costs, with conversion to the next-larger same-sign type generally (but not always) double the cost of conversion to the !unsigned! type of the same size.
    99113In the redesign, for consistency with the approach of the usual arithmetic conversions, which select a common type primarily based on size, but secondarily on sign, arcs in the new graph are annotated with whether they represent a sign change, and such sign changes are summed in a new $sign$ cost element that lexicographically succeeds $safe$.
    100114This means that sign conversions are approximately the same cost as widening conversions, but slightly more expensive (as opposed to less expensive in Bilson's graph).
    101 
    102 \begin{figure}
    103         \centering
    104         \includegraphics{figures/safe-conv-graph}
    105         \caption[Safe conversion graphs.]{Safe conversion graphs; Bilson's on the left, the extended graph on the right. In both graphs, plain arcs have cost $safe = 1, sign = 0$ while dashed sign-conversion arcs have cost $safe = 1, sign = 1$. As per \cite[\S{}6.3.1.8]{C11}, types promote to types of the same signedness with greater rank, from \lstinline{signed} to \lstinline{unsigned} with the same rank, and from \lstinline{unsigned} to \lstinline{signed} with greater size. The arc from \lstinline{unsigned long} to \lstinline{long long} is deliberately omitted in the modified graph, as on the presented system \lstinline{sizeof(long) == sizeof(long long)}.}
    106         \label{safe-conv-graph-fig}
    107 \end{figure}
    108115
    109116With these modifications, the current \CFA{} cost tuple is as follows:
Note: See TracChangeset for help on using the changeset viewer.