Black Lives Matter. Support the Equal Justice Initiative.

Source file src/cmd/compile/internal/ssa/layout.go

Documentation: cmd/compile/internal/ssa

     1  // Copyright 2015 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  // layout orders basic blocks in f with the goal of minimizing control flow instructions.
     8  // After this phase returns, the order of f.Blocks matters and is the order
     9  // in which those blocks will appear in the assembly output.
    10  func layout(f *Func) {
    11  	f.Blocks = layoutOrder(f)
    12  }
    13  
    14  // Register allocation may use a different order which has constraints
    15  // imposed by the linear-scan algorithm. Note that f.pass here is
    16  // regalloc, so the switch is conditional on -d=ssa/regalloc/test=N
    17  func layoutRegallocOrder(f *Func) []*Block {
    18  
    19  	switch f.pass.test {
    20  	case 0: // layout order
    21  		return layoutOrder(f)
    22  	case 1: // existing block order
    23  		return f.Blocks
    24  	case 2: // reverse of postorder; legal, but usually not good.
    25  		po := f.postorder()
    26  		visitOrder := make([]*Block, len(po))
    27  		for i, b := range po {
    28  			j := len(po) - i - 1
    29  			visitOrder[j] = b
    30  		}
    31  		return visitOrder
    32  	}
    33  
    34  	return nil
    35  }
    36  
    37  func layoutOrder(f *Func) []*Block {
    38  	order := make([]*Block, 0, f.NumBlocks())
    39  	scheduled := make([]bool, f.NumBlocks())
    40  	idToBlock := make([]*Block, f.NumBlocks())
    41  	indegree := make([]int, f.NumBlocks())
    42  	posdegree := f.newSparseSet(f.NumBlocks()) // blocks with positive remaining degree
    43  	defer f.retSparseSet(posdegree)
    44  	zerodegree := f.newSparseSet(f.NumBlocks()) // blocks with zero remaining degree
    45  	defer f.retSparseSet(zerodegree)
    46  	exit := f.newSparseSet(f.NumBlocks()) // exit blocks
    47  	defer f.retSparseSet(exit)
    48  
    49  	// Populate idToBlock and find exit blocks.
    50  	for _, b := range f.Blocks {
    51  		idToBlock[b.ID] = b
    52  		if b.Kind == BlockExit {
    53  			exit.add(b.ID)
    54  		}
    55  	}
    56  
    57  	// Expand exit to include blocks post-dominated by exit blocks.
    58  	for {
    59  		changed := false
    60  		for _, id := range exit.contents() {
    61  			b := idToBlock[id]
    62  		NextPred:
    63  			for _, pe := range b.Preds {
    64  				p := pe.b
    65  				if exit.contains(p.ID) {
    66  					continue
    67  				}
    68  				for _, s := range p.Succs {
    69  					if !exit.contains(s.b.ID) {
    70  						continue NextPred
    71  					}
    72  				}
    73  				// All Succs are in exit; add p.
    74  				exit.add(p.ID)
    75  				changed = true
    76  			}
    77  		}
    78  		if !changed {
    79  			break
    80  		}
    81  	}
    82  
    83  	// Initialize indegree of each block
    84  	for _, b := range f.Blocks {
    85  		if exit.contains(b.ID) {
    86  			// exit blocks are always scheduled last
    87  			continue
    88  		}
    89  		indegree[b.ID] = len(b.Preds)
    90  		if len(b.Preds) == 0 {
    91  			zerodegree.add(b.ID)
    92  		} else {
    93  			posdegree.add(b.ID)
    94  		}
    95  	}
    96  
    97  	bid := f.Entry.ID
    98  blockloop:
    99  	for {
   100  		// add block to schedule
   101  		b := idToBlock[bid]
   102  		order = append(order, b)
   103  		scheduled[bid] = true
   104  		if len(order) == len(f.Blocks) {
   105  			break
   106  		}
   107  
   108  		for _, e := range b.Succs {
   109  			c := e.b
   110  			indegree[c.ID]--
   111  			if indegree[c.ID] == 0 {
   112  				posdegree.remove(c.ID)
   113  				zerodegree.add(c.ID)
   114  			}
   115  		}
   116  
   117  		// Pick the next block to schedule
   118  		// Pick among the successor blocks that have not been scheduled yet.
   119  
   120  		// Use likely direction if we have it.
   121  		var likely *Block
   122  		switch b.Likely {
   123  		case BranchLikely:
   124  			likely = b.Succs[0].b
   125  		case BranchUnlikely:
   126  			likely = b.Succs[1].b
   127  		}
   128  		if likely != nil && !scheduled[likely.ID] {
   129  			bid = likely.ID
   130  			continue
   131  		}
   132  
   133  		// Use degree for now.
   134  		bid = 0
   135  		mindegree := f.NumBlocks()
   136  		for _, e := range order[len(order)-1].Succs {
   137  			c := e.b
   138  			if scheduled[c.ID] || c.Kind == BlockExit {
   139  				continue
   140  			}
   141  			if indegree[c.ID] < mindegree {
   142  				mindegree = indegree[c.ID]
   143  				bid = c.ID
   144  			}
   145  		}
   146  		if bid != 0 {
   147  			continue
   148  		}
   149  		// TODO: improve this part
   150  		// No successor of the previously scheduled block works.
   151  		// Pick a zero-degree block if we can.
   152  		for zerodegree.size() > 0 {
   153  			cid := zerodegree.pop()
   154  			if !scheduled[cid] {
   155  				bid = cid
   156  				continue blockloop
   157  			}
   158  		}
   159  		// Still nothing, pick any non-exit block.
   160  		for posdegree.size() > 0 {
   161  			cid := posdegree.pop()
   162  			if !scheduled[cid] {
   163  				bid = cid
   164  				continue blockloop
   165  			}
   166  		}
   167  		// Pick any exit block.
   168  		// TODO: Order these to minimize jump distances?
   169  		for {
   170  			cid := exit.pop()
   171  			if !scheduled[cid] {
   172  				bid = cid
   173  				continue blockloop
   174  			}
   175  		}
   176  	}
   177  	f.laidout = true
   178  	return order
   179  	//f.Blocks = order
   180  }
   181  

View as plain text