layout.go

     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.
    16  func layoutRegallocOrder(f *Func) []*Block {
    17  	// remnant of an experiment; perhaps there will be another.
    18  	return layoutOrder(f)
    19  }
    20  
    21  func layoutOrder(f *Func) []*Block {
    22  	order := make([]*Block, 0, f.NumBlocks())
    23  	scheduled := make([]bool, f.NumBlocks())
    24  	idToBlock := make([]*Block, f.NumBlocks())
    25  	indegree := make([]int, f.NumBlocks())
    26  	posdegree := f.newSparseSet(f.NumBlocks()) // blocks with positive remaining degree
    27  	defer f.retSparseSet(posdegree)
    28  	// blocks with zero remaining degree. Use slice to simulate a LIFO queue to implement
    29  	// the depth-first topology sorting algorithm.
    30  	var zerodegree []ID
    31  	// LIFO queue. Track the successor blocks of the scheduled block so that when we
    32  	// encounter loops, we choose to schedule the successor block of the most recently
    33  	// scheduled block.
    34  	var succs []ID
    35  	exit := f.newSparseSet(f.NumBlocks()) // exit blocks
    36  	defer f.retSparseSet(exit)
    37  
    38  	// Populate idToBlock and find exit blocks.
    39  	for _, b := range f.Blocks {
    40  		idToBlock[b.ID] = b
    41  		if b.Kind == BlockExit {
    42  			exit.add(b.ID)
    43  		}
    44  	}
    45  
    46  	// Expand exit to include blocks post-dominated by exit blocks.
    47  	for {
    48  		changed := false
    49  		for _, id := range exit.contents() {
    50  			b := idToBlock[id]
    51  		NextPred:
    52  			for _, pe := range b.Preds {
    53  				p := pe.b
    54  				if exit.contains(p.ID) {
    55  					continue
    56  				}
    57  				for _, s := range p.Succs {
    58  					if !exit.contains(s.b.ID) {
    59  						continue NextPred
    60  					}
    61  				}
    62  				// All Succs are in exit; add p.
    63  				exit.add(p.ID)
    64  				changed = true
    65  			}
    66  		}
    67  		if !changed {
    68  			break
    69  		}
    70  	}
    71  
    72  	// Initialize indegree of each block
    73  	for _, b := range f.Blocks {
    74  		if exit.contains(b.ID) {
    75  			// exit blocks are always scheduled last
    76  			continue
    77  		}
    78  		indegree[b.ID] = len(b.Preds)
    79  		if len(b.Preds) == 0 {
    80  			// Push an element to the tail of the queue.
    81  			zerodegree = append(zerodegree, b.ID)
    82  		} else {
    83  			posdegree.add(b.ID)
    84  		}
    85  	}
    86  
    87  	bid := f.Entry.ID
    88  blockloop:
    89  	for {
    90  		// add block to schedule
    91  		b := idToBlock[bid]
    92  		order = append(order, b)
    93  		scheduled[bid] = true
    94  		if len(order) == len(f.Blocks) {
    95  			break
    96  		}
    97  
    98  		// Here, the order of traversing the b.Succs affects the direction in which the topological
    99  		// sort advances in depth. Take the following cfg as an example, regardless of other factors.
   100  		//           b1
   101  		//         0/ \1
   102  		//        b2   b3
   103  		// Traverse b.Succs in order, the right child node b3 will be scheduled immediately after
   104  		// b1, traverse b.Succs in reverse order, the left child node b2 will be scheduled
   105  		// immediately after b1. The test results show that reverse traversal performs a little
   106  		// better.
   107  		// Note: You need to consider both layout and register allocation when testing performance.
   108  		for i := len(b.Succs) - 1; i >= 0; i-- {
   109  			c := b.Succs[i].b
   110  			indegree[c.ID]--
   111  			if indegree[c.ID] == 0 {
   112  				posdegree.remove(c.ID)
   113  				zerodegree = append(zerodegree, c.ID)
   114  			} else {
   115  				succs = append(succs, c.ID)
   116  			}
   117  		}
   118  
   119  		// Pick the next block to schedule
   120  		// Pick among the successor blocks that have not been scheduled yet.
   121  
   122  		// Use likely direction if we have it.
   123  		var likely *Block
   124  		switch b.Likely {
   125  		case BranchLikely:
   126  			likely = b.Succs[0].b
   127  		case BranchUnlikely:
   128  			likely = b.Succs[1].b
   129  		}
   130  		if likely != nil && !scheduled[likely.ID] {
   131  			bid = likely.ID
   132  			continue
   133  		}
   134  
   135  		// Use degree for now.
   136  		bid = 0
   137  		// TODO: improve this part
   138  		// No successor of the previously scheduled block works.
   139  		// Pick a zero-degree block if we can.
   140  		for len(zerodegree) > 0 {
   141  			// Pop an element from the tail of the queue.
   142  			cid := zerodegree[len(zerodegree)-1]
   143  			zerodegree = zerodegree[:len(zerodegree)-1]
   144  			if !scheduled[cid] {
   145  				bid = cid
   146  				continue blockloop
   147  			}
   148  		}
   149  
   150  		// Still nothing, pick the unscheduled successor block encountered most recently.
   151  		for len(succs) > 0 {
   152  			// Pop an element from the tail of the queue.
   153  			cid := succs[len(succs)-1]
   154  			succs = succs[:len(succs)-1]
   155  			if !scheduled[cid] {
   156  				bid = cid
   157  				continue blockloop
   158  			}
   159  		}
   160  
   161  		// Still nothing, pick any non-exit block.
   162  		for posdegree.size() > 0 {
   163  			cid := posdegree.pop()
   164  			if !scheduled[cid] {
   165  				bid = cid
   166  				continue blockloop
   167  			}
   168  		}
   169  		// Pick any exit block.
   170  		// TODO: Order these to minimize jump distances?
   171  		for {
   172  			cid := exit.pop()
   173  			if !scheduled[cid] {
   174  				bid = cid
   175  				continue blockloop
   176  			}
   177  		}
   178  	}
   179  	f.laidout = true
   180  	return order
   181  	//f.Blocks = order
   182  }
   183
View as plain text