src/cmd/compile/internal/ssacompile/downward_counting_loop.go

// Copyright 2026 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package ssacompile

import (
	"fmt"

	"cmd/compile/internal/ssa"
	"cmd/compile/internal/ssa/ssaop"
)

// maybeRewriteLoopToDownwardCountingLoop tries to rewrite the loop to a
// downward counting loop checking against start if the loop body does
// not depend on ind or nxt and end is known before the loop.
// That means this code:
//
//	loop:
//		ind = (Phi (Const [x]) nxt),
//		if ind < end
//		then goto enter_loop
//		else goto exit_loop
//
//	enter_loop:
//		do something without using ind nor nxt
//		nxt = inc + ind
//		goto loop
//
//	exit_loop:
//
// is rewritten to:
//
//	loop:
//		ind = (Phi end nxt)
//		if (Const [x]) < ind
//		then goto enter_loop
//		else goto exit_loop
//
//	enter_loop:
//		do something without using ind nor nxt
//		nxt = ind - inc
//		goto loop
//
//	exit_loop:
//
// This is better because it only requires to keep ind then nxt alive while looping,
// while the original form keeps ind then nxt and end alive.
//
// If the loop could not be rewritten, it is left unchanged.
func maybeRewriteLoopToDownwardCountingLoop(f *ssa.Func, v indVar) {
	ind := v.ind
	nxt := v.nxt
	if !(ind.Uses == 2 && // 2 used by comparison and next
		nxt.Uses == 1) { // 1 used by induction
		return
	}

	start, end := v.min, v.max

	if !start.IsGenericIntConst() {
		// if start is not a constant we would be winning nothing from inverting the loop
		return
	}
	if end.IsGenericIntConst() {
		// TODO: if both start and end are constants we should rewrite such that the comparison
		// is against zero and nxt is ++ or -- operation
		// That means:
		//	for i := 2; i < 11; i += 2 {
		// should be rewritten to:
		//	for i := 5; 0 < i; i-- {
		return
	}

	if end.Block == ind.Block {
		// we can't rewrite loops where the condition depends on the loop body
		// this simple check is forced to work because if this is true a Phi in ind.Block must exist
		return
	}

	check := v.entry.Preds[0].B.Controls[0]

	neededRoom := -v.step

	// The whole range of safe numbers to land in to stop the loop is shifted by one if the bounds are exclusive.
	if neededRoom < 0 && v.flags&indVarMinExc == 1 {
		neededRoom++ // safe because it is always against the number's sign
	}
	if neededRoom > 0 && v.flags&indVarMaxInc == 0 {
		neededRoom-- // safe because it is always against the number's sign
	}

	switch check.Op {
	case ssaop.OpLess8, ssaop.OpLess16, ssaop.OpLess32, ssaop.OpLess64, ssaop.OpLeq8, ssaop.OpLeq16, ssaop.OpLeq32, ssaop.OpLeq64:
		if _, ok := ssa.SafeAdd(start.AuxInt, neededRoom, uint(start.Type.Size())*8); !ok {
			// We lack sufficient room after start to safely land without an overflow.
			// See go.dev/issue/78303
			return
		}
	case ssaop.OpLess8U, ssaop.OpLess16U, ssaop.OpLess32U, ssaop.OpLess64U, ssaop.OpLeq8U, ssaop.OpLeq16U, ssaop.OpLeq32U, ssaop.OpLeq64U:
		panic(`parseIndVar didn't yet support unsigned induction variables, this code doesn't yet support them either.
If you are seeing this it is probably because you've fixed https://go.dev/issue/65918.
You need to update this code and add tests then.`)
	case ssaop.OpEq8, ssaop.OpEq16, ssaop.OpEq32, ssaop.OpEq64, ssaop.OpNeq8, ssaop.OpNeq16, ssaop.OpNeq32, ssaop.OpNeq64:
		panic(`parseIndVar didn't yet support induction variables using == or !=.
If you are seeing this it is probably because you've added support for them.
You need to update this code and add tests then.`)
	default:
		panic(fmt.Sprintf("unreachable; unexpected induction variable comparator %v %v", check, check.Op))
	}

	idxEnd, idxStart := -1, -1
	for i, v := range check.Args {
		if v == end {
			idxEnd = i
			break
		}
	}
	for i, v := range ind.Args {
		if v == start {
			idxStart = i
			break
		}
	}
	if idxEnd < 0 || idxStart < 0 {
		return
	}

	sdom := f.Sdom()
	// the end may not dominate the ind after rewrite, check it first
	if !sdom.IsAncestorEq(end.Block, ind.Block) {
		return
	}

	// swap start and end in the loop
	check.SetArg(idxEnd, start)
	ind.SetArg(idxStart, end)

	// invert the check
	check.Args[0], check.Args[1] = check.Args[1], check.Args[0]

	if nxt.Args[0] != ind {
		// unlike additions subtractions are not commutative so be sure we get it right
		nxt.Args[0], nxt.Args[1] = nxt.Args[1], nxt.Args[0]
	}

	switch nxt.Op {
	case ssaop.OpAdd8:
		nxt.Op = ssaop.OpSub8
	case ssaop.OpAdd16:
		nxt.Op = ssaop.OpSub16
	case ssaop.OpAdd32:
		nxt.Op = ssaop.OpSub32
	case ssaop.OpAdd64:
		nxt.Op = ssaop.OpSub64
	case ssaop.OpSub8:
		nxt.Op = ssaop.OpAdd8
	case ssaop.OpSub16:
		nxt.Op = ssaop.OpAdd16
	case ssaop.OpSub32:
		nxt.Op = ssaop.OpAdd32
	case ssaop.OpSub64:
		nxt.Op = ssaop.OpAdd64
	default:
		panic("unreachable")
	}

	if f.Pass.Debug > 0 {
		f.Warnl(ind.Pos, "Inverted loop iteration")
	}
}