Home | History | Annotate | Download | only in ssa 
      1 // Copyright 2016 The Go Authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style
      3 // license that can be found in the LICENSE file.
      4 
      5 package ssa
      6 
      7 import "testing"
      8 
      9 type lca interface {
     10 	find(a, b *Block) *Block
     11 }
     12 
     13 func lcaEqual(f *Func, lca1, lca2 lca) bool {
     14 	for _, b := range f.Blocks {
     15 		for _, c := range f.Blocks {
     16 			if lca1.find(b, c) != lca2.find(b, c) {
     17 				return false
     18 			}
     19 		}
     20 	}
     21 	return true
     22 }
     23 
     24 func testLCAgen(t *testing.T, bg blockGen, size int) {
     25 	c := NewConfig("amd64", DummyFrontend{t}, nil, true)
     26 	fun := Fun(c, "entry", bg(size)...)
     27 	CheckFunc(fun.f)
     28 	if size == 4 {
     29 		t.Logf(fun.f.String())
     30 	}
     31 	lca1 := makeLCArange(fun.f)
     32 	lca2 := makeLCAeasy(fun.f)
     33 	for _, b := range fun.f.Blocks {
     34 		for _, c := range fun.f.Blocks {
     35 			l1 := lca1.find(b, c)
     36 			l2 := lca2.find(b, c)
     37 			if l1 != l2 {
     38 				t.Errorf("lca(%s,%s)=%s, want %s", b, c, l1, l2)
     39 			}
     40 		}
     41 	}
     42 }
     43 
     44 func TestLCALinear(t *testing.T) {
     45 	testLCAgen(t, genLinear, 10)
     46 	testLCAgen(t, genLinear, 100)
     47 }
     48 
     49 func TestLCAFwdBack(t *testing.T) {
     50 	testLCAgen(t, genFwdBack, 10)
     51 	testLCAgen(t, genFwdBack, 100)
     52 }
     53 
     54 func TestLCAManyPred(t *testing.T) {
     55 	testLCAgen(t, genManyPred, 10)
     56 	testLCAgen(t, genManyPred, 100)
     57 }
     58 
     59 func TestLCAMaxPred(t *testing.T) {
     60 	testLCAgen(t, genMaxPred, 10)
     61 	testLCAgen(t, genMaxPred, 100)
     62 }
     63 
     64 func TestLCAMaxPredValue(t *testing.T) {
     65 	testLCAgen(t, genMaxPredValue, 10)
     66 	testLCAgen(t, genMaxPredValue, 100)
     67 }
     68 
     69 // Simple implementation of LCA to compare against.
     70 type lcaEasy struct {
     71 	parent []*Block
     72 }
     73 
     74 func makeLCAeasy(f *Func) *lcaEasy {
     75 	return &lcaEasy{parent: dominators(f)}
     76 }
     77 
     78 func (lca *lcaEasy) find(a, b *Block) *Block {
     79 	da := lca.depth(a)
     80 	db := lca.depth(b)
     81 	for da > db {
     82 		da--
     83 		a = lca.parent[a.ID]
     84 	}
     85 	for da < db {
     86 		db--
     87 		b = lca.parent[b.ID]
     88 	}
     89 	for a != b {
     90 		a = lca.parent[a.ID]
     91 		b = lca.parent[b.ID]
     92 	}
     93 	return a
     94 }
     95 
     96 func (lca *lcaEasy) depth(b *Block) int {
     97 	n := 0
     98 	for b != nil {
     99 		b = lca.parent[b.ID]
    100 		n++
    101 	}
    102 	return n
    103 }
    104