Using instruction set simulator on hello_world_small works:

/cygdrive/c/altera/myNios/software/hello_world_small_0
[SOPC Builder]$ nios2-iss  -f  hello_world_small.elf -p ../../system.ptf
Altera Nios II ISS Software Simulation Environment Version 5.0
Copyright (C) 2005 Altera Corporation

Info : Successfully read SOPC Builder PTF file '../../system.ptf'
Info : Configuring 'system' model
Info : PTF Setting jtag_uart_0/SYSTEM_BUILDER_INFO/Iss_Launch_Telnet="0" detecte
d
Info : 'jtag_uart_0' character stream will be displayed in this window
Info : The host communication device for stdin is jtag_uart_0
Info : The host communication device for stdout is jtag_uart_0
Info : The host communication device for stderr is jtag_uart_0
Info : Running 'system' model

Hello from Nios II!

Info : Component cpu_0's program has terminated
Info : Instructions executed = 836
Info : cpu_0 simulation return code 0
Info : Exiting system model with return code 0 (0 fatal errors, 0 errors, 0 warnings)
/cygdrive/c/altera/myNios/software/hello_world_small_0
[SOPC Builder]$

It does not work with bitrun, but the a.out file is relocatable not exec.

/cygdrive/c/altera/myNios/software
Usage: readelf  elf-file(s)
 Display information about the contents of ELF format files
 Options are:
  -a --all               Equivalent to: -h -l -S -s -r -d -V -A -I
  -h --file-header       Display the ELF file header
  -l --program-headers   Display the program headers
     --segments          An alias for --program-headers
  -S --section-headers   Display the sections' header
     --sections          An alias for --section-headers
  -e --headers           Equivalent to: -h -l -S
  -s --syms              Display the symbol table
      --symbols          An alias for --syms
  -n --notes             Display the core notes (if present)
  -r --relocs            Display the relocations (if present)
  -u --unwind            Display the unwind info (if present)
  -d --dynamic           Display the dynamic segment (if present)
  -V --version-info      Display the version sections (if present)
  -A --arch-specific     Display architecture specific information (if any).
  -D --use-dynamic       Use the dynamic section info when displaying symbols
  -x --hex-dump= Dump the contents of section 
  -w[liaprmfFso] or
  --debug-dump[=line,=info,=abbrev,=pubnames,=ranges,=macro,=frames,=str,=loc]
                         Display the contents of DWARF2 debug sections
  -I --histogram         Display histogram of bucket list lengths
  -W --wide              Allow output width to exceed 80 characters
  -H --help              Display this information
  -v --version           Display the version number of readelf
Report bugs to bug-binutils@gnu.org
/cygdrive/c/altera/myNios/software
[SOPC Builder]$ nios2-elf-readelf -h a.out
ELF Header:
  Magic:   7f 45 4c 46 01 01 01 ff 00 00 00 00 00 00 00 00
  Class:                             ELF32
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            Standalone App
  ABI Version:                       0
  Type:                              REL (Relocatable file)
  Machine:                           Altera Nios II
  Version:                           0x1
  Entry point address:               0x0
  Start of program headers:          0 (bytes into file)
  Start of section headers:          136 (bytes into file)
  Flags:                             0x0
  Size of this header:               52 (bytes)
  Size of program headers:           0 (bytes)
  Number of program headers:         0
  Size of section headers:           40 (bytes)
  Number of section headers:         7
  Section header string table index: 4
/cygdrive/c/altera/myNios/software
[SOPC Builder]$
/cygdrive/c/altera/myNios/software/hello_world_small_0
[SOPC Builder]$ nios2-elf-readelf -h hello_world_small.elf
ELF Header:
  Magic:   7f 45 4c 46 01 01 01 ff 00 00 00 00 00 00 00 00
  Class:                             ELF32
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            Standalone App
  ABI Version:                       0
  Type:                              EXEC (Executable file)
  Machine:                           Altera Nios II
  Version:                           0x1
  Entry point address:               0x1000
  Start of program headers:          52 (bytes into file)
  Start of section headers:          109172 (bytes into file)
  Flags:                             0x0
  Size of this header:               52 (bytes)
  Size of program headers:           32 (bytes)
  Number of program headers:         2
  Size of section headers:           40 (bytes)
  Number of section headers:         24
  Section header string table index: 21
