tos-ramsize

tinyos-2.x.rar

#!/usr/bin/perl -w

# Copyright (c) 2003-2009 University of Utah and the Flux Group.
# All rights reserved.
# 
# Permission to use, copy, modify, distribute, and sell this software
# and its documentation is hereby granted without fee, provided that the
# above copyright notice and this permission/disclaimer notice is
# retained in all copies or modified versions, and that both notices
# appear in supporting documentation.  THE COPYRIGHT HOLDERS PROVIDE
# THIS SOFTWARE "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED WARRANTIES,
# INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
# MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.  THE COPYRIGHT
# HOLDERS DISCLAIM ANY LIABILITY OF ANY KIND FOR ANY DAMAGES WHATSOEVER
# RESULTING FROM THE USE OF THIS SOFTWARE.
# 
# Users are requested, but not required, to send to [e-mail]
# any improvements that they make and grant redistribution rights to the
# University of Utah.
# 
# Author: John Regehr ([e-mail])
# Revised by: Xuejun Yang on 01/10/2009 

# For more information:
#   http://docs.tinyos.net/index.php/Stack_Analysis

use strict;
use warnings;
use Getopt::Long;

# TODO: 
#
# support TOSThreads
#
# support msp430
#
# optionally don't do recursion checking
#
# print path to WC stack depth, perhaps graphically
#
# make it possible to specify chips individually
#
# make it possible to explicitly specify which interrupts are atomic
# or not
#
# tighten results by keeping track of depths inside and out of
# atomic sections
#
# print stack used at thread blocking points
#
# support overriding the default heuristic for detecting atomic
# interrupts
#
# get rid of hard-coded non-terminating functions, just derive this
# when no "ret" is executed
#
# test for tightness / soundness using randprog + Avrora
#
# read config info from a file
#   chip parameters
#   libc information
#   recursion and interrupt info

##########################################################################

my %VEC_SIZE = (
    "mica2" => 4,
    "micaz" => 4,
    "iris" => 4,
    );

my %PC_SIZE = (
    "mica2" => 2,
    "micaz" => 2,
    "iris" => 2,
    );

my %NUM_VECTORS = (
    "mica2" => 35,
    "micaz" => 35,
    "iris" => 51,
    );

my %RAM_SIZE = (
    "mica2" => 4096,
    "micaz" => 4096,
    "iris" => 8192,
    );

my %DEV_SIZE = (
    "mica2" => 256,
    "micaz" => 256,
    "iris" => 512,
    );

my %NORETURN = (
    "deputy_fail_noreturn_fast" => 1,
    );

# any icall in the function on the left is assumed to go to the
# function on the right
my %ICALL_TARGETS = (
    "fputc" => "uart_putchar",
    "puts" => "uart_putchar",
    );    

# also look below for __prologue_saves__ and __epilogue_restores__
my %SPECIAL = (

    "TinyThreadSchedulerP__switchThreads" => 10,

    # these have icalls
    #"__eewr_block" => 35,
    #"__eerd_block" => 35,

    # these peel a return address off the stack before calling into a
    # function that returns to the caller's caller
    "__fp_split1" => 0,
    "__fp_split2" => 0,
    "__fp_split3" => 0,
    "__fp_split_a" => 0,
    );

##########################################################################

my $verbosity = 1;

my $ORIGIN = 0;
my $ZERO_STACK = -999999;

my $platform;
my %insns;
my %args;
my %addr_to_label;
my %label_to_addr;
my %lines;
my %line_to_addr;
my %stack_effect;
my %successors;
my %call_targets;
my %insn_size;
my %diehere;
my %raw_text;
my %jump_lists;
my $initial_stack_depth;

sub bynum {
    return $a <=> $b;
}

sub parse_pair ($) {
    (my $pair) = @_;
    if ($pair =~ /^([a-zA-Z0-9]+)\, ([a-zA-Z0-9\+]+)$/) {
	return ($1, $2);
    } else {
	die "tos-ramsize FAIL: expected 'x, y' got '$pair'";
    }
}

sub get_relative_address ($) {
    (my $addr) = @_;
    my $code = $args{$addr};
    die "tos-ramsize FAIL" if (!($code =~ /.(\-?[0-9]+)/));
    return 2+$1;
}

sub add_insn ($$$$) {
    (my $addr, my $code, my $size, my $linenum) = @_;
    if (($code =~ /^([a-zA-Z]+)\s*(.*)?$/)) { 
	if ($verbosity > 7) {
	    print "$code\n";
	}
	$line_to_addr{$linenum} = $addr; 
	my $insn = $1;
	my $arg = $2;
	$insns{$addr} = $insn;
	$args{$addr} = $arg;
	
	if ($verbosity > 7) {
	    print "'$insn' '$arg' @ $addr\n";
	}

	$insn_size{$addr} = $size;
    } else {
	if ($verbosity > 7) {
	    print "???? $code\n";
	}
    }
}

