File Manager

X7ROOT File Manager

Current Path: /opt/golang/1.19.4/src/cmd/compile/internal/ssa

opt / golang / 1.19.4 / src / cmd / compile / internal / ssa /

📁 ..
📄 README.md(8.14 KB)
📄 TODO(950 B)
📄 addressingmodes.go(23.64 KB)
📄 bench_test.go(531 B)
📄 biasedsparsemap.go(2.71 KB)
📄 block.go(11.1 KB)
📄 branchelim.go(11.98 KB)
📄 branchelim_test.go(5.21 KB)
📄 cache.go(2.46 KB)
📄 check.go(16.59 KB)
📄 checkbce.go(956 B)
📄 compile.go(18.19 KB)
📄 config.go(11.7 KB)
📄 copyelim.go(1.83 KB)
📄 copyelim_test.go(1.29 KB)
📄 critical.go(3.19 KB)
📄 cse.go(9.43 KB)
📄 cse_test.go(4.25 KB)
📄 deadcode.go(9.61 KB)
📄 deadcode_test.go(3.49 KB)
📄 deadstore.go(9.08 KB)
📄 deadstore_test.go(4.09 KB)
📄 debug.go(56.34 KB)
📄 debug_lines_test.go(8.29 KB)
📄 debug_test.go(28.75 KB)
📄 decompose.go(13.41 KB)
📄 dom.go(7.98 KB)
📄 dom_test.go(13.34 KB)
📄 expand_calls.go(63.5 KB)
📄 export_test.go(3.23 KB)
📄 flagalloc.go(6.68 KB)
📄 flags_amd64_test.s(533 B)
📄 flags_arm64_test.s(699 B)
📄 flags_test.go(2.49 KB)
📄 func.go(27.08 KB)
📄 func_test.go(13.07 KB)
📄 fuse.go(6.5 KB)
📄 fuse_branchredirect.go(3.24 KB)
📄 fuse_comparisons.go(4.04 KB)
📄 fuse_test.go(7.21 KB)
📁 gen
📄 html.go(34.72 KB)
📄 id.go(576 B)
📄 layout.go(4.82 KB)
📄 lca.go(3.77 KB)
📄 lca_test.go(1.65 KB)
📄 likelyadjust.go(15.24 KB)
📄 location.go(3.06 KB)
📄 loopbce.go(10.54 KB)
📄 loopreschedchecks.go(15.86 KB)
📄 looprotate.go(2.61 KB)
📄 lower.go(1.36 KB)
📄 magic.go(15.77 KB)
📄 magic_test.go(9.1 KB)
📄 nilcheck.go(11.06 KB)
📄 nilcheck_test.go(12.17 KB)
📄 numberlines.go(7.83 KB)
📄 op.go(18.65 KB)
📄 opGen.go(1.01 MB)
📄 opt.go(308 B)
📄 passbm_test.go(3.14 KB)
📄 phielim.go(1.48 KB)
📄 phiopt.go(8.08 KB)
📄 poset.go(37.2 KB)
📄 poset_test.go(18.14 KB)
📄 print.go(3.85 KB)
📄 prove.go(41.82 KB)
📄 regalloc.go(83.69 KB)
📄 regalloc_test.go(6.49 KB)
📄 rewrite.go(53.49 KB)
📄 rewrite386.go(289.01 KB)
📄 rewrite386splitload.go(4.05 KB)
📄 rewriteAMD64.go(888.95 KB)
📄 rewriteAMD64splitload.go(21.41 KB)
📄 rewriteARM.go(487.7 KB)
📄 rewriteARM64.go(751.84 KB)
📄 rewriteCond_test.go(10.62 KB)
📄 rewriteLOONG64.go(193.44 KB)
📄 rewriteMIPS.go(174.44 KB)
📄 rewriteMIPS64.go(195.55 KB)
📄 rewritePPC64.go(431.6 KB)
📄 rewriteRISCV64.go(159.66 KB)
📄 rewriteS390X.go(433.4 KB)
📄 rewriteWasm.go(109.86 KB)
📄 rewrite_test.go(6.91 KB)
📄 rewritedec.go(10.16 KB)
📄 rewritedec64.go(63.77 KB)
📄 rewritegeneric.go(617.96 KB)
📄 schedule.go(18.23 KB)
📄 schedule_test.go(2.91 KB)
📄 shift_test.go(4.05 KB)
📄 shortcircuit.go(12.63 KB)
📄 shortcircuit_test.go(1.31 KB)
📄 sizeof_test.go(855 B)
📄 softfloat.go(1.99 KB)
📄 sparsemap.go(1.98 KB)
📄 sparseset.go(1.54 KB)
📄 sparsetree.go(8.05 KB)
📄 stackalloc.go(12.79 KB)
📄 stackframe.go(290 B)
📄 stmtlines_test.go(2.96 KB)
📁 testdata
📄 tighten.go(4.3 KB)
📄 trim.go(4.24 KB)
📄 tuple.go(1.97 KB)
📄 value.go(15.21 KB)
📄 writebarrier.go(19.29 KB)
📄 writebarrier_test.go(1.75 KB)
📄 xposmap.go(3.29 KB)
📄 zcse.go(2.07 KB)
📄 zeroextension_test.go(1.66 KB)

