On 11/11/26 3:15 PM, Matt Turner wrote:
The ev6's two clusters keep separate register files that are resynchronized
once a cycle, so a value produced in one and consumed in the other arrives a
cycle late. Which cluster an instruction issues to follows from the
subcluster that Table 2-3 of the Compiler Writer's Guide slots it into, and
that depends on its position in the aligned octaword. Moving a loop body by
a single instruction can therefore put the two ends of a dependence on the
same side instead of opposite sides.
On an EV68AL, a conditional-move reduction and a shift/xor mixing loop each
run at 4.00 cycles per iteration with -mtune=ev6, against 3.00 with
-mtune=ev4 or -mtune=ev5, and inserting one nop recovers the cycle. A nop is
discarded at decode, so it changes only where the following instructions sit.
One of the loops has no cmov, so the cause is not the n+1 fetch rule for
cmovs in section 3.4.4.2. What differs is the subcluster Table 2-3 gives the
producer of the critical dependence.
Pad the loop with nops rather than reorder it. Reordering after scheduling
would have to rebuild the dependence graph and could not be undone if the
model guessed wrong, whereas padding can only shift alignment. Reordering
within an octaword cannot change throughput in any case: the number of
instructions slotted upper and lower is fixed by the multiset of their
requirements.
For each short loop with a single branch, try 0 to 3 nops after the loop
label. A pad is used only if it leaves the number of fetch cycles unchanged
and strictly reduces the number of split dependences. The fetch cost is paid
on every iteration, but a split saving depends on the model guessing the
hardware right. The fetch model counts one branch predicted per cycle
(section 3.4.3) and one extra cycle per cmov (section 3.4.4.2).
Only dependences that bound the loop count: those on a dependence cycle, and
those on a longest path through the body, weighted by insn_default_latency.
Other dependences are hidden by the issue queue, so repairing them costs fetch
bandwidth for nothing. Three further restrictions came from measurements:
- Only integer register dependences count. Floating-point values are
produced and consumed in the Fbox, which is not clustered.
- Loops containing a count/MVI or multiply insn are skipped. Those units
exist in one cluster each, so the cluster follows from the unit and not
from the subcluster.
- Loops with more than one branch are skipped. They are already at the
fetch limit. Padding the two-branch loops of Ackermann's function cost
1.00% +/- 0.22% where the model predicted a gain.
-mno-cluster-align turns the pass off and gives the same output as before.
Of the 54 single-file C benchmarks in llvm-test-suite, the pass changes the
code of 12. Over three interleaved sessions of min-of-7 whole-program cycles,
the nine whose timings are stable to within 5% have a geomean of 0.9962 with a
95% CI of [0.9948, 0.9977]. lowercase is 3.3% faster and huffbench 0.2%
faster; nothing regresses distinguishably. The other three are too short or
too noisy to time; including them gives 0.9929, CI [0.9797, 1.0060]. The gain
on typical code is small, and the pass is aimed at the loops that lose 25%.
Testing: 1574 gcc.c-torture/execute cases compile with the same ok and fail
counts with the option on and off. 300 of them were built and run on
hardware with 296 passing; the four failures also occur with -mtune=ev4,
-mtune=ev5 and -O0. All 56 llvm-test-suite benchmarks that run produce
identical output with and without the pass.
gcc/ChangeLog:
* config/alpha/alpha.opt (mcluster-align): New option.
* config/alpha/alpha.opt.urls: Regenerate.
* config/alpha/alpha.cc (ev6_slotting): New table.
(alpha_ev6_slot_req, alpha_ev6_depends_p, alpha_ev6_dependences)
(alpha_ev6_critical_pairs, alpha_ev6_split_deps)
(alpha_ev6_fetch_cycles, alpha_ev6_cost_at, alpha_ev6_loop_body)
(alpha_ev6_align_insns): New functions.
(alpha_align_insns): Call alpha_ev6_align_insns for ev6 when
alpha_cluster_align.
(pass_align_insns::gate): Enable for ev6.
* config/alpha/ev6.md: Replace the note on instruction order and
cluster issue.
* doc/invoke.texi (DEC Alpha Options): Document -mcluster-align.
gcc/testsuite/ChangeLog:
* gcc.target/alpha/cluster-align.c: New test.
* gcc.target/alpha/cluster-align-2.c: New test.
Wow. Reminds me a bit of the even/odd scheduling stuff for the PA from
so long ago. I forget all the details, but there were some ops that
were statically scheduled based on the address. So insertion of nops
could force steering those ops into different function units and
increase throughput. We never implemented anything to improve this.
+/* Set CRIT[i] to the positions that form a critical pair with position i.
+
+ A hop between clusters only slows the loop if it is on a path that bounds
+ the loop. A pair counts if the two insns are on a common dependence cycle,
+ or if the dependence between them lies on a longest path through the body.
+ The second case covers a loop with no recurrence that is still paced by a
+ chain running from one end of an iteration to the other.
+
+ Cycles: close DEP over the back edge with Warshall's algorithm and keep the
+ mutually reachable pairs. The result is written to a separate array
+ because narrowing REACH in place would change later rows.
+
+ Longest path: TOP[i] is the longest path ending at i and BOT[i] the longest
+ starting at i, over the intra-iteration edges, weighted by the default insn
+ latency. An edge is on a longest path when it lies on a path of length
+ BEST. */
+
+static void
+alpha_ev6_critical_pairs (rtx_insn **insns, int n, const ev6_set_t *dep,
+ ev6_set_t *crit)
I hope N is reasonably small (and given this is for small loops, I
suspect it is).
+
+/* Place the bodies of short loops so that latency-critical dependences stay
+ within one cluster.
+
+ The ev6's two clusters keep separate register files that are resynchronized
+ once a cycle, so a value produced in one and consumed in the other arrives
+ a cycle late. Which cluster an instruction issues to follows from the
+ subcluster that Table 2-3 slots it into, which depends on its position in
+ the aligned octaword. Moving a loop body by one instruction can therefore
+ put the two ends of a dependence on the same side instead of opposite
+ sides. Ordering within an octaword cannot change throughput, so only the
+ placement of the whole body is adjusted, by padding with unops. An unop is
+ discarded at decode. */
+
+static void
+alpha_ev6_align_insns (void)
+{
+ int delta = 0;
+
+ shorten_branches (get_insns ());
+
+ for (rtx_insn *insn = get_insns (); insn; insn = NEXT_INSN (insn))
+ {
+ rtx_insn *body[EV6_MAX_LOOP], *label;
+ int n, slot, base_fetch, best_splits, best_pad = 0;
+
+ /* A loop is a jump back to a label already passed. */
+ if (!JUMP_P (insn) || !JUMP_LABEL (insn) || !LABEL_P (JUMP_LABEL (insn)))
+ continue;
+ label = as_a <rtx_insn *> (JUMP_LABEL (insn));
+ if (INSN_ADDRESSES (INSN_UID (label))
+ > INSN_ADDRESSES (INSN_UID (insn)))
+ continue;
Not strictly correct. The strictly correct case is a backwards branch
where the target of the branch dominates the branch itself.
Depending on where you are in the RTL pipeline, you may be able to look
at the CFG data to find the backedges, loop backedges, blocks in the
loop, etc. That might simplify things a bit. It may not matter all
that much in practice.
I'm more than willing to just trust you on this implementation. We
don't really have anyone else doing alpha work these days.
Your call whether or not to adjust the comment or code WRT natural loop
discovery or computing the loop blocks from the CFG.
jeff
