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