Editing: loopbce.go

// Copyright 2018 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package ssa

import (
	"cmd/compile/internal/base"
	"fmt"
	"math"
)

type indVarFlags uint8

const (
	indVarMinExc indVarFlags = 1 << iota // minimum value is exclusive (default: inclusive)
	indVarMaxInc                         // maximum value is inclusive (default: exclusive)
)

type indVar struct {
	ind   *Value // induction variable
	min   *Value // minimum value, inclusive/exclusive depends on flags
	max   *Value // maximum value, inclusive/exclusive depends on flags
	entry *Block // entry block in the loop.
	flags indVarFlags
	// Invariant: for all blocks strictly dominated by entry:
	//	min <= ind <  max    [if flags == 0]
	//	min <  ind <  max    [if flags == indVarMinExc]
	//	min <= ind <= max    [if flags == indVarMaxInc]
	//	min <  ind <= max    [if flags == indVarMinExc|indVarMaxInc]
}

// parseIndVar checks whether the SSA value passed as argument is a valid induction
// variable, and, if so, extracts:
//   - the minimum bound
//   - the increment value
//   - the "next" value (SSA value that is Phi'd into the induction variable every loop)
//
// Currently, we detect induction variables that match (Phi min nxt),
// with nxt being (Add inc ind).
// If it can't parse the induction variable correctly, it returns (nil, nil, nil).
func parseIndVar(ind *Value) (min, inc, nxt *Value) {
	if ind.Op != OpPhi {
		return
	}

if n := ind.Args[0]; n.Op == OpAdd64 && (n.Args[0] == ind || n.Args[1] == ind) {
		min, nxt = ind.Args[1], n
	} else if n := ind.Args[1]; n.Op == OpAdd64 && (n.Args[0] == ind || n.Args[1] == ind) {
		min, nxt = ind.Args[0], n
	} else {
		// Not a recognized induction variable.
		return
	}

if nxt.Args[0] == ind { // nxt = ind + inc
		inc = nxt.Args[1]
	} else if nxt.Args[1] == ind { // nxt = inc + ind
		inc = nxt.Args[0]
	} else {
		panic("unreachable") // one of the cases must be true from the above.
	}

return
}

