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  
    56  	if !start.isGenericIntConst() {
    57  		// if start is not a constant we would be winning nothing from inverting the loop
    58  		return
    59  	}
    60  	if end.isGenericIntConst() {
    61  		// TODO: if both start and end are constants we should rewrite such that the comparison
    62  		// is against zero and nxt is ++ or -- operation
    63  		// That means:
    64  		//	for i := 2; i < 11; i += 2 {
    65  		// should be rewritten to:
    66  		//	for i := 5; 0 < i; i-- {
    67  		return
    68  	}
    69  
    70  	if end.Block == ind.Block {
    71  		// we can't rewrite loops where the condition depends on the loop body
    72  		// this simple check is forced to work because if this is true a Phi in ind.Block must exist
    73  		return
    74  	}
    75  
    76  	check := v.entry.Preds[0].b.Controls[0]
    77  
    78  	neededRoom := -v.step
    79  
    80  	// The whole range of safe numbers to land in to stop the loop is shifted by one if the bounds are exclusive.
    81  	if neededRoom < 0 && v.flags&indVarMinExc == 1 {
    82  		neededRoom++ // safe because it is always against the number's sign
    83  	}
    84  	if neededRoom > 0 && v.flags&indVarMaxInc == 0 {
    85  		neededRoom-- // safe because it is always against the number's sign
    86  	}
    87  
    88  	switch check.Op {
    89  	case OpLess8, OpLess16, OpLess32, OpLess64, OpLeq8, OpLeq16, OpLeq32, OpLeq64:
    90  		if _, ok := safeAdd(start.AuxInt, neededRoom, uint(start.Type.Size())*8); !ok {
    91  			// We lack sufficient room after start to safely land without an overflow.
    92  			// See go.dev/issue/78303
    93  			return
    94  		}
    95  	case OpLess8U, OpLess16U, OpLess32U, OpLess64U, OpLeq8U, OpLeq16U, OpLeq32U, OpLeq64U:
    96  		panic(`parseIndVar didn't yet support unsigned induction variables, this code doesn't yet support them either.
    97  If you are seeing this it is probably because you've fixed https://go.dev/issue/65918.
    98  You need to update this code and add tests then.`)
    99  	case OpEq8, OpEq16, OpEq32, OpEq64, OpNeq8, OpNeq16, OpNeq32, OpNeq64:
   100  		panic(`parseIndVar didn't yet support induction variables using == or !=.
   101  If you are seeing this it is probably because you've added support for them.
   102  You need to update this code and add tests then.`)
   103  	default:
   104  		panic(fmt.Sprintf("unreachable; unexpected induction variable comparator %v %v", check, check.Op))
   105  	}
   106  
   107  	idxEnd, idxStart := -1, -1
   108  	for i, v := range check.Args {
   109  		if v == end {
   110  			idxEnd = i
   111  			break
   112  		}
   113  	}
   114  	for i, v := range ind.Args {
   115  		if v == start {
   116  			idxStart = i
   117  			break
   118  		}
   119  	}
   120  	if idxEnd < 0 || idxStart < 0 {
   121  		return
   122  	}
   123  
   124  	sdom := f.Sdom()
   125  	// the end may not dominate the ind after rewrite, check it first
   126  	if !sdom.IsAncestorEq(end.Block, ind.Block) {
   127  		return
   128  	}
   129  
   130  	// swap start and end in the loop
   131  	check.SetArg(idxEnd, start)
   132  	ind.SetArg(idxStart, end)
   133  
   134  	// invert the check
   135  	check.Args[0], check.Args[1] = check.Args[1], check.Args[0]
   136  
   137  	if nxt.Args[0] != ind {
   138  		// unlike additions subtractions are not commutative so be sure we get it right
   139  		nxt.Args[0], nxt.Args[1] = nxt.Args[1], nxt.Args[0]
   140  	}
   141  
   142  	switch nxt.Op {
   143  	case OpAdd8:
   144  		nxt.Op = OpSub8
   145  	case OpAdd16:
   146  		nxt.Op = OpSub16
   147  	case OpAdd32:
   148  		nxt.Op = OpSub32
   149  	case OpAdd64:
   150  		nxt.Op = OpSub64
   151  	case OpSub8:
   152  		nxt.Op = OpAdd8
   153  	case OpSub16:
   154  		nxt.Op = OpAdd16
   155  	case OpSub32:
   156  		nxt.Op = OpAdd32
   157  	case OpSub64:
   158  		nxt.Op = OpAdd64
   159  	default:
   160  		panic("unreachable")
   161  	}
   162  
   163  	if f.pass.debug > 0 {
   164  		f.Warnl(ind.Pos, "Inverted loop iteration")
   165  	}
   166  }
   167
View as plain text