Peter Goodman pgoodman

This document explains how I would implement an SSA-based compiler if I was writing one today.

This document is intentionally opinionated. It just tells you how I would do it. This document is intended for anyone who has read about SSA and understands the concept, but is confused about how exactly to put it into practice. If you're that person, then I'm here to show you a way to do it that works well for me. If you're looking for a review of other ways to do it, I recommend this post.

My approach works well when implementing the compiler in any language that easily permits cyclic mutable data structures. I know from experience that it'll work great in C++, C#, or Java. The memory management of this approach is simple (and I'll explain it), so you won't have to stress about use after frees.

I like my approach because it leads to an ergonomic API by minimizing the amount of special cases you have to worry about. Most of the compiler is analyses and transformations ov

Note to readers: This document is an early draft of a model for memory-safe references that I've been working on for the last ~2 years. While I think it is quite promising, the design is unfinished. The "regions" that I present in this document have not been given a formal semantics, and I have not explained where they originate from. My goal is merely to convince you that the design is promising, and that if seen to completion, it would advance the frontier of zero-cost memory safety.

Update March 2025: I am working on a newer version of this proposal, that aims to simplify the model substantially. When I have finished that proposal, I will put a link here.

Update August 2025: Verdagon has written an awesome blog post that explains this proposal at a high level. I recommend you check it out!

Abstract

In this document, I present a novel model for memory-safe references that aims to significantly improve upon the Rust-inspired model that Mojo c

Some quick notes about the CVE-2023-3079(V8 type confusion), no PoC yet.

Official patch: https://chromium-review.googlesource.com/c/v8/v8/+/4584248

Patch come from KeyedStoreIC::StoreElementHandler(), it returns fast path code(Turbofan builtin) for keyed store depends on "receiver_map" and "store_mode". Based on the content of this function is all about element STORE, I personally believe that this is an OOB writes vulnerability.

If we divide the PoC exploration into two parts based on this func, they are:

Debug with GDB on macOS 11

The big reason to do this is that LLDB has no ability to "follow-fork-mode child", in other words, a multi-process target that doesn't have a single-process mode (or, a bug that only manifests when in multi-process mode) is going to be difficult or impossible to debug, especially if you have to run the target over and over in order to make the bug manifest. If you have a repeatable bug, no big deal, break on the fork from the parent process and attach to the child in a second lldb instance. Otherwise, read on.

Install GDB

Don't make the mistake of thinking you can just brew install gdb. Currently this is version 10.2 and it's mostly broken, with at least two annoying bugs as of April 29th 2021, but the big one is https://sourceware.org/bugzilla/show_bug.cgi?id=24069

$ xcode-select install  # install the XCode command-line tools

When you download a file from internet, the file would have the attribute com.apple.quarantine.

For example, when I downloaded gcc-arm-none-eabi-9-2019-q4-major-mac.tar.bz2, the file had it.

% xattr Downloads/gcc-arm-none-eabi-9-2019-q4-major-mac.tar.bz2 
com.apple.lastuseddate#PS
com.apple.macl
com.apple.metadata:kMDItemDownloadedDate
com.apple.metadata:kMDItemWhereFroms
com.apple.quarantine

	// Length-segregated string tables for length < 16. You use a separate overflow table for length >= 16.
	// By segregating like this you can pack the string data in the table itself tightly without any padding. The datapath
	// is uniform and efficient for all lengths < 16 by using unaligned 16-byte SIMD loads/compares and masking off the length prefix.

	// One of the benefits of packing string data tightly for each length table is that you can afford to reduce the load factor
	// on shorter length tables without hurting space utilization too much. This can push hole-in-one rates into the 95% range without
	// too much of a negative impact on cache utilization.

	// Since get() takes a vector register as an argument with the key, you want to shape the upstream code so the string to be queried
	// is naturally in a vector. For example, in an optimized identifier lexer you should already have a SIMD fast path for length < 16

	// This is another take on the mark-compact collector from https://gist.github.com/pervognsen/7fe51bef8977cb249ac4c6f830f818a5
	// To avoid having to do global compaction, our object indices will have two parts: a block index and a block offset.
	// Within a block we have the same linear older-to-newer ordering by offset. But now blocks are allowed to have different ages.
	// The block ages are defined by their position in a linked list: There's oldest_block and newest_block indices and then
	// previous_block[block_index] for each block. This enables newest-to-oldest block iteration and the linked-list structure
	// means that we can free an empty block by unlinking it. When a block is reused, it becomes the newest_block. Now, instead
	// of only compacting within a block we will actually be coalescing across an age range of blocks. By doing so, we will usually
	// be able to empty out entire blocks from the newer part of that age range, so they can be reused. This should have very similar
	// performance characteri

	from dataclasses import dataclass
	from typing import List, Tuple, Union, Dict, Iterator, Optional
	import sys
	import itertools

	Id = int

	class UnionFind:
	parents: List[Id]

	# IDA (disassembler) and Hex-Rays (decompiler) plugin for Apple AMX
	#
	# WIP research. (This was edited to add more info after someone posted it to
	# Hacker News. Click "Revisions" to see full changes.)
	#
	# Copyright (c) 2020 dougallj


	# Based on Python port of VMX intrinsics plugin:
	# Copyright (c) 2019 w4kfu - Synacktiv

	Welcome to Jordan's grab-bag of common Binary Ninja Snippets.

	These snippets are meant to run with the Binary Ninja Snippets Plugin
	(http://github.com/Vector35/snippets) though they can all also be pasted
	directly into the python console or turned into stand-alone plugins if needed.

	To install the entire collection at once, just install the Snippets plugin via
	the plugin manager (CMD/CTL-SHIFT-M), confirm the Snippet Editor works
	(Tool/Snippets/Snippet Editor), and unzip this bundle (Download ZIP above) into
	your Snippets folder.