diff options
Diffstat (limited to 'chapter-interprocedural-sccp')
7 files changed, 107 insertions, 24 deletions
diff --git a/chapter-interprocedural-sccp/README.ja.md b/chapter-interprocedural-sccp/README.ja.md index 21a5a381..4dec73c7 100644 --- a/chapter-interprocedural-sccp/README.ja.md +++ b/chapter-interprocedural-sccp/README.ja.md @@ -3,6 +3,7 @@ [English](README.md) | 日本語 [前: 関数内の SCCP](../chapter-sccp/README.ja.md) | +[次: 型が確定する前の SSA 構築](../chapter-incomplete-types/README.ja.md) | [章の分割案](../docs/chapter-split.md) 前の章では関数ごとに保守的な呼び出し境界で解析しました。この章では diff --git a/chapter-interprocedural-sccp/README.md b/chapter-interprocedural-sccp/README.md index d3b740a9..7310de80 100644 --- a/chapter-interprocedural-sccp/README.md +++ b/chapter-interprocedural-sccp/README.md @@ -3,12 +3,11 @@ English | [日本語](README.ja.md) [Previous: SCCP Within a Function](../chapter-sccp/README.md) | -[Split outline](../docs/chapter-split.md) +[Next: SSA Before Types Are Known](../chapter-incomplete-types/README.md) | -The previous chapter solves each function with conservative call interfaces. -This chapter lets the same worklist discover call edges and propagate values -between functions. It is an independent snapshot of the interprocedural -compiler previously taught in Chapter 24. +The previous chapter runs SCCP with each function, and assumes very +conservative typing across calls. This chapter lets the same worklist +discover call edges and propagate values between functions. ## Discovering calls while solving types @@ -20,9 +19,10 @@ Such edges make up a [Call Graph](https://en.wikipedia.org/wiki/Call_graph). We extend the normal SCCP algorithm to observe when a `Call`s function pointer input changes - when it picks up new function targets. There are only a finite -number so we represent them exactly with *function indices* as described in an -earlier chapter. (Separate compilation adds a special index for the infinite -unknown functions that are called outside this compilation unit). +number so we represent them exactly with *function indices*, or *fidx* +internally, as described earlier chapters. (Separate compilation adds a +special index for the infinite unknown functions that are called outside this +compilation unit). Once we observe a new *fidx* at a `Call`, we *link* the `Call` with the `Fun`, and the `Return` with the `CallEnd`. Such linkage acts exactly as-if we added @@ -42,24 +42,37 @@ e.g. not-null) on all calling paths. ## Recursion is a loop in disguise -An argument can flow from a Parm through arithmetic into a recursive call, -then back to the same Parm. A result has a separate cycle: Return -> CallEnd --> arithmetic -> Phi -> Return. Widening at Parm alone cannot stop a return -range from growing in `f(x-1)+1`. +We use the notion of *widening* integer ranges at loop heads, see Chapter XXX. +This allows us to have a sharper notion of integers over `BOTTOM` without also +allowing the lattice to fall 2^32 times. The same issue arises during +recursive calls: an argument can flow from a Parm through arithmetic into a +recursive call, then back to the same Parm. -Loop Phis, Parms, and CallEnds therefore need widening points. Their comments -cross-reference each other. Constants and above-center ranges remain narrow; -the growing below-center ranges widen within their type bounds. +```simple +val fact = { int x -> x ? 0 : f(x-1)+1; }; +``` + +Here if we pass in `f(999)` , parameter `x` will have the integer range +`[999]`. We'll then track the recursive call to `f(998)` via normal SCCP +and realize the parameter `x` has a range `[999-998]`. Lather, rinse, repeat +and we're at `[999-997]`. We need to *widen* integer parameters at `Parms` +not just loop-head `Phis`. + +The same issue arises during the recursive return: the first return will be +with `0` when `x` is zero, then we return `0+1` or the range `[0-1]` then range +`[0-2]`, etc. `CallEnds` also need to widen. + +Loop Phis, Parms, and CallEnds get widening points, and since this same issue +hits in 3 unrelated places, their comments all cross-reference each other. -`SccpTest` uses the same two calls as the previous chapter and checks that the -parameter now receives [1,2]. `Chapter24Test.testRecursiveWidening` exercises -argument and return cycles at several worklist seeds and evaluates the results. ## Unknown callers -A function address that survives outside a direct call may be called by code -we cannot see. Preserve its unknown-caller input. Precise escape analysis is -introduced later; this chapter does not infer exposure through memory. +A `FunPtrNode` (function address) that survives outside a direct call may be +called by code we cannot see. We have to assume the address escapes into +unknown code, which later calls it. We preserve its unknown-caller input, +since we cannot tell what that unknown caller will pass. Precise escape +analysis is introduced later exactly to inmprove this. ## Building and checking diff --git a/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index ad48dd5d..af670bda 100644 --- a/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -189,6 +189,12 @@ public class CodeGen { // the return is not part of the match). final Ary<FunNode> _linker = new Ary<>(FunNode.class); + // Native symbols belong to function identities, not to one ExternNode. + // Selection and spill copies can turn that node into an ordinary constant. + private final HashMap<TypeFunPtr,String> _externs = new HashMap<>(); + public void externFunc(TypeFunPtr tfp, String name) { _externs.put(tfp.makeFrom(Type.BOTTOM),name); } + public String externFunc(TypeFunPtr tfp) { return _externs.get(tfp.makeFrom(Type.BOTTOM)); } + // Parser object public final Parser P; diff --git a/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/codegen/Encoding.java index b5a8e148..019e3892 100644 --- a/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/codegen/Encoding.java +++ b/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/codegen/Encoding.java @@ -138,6 +138,10 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { } public Encoding relo( ConstantNode con ) { TypeFunPtr tfp = (TypeFunPtr)con._con; + // A native address has no local FunNode. Keep its symbol even after + // selection or a spill copy has replaced the original ExternNode. + String name = _code.externFunc(tfp); + if( name!=null ) return external(con,name); _internals.put(con,_code.link(tfp)); return this; } diff --git a/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/node/ExternNode.java b/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/node/ExternNode.java index ccbcfc66..7a26e2e9 100644 --- a/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/node/ExternNode.java +++ b/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/node/ExternNode.java @@ -13,7 +13,11 @@ import java.util.BitSet; public class ExternNode extends ConstantNode { public final String _extern; - public ExternNode(Type t, String ex) { super(t); _extern = ex; } + public ExternNode(Type t, String ex) { + super(t); + _extern = ex; + if( t instanceof TypeFunPtr tfp ) CodeGen.CODE.externFunc(tfp,ex); + } @Override public String label() { return "#"+_con+":"+_extern; } diff --git a/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/node/cpus/arm/TFPARM.java b/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/node/cpus/arm/TFPARM.java index 98a56089..2c41dc57 100644 --- a/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/node/cpus/arm/TFPARM.java +++ b/chapter-interprocedural-sccp/src/main/java/com/seaofnodes/simple/node/cpus/arm/TFPARM.java @@ -39,8 +39,9 @@ public class TFPARM extends ConstantNode implements MachNode, RIPRelSize { int base = opStart & ~0xFFF; delta = target-base; int adrp_delta = delta >> 12; - // patch upper 20 bits via adrp - enc.patch4(opStart, Arm64.adrp(1, adrp_delta & 0b11, 0b10000, adrp_delta >> 2, rpc)); + // ADRP splits a signed page offset into two unsigned bit fields. + // Mask the high field too, including for an address below this PC. + enc.patch4(opStart, Arm64.adrp(1, adrp_delta & 0b11, 0b10000, (adrp_delta >> 2) & 0x7FFFF, rpc)); // low 12 bits via add enc.patch4(opStart+4, Arm64.imm_inst_l(Arm64.OPI_ADD, delta & 0xfff, rpc)); } else { diff --git a/chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/NativeAddressTest.java b/chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/NativeAddressTest.java new file mode 100644 index 00000000..6d21ca5f --- /dev/null +++ b/chapter-interprocedural-sccp/src/test/java/com/seaofnodes/simple/NativeAddressTest.java @@ -0,0 +1,54 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.Encoding; +import com.seaofnodes.isa.eval.EvalArm64; +import com.seaofnodes.isa.eval.EvalRisc5; +import java.io.IOException; +import java.nio.file.Files; +import java.nio.file.Path; +import org.junit.Test; +import static org.junit.Assert.*; + +public class NativeAddressTest { + @Test public void testReturnedNativeAddress() throws IOException { + Path dir = Path.of("build/objs"); + Files.createDirectories(dir); + Files.writeString(dir.resolve("nativeAddress.smp"), """ + val getAbs = { -> + { i32 -> i32 } abs = "C"; + return abs; + }; + """); + Files.writeString(dir.resolve("nativeAddress.c"), """ + typedef int (*func)(int); + extern func getAbs(void); + int main(void) { + func f = getAbs(); + return f(-7) != 7 || f(9) != 9; + } + """); + TestC.run("build/objs", "nativeAddress", "", -1); + } + + @Test public void testEmulatedNativeAddress() throws IOException { + // No native call: return the address itself, patched to the emulator's + // known write entry. Both ports share Encoding's symbol lookup. + String src = "{ int -> int } write = \"C\"; return write;"; + for( String cpu : new String[]{"arm","riscv"} ) { + CodeGen code = new CodeGen(src).driver(cpu,"SystemV",null); + byte[] bits = code._encoding.bits(); + byte[] image = new byte[1<<20]; + System.arraycopy(bits,0,image,0,bits.length); + if( cpu.equals("arm") ) { + EvalArm64 eval = new EvalArm64(image,1<<16); + assertEquals(0,eval.step(100)); + assertEquals(Encoding.SENTINEL_WRITE,eval.regs[0]); + } else { + EvalRisc5 eval = new EvalRisc5(image,1<<16); + assertEquals(0,eval.step(100)); + assertEquals(Encoding.SENTINEL_WRITE,eval.regs[10]); + } + } + } +} |