Home | History | Annotate | Download | only in ssa 
      1 package ssa
      2 
      3 import (
      4 	"fmt"
      5 	"strconv"
      6 	"testing"
      7 )
      8 
      9 func TestFuseEliminatesOneBranch(t *testing.T) {
     10 	ptrType := &TypeImpl{Size_: 8, Ptr: true, Name: "testptr"} // dummy for testing
     11 	c := NewConfig("amd64", DummyFrontend{t}, nil, true)
     12 	fun := Fun(c, "entry",
     13 		Bloc("entry",
     14 			Valu("mem", OpInitMem, TypeMem, 0, nil),
     15 			Valu("sb", OpSB, TypeInvalid, 0, nil),
     16 			Goto("checkPtr")),
     17 		Bloc("checkPtr",
     18 			Valu("ptr1", OpLoad, ptrType, 0, nil, "sb", "mem"),
     19 			Valu("nilptr", OpConstNil, ptrType, 0, nil),
     20 			Valu("bool1", OpNeqPtr, TypeBool, 0, nil, "ptr1", "nilptr"),
     21 			If("bool1", "then", "exit")),
     22 		Bloc("then",
     23 			Goto("exit")),
     24 		Bloc("exit",
     25 			Exit("mem")))
     26 
     27 	CheckFunc(fun.f)
     28 	fuse(fun.f)
     29 
     30 	for _, b := range fun.f.Blocks {
     31 		if b == fun.blocks["then"] && b.Kind != BlockInvalid {
     32 			t.Errorf("then was not eliminated, but should have")
     33 		}
     34 	}
     35 }
     36 
     37 func TestFuseEliminatesBothBranches(t *testing.T) {
     38 	ptrType := &TypeImpl{Size_: 8, Ptr: true, Name: "testptr"} // dummy for testing
     39 	c := NewConfig("amd64", DummyFrontend{t}, nil, true)
     40 	fun := Fun(c, "entry",
     41 		Bloc("entry",
     42 			Valu("mem", OpInitMem, TypeMem, 0, nil),
     43 			Valu("sb", OpSB, TypeInvalid, 0, nil),
     44 			Goto("checkPtr")),
     45 		Bloc("checkPtr",
     46 			Valu("ptr1", OpLoad, ptrType, 0, nil, "sb", "mem"),
     47 			Valu("nilptr", OpConstNil, ptrType, 0, nil),
     48 			Valu("bool1", OpNeqPtr, TypeBool, 0, nil, "ptr1", "nilptr"),
     49 			If("bool1", "then", "else")),
     50 		Bloc("then",
     51 			Goto("exit")),
     52 		Bloc("else",
     53 			Goto("exit")),
     54 		Bloc("exit",
     55 			Exit("mem")))
     56 
     57 	CheckFunc(fun.f)
     58 	fuse(fun.f)
     59 
     60 	for _, b := range fun.f.Blocks {
     61 		if b == fun.blocks["then"] && b.Kind != BlockInvalid {
     62 			t.Errorf("then was not eliminated, but should have")
     63 		}
     64 		if b == fun.blocks["else"] && b.Kind != BlockInvalid {
     65 			t.Errorf("then was not eliminated, but should have")
     66 		}
     67 	}
     68 }
     69 
     70 func TestFuseHandlesPhis(t *testing.T) {
     71 	ptrType := &TypeImpl{Size_: 8, Ptr: true, Name: "testptr"} // dummy for testing
     72 	c := NewConfig("amd64", DummyFrontend{t}, nil, true)
     73 	fun := Fun(c, "entry",
     74 		Bloc("entry",
     75 			Valu("mem", OpInitMem, TypeMem, 0, nil),
     76 			Valu("sb", OpSB, TypeInvalid, 0, nil),
     77 			Goto("checkPtr")),
     78 		Bloc("checkPtr",
     79 			Valu("ptr1", OpLoad, ptrType, 0, nil, "sb", "mem"),
     80 			Valu("nilptr", OpConstNil, ptrType, 0, nil),
     81 			Valu("bool1", OpNeqPtr, TypeBool, 0, nil, "ptr1", "nilptr"),
     82 			If("bool1", "then", "else")),
     83 		Bloc("then",
     84 			Goto("exit")),
     85 		Bloc("else",
     86 			Goto("exit")),
     87 		Bloc("exit",
     88 			Valu("phi", OpPhi, ptrType, 0, nil, "ptr1", "ptr1"),
     89 			Exit("mem")))
     90 
     91 	CheckFunc(fun.f)
     92 	fuse(fun.f)
     93 
     94 	for _, b := range fun.f.Blocks {
     95 		if b == fun.blocks["then"] && b.Kind != BlockInvalid {
     96 			t.Errorf("then was not eliminated, but should have")
     97 		}
     98 		if b == fun.blocks["else"] && b.Kind != BlockInvalid {
     99 			t.Errorf("then was not eliminated, but should have")
    100 		}
    101 	}
    102 }
    103 
    104 func TestFuseEliminatesEmptyBlocks(t *testing.T) {
    105 	c := NewConfig("amd64", DummyFrontend{t}, nil, true)
    106 	fun := Fun(c, "entry",
    107 		Bloc("entry",
    108 			Valu("mem", OpInitMem, TypeMem, 0, nil),
    109 			Valu("sb", OpSB, TypeInvalid, 0, nil),
    110 			Goto("z0")),
    111 		Bloc("z1",
    112 			Goto("z2")),
    113 		Bloc("z3",
    114 			Goto("exit")),
    115 		Bloc("z2",
    116 			Goto("z3")),
    117 		Bloc("z0",
    118 			Goto("z1")),
    119 		Bloc("exit",
    120 			Exit("mem"),
    121 		))
    122 
    123 	CheckFunc(fun.f)
    124 	fuse(fun.f)
    125 
    126 	for k, b := range fun.blocks {
    127 		if k[:1] == "z" && b.Kind != BlockInvalid {
    128 			t.Errorf("%s was not eliminated, but should have", k)
    129 		}
    130 	}
    131 }
    132 
    133 func BenchmarkFuse(b *testing.B) {
    134 	for _, n := range [...]int{1, 10, 100, 1000, 10000} {
    135 		b.Run(strconv.Itoa(n), func(b *testing.B) {
    136 			c := testConfig(b)
    137 
    138 			blocks := make([]bloc, 0, 2*n+3)
    139 			blocks = append(blocks,
    140 				Bloc("entry",
    141 					Valu("mem", OpInitMem, TypeMem, 0, nil),
    142 					Valu("cond", OpArg, TypeBool, 0, nil),
    143 					Valu("x", OpArg, TypeInt64, 0, nil),
    144 					Goto("exit")))
    145 
    146 			phiArgs := make([]string, 0, 2*n)
    147 			for i := 0; i < n; i++ {
    148 				cname := fmt.Sprintf("c%d", i)
    149 				blocks = append(blocks,
    150 					Bloc(fmt.Sprintf("b%d", i), If("cond", cname, "merge")),
    151 					Bloc(cname, Goto("merge")))
    152 				phiArgs = append(phiArgs, "x", "x")
    153 			}
    154 			blocks = append(blocks,
    155 				Bloc("merge",
    156 					Valu("phi", OpPhi, TypeMem, 0, nil, phiArgs...),
    157 					Goto("exit")),
    158 				Bloc("exit",
    159 					Exit("mem")))
    160 
    161 			b.ResetTimer()
    162 			for i := 0; i < b.N; i++ {
    163 				fun := Fun(c, "entry", blocks...)
    164 				fuse(fun.f)
    165 				fun.f.Free()
    166 			}
    167 		})
    168 	}
    169 }
    170