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