sub disassemble ($) {
    (my $fn) = @_;
    open INF, "avr-objdump -zsD $fn |" or die "tos-ramsize FAIL: can't open input file $fn";
    my $linenum = 0;
    my $text_go = 0;
    my $raw_text_go = 0;
    my $raw_addr;
    
    while (my $line = <INF>) {
	chomp $line;

	$linenum++;
	$lines{$linenum} = $line;

	if ($line =~ m/Disassembly of section \.text/) {
	    $text_go = 1;
	    $raw_text_go = 0;
	    next;
	}

	if ($line =~ m/Contents of section \.text/) {
	    $text_go = 0;
	    $raw_text_go = 1;
	    next;
	}

	if ($line =~ m/Contents of section /) {
	    $text_go = 0;
	    $raw_text_go = 0;
	    next;
	}

	if ($line =~ m/Disassembly of section /) {
	    $text_go = 0;
	    $raw_text_go = 0;
	    next;
	}

	# skip blank line and obvious junk
	next if ($line eq "" or $line =~ /^\s*\.*$/);
	
	# kill comments
	($line =~ s/\s*;.*$//);
	
	if ($verbosity > 7) {
	    print "$line\n";
	}

	if ($raw_text_go) {
	    $line = substr $line, 0, 43;
	    $line .= " ";
	    if ($line =~ /^\s*([0-9a-f]{4}) ((([0-9a-f][0-9a-f]){1,4} ){1,4})\s*$/) {
		my $address = hex($1);
		my $bytes = $2;
		if (!defined($raw_addr)) {
		    $raw_addr = $address;
		} else {
		    die "tos-ramsize FAIL" if ($raw_addr != $address);
		}
		($bytes =~ s/\s//g);
		while (length($bytes)>0) {
		    die "tos-ramsize FAIL" if (length($bytes)==1);
		    my $b = substr $bytes, 0, 2;
		    $bytes = substr $bytes, 2, length($bytes)-2;
		    $raw_text{$raw_addr} = $b;
		    $raw_addr++;
		}
	    } else {
		print "cannot parse raw text: '$line'\n";
		die "tos-ramsize FAIL";
	    }
	}
	
	if ($text_go) {
	    # label
	    if ($line =~ /^0*([0-9a-f]+) <(.+)>:$/) {
		my $addr = hex($1);
		my $label = $2;
		$addr_to_label{$addr} = $label;
		$label_to_addr{$label} = $addr;
		next;
	    }
	    
	    # data in code segment
	    if ($line =~ /^\s+([0-9a-f]+):\s+([0-9a-fA-F][0-9a-fA-F] ){16}\s+/) {
		next;
	    }
	    
	    # regular code
	    
	    my $a;
	    my $code;

	    if ($line =~ /^\s+([0-9a-f]+):\s+([0-9a-f][0-9a-f]\s){4}\s*(.*)$/) {
		$a = hex($1);
		$code = $3;
		add_insn ($a, $code, 4, $linenum);
		next;
	    }
	    
	    if ($line =~ /^\s+([0-9a-f]+):\s+([0-9a-f][0-9a-f][ \t]){2}\s*(.*)$/) {
		$a = hex($1);
		$code = $3;
		add_insn ($a, $code, 2, $linenum);
		next;
	    }
	    
	    # paranoid: don't ignore lines that look funny
	    die "tos-ramsize FAIL: can't understand '$line'";
	}
    }

    if ($verbosity >= 2) {
	print "there are:\n";
	print "  ".scalar(keys %addr_to_label)." labels\n";
	print "  ".scalar(keys %insns)." instructions\n";
    }
    
    close INF;
}

sub is_branch ($) {
    (my $addr) = @_;
    my $insn = $insns{$addr};
    return ($insn eq "breq" || $insn eq "brge" || $insn eq "brne" ||
	    $insn eq "brcs" || $insn eq "brcc" || $insn eq "brlt" ||
	    $insn eq "brhc" || $insn eq "brhs" || $insn eq "brid" ||
	    $insn eq "brie" || $insn eq "brmi" || $insn eq "brpl" ||
	    $insn eq "brtc" || $insn eq "brts" || $insn eq "brvc" ||
	    $insn eq "brvs" || $insn eq "brbc" || $insn eq "brbs");
}

sub is_skip ($) {
    (my $addr) = @_;
    my $insn = $insns{$addr};
    return ($insn eq "sbrs" || $insn eq "sbrc" || $insn eq "cpse" ||
	    $insn eq "sbic" || $insn eq "sbis");
}

sub is_fallthrough ($) {
    (my $addr) = @_;
    my $insn = $insns{$addr};
    return (
	$insn eq "prologue_saves" || $insn eq "epilogue_restores" ||
	$insn eq "init_sp" || $insn eq "constant_push" || $insn eq "constant_pop" ||
	$insn eq "adc" || $insn eq "add" || $insn eq "adiw" ||
	$insn eq "and" || $insn eq "andi" || $insn eq "asr" ||
	$insn eq "bld" || $insn eq "break" || $insn eq "bst" ||
	$insn eq "cbi" || $insn eq "clh" || $insn eq "cli" ||
	$insn eq "cln" || $insn eq "cls" || $insn eq "clt" ||
	$insn eq "clv" || $insn eq "clz" || $insn eq "com" ||
	$insn eq "cp" || $insn eq "cpc" || $insn eq "cpi" ||
	$insn eq "dec" || $insn eq "elpm" || $insn eq "eor" ||
	$insn eq "fmul" || $insn eq "fmuls" || $insn eq "fmulsu" ||
	$insn eq "in" || $insn eq "inc" || $insn eq "ldi" ||
	$insn eq "lpm" || $insn eq "lsr" || $insn eq "mov" ||
	$insn eq "movw" || $insn eq "mul" || $insn eq "muls" ||
	$insn eq "mulsu" || $insn eq "neg" || $insn eq "nop" ||
	$insn eq "or" || $insn eq "ori" || $insn eq "out" ||
	$insn eq "pop" || $insn eq "push" || $insn eq "ror" ||
	$insn eq "sbc" || $insn eq "sbci" || $insn eq "sbi" ||
	$insn eq "sbiw" || $insn eq "seh" || $insn eq "sei" ||
	$insn eq "sen" || $insn eq "ses" || $insn eq "set" ||
	$insn eq "sev" || $insn eq "sez" || $insn eq "sleep" ||
	$insn eq "spm" || $insn eq "sub" || $insn eq "subi" ||
	$insn eq "swap" || $insn eq "wdr" || $insn eq "ld" ||
	$insn eq "ldd" || $insn eq "sec" || $insn eq "st" ||
	$insn eq "std" || $insn eq "lds" || $insn eq "sts"
	);
}

sub is_jmp ($) {
    (my $addr) = @_;
    my $insn = $insns{$addr};
    return ($insn eq "jmp" || $insn eq "rjmp");
}

sub is_direct_call ($) {
    (my $addr) = @_;
    my $insn = $insns{$addr};
    return ($insn eq "call" || $insn eq "rcall");
}

sub insn_stack_effects () {
    foreach my $addr (keys %insns) {
	my $insn = $insns{$addr};
	if ($insn eq "push") {
	    $stack_effect{$addr} = 1;
	} elsif ($insn eq "pop") {
	    $stack_effect{$addr} = -1;
	} elsif ($insn eq "ret" || $insn eq "reti") {
	    $stack_effect{$addr} = -$PC_SIZE{$platform};
	} else {
	    $stack_effect{$addr} = 0;
	}
    }
}

sub make16($$) {
    (my $l, my $h) = @_;
    return (hex($h) << 8) + hex($l);
}

sub jmp_call_target ($) {
    (my $addr) = @_;
    die "tos-ramsize FAIL" if ($insns{$addr} ne "jmp" && $insns{$addr} ne "call");
    my $code = $args{$addr};
    die "tos-ramsize FAIL" if (!($code =~ /0x([0-9a-f]+)/) && $code != 0);
    if (($code =~ /0x([0-9a-f]+)/)) {
	return hex ($1);
    } else {
	return 0;
    }
}

sub get_target ($) {
    (my $addr) = @_;
    my $insn = $insns{$addr};
    my $hex_addr = sprintf "%x", $addr;
    
    if (is_jmp ($addr) || is_direct_call ($addr)) {
        if ($insn eq "rjmp" || $insn eq "rcall") {
            return $addr + get_relative_address ($addr);
        } else {
	    return jmp_call_target ($addr);
        }
    }

    if (is_branch ($addr)) {
	return $addr + get_relative_address ($addr);
    }

    # skip size depends on size of subsequent insn
    if (is_skip ($addr)) {
	die "tos-ramsize FAIL: $hex_addr" if (!defined($insn_size{$addr}));
	my $next = $addr + $insn_size{$addr};
	if (!defined($insn_size{$next})) {
	    return $next + 2;
	} else {
	    return $next + $insn_size{$next};
	}
    }

    die "tos-ramsize FAIL";
}

sub match_branch ($$) {
    (my $addr, my $instruction) = @_;
    if (defined($insns{$addr}) && $insns{$addr} eq $instruction) { 
	return (1, get_target ($addr));
    } else {
	return (0, 0);
    }
}

sub match_2args ($$) {
    (my $addr, my $instruction) = @_;
    if (defined($insns{$addr}) && $insns{$addr} eq $instruction) { 
        (my $a, my $b) = parse_pair ($args{$addr});
	return (1, $a, $b);
    } else {
	return (0, 0, 0);
    }
}

sub match_0args ($$) {
    (my $addr, my $instruction) = @_;
    if (defined($insns{$addr}) && $insns{$addr} eq $instruction) { 
	return 1;
    } else {
	return 0;
    }
}

# ldi	r28, 0xFF	; 255
# ldi	r29, 0x21	; 33
# out	0x3e, r29	; 62
# out	0x3d, r28	; 61

sub match_init_sp ($) {
    (my $addr) = @_;
    my $match;
    my $reg;
    my $immed;
    ($match, $reg, my $sp_lo) = match_2args ($addr, "ldi");
    return (0,0,0) if (!$match || $reg ne "r28");
    ($match, $reg, my $sp_hi) = match_2args ($addr+2, "ldi");
    return (0,0,0) if (!$match || $reg ne "r29");
    ($match, $immed, $reg) = match_2args ($addr+4, "out");
    return (0,0,0) if (!$match || $reg ne "r29" || $immed ne "0x3e");
    ($match, $immed, $reg) = match_2args ($addr+6, "out");
    return (0,0,0) if (!$match || $reg ne "r28" || $immed ne "0x3d");
    my $init = make16($sp_lo,$sp_hi);
    my $init_stack = $RAM_SIZE{$platform} + $DEV_SIZE{$platform} - $init - 1;
    if ($verbosity > 3) {
	print "init = $sp_lo $sp_hi = $init = ${init_stack}\n";
    }
    return (1,8,$init_stack);
}

# cpi	r30, 0x12	; 18
# cpc	r31, r1
# brcs	.+2      	; 0x1a88 <SchedulerBasicP_xx_TaskBasic_xx_runTask+0x3e>
# rjmp	.+2218   	; 0x2332 <SchedulerBasicP_xx_TaskBasic_xx_runTask+0x8e8>
# subi	r30, 0xBA	; 186
# sbci	r31, 0xFF	; 255
# add	r30, r30
# adc	r31, r31
# lpm	r0, Z+
# lpm	r31, Z
# mov	r30, r0
# ijmp

# cpi	r16, 0x80	; 128
# cpc	r17, r1
# brcs	.+2      	; 0x13ec <__stack+0x2ed>
# rjmp	.+148    	; 0x1480 <__stack+0x381>
# subi	r16, 0xBA	; 186
# sbci	r17, 0xFF	; 255
# movw	r30, r16
# add	r30, r30
# adc	r31, r31
# lpm	r0, Z+
# lpm	r31, Z
# mov	r30, r0
# ijmp

# cpi	r30, 0x1E	; 30
# cpc	r31, r1
# brcc	.+78     	; 0x19ce <main+0x626>
# subi	r30, 0xBA	; 186
# sbci	r31, 0xFF	; 255
# add	r30, r30
# adc	r31, r31
# lpm	r0, Z+
# lpm	r31, Z
# mov	r30, r0
# ijmp

# cpi	r26, 0x48	; 72
# cpc	r27, r1
# brcc	.+38     	; 0x1954 <__stack+0x855>
# subi	r26, 0xBA	; 186
# sbci	r27, 0xFF	; 255
# movw	r30, r26
# add	r30, r30
# adc	r31, r31
# lpm	r0, Z+
# lpm	r31, Z
# mov	r30, r0
# ijmp

sub match_jump_table_1 ($) {
    (my $addr) = @_;
    my $match;
    my $reg1;
    my $reg2;
    my $immed;
    my $oob_target;
    my @targets;
    my $inc = 0;

    ($match, $reg1, my $table_size) = match_2args ($addr+$inc, "cpi");
    return (0, \@targets, 0) if (!$match);
    $inc += 2;
    
    ($match, $reg1, $reg2) = match_2args ($addr+$inc, "cpc");
    return (0, \@targets, 0) if (!$match);
    $inc += 2;

    ($match, $immed) = match_branch ($addr+$inc, "brcs");
    if ($match) {
	$inc += 2;
	($match, $oob_target) = match_branch ($addr+$inc, "rjmp");
	return (0, \@targets, 0) if (!$match);
	$inc += 2;
    } else {
	($match, $oob_target) = match_branch ($addr+$inc, "brcc");
	return (0, \@targets, 0) if (!$match);	
	$inc += 2;
    }