looprotate.go

     1  // Copyright 2017 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  	"slices"
     9  
    10  	"cmd/compile/internal/ssa"
    11  	"cmd/compile/internal/ssa/block"
    12  )
    13  
    14  // loopRotate converts loops with a check-loop-condition-at-beginning
    15  // to loops with a check-loop-condition-at-end.
    16  // This helps loops avoid extra unnecessary jumps.
    17  //
    18  //	 loop:
    19  //	   CMPQ ...
    20  //	   JGE exit
    21  //	   ...
    22  //	   JMP loop
    23  //	 exit:
    24  //
    25  //	  JMP entry
    26  //	loop:
    27  //	  ...
    28  //	entry:
    29  //	  CMPQ ...
    30  //	  JLT loop
    31  func loopRotate(f *ssa.Func) {
    32  	loopnest := f.Loopnest()
    33  	if loopnest.HasIrreducible {
    34  		return
    35  	}
    36  	if len(loopnest.Loops) == 0 {
    37  		return
    38  	}
    39  
    40  	idToIdx := f.Cache.AllocIntSlice(f.NumBlocks())
    41  	defer f.Cache.FreeIntSlice(idToIdx)
    42  	for i, b := range f.Blocks {
    43  		idToIdx[b.ID] = i
    44  	}
    45  
    46  	// Set of blocks we're moving, by ID.
    47  	move := map[ssa.ID]struct{}{}
    48  
    49  	// Map from block ID to the moving blocks that should
    50  	// come right after it.
    51  	// If a block, which has its ID present in keys of the 'after' map,
    52  	// occurs in some other block's 'after' list, that represents whole
    53  	// nested loop, e.g. consider an inner loop I nested into an outer
    54  	// loop O. It and Ot are corresponding top block for these loops
    55  	// chosen by our algorithm, and It is in the Ot's 'after' list.
    56  	//
    57  	//    Before:                     After:
    58  	//
    59  	//       e                       e
    60  	//       │                       │
    61  	//       │                       │Ot ◄───┐
    62  	//       ▼                       ▼▼      │
    63  	//   ┌───Oh ◄────┐           ┌─┬─Oh      │
    64  	//   │   │       │           │ │         │
    65  	//   │   │       │           │ │ It◄───┐ │
    66  	//   │   ▼       │           │ │ ▼     │ │
    67  	//   │ ┌─Ih◄───┐ │           │ └►Ih    │ │
    68  	//   │ │ │     │ │           │ ┌─┤     │ │
    69  	//   │ │ ▼     │ │           │ │ ▼     │ │
    70  	//   │ │ Ib    │ │           │ │ Ib    │ │
    71  	//   │ │ └─►It─┘ │           │ │ └─────┘ │
    72  	//   │ │         │           │ │         │
    73  	//   │ └►Ie      │           │ └►Ie      │
    74  	//   │   └─►Ot───┘           │   └───────┘
    75  	//   │                       │
    76  	//   └──►Oe                  └──►Oe
    77  	//
    78  	// We build the 'after' lists for each of the top blocks Ot and It:
    79  	//   after[Ot]: Oh, It, Ie
    80  	//   after[It]: Ih, Ib
    81  	after := map[ssa.ID][]*ssa.Block{}
    82  
    83  	// Map from loop header ID to the new top block for the loop.
    84  	tops := map[ssa.ID]*ssa.Block{}
    85  
    86  	// Order loops to rotate any child loop before adding its top block
    87  	// to the parent loop's 'after' list.
    88  	loopOrder := f.Cache.AllocIntSlice(len(loopnest.Loops))
    89  	for i := range loopOrder {
    90  		loopOrder[i] = i
    91  	}
    92  	defer f.Cache.FreeIntSlice(loopOrder)
    93  	slices.SortFunc(loopOrder, func(i, j int) int {
    94  		di := loopnest.Loops[i].Depth
    95  		dj := loopnest.Loops[j].Depth
    96  		switch {
    97  		case di > dj:
    98  			return -1
    99  		case di < dj:
   100  			return 1
   101  		default:
   102  			return 0
   103  		}
   104  	})
   105  
   106  	// Check each loop header and decide if we want to move it.
   107  	for _, loopIdx := range loopOrder {
   108  		loop := loopnest.Loops[loopIdx]
   109  		b := loop.Header
   110  		var p *ssa.Block // b's in-loop predecessor
   111  		for _, e := range b.Preds {
   112  			if e.B.Kind != block.BlockPlain {
   113  				continue
   114  			}
   115  			if loopnest.B2L[e.B.ID] != loop {
   116  				continue
   117  			}
   118  			p = e.B
   119  		}
   120  		if p == nil {
   121  			continue
   122  		}
   123  		tops[loop.Header.ID] = p
   124  		p.Hotness |= ssa.HotInitial
   125  		if f.IsPgoHot {
   126  			p.Hotness |= ssa.HotPgo
   127  		}
   128  		// blocks will be arranged so that p is ordered first, if it isn't already.
   129  		if p == b { // p is header, already first (and also, only block in the loop)
   130  			continue
   131  		}
   132  		p.Hotness |= ssa.HotNotFlowIn
   133  
   134  		// the loop header b follows p
   135  		after[p.ID] = []*ssa.Block{b}
   136  		for {
   137  			nextIdx := idToIdx[b.ID] + 1
   138  			if nextIdx >= len(f.Blocks) { // reached end of function (maybe impossible?)
   139  				break
   140  			}
   141  			nextb := f.Blocks[nextIdx]
   142  			if nextb == p { // original loop predecessor is next
   143  				break
   144  			}
   145  			if bloop := loopnest.B2L[nextb.ID]; bloop != nil {
   146  				if bloop == loop || bloop.Outer == loop && tops[bloop.Header.ID] == nextb {
   147  					after[p.ID] = append(after[p.ID], nextb)
   148  				}
   149  			}
   150  			b = nextb
   151  		}
   152  		// Swap b and p so that we'll handle p before b when moving blocks.
   153  		f.Blocks[idToIdx[loop.Header.ID]] = p
   154  		f.Blocks[idToIdx[p.ID]] = loop.Header
   155  		idToIdx[loop.Header.ID], idToIdx[p.ID] = idToIdx[p.ID], idToIdx[loop.Header.ID]
   156  
   157  		// Place loop blocks after p.
   158  		for _, b := range after[p.ID] {
   159  			move[b.ID] = struct{}{}
   160  		}
   161  	}
   162  
   163  	// Move blocks to their destinations in a single pass.
   164  	// We rely here on the fact that loop headers must come
   165  	// before the rest of the loop.  And that relies on the
   166  	// fact that we only identify reducible loops.
   167  	j := 0
   168  	// Some blocks that are not part of a loop may be placed
   169  	// between loop blocks. In order to avoid these blocks from
   170  	// being overwritten, use a temporary slice.
   171  	oldOrder := f.Cache.AllocBlockSlice(len(f.Blocks))
   172  	defer f.Cache.FreeBlockSlice(oldOrder)
   173  	copy(oldOrder, f.Blocks)
   174  	var moveBlocks func(bs []*ssa.Block)
   175  	moveBlocks = func(blocks []*ssa.Block) {
   176  		for _, a := range blocks {
   177  			f.Blocks[j] = a
   178  			j++
   179  			if nextBlocks, ok := after[a.ID]; ok {
   180  				moveBlocks(nextBlocks)
   181  			}
   182  		}
   183  	}
   184  	for _, b := range oldOrder {
   185  		if _, ok := move[b.ID]; ok {
   186  			continue
   187  		}
   188  		f.Blocks[j] = b
   189  		j++
   190  		moveBlocks(after[b.ID])
   191  	}
   192  	if j != len(oldOrder) {
   193  		f.Fatalf("bad reordering in looprotate")
   194  	}
   195  }
   196
View as plain text