For style and formatting, your asm is pretty good except for label names. Correctly indented, and some intro comments about register usage. But missing comments about even the major steps of the algorithm on any of the instructions or labels.
It would also help to leave a blank line after the end of a loop, so it's easier to see that later code isn't going to jump back into it. It's a good place to put a comment about what invariants are now true, or what the next code does.
As other answers point out, your algorithm is doing way too much work, using malloc/free (and in asm, effectively alloca) and copying your data twice, instead of just figuring out how far to memmove it.
Beyond that, you have multiple other major and minor implementation details that could be more efficient.
(Important background reading: https://agner.org/optimize/ has lots of important micro-optimization stuff, some of which I'm going to point out specifically. If you don't know what micro-uops (uops) are, go read Agner's asm optimization guide and micro-architecture guide. Also this SO Q&A and/or some of the links from my answer. Also a good idea to use compiler-generated asm as a starting-point for your hand-written asm, because compilers generally get the small details right, and might lay out the branching nicely. (If not you can try [[likely]] somewhere and try again).)
Also, not using SIMD means you can at best check 1 byte at a time, not 16 or 32. SSE2 is baseline for x86-64, so any string processing like this should be using SIMD unless you expect strings to be tiny, like less than 8 bytes or so. (Or as a baby-steps learning exercise just to write correct scalar code, not useful for performance.) With some loop unrolling, scalar could possibly check 2 bytes per clock cycle, but branching on a SIMD compare takes more work. Still a big speedup available.
You might hope that a good C compiler could optimize simple loops to use SIMD, but unfortunately existing compilers like GCC and clang can only auto-vectorize loops where the trip-count can be computed before the first iteration. i.e. not search loops with a data-dependent exit condition. (ICC can sometimes vectorize search loops, and sometimes even do a decent job at it IIRC.) So this is actually a problem where it does make sense to get your hands dirty and use SIMD intrinsics. There's little need to hand-write anything in assembly, though, especially for x86 where compilers do a good job with intrinsics.
You might also hope that repe scasb would be efficient, but it's not, unfortunately.
Only the unconditional rep movs and rep stos instructions have Fast Strings microcode. (See Why is this code using strlen heavily 6.5x slower with GCC optimizations enabled? for how GCC used to inline an inefficient strlen at -O1 or -O2 in some cases, vs. my simple example of a 16-byte-at-a-time SSE2 implementation that assumes an aligned buffer.)
Use more concise label names, prefer NASM local labels like .else:
Asm label names are private to the current file, like static function names or goto labels within a function in C. You don't need to make them globally unique since you're not using global foo to export them.
It took me half a minute or so to figure out the naming pattern with labels like _after_remove_leading_zeroes_if_1 vs. _remove_leading_zeroes_loop_2. The "if" vs. "loop" part is a very small part of the label. It seems obvious in hindsight once you know where to look, but on reading the code for the first time, my reaction was "what is this mess of mostly-redundant long label names? Hard to see what jumps where". Then wondering why are there two different _2 labels, then finally seeing the if vs. while naming (which also apparently go with _after_remove... vs. _remove... for no apparent reason since the last label in the function isn't named "after".
Meaningful label names are tricky, so yeah you might sometimes just give up and number them from a common base.
In NASM, .bar: following a non-dot label like foo: is the same as foo.bar:, so it lets you use short label names but still avoid name conflicts with the rest of your file.
So you could have asm like
remove_leading_zeroes: ; in Linux ELF, C names don't get leading underscores
...
je .no_lz
; else fall through
.find_nonzero:
...
jne .find_nonzero
.strmove: ; in-place strcpy to fill the gap
...
jne .strmove
.no_lz: ; return without copying anything
ret
Make two loops instead of branching inside loops
do {
if (rdi[r9] != '0')
cl = true;
if (cl) {
rsp[r8] = rdi[r9];
r8++;
}
r9++;
} while (r9 < strlen(rdi));
This is searching for the first non-'0' byte in the input string, and then copying the rest of the string to another buffer. There's no reason to put those two things into one loop, and force yourself to write asm that branches inside each iteration to figure out what to do that iteration.
It wastes at least one uop every iteration, and one side of the if is going to have an extra taken branch every iteration for that phase. (Taken branches are more expensive for the front-end, since code-fetch isn't contiguous and branch prediction has to provide a correct prediction of the new place to fetch from early enough to avoid a bubble. Also, on Haswell and later, predicted-taken jump uops can only execute on port 6; the other ALU port that can check branch predictions can only handle predicted-not-taken branches.)
There's no upside; it would be more efficient to make a simple search loop, and then strcpy (manually implemented or not). If you need some extra logic to detect the case of an all-zero string, that logic can be outside any loops. Small static code-size is nice, but fewer instructions inside loops is usually more important.
I think the simplest way to handle the possibility of an input like "0000" or the empty string is to copy the first byte unconditionally, before doing anything else. That also lets the CPU get started on getting write access to the output buffer, in case it was cold in cache or TLB, letting out-of-order exec hide latency. Normally not a factor for stack space, it's usually hot in cache. (If you can't allocate the output buffer until after reading all of the input to calculate the size, that's unfortunate. Depending on your allocator, over-allocating and then using realloc to give back a chunk at the end might be ok.)
Of course this problem goes away when you're doing it in-place, not copying to a separate buffer. Once you make that other algorithmic change, you can't use ISO C strcpy since it has undefined behaviour if the src and dst overlap. So you would need to hand-roll your copy loop for that in asm, or in C use strlen and memmove, or intrinsics like _mm_cmpeq_epi8. Pure ISO C doesn't give you the building blocks you need to make an efficient version of this function, given limitations of current compilers, so the best you can portably do in C is glue together hand-written asm building blocks like strlen and memmove, even though that makes two passes over the data.
(Perhaps cache-block it in 16KiB chunks with memchr instead of strlen, so you stop after 16K and can memmove while that part of the data is still hot in L1d cache.)
In asm you can potentially do as well as the hand-written libc code, most simply by using a copy of it. https://codebrowser.dev/glibc/glibc/sysdeps/x86_64/multiarch/strlen-avx2.S.html shows a version of glibc's strlen; with minor changes you could adapt it or memchr to look for a non-match of '0'. (That would cover finding the terminating 0 byte). Or pick any other asm strlen or memchr you want. Most should be safe for the case where dst is at a lower address than src: reads will happen before writes so it should be reading pristine data.
Depending on the input buffer, you might also have to worry about alignment, e.g. a 2 byte string in the last 2 bytes of a page, followed by an unmapped page. A 16-byte load would segfault. (Or if the next page is mapped, still be expensive, worst case even paging it in from disk if it didn't otherwise need to be touched.) See Is it safe to read past the end of a buffer within the same page on x86 and x64? - an aligned 16 or 32-byte load can never be split across a wider alignment boundary like 4k. So if your input buffer is always aligned, or always at least 32 bytes allocated, this is trivial: do the first 16-byte vector unaligned, then do (p + 32) & -32 and stay aligned from there.
Micro-optimizations
Some of these instructions are ones you won't need after algorithmic changes, but in other functions you might still want to do something similar. Some of them will still be needed in different forms.
Prefer pointer-increments over indexed addressing modes
cmp byte [rdi + r9], 48 / jz will decode to 3 uops for the front-end on Intel Skylake CPUs. Micro-fusion is defeated by the indexed addressing mode (2 registers), and macro-fusion of the cmp/jnz doesn't happen with cmp mem,imm (See What is instruction fusion in contemporary x86 processors?).
This also saves registers; you just need an input and an output pointer. (And an end-pointer or a down-counter).
The loop structure should be something like for(char *p = start, *endp = start+len ; p<endp ; p++) { stuff with *p; }. But of course in a do{}while() style like you're doing, with the conditional branch at the bottom. That's a very Good Thing. Generating endp = start+len just takes an LEA, and then the bottom of the loop is still a cmp/jne or jb. Otherwise you might use dec ecx/jnz or whatever for a loop like do{ p++ }while(--len);. Intel CPUs can macro-fuse dec/jnz, but AMD CPUs can only macro-fuse CMP or TEST. So it can save a uop inside the loop to do a pointer compare, at the cost of needing an LEA at the start.
Of course this only applies to counted loops in the first place, and after the algorithmic changes you wouldn't have those, just search loops. But you'd still have pointers that you increment, first read-only for the first non-'0', then from there and from the start to copy, checking for a terminating 0.
In a loop where you're going to want that byte in a register later (to store), you should just load it into a register now and test it there.
movzx eax, byte [rdi] ; 1 uop, no false dependency on the old RAX
cmp al, '0' ; macro-fused with jnz
jnz ; 1 uop
; 2 total uops for the front-end, 2 for the back-end.
(Write ASCII characters as character literals like '0', not 48)
Also, use jb or ja for comparing pointers, or jl/jg for comparing signed integers. You did
cmp r9, r8
js ...
This is different from jl if the subtraction has signed overflow. That's normally not going to be a problem with 64-bit integers that work as offsets to an address, because the middle of the address space (around the signed-overflow wrapping point) is non-canonical. See Should pointer comparisons be signed or unsigned in 64-bit x86?
For performance, js won't macro-fuse with cmp on Intel CPUs, but jl and jb will.
Also, for human readers, jumping on less-than has the right semantic meaning of do{}while(r9<r8) like you wrote in your C source. Jumping if the subtraction result is negative (after wrapping) does not.
Use movzx for byte loads, especially in loops
movzx avoids false dependencies on CPUs more recent than Nehalem and first-generation Sandybridge. See Why doesn't GCC use partial registers?.
Similarly, mov ecx, 1 or xor ecx,ecx for a boolean. Don't write partial registers if you don't need to.
In fact, always xor-zero with 32-bit operand-size, even for registers that need a REX prefix to access, because early Silvermont CPUs only recognize xor r8d,r8d as a zeroing idiom, not xor r8,r8. See details in What is the best way to set a register to zero in x86 assembly: xor, mov or and?
inc rax
sub rsp, rax
dec rax
Normally you'd want to keep the stack aligned by 16, and there's no need to change RAX when you want that value later; you could add into a different register.
lea rcx, [rax+1 + 15] ; rax+1 for the extra byte, and +15 as part of (x+15)&-16 to round up to the next multiple of 16
and rcx, -16
sub rsp, rcx ; alignas(16) char buf[rax+1]
To save code-size, if your string will always be less than 4GiB you can use ecx for LEA and AND (32-bit operand-size is the default in x86-64 machine code with no prefixes). On a CPU without partial-register stalls, and cl, -16 would also work efficiently, since the only bits you're clearing are in the low byte so it works to leave the rest unmodified. Same as and rcx, -16 but without needing a REX prefix.
push rbp
mov rbp, rsp
...
leave
That is useful if you variably modify RSP. Otherwise don't do it. Once you fix the algorithm, there's no need to touch stack space.
malloc()- it's avoid*, which converts implicitly to any pointer type. \$\endgroup\$movdqu xmm0, [rdi]) not crossing into the next page, especially an unmapped page? \$\endgroup\$strlennot modifying RDI, but that register is call-clobbered. (What registers are preserved through a linux x86-64 function call). On Linux/glibc, RDI is probably left pointing to the last aligned cache-line of the string, or something like that. Also, you have a leading_in the function name, but this is supposed to be for Linux. \$\endgroup\$