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