sccp.go

     1  // Copyright 2023 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 ssacompile
     6  
     7  import (
     8  	"cmd/compile/internal/ssa"
     9  	blockpkg "cmd/compile/internal/ssa/block"
    10  	"cmd/compile/internal/ssa/ssaop"
    11  	"cmd/compile/internal/ssarewrite/rewritegeneric"
    12  )
    13  
    14  // ----------------------------------------------------------------------------
    15  // Sparse Conditional Constant Propagation
    16  //
    17  // Described in
    18  // Mark N. Wegman, F. Kenneth Zadeck: Constant Propagation with Conditional Branches.
    19  // TOPLAS 1991.
    20  //
    21  // This algorithm uses three level lattice for SSA value
    22  //
    23  //      Top        undefined
    24  //     / | \
    25  // .. 1  2  3 ..   constant
    26  //     \ | /
    27  //     Bottom      not constant
    28  //
    29  // It starts with optimistically assuming that all SSA values are initially Top
    30  // and then propagates constant facts only along reachable control flow paths.
    31  // Since some basic blocks are not visited yet, corresponding inputs of phi become
    32  // Top, we use the meet(phi) to compute its lattice.
    33  //
    34  // 	  Top ∩ any = any
    35  // 	  Bottom ∩ any = Bottom
    36  // 	  ConstantA ∩ ConstantA = ConstantA
    37  // 	  ConstantA ∩ ConstantB = Bottom
    38  //
    39  // Each lattice value is lowered most twice(Top to Constant, Constant to Bottom)
    40  // due to lattice depth, resulting in a fast convergence speed of the algorithm.
    41  // In this way, sccp can discover optimization opportunities that cannot be found
    42  // by just combining constant folding and constant propagation and dead code
    43  // elimination separately.
    44  
    45  // Three level lattice holds compile time knowledge about SSA value
    46  const (
    47  	top      int8 = iota // undefined
    48  	constant             // constant
    49  	bottom               // not a constant
    50  )
    51  
    52  type lattice struct {
    53  	tag int8       // lattice type
    54  	val *ssa.Value // constant value
    55  }
    56  
    57  type worklist struct {
    58  	f            *ssa.Func                   // the target function to be optimized out
    59  	edges        []ssa.Edge                  // propagate constant facts through edges
    60  	inUses       *ssa.SparseSet              // IDs already in uses, for duplicate check
    61  	uses         []*ssa.Value                // re-visiting set
    62  	visited      map[ssa.Edge]bool           // visited edges
    63  	latticeCells map[*ssa.Value]lattice      // constant lattices
    64  	defUse       map[*ssa.Value][]*ssa.Value // def-use chains for some values
    65  	defBlock     map[*ssa.Value][]*ssa.Block // use blocks of def
    66  	visitedBlock []bool                      // visited block
    67  }
    68  
    69  // sccp stands for sparse conditional constant propagation, it propagates constants
    70  // through CFG conditionally and applies constant folding, constant replacement and
    71  // dead code elimination all together.
    72  func sccp(f *ssa.Func) {
    73  	var t worklist
    74  	t.f = f
    75  	t.edges = make([]ssa.Edge, 0)
    76  	t.visited = make(map[ssa.Edge]bool)
    77  	t.edges = append(t.edges, ssa.Edge{B: f.Entry, I: 0})
    78  	t.defUse = make(map[*ssa.Value][]*ssa.Value)
    79  	t.defBlock = make(map[*ssa.Value][]*ssa.Block)
    80  	t.latticeCells = make(map[*ssa.Value]lattice)
    81  	t.visitedBlock = f.Cache.AllocBoolSlice(f.NumBlocks())
    82  	t.inUses = f.NewSparseSet(f.NumValues())
    83  	defer f.RetSparseSet(t.inUses)
    84  	defer f.Cache.FreeBoolSlice(t.visitedBlock)
    85  
    86  	// build it early since we rely heavily on the def-use chain later
    87  	t.buildDefUses()
    88  
    89  	// pick up either an edge or SSA value from worklist, process it
    90  	for {
    91  		if len(t.edges) > 0 {
    92  			edge := t.edges[0]
    93  			t.edges = t.edges[1:]
    94  			if _, exist := t.visited[edge]; !exist {
    95  				dest := edge.B
    96  				destVisited := t.visitedBlock[dest.ID]
    97  
    98  				// mark edge as visited
    99  				t.visited[edge] = true
   100  				t.visitedBlock[dest.ID] = true
   101  				for _, val := range dest.Values {
   102  					if val.Op == ssaop.OpPhi || !destVisited {
   103  						t.visitValue(val)
   104  					}
   105  				}
   106  				// propagates constants facts through CFG, taking condition test
   107  				// into account
   108  				if !destVisited {
   109  					t.propagate(dest)
   110  				}
   111  			}
   112  			continue
   113  		}
   114  		if len(t.uses) > 0 {
   115  			use := t.uses[0]
   116  			t.uses = t.uses[1:]
   117  			t.inUses.Remove(use.ID)
   118  			t.visitValue(use)
   119  			continue
   120  		}
   121  		break
   122  	}
   123  
   124  	// apply optimizations based on discovered constants
   125  	constCnt, rewireCnt := t.replaceConst()
   126  	if f.Pass.Debug > 0 {
   127  		if constCnt > 0 || rewireCnt > 0 {
   128  			f.Warnl(f.Entry.Pos, "Phase SCCP for %v : %v constants, %v dce", f.Name, constCnt, rewireCnt)
   129  		}
   130  	}
   131  }
   132  
   133  func equals(a, b lattice) bool {
   134  	if a == b {
   135  		// fast path
   136  		return true
   137  	}
   138  	if a.tag != b.tag {
   139  		return false
   140  	}
   141  	if a.tag == constant {
   142  		// The same content of const value may be different, we should
   143  		// compare with auxInt instead
   144  		v1 := a.val
   145  		v2 := b.val
   146  		if v1.Op == v2.Op && v1.AuxInt == v2.AuxInt {
   147  			return true
   148  		} else {
   149  			return false
   150  		}
   151  	}
   152  	return true
   153  }
   154  
   155  // possibleConst checks if Value can be folded to const. For those Values that can
   156  // never become constants(e.g. StaticCall), we don't make futile efforts.
   157  func possibleConst(val *ssa.Value) bool {
   158  	if isConst(val) {
   159  		return true
   160  	}
   161  	switch val.Op {
   162  	case ssaop.OpCopy:
   163  		return true
   164  	case ssaop.OpPhi:
   165  		return true
   166  	case
   167  		// negate
   168  		ssaop.OpNeg8, ssaop.OpNeg16, ssaop.OpNeg32, ssaop.OpNeg64, ssaop.OpNeg32F, ssaop.OpNeg64F,
   169  		ssaop.OpCom8, ssaop.OpCom16, ssaop.OpCom32, ssaop.OpCom64,
   170  		// math
   171  		ssaop.OpFloor, ssaop.OpCeil, ssaop.OpTrunc, ssaop.OpRoundToEven, ssaop.OpSqrt,
   172  		// conversion
   173  		ssaop.OpTrunc16to8, ssaop.OpTrunc32to8, ssaop.OpTrunc32to16, ssaop.OpTrunc64to8,
   174  		ssaop.OpTrunc64to16, ssaop.OpTrunc64to32, ssaop.OpCvt32to32F, ssaop.OpCvt32to64F,
   175  		ssaop.OpCvt64to32F, ssaop.OpCvt64to64F, ssaop.OpCvt32Fto32, ssaop.OpCvt32Fto64,
   176  		ssaop.OpCvt64Fto32, ssaop.OpCvt64Fto64, ssaop.OpCvt32Fto64F, ssaop.OpCvt64Fto32F,
   177  		ssaop.OpCvtBoolToUint8,
   178  		ssaop.OpZeroExt8to16, ssaop.OpZeroExt8to32, ssaop.OpZeroExt8to64, ssaop.OpZeroExt16to32,
   179  		ssaop.OpZeroExt16to64, ssaop.OpZeroExt32to64, ssaop.OpSignExt8to16, ssaop.OpSignExt8to32,
   180  		ssaop.OpSignExt8to64, ssaop.OpSignExt16to32, ssaop.OpSignExt16to64, ssaop.OpSignExt32to64,
   181  		// bit
   182  		ssaop.OpCtz8, ssaop.OpCtz16, ssaop.OpCtz32, ssaop.OpCtz64,
   183  		// mask
   184  		ssaop.OpSlicemask,
   185  		// safety check
   186  		ssaop.OpIsNonNil,
   187  		// not
   188  		ssaop.OpNot:
   189  		return true
   190  	case
   191  		// add
   192  		ssaop.OpAdd64, ssaop.OpAdd32, ssaop.OpAdd16, ssaop.OpAdd8,
   193  		ssaop.OpAdd32F, ssaop.OpAdd64F,
   194  		// sub
   195  		ssaop.OpSub64, ssaop.OpSub32, ssaop.OpSub16, ssaop.OpSub8,
   196  		ssaop.OpSub32F, ssaop.OpSub64F,
   197  		// mul
   198  		ssaop.OpMul64, ssaop.OpMul32, ssaop.OpMul16, ssaop.OpMul8,
   199  		ssaop.OpMul32F, ssaop.OpMul64F,
   200  		// div
   201  		ssaop.OpDiv32F, ssaop.OpDiv64F,
   202  		ssaop.OpDiv8, ssaop.OpDiv16, ssaop.OpDiv32, ssaop.OpDiv64,
   203  		ssaop.OpDiv8u, ssaop.OpDiv16u, ssaop.OpDiv32u, ssaop.OpDiv64u,
   204  		ssaop.OpMod8, ssaop.OpMod16, ssaop.OpMod32, ssaop.OpMod64,
   205  		ssaop.OpMod8u, ssaop.OpMod16u, ssaop.OpMod32u, ssaop.OpMod64u,
   206  		// compare
   207  		ssaop.OpEq64, ssaop.OpEq32, ssaop.OpEq16, ssaop.OpEq8,
   208  		ssaop.OpEq32F, ssaop.OpEq64F,
   209  		ssaop.OpLess64, ssaop.OpLess32, ssaop.OpLess16, ssaop.OpLess8,
   210  		ssaop.OpLess64U, ssaop.OpLess32U, ssaop.OpLess16U, ssaop.OpLess8U,
   211  		ssaop.OpLess32F, ssaop.OpLess64F,
   212  		ssaop.OpLeq64, ssaop.OpLeq32, ssaop.OpLeq16, ssaop.OpLeq8,
   213  		ssaop.OpLeq64U, ssaop.OpLeq32U, ssaop.OpLeq16U, ssaop.OpLeq8U,
   214  		ssaop.OpLeq32F, ssaop.OpLeq64F,
   215  		ssaop.OpEqB, ssaop.OpNeqB,
   216  		// shift
   217  		ssaop.OpLsh64x64, ssaop.OpRsh64x64, ssaop.OpRsh64Ux64, ssaop.OpLsh32x64,
   218  		ssaop.OpRsh32x64, ssaop.OpRsh32Ux64, ssaop.OpLsh16x64, ssaop.OpRsh16x64,
   219  		ssaop.OpRsh16Ux64, ssaop.OpLsh8x64, ssaop.OpRsh8x64, ssaop.OpRsh8Ux64,
   220  		// safety check
   221  		ssaop.OpIsInBounds, ssaop.OpIsSliceInBounds,
   222  		// bit
   223  		ssaop.OpAnd8, ssaop.OpAnd16, ssaop.OpAnd32, ssaop.OpAnd64,
   224  		ssaop.OpOr8, ssaop.OpOr16, ssaop.OpOr32, ssaop.OpOr64,
   225  		ssaop.OpXor8, ssaop.OpXor16, ssaop.OpXor32, ssaop.OpXor64:
   226  		return true
   227  	default:
   228  		return false
   229  	}
   230  }
   231  
   232  func (t *worklist) getLatticeCell(val *ssa.Value) lattice {
   233  	if !possibleConst(val) {
   234  		// they are always worst
   235  		return lattice{bottom, nil}
   236  	}
   237  	lt, exist := t.latticeCells[val]
   238  	if !exist {
   239  		return lattice{top, nil} // optimistically for un-visited value
   240  	}
   241  	return lt
   242  }
   243  
   244  func isConst(val *ssa.Value) bool {
   245  	switch val.Op {
   246  	case ssaop.OpConst64, ssaop.OpConst32, ssaop.OpConst16, ssaop.OpConst8,
   247  		ssaop.OpConstBool, ssaop.OpConst32F, ssaop.OpConst64F:
   248  		return true
   249  	default:
   250  		return false
   251  	}
   252  }
   253  
   254  // buildDefUses builds def-use chain for some values early, because once the
   255  // lattice of a value is changed, we need to update lattices of use. But we don't
   256  // need all uses of it, only uses that can become constants would be added into
   257  // re-visit worklist since no matter how many times they are revisited, uses which
   258  // can't become constants lattice remains unchanged, i.e. Bottom.
   259  func (t *worklist) buildDefUses() {
   260  	for _, block := range t.f.Blocks {
   261  		for _, val := range block.Values {
   262  			for _, arg := range val.Args {
   263  				// find its uses, only uses that can become constants take into account
   264  				if possibleConst(arg) && possibleConst(val) {
   265  					// Phi may refer to itself as uses, avoid duplicate visits
   266  					if arg == val {
   267  						continue
   268  					}
   269  					if _, exist := t.defUse[arg]; !exist {
   270  						t.defUse[arg] = make([]*ssa.Value, 0, arg.Uses)
   271  					}
   272  					t.defUse[arg] = append(t.defUse[arg], val)
   273  				}
   274  			}
   275  		}
   276  		for _, ctl := range block.ControlValues() {
   277  			// for control values that can become constants, find their use blocks
   278  			if possibleConst(ctl) {
   279  				t.defBlock[ctl] = append(t.defBlock[ctl], block)
   280  			}
   281  		}
   282  	}
   283  }
   284  
   285  // addUses finds all uses of value and appends them into work list for further process
   286  func (t *worklist) addUses(val *ssa.Value) {
   287  	for _, use := range t.defUse[val] {
   288  		// Provenly not a constant, ignore
   289  		useLt := t.getLatticeCell(use)
   290  		if useLt.tag == bottom {
   291  			continue
   292  		}
   293  		// Avoid duplicate visits
   294  		if !t.inUses.Contains(use.ID) {
   295  			t.inUses.Add(use.ID)
   296  			t.uses = append(t.uses, use)
   297  		}
   298  	}
   299  	for _, block := range t.defBlock[val] {
   300  		if t.visitedBlock[block.ID] {
   301  			t.propagate(block)
   302  		}
   303  	}
   304  }
   305  
   306  // meet meets all of phi arguments and computes result lattice
   307  func (t *worklist) meet(val *ssa.Value) lattice {
   308  	optimisticLt := lattice{top, nil}
   309  	for i := 0; i < len(val.Args); i++ {
   310  		edge := ssa.Edge{B: val.Block, I: i}
   311  		// If incoming edge for phi is not visited, assume top optimistically.
   312  		// According to rules of meet:
   313  		// 		Top ∩ any = any
   314  		// Top participates in meet() but does not affect the result, so here
   315  		// we will ignore Top and only take other lattices into consideration.
   316  		if _, exist := t.visited[edge]; exist {
   317  			lt := t.getLatticeCell(val.Args[i])
   318  			if lt.tag == constant {
   319  				if optimisticLt.tag == top {
   320  					optimisticLt = lt
   321  				} else {
   322  					if !equals(optimisticLt, lt) {
   323  						// ConstantA ∩ ConstantB = Bottom
   324  						return lattice{bottom, nil}
   325  					}
   326  				}
   327  			} else if lt.tag == bottom {
   328  				// Bottom ∩ any = Bottom
   329  				return lattice{bottom, nil}
   330  			} else {
   331  				// Top ∩ any = any
   332  			}
   333  		} else {
   334  			// Top ∩ any = any
   335  		}
   336  	}
   337  
   338  	// ConstantA ∩ ConstantA = ConstantA or Top ∩ any = any
   339  	return optimisticLt
   340  }
   341  
   342  func computeLattice(f *ssa.Func, val *ssa.Value, args ...*ssa.Value) lattice {
   343  	// In general, we need to perform constant evaluation based on constant args:
   344  	//
   345  	//  res := lattice{constant, nil}
   346  	// 	switch op {
   347  	// 	case OpAdd16:
   348  	//		res.val = newConst(argLt1.val.AuxInt16() + argLt2.val.AuxInt16())
   349  	// 	case OpAdd32:
   350  	// 		res.val = newConst(argLt1.val.AuxInt32() + argLt2.val.AuxInt32())
   351  	//	case OpDiv8:
   352  	//		if !isDivideByZero(argLt2.val.AuxInt8()) {
   353  	//			res.val = newConst(argLt1.val.AuxInt8() / argLt2.val.AuxInt8())
   354  	//		}
   355  	//  ...
   356  	// 	}
   357  	//
   358  	// However, this would create a huge switch for all opcodes that can be
   359  	// evaluated during compile time. Moreover, some operations can be evaluated
   360  	// only if its arguments satisfy additional conditions(e.g. divide by zero).
   361  	// It's fragile and error-prone. We did a trick by reusing the existing rules
   362  	// in generic rules for compile-time evaluation. But generic rules rewrite
   363  	// original value, this behavior is undesired, because the lattice of values
   364  	// may change multiple times, once it was rewritten, we lose the opportunity
   365  	// to change it permanently, which can lead to errors. For example, We cannot
   366  	// change its value immediately after visiting Phi, because some of its input
   367  	// edges may still not be visited at this moment.
   368  	constValue := f.NewValue(val.Op, val.Type, f.Entry, val.Pos)
   369  	constValue.AddArgs(args...)
   370  	matched := rewritegeneric.RewriteValue(constValue)
   371  	if matched {
   372  		if isConst(constValue) {
   373  			return lattice{constant, constValue}
   374  		}
   375  	}
   376  	// Either we can not match generic rules for given value or it does not
   377  	// satisfy additional constraints(e.g. divide by zero), in these cases, clean
   378  	// up temporary value immediately in case they are not dominated by their args.
   379  	constValue.Reset(ssaop.OpInvalid)
   380  	return lattice{bottom, nil}
   381  }
   382  
   383  func (t *worklist) visitValue(val *ssa.Value) {
   384  	// Impossible to be a constant, fast fail
   385  	if !possibleConst(val) {
   386  		return
   387  	}
   388  
   389  	// Provenly not a constant, fast fail
   390  	oldLt := t.getLatticeCell(val)
   391  	if oldLt.tag == bottom {
   392  		return
   393  	}
   394  
   395  	// Re-visit all uses of value if its lattice is changed
   396  	defer func() {
   397  		newLt := t.getLatticeCell(val)
   398  		if !equals(newLt, oldLt) {
   399  			if oldLt.tag > newLt.tag {
   400  				t.f.Fatalf("Must lower lattice\n")
   401  			}
   402  			t.addUses(val)
   403  		}
   404  	}()
   405  
   406  	switch val.Op {
   407  	// they are constant values, aren't they?
   408  	case ssaop.OpConst64, ssaop.OpConst32, ssaop.OpConst16, ssaop.OpConst8,
   409  		ssaop.OpConstBool, ssaop.OpConst32F, ssaop.OpConst64F: //TODO: support ConstNil ConstString etc
   410  		t.latticeCells[val] = lattice{constant, val}
   411  	// lattice value of copy(x) actually means lattice value of (x)
   412  	case ssaop.OpCopy:
   413  		t.latticeCells[val] = t.getLatticeCell(val.Args[0])
   414  	// phi should be processed specially
   415  	case ssaop.OpPhi:
   416  		t.latticeCells[val] = t.meet(val)
   417  	// fold 1-input operations:
   418  	case
   419  		// negate
   420  		ssaop.OpNeg8, ssaop.OpNeg16, ssaop.OpNeg32, ssaop.OpNeg64, ssaop.OpNeg32F, ssaop.OpNeg64F,
   421  		ssaop.OpCom8, ssaop.OpCom16, ssaop.OpCom32, ssaop.OpCom64,
   422  		// math
   423  		ssaop.OpFloor, ssaop.OpCeil, ssaop.OpTrunc, ssaop.OpRoundToEven, ssaop.OpSqrt,
   424  		// conversion
   425  		ssaop.OpTrunc16to8, ssaop.OpTrunc32to8, ssaop.OpTrunc32to16, ssaop.OpTrunc64to8,
   426  		ssaop.OpTrunc64to16, ssaop.OpTrunc64to32, ssaop.OpCvt32to32F, ssaop.OpCvt32to64F,
   427  		ssaop.OpCvt64to32F, ssaop.OpCvt64to64F, ssaop.OpCvt32Fto32, ssaop.OpCvt32Fto64,
   428  		ssaop.OpCvt64Fto32, ssaop.OpCvt64Fto64, ssaop.OpCvt32Fto64F, ssaop.OpCvt64Fto32F,
   429  		ssaop.OpCvtBoolToUint8,
   430  		ssaop.OpZeroExt8to16, ssaop.OpZeroExt8to32, ssaop.OpZeroExt8to64, ssaop.OpZeroExt16to32,
   431  		ssaop.OpZeroExt16to64, ssaop.OpZeroExt32to64, ssaop.OpSignExt8to16, ssaop.OpSignExt8to32,
   432  		ssaop.OpSignExt8to64, ssaop.OpSignExt16to32, ssaop.OpSignExt16to64, ssaop.OpSignExt32to64,
   433  		// bit
   434  		ssaop.OpCtz8, ssaop.OpCtz16, ssaop.OpCtz32, ssaop.OpCtz64,
   435  		// mask
   436  		ssaop.OpSlicemask,
   437  		// safety check
   438  		ssaop.OpIsNonNil,
   439  		// not
   440  		ssaop.OpNot:
   441  		lt1 := t.getLatticeCell(val.Args[0])
   442  
   443  		if lt1.tag == constant {
   444  			// here we take a shortcut by reusing generic rules to fold constants
   445  			t.latticeCells[val] = computeLattice(t.f, val, lt1.val)
   446  		} else {
   447  			t.latticeCells[val] = lattice{lt1.tag, nil}
   448  		}
   449  	// fold 2-input operations
   450  	case
   451  		// add
   452  		ssaop.OpAdd64, ssaop.OpAdd32, ssaop.OpAdd16, ssaop.OpAdd8,
   453  		ssaop.OpAdd32F, ssaop.OpAdd64F,
   454  		// sub
   455  		ssaop.OpSub64, ssaop.OpSub32, ssaop.OpSub16, ssaop.OpSub8,
   456  		ssaop.OpSub32F, ssaop.OpSub64F,
   457  		// mul
   458  		ssaop.OpMul64, ssaop.OpMul32, ssaop.OpMul16, ssaop.OpMul8,
   459  		ssaop.OpMul32F, ssaop.OpMul64F,
   460  		// div
   461  		ssaop.OpDiv32F, ssaop.OpDiv64F,
   462  		ssaop.OpDiv8, ssaop.OpDiv16, ssaop.OpDiv32, ssaop.OpDiv64,
   463  		ssaop.OpDiv8u, ssaop.OpDiv16u, ssaop.OpDiv32u, ssaop.OpDiv64u, //TODO: support div128u
   464  		// mod
   465  		ssaop.OpMod8, ssaop.OpMod16, ssaop.OpMod32, ssaop.OpMod64,
   466  		ssaop.OpMod8u, ssaop.OpMod16u, ssaop.OpMod32u, ssaop.OpMod64u,
   467  		// compare
   468  		ssaop.OpEq64, ssaop.OpEq32, ssaop.OpEq16, ssaop.OpEq8,
   469  		ssaop.OpEq32F, ssaop.OpEq64F,
   470  		ssaop.OpLess64, ssaop.OpLess32, ssaop.OpLess16, ssaop.OpLess8,
   471  		ssaop.OpLess64U, ssaop.OpLess32U, ssaop.OpLess16U, ssaop.OpLess8U,
   472  		ssaop.OpLess32F, ssaop.OpLess64F,
   473  		ssaop.OpLeq64, ssaop.OpLeq32, ssaop.OpLeq16, ssaop.OpLeq8,
   474  		ssaop.OpLeq64U, ssaop.OpLeq32U, ssaop.OpLeq16U, ssaop.OpLeq8U,
   475  		ssaop.OpLeq32F, ssaop.OpLeq64F,
   476  		ssaop.OpEqB, ssaop.OpNeqB,
   477  		// shift
   478  		ssaop.OpLsh64x64, ssaop.OpRsh64x64, ssaop.OpRsh64Ux64, ssaop.OpLsh32x64,
   479  		ssaop.OpRsh32x64, ssaop.OpRsh32Ux64, ssaop.OpLsh16x64, ssaop.OpRsh16x64,
   480  		ssaop.OpRsh16Ux64, ssaop.OpLsh8x64, ssaop.OpRsh8x64, ssaop.OpRsh8Ux64,
   481  		// safety check
   482  		ssaop.OpIsInBounds, ssaop.OpIsSliceInBounds,
   483  		// bit
   484  		ssaop.OpAnd8, ssaop.OpAnd16, ssaop.OpAnd32, ssaop.OpAnd64,
   485  		ssaop.OpOr8, ssaop.OpOr16, ssaop.OpOr32, ssaop.OpOr64,
   486  		ssaop.OpXor8, ssaop.OpXor16, ssaop.OpXor32, ssaop.OpXor64:
   487  		lt1 := t.getLatticeCell(val.Args[0])
   488  		lt2 := t.getLatticeCell(val.Args[1])
   489  
   490  		if lt1.tag == constant && lt2.tag == constant {
   491  			// here we take a shortcut by reusing generic rules to fold constants
   492  			t.latticeCells[val] = computeLattice(t.f, val, lt1.val, lt2.val)
   493  		} else {
   494  			if lt1.tag == bottom || lt2.tag == bottom {
   495  				t.latticeCells[val] = lattice{bottom, nil}
   496  			} else {
   497  				t.latticeCells[val] = lattice{top, nil}
   498  			}
   499  		}
   500  	default:
   501  		// Any other type of value cannot be a constant, they are always worst(Bottom)
   502  	}
   503  }
   504  
   505  // propagate propagates constants facts through CFG. If the block has single successor,
   506  // add the successor anyway. If the block has multiple successors, only add the
   507  // branch destination corresponding to lattice value of condition value.
   508  func (t *worklist) propagate(block *ssa.Block) {
   509  	switch block.Kind {
   510  	case blockpkg.BlockExit, blockpkg.BlockRet, blockpkg.BlockRetJmp, blockpkg.BlockInvalid:
   511  		// control flow ends, do nothing then
   512  		break
   513  	case blockpkg.BlockDefer:
   514  		// we know nothing about control flow, add all branch destinations
   515  		t.edges = append(t.edges, block.Succs...)
   516  	case blockpkg.BlockFirst:
   517  		fallthrough // always takes the first branch
   518  	case blockpkg.BlockPlain:
   519  		t.edges = append(t.edges, block.Succs[0])
   520  	case blockpkg.BlockIf, blockpkg.BlockJumpTable:
   521  		cond := block.ControlValues()[0]
   522  		condLattice := t.getLatticeCell(cond)
   523  		if condLattice.tag == bottom {
   524  			// we know nothing about control flow, add all branch destinations
   525  			t.edges = append(t.edges, block.Succs...)
   526  		} else if condLattice.tag == constant {
   527  			// add branchIdx destinations depends on its condition
   528  			var branchIdx int64
   529  			if block.Kind == blockpkg.BlockIf {
   530  				branchIdx = 1 - condLattice.val.AuxInt
   531  			} else {
   532  				branchIdx = condLattice.val.AuxInt
   533  				if branchIdx < 0 || branchIdx >= int64(len(block.Succs)) {
   534  					// unreachable code, do nothing then
   535  					break
   536  				}
   537  			}
   538  			t.edges = append(t.edges, block.Succs[branchIdx])
   539  		} else {
   540  			// condition value is not visited yet, don't propagate it now
   541  		}
   542  	default:
   543  		t.f.Fatalf("All kind of block should be processed above.")
   544  	}
   545  }
   546  
   547  // rewireSuccessor rewires corresponding successors according to constant value
   548  // discovered by previous analysis. As the result, some successors become unreachable
   549  // and thus can be removed in further deadcode phase
   550  func rewireSuccessor(block *ssa.Block, constVal *ssa.Value) bool {
   551  	switch block.Kind {
   552  	case blockpkg.BlockIf:
   553  		block.RemoveEdge(int(constVal.AuxInt))
   554  		block.Kind = blockpkg.BlockPlain
   555  		block.Likely = ssa.BranchUnknown
   556  		block.ResetControls()
   557  		return true
   558  	case blockpkg.BlockJumpTable:
   559  		// Remove everything but the known taken branch.
   560  		idx := int(constVal.AuxInt)
   561  		if idx < 0 || idx >= len(block.Succs) {
   562  			// This can only happen in unreachable code,
   563  			// as an invariant of jump tables is that their
   564  			// input index is in range.
   565  			// See issue 64826.
   566  			return false
   567  		}
   568  		block.SwapSuccessorsByIdx(0, idx)
   569  		for len(block.Succs) > 1 {
   570  			block.RemoveEdge(1)
   571  		}
   572  		block.Kind = blockpkg.BlockPlain
   573  		block.Likely = ssa.BranchUnknown
   574  		block.ResetControls()
   575  		return true
   576  	default:
   577  		return false
   578  	}
   579  }
   580  
   581  // replaceConst will replace non-constant values that have been proven by sccp
   582  // to be constants.
   583  func (t *worklist) replaceConst() (int, int) {
   584  	constCnt, rewireCnt := 0, 0
   585  	for val, lt := range t.latticeCells {
   586  		if lt.tag == constant {
   587  			if !isConst(val) {
   588  				if t.f.Pass.Debug > 0 {
   589  					t.f.Warnl(val.Pos, "Replace %v with %v", val.LongString(), lt.val.LongString())
   590  				}
   591  				val.Reset(lt.val.Op)
   592  				val.AuxInt = lt.val.AuxInt
   593  				constCnt++
   594  			}
   595  			// If const value controls this block, rewires successors according to its value
   596  			ctrlBlock := t.defBlock[val]
   597  			for _, block := range ctrlBlock {
   598  				if rewireSuccessor(block, lt.val) {
   599  					rewireCnt++
   600  					if t.f.Pass.Debug > 0 {
   601  						t.f.Warnl(block.Pos, "Rewire %v %v successors", block.Kind, block)
   602  					}
   603  				}
   604  			}
   605  		}
   606  	}
   607  	return constCnt, rewireCnt
   608  }
   609
View as plain text