/cygdrive/c/altera/myNios/software/hello_world_small_0
[SOPC Builder]$
/cygdrive/c/altera/myNios/software
[SOPC Builder]$ nios2-iss -ta:simulation.txt -e0x30 -f a.out -p ../system.ptf
Altera Nios II ISS Software Simulation Environment Version 5.0
Copyright (C) 2005 Altera Corporation

Info : Successfully read SOPC Builder PTF file '../system.ptf'
Info : Configuring 'system' model
Info : PTF Setting jtag_uart_0/SYSTEM_BUILDER_INFO/Iss_Launch_Telnet="0" detecte
d
Info : 'jtag_uart_0' character stream will be displayed in this window
Info : The host communication device for stdin is jtag_uart_0
Info : The host communication device for stdout is jtag_uart_0
Info : The host communication device for stderr is jtag_uart_0
Info : Running 'system' model


Info : Component cpu_0's program has terminated
Info : Instructions executed = 27
Info : cpu_0 simulation return code 4
Info : Exiting system model with return code 4 (0 fatal errors, 0 errors, 0 warn
ings)
/cygdrive/c/altera/myNios/software
[SOPC Builder]$ nios2-iss -ta -e0x30 -f a.out -p ../system.ptf

I devised the following shell script:

#!/bin/sh
echo "compile bitrun"
nios2-elf-gcc bitrun.s
echo "show ELF header (note location of main)"
nios2-elf-readelf -hs a.out
echo "run with instruction set simulator (starting from main)"
nios2-iss -ta:simulation.txt -e0x30 -f a.out -p ../system.ptf

Which gives the following results:

/cygdrive/c/altera/myNios/software
[SOPC Builder]$ test.sh
compile bitrun
show ELF header (note location of main)
ELF Header:
  Magic:   7f 45 4c 46 01 01 01 ff 00 00 00 00 00 00 00 00
  Class:                             ELF32
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            Standalone App
  ABI Version:                       0
  Type:                              EXEC (Executable file)
  Machine:                           Altera Nios II
  Version:                           0x1
  Entry point address:               0x0
  Start of program headers:          52 (bytes into file)
  Start of section headers:          12912 (bytes into file)
  Flags:                             0x0
  Size of this header:               52 (bytes)
  Size of program headers:           32 (bytes)
  Number of program headers:         2
  Size of section headers:           40 (bytes)
  Number of section headers:         18
  Section header string table index: 15

