diff options
Diffstat (limited to 'chapter02')
| -rw-r--r-- | chapter02/README.md | 13 | ||||
| -rw-r--r-- | chapter02/docs/02-lattice.gv | 35 | ||||
| -rw-r--r-- | chapter02/docs/02-lattice.svg | 143 | ||||
| -rw-r--r-- | chapter02/docs/lattice.gv | 40 | ||||
| -rw-r--r-- | chapter02/docs/lattice.svg | 159 |
5 files changed, 206 insertions, 184 deletions
diff --git a/chapter02/README.md b/chapter02/README.md index db23796d..04e34eb9 100644 --- a/chapter02/README.md +++ b/chapter02/README.md @@ -93,17 +93,18 @@ Type ``` It turns out that the set of values associated with a Type at a specific Node -can be conveniently represented as a "lattice" -https://en.wikipedia.org/wiki/Lattice_(order) -. Our lattice has the following structure: +can be conveniently represented as a *lattice* +[wiki/Lattice_(order)](https://en.wikipedia.org/wiki/Lattice_(order)). Our lattice has the following structure: - + Our lattice elements can be one of three types: -* The highest element is "top", denoted by T; assigning T means that the Node's value may or may not be a compile time constant. +* The highest element is "top", denoted by ⊤; assigning ⊤ means that the Node's + value may or may not be a compile time constant. * All elements in the middle are constants. -* The lowest is "bottom", denoted by ⊥; assigning ⊥ means that we know that the Node's value is **not** a compile time constant. +* The lowest is "bottom", denoted by ⊥; assigning ⊥ means that we know that the + Node's value is **not** a compile time constant. An invariant of peephole optimizations is that the type of a Node always moves *up* the lattice (towards "top"); peepholes are *pessmistic* assuming the worst diff --git a/chapter02/docs/02-lattice.gv b/chapter02/docs/02-lattice.gv deleted file mode 100644 index 4faa0e11..00000000 --- a/chapter02/docs/02-lattice.gv +++ /dev/null @@ -1,35 +0,0 @@ -digraph Lattice { - // Define nodes - node [shape=circle, style=filled, fillcolor=lightblue]; - Top [label="⊤"]; - Bottom [label="⊥"]; - - A [label="MIN_INT"]; - B [label="..." shape=none style=none]; - C [label="-1"]; - D [label="0"]; - E [label="1"]; - F [label="..." shape=none style=none]; - G [label="MAX_INT"]; - - - // Define edges - Top -> A [arrowhead=none]; - Top -> B [arrowhead=none]; - Top -> C [arrowhead=none]; - Top -> D [arrowhead=none]; - Top -> E [arrowhead=none]; - Top -> F [arrowhead=none]; - Top -> G [arrowhead=none]; - A -> Bottom [arrowhead=none]; - B -> Bottom [arrowhead=none]; - C -> Bottom [arrowhead=none]; - D -> Bottom [arrowhead=none]; - E -> Bottom [arrowhead=none]; - F -> Bottom [arrowhead=none]; - G -> Bottom [arrowhead=none]; - - // Additional customization - {rank=same; A; B; C; D; E; F; G; } - {rank=same; Bottom;} -} diff --git a/chapter02/docs/02-lattice.svg b/chapter02/docs/02-lattice.svg deleted file mode 100644 index 218acc6a..00000000 --- a/chapter02/docs/02-lattice.svg +++ /dev/null @@ -1,143 +0,0 @@ -<?xml version="1.0" encoding="UTF-8" standalone="no"?> -<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" - "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> -<!-- Generated by graphviz version 2.43.0 (0) - --> -<!-- Title: Lattice Pages: 1 --> -<svg width="548pt" height="266pt" - viewBox="0.00 0.00 547.59 265.88" xmlns="http://www.w3.org/2000/svg"> - <g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 261.88)"> - <title>Lattice</title> - <polygon fill="white" stroke="transparent" points="-4,4 -4,-261.88 543.59,-261.88 543.59,4 -4,4"/> - <!-- Top --> - <g id="node1" class="node"> - <title>Top</title> - <ellipse fill="lightblue" stroke="black" cx="269.65" cy="-238.39" rx="19.5" ry="19.5"/> - <text text-anchor="middle" x="269.65" y="-234.69" font-family="Times,serif" font-size="14.00">⊤</text> - </g> - <!-- A --> - <g id="node3" class="node"> - <title>A</title> - <ellipse fill="lightblue" stroke="black" cx="52.65" cy="-128.94" rx="52.79" ry="52.79"/> - <text text-anchor="middle" x="52.65" y="-125.24" font-family="Times,serif" font-size="14.00">MIN_INT</text> - </g> - <!-- Top->A --> - <g id="edge1" class="edge"> - <title>Top->A</title> - <path fill="none" stroke="black" - d="M250.55,-233.09C220.3,-225.77 160.13,-209.08 114.65,-182.89 106.3,-178.08 98.02,-172.1 90.35,-165.89"/> - </g> - <!-- B --> - <g id="node4" class="node"> - <title>B</title> - <text text-anchor="middle" x="150.65" y="-125.24" font-family="Times,serif" font-size="14.00">...</text> - </g> - <!-- Top->B --> - <g id="edge2" class="edge"> - <title>Top->B</title> - <path fill="none" stroke="black" - d="M252.34,-228.66C234.5,-219.09 206.55,-202.47 186.65,-182.89 175.87,-172.28 166.38,-158 159.86,-146.95"/> - </g> - <!-- C --> - <g id="node5" class="node"> - <title>C</title> - <ellipse fill="lightblue" stroke="black" cx="214.65" cy="-128.94" rx="19.5" ry="19.5"/> - <text text-anchor="middle" x="214.65" y="-125.24" font-family="Times,serif" font-size="14.00">-1</text> - </g> - <!-- Top->C --> - <g id="edge3" class="edge"> - <title>Top->C</title> - <path fill="none" stroke="black" d="M261.05,-220.6C250.72,-200.41 233.48,-166.74 223.18,-146.61"/> - </g> - <!-- D --> - <g id="node6" class="node"> - <title>D</title> - <ellipse fill="lightblue" stroke="black" cx="269.65" cy="-128.94" rx="18" ry="18"/> - <text text-anchor="middle" x="269.65" y="-125.24" font-family="Times,serif" font-size="14.00">0</text> - </g> - <!-- Top->D --> - <g id="edge4" class="edge"> - <title>Top->D</title> - <path fill="none" stroke="black" d="M269.65,-218.67C269.65,-198.47 269.65,-166.57 269.65,-147.03"/> - </g> - <!-- E --> - <g id="node7" class="node"> - <title>E</title> - <ellipse fill="lightblue" stroke="black" cx="323.65" cy="-128.94" rx="18" ry="18"/> - <text text-anchor="middle" x="323.65" y="-125.24" font-family="Times,serif" font-size="14.00">1</text> - </g> - <!-- Top->E --> - <g id="edge5" class="edge"> - <title>Top->E</title> - <path fill="none" stroke="black" d="M278.08,-220.6C288.46,-199.94 305.94,-165.16 315.97,-145.22"/> - </g> - <!-- F --> - <g id="node8" class="node"> - <title>F</title> - <text text-anchor="middle" x="386.65" y="-125.24" font-family="Times,serif" font-size="14.00">...</text> - </g> - <!-- Top->F --> - <g id="edge6" class="edge"> - <title>Top->F</title> - <path fill="none" stroke="black" - d="M286.52,-228.57C303.92,-218.93 331.18,-202.25 350.65,-182.89 361.2,-172.38 370.57,-158.37 377.1,-147.4"/> - </g> - <!-- G --> - <g id="node9" class="node"> - <title>G</title> - <ellipse fill="lightblue" stroke="black" cx="485.65" cy="-128.94" rx="53.89" ry="53.89"/> - <text text-anchor="middle" x="485.65" y="-125.24" font-family="Times,serif" font-size="14.00">MAX_INT</text> - </g> - <!-- Top->G --> - <g id="edge7" class="edge"> - <title>Top->G</title> - <path fill="none" stroke="black" - d="M288.46,-233C318.29,-225.56 377.63,-208.69 422.65,-182.89 430.83,-178.2 438.98,-172.41 446.57,-166.39"/> - </g> - <!-- Bottom --> - <g id="node2" class="node"> - <title>Bottom</title> - <ellipse fill="lightblue" stroke="black" cx="269.65" cy="-19.5" rx="19.5" ry="19.5"/> - <text text-anchor="middle" x="269.65" y="-15.8" font-family="Times,serif" font-size="14.00">⊥</text> - </g> - <!-- A->Bottom --> - <g id="edge8" class="edge"> - <title>A->Bottom</title> - <path fill="none" stroke="black" - d="M90.35,-91.99C98.02,-85.79 106.3,-79.8 114.65,-75 160.13,-48.81 220.3,-32.11 250.55,-24.79"/> - </g> - <!-- B->Bottom --> - <g id="edge9" class="edge"> - <title>B->Bottom</title> - <path fill="none" stroke="black" - d="M159.86,-110.94C166.38,-99.88 175.87,-85.6 186.65,-75 206.55,-55.41 234.5,-38.79 252.34,-29.22"/> - </g> - <!-- C->Bottom --> - <g id="edge10" class="edge"> - <title>C->Bottom</title> - <path fill="none" stroke="black" d="M223.24,-111.15C233.57,-90.97 250.81,-57.3 261.11,-37.17"/> - </g> - <!-- D->Bottom --> - <g id="edge11" class="edge"> - <title>D->Bottom</title> - <path fill="none" stroke="black" d="M269.65,-110.68C269.65,-91.1 269.65,-59.3 269.65,-39.16"/> - </g> - <!-- E->Bottom --> - <g id="edge12" class="edge"> - <title>E->Bottom</title> - <path fill="none" stroke="black" d="M315.91,-112.55C305.88,-92.59 288.44,-57.9 278.08,-37.28"/> - </g> - <!-- F->Bottom --> - <g id="edge13" class="edge"> - <title>F->Bottom</title> - <path fill="none" stroke="black" - d="M377.1,-110.49C370.57,-99.52 361.2,-85.5 350.65,-75 331.18,-55.63 303.92,-38.95 286.52,-29.31"/> - </g> - <!-- G->Bottom --> - <g id="edge14" class="edge"> - <title>G->Bottom</title> - <path fill="none" stroke="black" - d="M446.57,-91.49C438.98,-85.48 430.83,-79.69 422.65,-75 377.63,-49.19 318.29,-32.33 288.46,-24.88"/> - </g> - </g> -</svg> diff --git a/chapter02/docs/lattice.gv b/chapter02/docs/lattice.gv new file mode 100644 index 00000000..fe8df136 --- /dev/null +++ b/chapter02/docs/lattice.gv @@ -0,0 +1,40 @@ +digraph Lattice { + compound = true; + // Define nodes + splines=false; + node [shape=circle, style=filled]; + nodesep=0.6; + + // ---------------------- + // Integers + INT_TOP [label=<<B>⊤</B >:int>, fillcolor=lightblue, shape=oval]; + INT_BOT [label=<<B>⊥</B>:int>, fillcolor=lightblue, shape=oval]; + + INT_MIN [label="-n" , fillcolor=lightblue]; + INT_MINDOTS [label="...", fillcolor=lightblue shape=oval]; + INT_MINUS [label="-1" , fillcolor=lightblue]; + INT_ZERO [label="0" , fillcolor=lightblue]; + INT_PLUS [label="1" , fillcolor=lightblue]; + INT_MAXDOTS [label="...", fillcolor=lightblue, shape=oval]; + INT_MAX [label="+n" , fillcolor=lightblue]; + + INT_TOP -> INT_MIN; + INT_TOP -> INT_MINDOTS; + INT_TOP -> INT_MINUS; + INT_TOP -> INT_ZERO; + INT_TOP -> INT_PLUS; + INT_TOP -> INT_MAXDOTS; + INT_TOP -> INT_MAX; + INT_MIN -> INT_BOT; + INT_MINDOTS -> INT_BOT; + INT_MINUS -> INT_BOT; + INT_ZERO -> INT_BOT; + INT_PLUS -> INT_BOT; + INT_MAXDOTS -> INT_BOT; + INT_MAX -> INT_BOT; + + INT_MIN -> INT_MINDOTS -> INT_MINUS -> INT_ZERO -> INT_PLUS -> INT_MAXDOTS -> INT_MAX [style=invis]; + + // Additional customization + {rank=same; INT_MIN; INT_MINDOTS; INT_MINUS; INT_ZERO; INT_PLUS; INT_MAXDOTS; INT_MAX; } +} diff --git a/chapter02/docs/lattice.svg b/chapter02/docs/lattice.svg new file mode 100644 index 00000000..b11d57aa --- /dev/null +++ b/chapter02/docs/lattice.svg @@ -0,0 +1,159 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
+ "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
+<!-- Generated by graphviz version 12.2.0 (20241103.1931)
+ -->
+<!-- Title: Lattice Pages: 1 -->
+<svg width="564pt" height="194pt"
+ viewBox="0.00 0.00 563.75 194.31" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
+<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 190.31)">
+<title>Lattice</title>
+<polygon fill="white" stroke="none" points="-4,4 -4,-190.31 559.75,-190.31 559.75,4 -4,4"/>
+<!-- INT_TOP -->
+<g id="node1" class="node">
+<title>INT_TOP</title>
+<ellipse fill="lightblue" stroke="black" cx="276.6" cy="-168.31" rx="33.95" ry="18"/>
+<text text-anchor="start" x="259.72" y="-164.26" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊤</text>
+<text text-anchor="start" x="275.47" y="-164.26" font-family="Times New Roman,serif" font-size="14.00">:int</text>
+</g>
+<!-- INT_MIN -->
+<g id="node3" class="node">
+<title>INT_MIN</title>
+<ellipse fill="lightblue" stroke="black" cx="18.6" cy="-93.15" rx="18.6" ry="18.6"/>
+<text text-anchor="middle" x="18.6" y="-88.1" font-family="Times New Roman,serif" font-size="14.00">-n</text>
+</g>
+<!-- INT_TOP->INT_MIN -->
+<g id="edge1" class="edge">
+<title>INT_TOP->INT_MIN</title>
+<path fill="none" stroke="black" d="M247,-158.92C197.13,-144.78 96.96,-116.37 47.53,-102.36"/>
+<polygon fill="black" stroke="black" points="48.71,-99.06 38.13,-99.69 46.8,-105.79 48.71,-99.06"/>
+</g>
+<!-- INT_MINDOTS -->
+<g id="node4" class="node">
+<title>INT_MINDOTS</title>
+<ellipse fill="lightblue" stroke="black" cx="107.6" cy="-93.15" rx="27" ry="18"/>
+<text text-anchor="middle" x="107.6" y="-88.1" font-family="Times New Roman,serif" font-size="14.00">...</text>
+</g>
+<!-- INT_TOP->INT_MINDOTS -->
+<g id="edge2" class="edge">
+<title>INT_TOP->INT_MINDOTS</title>
+<path fill="none" stroke="black" d="M250.93,-156.2C221.31,-143.38 172.55,-122.27 140.26,-108.29"/>
+<polygon fill="black" stroke="black" points="141.94,-105.21 131.38,-104.45 139.16,-111.63 141.94,-105.21"/>
+</g>
+<!-- INT_MINUS -->
+<g id="node5" class="node">
+<title>INT_MINUS</title>
+<ellipse fill="lightblue" stroke="black" cx="196.6" cy="-93.15" rx="18.6" ry="18.6"/>
+<text text-anchor="middle" x="196.6" y="-88.1" font-family="Times New Roman,serif" font-size="14.00">-1</text>
+</g>
+<!-- INT_TOP->INT_MINUS -->
+<g id="edge3" class="edge">
+<title>INT_TOP->INT_MINUS</title>
+<path fill="none" stroke="black" d="M260.02,-152.15C247.97,-141.13 231.55,-126.11 218.43,-114.12"/>
+<polygon fill="black" stroke="black" points="220.83,-111.57 211.09,-107.41 216.11,-116.74 220.83,-111.57"/>
+</g>
+<!-- INT_ZERO -->
+<g id="node6" class="node">
+<title>INT_ZERO</title>
+<ellipse fill="lightblue" stroke="black" cx="276.6" cy="-93.15" rx="18" ry="18"/>
+<text text-anchor="middle" x="276.6" y="-88.1" font-family="Times New Roman,serif" font-size="14.00">0</text>
+</g>
+<!-- INT_TOP->INT_ZERO -->
+<g id="edge4" class="edge">
+<title>INT_TOP->INT_ZERO</title>
+<path fill="none" stroke="black" d="M276.6,-149.97C276.6,-141.92 276.6,-132.14 276.6,-123.02"/>
+<polygon fill="black" stroke="black" points="280.1,-123.13 276.6,-113.13 273.1,-123.13 280.1,-123.13"/>
+</g>
+<!-- INT_PLUS -->
+<g id="node7" class="node">
+<title>INT_PLUS</title>
+<ellipse fill="lightblue" stroke="black" cx="355.6" cy="-93.15" rx="18" ry="18"/>
+<text text-anchor="middle" x="355.6" y="-88.1" font-family="Times New Roman,serif" font-size="14.00">1</text>
+</g>
+<!-- INT_TOP->INT_PLUS -->
+<g id="edge5" class="edge">
+<title>INT_TOP->INT_PLUS</title>
+<path fill="none" stroke="black" d="M292.96,-152.15C305.01,-141 321.48,-125.74 334.51,-113.68"/>
+<polygon fill="black" stroke="black" points="336.82,-116.31 341.78,-106.95 332.06,-111.18 336.82,-116.31"/>
+</g>
+<!-- INT_MAXDOTS -->
+<g id="node8" class="node">
+<title>INT_MAXDOTS</title>
+<ellipse fill="lightblue" stroke="black" cx="443.6" cy="-93.15" rx="27" ry="18"/>
+<text text-anchor="middle" x="443.6" y="-88.1" font-family="Times New Roman,serif" font-size="14.00">...</text>
+</g>
+<!-- INT_TOP->INT_MAXDOTS -->
+<g id="edge6" class="edge">
+<title>INT_TOP->INT_MAXDOTS</title>
+<path fill="none" stroke="black" d="M302.32,-156.04C331.46,-143.28 379,-122.45 410.79,-108.53"/>
+<polygon fill="black" stroke="black" points="412.17,-111.74 419.93,-104.52 409.36,-105.33 412.17,-111.74"/>
+</g>
+<!-- INT_MAX -->
+<g id="node9" class="node">
+<title>INT_MAX</title>
+<ellipse fill="lightblue" stroke="black" cx="534.6" cy="-93.15" rx="21.15" ry="21.15"/>
+<text text-anchor="middle" x="534.6" y="-88.1" font-family="Times New Roman,serif" font-size="14.00">+n</text>
+</g>
+<!-- INT_TOP->INT_MAX -->
+<g id="edge7" class="edge">
+<title>INT_TOP->INT_MAX</title>
+<path fill="none" stroke="black" d="M306.19,-158.92C355.31,-144.99 453.21,-117.23 503.38,-103.01"/>
+<polygon fill="black" stroke="black" points="504.07,-106.45 512.73,-100.35 502.16,-99.71 504.07,-106.45"/>
+</g>
+<!-- INT_BOT -->
+<g id="node2" class="node">
+<title>INT_BOT</title>
+<ellipse fill="lightblue" stroke="black" cx="276.6" cy="-18" rx="33.95" ry="18"/>
+<text text-anchor="start" x="259.72" y="-13.95" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊥</text>
+<text text-anchor="start" x="275.47" y="-13.95" font-family="Times New Roman,serif" font-size="14.00">:int</text>
+</g>
+<!-- INT_MIN->INT_BOT -->
+<g id="edge8" class="edge">
+<title>INT_MIN->INT_BOT</title>
+<path fill="none" stroke="black" d="M36.33,-87.13C77.31,-75.51 179.45,-46.55 236.48,-30.38"/>
+<polygon fill="black" stroke="black" points="237.13,-33.83 245.79,-27.73 235.22,-27.09 237.13,-33.83"/>
+</g>
+<!-- INT_MIN->INT_MINDOTS -->
+<!-- INT_MINDOTS->INT_BOT -->
+<g id="edge9" class="edge">
+<title>INT_MINDOTS->INT_BOT</title>
+<path fill="none" stroke="black" d="M129.69,-82.59C157.87,-70.39 206.96,-49.14 240.58,-34.59"/>
+<polygon fill="black" stroke="black" points="241.73,-37.91 249.51,-30.72 238.95,-31.48 241.73,-37.91"/>
+</g>
+<!-- INT_MINDOTS->INT_MINUS -->
+<!-- INT_MINUS->INT_BOT -->
+<g id="edge10" class="edge">
+<title>INT_MINUS->INT_BOT</title>
+<path fill="none" stroke="black" d="M210.17,-79.75C221.61,-69.28 238.28,-54.04 252.06,-41.44"/>
+<polygon fill="black" stroke="black" points="254.05,-44.36 259.07,-35.03 249.33,-39.19 254.05,-44.36"/>
+</g>
+<!-- INT_MINUS->INT_ZERO -->
+<!-- INT_ZERO->INT_BOT -->
+<g id="edge11" class="edge">
+<title>INT_ZERO->INT_BOT</title>
+<path fill="none" stroke="black" d="M276.6,-74.82C276.6,-66.77 276.6,-56.98 276.6,-47.86"/>
+<polygon fill="black" stroke="black" points="280.1,-47.98 276.6,-37.98 273.1,-47.98 280.1,-47.98"/>
+</g>
+<!-- INT_ZERO->INT_PLUS -->
+<!-- INT_PLUS->INT_BOT -->
+<g id="edge12" class="edge">
+<title>INT_PLUS->INT_BOT</title>
+<path fill="none" stroke="black" d="M342.55,-80.07C331.3,-69.66 314.75,-54.33 301.04,-41.64"/>
+<polygon fill="black" stroke="black" points="303.78,-39.4 294.06,-35.17 299.02,-44.53 303.78,-39.4"/>
+</g>
+<!-- INT_PLUS->INT_MAXDOTS -->
+<!-- INT_MAXDOTS->INT_BOT -->
+<g id="edge13" class="edge">
+<title>INT_MAXDOTS->INT_BOT</title>
+<path fill="none" stroke="black" d="M421.42,-82.44C393.56,-70.24 345.4,-49.14 312.32,-34.65"/>
+<polygon fill="black" stroke="black" points="314.1,-31.61 303.54,-30.8 311.29,-38.02 314.1,-31.61"/>
+</g>
+<!-- INT_MAXDOTS->INT_MAX -->
+<!-- INT_MAX->INT_BOT -->
+<g id="edge14" class="edge">
+<title>INT_MAX->INT_BOT</title>
+<path fill="none" stroke="black" d="M514.35,-86.41C471.9,-74.38 372.87,-46.3 316.93,-30.44"/>
+<polygon fill="black" stroke="black" points="318.05,-27.12 307.47,-27.76 316.14,-33.85 318.05,-27.12"/>
+</g>
+</g>
+</svg>
|
