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