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
5package ssa
6
7// loopRotate converts loops with a check-loop-condition-at-beginning
8// to loops with a check-loop-condition-at-end.
9// This helps loops avoid extra unnecessary jumps.
10//
11//	 loop:
12//	   CMPQ ...
13//	   JGE exit
14//	   ...
15//	   JMP loop
16//	 exit:
17//
18//	  JMP entry
19//	loop:
20//	  ...
21//	entry:
22//	  CMPQ ...
23//	  JLT loop
24func loopRotate(f *Func) {
25	loopnest := f.loopnest()
26	if loopnest.hasIrreducible {
27		return
28	}
29	if len(loopnest.loops) == 0 {
30		return
31	}
32
33	idToIdx := f.Cache.allocIntSlice(f.NumBlocks())
34	defer f.Cache.freeIntSlice(idToIdx)
35	for i, b := range f.Blocks {
36		idToIdx[b.ID] = i
37	}
38
39	// Set of blocks we're moving, by ID.
40	move := map[ID]struct{}{}
41
42	// Map from block ID to the moving blocks that should
43	// come right after it.
44	after := map[ID][]*Block{}
45
46	// Check each loop header and decide if we want to move it.
47	for _, loop := range loopnest.loops {
48		b := loop.header
49		var p *Block // b's in-loop predecessor
50		for _, e := range b.Preds {
51			if e.b.Kind != BlockPlain {
52				continue
53			}
54			if loopnest.b2l[e.b.ID] != loop {
55				continue
56			}
57			p = e.b
58		}
59		if p == nil {
60			continue
61		}
62		p.Hotness |= HotInitial
63		if f.IsPgoHot {
64			p.Hotness |= HotPgo
65		}
66		// blocks will be arranged so that p is ordered first, if it isn't already.
67		if p == b { // p is header, already first (and also, only block in the loop)
68			continue
69		}
70		p.Hotness |= HotNotFlowIn
71
72		// the loop header b follows p
73		after[p.ID] = []*Block{b}
74		for {
75			nextIdx := idToIdx[b.ID] + 1
76			if nextIdx >= len(f.Blocks) { // reached end of function (maybe impossible?)
77				break
78			}
79			nextb := f.Blocks[nextIdx]
80			if nextb == p { // original loop predecessor is next
81				break
82			}
83			if loopnest.b2l[nextb.ID] == loop {
84				after[p.ID] = append(after[p.ID], nextb)
85			}
86			b = nextb
87		}
88		// Swap b and p so that we'll handle p before b when moving blocks.
89		f.Blocks[idToIdx[loop.header.ID]] = p
90		f.Blocks[idToIdx[p.ID]] = loop.header
91		idToIdx[loop.header.ID], idToIdx[p.ID] = idToIdx[p.ID], idToIdx[loop.header.ID]
92
93		// Place b after p.
94		for _, b := range after[p.ID] {
95			move[b.ID] = struct{}{}
96		}
97	}
98
99	// Move blocks to their destinations in a single pass.
100	// We rely here on the fact that loop headers must come
101	// before the rest of the loop.  And that relies on the
102	// fact that we only identify reducible loops.
103	j := 0
104	// Some blocks that are not part of a loop may be placed
105	// between loop blocks. In order to avoid these blocks from
106	// being overwritten, use a temporary slice.
107	oldOrder := f.Cache.allocBlockSlice(len(f.Blocks))
108	defer f.Cache.freeBlockSlice(oldOrder)
109	copy(oldOrder, f.Blocks)
110	for _, b := range oldOrder {
111		if _, ok := move[b.ID]; ok {
112			continue
113		}
114		f.Blocks[j] = b
115		j++
116		for _, a := range after[b.ID] {
117			f.Blocks[j] = a
118			j++
119		}
120	}
121	if j != len(oldOrder) {
122		f.Fatalf("bad reordering in looprotate")
123	}
124}
125