compiler.cfg.alias-analysis: write unit tests and fix redundant store elimination

diff --git a/basis/compiler/cfg/alias-analysis/alias-analysis-tests.factor b/basis/compiler/cfg/alias-analysis/alias-analysis-tests.factor
new file mode 100644 (file)
index 0000000..4a41129
--- /dev/null
+++ b/basis/compiler/cfg/alias-analysis/alias-analysis-tests.factor
@@ -0,0 +1,244 @@
+USING: arrays compiler.cfg.alias-analysis compiler.cfg.instructions
+compiler.cfg.registers compiler.cfg.debugger compiler.cfg.comparisons
+cpu.architecture tools.test ;
+IN: compiler.cfg.alias-analysis.tests
+
+! Redundant load elimination
+[
+    V{
+        T{ ##peek f 0 D 0 }
+        T{ ##slot-imm f 1 0 1 0 }
+        T{ ##copy f 2 1 any-rep }
+    }
+] [
+    V{
+        T{ ##peek f 0 D 0 }
+        T{ ##slot-imm f 1 0 1 0 }
+        T{ ##slot-imm f 2 0 1 0 }
+    } alias-analysis-step
+] unit-test
+
+! Store-load forwarding
+[
+    V{
+        T{ ##peek f 0 D 0 }
+        T{ ##peek f 1 D 1 }
+        T{ ##set-slot-imm f 1 0 1 0 }
+        T{ ##copy f 2 1 any-rep }
+    }
+] [
+    V{
+        T{ ##peek f 0 D 0 }
+        T{ ##peek f 1 D 1 }
+        T{ ##set-slot-imm f 1 0 1 0 }
+        T{ ##slot-imm f 2 0 1 0 }
+    } alias-analysis-step
+] unit-test
+
+! Dead store elimination
+[
+    V{
+        T{ ##peek f 0 D 0 }
+        T{ ##peek f 1 D 1 }
+        T{ ##peek f 2 D 2 }
+        T{ ##set-slot-imm f 2 0 1 0 }
+    }
+] [
+    V{
+        T{ ##peek f 0 D 0 }
+        T{ ##peek f 1 D 1 }
+        T{ ##peek f 2 D 2 }
+        T{ ##set-slot-imm f 1 0 1 0 }
+        T{ ##set-slot-imm f 2 0 1 0 }
+    } alias-analysis-step
+] unit-test
+
+! Redundant store elimination
+[
+    V{
+        T{ ##peek f 0 D 0 }
+        T{ ##slot-imm f 1 0 1 0 }
+    }
+] [
+    V{
+        T{ ##peek f 0 D 0 }
+        T{ ##slot-imm f 1 0 1 0 }
+        T{ ##set-slot-imm f 1 0 1 0 }
+    } alias-analysis-step
+] unit-test
+
+[
+    V{
+        T{ ##peek f 0 D 0 }
+        T{ ##slot-imm f 1 0 1 0 }
+        T{ ##copy f 2 1 any-rep }
+    }
+] [
+    V{
+        T{ ##peek f 0 D 0 }
+        T{ ##slot-imm f 1 0 1 0 }
+        T{ ##copy f 2 1 any-rep }
+        T{ ##set-slot-imm f 2 0 1 0 }
+    } alias-analysis-step
+] unit-test
+
+! Not a redundant load
+[
+    V{
+        T{ ##peek f 0 D 0 }
+        T{ ##peek f 1 D 1 }
+        T{ ##slot-imm f 1 0 1 0 }
+        T{ ##set-slot-imm f 0 1 1 0 }
+        T{ ##slot-imm f 2 0 1 0 }
+    }
+] [
+    V{
+        T{ ##peek f 0 D 0 }
+        T{ ##peek f 1 D 1 }
+        T{ ##slot-imm f 1 0 1 0 }
+        T{ ##set-slot-imm f 0 1 1 0 }
+        T{ ##slot-imm f 2 0 1 0 }
+    } alias-analysis-step
+] unit-test
+
+! Not a redundant store
+[
+    V{
+        T{ ##peek f 0 D 0 }
+        T{ ##peek f 1 D 1 }
+        T{ ##peek f 2 D 2 }
+        T{ ##peek f 3 D 3 }
+        T{ ##set-slot-imm f 2 1 1 0 }
+        T{ ##slot-imm f 4 0 1 0 }
+        T{ ##set-slot-imm f 3 1 1 0 }
+    }
+] [
+    V{
+        T{ ##peek f 0 D 0 }
+        T{ ##peek f 1 D 1 }
+        T{ ##peek f 2 D 2 }
+        T{ ##peek f 3 D 3 }
+        T{ ##set-slot-imm f 2 1 1 0 }
+        T{ ##slot-imm f 4 0 1 0 }
+        T{ ##set-slot-imm f 3 1 1 0 }
+    } alias-analysis-step
+] unit-test
+
+! There's a redundant load, but not a redundant store
+[
+    V{
+        T{ ##peek f 0 D 0 }
+        T{ ##peek f 1 D 1 }
+        T{ ##peek f 2 D 2 }
+        T{ ##peek f 3 D 3 }
+        T{ ##slot-imm f 4 0 1 0 }
+        T{ ##set-slot-imm f 2 0 1 0 }
+        T{ ##slot f 5 0 3 0 0 }
+        T{ ##set-slot-imm f 3 0 1 0 }
+        T{ ##copy f 6 3 any-rep }
+    }
+] [
+    V{
+        T{ ##peek f 0 D 0 }
+        T{ ##peek f 1 D 1 }
+        T{ ##peek f 2 D 2 }
+        T{ ##peek f 3 D 3 }
+        T{ ##slot-imm f 4 0 1 0 }
+        T{ ##set-slot-imm f 2 0 1 0 }
+        T{ ##slot f 5 0 3 0 0 }
+        T{ ##set-slot-imm f 3 0 1 0 }
+        T{ ##slot-imm f 6 0 1 0 }
+    } alias-analysis-step
+] unit-test
+
+! Fresh allocations don't alias existing values
+
+! Redundant load elimination
+[
+    V{
+        T{ ##peek f 1 D 1 }
+        T{ ##peek f 2 D 2 }
+        T{ ##peek f 3 D 3 }
+        T{ ##allot f 4 16 array }
+        T{ ##set-slot-imm f 3 4 1 0 }
+        T{ ##set-slot-imm f 2 1 1 0 }
+        T{ ##copy f 5 3 any-rep }
+    }
+] [
+    V{
+        T{ ##peek f 1 D 1 }
+        T{ ##peek f 2 D 2 }
+        T{ ##peek f 3 D 3 }
+        T{ ##allot f 4 16 array }
+        T{ ##set-slot-imm f 3 4 1 0 }
+        T{ ##set-slot-imm f 2 1 1 0 }
+        T{ ##slot-imm f 5 4 1 0 }
+    } alias-analysis-step
+] unit-test
+
+! Redundant store elimination
+[
+    V{
+        T{ ##peek f 1 D 1 }
+        T{ ##peek f 2 D 2 }
+        T{ ##peek f 3 D 3 }
+        T{ ##allot f 4 16 array }
+        T{ ##slot-imm f 5 1 1 0 }
+        T{ ##set-slot-imm f 3 4 1 0 }
+    }
+] [
+    V{
+        T{ ##peek f 1 D 1 }
+        T{ ##peek f 2 D 2 }
+        T{ ##peek f 3 D 3 }
+        T{ ##allot f 4 16 array }
+        T{ ##set-slot-imm f 1 4 1 0 }
+        T{ ##slot-imm f 5 1 1 0 }
+        T{ ##set-slot-imm f 3 4 1 0 }
+    } alias-analysis-step
+] unit-test
+
+! Storing a new alias class into another object means that heap-ac
+! can now alias the new ac
+[
+    V{
+        T{ ##peek f 0 D 0 }
+        T{ ##peek f 1 D 1 }
+        T{ ##peek f 2 D 2 }
+        T{ ##peek f 3 D 3 }
+        T{ ##allot f 4 16 array }
+        T{ ##set-slot-imm f 0 4 1 0 }
+        T{ ##set-slot-imm f 4 2 1 0 }
+        T{ ##slot-imm f 5 3 1 0 }
+        T{ ##set-slot-imm f 1 5 1 0 }
+        T{ ##slot-imm f 6 4 1 0 }
+    }
+] [
+    V{
+        T{ ##peek f 0 D 0 }
+        T{ ##peek f 1 D 1 }
+        T{ ##peek f 2 D 2 }
+        T{ ##peek f 3 D 3 }
+        T{ ##allot f 4 16 array }
+        T{ ##set-slot-imm f 0 4 1 0 }
+        T{ ##set-slot-imm f 4 2 1 0 }
+        T{ ##slot-imm f 5 3 1 0 }
+        T{ ##set-slot-imm f 1 5 1 0 }
+        T{ ##slot-imm f 6 4 1 0 }
+    } alias-analysis-step
+] unit-test
+
+! Compares between objects which cannot alias are eliminated
+[
+    V{
+        T{ ##peek f 0 D 0 }
+        T{ ##allot f 1 16 array }
+        T{ ##load-reference f 2 f }
+    }
+] [
+    V{
+        T{ ##peek f 0 D 0 }
+        T{ ##allot f 1 16 array }
+        T{ ##compare f 2 0 1 cc= }
+    } alias-analysis-step
+] unit-test

diff --git a/basis/compiler/cfg/alias-analysis/alias-analysis.factor b/basis/compiler/cfg/alias-analysis/alias-analysis.factor
index ba2caa1e7138816d817bd2f1f8558cac3450d1d1..ee60e112b766d36b3fba643b6f189d2151fa35a8 100644 (file)
--- a/basis/compiler/cfg/alias-analysis/alias-analysis.factor
+++ b/basis/compiler/cfg/alias-analysis/alias-analysis.factor
@@ -7,7 +7,6 @@ compiler.cfg
 compiler.cfg.rpo
 compiler.cfg.def-use
 compiler.cfg.liveness
-compiler.cfg.copy-prop
 compiler.cfg.registers
 compiler.cfg.utilities
 compiler.cfg.comparisons
@@ -69,6 +68,14 @@ IN: compiler.cfg.alias-analysis
 ! e = c
 ! x[1] = c
 
+! Local copy propagation
+SYMBOL: copies
+
+: resolve ( vreg -- vreg ) copies get ?at drop ;
+
+: record-copy ( ##copy -- )
+    [ src>> resolve ] [ dst>> ] bi copies get set-at ; inline
+
 ! Map vregs -> alias classes
 SYMBOL: vregs>acs
 
@@ -86,15 +93,10 @@ SYMBOL: acs>vregs
 
 : ac>vregs ( ac -- vregs ) acs>vregs get at ;
 
-GENERIC: aliases ( vreg -- vregs )
-
-M: integer aliases
+: aliases ( vreg -- vregs )
     #! All vregs which may contain the same value as vreg.
     vreg>ac ac>vregs ;
 
-M: word aliases
-    1array ;
-
 : each-alias ( vreg quot -- )
     [ aliases ] dip each ; inline
 
@@ -259,7 +261,9 @@ M: ##read analyze-aliases*
 M: ##write analyze-aliases*
     dup
     [ src>> resolve ] [ insn-slot# ] [ insn-object ] tri
-    [ remember-set-slot drop ] [ load-slot ] 3bi ;
+    3dup idempotent? [ 3drop ] [
+        [ remember-set-slot drop ] [ load-slot ] 3bi
+    ] if ;
 
 M: ##copy analyze-aliases*
     #! The output vreg gets the same alias class as the input