BMardle
Posts: 111
Joined: Wed Feb 13, 2013 4:00 pm
Location: Isle of Wight

BL instruction vs. basic blocks

Sun Dec 01, 2019 3:59 pm

Hi, all.
I'm back at trying to write a compiler targetted on ARM again (for amusement/masochism).
I know basic blocks usually (by definition) end with a branch/jump (or if the next instruction is a branch target), but I'm wondering whether it'd be simpler for my compiler to regard BL as a not-a-branch. After all (ignoring exceptions), the next instruction will be executed.
Can anyone think of a reason why a BL can't be in the middle of a basic block, i.e. that it differs from an instruction with lots of potential side-effects?
Bruce Mardle. "You know I yearn for a simpler time of barn dances and buggy rides before life was cheapened by heartless machines."

LdB
Posts: 1311
Joined: Wed Dec 07, 2016 2:29 pm

Re: BL instruction vs. basic blocks

Tue Dec 03, 2019 1:08 am

I can't work out what you mean the BL instruction is always going to branch it will NEVER execute the next instruction (it has no condition)
It literally means take the program counter (PC) copy to the link register (LR) and branch.

Functionally it is exactly equal to

Code: Select all

MOV R14, PC
B address

BMardle
Posts: 111
Joined: Wed Feb 13, 2013 4:00 pm
Location: Isle of Wight

Re: BL instruction vs. basic blocks

Tue Dec 03, 2019 9:09 am

All true, LdB. I meant that sooner or later LR will be copied back to PC and then the next instruction will be executed.
Thanks for reminding me about conditional instructions, though!
Bruce Mardle. "You know I yearn for a simpler time of barn dances and buggy rides before life was cheapened by heartless machines."

hippy
Posts: 6223
Joined: Fri Sep 09, 2011 10:34 pm
Location: UK

Re: BL instruction vs. basic blocks

Tue Dec 03, 2019 10:48 am

LdB wrote:
Tue Dec 03, 2019 1:08 am
I can't work out what you mean the BL instruction is always going to branch it will NEVER execute the next instruction (it has no condition)
Though where BL is used in most code, to call a subroutine, after it has branched, an RTS will usually be executed which causes the code to return to after the BL and the next instruction would be executed.

If one were writing a code traversing disassembler, BL would normally be treated as a 'branch and execute next instruction'. Having two paths of execution rather than just the one of a pure branch or a fall through to next instruction.

But on ARM it's not guaranteed a BL is a jump to subroutine. It could be used as an obtuse way of implementing a B branch without any return, even used as a means to trip-up and thwart code traversing disassemblers.

But, while this is important when it comes to disassembly, I don't understand why it would be an issue for a compiler other than in determining where 'dead code' is or optimising code.

I also don't understand the OP's reference to 'basic blocks' or what 'side-effects' of instructions are, why they are being tracked, why they need to be known. If it's tracking 'known system state' as code is being emitted that would normally be set to unknown after a BL.

LdB
Posts: 1311
Joined: Wed Dec 07, 2016 2:29 pm

Re: BL instruction vs. basic blocks

Tue Dec 03, 2019 12:55 pm

It's actually far worse than that hippy on many arm compilers BL is a pseudo code like LDR and you need to treat it as such

This is how keil describes it
http://www.keil.com/support/man/docs/ar ... 865686.htm
Machine-level BL instructions have restricted ranges from the address of the current instruction. However, you can use these instructions even if label is out of range. Often you do not know where the linker places label. When necessary, the linker adds code to enable longer branches. The added code is called a veneer.
The opcode itself only has 24-bit immediate branch offset (plus or minus 32MB offset) but the veneer usually extends that to the entire address space.

The reason is for exactly what you said it is usually used for calls to subroutines and only being able to call a subroutine 32MB away is pretty limiting. You could easily get to the situation that it was impossible to get all needed code blocks close enough to be able to call.

BMardle
Posts: 111
Joined: Wed Feb 13, 2013 4:00 pm
Location: Isle of Wight

Re: BL instruction vs. basic blocks

Tue Dec 03, 2019 2:21 pm

hippy wrote:
Tue Dec 03, 2019 10:48 am
LdB wrote:
Tue Dec 03, 2019 1:08 am
I can't work out what you mean the BL instruction is always going to branch it will NEVER execute the next instruction (it has no condition)
I also don't understand the OP's reference to 'basic blocks' or what 'side-effects' of instructions are, why they are being tracked, why they need to be known. If it's tracking 'known system state' as code is being emitted that would normally be set to unknown after a BL.
Well, I'm thinking if I had code like this (but less silly):

Code: Select all

	MOV	R4, #42
	BL	somewhere
(and subroutines obey the 'usual' rules) then I can assume that R4 still contains 42. R1-3 might have been 'corrupted', LR definitely will be, R0 might have if it's not a return value.
At the start of a basic block, I'll probably assume all bets are off since the processor could have 'arrived' from anywhere (though some cunning optimisations are possible).

Since I'm generating the code, I can assume it's not doing anything perverse!
Bruce Mardle. "You know I yearn for a simpler time of barn dances and buggy rides before life was cheapened by heartless machines."

LdB
Posts: 1311
Joined: Wed Dec 07, 2016 2:29 pm

Re: BL instruction vs. basic blocks

Tue Dec 03, 2019 3:14 pm

That is called calling convention and since you are writing the assembler that is up to you

You can see the GCC one
https://wiki.osdev.org/Calling_Conventions

As many compilers link to GCC c code they often just adopt GCC calling convention.

BMardle
Posts: 111
Joined: Wed Feb 13, 2013 4:00 pm
Location: Isle of Wight

Re: BL instruction vs. basic blocks

Tue Dec 03, 2019 3:44 pm

LdB wrote:
Tue Dec 03, 2019 3:14 pm
That is called calling convention and since you are writing the assembler that is up to you

You can see the GCC one
https://wiki.osdev.org/Calling_Conventions

As many compilers link to GCC c code they often just adopt GCC calling convention.
It's interesting that lists R12 as a 'scratch' register.
Bruce Mardle. "You know I yearn for a simpler time of barn dances and buggy rides before life was cheapened by heartless machines."

LdB
Posts: 1311
Joined: Wed Dec 07, 2016 2:29 pm

Re: BL instruction vs. basic blocks

Tue Dec 03, 2019 4:17 pm

It is .. it even has a special name "Intra-procedure-call scratch register" :-)

Microsoft follows the same as GCC on there ARM compiler
https://docs.microsoft.com/en-us/cpp/bu ... ew=vs-2019

hippy
Posts: 6223
Joined: Fri Sep 09, 2011 10:34 pm
Location: UK

Re: BL instruction vs. basic blocks

Tue Dec 03, 2019 5:16 pm

BMardle wrote:
Tue Dec 03, 2019 2:21 pm
Since I'm generating the code, I can assume it's not doing anything perverse!
If you are generating the code and know exactly what your called routines will affect then you can assume that. In fact; not so much assume as know.

Return to “Bare metal, Assembly language”