downward_counting_loop.go

     1  // Copyright 2026 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  	"fmt"
     9  
    10  	"cmd/compile/internal/ssa"
    11  	"cmd/compile/internal/ssa/ssaop"
    12  )
    13  
    14  // maybeRewriteLoopToDownwardCountingLoop tries to rewrite the loop to a
    15  // downward counting loop checking against start if the loop body does
    16  // not depend on ind or nxt and end is known before the loop.
    17  // That means this code:
    18  //
    19  //	loop:
    20  //		ind = (Phi (Const [x]) nxt),
    21  //		if ind < end
    22  //		then goto enter_loop
    23  //		else goto exit_loop
    24  //
    25  //	enter_loop:
    26  //		do something without using ind nor nxt
    27  //		nxt = inc + ind
    28  //		goto loop
    29  //
    30  //	exit_loop:
    31  //
    32  // is rewritten to:
    33  //
    34  //	loop:
    35  //		ind = (Phi end nxt)
    36  //		if (Const [x]) < ind
    37  //		then goto enter_loop
    38  //		else goto exit_loop
    39  //
    40  //	enter_loop:
    41  //		do something without using ind nor nxt
    42  //		nxt = ind - inc
    43  //		goto loop
    44  //
    45  //	exit_loop:
    46  //
    47  // This is better because it only requires to keep ind then nxt alive while looping,
    48  // while the original form keeps ind then nxt and end alive.
    49  //
    50  // If the loop could not be rewritten, it is left unchanged.
    51  func maybeRewriteLoopToDownwardCountingLoop(f *ssa.Func, v indVar) {
    52  	ind := v.ind
    53  	nxt := v.nxt
    54  	if !(ind.Uses == 2 && // 2 used by comparison and next
    55  		nxt.Uses == 1) { // 1 used by induction
    56  		return
    57  	}
    58  
    59  	start, end := v.min, v.max
    60  
    61  	if !start.IsGenericIntConst() {
    62  		// if start is not a constant we would be winning nothing from inverting the loop
    63  		return
    64  	}
    65  	if end.IsGenericIntConst() {
    66  		// TODO: if both start and end are constants we should rewrite such that the comparison
    67  		// is against zero and nxt is ++ or -- operation
    68  		// That means:
    69  		//	for i := 2; i < 11; i += 2 {
    70  		// should be rewritten to:
    71  		//	for i := 5; 0 < i; i-- {
    72  		return
    73  	}
    74  
    75  	if end.Block == ind.Block {
    76  		// we can't rewrite loops where the condition depends on the loop body
    77  		// this simple check is forced to work because if this is true a Phi in ind.Block must exist
    78  		return
    79  	}
    80  
    81  	check := v.entry.Preds[0].B.Controls[0]
    82  
    83  	neededRoom := -v.step
    84  
    85  	// The whole range of safe numbers to land in to stop the loop is shifted by one if the bounds are exclusive.
    86  	if neededRoom < 0 && v.flags&indVarMinExc == 1 {
    87  		neededRoom++ // safe because it is always against the number's sign
    88  	}
    89  	if neededRoom > 0 && v.flags&indVarMaxInc == 0 {
    90  		neededRoom-- // safe because it is always against the number's sign
    91  	}
    92  
    93  	switch check.Op {
    94  	case ssaop.OpLess8, ssaop.OpLess16, ssaop.OpLess32, ssaop.OpLess64, ssaop.OpLeq8, ssaop.OpLeq16, ssaop.OpLeq32, ssaop.OpLeq64:
    95  		if _, ok := ssa.SafeAdd(start.AuxInt, neededRoom, uint(start.Type.Size())*8); !ok {
    96  			// We lack sufficient room after start to safely land without an overflow.
    97  			// See go.dev/issue/78303
    98  			return
    99  		}
   100  	case ssaop.OpLess8U, ssaop.OpLess16U, ssaop.OpLess32U, ssaop.OpLess64U, ssaop.OpLeq8U, ssaop.OpLeq16U, ssaop.OpLeq32U, ssaop.OpLeq64U:
   101  		panic(`parseIndVar didn't yet support unsigned induction variables, this code doesn't yet support them either.
   102  If you are seeing this it is probably because you've fixed https://go.dev/issue/65918.
   103  You need to update this code and add tests then.`)
   104  	case ssaop.OpEq8, ssaop.OpEq16, ssaop.OpEq32, ssaop.OpEq64, ssaop.OpNeq8, ssaop.OpNeq16, ssaop.OpNeq32, ssaop.OpNeq64:
   105  		panic(`parseIndVar didn't yet support induction variables using == or !=.
   106  If you are seeing this it is probably because you've added support for them.
   107  You need to update this code and add tests then.`)
   108  	default:
   109  		panic(fmt.Sprintf("unreachable; unexpected induction variable comparator %v %v", check, check.Op))
   110  	}
   111  
   112  	idxEnd, idxStart := -1, -1
   113  	for i, v := range check.Args {
   114  		if v == end {
   115  			idxEnd = i
   116  			break
   117  		}
   118  	}
   119  	for i, v := range ind.Args {
   120  		if v == start {
   121  			idxStart = i
   122  			break
   123  		}
   124  	}
   125  	if idxEnd < 0 || idxStart < 0 {
   126  		return
   127  	}
   128  
   129  	sdom := f.Sdom()
   130  	// the end may not dominate the ind after rewrite, check it first
   131  	if !sdom.IsAncestorEq(end.Block, ind.Block) {
   132  		return
   133  	}
   134  
   135  	// swap start and end in the loop
   136  	check.SetArg(idxEnd, start)
   137  	ind.SetArg(idxStart, end)
   138  
   139  	// invert the check
   140  	check.Args[0], check.Args[1] = check.Args[1], check.Args[0]
   141  
   142  	if nxt.Args[0] != ind {
   143  		// unlike additions subtractions are not commutative so be sure we get it right
   144  		nxt.Args[0], nxt.Args[1] = nxt.Args[1], nxt.Args[0]
   145  	}
   146  
   147  	switch nxt.Op {
   148  	case ssaop.OpAdd8:
   149  		nxt.Op = ssaop.OpSub8
   150  	case ssaop.OpAdd16:
   151  		nxt.Op = ssaop.OpSub16
   152  	case ssaop.OpAdd32:
   153  		nxt.Op = ssaop.OpSub32
   154  	case ssaop.OpAdd64:
   155  		nxt.Op = ssaop.OpSub64
   156  	case ssaop.OpSub8:
   157  		nxt.Op = ssaop.OpAdd8
   158  	case ssaop.OpSub16:
   159  		nxt.Op = ssaop.OpAdd16
   160  	case ssaop.OpSub32:
   161  		nxt.Op = ssaop.OpAdd32
   162  	case ssaop.OpSub64:
   163  		nxt.Op = ssaop.OpAdd64
   164  	default:
   165  		panic("unreachable")
   166  	}
   167  
   168  	if f.Pass.Debug > 0 {
   169  		f.Warnl(ind.Pos, "Inverted loop iteration")
   170  	}
   171  }
   172
View as plain text