Pandora A "new" Good Way To Program For The Pandora?

[ari64]

"Look up BTB entry" per here of course meaning "checks if it's a hit", since most instructions have no rightful business being in the BTB. I don't know if the issue is limit in access rate of the BTB, because I think that a one cycle stall on the second branch wouldn't be as serious as you're making this sound. I think it's more likely a collision in one of the prediction arrays. I'm voting against the BTB because it's not direct mapped. But the global historical buffer would hurt you if the two branches go opposite directions and share common low-enough order bits. I'm going to assume that they went opposite directions because it doesn't make much sense otherwise. Of course, Thumb-2 aggravates the issue by having more significant low end PC bits, and ARM does say that the performance with Thumb-2 is worse.

Can you test to see if the penalty is the same regardless of whether or the instructions are in the same 8 byte alignment?

If the instructions are not in the same 8 byte alignment then there is no effect.

b    12345678
mov  r0,r0    ;stall

b    12345678
add  r0,r0,#0 ;no penalty

b    12345678
ldr  r0,[sp,#0] ;stall

b    12345678
str  r0,[sp,#0] ;no penalty

Checking bits 20 & 25-27 of the instruction is sufficient to distinguish these cases, so that's probably all it does. Note that the second instruction is never executed; this is an issue with the instruction decoder and branch predictor only. The mov and ldr are treated as possible branches because they would be branches if the destination register was the program counter.

What's really strange is there IS a section in the TRM addressing similar (but more mild) issues regarding branch proximity.

Yeah, section 5.4: "You can avoid certain code constructs to maximize branch prediction performance. For example: [...] Coding more than two likely taken branches per fetch. This can only happen in Thumb state. Unless used as a jump table where each branch is its own basic block, use NOPs for padding."

However, there is a penalty for coding two likely taken branches per fetch in ARM state, eg

beq 0x12345678
b   0x1234abcd

If the first branch is usually taken then it can be advantageous to insert a NOP like this:

beq 0x12345678
add r0, r0, #0
b   0x1234abcd

If the first branch is never taken, then the NOP does not help since both branches will always be decoded and predicted.

Also the TRM neglects to mention that using MOV as a NOP is a bad idea.

 

[ari64]

Oh - one other thing:

Don't try to align code so that it fits in a cache line on the A8. The BTB seems to be indexed based on the low bits of the instruction address, and if you have too many branches at the same alignment, you will get very bad branch prediction.

 

[ari64]

It would be better to put this information on the wiki.

 

[Exophase]

"Shift or rotate instructions take two cycles, and may stall if any of three preceding instructions write to the shifted register."

This doesn't agree with the TRM... it says shifts happen one pipeline stage prior to most execution, same as address generation, so the interlocks should be the same. "Take two cycles" implies two issue cycles, is this what you meant? Are these things you've measured, and can you provide the conditions of the experiment if so?

Does "branches are always predicted as not taken the first time" apply to unconditional branches too?

 

[ldesnogu]

I think the code alignment section could be misinterpreted. It's true for short basic blocks where the probability of conflicting offsets increases. So for JIT, it's probably a good advice, but for instance for long sequences of instructions without any branch, it isn't.

 

[ari64]

"Shift or rotate instructions take two cycles, and may stall if any of three preceding instructions write to the shifted register."

This doesn't agree with the TRM... it says shifts happen one pipeline stage prior to most execution, same as address generation, so the interlocks should be the same. "Take two cycles" implies two issue cycles, is this what you meant? Are these things you've measured, and can you provide the conditions of the experiment if so?

Can you think of a better way to word this? The shift happens in E1, and the prior instruction completes in E2, so there is a one-cycle stall.

The dynarec uses arithmetic shifts for sign extension, and I did find that scheduling other instructions in between was helpful, which is consistent with what is stated in the TRM.

Does "branches are always predicted as not taken the first time" apply to unconditional branches too?

Apparently so. In the case of calls, this is somewhat beneficial as the return path gets prefetched. Yes, I have measured this, and it remains true even if the return is mispredicted for not using r14 (as is the case with the dynamic recompiler). Putting NOPs after the call, and jumping over them on return diminishes this effect, although I haven't tried to figure out exactly how many nops it takes to completely eliminate the effect of the prefetch.

I think the code alignment section could be misinterpreted. It's true for short basic blocks where the probability of conflicting offsets increases. So for JIT, it's probably a good advice, but for instance for long sequences of instructions without any branch, it isn't.

How is that a misinterpretation? If you have a long sequence of instructions without any branches, then branch prediction isn't an issue.

 

[ldesnogu]

I think the code alignment section could be misinterpreted. It's true for short basic blocks where the probability of conflicting offsets increases. So for JIT, it's probably a good advice, but for instance for long sequences of instructions without any branch, it isn't.

How is that a misinterpretation? If you have a long sequence of instructions without any branches, then branch prediction isn't an issue.

In that case instruction alignment might be beneficial if you jump into the sequence.

 

[ari64]

I think the code alignment section could be misinterpreted. It's true for short basic blocks where the probability of conflicting offsets increases. So for JIT, it's probably a good advice, but for instance for long sequences of instructions without any branch, it isn't.

How is that a misinterpretation? If you have a long sequence of instructions without any branches, then branch prediction isn't an issue.

In that case instruction alignment might be beneficial if you jump into the sequence.

It might be, if you don't have to put too many nops into that sequence to align the entry point. There are a few rare cases where it's beneficial, the point is that it's not helpful in most cases.

Are there any compilers that align code on A8, and what strategy do they use? I know gcc doesn't do this.

 

[ari64]

The overall improvement that I've seen from code alignment is around 0.5% in the best case. The branch prediction anomalies are very random, sometimes it is fast and sometimes it is slow. Sometimes changing one part of the code will cause a problem in something unrelated, probably due to BTB collisions. If the branch prediction problems prove to be infrequent enough, I may decide to go with the code alignment after all, but it's a very small improvement and I'd need to test it further.

Perhaps it would be better to say, "Code alignment should be used with caution."

Another interesting result is that intentionally stalling the decoder by padding with MOV r0,r0 instead of ADD r0,#0 after an unconditional branch can improve performance if you do not want that code prefetched. Even a single MOV instruction can be surprisingly effective.

 

[Exophase]

Can you think of a better way to word this? The shift happens in E1, and the prior instruction completes in E2, so there is a one-cycle stall.

I would word it the same way you've worded AGIs, ie writing the cycle before will cause a one-cycle stall (that writing the cycle of prevents pairing should go without saying). What you have now is technically correct, but in the TI's terminology how many "cycles" an operation is refers to its issue rate or throughput, not its latency. Saying any access three instructions before would cause a stall is only true if otherwise those four would have paired perfectly, which could have been expected not to be the case anyway with this kind of access. It also assumes the instruction is on the second edge of its pairing, which is not necessarily true, so it could just be two instructions.

Apparently so. In the case of calls, this is somewhat beneficial as the return path gets prefetched. Yes, I have measured this, and it remains true even if the return is mispredicted for not using r14 (as is the case with the dynamic recompiler). Putting NOPs after the call, and jumping over them on return diminishes this effect, although I haven't tried to figure out exactly how many nops it takes to completely eliminate the effect of the prefetch.[/qoute]

I dunno, I think this is pretty annoying. A branch mispredict costs a lot more than an L1 miss, and I think you'll run out of BTB a lot faster than you run out of L2. If you feel that this has a big enough effect for your recompiler then I'd imagine that moving to Thumb-2 would be beneficial afterall.. I'm sure you've thought of this already of course, and there would be some disadvantages, especially if you're using conditional execution a lot.

Another question: does the inability of paired instructions to write to the same register limitation apply to movw/movt pairs too?

 

[ari64]

I dunno, I think this is pretty annoying. A branch mispredict costs a lot more than an L1 miss, and I think you'll run out of BTB a lot faster than you run out of L2. If you feel that this has a big enough effect for your recompiler then I'd imagine that moving to Thumb-2 would be beneficial afterall.. I'm sure you've thought of this already of course, and there would be some disadvantages, especially if you're using conditional execution a lot.

The issue isn't running out of BTB entries, it's that aligning the code shifts things around so that the branches occupy different BTB entries, which may make collisions more or less likely. It's a little hard to predict exactly what effect it will have. I've now got the recompiler generating the main code aligned, but not the epilogue code, and it seems to be working reasonably well, so I think I will leave it like that.

All of this is quite annoying. I didn't really set out to optimize instruction decoding or branch prediction. I was working on optimizing other things, but sometimes when I would make a change, it would affect the instruction decoding and that would skew the results, so then I ended up tracking down what did this particular change do to the instruction decoder.

An example of this is the mispredicted unconditional jump. What I really wanted to look at was whether I could optimize the return address lookup by matching returns with calls, but I kept running into this issue where the performance depended strongly on what instructions came after the call or return.

Another question: does the inability of paired instructions to write to the same register limitation apply to movw/movt pairs too?

Is there something special about these? They seem to pair like any other instruction.

 

[Exophase]

The issue isn't running out of BTB entries, it's that aligning the code shifts things around so that the branches occupy different BTB entries, which may make collisions more or less likely. It's a little hard to predict exactly what effect it will have. I've now got the recompiler generating the main code aligned, but not the epilogue code, and it seems to be working reasonably well, so I think I will leave it like that.

Right, I was saying that I thought it's strange that you were calling the mispredicted unconditional branches beneficial due to preloading when the mispredict probably tends to outweigh the preload.

Is there something special about these? They seem to pair like any other instruction.

I'm asking if the following:

movw r0, #low
movt r0, #high

Is special cased and can pair. I'm guessing not.

 

[ari64]

Right, I was saying that I thought it's strange that you were calling the mispredicted unconditional branches beneficial due to preloading when the mispredict probably tends to outweigh the preload.

The misprediction is unavoidable as the branches appear to always mispredict the first time. It's more a matter of making sure it's not doing anything bad when it goes down the wrong path. In the case where it prefetches code that will be needed later anyway, at least it's doing something somewhat useful during that otherwise wasted time.

It's hard to figure out exactly how much time is spent on mispredicted branches, but it's clearly a non-trivial amount. All I can see is the effect on the cache from fetching unwanted instructions/data.

I'm asking if the following:

movw r0, #low
movt r0, #high

Is special cased and can pair. I'm guessing not.

It doesn't seem to be. Replacing movw/movt with a mov/add pair doesn't make any difference.