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