Source file src/pkg/cmd/compile/internal/ssa/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/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