shortcircuit.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  // ReplaceUses replaces all uses of old in b with new.
     8  func (b *Block) ReplaceUses(old, new *Value) {
     9  	for _, v := range b.Values {
    10  		for i, a := range v.Args {
    11  			if a == old {
    12  				v.SetArg(i, new)
    13  			}
    14  		}
    15  	}
    16  	for i, v := range b.ControlValues() {
    17  		if v == old {
    18  			b.ReplaceControl(i, new)
    19  		}
    20  	}
    21  }
    22  
    23  // MoveTo moves v to dst, adjusting the appropriate Block.Values slices.
    24  // The caller is responsible for ensuring that this is safe.
    25  // i is the index of v in v.Block.Values.
    26  func (v *Value) MoveTo(dst *Block, i int) {
    27  	if dst.Func.Scheduled {
    28  		v.Fatalf("moveTo after scheduling")
    29  	}
    30  	src := v.Block
    31  	if src.Values[i] != v {
    32  		v.Fatalf("moveTo bad index %d", v, i)
    33  	}
    34  	if src == dst {
    35  		return
    36  	}
    37  	v.Block = dst
    38  	dst.Values = append(dst.Values, v)
    39  	last := len(src.Values) - 1
    40  	src.Values[i] = src.Values[last]
    41  	src.Values[last] = nil
    42  	src.Values = src.Values[:last]
    43  }
    44  
    45  // FlowsTo checks that the subgraph starting from v and ends at t is a DAG, with
    46  // the following constraints:
    47  //
    48  //	(1) v can reach t.
    49  //	(2) v's connected component removing the paths containing t is a DAG.
    50  //	(3) The blocks in the subgraph G defined in (2) has all their preds also in G,
    51  //	    except v.
    52  //	(4) The subgraph defined in (2) has a size smaller than cap.
    53  //
    54  //	We know that the subgraph G defined in constraint (2)(3) has the property that v
    55  //	dominates all the blocks in G:
    56  //		If there exist a block x in G that is not dominated by v, then there exist a
    57  //		path P from entry to x that does not contain v. Denote x's predecessor in P
    58  //		as x', then x' must also be in G given constraint (3), same to its pred x''
    59  //		in P. Given constraint (2), by going back in P we will in the end reach v,
    60  //		which conflicts with the definition of P.
    61  //
    62  // Constraint (2)'s DAG requirement could be further relaxed to contain "internal"
    63  // loops that doesn't change the dominance relation of v. But that is more subtle
    64  // and requires another constraint on the source block v, and a more complex proof.
    65  // Furthermore optimizing the branch guarding a loop might bring less gains as the
    66  // loop itself might be the bottleneck.
    67  func (v *Block) FlowsTo(t *Block, cap int) map[*Block]struct{} {
    68  	seen := map[*Block]struct{}{}
    69  	var boundedDFS func(b *Block)
    70  	hasPathToT := false
    71  	fullyExplored := true
    72  	isDAG := true
    73  	visited := map[*Block]struct{}{}
    74  	boundedDFS = func(b *Block) {
    75  		if _, ok := seen[b]; ok {
    76  			return
    77  		}
    78  		if _, ok := visited[b]; ok {
    79  			isDAG = false
    80  			return
    81  		}
    82  		if b == t {
    83  			// do not put t into seen, this way
    84  			// if v can reach t's connected component without going through t,
    85  			// it will fail the pred check after boundedDFSUntil.
    86  			hasPathToT = true
    87  			return
    88  		}
    89  		if len(seen) > cap {
    90  			fullyExplored = false
    91  			return
    92  		}
    93  		seen[b] = struct{}{}
    94  		visited[b] = struct{}{}
    95  		for _, se := range b.Succs {
    96  			boundedDFS(se.B)
    97  			if !(isDAG && fullyExplored) {
    98  				return
    99  			}
   100  		}
   101  		delete(visited, b)
   102  	}
   103  	boundedDFS(v)
   104  	if hasPathToT && fullyExplored && isDAG {
   105  		for b := range seen {
   106  			if b != v {
   107  				for _, se := range b.Preds {
   108  					if _, ok := seen[se.B]; !ok {
   109  						return nil
   110  					}
   111  				}
   112  			}
   113  		}
   114  		return seen
   115  	}
   116  	return nil
   117  }
   118
View as plain text