[U-Boot,RFC/PATCH] tools: New 'spl-stackusage' script

diff --git a/tools/spl-stackusage/spl-stackusage b/tools/spl-stackusage/spl-stackusage
new file mode 120000
index 0000000..eb10b9e
--- /dev/null
+++ b/tools/spl-stackusage/spl-stackusage
@@ -0,0 +1 @@ 
+spl-stackusage.rb
\ No newline at end of file
diff --git a/tools/spl-stackusage/spl-stackusage.rb b/tools/spl-stackusage/spl-stackusage.rb
new file mode 100755
index 0000000..a135d6c
--- /dev/null
+++ b/tools/spl-stackusage/spl-stackusage.rb
@@ -0,0 +1,471 @@ 
+#!/usr/bin/env ruby
+#
+# Copyright © 2015 Siarhei Siamashka <siarhei.siamashka@gmail.com>
+#
+# This program is free software; you can redistribute it and/or
+# modify it under the terms of the GNU General Public License
+# as published by the Free Software Foundation; either version 2
+# of the License, or (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
+
+###############################################################################
+# This is a u-boot SPL stack usage analysis script. Needs to be run           #
+# from the root of the u-boot source tree after a successful SPL build.       #
+#                                                                             #
+# Produces 'spl-stackusage.png' file as the output.                           #
+###############################################################################
+
+require 'find'
+
+###############################################################################
+# Process command line arguments
+#
+# add_node[node_name, stack_usage]
+# remove_node[node_name, stack_usage]
+# add_arrow[node_name1, node_name2]
+# remove_arrow[node_name1, node_name2]
+#
+###############################################################################
+
+$removed_arrows = {}
+
+ARGV.each {|a|
+  a.split(";").each {|a|
+    if a =~ /remove_arrow[\(\[]\s*(\S+)\s*\,\s*(\S+)\s*[\)\]]/
+      $removed_arrows[[$1, $2]] = 1
+    end
+  }
+}
+
+###############################################################################
+
+if !File.directory?("spl")
+  abort("Error: can't find the 'spl' directory.\n" +
+        "Please ensure that you are in the root of the u-boot source tree.\n")
+end
+
+def tool_exists(tool_name)
+    `which #{tool_name} > /dev/null 2>&1`
+    return $?.to_i == 0
+end
+
+if !tool_exists("dot")
+  abort("Please install the graphviz dot tool.\n")
+end
+
+###############################################################################
+# Get objdump log                                                             #
+###############################################################################
+
+# Get the information from the environment
+$toolchain = ENV["CROSS_COMPILE"]
+
+# Try to guess the ARM toolchain automatically
+if !$toolchain && `file spl/u-boot-spl` =~ / ARM, /
+  toolchain_list = [
+    "arm-none-linux-gnueabi-",
+    "armv7a-hardfloat-linux-gnueabi-",
+    "arm-linux-gnueabihf-"
+  ]
+  toolchain_list.each {|toolchain|
+    if tool_exists("#{toolchain}objdump")
+      $toolchain = toolchain
+      break
+    end
+  }
+end
+
+if !$toolchain
+  abort("Error: can't find a usable toolchain.\n" +
+        "Try to set the CROSS_COMPILE environment variable.\n")
+end
+
+$objdump_dis_log = `#{$toolchain}objdump -d -M reg-names-raw spl/u-boot-spl`
+$objdump_sym_log = `#{$toolchain}objdump -t spl/u-boot-spl`
+$size_log = `#{$toolchain}size spl/u-boot-spl`
+
+File.open("spl-stackusage.dis", "w").write($objdump_dis_log)
+File.open("spl-stackusage.sym", "w").write($objdump_sym_log)
+
+###############################################################################
+# Read the *.su files (generated by GCC with '-fstack-usage' option)          #
+###############################################################################
+
+$dynamic_stack_size = {}
+$self_stack_size = {}
+$total_stack_size  = {}
+
+Find.find("spl") { |filename|
+  next unless filename =~ /.*\.su$/
+  File.open(filename).each_line {|l|
+    if l =~ /\:([^\:\s]+)\s+(\d+)\s+(\S+)$/
+      case $3
+      when "dynamic"
+        $dynamic_stack_size[$1] = true
+      when "static"
+        $self_stack_size[$1] = [$2.to_i, ($self_stack_size[$1] || 0)].max
+      else
+        abort("Unsupported stack usage type #{$3} in #{filename}\n")
+      end
+    end
+  }
+}
+
+if $self_stack_size.size == 0
+  abort("Error: could not load anything from *.su files in 'spl' directory.\n" +
+        "Please ensure that you are using '-fstack-usage' GCC option.\n")
+end
+
+###############################################################################
+# Parse the objdump log                                                       #
+###############################################################################
+
+$detected_cycles = {}
+$labels = {}
+$arrows = {}
+$functions = {}
+$func_code = {}
+$datastructs = {}
+$refs = {}
+$xrefs = {}
+$max_stack_size = 0
+$critical_path = {}
+$shortest_cycle = nil
+$indirect_targets = {}
+$indirect_sources = {}
+$blue_arrows = {}
+
+# Stack usage, based on inspecting disassembly listing in objdump log
+def guess_func_stack_usage(func_name)
+  func_code = $func_code[func_name]
+  if !func_code
+    printf("No function code for '%s'\n", func_name)
+    return nil
+  end
+  stack_usage = 0
+  func_code.each_line { |l|
+    # 'push {reglist}' instruction
+    if l =~ /push\s+\{\s*(.*?)\s*\}/
+      reglist = $1.split(",")
+      abort("Register ranges are not supported") if $1 =~ /\-/
+      stack_usage += reglist.size * 4
+    end
+    # 'sub sp, sp, #imm' instruction
+    if l =~ /sub\s+r13\s*\,\s*(r13\s*)\,\s*\#(\d+)/
+      stack_usage += $2.to_i
+    end
+  }
+  return stack_usage
+end
+
+# Stack usage, based on parsing *.su files
+def get_func_stack_usage(func_name)
+  stack_usage = $self_stack_size[func_name]
+  stack_usage = guess_func_stack_usage(func_name) if !stack_usage
+  return stack_usage
+end
+
+$objdump_sym_log.each_line {|l|
+  # 000034c8 l     F .text	000000c8 twsi_i2c_read
+  next unless l =~ /^(\h+)\s+\S+\s+(\S+)\s+(\.\S+)\s+\h+.*?\s+(\S+)\s*$/
+  addr = $1
+  type = $2
+  sect = $3
+  name = $4
+  if type == "F" && sect == ".text"
+    $functions[name] = addr.to_i(16)
+  else
+    $datastructs[name] = addr.to_i(16)
+  end
+}
+
+$functions.each { |func, _|
+  if $dynamic_stack_size.has_key?(func)
+    abort("dynamic stack size in #{func}")
+  end
+}
+
+Find.find("spl") { |filename|
+  next unless filename =~ /.*\.o$/
+  skipflag = false
+  current_section = ""
+  `#{$toolchain}objdump -r #{filename}`.each_line {|l|
+    if l =~ /RELOCATION RECORDS FOR/
+      if l =~ /\[\.text\.(.*?)\]/
+        skipflag = !$functions.has_key?($1)
+      elsif l =~ /\[\.(data|rodata)\.(.*?)\]/
+        skipflag = !$datastructs.has_key?($2)
+      else
+        skipflag = false
+      end
+    end
+
+    next if skipflag
+
+    if l =~ /(\S+)\s+(\S+)\s+(\S+)/
+      reltype = $2
+      name    = $3
+      next if !$functions.has_key?(name)
+      next if reltype == "R_ARM_CALL" || reltype == "R_ARM_JUMP24"
+      next if reltype == "R_ARM_THM_CALL" || reltype == "R_ARM_THM_JUMP24"
+      $indirect_targets[name] = 1
+    end
+  }
+}
+
+def add_ref(current_func, func_name)
+  return if $removed_arrows.has_key?([current_func, func_name])
+
+  $arrows[[current_func, func_name]] = 1
+  $refs[current_func] = {} if !$refs.has_key?(current_func)
+  $refs[func_name] = {} if !$refs.has_key?(func_name)
+  $refs[current_func][func_name] = true
+
+  $xrefs[current_func] = {} if !$xrefs.has_key?(current_func)
+  $xrefs[func_name] = {} if !$xrefs.has_key?(func_name)
+  $xrefs[func_name][current_func] = true
+end
+
+# First pass, collect local aliases
+current_func = "entry"
+current_label = "entry"
+$label_to_func_mapping = {}
+$objdump_dis_log.each_line {|l|
+  current_label = $1 if l =~ /^\h+\s+\<(.*?)>\:$/
+  current_func = $1 if l =~ /^\h+\s+\<(.*?)>\:$/ && $functions.has_key?($1)
+  $label_to_func_mapping[current_label] = current_func
+}
+
+current_func = "entry"
+$objdump_dis_log.each_line {|l|
+  current_func = $1 if l =~ /^\h+\s+\<(.*?)>\:$/ && $functions.has_key?($1)
+  if l =~ /(.*?)\<(.*?)(\+0x\h+)?\>/
+    target_func = $label_to_func_mapping[$2]
+    add_ref(current_func, target_func) if target_func != current_func
+  end
+  if l =~ /\s+blx?\s+r/
+    $indirect_sources[current_func] = 1
+  end
+  if l =~ /\s+bx?\s+r/ && !(l =~ /\s+bx?\s+r14/)
+    $indirect_sources[current_func] = 1
+  end
+  $func_code[current_func] = "" unless $func_code.has_key?(current_func)
+  $func_code[current_func] << sprintf("%s\n", l.strip)
+}
+
+###############################################################################
+# Handle indirect calls                                                       #
+###############################################################################
+
+$functions["<indirect-call>"] = 1
+$self_stack_size["<indirect-call>"] = 0
+
+$multiplexed_indirect_sources = $indirect_sources.clone
+$multiplexed_indirect_targets = $indirect_targets.clone
+
+# A function can't indirectly call itself (that would be a recursion)
+$indirect_sources.each {|src, _|
+  $removed_arrows[[src, src]] = 1
+}
+# A function can't indirectly call its caller (that would be a recursion)
+$refs.each {|src, dst_list|
+  dst_list.each {|dst, _|
+    $removed_arrows[[dst, src]] = 1
+  }
+}
+
+def impossible_indirect_call(bad_src, bad_dst)
+  return unless $multiplexed_indirect_sources.has_key?(bad_src)
+  return unless $multiplexed_indirect_targets.has_key?(bad_dst)
+
+  if $multiplexed_indirect_sources.size < $multiplexed_indirect_targets.size
+    $multiplexed_indirect_sources.delete(bad_src)
+    $multiplexed_indirect_targets.each {|dst, _|
+      next if dst == bad_dst
+      newarrow = [bad_src, dst]
+      if !($removed_arrows.has_key?(newarrow))
+        add_ref(newarrow[0], newarrow[1])
+        $blue_arrows[newarrow] = 1
+      end
+    }
+  else
+    $multiplexed_indirect_targets.delete(bad_dst)
+    $multiplexed_indirect_sources.each {|src, _|
+      next if src == bad_src
+      newarrow = [src, bad_dst]
+      if !($removed_arrows.has_key?(newarrow))
+        add_ref(newarrow[0], newarrow[1])
+        $blue_arrows[newarrow] = 1
+      end
+    }
+  end
+end
+
+$removed_arrows.each {|k, _|
+  impossible_indirect_call(k[0], k[1])
+}
+
+$multiplexed_indirect_sources.each {|src, _|
+  newarrow = [src, "<indirect-call>"]
+  add_ref(newarrow[0], newarrow[1])
+  $blue_arrows[newarrow] = 1
+}
+
+$multiplexed_indirect_targets.each {|dst, _|
+  newarrow = ["<indirect-call>", dst]
+  add_ref(newarrow[0], newarrow[1])
+  $blue_arrows[newarrow] = 1
+}
+
+###############################################################################
+
+def recursive_walk(node, visited_nodes, depth, total_stack)
+  $total_stack_size[node] = [total_stack, ($total_stack_size[node] || 0)].max
+  if $total_stack_size[node] > $max_stack_size
+    $critical_path = visited_nodes.clone
+    $max_stack_size = $total_stack_size[node]
+  end
+  $refs[node].each {|next_node, _|
+    func_stack = get_func_stack_usage(next_node)
+    if visited_nodes.has_key?(next_node) then
+      # Find shortest cycle
+      tmp = visited_nodes.sort {|a, b| a[1] <=> b[1]}.map {|a| a[0]}
+      idx = tmp.find_index(next_node)
+      tmp = tmp.slice(idx, tmp.size - idx)
+      $shortest_cycle = tmp if !$shortest_cycle
+      $shortest_cycle = tmp if tmp.size < $shortest_cycle.size
+      $detected_cycles[[node, next_node]] = 1
+      next
+    end
+    visited_nodes[next_node] = depth if next_node != "<indirect-call>"
+    recursive_walk(next_node, visited_nodes, depth + 1,
+                   total_stack + func_stack)
+    visited_nodes.delete(next_node)
+  }
+end
+
+# Find the 'root' nodes and recursively traverse the graph starting from them
+$xrefs.each {|func_name, nodes|
+  next if nodes.size != 0
+  visited_nodes = {}
+  depth = 0
+  visited_nodes[func_name] = depth
+  recursive_walk(func_name, visited_nodes, depth + 1,
+                 get_func_stack_usage(func_name))
+}
+
+###############################################################################
+# Generate .dot file for graphviz                                             #
+###############################################################################
+
+$legend = ""
+$max_stack_size = $total_stack_size.map { |k, v| v }.max
+
+def format_path_arr(path_arr)
+  result = ""
+  (path_arr + [path_arr[0]]).each_cons(2) { |a|
+    normal_call   = $refs[a[0]].has_key?(a[1]) &&
+                    !$blue_arrows.has_key?([a[0], a[1]])
+    indirect_call = ($refs[a[0]].has_key?("<indirect-call>") &&
+                     $refs["<indirect-call>"].has_key?(a[1])) ||
+                     $blue_arrows.has_key?([a[0], a[1]])
+    if normal_call
+      result << sprintf("%s > ", a[0])
+    elsif indirect_call
+      result << sprintf("%s ? ", a[0])
+    else
+      result << sprintf("%s ! ", a[0])
+    end
+  }
+  return result + path_arr[0]
+end
+
+if $size_log =~ /(\d+)\s+(\d+)\s+(\d+)\s+(\d+)\s+(\h+)\s+spl\/u\-boot\-spl/
+    text_plus_data_size = $1.to_i + $2.to_i
+    bss_size = $3.to_i
+
+    $legend << sprintf("------------ u-boot SPL ------------\\l")
+    $legend << sprintf("text+data   = %5d bytes\\l", text_plus_data_size)
+    $legend << sprintf("bss         = %5d bytes\\l", bss_size)
+    $legend << sprintf("stack usage = %5d bytes\\l", $max_stack_size)
+end
+
+if $detected_cycles.size != 0
+  $legend << sprintf("--------------------------------------\\l")
+  $legend << sprintf("Warning, recursion suspected:\\l\\\"%s\\\"\\l",
+                     format_path_arr($shortest_cycle))
+  $legend << sprintf("\\lWhere:")
+  $legend << sprintf("\\l  '>' - means normal function call")
+  $legend << sprintf("\\l  '?' - indirect call (via a pointer)\\l")
+  $legend << sprintf("\\lBlue arrows highlight possible indirect calls")
+  $legend << sprintf("\\lgoing through a fake multiplexer node. Red")
+  $legend << sprintf("\\larrows highlight possible cases of recursion")
+  $legend << sprintf("\\lon the callgraph. Recursion is bad because it")
+  $legend << sprintf("\\lmakes stack usage estimation unpredictable.\\l")
+  $legend << sprintf("\\lThe recursion warnings can be eliminated by:")
+  $legend << sprintf("\\l  1) Fixing the SPL code if it is really broken.")
+  $legend << sprintf("\\l  2) Incorrectly guessed indirect calls can")
+  $legend << sprintf("\\l     be suppressed by using one or more")
+  $legend << sprintf("\\l     'remove_arrow[caller,callee]' command")
+  $legend << sprintf("\\l     line arguments passed to the script.\\l")
+  $legend << sprintf("\\lThe nodes on the execution path with maximized")
+  $legend << sprintf("\\lstack usage are orange colored.\\l")
+end
+
+fh = File.open("spl-stackusage.dot", "w")
+
+$refs.each {|func_name, nodes|
+  $labels[func_name] = sprintf("%s\\n[total=%d, self=%d]",
+                               func_name,
+                               $total_stack_size[func_name],
+                               get_func_stack_usage(func_name))
+}
+
+fh.printf("digraph graphname {\n")
+fh.printf("rankdir=LR;\n")
+fh.printf("node [shape=box,fontname=helvetica];\n")
+
+$total_stack_size.each { |k, v|
+  extra = ""
+  shape = "box"
+  shape = "octagon" if $indirect_sources.has_key?(k)
+  shape = "doubleoctagon" if $indirect_targets.has_key?(k)
+  if $critical_path.has_key?(k)
+    extra = ",style=filled,fillcolor=orange,group=main"
+  end
+  if k == "<indirect-call>"
+    shape = "oval"
+    extra = ",style=filled,fillcolor=lightblue"
+  end
+  fh.printf("\"%s\" [shape=#{shape}#{extra}];\n", $labels[k])
+}
+
+$arrows.each {|k, v|
+  if $detected_cycles.has_key?(k) then
+    fh.printf("\"%s\" -> \"%s\" [color=\"red\",penwidth=3];\n",
+              $labels[k[0]], $labels[k[1]])
+  elsif $blue_arrows.has_key?(k) then
+    fh.printf("\"%s\" -> \"%s\" [color=blue];\n",
+              $labels[k[0]], $labels[k[1]])
+  else
+    fh.printf("\"%s\" -> \"%s\";\n", $labels[k[0]], $labels[k[1]])
+  end
+}
+fh.printf("legend [shape=box,style=filled,fontname=monospace,fontsize=24," +
+          "color=\"lightgray\",label=\"#{$legend}\"];\n")
+fh.printf("}\n")
+fh.close
+
+printf("Execution path with maximized stack usage (%d bytes):\n%s\n",
+       $max_stack_size,
+       format_path_arr($critical_path.invert.sort.map { |a| a[1] }))
+
+`dot -Tpng -o spl-stackusage.png spl-stackusage.dot`