Source file src/pkg/cmd/compile/internal/ssa/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. 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		// Initialize indegree of each block
    50		for _, b := range f.Blocks {
    51			idToBlock[b.ID] = b
    52			if b.Kind == BlockExit {
    53				// exit blocks are always scheduled last
    54				// TODO: also add blocks post-dominated by exit blocks
    55				exit.add(b.ID)
    56				continue
    57			}
    58			indegree[b.ID] = len(b.Preds)
    59			if len(b.Preds) == 0 {
    60				zerodegree.add(b.ID)
    61			} else {
    62				posdegree.add(b.ID)
    63			}
    64		}
    65	
    66		bid := f.Entry.ID
    67	blockloop:
    68		for {
    69			// add block to schedule
    70			b := idToBlock[bid]
    71			order = append(order, b)
    72			scheduled[bid] = true
    73			if len(order) == len(f.Blocks) {
    74				break
    75			}
    76	
    77			for _, e := range b.Succs {
    78				c := e.b
    79				indegree[c.ID]--
    80				if indegree[c.ID] == 0 {
    81					posdegree.remove(c.ID)
    82					zerodegree.add(c.ID)
    83				}
    84			}
    85	
    86			// Pick the next block to schedule
    87			// Pick among the successor blocks that have not been scheduled yet.
    88	
    89			// Use likely direction if we have it.
    90			var likely *Block
    91			switch b.Likely {
    92			case BranchLikely:
    93				likely = b.Succs[0].b
    94			case BranchUnlikely:
    95				likely = b.Succs[1].b
    96			}
    97			if likely != nil && !scheduled[likely.ID] {
    98				bid = likely.ID
    99				continue
   100			}
   101	
   102			// Use degree for now.
   103			bid = 0
   104			mindegree := f.NumBlocks()
   105			for _, e := range order[len(order)-1].Succs {
   106				c := e.b
   107				if scheduled[c.ID] || c.Kind == BlockExit {
   108					continue
   109				}
   110				if indegree[c.ID] < mindegree {
   111					mindegree = indegree[c.ID]
   112					bid = c.ID
   113				}
   114			}
   115			if bid != 0 {
   116				continue
   117			}
   118			// TODO: improve this part
   119			// No successor of the previously scheduled block works.
   120			// Pick a zero-degree block if we can.
   121			for zerodegree.size() > 0 {
   122				cid := zerodegree.pop()
   123				if !scheduled[cid] {
   124					bid = cid
   125					continue blockloop
   126				}
   127			}
   128			// Still nothing, pick any non-exit block.
   129			for posdegree.size() > 0 {
   130				cid := posdegree.pop()
   131				if !scheduled[cid] {
   132					bid = cid
   133					continue blockloop
   134				}
   135			}
   136			// Pick any exit block.
   137			// TODO: Order these to minimize jump distances?
   138			for {
   139				cid := exit.pop()
   140				if !scheduled[cid] {
   141					bid = cid
   142					continue blockloop
   143				}
   144			}
   145		}
   146		f.laidout = true
   147		return order
   148		//f.Blocks = order
   149	}
   150	

View as plain text