Repository: VKCOM/noverify
Pull request #668 (2020-08-13 07:13:04)

cmd/php-guru: initial commit
Add experimental php-guru command.

php-guru analyzes the code base and answers some queries about it.

Right now it can only find duplicated funcs/methods.

Signed-off-by: Iskander Sharipov <quasilyte@gmail.com>


Patch:
diff --git a/src/cmd/php-guru/cmd_help.go b/src/cmd/php-guru/cmd_help.go
new file mode 100644
index 0000000..3ded118
--- /dev/null
+++ b/src/cmd/php-guru/cmd_help.go
@@ -0,0 +1,15 @@
+package main
+
+import (
+	"flag"
+
+	"github.com/VKCOM/noverify/src/cmd/php-guru/guru"
+)
+
+func cmdHelp(ctx *guru.Context) (int, error) {
+	flag.Parse()
+
+	printSupportedCommands(commands)
+
+	return 0, nil
+}
diff --git a/src/cmd/php-guru/dupcode/complexity.go b/src/cmd/php-guru/dupcode/complexity.go
new file mode 100644
index 0000000..56ecfc5
--- /dev/null
+++ b/src/cmd/php-guru/dupcode/complexity.go
@@ -0,0 +1,62 @@
+package dupcode
+
+import (
+	"github.com/VKCOM/noverify/src/ir"
+)
+
+// assertComplexity reports whether the given node list reaches the min complexity value.
+//
+// We don't calculate the precise complexity to avoid full IR traversal for big functions.
+// When we reached the min complexity goal, the traversal terminates.
+func assertComplexity(list []ir.Node, min uint) bool {
+	// Most nodes have the "cost" of at least 1, so
+	// if we have more than min nodes, we'll probably will
+	// reach the complexity requirement.
+	if uint(len(list)) >= min {
+		return true
+	}
+
+	c := complexityWalker{target: min}
+	for _, n := range list {
+		n.Walk(&c)
+		if c.goalReached() {
+			return true
+		}
+	}
+	return c.goalReached()
+}
+
+type complexityWalker struct {
+	current uint
+	target  uint
+}
+
+func (c *complexityWalker) goalReached() bool {
+	return c.current >= c.target
+}
+
+func (c *complexityWalker) LeaveNode(n ir.Node) {}
+
+func (c *complexityWalker) EnterNode(n ir.Node) bool {
+	if c.goalReached() {
+		return false
+	}
+
+	delta := uint(1)
+
+	switch n := n.(type) {
+	case *ir.Argument, *ir.ArrayItemExpr:
+		delta = 0
+	case *ir.IfStmt, *ir.TryStmt:
+		delta = 2
+	case *ir.ForStmt, *ir.ForeachStmt, *ir.WhileStmt, *ir.DoStmt, *ir.SwitchStmt:
+		delta = 3
+	case *ir.String:
+		delta = uint(len(n.Value)/25) + 1
+	case *ir.EncapsedStringPart:
+		delta = uint(len(n.Value)/25) + 1
+	}
+
+	c.current += delta
+	return !c.goalReached()
+}
diff --git a/src/cmd/php-guru/dupcode/fileindexer.go b/src/cmd/php-guru/dupcode/fileindexer.go
new file mode 100644
index 0000000..daffca1
--- /dev/null
+++ b/src/cmd/php-guru/dupcode/fileindexer.go
@@ -0,0 +1,126 @@
+package dupcode
+
+import (
+	"github.com/VKCOM/noverify/src/ir"
+	"github.com/VKCOM/noverify/src/ir/normalize"
+)
+
+type fileIndexer struct {
+	funcs        funcSet
+	fileContents []byte
+	filename     string
+	args         *arguments
+}
+
+func (indexer *fileIndexer) CollectFuncs(root *ir.Root) {
+	indexer.walkStatements(root.Stmts)
+}
+
+func (indexer *fileIndexer) walkStatements(list []ir.Node) {
+	for _, stmt := range list {
+		switch stmt := stmt.(type) {
+		case *ir.FunctionStmt:
+			indexer.walkFunc(stmt)
+		case *ir.ClassStmt:
+			indexer.walkClass(stmt)
+		case *ir.NamespaceStmt:
+			indexer.walkStatements(stmt.Stmts)
+		}
+	}
+}
+
+func (indexer *fileIndexer) walkClass(n *ir.ClassStmt) {
+	for _, stmt := range n.Stmts {
+		method, ok := stmt.(*ir.ClassMethodStmt)
+		if !ok {
+			continue
+		}
+		indexer.walkMethod(n.ClassName.Value, method)
+	}
+}
+
+func (indexer *fileIndexer) walkMethod(className string, n *ir.ClassMethodStmt) {
+	body, ok := n.Stmt.(*ir.StmtList)
+	if !ok {
+		return
+	}
+	if !indexer.canAnalyzeMethod(body.Stmts) {
+		return
+	}
+	// Visit private methods only if told to do so.
+	if !indexer.args.checkPrivate && hasModifier(n.Modifiers, "private") {
+		return
+	}
+	if !assertComplexity(body.Stmts, indexer.args.minComplexity) {
+		return
+	}
+
+	indexer.collectFunc(n, className, n.MethodName.Value, n.Params, body.Stmts)
+}
+
+func (indexer *fileIndexer) walkFunc(n *ir.FunctionStmt) {
+	if !assertComplexity(n.Stmts, indexer.args.minComplexity) {
+		return
+	}
+
+	indexer.collectFunc(n, "", n.FunctionName.Value, n.Params, n.Stmts)
+}
+
+func (indexer *fileIndexer) collectFunc(n ir.Node, className, funcName string, params, stmts []ir.Node) {
+	if indexer.args.norm != 0 {
+		conf := normalize.Config{
+			NormalizeMore: indexer.args.norm > 1,
+		}
+		stmts = normalize.FuncBody(conf, params, stmts)
+	}
+
+	pos := ir.GetPosition(n)
+	key := calculateCodeHash(stmts)
+	newFunc := &funcInfo{
+		className: className,
+		name:      funcName,
+		declPos: position{
+			line:     pos.StartLine,
+			filename: indexer.filename,
+		},
+		linesOfCode: pos.EndLine - pos.StartLine,
+		code:        indexer.nodeText(n),
+	}
+	indexer.funcs.AddFunc(key, newFunc)
+}
+
+func (indexer *fileIndexer) canAnalyzeMethod(list []ir.Node) bool {
+	// Don't waste time on huge methods.
+	if len(list) > 25 {
+		return false
+	}
+
+	for _, stmt := range list {
+		cantAnalyze := findNode(stmt, func(n ir.Node) bool {
+			switch n := n.(type) {
+			case *ir.SimpleVar:
+				if n.Name == "this" {
+					return true
+				}
+			case *ir.Name:
+				if n.Value == "self" || n.Value == "static" {
+					return true
+				}
+			case *ir.Identifier:
+				if n.Value == "self" || n.Value == "static" {
+					return true
+				}
+			}
+			return false
+		})
+		if cantAnalyze {
+			return false
+		}
+	}
+	return true
+}
+
+func (indexer *fileIndexer) nodeText(n ir.Node) []byte {
+	pos := ir.GetPosition(n)
+	return indexer.fileContents[pos.StartPos:pos.EndPos]
+}
diff --git a/src/cmd/php-guru/dupcode/funcinfo.go b/src/cmd/php-guru/dupcode/funcinfo.go
new file mode 100644
index 0000000..b9dd51c
--- /dev/null
+++ b/src/cmd/php-guru/dupcode/funcinfo.go
@@ -0,0 +1,23 @@
+package dupcode
+
+import (
+	"fmt"
+)
+
+type funcInfo struct {
+	name        string
+	className   string
+	declPos     position
+	linesOfCode int
+	dups        []*funcInfo
+	code        []byte
+}
+
+type position struct {
+	line     int
+	filename string
+}
+
+func (pos position) String() string {
+	return fmt.Sprintf("%s:%d", pos.filename, pos.line)
+}
diff --git a/src/cmd/php-guru/dupcode/funcset.go b/src/cmd/php-guru/dupcode/funcset.go
new file mode 100644
index 0000000..5aa7404
--- /dev/null
+++ b/src/cmd/php-guru/dupcode/funcset.go
@@ -0,0 +1,41 @@
+package dupcode
+
+import (
+	"crypto/md5"
+	"fmt"
+
+	"github.com/VKCOM/noverify/src/ir"
+	"github.com/VKCOM/noverify/src/ir/irfmt"
+)
+
+type codeHash string
+
+func calculateCodeHash(list []ir.Node) codeHash {
+	asBlock := &ir.StmtList{Stmts: list}
+	codeText := irfmt.Node(asBlock)
+	h := md5.Sum([]byte(codeText))
+	return codeHash(fmt.Sprintf("%x", h))
+}
+
+type funcSet map[codeHash]*funcInfo
+
+func (set funcSet) AddFunc(key codeHash, info *funcInfo) {
+	origFunc, ok := set[key]
+	if ok {
+		origFunc.dups = append(origFunc.dups, info)
+		return
+	}
+	set[key] = info
+}
+
+func (set funcSet) Merge(otherSet funcSet) {
+	for hash, x := range otherSet {
+		y, ok := set[hash]
+		if !ok {
+			set[hash] = x
+			continue
+		}
+		y.dups = append(y.dups, x)
+		y.dups = append(y.dups, x.dups...)
+	}
+}
diff --git a/src/cmd/php-guru/dupcode/main.go b/src/cmd/php-guru/dupcode/main.go
new file mode 100644
index 0000000..cf630d5
--- /dev/null
+++ b/src/cmd/php-guru/dupcode/main.go
@@ -0,0 +1,116 @@
+package dupcode
+
+import (
+	"flag"
+	"fmt"
+	"io/ioutil"
+	"log"
+	"regexp"
+	"runtime"
+	"sync"
+
+	"github.com/VKCOM/noverify/src/cmd/php-guru/guru"
+	"github.com/VKCOM/noverify/src/ir/irconv"
+	"github.com/VKCOM/noverify/src/php/parseutil"
+	"github.com/VKCOM/noverify/src/workspace"
+)
+
+// We don't use linter "custom" API here as it doesn't bring much to the
+// table for us and we don't want to depend on that API.
+//
+// Maybe we'll roll the custom-v2 and use it here.
+
+// TODO: handle methods better (don't give up on self-references).
+
+func Main(ctx *guru.Context) (int, error) {
+	var args arguments
+	flag.BoolVar(&args.checkPrivate, "private", false,
+		"whether private methods should be analyzed")
+	flag.BoolVar(&args.checkAutogen, "autogen", false,
+		"whether auto-generated files should be analyzed")
+	flag.StringVar(&args.exclude, "exclude", "",
+		"regexp that excludes files from the analysis")
+	flag.UintVar(&args.minComplexity, "min-complexity", 20,
+		"min function complexity level threshold")
+	flag.UintVar(&args.norm, "norm", 1,
+		"code normalization level: 0 for none, 1 for safe, 2 if you feel lucky")
+
+	flag.Parse()
+
+	var exclude *regexp.Regexp
+	if args.exclude != "" {
+		var err error
+		exclude, err = regexp.Compile(args.exclude)
+		if err != nil {
+			return 1, fmt.Errorf("parse -exclude: %v", err)
+		}
+	}
+	switch args.norm {
+	case 0, 1, 2:
+		// OK.
+	default:
+		return 1, fmt.Errorf("invalid -norm level %d", args.norm)
+	}
+
+	targets := flag.Args()
+
+	filter := workspace.NewFilenameFilter(exclude)
+	readFileNamesFunc := workspace.ReadFilenames(targets, filter)
+	filenamesCh := make(chan workspace.FileInfo, 512)
+	go func() {
+		readFileNamesFunc(filenamesCh)
+		close(filenamesCh)
+	}()
+
+	nworkers := runtime.NumCPU()
+	results := make([]funcSet, nworkers)
+	var wg sync.WaitGroup
+	wg.Add(nworkers)
+	for i := 0; i < nworkers; i++ {
+		go func(workerID int) {
+			workerResult := make(funcSet)
+			for f := range filenamesCh {
+				data, err := ioutil.ReadFile(f.Filename)
+				if err != nil {
+					log.Printf("read %s file: %v", f.Filename, err)
+				}
+				if !args.checkAutogen && workspace.FileIsAutoGenerated(data) {
+					continue
+				}
+				root, err := parseutil.ParseFile(data)
+				if err != nil {
+					log.Printf("parse %s file: %v", f.Filename, err)
+				}
+				rootIR := irconv.ConvertRoot(root)
+
+				indexer := &fileIndexer{
+					funcs:        workerResult,
+					fileContents: data,
+					filename:     f.Filename,
+					args:         &args,
+				}
+				indexer.CollectFuncs(rootIR)
+			}
+			results[workerID] = workerResult
+			wg.Done()
+		}(i)
+	}
+	wg.Wait()
+
+	allFuncs := make(funcSet)
+	for _, workerResult := range results {
+		allFuncs.Merge(workerResult)
+	}
+
+	printDuplicates(allFuncs)
+
+	return 0, nil
+}
+
+type arguments struct {
+	checkPrivate  bool
+	checkAutogen  bool
+	exclude       string
+	minComplexity uint
+	norm          uint
+}
diff --git a/src/cmd/php-guru/dupcode/print.go b/src/cmd/php-guru/dupcode/print.go
new file mode 100644
index 0000000..1b56a95
--- /dev/null
+++ b/src/cmd/php-guru/dupcode/print.go
@@ -0,0 +1,41 @@
+package dupcode
+
+import (
+	"fmt"
+	"sort"
+)
+
+func printDuplicates(funcs funcSet) {
+	funcScore := func(fn *funcInfo) int {
+		baseScore := len(fn.code)
+		return baseScore * len(fn.dups)
+	}
+
+	funcList := make([]*funcInfo, 0, len(funcs))
+	for _, fn := range funcs {
+		if len(fn.dups) == 0 {
+			continue // No duplicates
+		}
+		funcList = append(funcList, fn)
+	}
+	sort.Slice(funcList, func(i, j int) bool {
+		return funcScore(funcList[i]) > funcScore(funcList[j])
+	})
+
+	dupLines := 0
+	totalFuncs := 0
+	for _, fn := range funcList {
+		fmt.Printf("%s: %s()\n", fn.declPos, fn.name)
+		for _, dup := range fn.dups {
+			fmt.Printf("%s: %s()\n", dup.declPos, dup.name)
+		}
+		fmt.Println(string(fn.code))
+		fmt.Println("----")
+		dupLines += fn.linesOfCode * len(fn.dups)
+		totalFuncs += len(fn.dups) + 1
+	}
+
+	fmt.Printf("%d duplicated patterns reported\n", len(funcList))
+	fmt.Printf("%d funcs included\n", totalFuncs)
+	fmt.Printf("%d duplicated lines of code\n", dupLines)
+}
diff --git a/src/cmd/php-guru/dupcode/utils.go b/src/cmd/php-guru/dupcode/utils.go
new file mode 100644
index 0000000..7b6a8ff
--- /dev/null
+++ b/src/cmd/php-guru/dupcode/utils.go
@@ -0,0 +1,37 @@
+package dupcode
+
+import (
+	"github.com/VKCOM/noverify/src/ir"
+	"github.com/VKCOM/noverify/src/ir/irutil"
+)
+
+func findNode(root ir.Node, pred func(n ir.Node) bool) bool {
+	found := false
+	irutil.Inspect(root, func(n ir.Node) bool {
+		if found {
+			return false
+		}
+		if pred(n) {
+			found = true
+		}
+		if v, ok := n.(*ir.SimpleVar); ok {
+			if v.Name == "this" {
+				found = true
+			}
+		}
+		return !found
+	})
+	if found {
+		return true
+	}
+	return found
+}
+
+func hasModifier(list []*ir.Identifier, key string) bool {
+	for _, x := range list {
+		if x.Value == key {
+			return true
+		}
+	}
+	return false
+}
diff --git a/src/cmd/php-guru/guru/guru.go b/src/cmd/php-guru/guru/guru.go
new file mode 100644
index 0000000..c6bc79e
--- /dev/null
+++ b/src/cmd/php-guru/guru/guru.go
@@ -0,0 +1,7 @@
+package guru
+
+type Context struct{}
+
+func NewContext() *Context {
+	return &Context{}
+}
diff --git a/src/cmd/php-guru/main.go b/src/cmd/php-guru/main.go
new file mode 100644
index 0000000..9a4993b
--- /dev/null
+++ b/src/cmd/php-guru/main.go
@@ -0,0 +1,82 @@
+package main
+
+import (
+	"log"
+	"os"
+	"sort"
+
+	"github.com/VKCOM/noverify/src/cmd/php-guru/dupcode"
+	"github.com/VKCOM/noverify/src/cmd/php-guru/guru"
+)
+
+var commands []*subCommand
+
+func guruCommands() []*subCommand {
+	commands := []*subCommand{
+		{
+			name:    "help",
+			main:    cmdHelp,
+			summary: "print documentation based on the subject",
+			examples: []subCommandExample{
+				{
+					comment: "show supported sub-commands",
+					line:    "",
+				},
+			},
+		},
+
+		{
+			name:    "dupcode",
+			main:    dupcode.Main,
+			summary: "find the code duplication",
+			examples: []subCommandExample{
+				{
+					comment: "show dupcode sub-command help",
+					line:    "-help",
+				},
+				{
+					comment: "print all code duplicates across the project",
+					line:    "path/to/project",
+				},
+			},
+		},
+	}
+
+	sort.Slice(commands, func(i, j int) bool {
+		return commands[i].name < commands[j].name
+	})
+
+	return commands
+}
+
+func main() {
+	log.SetFlags(0)
+
+	commands = guruCommands()
+
+	if len(os.Args) < 2 {
+		log.Println("Please provide a sub-command argument")
+		printSupportedCommands(commands)
+		os.Exit(1)
+	}
+
+	subcmdName := os.Args[1]
+	subcmd := findSubCommand(commands, subcmdName)
+	if subcmd == nil {
+		log.Printf("Sub-command %s doesn't exist\n\n", subcmdName)
+		printSupportedCommands(commands)
+		os.Exit(1)
+	}
+
+	subIdx := 1 // [0] is program name
+	// Erase sub-command argument (index=1) to make it invisible for
+	// sub commands themselves.
+	os.Args = append(os.Args[:subIdx], os.Args[subIdx+1:]...)
+
+	ctx := guru.NewContext()
+	status, err := subcmd.main(ctx)
+	if err != nil {
+		log.Fatal(err)
+	}
+	os.Exit(status)
+}
diff --git a/src/cmd/php-guru/subcmd.go b/src/cmd/php-guru/subcmd.go
new file mode 100644
index 0000000..e6b4081
--- /dev/null
+++ b/src/cmd/php-guru/subcmd.go
@@ -0,0 +1,40 @@
+package main
+
+import (
+	"fmt"
+
+	"github.com/VKCOM/noverify/src/cmd/php-guru/guru"
+)
+
+type subCommand struct {
+	name     string
+	main     func(*guru.Context) (int, error)
+	summary  string
+	examples []subCommandExample
+}
+
+type subCommandExample struct {
+	comment string
+	line    string
+}
+
+func findSubCommand(list []*subCommand, name string) *subCommand {
+	for _, cmd := range list {
+		if cmd.name == name {
+			return cmd
+		}
+	}
+	return nil
+}
+
+func printSupportedCommands(list []*subCommand) {
+	fmt.Printf("Supported sub-commands:\n")
+	for _, cmd := range list {
+		fmt.Printf("\n\tphp-guru %s\n", cmd.name)
+		fmt.Printf("\tDescription: %s.\n", cmd.summary)
+		for _, ex := range cmd.examples {
+			fmt.Printf("\t%s:\n", ex.comment)
+			fmt.Printf("\t\t$ php-guru %s %s\n", cmd.name, ex.line)
+		}
+	}
+}
diff --git a/src/ir/normalize/normalize.go b/src/ir/normalize/normalize.go
new file mode 100644
index 0000000..63896d4
--- /dev/null
+++ b/src/ir/normalize/normalize.go
@@ -0,0 +1,471 @@
+package normalize
+
+import (
+	"fmt"
+	"sort"
+	"strings"
+
+	"github.com/VKCOM/noverify/src/ir"
+	"github.com/VKCOM/noverify/src/ir/irfmt"
+	"github.com/VKCOM/noverify/src/ir/irutil"
+)
+
+type Config struct {
+	CurrentClass  string
+	NormalizeMore bool
+}
+
+func FuncBody(conf Config, params, statements []ir.Node) []ir.Node {
+	norm := normalizer{
+		out:     irutil.NodeSliceClone(statements),
+		conf:    conf,
+		globals: make(map[string]struct{}),
+	}
+
+	norm.runPre()
+
+	norm.run(params)
+	changed := !irutil.NodeSliceEqual(norm.out, statements)
+	if changed {
+		norm.run(params)
+	}
+	return norm.out
+}
+
+type normalizer struct {
+	out      []ir.Node
+	conf     Config
+	varNames map[string]int
+	globals  map[string]struct{}
+}
+
+func (norm *normalizer) runPre() {
+	norm.out = norm.sortStatements(norm.out)
+
+	// TODO:
+	// `$x = $y = 10` => `$y = 10; $x = $y;`
+	// `global $x, $y` => `global $x; global $y;`
+}
+
+func (norm *normalizer) run(params []ir.Node) {
+	norm.varNames = make(map[string]int)
+	for _, p := range params {
+		p := p.(*ir.Parameter)
+		norm.internVarName(p.Variable.Name)
+	}
+
+	for _, n := range norm.out {
+		n.Walk(norm)
+	}
+}
+
+func (norm *normalizer) sortStatements(statements []ir.Node) []ir.Node {
+	var simpleExpr func(n ir.Node) bool
+	simpleExpr = func(n ir.Node) bool {
+		if n == nil {
+			return true
+		}
+		switch n := n.(type) {
+		case *ir.ArrayItemExpr:
+			return simpleExpr(n.Key) && simpleExpr(n.Val)
+		case *ir.ArrayExpr:
+			for _, item := range n.Items {
+				if !simpleExpr(item) {
+					return false
+				}
+			}
+			return true
+		case *ir.String, *ir.Lnumber, *ir.Dnumber, *ir.ConstFetchExpr:
+			return true
+		}
+		return false
+	}
+
+	var sortKey func(n ir.Node) string
+	sortKey = func(n ir.Node) string {
+		switch n := n.(type) {
+		case *ir.ImportExpr, *ir.GlobalStmt:
+			// Since we don't allow variables and function calls inside
+			// reordered blocks, requires and global statements can be
+			// considered to be reorderable.
+			return irfmt.Node(n)
+		case *ir.ExpressionStmt:
+			return sortKey(n.Expr)
+		case *ir.Assign:
+			_, ok := n.Variable.(*ir.SimpleVar)
+			if ok && simpleExpr(n.Expression) {
+				return irfmt.Node(n.Expression)
+			}
+		}
+		return ""
+	}
+
+	out := statements[:0]
+	for len(statements) > 0 {
+		type sortableStatement struct {
+			key string
+			n   ir.Node
+		}
+		var block []sortableStatement
+		for _, n := range statements {
+			k := sortKey(n)
+			if k == "" {
+				break
+			}
+			block = append(block, sortableStatement{key: k, n: n})
+		}
+		if len(block) == 0 {
+			out = append(out, statements[0])
+			statements = statements[1:]
+		} else {
+			sort.SliceStable(block, func(i, j int) bool {
+				return block[i].key < block[j].key
+			})
+			for i := range block {
+				out = append(out, block[i].n)
+			}
+			statements = statements[len(block):]
+		}
+	}
+	return out
+}
+
+func (norm *normalizer) LeaveNode(n ir.Node) {}
+
+func (norm *normalizer) EnterNode(w ir.Node) bool {
+	switch n := w.(type) {
+	case *ir.GlobalStmt:
+		for _, v := range n.Vars {
+			v, ok := v.(*ir.SimpleVar)
+			if !ok {
+				continue
+			}
+			norm.globals[v.Name] = struct{}{}
+		}
+		return false
+
+	case *ir.IfStmt:
+		norm.normalizeIf(n)
+
+	case *ir.SimpleVar:
+		norm.renameVar(n)
+
+	case *ir.StmtList:
+		n.Stmts = norm.sortStatements(n.Stmts)
+
+	case *ir.ReturnStmt:
+		n.Expr = norm.normalizedExpr(n.Expr)
+	case *ir.Argument:
+		n.Expr = norm.normalizedExpr(n.Expr)
+	case *ir.ExpressionStmt:
+		n.Expr = norm.normalizedStmtExpr(n.Expr)
+
+	case *ir.Assign:
+		n.Expression = norm.normalizedExpr(n.Expression)
+		n.Variable = norm.normalizedExpr(n.Variable)
+	case *ir.AssignPlus:
+		n.Expression = norm.normalizedExpr(n.Expression)
+		n.Variable = norm.normalizedExpr(n.Variable)
+	case *ir.AssignConcat:
+		n.Expression = norm.normalizedExpr(n.Expression)
+		n.Variable = norm.normalizedExpr(n.Variable)
+
+	case *ir.StaticPropertyFetchExpr:
+		n.Class = norm.normalizedExpr(n.Class)
+		return false // To avoid var renaming
+
+	case *ir.StaticCallExpr:
+		n.Class = norm.normalizedExpr(n.Class)
+	case *ir.ClassConstFetchExpr:
+		n.Class = norm.normalizedExpr(n.Class)
+
+	case *ir.ForStmt:
+		for i := range n.Init {
+			n.Init[i] = norm.normalizedStmtExpr(n.Init[i])
+		}
+		for i := range n.Loop {
+			n.Loop[i] = norm.normalizedStmtExpr(n.Loop[i])
+		}
+
+	case *ir.EchoStmt:
+		for i := range n.Exprs {
+			n.Exprs[i] = norm.normalizedExpr(n.Exprs[i])
+		}
+	}
+
+	return true
+}
+
+func (norm *normalizer) normalizeIf(n *ir.IfStmt) {
+	// `if (!$x) { $a } else { $b }` => `if ($x) { $b } else { $a }`
+	if len(n.ElseIf) != 0 || n.Else == nil {
+		return
+	}
+	not, ok := n.Cond.(*ir.BooleanNotExpr)
+	if !ok {
+		return
+	}
+	elseNode := n.Else.(*ir.ElseStmt)
+	n.Stmt, elseNode.Stmt = elseNode.Stmt, n.Stmt
+	n.Cond = not.Expr
+}
+
+func (norm *normalizer) normalizedStmtExpr(e ir.Node) ir.Node {
+	// We can be less conservative if expression result is unused.
+	// For example, in loop pos-statement both `$i++` and `++$i` are identical.
+
+	switch e := e.(type) {
+	case *ir.PostIncExpr:
+		// `$x++` => `++$x`
+		return &ir.PreIncExpr{Variable: e.Variable}
+	case *ir.PostDecExpr:
+		// `$x--` => `--$x`
+		return &ir.PreDecExpr{Variable: e.Variable}
+	case *ir.FunctionCallExpr:
+		funcName, ok := e.Function.(*ir.Name)
+		if !ok {
+			break
+		}
+		// `array_push($a, $e)` => `$a[] = $e`
+		if len(e.Args) == 2 && funcName.Value == "array_push" {
+			a := e.Arg(0).Expr
+			e := e.Arg(1).Expr
+			return &ir.Assign{
+				Variable: &ir.ArrayDimFetchExpr{
+					Variable: norm.normalizedExpr(a),
+				},
+				Expression: norm.normalizedExpr(e),
+			}
+		}
+	}
+
+	return norm.normalizedExpr(e)
+}
+
+func (norm *normalizer) normalizedExpr(e ir.Node) ir.Node {
+	switch e := e.(type) {
+	case *ir.Name:
+		if e.Value == "self" {
+			return &ir.Name{Value: norm.conf.CurrentClass}
+		}
+
+	case *ir.NewExpr:
+		// `new T` => `new T()`
+		if e.Args == nil {
+			e.Args = []ir.Node{}
+		}
+
+	case *ir.BooleanNotExpr:
+		// `!!$x` => `(bool)$x`
+		if x, ok := e.Expr.(*ir.BooleanNotExpr); ok {
+			return &ir.TypeCastExpr{
+				Type: "bool",
+				Expr: norm.normalizedExpr(x.Expr),
+			}
+		}
+
+	case *ir.Encapsed:
+		// `"$x"` => `'' . $x`
+		if len(e.Parts) == 1 {
+			return &ir.ConcatExpr{
+				Left:  emptyStringNode,
+				Right: encapsedPartToConcatArg(e.Parts[0]),
+			}
+		}
+		// `"$x$y"` => `$x . $y`
+		// `"$x$y$z"` => `$x . $y . $z`
+		concat := &ir.ConcatExpr{
+			Left:  encapsedPartToConcatArg(e.Parts[0]),
+			Right: encapsedPartToConcatArg(e.Parts[1]),
+		}
+		for _, p := range e.Parts[2:] {
+			concat = &ir.ConcatExpr{
+				Left:  concat,
+				Right: encapsedPartToConcatArg(p),
+			}
+		}
+		return concat
+
+	case *ir.PlusExpr:
+		norm.sortCommutative(&e.Left, &e.Right)
+	case *ir.MulExpr:
+		norm.sortCommutative(&e.Left, &e.Right)
+	case *ir.EqualExpr:
+		norm.sortCommutative(&e.Left, &e.Right)
+	case *ir.NotEqualExpr:
+		norm.sortCommutative(&e.Left, &e.Right)
+	case *ir.IdenticalExpr:
+		norm.sortCommutative(&e.Left, &e.Right)
+	case *ir.NotIdenticalExpr:
+		norm.sortCommutative(&e.Left, &e.Right)
+
+	case *ir.String:
+		// `"abc"` => `'abc'`
+		if e.Value[0] != '"' {
+			break
+		}
+		if !strings.ContainsAny(e.Value, `'\`) {
+			e.Value = `'` + strings.Trim(e.Value, `"`) + `'`
+		}
+
+	case *ir.TernaryExpr:
+		// `$x ? $x : $y` => `$x ?: $y`
+		if sideEffectFree(e.Condition) && irutil.NodeEqual(e.Condition, e.IfTrue) {
+			e.IfTrue = nil
+			return e
+		}
+		// TODO: `isset($x) ? $x : $y` => `$x ?? $y`
+
+	case *ir.ConstFetchExpr:
+		// `NULL` => `null`
+		constNameString := e.Constant.Value
+		switch {
+		case strings.EqualFold(constNameString, `null`):
+			if constNameString != `null` {
+				e.Constant = &ir.Name{Value: `null`}
+			}
+		case strings.EqualFold(constNameString, `true`):
+			if constNameString != `true` {
+				e.Constant = &ir.Name{Value: `true`}
+			}
+		case strings.EqualFold(constNameString, `false`):
+			if constNameString != `false` {
+				e.Constant = &ir.Name{Value: `false`}
+			}
+		}
+
+	case *ir.FunctionCallExpr:
+		funcName, ok := e.Function.(*ir.Name)
+		if !ok {
+			break
+		}
+		// `is_null($x)` => `$x === null`
+		if funcName.Value == "is_null" {
+			return &ir.IdenticalExpr{
+				Left:  e.Arg(0).Expr,
+				Right: nullConstNode,
+			}
+		}
+
+		// Replace aliased functions.
+		alias, ok := funcAliases[funcName.Value]
+		if ok {
+			e.Function = alias
+		}
+
+	case *ir.Assign:
+		if !sideEffectFree(e.Variable) {
+			break
+		}
+		// `$x = $x <op> $y` => `$x <op>= $y`
+		switch rhs := e.Expression.(type) {
+		case *ir.PlusExpr:
+			if irutil.NodeEqual(e.Variable, rhs.Left) {
+				return &ir.AssignPlus{Variable: e.Variable, Expression: rhs.Right}
+			}
+		case *ir.MinusExpr:
+			if irutil.NodeEqual(e.Variable, rhs.Left) {
+				return &ir.AssignMinus{Variable: e.Variable, Expression: rhs.Right}
+			}
+		case *ir.ConcatExpr:
+			if irutil.NodeEqual(e.Variable, rhs.Left) {
+				return &ir.AssignConcat{Variable: e.Variable, Expression: rhs.Right}
+			}
+		}
+
+	case *ir.AssignPlus:
+		// `$x += 1` => `++$x`
+		if literalValue(e.Expression) == `1` {
+			return &ir.PreIncExpr{Variable: e.Variable}
+		}
+	case *ir.AssignMinus:
+		// `$x -= 1` => `--$x`
+		if literalValue(e.Expression) == `1` {
+			return &ir.PreDecExpr{Variable: e.Variable}
+		}
+
+	case *ir.ArrayExpr:
+		// `array(...)` => `[...]`
+		e.ShortSyntax = true
+	case *ir.ListExpr:
+		// `list(...)` => `[...]`
+		e.ShortSyntax = true
+	}
+
+	return e
+}
+
+func (norm *normalizer) internVarName(name string) int {
+	id, ok := norm.varNames[name]
+	if !ok {
+		id = len(norm.varNames)
+		norm.varNames[name] = id
+	}
+	return id
+}
+
+func (norm *normalizer) sortCommutative(left, right *ir.Node) {
+	if !(sideEffectFree(*left) && sideEffectFree(*right)) {
+		return
+	}
+
+	if irfmt.Node(*left) > irfmt.Node(*right) {
+		*left, *right = *right, *left
+	}
+}
+
+func (norm *normalizer) renameVar(v *ir.SimpleVar) {
+	if _, ok := norm.globals[v.Name]; ok {
+		return
+	}
+	id := norm.internVarName(v.Name)
+	v.Name = fmt.Sprintf("v%d", id)
+}
+
+var (
+	nullConstNode   = &ir.ConstFetchExpr{Constant: &ir.Name{Value: "null"}}
+	emptyStringNode = &ir.String{Value: `''`}
+)
+
+var funcAliases = map[string]*ir.Name{
+	// See https://www.php.net/manual/ru/aliases.php
+
+	`doubleval`: {Value: `floatval`},
+
+	`ini_alter`:    {Value: `ini_set`},
+	`is_integer`:   {Value: `is_int`},
+	`is_long`:      {Value: `is_int`},
+	`is_real`:      {Value: `is_float`},
+	`is_double`:    {Value: `is_float`},
+	`is_writeable`: {Value: `is_writable`},
+
+	`join`:       {Value: `implode`},
+	`chop`:       {Value: `rtrim`},
+	`strchr`:     {Value: `strstr`},
+	`pos`:        {Value: `current`},
+	`key_exists`: {Value: `array_key_exists`},
+	`sizeof`:     {Value: `count`},
+
+	`close`:                {Value: `closedir`},
+	`fputs`:                {Value: `fwrite`},
+	`magic_quotes_runtime`: {Value: `set_magic_quotes_runtime`},
+	`show_source`:          {Value: `highlight_file`},
+}
+
+func literalValue(e ir.Node) string {
+	switch e := e.(type) {
+	case *ir.Lnumber:
+		return e.Value
+	default:
+		return ""
+	}
+}
+
+func encapsedPartToConcatArg(n ir.Node) ir.Node {
+	switch n := n.(type) {
+	case *ir.EncapsedStringPart:
+		return &ir.String{Value: `'` + n.Value + `'`}
+	default:
+		return n
+	}
+}
diff --git a/src/ir/normalize/side_effects.go b/src/ir/normalize/side_effects.go
new file mode 100644
index 0000000..b771b2b
--- /dev/null
+++ b/src/ir/normalize/side_effects.go
@@ -0,0 +1,164 @@
+package normalize
+
+import (
+	"github.com/VKCOM/noverify/src/ir"
+)
+
+func sideEffectFree(n ir.Node) bool {
+	f := sideEffectsFinder{}
+	n.Walk(&f)
+	return !f.sideEffects
+}
+
+type sideEffectsFinder struct {
+	sideEffects bool
+}
+
+var pureBuiltins = func() map[string]struct{} {
+	list := []string{
+		`\count`,
+		`\sizeof`,
+
+		// Array functions.
+		`\array_key_exists`,
+		`\array_keys`,
+		`\array_merge`,
+		`\array_slice`,
+		`\array_values`,
+		`\explode`,
+		`\implode`,
+		`\in_array`,
+
+		// String functions.
+		`\str_replace`,
+		`\strlen`,
+		`\strpos`,
+		`\strtolower`,
+		`\strtoupper`,
+		`\substr`,
+		`\trim`,
+
+		// Simple math functions.
+		`\abs`,
+		`\floor`,
+		`\max`,
+		`\min`,
+
+		// All type converting functions are pure.
+		`\boolval`,
+		`\doubleval`,
+		`\floatval`,
+		`\intval`,
+		`\strval`,
+
+		// All type predicates are pure.
+		`\is_array`,
+		`\is_bool`,
+		`\is_callable`,
+		`\is_countable`,
+		`\is_double`,
+		`\is_float`,
+		`\is_int`,
+		`\is_integer`,
+		`\is_iterable`,
+		`\is_long`,
+		`\is_null`,
+		`\is_numeric`,
+		`\is_object`,
+		`\is_real`,
+		`\is_resource`,
+		`\is_scalar`,
+		`\is_string`,
+	}
+
+	set := make(map[string]struct{}, len(list))
+	for _, nm := range list {
+		set[nm] = struct{}{}
+	}
+	return set
+}()
+
+func (f *sideEffectsFinder) functionCallIsPure(n *ir.FunctionCallExpr) bool {
+	// We allow referencing builtin funcs even before indexing is completed.
+
+	var funcName string
+	nm, ok := n.Function.(*ir.Name)
+	if ok {
+		if nm.IsFullyQualified() {
+			funcName = nm.Value
+		} else {
+			funcName = `\` + nm.Value
+		}
+	}
+
+	if funcName != "" {
+		// Might be a builtin.
+		if _, ok := pureBuiltins[funcName]; ok {
+			return true
+		}
+	}
+
+	return false
+}
+
+func (f *sideEffectsFinder) EnterNode(n ir.Node) bool {
+	if f.sideEffects {
+		return false
+	}
+
+	// We can get false positives for overloaded operations.
+	// For example, array index can be an offsetGet() call,
+	// which might not be pure.
+
+	switch n := n.(type) {
+	case *ir.FunctionCallExpr:
+		if f.functionCallIsPure(n) {
+			return true
+		}
+		f.sideEffects = true
+		return false
+
+	case *ir.MethodCallExpr:
+		f.sideEffects = true
+		return false
+
+	case *ir.StaticCallExpr:
+		f.sideEffects = true
+		return false
+
+	case *ir.PrintExpr,
+		*ir.EchoStmt,
+		*ir.UnsetStmt,
+		*ir.ThrowStmt,
+		*ir.GlobalStmt,
+		*ir.ExitExpr,
+		*ir.Assign,
+		*ir.AssignReference,
+		*ir.AssignBitwiseAnd,
+		*ir.AssignBitwiseOr,
+		*ir.AssignBitwiseXor,
+		*ir.AssignConcat,
+		*ir.AssignDiv,
+		*ir.AssignMinus,
+		*ir.AssignMod,
+		*ir.AssignMul,
+		*ir.AssignPlus,
+		*ir.AssignPow,
+		*ir.AssignShiftLeft,
+		*ir.AssignShiftRight,
+		*ir.YieldExpr,
+		*ir.YieldFromExpr,
+		*ir.EvalExpr,
+		*ir.PreIncExpr,
+		*ir.PostIncExpr,
+		*ir.PreDecExpr,
+		*ir.PostDecExpr,
+		*ir.ImportExpr:
+		f.sideEffects = true
+		return false
+	}
+
+	return true
+}
+
+func (f *sideEffectsFinder) LeaveNode(n ir.Node) {}


Test patch:
diff --git a/src/ir/normalize/normalize_test.go b/src/ir/normalize/normalize_test.go
new file mode 100644
index 0000000..de1768f
--- /dev/null
+++ b/src/ir/normalize/normalize_test.go
@@ -0,0 +1,173 @@
+package normalize
+
+import (
+	"errors"
+	"strings"
+	"testing"
+
+	"github.com/VKCOM/noverify/src/ir"
+	"github.com/VKCOM/noverify/src/ir/irconv"
+	"github.com/VKCOM/noverify/src/ir/irfmt"
+	"github.com/VKCOM/noverify/src/php/parser/php7"
+	"github.com/VKCOM/noverify/src/php/parseutil"
+)
+
+func TestNormalizeStmtList(t *testing.T) {
+	tests := []struct {
+		orig string
+		want string
+	}{
+		// Global vars should not be renamed.
+		{
+			`global $x; echo $x;`,
+			`global $x; echo $x;`,
+		},
+
+		// Swap if then/else for negated conditions.
+		{
+			`if (!$x) { a(); } else { b(); }`,
+			`if ($v0) { b(); } else { a(); }`,
+		},
+
+		// $x++ transformed into ++$x in stmt context.
+		{
+			`$x++; $x--;`,
+			`++$v0; --$v0;`,
+		},
+		{
+			`for (; ; $x++);`,
+			`for (; ; ++$v0);`,
+		},
+		// ...but not in expression context.
+		{
+			`$x = $y++;`,
+			`$v0 = $v1++;`,
+		},
+
+		// array_push() of 2 arguments is translated into []= assignment.
+		{
+			`array_push($a, 10);`,
+			`$v0[] = 10;`,
+		},
+
+		// Some statements can be re-ordered (sorted).
+		{
+			`$x = 0; $y = 'abc';`,
+			`$v0 = 'abc'; $v1 = 0;`,
+		},
+		{
+			`require 'b'; require 'a';`,
+			`require 'a'; require 'b';`,
+		},
+
+		{
+			`f(array(), "1$x$y/23");`,
+			`f([], '1' . $v0 . $v1 . '/23');`,
+		},
+
+		{
+			`self::$x; self::myconst;`,
+			`Foo::$x; Foo::myconst;`,
+		},
+	}
+
+	conf := Config{CurrentClass: `Foo`}
+	for _, test := range tests {
+
+		list, err := parseStmtList(test.orig)
+		if err != nil {
+			t.Errorf("parse `%s`: %v", test.orig, err)
+			continue
+		}
+		normalized := FuncBody(conf, nil, list)
+		have := strings.ReplaceAll(irfmt.Node(&ir.StmtList{Stmts: normalized}), "\n", "")
+		have = strings.ReplaceAll(have, "  ", " ")
+		want := `{ ` + test.want + `}`
+		if have != want {
+			t.Errorf("normalize `%s`:\nhave: %s\nwant: %s",
+				test.orig, have, want)
+			continue
+		}
+	}
+}
+
+func TestNormalizeExpr(t *testing.T) {
+	tests := []struct {
+		orig string
+		want string
+	}{
+		{`new T`, `new T()`},
+
+		{`"$x"`, `'' . $v0`},
+
+		{`$x`, `$v0`},
+		{`echo $x`, `echo $v0`},
+
+		{`!!$x`, `(bool)$v0`},
+
+		// Commutative operands are sorted if they don't have side effects.
+		{`0 == $x`, `$v0 == 0`},
+		{`$x === "abc"`, `"abc" === $v0`},
+		{`$x + $y + $x`, `$v0 + $v0 + $v1`},
+
+		{`"abc"`, `'abc'`},
+
+		{`NULL`, `null`},
+		{`MyConst`, `MyConst`},
+
+		{`is_null($x)`, `$v0 === null`},
+
+		{`is_integer($v)`, `is_int($v0)`},
+		{`is_real($v)`, `is_float($v0)`},
+
+		{`$x = $x + 2`, `$v0 += 2`},
+		{`$x = $x + 1`, `++$v0`},
+		{`$x = $x - 1`, `--$v0`},
+
+		{`array(1, 2)`, `[1, 2]`},
+		{`list($x, $y) = f()`, `[$v0, $v1] = f()`},
+
+		{`$x ? $x : $y`, `$v0 ?: $v1`},
+		{`f() ? f() : $y`, `f() ? f() : $v0`},
+	}
+
+	conf := Config{CurrentClass: `Foo`}
+	for _, test := range tests {
+		n, _, err := parseutil.ParseStmt([]byte(test.orig))
+		if err != nil {
+			t.Errorf("parse `%s`: %v", test.orig, err)
+			continue
+		}
+		irNode := irconv.ConvertNode(n)
+		normalized := FuncBody(conf, nil, []ir.Node{irNode})
+		have := strings.TrimSuffix(irfmt.Node(normalized[0]), ";")
+		if have != test.want {
+			t.Errorf("normalize `%s`:\nhave: %s\nwant: %s",
+				test.orig, have, test.want)
+			continue
+		}
+		n2, _, err := parseutil.ParseStmt([]byte(have))
+		if err != nil {
+			t.Errorf("parse normalized `%s`: %v", test.orig, err)
+			continue
+		}
+		irNode2 := irconv.ConvertNode(n2)
+		normalized2 := FuncBody(conf, nil, []ir.Node{irNode2})
+		have2 := strings.TrimSuffix(irfmt.Node(normalized2[0]), ";")
+		if have != have2 {
+			t.Errorf("second normalization of `%s`:\nhave: %s\nwant: %s",
+				test.orig, have2, have)
+		}
+	}
+}
+
+func parseStmtList(s string) ([]ir.Node, error) {
+	source := "<?php " + s
+	p := php7.NewParser([]byte(source))
+	p.Parse()
+	if len(p.GetErrors()) != 0 {
+		return nil, errors.New(p.GetErrors()[0].String())
+	}
+	rootIR := irconv.ConvertRoot(p.GetRootNode())
+	return rootIR.Stmts, nil
+}