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 ssa
     6  
     7  import "fmt"
     8  
     9  // maybeRewriteLoopToDownwardCountingLoop tries to rewrite the loop to a
    10  // downward counting loop checking against start if the loop body does
    11  // not depend on ind or nxt and end is known before the loop.
    12  // That means this code:
    13  //
    14  //	loop:
    15  //		ind = (Phi (Const [x]) nxt),
    16  //		if ind < end
    17  //		then goto enter_loop
    18  //		else goto exit_loop
    19  //
    20  //	enter_loop:
    21  //		do something without using ind nor nxt
    22  //		nxt = inc + ind
    23  //		goto loop
    24  //
    25  //	exit_loop:
    26  //
    27  // is rewritten to:
    28  //
    29  //	loop:
    30  //		ind = (Phi end nxt)
    31  //		if (Const [x]) < ind
    32  //		then goto enter_loop
    33  //		else goto exit_loop
    34  //
    35  //	enter_loop:
    36  //		do something without using ind nor nxt
    37  //		nxt = ind - inc
    38  //		goto loop
    39  //
    40  //	exit_loop:
    41  //
    42  // This is better because it only requires to keep ind then nxt alive while looping,
    43  // while the original form keeps ind then nxt and end alive.
    44  //
    45  // If the loop could not be rewritten, it is left unchanged.
    46  func maybeRewriteLoopToDownwardCountingLoop(f *Func, v indVar) {
    47  	ind := v.ind
    48  	nxt := v.nxt
    49  	if !(ind.Uses == 2 && // 2 used by comparison and next
    50  		nxt.Uses == 1) { // 1 used by induction
    51  		return
    52  	}
    53  
    54  	start, end := v.min, v.max
    55  	if v.flags&indVarCountDown != 0 {
    56  		start, end = end, start
    57  	}
    58  
    59  	if !start.isGenericIntConst() {
    60  		// if start is not a constant we would be winning nothing from inverting the loop
    61  		return
    62  	}
    63  	if end.isGenericIntConst() {
    64  		// TODO: if both start and end are constants we should rewrite such that the comparison
    65  		// is against zero and nxt is ++ or -- operation
    66  		// That means:
    67  		//	for i := 2; i < 11; i += 2 {
    68  		// should be rewritten to:
    69  		//	for i := 5; 0 < i; i-- {
    70  		return
    71  	}
    72  
    73  	if end.Block == ind.Block {
    74  		// we can't rewrite loops where the condition depends on the loop body
    75  		// this simple check is forced to work because if this is true a Phi in ind.Block must exist
    76  		return
    77  	}
    78  
    79  	check := ind.Block.Controls[0]
    80  	// invert the check
    81  	check.Args[0], check.Args[1] = check.Args[1], check.Args[0]
    82  
    83  	// swap start and end in the loop
    84  	for i, v := range check.Args {
    85  		if v != end {
    86  			continue
    87  		}
    88  
    89  		check.SetArg(i, start)
    90  		goto replacedEnd
    91  	}
    92  	panic(fmt.Sprintf("unreachable, ind: %v, start: %v, end: %v", ind, start, end))
    93  replacedEnd:
    94  
    95  	for i, v := range ind.Args {
    96  		if v != start {
    97  			continue
    98  		}
    99  
   100  		ind.SetArg(i, end)
   101  		goto replacedStart
   102  	}
   103  	panic(fmt.Sprintf("unreachable, ind: %v, start: %v, end: %v", ind, start, end))
   104  replacedStart:
   105  
   106  	if nxt.Args[0] != ind {
   107  		// unlike additions subtractions are not commutative so be sure we get it right
   108  		nxt.Args[0], nxt.Args[1] = nxt.Args[1], nxt.Args[0]
   109  	}
   110  
   111  	switch nxt.Op {
   112  	case OpAdd8:
   113  		nxt.Op = OpSub8
   114  	case OpAdd16:
   115  		nxt.Op = OpSub16
   116  	case OpAdd32:
   117  		nxt.Op = OpSub32
   118  	case OpAdd64:
   119  		nxt.Op = OpSub64
   120  	case OpSub8:
   121  		nxt.Op = OpAdd8
   122  	case OpSub16:
   123  		nxt.Op = OpAdd16
   124  	case OpSub32:
   125  		nxt.Op = OpAdd32
   126  	case OpSub64:
   127  		nxt.Op = OpAdd64
   128  	default:
   129  		panic("unreachable")
   130  	}
   131  
   132  	if f.pass.debug > 0 {
   133  		f.Warnl(ind.Pos, "Inverted loop iteration")
   134  	}
   135  }
   136
View as plain text