// findIndVar finds induction variables in a function.
//
// Look for variables and blocks that satisfy the following
//
//	 loop:
//	   ind = (Phi min nxt),
//	   if ind < max
//	     then goto enter_loop
//	     else goto exit_loop
//
//	   enter_loop:
//		do something
//	      nxt = inc + ind
//		goto loop
//
//	 exit_loop:
//
// TODO: handle 32 bit operations
func findIndVar(f *Func) []indVar {
	var iv []indVar
	sdom := f.Sdom()

for _, b := range f.Blocks {
		if b.Kind != BlockIf || len(b.Preds) != 2 {
			continue
		}

var ind *Value   // induction variable
		var init *Value  // starting value
		var limit *Value // ending value

// Check thet the control if it either ind </<= limit or limit </<= ind.
		// TODO: Handle 32-bit comparisons.
		// TODO: Handle unsigned comparisons?
		c := b.Controls[0]
		inclusive := false
		switch c.Op {
		case OpLeq64:
			inclusive = true
			fallthrough
		case OpLess64:
			ind, limit = c.Args[0], c.Args[1]
		default:
			continue
		}

// See if this is really an induction variable
		less := true
		init, inc, nxt := parseIndVar(ind)
		if init == nil {
			// We failed to parse the induction variable. Before punting, we want to check
			// whether the control op was written with the induction variable on the RHS
			// instead of the LHS. This happens for the downwards case, like:
			//     for i := len(n)-1; i >= 0; i--
			init, inc, nxt = parseIndVar(limit)
			if init == nil {
				// No recognied induction variable on either operand
				continue
			}

// Ok, the arguments were reversed. Swap them, and remember that we're
			// looking at a ind >/>= loop (so the induction must be decrementing).
			ind, limit = limit, ind
			less = false
		}

// Expect the increment to be a nonzero constant.
		if inc.Op != OpConst64 {
			continue
		}
		step := inc.AuxInt
		if step == 0 {
			continue
		}

// Increment sign must match comparison direction.
		// When incrementing, the termination comparison must be ind </<= limit.
		// When decrementing, the termination comparison must be ind >/>= limit.
		// See issue 26116.
		if step > 0 && !less {
			continue
		}
		if step < 0 && less {
			continue
		}

// Up to now we extracted the induction variable (ind),
		// the increment delta (inc), the temporary sum (nxt),
		// the initial value (init) and the limiting value (limit).
		//
		// We also know that ind has the form (Phi init nxt) where
		// nxt is (Add inc nxt) which means: 1) inc dominates nxt
		// and 2) there is a loop starting at inc and containing nxt.
		//
		// We need to prove that the induction variable is incremented
		// only when it's smaller than the limiting value.
		// Two conditions must happen listed below to accept ind
		// as an induction variable.

// First condition: loop entry has a single predecessor, which
		// is the header block.  This implies that b.Succs[0] is
		// reached iff ind < limit.
		if len(b.Succs[0].b.Preds) != 1 {
			// b.Succs[1] must exit the loop.
			continue
		}

// Second condition: b.Succs[0] dominates nxt so that
		// nxt is computed when inc < limit.
		if !sdom.IsAncestorEq(b.Succs[0].b, nxt.Block) {
			// inc+ind can only be reached through the branch that enters the loop.
			continue
		}

// Check for overflow/underflow. We need to make sure that inc never causes
		// the induction variable to wrap around.
		// We use a function wrapper here for easy return true / return false / keep going logic.
		// This function returns true if the increment will never overflow/underflow.
		ok := func() bool {
			if step > 0 {
				if limit.Op == OpConst64 {
					// Figure out the actual largest value.
					v := limit.AuxInt
					if !inclusive {
						if v == math.MinInt64 {
							return false // < minint is never satisfiable.
						}
						v--
					}
					if init.Op == OpConst64 {
						// Use stride to compute a better lower limit.
						if init.AuxInt > v {
							return false
						}
						v = addU(init.AuxInt, diff(v, init.AuxInt)/uint64(step)*uint64(step))
					}
					// It is ok if we can't overflow when incrementing from the largest value.
					return !addWillOverflow(v, step)
				}
				if step == 1 && !inclusive {
					// Can't overflow because maxint is never a possible value.
					return true
				}
				// If the limit is not a constant, check to see if it is a
				// negative offset from a known non-negative value.
				knn, k := findKNN(limit)
				if knn == nil || k < 0 {
					return false
				}
				// limit == (something nonnegative) - k. That subtraction can't underflow, so
				// we can trust it.
				if inclusive {
					// ind <= knn - k cannot overflow if step is at most k
					return step <= k
				}
				// ind < knn - k cannot overflow if step is at most k+1
				return step <= k+1 && k != math.MaxInt64
			} else { // step < 0
				if limit.Op == OpConst64 {
					// Figure out the actual smallest value.
					v := limit.AuxInt
					if !inclusive {
						if v == math.MaxInt64 {
							return false // > maxint is never satisfiable.
						}
						v++
					}
					if init.Op == OpConst64 {
						// Use stride to compute a better lower limit.
						if init.AuxInt < v {
							return false
						}
						v = subU(init.AuxInt, diff(init.AuxInt, v)/uint64(-step)*uint64(-step))
					}
					// It is ok if we can't underflow when decrementing from the smallest value.
					return !subWillUnderflow(v, -step)
				}
				if step == -1 && !inclusive {
					// Can't underflow because minint is never a possible value.
					return true
				}
			}
			return false

}

if ok() {
			flags := indVarFlags(0)
			var min, max *Value
			if step > 0 {
				min = init
				max = limit
				if inclusive {
					flags |= indVarMaxInc
				}
			} else {
				min = limit
				max = init
				flags |= indVarMaxInc
				if !inclusive {
					flags |= indVarMinExc
				}
				step = -step
			}
			if f.pass.debug >= 1 {
				printIndVar(b, ind, min, max, step, flags)
			}

iv = append(iv, indVar{
				ind:   ind,
				min:   min,
				max:   max,
				entry: b.Succs[0].b,
				flags: flags,
			})
			b.Logf("found induction variable %v (inc = %v, min = %v, max = %v)\n", ind, inc, min, max)
		}

// TODO: other unrolling idioms
		// for i := 0; i < KNN - KNN % k ; i += k
		// for i := 0; i < KNN&^(k-1) ; i += k // k a power of 2
		// for i := 0; i < KNN&(-k) ; i += k // k a power of 2
	}

return iv
}

