AND, OR, NOT, XOR: layout as sets

Some of the most important shapes on a chip are drawn by no one. The picture at the top of this page is a real logic cell, a two-input multiplexer from the open SkyWater SKY130 cell library, about 4.6 µm wide. Its designer drew green islands of silicon where transistors may form, red strips of polysilicon that will switch them, and a pale field across the top half that marks an n-type well. The small dark rectangles were not drawn by anyone. LayoutEditor computed them from the drawn layers: dark blue wherever a red strip crosses a green island outside the well, dark brown wherever it crosses one inside the well. Those twelve patches are the gates of the cell's twelve transistors, six n-channel devices along the bottom and six p-channel devices along the top. Each is 0.15 µm long, the width of the poly strip, and most are 0.42 µm wide, the height of the island under the strip; the two at the far left are wider.

Computing them is a boolean operation, a question about where shapes are that is answered with new shapes. You name two sets of shapes, say which combination of them you want, and the program writes the outline of that region onto a layer of your choice. The four basic questions are called AND, OR, NOT, and XOR, after the logic they borrow from. Merging the shapes of one layer into one outline is a special case of OR with its own pitfalls, covered in merging polygons. This note is about combining two layers, or two groups of shapes, and about why so much of layout work quietly runs on these four words.

Four questions about two regions

For a moment, stop thinking of a layer as a list of rectangles and polygons, and think of it as a region: the set of every point its shapes cover. Asked of two regions, A and B, the four questions are these.

• AND, the intersection, keeps the points that are in A and in B.
• OR, the union, keeps the points that are in A, in B, or in both. Overlap counts once.
• NOT, the difference A − B, keeps the points of A that are not in B. It is often written A AND NOT B.
• XOR, the exclusive or, keeps the points that are in exactly one of the two. It equals A − B together with B − A, which is the union with the intersection taken out.

AND, OR, and XOR give the same answer whichever region you name first. NOT does not: A − B and B − A are different shapes, and usually very different amounts of material.

The figure runs all five two-input operations on one pair of inputs. In the top-left panel, A is a copper-colored pour, 10 µm by 7 µm with one corner cut off, 68 µm² in all. B is two round pads in blue: one 3 µm across that lies entirely inside the pour, and one 3.4 µm across that hangs over its right edge. The other five panels are the results LayoutEditor computed, in purple, with gray hairlines repeating the input outlines so you can see where each result came from. Top row: A OR B, then A AND B. Bottom row: A − B, B − A, then A XOR B.

OR returns one polygon of 73.21 µm², the pour plus the part of the outer pad that sticks out past its edge. The inner pad vanishes into the pour; it adds nothing because every point of it was already covered. AND returns two polygons: the whole inner pad and the slice of the outer pad that lies over the pour, 10.91 µm² together. A − B is the pour with a round hole and a round bite out of its right edge, 57.09 µm², and it is still a single polygon. B − A is only the cap of the outer pad that hangs past the edge, 5.21 µm². The inner pad leaves no trace in it at all, because none of it lies outside A. XOR is the last two results side by side, two polygons and 62.30 µm², which is exactly the union minus the intersection.

The number of polygons is part of the answer. The same two inputs produced one, two, one, one, and two polygons, and a hole did not add a polygon at all. When a result contains more pieces or fewer than you expected, the inputs were not what you thought.

Why layout runs on them

The gates in the lead picture are the clearest reason. A process description calls them derived layers: layers no one draws, defined by a recipe over the layers people do draw. The SKY130 design-rule documentation defines a gate as poly AND diff, where diff is that process's name for the active islands. An n-channel gate is gate NOT nwell, a p-channel gate is gate AND nwell, and n-type diffusion is diff NOT nwell. A rule about how close a contact may come to a gate needs a gate layer to measure from, so a design-rule check computes one this way before it measures anything. The program behind layout versus schematic checking, which rebuilds the circuit from the drawing, finds transistors exactly like this and then takes the source and drain regions as diffusion NOT poly. How a MOSFET is drawn reads the same overlaps by eye.

Masks are built the same way. The plates a factory exposes do not always match the layers you drew one for one. Some mask layers are computed from several drawn layers, often with a step that grows or shrinks shapes, as process layers vs. drawing layers explains. Fast algorithms for these "mask operations" were already a research topic in the early 1980s, because the shapes behind a set of photomasks for a whole chip are far too many to combine by hand.

Circuit boards use the same operations, mostly out of sight. When a copper pour flows around a pad that belongs to another signal, the board tool computes the pour minus that pad grown by the required clearance, and computes it again every time you move a part. A Gerber file can even express the subtraction itself: it paints shapes in order, and a shape drawn with clear polarity erases whatever lies beneath it.

Other jobs ask for "everything except." A plate used with a negative resist, a keep-out region, or the space a fill program may use is a frame minus a layer, an operation usually called invert. In waveguide design it is common to draw only the light-guiding core and derive the etched trench beside it as the core grown by the trench width, minus the core.

How a computer decides

All four operations can run on one machine. As with a merge, picture a line sliding across the layout and stopping wherever an edge starts, ends, or crosses another edge. This time the program keeps two counts for each stretch of the line: how many shapes of A cover it, and how many shapes of B. Each operation is a rule about those two counts. OR keeps a stretch when either count is above zero. AND keeps it when both are. A − B keeps it when A's count is above zero and B's is zero. XOR keeps it when exactly one count is above zero. A result edge is written wherever the rule switches from keep to discard, and everything else is thrown away. A merge is the same machine with B left empty.

