OXIESEC PANEL
- Current Dir:
/
/
opt
/
golang
/
1.22.0
/
src
/
cmd
/
compile
/
internal
/
ssa
Server IP: 191.96.63.230
Upload:
Create Dir:
Name
Size
Modified
Perms
📁
..
-
02/02/2024 06:09:55 PM
rwxr-xr-x
📄
README.md
8.14 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
TODO
950 bytes
02/02/2024 06:09:55 PM
rw-r--r--
📁
_gen
-
02/02/2024 06:09:55 PM
rwxr-xr-x
📄
addressingmodes.go
24.26 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
allocators.go
7.37 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
bench_test.go
835 bytes
02/02/2024 06:09:55 PM
rw-r--r--
📄
biasedsparsemap.go
2.67 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
block.go
11.03 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
branchelim.go
12.7 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
branchelim_test.go
5.21 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
cache.go
1.55 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
check.go
17.52 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
checkbce.go
956 bytes
02/02/2024 06:09:55 PM
rw-r--r--
📄
compile.go
18.66 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
config.go
12.95 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
copyelim.go
1.83 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
copyelim_test.go
1.29 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
critical.go
3.06 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
cse.go
9.63 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
cse_test.go
4.2 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
deadcode.go
9.25 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
deadcode_test.go
3.49 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
deadstore.go
10.42 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
deadstore_test.go
4.09 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
debug.go
56.4 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
debug_lines_test.go
8.44 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
debug_test.go
28.64 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
decompose.go
13.42 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
dom.go
7.35 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
dom_test.go
13.34 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
expand_calls.go
31.88 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
export_test.go
3.04 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
flagalloc.go
6.72 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
flags_amd64_test.s
533 bytes
02/02/2024 06:09:55 PM
rw-r--r--
📄
flags_arm64_test.s
699 bytes
02/02/2024 06:09:55 PM
rw-r--r--
📄
flags_test.go
2.47 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
fmahash_test.go
1.82 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
func.go
25.07 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
func_test.go
13.05 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
fuse.go
9.03 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
fuse_branchredirect.go
3.22 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
fuse_comparisons.go
4.04 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
fuse_test.go
7.37 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
generate.go
225 bytes
02/02/2024 06:09:55 PM
rw-r--r--
📄
html.go
34.85 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
id.go
576 bytes
02/02/2024 06:09:55 PM
rw-r--r--
📄
layout.go
4.97 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
lca.go
3.77 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
lca_test.go
1.65 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
likelyadjust.go
15.43 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
location.go
3.06 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
loopbce.go
11.81 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
loopreschedchecks.go
15.96 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
looprotate.go
2.68 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
lower.go
1.66 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
magic.go
15.77 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
magic_test.go
9.1 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
memcombine.go
18.44 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
nilcheck.go
11.3 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
nilcheck_test.go
12.33 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
numberlines.go
7.82 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
op.go
18.67 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
opGen.go
1.03 MB
02/02/2024 06:09:55 PM
rw-r--r--
📄
opt.go
309 bytes
02/02/2024 06:09:55 PM
rw-r--r--
📄
passbm_test.go
3.14 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
phielim.go
1.48 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
phiopt.go
8.08 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
poset.go
37.21 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
poset_test.go
18.14 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
print.go
3.86 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
prove.go
49.44 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
regalloc.go
87.22 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
regalloc_test.go
6.31 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
rewrite.go
60.26 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
rewrite386.go
262.37 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
rewrite386splitload.go
4.04 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
rewriteAMD64.go
713.19 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
rewriteAMD64latelower.go
2.58 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
rewriteAMD64splitload.go
21.4 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
rewriteARM.go
486.78 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
rewriteARM64.go
623.93 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
rewriteARM64latelower.go
6.88 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
rewriteCond_test.go
11.12 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
rewriteLOONG64.go
195.82 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
rewriteMIPS.go
176.61 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
rewriteMIPS64.go
211.6 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
rewritePPC64.go
371.03 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
rewritePPC64latelower.go
14.78 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
rewriteRISCV64.go
203.12 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
rewriteRISCV64latelower.go
5.08 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
rewriteS390X.go
395.13 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
rewriteWasm.go
108.58 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
rewrite_test.go
6.91 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
rewritedec.go
24.94 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
rewritedec64.go
65.29 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
rewritegeneric.go
796.35 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
sccp.go
17.56 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
sccp_test.go
3.57 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
schedule.go
16.42 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
schedule_test.go
5.57 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
shift_test.go
4.05 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
shortcircuit.go
12.63 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
shortcircuit_test.go
1.31 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
sizeof_test.go
855 bytes
02/02/2024 06:09:55 PM
rw-r--r--
📄
softfloat.go
1.99 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
sparsemap.go
1.9 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
sparsemappos.go
1.7 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
sparseset.go
1.54 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
sparsetree.go
8.05 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
stackalloc.go
12.56 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
stmtlines_test.go
3.46 KB
02/02/2024 06:09:55 PM
rw-r--r--
📁
testdata
-
02/02/2024 06:09:55 PM
rwxr-xr-x
📄
tighten.go
7.67 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
trim.go
4.25 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
tuple.go
1.97 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
value.go
16.67 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
writebarrier.go
23.5 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
writebarrier_test.go
1.75 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
xposmap.go
3.29 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
zcse.go
2.07 KB
02/02/2024 06:09:55 PM
rw-r--r--
📄
zeroextension_test.go
1.66 KB
02/02/2024 06:09:55 PM
rw-r--r--
Editing: loopbce.go
Close
// 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" "cmd/compile/internal/types" "fmt" ) type indVarFlags uint8 const ( indVarMinExc indVarFlags = 1 << iota // minimum value is exclusive (default: inclusive) indVarMaxInc // maximum value is inclusive (default: exclusive) indVarCountDown // if set the iteration starts at max and count towards min (default: min towards max) ) type indVar struct { ind *Value // induction variable nxt *Value // the incremented 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.Op == OpAdd32 || n.Op == OpAdd16 || n.Op == OpAdd8) && (n.Args[0] == ind || n.Args[1] == ind) { min, nxt = ind.Args[1], n } else if n := ind.Args[1]; (n.Op == OpAdd64 || n.Op == OpAdd32 || n.Op == OpAdd16 || n.Op == OpAdd8) && (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: 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 that the control if it either ind </<= limit or limit </<= ind. // TODO: Handle unsigned comparisons? c := b.Controls[0] inclusive := false switch c.Op { case OpLeq64, OpLeq32, OpLeq16, OpLeq8: inclusive = true fallthrough case OpLess64, OpLess32, OpLess16, OpLess8: 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 recognized induction variable on either operand continue } // Ok, the arguments were reversed. Swap them, and remember that we're // looking at an ind >/>= loop (so the induction must be decrementing). ind, limit = limit, ind less = false } if ind.Block != b { // TODO: Could be extended to include disjointed loop headers. // I don't think this is causing missed optimizations in real world code often. // See https://go.dev/issue/63955 continue } // Expect the increment to be a nonzero constant. if !inc.isGenericIntConst() { 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.isGenericIntConst() { // Figure out the actual largest value. v := limit.AuxInt if !inclusive { if v == minSignedValue(limit.Type) { return false // < minint is never satisfiable. } v-- } if init.isGenericIntConst() { // 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)) } if addWillOverflow(v, step) { return false } if inclusive && v != limit.AuxInt || !inclusive && v+1 != limit.AuxInt { // We know a better limit than the programmer did. Use our limit instead. limit = f.constVal(limit.Op, limit.Type, v, true) inclusive = true } return true } 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 != maxSignedValue(limit.Type) } else { // step < 0 if limit.Op == OpConst64 { // Figure out the actual smallest value. v := limit.AuxInt if !inclusive { if v == maxSignedValue(limit.Type) { return false // > maxint is never satisfiable. } v++ } if init.isGenericIntConst() { // 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)) } if subWillUnderflow(v, -step) { return false } if inclusive && v != limit.AuxInt || !inclusive && v-1 != limit.AuxInt { // We know a better limit than the programmer did. Use our limit instead. limit = f.constVal(limit.Op, limit.Type, v, true) inclusive = true } return true } 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 } flags |= indVarCountDown step = -step } if f.pass.debug >= 1 { printIndVar(b, ind, min, max, step, flags) } iv = append(iv, indVar{ ind: ind, nxt: nxt, 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, OpSub32, OpSub16, OpSub8: x = v.Args[0] y = v.Args[1] case OpAdd64, OpAdd32, OpAdd16, OpAdd8: x = v.Args[0] y = v.Args[1] if x.isGenericIntConst() { x, y = y, x } } switch x.Op { case OpSliceLen, OpStringLen, OpSliceCap: default: return nil, 0 } if y == nil { return x, 0 } if !y.isGenericIntConst() { return nil, 0 } if v.Op == OpAdd64 || v.Op == OpAdd32 || v.Op == OpAdd16 || v.Op == OpAdd8 { 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) } func minSignedValue(t *types.Type) int64 { return -1 << (t.Size()*8 - 1) } func maxSignedValue(t *types.Type) int64 { return 1<<((t.Size()*8)-1) - 1 }