forked from alecthomas/gometalinter
/
loops.go
50 lines (46 loc) · 959 Bytes
/
loops.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package functions
import "honnef.co/go/tools/ssa"
type Loop map[*ssa.BasicBlock]bool
func findLoops(fn *ssa.Function) []Loop {
if fn.Blocks == nil {
return nil
}
tree := fn.DomPreorder()
var sets []Loop
for _, h := range tree {
for _, n := range h.Preds {
if !h.Dominates(n) {
continue
}
// n is a back-edge to h
// h is the loop header
if n == h {
sets = append(sets, Loop{n: true})
continue
}
set := Loop{h: true, n: true}
for _, b := range allPredsBut(n, h, nil) {
set[b] = true
}
sets = append(sets, set)
}
}
return sets
}
func allPredsBut(b, but *ssa.BasicBlock, list []*ssa.BasicBlock) []*ssa.BasicBlock {
outer:
for _, pred := range b.Preds {
if pred == but {
continue
}
for _, p := range list {
// TODO improve big-o complexity of this function
if pred == p {
continue outer
}
}
list = append(list, pred)
list = allPredsBut(pred, but, list)
}
return list
}