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