compile.go

Documentation: cmd/compile/internal/ssa

     1  // Copyright 2015 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 (
     8  	"bytes"
     9  	"cmd/internal/objabi"
    10  	"cmd/internal/src"
    11  	"fmt"
    12  	"hash/crc32"
    13  	"log"
    14  	"math/rand"
    15  	"os"
    16  	"regexp"
    17  	"runtime"
    18  	"sort"
    19  	"strings"
    20  	"time"
    21  )
    22  
    23  // Compile is the main entry point for this package.
    24  // Compile modifies f so that on return:
    25  //   · all Values in f map to 0 or 1 assembly instructions of the target architecture
    26  //   · the order of f.Blocks is the order to emit the Blocks
    27  //   · the order of b.Values is the order to emit the Values in each Block
    28  //   · f has a non-nil regAlloc field
    29  func Compile(f *Func) {
    30  	// TODO: debugging - set flags to control verbosity of compiler,
    31  	// which phases to dump IR before/after, etc.
    32  	if f.Log() {
    33  		f.Logf("compiling %s\n", f.Name)
    34  	}
    35  
    36  	var rnd *rand.Rand
    37  	if checkEnabled {
    38  		seed := int64(crc32.ChecksumIEEE(([]byte)(f.Name))) ^ int64(checkRandSeed)
    39  		rnd = rand.New(rand.NewSource(seed))
    40  	}
    41  
    42  	// hook to print function & phase if panic happens
    43  	phaseName := "init"
    44  	defer func() {
    45  		if phaseName != "" {
    46  			err := recover()
    47  			stack := make([]byte, 16384)
    48  			n := runtime.Stack(stack, false)
    49  			stack = stack[:n]
    50  			if f.HTMLWriter != nil {
    51  				f.HTMLWriter.flushPhases()
    52  			}
    53  			f.Fatalf("panic during %s while compiling %s:\n\n%v\n\n%s\n", phaseName, f.Name, err, stack)
    54  		}
    55  	}()
    56  
    57  	// Run all the passes
    58  	if f.Log() {
    59  		printFunc(f)
    60  	}
    61  	f.HTMLWriter.WritePhase("start", "start")
    62  	if BuildDump != "" && BuildDump == f.Name {
    63  		f.dumpFile("build")
    64  	}
    65  	if checkEnabled {
    66  		checkFunc(f)
    67  	}
    68  	const logMemStats = false
    69  	for _, p := range passes {
    70  		if !f.Config.optimize && !p.required || p.disabled {
    71  			continue
    72  		}
    73  		f.pass = &p
    74  		phaseName = p.name
    75  		if f.Log() {
    76  			f.Logf("  pass %s begin\n", p.name)
    77  		}
    78  		// TODO: capture logging during this pass, add it to the HTML
    79  		var mStart runtime.MemStats
    80  		if logMemStats || p.mem {
    81  			runtime.ReadMemStats(&mStart)
    82  		}
    83  
    84  		if checkEnabled && !f.scheduled {
    85  			// Test that we don't depend on the value order, by randomizing
    86  			// the order of values in each block. See issue 18169.
    87  			for _, b := range f.Blocks {
    88  				for i := 0; i < len(b.Values)-1; i++ {
    89  					j := i + rnd.Intn(len(b.Values)-i)
    90  					b.Values[i], b.Values[j] = b.Values[j], b.Values[i]
    91  				}
    92  			}
    93  		}
    94  
    95  		tStart := time.Now()
    96  		p.fn(f)
    97  		tEnd := time.Now()
    98  
    99  		// Need something less crude than "Log the whole intermediate result".
   100  		if f.Log() || f.HTMLWriter != nil {
   101  			time := tEnd.Sub(tStart).Nanoseconds()
   102  			var stats string
   103  			if logMemStats {
   104  				var mEnd runtime.MemStats
   105  				runtime.ReadMemStats(&mEnd)
   106  				nBytes := mEnd.TotalAlloc - mStart.TotalAlloc
   107  				nAllocs := mEnd.Mallocs - mStart.Mallocs
   108  				stats = fmt.Sprintf("[%d ns %d allocs %d bytes]", time, nAllocs, nBytes)
   109  			} else {
   110  				stats = fmt.Sprintf("[%d ns]", time)
   111  			}
   112  
   113  			if f.Log() {
   114  				f.Logf("  pass %s end %s\n", p.name, stats)
   115  				printFunc(f)
   116  			}
   117  			f.HTMLWriter.WritePhase(phaseName, fmt.Sprintf("%s <span class=\"stats\">%s</span>", phaseName, stats))
   118  		}
   119  		if p.time || p.mem {
   120  			// Surround timing information w/ enough context to allow comparisons.
   121  			time := tEnd.Sub(tStart).Nanoseconds()
   122  			if p.time {
   123  				f.LogStat("TIME(ns)", time)
   124  			}
   125  			if p.mem {
   126  				var mEnd runtime.MemStats
   127  				runtime.ReadMemStats(&mEnd)
   128  				nBytes := mEnd.TotalAlloc - mStart.TotalAlloc
   129  				nAllocs := mEnd.Mallocs - mStart.Mallocs
   130  				f.LogStat("TIME(ns):BYTES:ALLOCS", time, nBytes, nAllocs)
   131  			}
   132  		}
   133  		if p.dump != nil && p.dump[f.Name] {
   134  			// Dump function to appropriately named file
   135  			f.dumpFile(phaseName)
   136  		}
   137  		if checkEnabled {
   138  			checkFunc(f)
   139  		}
   140  	}
   141  
   142  	if f.HTMLWriter != nil {
   143  		// Ensure we write any pending phases to the html
   144  		f.HTMLWriter.flushPhases()
   145  	}
   146  
   147  	if f.ruleMatches != nil {
   148  		var keys []string
   149  		for key := range f.ruleMatches {
   150  			keys = append(keys, key)
   151  		}
   152  		sort.Strings(keys)
   153  		buf := new(bytes.Buffer)
   154  		fmt.Fprintf(buf, "%s: ", f.Name)
   155  		for _, key := range keys {
   156  			fmt.Fprintf(buf, "%s=%d ", key, f.ruleMatches[key])
   157  		}
   158  		fmt.Fprint(buf, "\n")
   159  		fmt.Print(buf.String())
   160  	}
   161  
   162  	// Squash error printing defer
   163  	phaseName = ""
   164  }
   165  
   166  // dumpFile creates a file from the phase name and function name
   167  // Dumping is done to files to avoid buffering huge strings before
   168  // output.
   169  func (f *Func) dumpFile(phaseName string) {
   170  	f.dumpFileSeq++
   171  	fname := fmt.Sprintf("%s_%02d__%s.dump", f.Name, int(f.dumpFileSeq), phaseName)
   172  	fname = strings.Replace(fname, " ", "_", -1)
   173  	fname = strings.Replace(fname, "/", "_", -1)
   174  	fname = strings.Replace(fname, ":", "_", -1)
   175  
   176  	fi, err := os.Create(fname)
   177  	if err != nil {
   178  		f.Warnl(src.NoXPos, "Unable to create after-phase dump file %s", fname)
   179  		return
   180  	}
   181  
   182  	p := stringFuncPrinter{w: fi}
   183  	fprintFunc(p, f)
   184  	fi.Close()
   185  }
   186  
   187  type pass struct {
   188  	name     string
   189  	fn       func(*Func)
   190  	required bool
   191  	disabled bool
   192  	time     bool            // report time to run pass
   193  	mem      bool            // report mem stats to run pass
   194  	stats    int             // pass reports own "stats" (e.g., branches removed)
   195  	debug    int             // pass performs some debugging. =1 should be in error-testing-friendly Warnl format.
   196  	test     int             // pass-specific ad-hoc option, perhaps useful in development
   197  	dump     map[string]bool // dump if function name matches
   198  }
   199  
   200  func (p *pass) addDump(s string) {
   201  	if p.dump == nil {
   202  		p.dump = make(map[string]bool)
   203  	}
   204  	p.dump[s] = true
   205  }
   206  
   207  func (p *pass) String() string {
   208  	if p == nil {
   209  		return "nil pass"
   210  	}
   211  	return p.name
   212  }
   213  
   214  // Run consistency checker between each phase
   215  var (
   216  	checkEnabled  = false
   217  	checkRandSeed = 0
   218  )
   219  
   220  // Debug output
   221  var IntrinsicsDebug int
   222  var IntrinsicsDisable bool
   223  
   224  var BuildDebug int
   225  var BuildTest int
   226  var BuildStats int
   227  var BuildDump string // name of function to dump after initial build of ssa
   228  
   229  // PhaseOption sets the specified flag in the specified ssa phase,
   230  // returning empty string if this was successful or a string explaining
   231  // the error if it was not.
   232  // A version of the phase name with "_" replaced by " " is also checked for a match.
   233  // If the phase name begins a '~' then the rest of the underscores-replaced-with-blanks
   234  // version is used as a regular expression to match the phase name(s).
   235  //
   236  // Special cases that have turned out to be useful:
   237  //  ssa/check/on enables checking after each phase
   238  //  ssa/all/time enables time reporting for all phases
   239  //
   240  // See gc/lex.go for dissection of the option string.
   241  // Example uses:
   242  //
   243  // GO_GCFLAGS=-d=ssa/generic_cse/time,ssa/generic_cse/stats,ssa/generic_cse/debug=3 ./make.bash
   244  //
   245  // BOOT_GO_GCFLAGS=-d='ssa/~^.*scc$/off' GO_GCFLAGS='-d=ssa/~^.*scc$/off' ./make.bash
   246  //
   247  func PhaseOption(phase, flag string, val int, valString string) string {
   248  	switch phase {
   249  	case "", "help":
   250  		lastcr := 0
   251  		phasenames := "    check, all, build, intrinsics"
   252  		for _, p := range passes {
   253  			pn := strings.Replace(p.name, " ", "_", -1)
   254  			if len(pn)+len(phasenames)-lastcr > 70 {
   255  				phasenames += "\n    "
   256  				lastcr = len(phasenames)
   257  				phasenames += pn
   258  			} else {
   259  				phasenames += ", " + pn
   260  			}
   261  		}
   262  		return `PhaseOptions usage:
   263  
   264      go tool compile -d=ssa/<phase>/<flag>[=<value>|<function_name>]
   265  
   266  where:
   267  
   268  - <phase> is one of:
   269  ` + phasenames + `
   270  
   271  - <flag> is one of:
   272      on, off, debug, mem, time, test, stats, dump, seed
   273  
   274  - <value> defaults to 1
   275  
   276  - <function_name> is required for the "dump" flag, and specifies the
   277    name of function to dump after <phase>
   278  
   279  Phase "all" supports flags "time", "mem", and "dump".
   280  Phase "intrinsics" supports flags "on", "off", and "debug".
   281  
   282  If the "dump" flag is specified, the output is written on a file named
   283  <phase>__<function_name>_<seq>.dump; otherwise it is directed to stdout.
   284  
   285  Examples:
   286  
   287      -d=ssa/check/on
   288  enables checking after each phase
   289  
   290  	-d=ssa/check/seed=1234
   291  enables checking after each phase, using 1234 to seed the PRNG
   292  used for value order randomization
   293  
   294      -d=ssa/all/time
   295  enables time reporting for all phases
   296  
   297      -d=ssa/prove/debug=2
   298  sets debugging level to 2 in the prove pass
   299  
   300  Multiple flags can be passed at once, by separating them with
   301  commas. For example:
   302  
   303      -d=ssa/check/on,ssa/all/time
   304  `
   305  	}
   306  
   307  	if phase == "check" {
   308  		switch flag {
   309  		case "on":
   310  			checkEnabled = val != 0
   311  			debugPoset = checkEnabled // also turn on advanced self-checking in prove's datastructure
   312  			return ""
   313  		case "off":
   314  			checkEnabled = val == 0
   315  			debugPoset = checkEnabled
   316  			return ""
   317  		case "seed":
   318  			checkEnabled = true
   319  			checkRandSeed = val
   320  			debugPoset = checkEnabled
   321  			return ""
   322  		}
   323  	}
   324  
   325  	alltime := false
   326  	allmem := false
   327  	alldump := false
   328  	if phase == "all" {
   329  		switch flag {
   330  		case "time":
   331  			alltime = val != 0
   332  		case "mem":
   333  			allmem = val != 0
   334  		case "dump":
   335  			alldump = val != 0
   336  			if alldump {
   337  				BuildDump = valString
   338  			}
   339  		default:
   340  			return fmt.Sprintf("Did not find a flag matching %s in -d=ssa/%s debug option", flag, phase)
   341  		}
   342  	}
   343  
   344  	if phase == "intrinsics" {
   345  		switch flag {
   346  		case "on":
   347  			IntrinsicsDisable = val == 0
   348  		case "off":
   349  			IntrinsicsDisable = val != 0
   350  		case "debug":
   351  			IntrinsicsDebug = val
   352  		default:
   353  			return fmt.Sprintf("Did not find a flag matching %s in -d=ssa/%s debug option", flag, phase)
   354  		}
   355  		return ""
   356  	}
   357  	if phase == "build" {
   358  		switch flag {
   359  		case "debug":
   360  			BuildDebug = val
   361  		case "test":
   362  			BuildTest = val
   363  		case "stats":
   364  			BuildStats = val
   365  		case "dump":
   366  			BuildDump = valString
   367  		default:
   368  			return fmt.Sprintf("Did not find a flag matching %s in -d=ssa/%s debug option", flag, phase)
   369  		}
   370  		return ""
   371  	}
   372  
   373  	underphase := strings.Replace(phase, "_", " ", -1)
   374  	var re *regexp.Regexp
   375  	if phase[0] == '~' {
   376  		r, ok := regexp.Compile(underphase[1:])
   377  		if ok != nil {
   378  			return fmt.Sprintf("Error %s in regexp for phase %s, flag %s", ok.Error(), phase, flag)
   379  		}
   380  		re = r
   381  	}
   382  	matchedOne := false
   383  	for i, p := range passes {
   384  		if phase == "all" {
   385  			p.time = alltime
   386  			p.mem = allmem
   387  			if alldump {
   388  				p.addDump(valString)
   389  			}
   390  			passes[i] = p
   391  			matchedOne = true
   392  		} else if p.name == phase || p.name == underphase || re != nil && re.MatchString(p.name) {
   393  			switch flag {
   394  			case "on":
   395  				p.disabled = val == 0
   396  			case "off":
   397  				p.disabled = val != 0
   398  			case "time":
   399  				p.time = val != 0
   400  			case "mem":
   401  				p.mem = val != 0
   402  			case "debug":
   403  				p.debug = val
   404  			case "stats":
   405  				p.stats = val
   406  			case "test":
   407  				p.test = val
   408  			case "dump":
   409  				p.addDump(valString)
   410  			default:
   411  				return fmt.Sprintf("Did not find a flag matching %s in -d=ssa/%s debug option", flag, phase)
   412  			}
   413  			if p.disabled && p.required {
   414  				return fmt.Sprintf("Cannot disable required SSA phase %s using -d=ssa/%s debug option", phase, phase)
   415  			}
   416  			passes[i] = p
   417  			matchedOne = true
   418  		}
   419  	}
   420  	if matchedOne {
   421  		return ""
   422  	}
   423  	return fmt.Sprintf("Did not find a phase matching %s in -d=ssa/... debug option", phase)
   424  }
   425  
   426  // list of passes for the compiler
   427  var passes = [...]pass{
   428  	// TODO: combine phielim and copyelim into a single pass?
   429  	{name: "number lines", fn: numberLines, required: true},
   430  	{name: "early phielim", fn: phielim},
   431  	{name: "early copyelim", fn: copyelim},
   432  	{name: "early deadcode", fn: deadcode}, // remove generated dead code to avoid doing pointless work during opt
   433  	{name: "short circuit", fn: shortcircuit},
   434  	{name: "decompose args", fn: decomposeArgs, required: !go116lateCallExpansion, disabled: go116lateCallExpansion}, // handled by late call lowering
   435  	{name: "decompose user", fn: decomposeUser, required: true},
   436  	{name: "pre-opt deadcode", fn: deadcode},
   437  	{name: "opt", fn: opt, required: true},               // NB: some generic rules know the name of the opt pass. TODO: split required rules and optimizing rules
   438  	{name: "zero arg cse", fn: zcse, required: true},     // required to merge OpSB values
   439  	{name: "opt deadcode", fn: deadcode, required: true}, // remove any blocks orphaned during opt
   440  	{name: "generic cse", fn: cse},
   441  	{name: "phiopt", fn: phiopt},
   442  	{name: "gcse deadcode", fn: deadcode, required: true}, // clean out after cse and phiopt
   443  	{name: "nilcheckelim", fn: nilcheckelim},
   444  	{name: "prove", fn: prove},
   445  	{name: "early fuse", fn: fuseEarly},
   446  	{name: "decompose builtin", fn: decomposeBuiltIn, required: true},
   447  	{name: "expand calls", fn: expandCalls, required: true},
   448  	{name: "softfloat", fn: softfloat, required: true},
   449  	{name: "late opt", fn: opt, required: true}, // TODO: split required rules and optimizing rules
   450  	{name: "dead auto elim", fn: elimDeadAutosGeneric},
   451  	{name: "generic deadcode", fn: deadcode, required: true}, // remove dead stores, which otherwise mess up store chain
   452  	{name: "check bce", fn: checkbce},
   453  	{name: "branchelim", fn: branchelim},
   454  	{name: "late fuse", fn: fuseLate},
   455  	{name: "dse", fn: dse},
   456  	{name: "writebarrier", fn: writebarrier, required: true}, // expand write barrier ops
   457  	{name: "insert resched checks", fn: insertLoopReschedChecks,
   458  		disabled: objabi.Preemptibleloops_enabled == 0}, // insert resched checks in loops.
   459  	{name: "lower", fn: lower, required: true},
   460  	{name: "addressing modes", fn: addressingModes, required: false},
   461  	{name: "lowered deadcode for cse", fn: deadcode}, // deadcode immediately before CSE avoids CSE making dead values live again
   462  	{name: "lowered cse", fn: cse},
   463  	{name: "elim unread autos", fn: elimUnreadAutos},
   464  	{name: "tighten tuple selectors", fn: tightenTupleSelectors, required: true},
   465  	{name: "lowered deadcode", fn: deadcode, required: true},
   466  	{name: "checkLower", fn: checkLower, required: true},
   467  	{name: "late phielim", fn: phielim},
   468  	{name: "late copyelim", fn: copyelim},
   469  	{name: "tighten", fn: tighten}, // move values closer to their uses
   470  	{name: "late deadcode", fn: deadcode},
   471  	{name: "critical", fn: critical, required: true}, // remove critical edges
   472  	{name: "phi tighten", fn: phiTighten},            // place rematerializable phi args near uses to reduce value lifetimes
   473  	{name: "likelyadjust", fn: likelyadjust},
   474  	{name: "layout", fn: layout, required: true},     // schedule blocks
   475  	{name: "schedule", fn: schedule, required: true}, // schedule values
   476  	{name: "late nilcheck", fn: nilcheckelim2},
   477  	{name: "flagalloc", fn: flagalloc, required: true}, // allocate flags register
   478  	{name: "regalloc", fn: regalloc, required: true},   // allocate int & float registers + stack slots
   479  	{name: "loop rotate", fn: loopRotate},
   480  	{name: "stackframe", fn: stackframe, required: true},
   481  	{name: "trim", fn: trim}, // remove empty blocks
   482  }
   483  
   484  // Double-check phase ordering constraints.
   485  // This code is intended to document the ordering requirements
   486  // between different phases. It does not override the passes
   487  // list above.
   488  type constraint struct {
   489  	a, b string // a must come before b
   490  }
   491  
   492  var passOrder = [...]constraint{
   493  	// "insert resched checks" uses mem, better to clean out stores first.
   494  	{"dse", "insert resched checks"},
   495  	// insert resched checks adds new blocks containing generic instructions
   496  	{"insert resched checks", "lower"},
   497  	{"insert resched checks", "tighten"},
   498  
   499  	// prove relies on common-subexpression elimination for maximum benefits.
   500  	{"generic cse", "prove"},
   501  	// deadcode after prove to eliminate all new dead blocks.
   502  	{"prove", "generic deadcode"},
   503  	// common-subexpression before dead-store elim, so that we recognize
   504  	// when two address expressions are the same.
   505  	{"generic cse", "dse"},
   506  	// cse substantially improves nilcheckelim efficacy
   507  	{"generic cse", "nilcheckelim"},
   508  	// allow deadcode to clean up after nilcheckelim
   509  	{"nilcheckelim", "generic deadcode"},
   510  	// nilcheckelim generates sequences of plain basic blocks
   511  	{"nilcheckelim", "late fuse"},
   512  	// nilcheckelim relies on opt to rewrite user nil checks
   513  	{"opt", "nilcheckelim"},
   514  	// tighten will be most effective when as many values have been removed as possible
   515  	{"generic deadcode", "tighten"},
   516  	{"generic cse", "tighten"},
   517  	// checkbce needs the values removed
   518  	{"generic deadcode", "check bce"},
   519  	// don't run optimization pass until we've decomposed builtin objects
   520  	{"decompose builtin", "late opt"},
   521  	// decompose builtin is the last pass that may introduce new float ops, so run softfloat after it
   522  	{"decompose builtin", "softfloat"},
   523  	// tuple selectors must be tightened to generators and de-duplicated before scheduling
   524  	{"tighten tuple selectors", "schedule"},
   525  	// remove critical edges before phi tighten, so that phi args get better placement
   526  	{"critical", "phi tighten"},
   527  	// don't layout blocks until critical edges have been removed
   528  	{"critical", "layout"},
   529  	// regalloc requires the removal of all critical edges
   530  	{"critical", "regalloc"},
   531  	// regalloc requires all the values in a block to be scheduled
   532  	{"schedule", "regalloc"},
   533  	// checkLower must run after lowering & subsequent dead code elim
   534  	{"lower", "checkLower"},
   535  	{"lowered deadcode", "checkLower"},
   536  	// late nilcheck needs instructions to be scheduled.
   537  	{"schedule", "late nilcheck"},
   538  	// flagalloc needs instructions to be scheduled.
   539  	{"schedule", "flagalloc"},
   540  	// regalloc needs flags to be allocated first.
   541  	{"flagalloc", "regalloc"},
   542  	// loopRotate will confuse regalloc.
   543  	{"regalloc", "loop rotate"},
   544  	// stackframe needs to know about spilled registers.
   545  	{"regalloc", "stackframe"},
   546  	// trim needs regalloc to be done first.
   547  	{"regalloc", "trim"},
   548  }
   549  
   550  func init() {
   551  	for _, c := range passOrder {
   552  		a, b := c.a, c.b
   553  		i := -1
   554  		j := -1
   555  		for k, p := range passes {
   556  			if p.name == a {
   557  				i = k
   558  			}
   559  			if p.name == b {
   560  				j = k
   561  			}
   562  		}
   563  		if i < 0 {
   564  			log.Panicf("pass %s not found", a)
   565  		}
   566  		if j < 0 {
   567  			log.Panicf("pass %s not found", b)
   568  		}
   569  		if i >= j {
   570  			log.Panicf("passes %s and %s out of order", a, b)
   571  		}
   572  	}
   573  }
   574
View as plain text