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  	loopOrder := f.Cache.allocIntSlice(len(loopnest.loops))
    86  	for i := range loopOrder {
    87  		loopOrder[i] = i
    88  	}
    89  	defer f.Cache.freeIntSlice(loopOrder)
    90  	slices.SortFunc(loopOrder, func(i, j int) int {
    91  		di := loopnest.loops[i].depth
    92  		dj := loopnest.loops[j].depth
    93  		switch {
    94  		case di > dj:
    95  			return -1
    96  		case di < dj:
    97  			return 1
    98  		default:
    99  			return 0
   100  		}
   101  	})
   102  
   103  	// Check each loop header and decide if we want to move it.
   104  	for _, loopIdx := range loopOrder {
   105  		loop := loopnest.loops[loopIdx]
   106  		b := loop.header
   107  		var p *Block // b's in-loop predecessor
   108  		for _, e := range b.Preds {
   109  			if e.b.Kind != BlockPlain {
   110  				continue
   111  			}
   112  			if loopnest.b2l[e.b.ID] != loop {
   113  				continue
   114  			}
   115  			p = e.b
   116  		}
   117  		if p == nil {
   118  			continue
   119  		}
   120  		tops[loop.header.ID] = p
   121  		p.Hotness |= HotInitial
   122  		if f.IsPgoHot {
   123  			p.Hotness |= HotPgo
   124  		}
   125  		// blocks will be arranged so that p is ordered first, if it isn't already.
   126  		if p == b { // p is header, already first (and also, only block in the loop)
   127  			continue
   128  		}
   129  		p.Hotness |= HotNotFlowIn
   130  
   131  		// the loop header b follows p
   132  		after[p.ID] = []*Block{b}
   133  		for {
   134  			nextIdx := idToIdx[b.ID] + 1
   135  			if nextIdx >= len(f.Blocks) { // reached end of function (maybe impossible?)
   136  				break
   137  			}
   138  			nextb := f.Blocks[nextIdx]
   139  			if nextb == p { // original loop predecessor is next
   140  				break
   141  			}
   142  			if bloop := loopnest.b2l[nextb.ID]; bloop != nil {
   143  				if bloop == loop || bloop.outer == loop && tops[bloop.header.ID] == nextb {
   144  					after[p.ID] = append(after[p.ID], nextb)
   145  				}
   146  			}
   147  			b = nextb
   148  		}
   149  		// Swap b and p so that we'll handle p before b when moving blocks.
   150  		f.Blocks[idToIdx[loop.header.ID]] = p
   151  		f.Blocks[idToIdx[p.ID]] = loop.header
   152  		idToIdx[loop.header.ID], idToIdx[p.ID] = idToIdx[p.ID], idToIdx[loop.header.ID]
   153  
   154  		// Place loop blocks after p.
   155  		for _, b := range after[p.ID] {
   156  			move[b.ID] = struct{}{}
   157  		}
   158  	}
   159  
   160  	// Move blocks to their destinations in a single pass.
   161  	// We rely here on the fact that loop headers must come
   162  	// before the rest of the loop.  And that relies on the
   163  	// fact that we only identify reducible loops.
   164  	j := 0
   165  	// Some blocks that are not part of a loop may be placed
   166  	// between loop blocks. In order to avoid these blocks from
   167  	// being overwritten, use a temporary slice.
   168  	oldOrder := f.Cache.allocBlockSlice(len(f.Blocks))
   169  	defer f.Cache.freeBlockSlice(oldOrder)
   170  	copy(oldOrder, f.Blocks)
   171  	var moveBlocks func(bs []*Block)
   172  	moveBlocks = func(blocks []*Block) {
   173  		for _, a := range blocks {
   174  			f.Blocks[j] = a
   175  			j++
   176  			if nextBlocks, ok := after[a.ID]; ok {
   177  				moveBlocks(nextBlocks)
   178  			}
   179  		}
   180  	}
   181  	for _, b := range oldOrder {
   182  		if _, ok := move[b.ID]; ok {
   183  			continue
   184  		}
   185  		f.Blocks[j] = b
   186  		j++
   187  		moveBlocks(after[b.ID])
   188  	}
   189  	if j != len(oldOrder) {
   190  		f.Fatalf("bad reordering in looprotate")
   191  	}
   192  }
   193
View as plain text