...
Run Format

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

View as plain text