compile.go

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