- 投稿日
React Compiler はどのように値のメモ化を決定しているのか(InferMutationAliasingRanges 篇)
React Compiler core team が 6/19 に公開した MUTABILITY_ALIASING_MODEL.md は、React における値のメモ化の決定プロセスについての詳細を提供した。 この文書では、メモ化の背後にある理論と実装の詳細が説明されており、React のパフォーマンス最適化における重要な要素となっている。
公開されたタイトルには、いかにも可変性やエイリアシングなど CS 的な視点からの仕様であるように読み取れるが、React Compiler の中で実際に独立したモジュールやクラスがあるわけではなく、設計上の「責務のまとまり」を指すものとして捉えると良い。 React Compiler に導入された新しい解析レイヤ(以降これを The Mutability & Aliasing Model と呼ぶ)の目的は、「一緒に変化する値の最小集合」と「それらを変更する命令の範囲」を特定することである。
この記事では、The Mutability & Aliasing Model の実装の一部である InferMutationAliasingRanges
について詳しく解説する。
InferMutationAliasingRanges
は、「どの値がいつからいつまで mutable だったか」を求める解析パスである。
その具体の流れは 3 段構えになっている。
グラフの構築とミューテーションの収集
effect と
mutableRange
の補正外部に漏れる副作用の決定
それぞれのフェーズをコードで追ってみる。
InferMutationAliasingRanges
の最初のフェーズでは、関数の引数や戻り値を含むすべての値をノードとして生成し、命令を走査して副作用の候補をグラフに追加する。1
ノード生成
すべての
params
,context
,returns
をAliasingState.create
で初期ノード化する
ブロック走査
Φノード:
pendingPhis
に遅延登録し、 index を保存。通常命令:
effect.kind
を見てCreate*
-> 新規ノードAssign/Alias/Capture
-> エッジ追加 (state.assign
,state.capture
)Mutate*
-> 後で処理するためmutations
配列へ格納
phi の接続 & return の alias
pendingPhis
とterminal
を使い、最後に全エッジが張られたグラフを得る。terminal
とはreturn
やthrow
など、関数の終端を表す命令である。
/**
* Part 1: Infer mutable ranges for values. We build an abstract model of
* values, the alias/capture edges between them, and the set of mutations.
* Edges and mutations are ordered, with mutations processed against the
* abstract model only after it is fully constructed by visiting all blocks
* _and_ connecting phis. Phis are considered ordered at the time of the
* phi node.
*
* This should (may?) mean that mutations are able to see the full state
* of the graph and mark all the appropriate identifiers as mutated at
* the correct point, accounting for both backward and forward edges.
* Ie a mutation of x accounts for both values that flowed into x,
* and values that x flowed into.
*/
const state = new AliasingState();
type PendingPhiOperand = {from: Place; into: Place; index: number};
const pendingPhis = new Map<BlockId, Array<PendingPhiOperand>>();
const mutations: Array<{
index: number;
id: InstructionId;
transitive: boolean;
kind: MutationKind;
place: Place;
}> = [];
const renders: Array<{index: number; place: Place}> = [];
let index = 0;
const errors = new CompilerError();
for (const param of [...fn.params, ...fn.context, fn.returns]) {
const place = param.kind === 'Identifier' ? param : param.place;
state.create(place, {kind: 'Object'});
}
/* ほかの effect は assign/capture/create の形でグラフに追加 */
その後、実際の mutation
を時間軸順に処理していく。2
for (const mutation of mutations) {
state.mutate(
mutation.index,
mutation.place.identifier,
makeInstructionId(mutation.id + 1),
mutation.transitive,
mutation.kind,
mutation.place.loc,
errors,
);
}
このとき、state.mutate
のキーとなる実装は AliasingState.mutate
である。3
AliasingState.mutate
は「いま起きた 1 個のミューテーションが、いつ・だれまで波及するか」を BFS でシミュレーションして、各 Identifier
ノードに
lastMutated
(最後に触られた時刻 = 副作用の順序)mutableRange.end
(実際の IR 上で「ここ以降は変更済み」と分かる命令番号)local
,transitive
(直接 vs. 伝搬で壊れたか、さらに Definite / Conditional の強度付き)
を刻み込む。これが後続パスの可変性の判定と外部に漏れる副作用の基礎になる。
AliasingState.mutate
はまず、初期ノードを backwards に入れ、エッジごとに「forward or backward に進むか / transitive を引き継ぐか」を切り替えながら広げていく。4
const queue: Array<{
place: Identifier;
transitive: boolean;
direction: 'backwards' | 'forwards';
}> = [{place: start, transitive, direction: 'backwards'}];
while (queue.length !== 0) {
const {place: current, transitive, direction} = queue.pop()!;
// ①ノード更新
// ②辺をたどって enqueue
}
まずは、mutableRange
を伸ばす。解析時は end
にmutation の直後の命令 IDが来るので、それより短ければ上書きする。
その後、以下のように local / transitive をセットする。より強い (Definite > Conditional) mutation で上書きする。
if (transitive) {
if (node.transitive == null || node.transitive.kind < kind) {
node.transitive = {kind, loc};
}
} else {
if (node.local == null || node.local.kind < kind) {
node.local = {kind, loc};
}
}
最後に、まだ local/transitive が無い(=純粋と推定)のに壊されたら、appendFunctionErrors
でその関数本体をエラーとしてマークする。
if (
node.value.kind === 'Function' &&
node.transitive == null &&
node.local == null
) {
appendFunctionErrors(errors, node.value.function);
}
/**
* all mutations affect "forward" edges by the rules:
* - Capture a -> b, mutate(a) => mutate(b)
* - Alias a -> b, mutate(a) => mutate(b)
*/
for (const edge of node.edges) {
if (edge.index >= index) {
break;
}
queue.push({place: edge.node, transitive, direction: 'forwards'});
}
for (const [alias, when] of node.createdFrom) {
if (when >= index) {
continue;
}
queue.push({place: alias, transitive: true, direction: 'backwards'});
}
if (direction === 'backwards' || node.value.kind !== 'Phi') {
/**
* all mutations affect backward alias edges by the rules:
* - Alias a -> b, mutate(b) => mutate(a)
* - Alias a -> b, mutateTransitive(b) => mutate(a)
*
* However, if we reached a phi because one of its inputs was mutated
* (and we're advancing "forwards" through that node's edges), then
* we know we've already processed the mutation at its source. The
* phi's other inputs can't be affected.
*/
for (const [alias, when] of node.aliases) {
if (when >= index) {
continue;
}
queue.push({place: alias, transitive, direction: 'backwards'});
}
}
/**
* but only transitive mutations affect captures
*/
if (transitive) {
for (const [capture, when] of node.captures) {
if (when >= index) {
continue;
}
queue.push({place: capture, transitive, direction: 'backwards'});
}
}
時間順序の尊重
各エッジには生成されたインデックスが付いており、mutation より後に出来たエッジ (when ≥ index) は無視する
forward
a -> b の向きは
Capture
とAlias
の両方が対象
backward
createdFrom
、Alias
、Capture
を逆流Φノードから来た
forward
探索では、もう一方の入力は触らないようdirection=='forwards'
かつvalue.kind==='Phi'
の時に別入力をスキップ
capture Edge
は transitive 限定Mutate
は閉じたスコープ外へ波及しないが、MutateTransitive
は捕まえられた値にも影響、という React Compiler の不変条件をそのままコード化している。
AliasingState.mutate
はエッジに時刻スタンプを付けた alias, capture 有向グラフ上で「この瞬間に x を壊したら、どの値が壊れたことになるか?」を正確にマーキングする。
この情報を
mutableRange
後段の再計算除外 / メモ化
local/transitive
外から見える副作用を判定
lastMutated - シミュレーションでの到達をチェック に利用し、React Compiler の安全な副作用解析を支えている。
InferMutationAliasingRanges
の 2 番目のフェーズでは、HIR の Place ごとの effect フィールドを確定し、mutableRange
を補正する。5
その具体の流れは 5 段構えになっている。
Φノードの後処理
命令ごとの effect と
mutableRange
を補正オペランドのもつ effect を確定
hoist された関数の
mutableRange
を補正terminal
の effect を確定
それぞれのフェーズをコードで追ってみる。
for (const block of fn.body.blocks.values()) {
for (const phi of block.phis) {
// TODO: we don't actually set these effects today!
phi.place.effect = Effect.Store;
const isPhiMutatedAfterCreation: boolean =
phi.place.identifier.mutableRange.end >
(block.instructions.at(0)?.id ?? block.terminal.id);
for (const operand of phi.operands.values()) {
operand.effect = isPhiMutatedAfterCreation
? Effect.Capture
: Effect.Read;
}
if (
isPhiMutatedAfterCreation &&
phi.place.identifier.mutableRange.start === 0
) {
/*
* TODO: ideally we'd construct a precise start range, but what really
* matters is that the phi's range appears mutable (end > start + 1)
* so we just set the start to the previous instruction before this block
*/
const firstInstructionIdOfBlock =
block.instructions.at(0)?.id ?? block.terminal.id;
phi.place.identifier.mutableRange.start = makeInstructionId(
firstInstructionIdOfBlock - 1,
);
}
}
まず Φノード自体の副作用には Store
が付与される。
これは Φノードが「どの値を受け取るか」を決定するためのものであり、実際に値を変更するわけではないからである。
しかし、Φノードが生成された後に mutation が起きる場合、Φノードの入力側の副作用は Capture
に格上げされる。
つまり、Φノードが a,b のどちらを返してもそれは書き換わったものとして扱われる。
最後にΦノードのうち、mutableRange.start
が 0 のものにはブロック直前の ID をセットし、 mutableRange
を start < end で正規化する。
for (const lvalue of eachInstructionLValue(instr)) {
lvalue.effect = Effect.ConditionallyMutate;
if (lvalue.identifier.mutableRange.start === 0) {
lvalue.identifier.mutableRange.start = instr.id;
}
if (lvalue.identifier.mutableRange.end === 0) {
lvalue.identifier.mutableRange.end = makeInstructionId(
Math.max(instr.id + 1, lvalue.identifier.mutableRange.end),
);
}
}
for (const operand of eachInstructionValueOperand(instr.value)) {
operand.effect = Effect.Read;
}
if (instr.effects == null) {
continue;
}
次に、命令の effect と mutableRange
を補正する。
まず暫定的に命令の左辺を ConditionallyMutate
、右辺を Read
とする。
const operandEffects = new Map<IdentifierId, Effect>();
for (const effect of instr.effects) {
switch (effect.kind) {
case 'Assign':
case 'Alias':
case 'Capture':
case 'CreateFrom': {
const isMutatedOrReassigned =
effect.into.identifier.mutableRange.end > instr.id;
if (isMutatedOrReassigned) {
operandEffects.set(effect.from.identifier.id, Effect.Capture);
operandEffects.set(effect.into.identifier.id, Effect.Store);
} else {
operandEffects.set(effect.from.identifier.id, Effect.Read);
operandEffects.set(effect.into.identifier.id, Effect.Store);
}
break;
}
case 'CreateFunction':
case 'Create': {
break;
}
case 'Mutate': {
operandEffects.set(effect.value.identifier.id, Effect.Store);
break;
}
case 'Apply': {
CompilerError.invariant(false, {
reason: `[AnalyzeFunctions] Expected Apply effects to be replaced with more precise effects`,
loc: effect.function.loc,
});
}
case 'MutateTransitive':
case 'MutateConditionally':
case 'MutateTransitiveConditionally': {
operandEffects.set(
effect.value.identifier.id,
Effect.ConditionallyMutate,
);
break;
}
case 'Freeze': {
operandEffects.set(effect.value.identifier.id, Effect.Freeze);
break;
}
case 'ImmutableCapture': {
// no-op, Read is the default
break;
}
case 'Impure':
case 'Render':
case 'MutateFrozen':
case 'MutateGlobal': {
// no-op
break;
}
default: {
assertExhaustive(
effect,
`Unexpected effect kind ${(effect as any).kind}`,
);
}
}
}
その後命令本体のもつ effect を参照して、先程置いた暫定的な effect を上書きする。
例えば命令が Assign
であれば、その参照元が再度 mutate されるのであればその effect は Capture
になる。
再度 mutate されないのであれば、その命令は純粋な読み取りのみであるので Read
になる。
/**
* This case is targeted at hoisted functions like:
*
* ```
* x();
* function x() { ... }
* ```
*
* Which turns into:
*
* t0 = DeclareContext HoistedFunction x
* t1 = LoadContext x
* t2 = CallExpression t1 ( )
* t3 = FunctionExpression ...
* t4 = StoreContext Function x = t3
*
* If the function had captured mutable values, it would already have its
* range extended to include the StoreContext. But if the function doesn't
* capture any mutable values its range won't have been extended yet. We
* want to ensure that the value is memoized along with the context variable,
* not independently of it (bc of the way we do codegen for hoisted functions).
* So here we check for StoreContext rvalues and if they haven't already had
* their range extended to at least this instruction, we extend it.
*/
if (
instr.value.kind === 'StoreContext' &&
instr.value.value.identifier.mutableRange.end <= instr.id
) {
instr.value.value.identifier.mutableRange.end = makeInstructionId(
instr.id + 1,
);
}
関数宣言の hoist では、関数自体の mutableRange.end
が StoreContext
を持つ Place HIR よりも前にある場合がある。
その場合、関数の mutableRange.end
を StoreContext
の直後に補正する。
これにより、関数と hoist した関数値の両方が同一メモ化単位として扱われる。
if (block.terminal.kind === 'return') {
block.terminal.value.effect = isFunctionExpression
? Effect.Read
: Effect.Freeze;
} else {
for (const operand of eachTerminalOperand(block.terminal)) {
operand.effect = Effect.Read;
}
}
最後に terminal
の effect を確定する。
関数の return
は外部へ出るという意味で、書き換え不可能 であることから Freeze
として扱われる。
ここで、関数が関数式の場合は、その式の結果はあくまで呼び出した親に依存するため Read
として扱われる。
それ以外の terminal
は Read
として扱われる。
これらの処理により、各 Place HIR がいつ作られ、いつ最後に書かれ、どのように読まれるかをその HIR が持つ情報のみで決定できるようになる。
InferMutationAliasingRanges
の最後のフェーズでは、外部に漏れる副作用を決定する。[^6]
[66]: facebook/react/compiler/packages/babel-plugin-react-compiler/src/Inference/InferMutationAliasingRanges.ts#L468-L543
このフェーズでは functionEffects
配列に対して、
副作用そのもの
外から観測できるデータフロー
戻り値の
Create
を追加し、呼び出し側から見える副作用を決定する。
いくつかの処理を追ってみる。
const returns = fn.returns.identifier;
functionEffects.push({
kind: 'Create',
into: fn.returns,
value: isPrimitiveType(returns)
? ValueKind.Primitive
: isJsxType(returns.type)
? ValueKind.Frozen
: ValueKind.Mutable,
reason: ValueReason.KnownReturnSignature,
});
戻り値それ自体が新しい値を生成する副作用として必ず記録される。
ValueKind
が primitive と JSX で分岐されているのは、後続パスで freeze 可能かどうかを決定するためである。
JSX だと freeze するのは React のコンポーネントは純粋であるという前提が感じ取れて面白い。
/**
* Determine precise data-flow effects by simulating transitive mutations of the params/
* captures and seeing what other params/context variables are affected. Anything that
* would be transitively mutated needs a capture relationship.
*/
const tracked: Array<Place> = [];
const ignoredErrors = new CompilerError();
for (const param of [...fn.params, ...fn.context, fn.returns]) {
const place = param.kind === 'Identifier' ? param : param.place;
tracked.push(place);
}
次に、 tracked
という配列に関数外と共有し得る値を集約する。
for (const into of tracked) {
const mutationIndex = index++;
state.mutate(
mutationIndex,
into.identifier,
null,
true,
MutationKind.Conditional,
into.loc,
ignoredErrors,
);
その後集約した tracked
を AliasingState
でシミュレートし、どのノードの lastMutated
が更新されるかを確認する。
for (const from of tracked) {
if (
from.identifier.id === into.identifier.id ||
from.identifier.id === fn.returns.identifier.id
) {
continue;
}
const fromNode = state.nodes.get(from.identifier);
CompilerError.invariant(fromNode != null, {
reason: `Expected a node to exist for all parameters and context variables`,
loc: into.loc,
});
if (fromNode.lastMutated === mutationIndex) {
if (into.identifier.id === fn.returns.identifier.id) {
// The return value could be any of the params/context variables
functionEffects.push({
kind: 'Alias',
from,
into,
});
} else {
// Otherwise params/context-vars can only capture each other
functionEffects.push({
kind: 'Capture',
from,
into,
});
}
}
}
そして、副作用の波及を functionEffects
に追加する。
具体的には、
波及先が戻り値でかつ、他の params や context が変更されていれば
Alias
とする関数の
return
と params は同じリファレンスを共有するためである。
波及先が params や context であれば
Capture
とする関数のある param を変えると別の param も壊れるためである。
if (errors.hasErrors() && !isFunctionExpression) {
return Err(errors);
}
return Ok(functionEffects);
これらの処理により、副作用の安全な分離や DCE を呼び出し側に影響を漏らさず行えるようになる。
たらたらと InferMutationAliasingRanges
の実装を追ってきたが、どのように動くのかを見てみよう。
export const setActive = (user) => {
user.active = true;
};
この関数は、引数 user
の active
プロパティを true
に設定するだけの単純な関数である。
InferMutationAliasingRanges
はこの関数を解析し、以下のような functionEffects
を生成する。
[
// ① 戻り値は常に Create(値は undefined でも “生成” とみなす)
{ kind: 'Create', into: returnValue, value: ValueKind.Primitive },
// ② param `user` を書き換えているので外部からは Mutate
{ kind: 'MutateTransitive', value: user },
]
export const identity = (x) => {
return x;
};
この関数は引数 x
をそのまま返すだけの関数である。
InferMutationAliasingRanges
はこの関数を解析し、以下のような functionEffects
を生成する。
[
{ kind: 'Create', into: returnValue, value: ValueKind.Mutable },
// 戻り値と param x が同一参照なので Alias
{ kind: 'Alias', from: x, into: returnValue },
]
このとき、 InferMutationAliasingRange
は identity
関数の副作用をシミュレーションし、引数 x
を壊すと戻り値も壊れることを確認しているため Alias
として扱われる。
export const link = (a, b) => {
a.ref = b;
};
この関数は引数 a
の ref
プロパティに b
を設定する。
InferMutationAliasingRanges
はこの関数を解析し、以下のような functionEffects
を生成する。
[
{ kind: 'Create', into: returnValue, value: ValueKind.Primitive },
// a は書き換えたので MutateTransitive
{ kind: 'MutateTransitive', value: a },
/* ====== Part 3 のシミュレーション結果 ====== */
// b を仮にミュートすると a も汚染される → Capture
{ kind: 'Capture', from: b, into: a },
]
このとき、InferMutationAliasingRanges
は a.ref = b
の命令をシミュレーションし、b
を壊すと a
も壊れることを確認しているため Capture
として扱われる。
InferMutationAliasingRanges
はプログラムを時間軸でのエイリアシングと mutation のシミュレーションの結果から、静的に副作用を決定する。
その結果、 React Compiler は「副作用のない再利用可能コード」と「依存関係を持つコード」を安全に分離し、後続での DCE やメモ化に役立てている。