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

View as plain text