Home | History | Annotate | Download | only in 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 	order := make([]*Block, 0, f.NumBlocks())
     12 	scheduled := make([]bool, f.NumBlocks())
     13 	idToBlock := make([]*Block, f.NumBlocks())
     14 	indegree := make([]int, f.NumBlocks())
     15 	posdegree := f.newSparseSet(f.NumBlocks()) // blocks with positive remaining degree
     16 	defer f.retSparseSet(posdegree)
     17 	zerodegree := f.newSparseSet(f.NumBlocks()) // blocks with zero remaining degree
     18 	defer f.retSparseSet(zerodegree)
     19 	exit := f.newSparseSet(f.NumBlocks()) // exit blocks
     20 	defer f.retSparseSet(exit)
     21 
     22 	// Initialize indegree of each block
     23 	for _, b := range f.Blocks {
     24 		idToBlock[b.ID] = b
     25 		if b.Kind == BlockExit {
     26 			// exit blocks are always scheduled last
     27 			// TODO: also add blocks post-dominated by exit blocks
     28 			exit.add(b.ID)
     29 			continue
     30 		}
     31 		indegree[b.ID] = len(b.Preds)
     32 		if len(b.Preds) == 0 {
     33 			zerodegree.add(b.ID)
     34 		} else {
     35 			posdegree.add(b.ID)
     36 		}
     37 	}
     38 
     39 	bid := f.Entry.ID
     40 blockloop:
     41 	for {
     42 		// add block to schedule
     43 		b := idToBlock[bid]
     44 		order = append(order, b)
     45 		scheduled[bid] = true
     46 		if len(order) == len(f.Blocks) {
     47 			break
     48 		}
     49 
     50 		for _, e := range b.Succs {
     51 			c := e.b
     52 			indegree[c.ID]--
     53 			if indegree[c.ID] == 0 {
     54 				posdegree.remove(c.ID)
     55 				zerodegree.add(c.ID)
     56 			}
     57 		}
     58 
     59 		// Pick the next block to schedule
     60 		// Pick among the successor blocks that have not been scheduled yet.
     61 
     62 		// Use likely direction if we have it.
     63 		var likely *Block
     64 		switch b.Likely {
     65 		case BranchLikely:
     66 			likely = b.Succs[0].b
     67 		case BranchUnlikely:
     68 			likely = b.Succs[1].b
     69 		}
     70 		if likely != nil && !scheduled[likely.ID] {
     71 			bid = likely.ID
     72 			continue
     73 		}
     74 
     75 		// Use degree for now.
     76 		bid = 0
     77 		mindegree := f.NumBlocks()
     78 		for _, e := range order[len(order)-1].Succs {
     79 			c := e.b
     80 			if scheduled[c.ID] || c.Kind == BlockExit {
     81 				continue
     82 			}
     83 			if indegree[c.ID] < mindegree {
     84 				mindegree = indegree[c.ID]
     85 				bid = c.ID
     86 			}
     87 		}
     88 		if bid != 0 {
     89 			continue
     90 		}
     91 		// TODO: improve this part
     92 		// No successor of the previously scheduled block works.
     93 		// Pick a zero-degree block if we can.
     94 		for zerodegree.size() > 0 {
     95 			cid := zerodegree.pop()
     96 			if !scheduled[cid] {
     97 				bid = cid
     98 				continue blockloop
     99 			}
    100 		}
    101 		// Still nothing, pick any non-exit block.
    102 		for posdegree.size() > 0 {
    103 			cid := posdegree.pop()
    104 			if !scheduled[cid] {
    105 				bid = cid
    106 				continue blockloop
    107 			}
    108 		}
    109 		// Pick any exit block.
    110 		// TODO: Order these to minimize jump distances?
    111 		for {
    112 			cid := exit.pop()
    113 			if !scheduled[cid] {
    114 				bid = cid
    115 				continue blockloop
    116 			}
    117 		}
    118 	}
    119 	f.Blocks = order
    120 }
    121