1// Copyright 2020 The SwiftShader Authors. All Rights Reserved. 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15package cov 16 17import ( 18 "log" 19 "sort" 20 "sync" 21) 22 23// Optimize optimizes the Tree by de-duplicating common spans into a tree of 24// SpanGroups. 25func (t *Tree) Optimize() { 26 log.Printf("Optimizing coverage tree...") 27 28 // Start by gathering all of the unique spansets 29 wg := sync.WaitGroup{} 30 wg.Add(len(t.files)) 31 for _, file := range t.files { 32 file := file 33 go func() { 34 defer wg.Done() 35 o := optimizer{} 36 for idx, tc := range file.tcm { 37 o.invertForCommon(tc, &t.testRoot.children[idx]) 38 } 39 o.createGroups(file) 40 }() 41 } 42 wg.Wait() 43} 44 45type optimizer struct{} 46 47// createGroups looks for common SpanSets, and creates indexable span groups 48// which are then used instead. 49func (o *optimizer) createGroups(f *treeFile) { 50 const minSpansInGroup = 2 51 52 type spansetKey string 53 spansetMap := map[spansetKey]SpanSet{} 54 55 f.tcm.traverse(func(tc *TestCoverage) { 56 if len(tc.Spans) >= minSpansInGroup { 57 key := spansetKey(tc.Spans.String()) 58 if _, ok := spansetMap[key]; !ok { 59 spansetMap[key] = tc.Spans 60 } 61 } 62 }) 63 64 if len(spansetMap) == 0 { 65 return 66 } 67 68 type spansetInfo struct { 69 key spansetKey 70 set SpanSet // fully expanded set 71 grp SpanGroup 72 id SpanGroupID 73 } 74 spansets := make([]*spansetInfo, 0, len(spansetMap)) 75 for key, set := range spansetMap { 76 spansets = append(spansets, &spansetInfo{ 77 key: key, 78 set: set, 79 grp: SpanGroup{Spans: set}, 80 }) 81 } 82 83 // Sort by number of spans in each sets starting with the largest. 84 sort.Slice(spansets, func(i, j int) bool { 85 a, b := spansets[i].set, spansets[j].set 86 switch { 87 case len(a) > len(b): 88 return true 89 case len(a) < len(b): 90 return false 91 } 92 return a.List().Compare(b.List()) == -1 // Just to keep output stable 93 }) 94 95 // Assign IDs now that we have stable order. 96 for i := range spansets { 97 spansets[i].id = SpanGroupID(i) 98 } 99 100 // Loop over the spanGroups starting from the largest, and try to fold them 101 // into the larger sets. 102 // This is O(n^2) complexity. 103nextSpan: 104 for i, a := range spansets[:len(spansets)-1] { 105 for _, b := range spansets[i+1:] { 106 if len(a.set) > len(b.set) && a.set.containsAll(b.set) { 107 extend := b.id // Do not take address of iterator! 108 a.grp.Spans = a.set.removeAll(b.set) 109 a.grp.Extend = &extend 110 continue nextSpan 111 } 112 } 113 } 114 115 // Rebuild a map of spansetKey to SpanGroup 116 spangroupMap := make(map[spansetKey]*spansetInfo, len(spansets)) 117 for _, s := range spansets { 118 spangroupMap[s.key] = s 119 } 120 121 // Store the groups in the tree 122 f.spangroups = make(map[SpanGroupID]SpanGroup, len(spansets)) 123 for _, s := range spansets { 124 f.spangroups[s.id] = s.grp 125 } 126 127 // Update all the uses. 128 f.tcm.traverse(func(tc *TestCoverage) { 129 key := spansetKey(tc.Spans.String()) 130 if g, ok := spangroupMap[key]; ok { 131 tc.Spans = nil 132 tc.Group = &g.id 133 } 134 }) 135} 136 137// invertCommon looks for tree nodes with the majority of the child nodes with 138// the same spans. This span is promoted up to the parent, and the children 139// have the span inverted. 140func (o *optimizer) invertForCommon(tc *TestCoverage, t *Test) { 141 wg := sync.WaitGroup{} 142 wg.Add(len(tc.Children)) 143 for id, child := range tc.Children { 144 id, child := id, child 145 go func() { 146 defer wg.Done() 147 o.invertForCommon(child, &t.children[id]) 148 }() 149 } 150 wg.Wait() 151 152 counts := map[SpanID]int{} 153 for _, child := range tc.Children { 154 for span := range child.Spans { 155 counts[span] = counts[span] + 1 156 } 157 } 158 159 for span, count := range counts { 160 if count > len(t.children)/2 { 161 tc.Spans = tc.Spans.invert(span) 162 for _, idx := range t.indices { 163 child := tc.Children.index(idx) 164 child.Spans = child.Spans.invert(span) 165 if child.deletable() { 166 delete(tc.Children, idx) 167 } 168 } 169 } 170 } 171} 172