lca_test.go

     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  func testLCAgen(t *testing.T, bg blockGen, size int) {
    10  	c := testConfig(t)
    11  	fun := c.Fun("entry", bg(size)...)
    12  	CheckFunc(fun.f)
    13  	if size == 4 {
    14  		t.Log(fun.f.String())
    15  	}
    16  	lca1 := makeLCArange(fun.f)
    17  	lca2 := makeLCAeasy(fun.f)
    18  	for _, b := range fun.f.Blocks {
    19  		for _, c := range fun.f.Blocks {
    20  			l1 := lca1.find(b, c)
    21  			l2 := lca2.find(b, c)
    22  			if l1 != l2 {
    23  				t.Errorf("lca(%s,%s)=%s, want %s", b, c, l1, l2)
    24  			}
    25  		}
    26  	}
    27  }
    28  
    29  func TestLCALinear(t *testing.T) {
    30  	testLCAgen(t, genLinear, 10)
    31  	testLCAgen(t, genLinear, 100)
    32  }
    33  
    34  func TestLCAFwdBack(t *testing.T) {
    35  	testLCAgen(t, genFwdBack, 10)
    36  	testLCAgen(t, genFwdBack, 100)
    37  }
    38  
    39  func TestLCAManyPred(t *testing.T) {
    40  	testLCAgen(t, genManyPred, 10)
    41  	testLCAgen(t, genManyPred, 100)
    42  }
    43  
    44  func TestLCAMaxPred(t *testing.T) {
    45  	testLCAgen(t, genMaxPred, 10)
    46  	testLCAgen(t, genMaxPred, 100)
    47  }
    48  
    49  func TestLCAMaxPredValue(t *testing.T) {
    50  	testLCAgen(t, genMaxPredValue, 10)
    51  	testLCAgen(t, genMaxPredValue, 100)
    52  }
    53  
    54  // Simple implementation of LCA to compare against.
    55  type lcaEasy struct {
    56  	parent []*Block
    57  }
    58  
    59  func makeLCAeasy(f *Func) *lcaEasy {
    60  	return &lcaEasy{parent: dominators(f)}
    61  }
    62  
    63  func (lca *lcaEasy) find(a, b *Block) *Block {
    64  	da := lca.depth(a)
    65  	db := lca.depth(b)
    66  	for da > db {
    67  		da--
    68  		a = lca.parent[a.ID]
    69  	}
    70  	for da < db {
    71  		db--
    72  		b = lca.parent[b.ID]
    73  	}
    74  	for a != b {
    75  		a = lca.parent[a.ID]
    76  		b = lca.parent[b.ID]
    77  	}
    78  	return a
    79  }
    80  
    81  func (lca *lcaEasy) depth(b *Block) int {
    82  	n := 0
    83  	for b != nil {
    84  		b = lca.parent[b.ID]
    85  		n++
    86  	}
    87  	return n
    88  }
    89
View as plain text