// addWillOverflow reports whether x+y would result in a value more than maxint.
func addWillOverflow(x, y int64) bool {
	return x+y < x
}

// subWillUnderflow reports whether x-y would result in a value less than minint.
func subWillUnderflow(x, y int64) bool {
	return x-y > x
}

// diff returns x-y as a uint64. Requires x>=y.
func diff(x, y int64) uint64 {
	if x < y {
		base.Fatalf("diff %d - %d underflowed", x, y)
	}
	return uint64(x - y)
}

// addU returns x+y. Requires that x+y does not overflow an int64.
func addU(x int64, y uint64) int64 {
	if y >= 1<<63 {
		if x >= 0 {
			base.Fatalf("addU overflowed %d + %d", x, y)
		}
		x += 1<<63 - 1
		x += 1
		y -= 1 << 63
	}
	if addWillOverflow(x, int64(y)) {
		base.Fatalf("addU overflowed %d + %d", x, y)
	}
	return x + int64(y)
}

// subU returns x-y. Requires that x-y does not underflow an int64.
func subU(x int64, y uint64) int64 {
	if y >= 1<<63 {
		if x < 0 {
			base.Fatalf("subU underflowed %d - %d", x, y)
		}
		x -= 1<<63 - 1
		x -= 1
		y -= 1 << 63
	}
	if subWillUnderflow(x, int64(y)) {
		base.Fatalf("subU underflowed %d - %d", x, y)
	}
	return x - int64(y)
}

// if v is known to be x - c, where x is known to be nonnegative and c is a
// constant, return x, c. Otherwise return nil, 0.
func findKNN(v *Value) (*Value, int64) {
	var x, y *Value
	x = v
	switch v.Op {
	case OpSub64:
		x = v.Args[0]
		y = v.Args[1]

case OpAdd64:
		x = v.Args[0]
		y = v.Args[1]
		if x.Op == OpConst64 {
			x, y = y, x
		}
	}
	switch x.Op {
	case OpSliceLen, OpStringLen, OpSliceCap:
	default:
		return nil, 0
	}
	if y == nil {
		return x, 0
	}
	if y.Op != OpConst64 {
		return nil, 0
	}
	if v.Op == OpAdd64 {
		return x, -y.AuxInt
	}
	return x, y.AuxInt
}

func printIndVar(b *Block, i, min, max *Value, inc int64, flags indVarFlags) {
	mb1, mb2 := "[", "]"
	if flags&indVarMinExc != 0 {
		mb1 = "("
	}
	if flags&indVarMaxInc == 0 {
		mb2 = ")"
	}

mlim1, mlim2 := fmt.Sprint(min.AuxInt), fmt.Sprint(max.AuxInt)
	if !min.isGenericIntConst() {
		if b.Func.pass.debug >= 2 {
			mlim1 = fmt.Sprint(min)
		} else {
			mlim1 = "?"
		}
	}
	if !max.isGenericIntConst() {
		if b.Func.pass.debug >= 2 {
			mlim2 = fmt.Sprint(max)
		} else {
			mlim2 = "?"
		}
	}
	extra := ""
	if b.Func.pass.debug >= 2 {
		extra = fmt.Sprintf(" (%s)", i)
	}
	b.Func.Warnl(b.Pos, "Induction variable: limits %v%v,%v%v, increment %d%s", mb1, mlim1, mlim2, mb2, inc, extra)
}

X7ROOT File Manager

Editing: loopbce.go

Upload File

Create Folder