Because the program records only where the answer changes, it knows nothing about the shapes it started from. That is why a result can split into pieces, why two inputs can come back as one outline, and why a hole has to be stored in a roundabout way. GDSII, the file format most chip layouts travel in, has no way to say "hole." LayoutEditor stored the pour with its round hole as one outline of 103 corners that runs in along a short cut to the hole, around it, and back out along the same line; two of those corners repeat. Holes in polygons explains why that keyhole is legal and how to treat it.

XOR as a spot-the-difference

The exclusive or has one job the other three do not: comparing two versions of the same drawing.

The figure uses li1, the lowest wiring layer of SKY130, from the same multiplexer. The left panel is the layer as it comes in the cell library. The middle panel is an edited copy with three changes: one rectangle moved 120 nm to the right, one shape near the left edge deleted, and the top power rail drawn with an extra, overlapping piece (the dark outline). The right panel is the XOR of the two in red, over a gray outline of the original. It holds exactly three polygons. One is the deleted shape, whole. The other two are slivers 120 nm wide and 1.16 µm tall, one on each side of the moved rectangle; the strip between them is where the old and new positions overlap, so it is the same in both versions. At the rail there is nothing, because the extra piece covers metal that was already there. XOR compares covered area, not the way the area was drawn.

An empty XOR, layer by layer, is good evidence that two files hold the same geometry. Designers use it to check a file conversion, an edited cell, or the revision about to go to a factory. Real comparisons often turn up differences of a single database unit, the smallest step a file can store, left behind by rounding. Comparison tools therefore offer a tolerance, and a common way to apply one is to shrink the XOR result by a small amount and grow it back: anything thinner than twice that amount disappears, while real differences survive. When the computer moves an edge covers growing and shrinking.

A common mix-up

A boolean cuts shapes; a selection keeps them whole. "Poly AND diff" returns the small gate patches. "Poly shapes that touch diff" returns the entire poly strips that happen to cross an island, untouched. Both questions are useful, menus and rule files offer both, and they are easy to confuse because both mention two layers. In LayoutEditor's rule-file language, poly & diff cuts, while interacting(poly, diff) keeps whole shapes of poly.

NOT is not "everything else." In layout it always takes two inputs and means a difference. To get the region not covered by a layer you need a frame to subtract from, which is what an invert supplies.

The XOR of two layers is also not the same as LayoutEditor's single-layer "A xor," which keeps area covered by an odd number of shapes. On one layer, two of your own overlapping pieces cancel where they overlap. That is a test for overlaps, not a comparison.

Things that go wrong

Running NOT in the wrong order is the classic mistake. In the figure, A − B is 57.09 µm² of pour and B − A is a 5.21 µm² cap. If the result looks like the piece you meant to throw away, swap the order and run it again.

Shapes that only touch share no area. The AND of two rectangles that meet along an edge is empty, and subtracting a shape that only touches the outline of another leaves it unchanged. Whether an OR joins shapes that meet at a single corner depends on the tool's definition, which merging polygons compares.

Slivers are the quiet failure. If a cutting shape stops one nanometer short of an edge, A − B leaves a polygon one nanometer wide along that edge. You will not see it on screen, but a width check will report it and a mask writer would have to expose it. Fix the input so the edges line up instead of piling more booleans on top.

Slanted edges bring rounding. Where a slanted edge crosses another edge, the crossing point often falls between two whole database units, so each operation moves it slightly, and a long chain of booleans adds up those small moves into jogs and corners off the manufacturing grid.

Results come in pieces. An operation does not merge its output with shapes already on the target layer, and an XOR can leave touching pieces that stay separate polygons until you merge them.

Hierarchy changes what an operation can see. LayoutEditor's Boolean tool works on the shapes of the cell you are editing, and references to other cells are ignored when shapes are added to a group. Bool on Layer ignores the hierarchy and treats the layout as if it were flat. Its result is correct, but it is flat geometry that no longer repeats the way the instances do, so the file can grow; flattening describes that trade.

Inputs stay behind unless you remove them. Both of LayoutEditor's boolean commands keep the source shapes by default, so after a careless run the layer can hold the old pieces and the new result on top of each other.

Finally, an empty AND is a question, not an answer. If a recipe names the wrong layer or datatype, one input is empty, and the intersection is empty too. Before you conclude that two layers never overlap, check that both of them contain shapes.

In LayoutEditor

For two single shapes, the select mode's context menu is enough: move the mouse over the first shape, open the context menu with a right-click, choose the operation, and then click the second shape. For groups, use the Boolean tool. Select the first group and choose Set Selection to A, select the second and choose Set Selection to B, make the layer that should receive the result active, and run union, intersection, A − B, B − A, or exclusive or. The originals stay unless you ask for them to be deleted.

Bool on Layer, in the full version, works on entire layers. A dialog takes two source layers, a result layer, and the operation: A+B, A*B, A-B, B-A, and AxorB, plus single-layer operations such as A merge, A xor, and A invert, which uses the cell's bounding box as the frame. A-B (multi-shape) counts shapes, so it keeps a spot covered by two shapes on layer A and one on layer B, but not one covered by two on each. Bool on Layer ignores cell hierarchy, splits a large design into frames, and spreads the work over all processor cores.

In a rule file the operators are written as symbols: | for OR, & for AND, - for NOT, and ^ for XOR. The gates of the lead picture are three lines: layer gate = poly & diff, then layer nfet = gate - nwell and layer pfet = gate & nwell. Scripts reach the same engine through the layout's boolean tool.

One habit catches most of the failures above. Write each result to a scratch layer first and count its polygons. Then check the areas: the difference plus the intersection must equal the area of A, and the intersection plus the exclusive or must equal the union. For the figure, 57.09 + 10.91 = 68.00 µm², and 10.91 + 62.30 = 73.21 µm². Zoom in on every place where edges nearly meet, looking for slivers. Only then move the result onto the layer it belongs to and decide whether the inputs stay.