Logic Flaw: IsAlwaysDuplicable violates may_duplicate_ semantics and ignores index-computation costs

[red1239109-cmd]

InstructionFusion currently allows certain instructions (e.g., kBroadcast, widening kConvert) to be duplicated even when may_duplicate_ == false, via the IsAlwaysDuplicable exception logic.

This implementation weakens the semantic contract of may_duplicate_, introduces hidden policy exceptions, and ignores non-trivial index-computation and register-pressure costs—especially for high-rank broadcasts. While this may have originated as a performance heuristic, it now represents a structural logic flaw that complicates reasoning, maintenance, and future optimization decisions.

Problem 1: Semantic Violation of may_duplicate_

From a reader and maintainer perspective, the meaning of may_duplicate_ is straightforward:
"may_duplicate_ = false" implies that instruction duplication must not occur.

However, the current implementation violates this expectation:

bool IsAlwaysDuplicable(const HloInstruction& instruction) {
  return (instruction.opcode() == HloOpcode::kConvert && widening) ||
         instruction.opcode() == HloOpcode::kBroadcast;
}

This creates a policy exception path where duplication occurs even when explicitly disabled by the caller. The code itself acknowledges the inconsistency:

// TODO(jlebar): Duplicating instructions when we have a variable called "may
// duplicate" that's equal to false is not pretty.

This is not merely cosmetic:

1. It breaks the semantic contract of the flag.
2. It forces maintainers to remember undocumented exceptions.
3. It makes fusion behavior harder to reason about, debug, and evolve.

In practice, may_duplicate_ no longer means "no duplication," but rather "no duplication except for a hardcoded whitelist."

Problem 2: Ignoring Index-Generation and Register Costs

The rationale for IsAlwaysDuplicable appears to be primarily memory-centric:
"Duplicating these ops reduces memory traffic."

This assumption is incomplete. "Memory-cheap" does not imply "compute-cheap."

For kBroadcast in particular, duplication can significantly increase compute cost:

• High-rank broadcasts require repeated index reconstruction at every consumer.
• Index computation often involves div/mod or equivalent arithmetic operations per element.
• These operations increase register pressure, instruction count, and can reduce occupancy.

In fused kernels with large shapes, duplicating a broadcast can easily shift the bottleneck from memory to compute—especially on architectures where integer division/modulo is expensive. Yet, IsAlwaysDuplicable treats kBroadcast as universally safe, regardless of tensor rank, broadcast dimensionality, or backend-specific cost models.

Problem 3: Structural Smell in the Cost Model

Conceptually, this creates a layering issue:

• may_duplicate_ is supposed to express a global fusion policy.
• IsAlwaysDuplicable bypasses that policy with opcode-based exceptions.

Cost reasoning is currently split across flag semantics, opcode whitelists, and backend heuristics. This results in a system that is pattern-driven rather than policy-driven, which becomes increasingly brittle as the compiler supports more architectures.

Suggested Direction

This issue is raised for correctness and design clarity. Possible directions include:

1. Enforce may_duplicate_ strictly: Remove the exception path. If the caller sets it to false, respect it.
2. Restrict IsAlwaysDuplicable: Limit the exception to strictly scalar broadcasts where index computation is negligible.
3. Explicit Policy: Replace opcode-based exceptions with an explicit, documented duplication policy or cost model hook.
4. Cost-Awareness: Make duplication decisions depend on rank/index cost instead of opcode alone.

Why This Matters

This is not about a single missed optimization. It is about keeping compiler reasoning explicit, composable, and honest. Hidden exceptions accumulate technical debt, especially in passes like fusion where behavior is global, performance-sensitive, and highly backend-dependent. Surfacing this inconsistency helps prevent harder-to-debug performance regressions.

[akuegel]

• For which backend do you care about this? For example GPU doesn't use this code anymore (however we currently do allow duplication if cost model determines it is worth it, in the hope of multi-output fusion later combining the fusions and with CSE the duplicates will go away).

• Usually backends call fusion twice: once with may_duplicate set to false, then another time with may_duplicate set to true. The idea being that we first prefer to form the obvious fusions, and later the not so obvious fusions. Broadcasts are indeed considered obvious fusions, as if you don't fuse it it means the broadcast will be materialized.

• What I don't understand yet: fusing a broadcast into a fusion might make it compute bound instead of memory bound, but what has that to do with duplication? I assume a backend will run just a single fusion as a kernel, so it should not matter for this fusion whether the same broadcast was fused into another fusion as well.

[red1239109-cmd]

​Thanks for the context - that helps.
​Backend / Scope:
I'm not claiming this affects the GPU pipeline today. My concern is primarily about (a) backends that still route through this fusion logic (CPU / non-GPU / experimental), and (b) the semantic contract of the may_duplicate flag inside InstructionFusion regardless of backend.
​Why I brought up "duplication" (not just fusion):
Even if each fusion becomes a single kernel, duplication still matters because it changes the global work performed across the module: the same producer (e.g. a high-rank broadcast) can be cloned into multiple consumers/fusions, so its index generation / address arithmetic can be replicated across multiple kernels. In cases where the broadcast is not trivially scalar-like, this can increase total compute and register pressure across the program, even if each kernel is "valid" in isolation.
​Also, the may_duplicate=false -> "prefer obvious fusions first, then allow duplication later" strategy makes sense, but the hardcoded IsAlwaysDuplicable() exception means may_duplicate=false no longer strictly corresponds to "no duplication in this phase." That's the semantics/maintainability issue I'm trying to surface.
​Clarifying the intended meaning:
If the intended policy is "we still allow duplication of a small whitelist even when may_duplicate=false," then perhaps the flag name / comment should reflect that (or the exception should be gated by a backend cost model / 'broadcast is scalar-like' check). Right now, the TODO itself hints this is a bit of a semantic mismatch.
​Concrete ask / next step:
Could you confirm which backends still rely on this path and whether may_duplicate=false is intended to allow any cloning? If the answer is "yes by design," then I think the issue should be reframed as a documentation / invariants clarification + potentially making the broadcast exception cost-aware (e.g. scalar-only / low-rank / cheap index path).
​Happy to update the issue description accordingly once the intended contract is clarified.

[akuegel]

The CPU backend currently runs fusion only once, and sets may_duplicate to true if and only if multi-output fusion is enabled (I think it is enabled by default). There is already a plan to create a PriorityFusion pass for the CPU backend similar to the one GPU uses.
As far as I can tell, there is no other in-tree backend that uses InstructionFusion and sets may_duplicate to false (except possibly in tests).

[red1239109-cmd]

Understood. Given the limited current usage across active backends, I agree this isn’t urgent.

I’ll leave this issue open primarily as a design note regarding the semantic divergence of may_duplicate_ and the hardcoded exceptions. It should serve as a reference for any future fusion refactors or new backend integrations to avoid tripping over these implicit constraints.

Thanks for engaging in the discussion, @akuegel. I genuinely appreciate that you took the time to verify and respond instead of dismissing or ignoring the issue. As expected, it shows the quality of Google engineering. I hope this short exchange was mutually beneficial.