Symbol table '.symtab' contains 48 entries:
   Num:    Value  Size Type    Bind   Vis      Ndx Name
     0: 00000000     0 NOTYPE  LOCAL  DEFAULT  UND
     1: 00000000     0 SECTION LOCAL  DEFAULT    1
     2: 0000025c     0 SECTION LOCAL  DEFAULT    2
     3: 00000260     0 SECTION LOCAL  DEFAULT    3
     4: 000005dc     0 SECTION LOCAL  DEFAULT    4
     5: 000005e0     0 SECTION LOCAL  DEFAULT    5
     6: 000005e0     0 SECTION LOCAL  DEFAULT    6
     7: 00000000     0 SECTION LOCAL  DEFAULT    7
     8: 00000000     0 SECTION LOCAL  DEFAULT    8
     9: 00000000     0 SECTION LOCAL  DEFAULT    9
    10: 00000000     0 SECTION LOCAL  DEFAULT   10
    11: 00000000     0 SECTION LOCAL  DEFAULT   11
    12: 00000000     0 SECTION LOCAL  DEFAULT   12
    13: 00000000     0 SECTION LOCAL  DEFAULT   13
    14: 00000000     0 SECTION LOCAL  DEFAULT   14
    15: 00000000     0 SECTION LOCAL  DEFAULT   15
    16: 00000000     0 SECTION LOCAL  DEFAULT   16
    17: 00000000     0 SECTION LOCAL  DEFAULT   17
    18: 00000001     0 NOTYPE  LOCAL  DEFAULT  ABS _nios2_macros_
    19: 90abcd3f     0 NOTYPE  LOCAL  DEFAULT  ABS TEST_NUM
    20: 0000003c     0 NOTYPE  LOCAL  DEFAULT    1 string_counter
    21: 00000040     0 NOTYPE  LOCAL  DEFAULT    1 string_counter_loop
    22: 00000054     0 NOTYPE  LOCAL  DEFAULT    1 end_string_counter
    23: 00000058     0 NOTYPE  LOCAL  DEFAULT    1 end
    24: 00000000     0 FILE    LOCAL  DEFAULT  ABS nosys_crt0.c
    25: 00000000     0 FILE    LOCAL  DEFAULT  ABS _zero_bss.c
    26: 00000000     0 FILE    LOCAL  DEFAULT  ABS exit.c
    27: 00000000     0 FILE    LOCAL  DEFAULT  ABS impure.c
    28: 00000260   892 OBJECT  LOCAL  DEFAULT    3 impure_data
    29: 00000000     0 FILE    LOCAL  DEFAULT  ABS memset.c
    30: 00000000     0 FILE    LOCAL  DEFAULT  ABS nosys_exit.c
    31: 0000005c     4 FUNC    GLOBAL DEFAULT    1 __fake_init
    32: 000085d0     0 NOTYPE  GLOBAL DEFAULT  ABS _gp
    33: 00000060    64 FUNC    GLOBAL DEFAULT    1 __start_2
    34: 000000a0    12 FUNC    GLOBAL DEFAULT    1 _zero_bss
    35: 0000005c     4 FUNC    WEAK   DEFAULT    1 _init
    36: 00000000     0 FUNC    GLOBAL DEFAULT    1 _start
    37: 0000022c     4 FUNC    GLOBAL DEFAULT    1 __fake_fini
    38: 000005e0     0 NOTYPE  GLOBAL DEFAULT  ABS __bss_start
    39: 00000190   156 FUNC    GLOBAL DEFAULT    1 memset
    40: 00000030     0 FUNC    GLOBAL DEFAULT    1 main
    41: 0000022c     4 FUNC    WEAK   DEFAULT    1 _fini
    42: 000005dc     4 OBJECT  GLOBAL DEFAULT    4 _impure_ptr
    43: 07ffff00     0 NOTYPE  GLOBAL DEFAULT  ABS nasys_stack_top
    44: 000005e0     0 NOTYPE  GLOBAL DEFAULT  ABS _edata
    45: 000005e0     0 NOTYPE  GLOBAL DEFAULT  ABS _end
    46: 000000ac   228 FUNC    GLOBAL DEFAULT    1 exit
    47: 00000230    44 FUNC    GLOBAL DEFAULT    1 _exit
run with instruction set simulator (starting from main)
Altera Nios II ISS Software Simulation Environment Version 5.0
Copyright (C) 2005 Altera Corporation

Info : Successfully read SOPC Builder PTF file '../system.ptf'
Info : Configuring 'system' model
Info : PTF Setting jtag_uart_0/SYSTEM_BUILDER_INFO/Iss_Launch_Telnet="0" detecte
d
Info : 'jtag_uart_0' character stream will be displayed in this window
Info : The host communication device for stdin is jtag_uart_0
Info : The host communication device for stdout is jtag_uart_0
Info : The host communication device for stderr is jtag_uart_0
Info : Running 'system' model


Info : Component cpu_0's program has terminated
Info : Instructions executed = 37
Info : cpu_0 simulation return code 6
Info : Exiting system model with return code 6 (0 fatal errors, 0 errors, 0 warn
ings)
/cygdrive/c/altera/myNios/software
[SOPC Builder]$