1use std::any::Any;
2use std::collections::hash_map::DefaultHasher;
3use std::collections::HashMap;
4#[cfg(feature = "autodiff")]
5use std::collections::HashSet;
6use std::hash::{Hash, Hasher};
7use std::sync::Arc;
8
9use computegraph::graph::GraphBuilder;
10use computegraph::types::ValueRef;
11#[cfg(feature = "autodiff")]
12use tenferro_ad::semantic_extension::{
13 AdValue, ResidualSpec, SemanticAdError, SemanticAdRuleRole, SemanticExtensionRegistryError,
14 SemanticExtensionRuleSet, SemanticLinearTransposeRequest, SemanticLinearTransposeRule,
15 SemanticLinearizeRequest, SemanticLinearizeResult, SemanticLinearizeRule,
16 SemanticPrimalVjpRequest, SemanticPrimalVjpRule,
17};
18use tenferro_extension_macros::define_extension_runtime;
19#[cfg(feature = "autodiff")]
20use tenferro_ops::dim_expr::DimExpr;
21use tenferro_ops::ext_op::{
22 ExtensionLoweringError, ExtensionLoweringResult, ExtensionOp, ExtensionStandardLowering,
23};
24use tenferro_ops::std_tensor_op::StdTensorOp;
25use tenferro_ops::sym_dim::SymDim;
26#[cfg(feature = "autodiff")]
27use tenferro_ops::ShapeExtent;
28use tenferro_runtime::extension::{ExtensionCacheKey, ExtensionExecutionContext};
29#[cfg(feature = "autodiff")]
30use tenferro_runtime::program::{
31 CoreSemanticOp, ProgramValue, ProgramValueMetadata, SemanticProgramBuilder,
32};
33use tenferro_tensor::{DType, Engine, Error as TensorError, Tensor, TensorRead};
34
35#[cfg(feature = "autodiff")]
36use crate::broadcast::{broadcast_axis_reduce, classify_dim_exprs, UndecidedBroadcastAxis};
37use crate::broadcast::{merge_broadcast_extent, ExtentMerge};
38use crate::builder::build_einsum_graph;
39use crate::cache::{
40 einsum_subscripts_retained_bytes, saturating_sum, vec_retained_bytes,
41 EINSUM_EXTENSION_FAMILY_ID, EINSUM_RUNTIME_PLANS_CACHE,
42};
43#[cfg(test)]
44use crate::optimize::default_auto_options;
45#[cfg(feature = "autodiff")]
46use crate::optimize::jax_path_to_v1_pairs;
47use crate::optimize::{hash_einsum_plan_spec, plan_specs_equal, resolve_plan_spec, EinsumPlanSpec};
48#[cfg(feature = "autodiff")]
49use crate::util::map_label_occurrences;
50use crate::{
51 ContractionTree, EinsumSubscripts, Error as EinsumError, Result as EinsumResult, Subscripts,
52};
53
54#[derive(Clone)]
59pub(crate) struct EinsumExtensionOp {
60 subscripts: EinsumSubscripts,
61 plan_spec: EinsumPlanSpec,
62 output_shape_hint: Option<Vec<SymDim>>,
63 allow_broadcast: bool,
64}
65
66impl std::fmt::Debug for EinsumExtensionOp {
67 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
68 f.debug_struct("EinsumExtensionOp")
69 .field("subscripts", &self.subscripts)
70 .field("plan_spec", &self.plan_spec)
71 .field("output_shape_hint", &self.output_shape_hint)
72 .field("allow_broadcast", &self.allow_broadcast)
73 .finish()
74 }
75}
76
77impl EinsumExtensionOp {
78 #[must_use]
80 #[cfg(test)]
81 pub(crate) fn new(subscripts: EinsumSubscripts) -> Self {
82 Self::with_plan_spec(subscripts, EinsumPlanSpec::Auto(default_auto_options()))
83 }
84
85 #[must_use]
86 pub(crate) fn with_plan_spec(subscripts: EinsumSubscripts, plan_spec: EinsumPlanSpec) -> Self {
87 Self {
88 subscripts,
89 plan_spec,
90 output_shape_hint: None,
91 allow_broadcast: false,
92 }
93 }
94
95 pub(crate) fn with_plan_spec_and_broadcast(
96 subscripts: EinsumSubscripts,
97 plan_spec: EinsumPlanSpec,
98 allow_broadcast: bool,
99 ) -> Self {
100 let mut op = Self::with_plan_spec(subscripts, plan_spec);
101 op.allow_broadcast = allow_broadcast;
102 op
103 }
104
105 #[must_use]
107 #[cfg(any(feature = "autodiff", test))]
108 pub(crate) fn with_output_shape_hint(
109 subscripts: EinsumSubscripts,
110 output_shape_hint: Vec<SymDim>,
111 plan_spec: EinsumPlanSpec,
112 ) -> Self {
113 let mut op = Self::with_plan_spec(subscripts, plan_spec);
114 op.output_shape_hint = Some(output_shape_hint);
115 op
116 }
117
118 #[must_use]
119 #[cfg(feature = "autodiff")]
120 pub(crate) fn with_output_shape_hint_and_broadcast(
121 subscripts: EinsumSubscripts,
122 output_shape_hint: Vec<SymDim>,
123 plan_spec: EinsumPlanSpec,
124 allow_broadcast: bool,
125 ) -> Self {
126 let mut op = Self::with_plan_spec_and_broadcast(subscripts, plan_spec, allow_broadcast);
127 op.output_shape_hint = Some(output_shape_hint);
128 op
129 }
130
131 #[must_use]
133 pub(crate) fn subscripts(&self) -> &EinsumSubscripts {
134 &self.subscripts
135 }
136
137 #[must_use]
139 pub(crate) fn plan_spec(&self) -> &EinsumPlanSpec {
140 &self.plan_spec
141 }
142
143 #[must_use]
144 #[cfg(feature = "autodiff")]
145 pub(crate) fn allow_broadcast(&self) -> bool {
146 self.allow_broadcast
147 }
148}
149
150impl ExtensionOp for EinsumExtensionOp {
151 fn family_id(&self) -> &'static str {
152 EINSUM_EXTENSION_FAMILY_ID
153 }
154
155 fn payload_hash(&self, hasher: &mut dyn Hasher) {
156 hasher.write_usize(self.subscripts.inputs.len());
157 for input in &self.subscripts.inputs {
158 hasher.write_usize(input.len());
159 for label in input {
160 hasher.write_u32(*label);
161 }
162 }
163 hasher.write_usize(self.subscripts.output.len());
164 for label in &self.subscripts.output {
165 hasher.write_u32(*label);
166 }
167 hash_einsum_plan_spec(self.plan_spec(), hasher);
168 hasher.write_u8(u8::from(self.allow_broadcast));
169 if let Some(shape) = &self.output_shape_hint {
170 hasher.write_usize(shape.len());
171 for dim in shape {
172 match dim.constant_value() {
173 Some(value) => {
174 hasher.write_u8(1);
175 hasher.write_usize(value);
176 }
177 None => hasher.write_u8(0),
178 }
179 }
180 } else {
181 hasher.write_usize(usize::MAX);
182 }
183 }
184
185 fn payload_eq(&self, other: &dyn ExtensionOp) -> bool {
186 other.as_any().downcast_ref::<Self>().is_some_and(|that| {
187 self.subscripts == that.subscripts
188 && plan_specs_equal(self.plan_spec(), that.plan_spec())
189 && self.output_shape_hint == that.output_shape_hint
190 && self.allow_broadcast == that.allow_broadcast
191 })
192 }
193
194 fn clone_arc(&self) -> Arc<dyn ExtensionOp> {
195 Arc::new(self.clone())
196 }
197
198 fn as_any(&self) -> &dyn Any {
199 self
200 }
201
202 fn input_count(&self) -> usize {
203 self.subscripts.inputs.len()
204 }
205
206 fn output_count(&self) -> usize {
207 1
208 }
209
210 fn semantic_effects(&self) -> tenferro_ops::ext_op::ExtensionEffectDeclaration<'_> {
211 tenferro_ops::ext_op::ExtensionEffectDeclaration::Declared(&[])
212 }
213
214 fn semantic_aliases(&self) -> tenferro_ops::ext_op::ExtensionAliasDeclaration<'_> {
215 tenferro_ops::ext_op::ExtensionAliasDeclaration::AllFresh
216 }
217
218 fn infer_output_meta(
219 &self,
220 ctx: &mut tenferro_ops::ExtensionShapeContext<'_>,
221 ) -> tenferro_tensor::Result<Vec<(DType, Vec<SymDim>)>> {
222 let input_dtypes = (0..self.input_count())
223 .map(|input| ctx.input_dtype(input))
224 .collect::<Result<Vec<_>, _>>()?;
225 let input_shapes = (0..self.input_count())
226 .map(|input| ctx.input_shape(input).map(<[_]>::to_vec))
227 .collect::<Result<Vec<_>, _>>()?;
228
229 let mut label_dims: HashMap<u32, SymDim> = HashMap::new();
230 for (labels, shape) in self.subscripts.inputs.iter().zip(input_shapes.iter()) {
231 if labels.len() != shape.len() {
232 return Err(TensorError::rank_mismatch(
233 "einsum",
234 labels.len(),
235 shape.len(),
236 ));
237 }
238 let mut operand_dims: HashMap<u32, SymDim> = HashMap::new();
239 for (&label, dim) in labels.iter().zip(shape.iter()) {
240 if let Some(existing) = operand_dims.get(&label) {
244 ctx.require_equal(existing.clone(), dim.clone())?;
245 continue;
246 }
247 operand_dims.insert(label, dim.clone());
248 if let Some(existing) = label_dims.get_mut(&label) {
249 match merge_broadcast_extent(existing, dim, self.allow_broadcast) {
250 ExtentMerge::Merged(merged) => *existing = merged,
251 ExtentMerge::RequireEqual => {
252 ctx.require_equal(existing.clone(), dim.clone())?;
253 }
254 }
255 } else {
256 label_dims.insert(label, dim.clone());
257 }
258 }
259 }
260
261 let output_shape = match &self.output_shape_hint {
262 Some(shape) if shape.iter().all(|dim| dim.constant_value().is_some()) => shape.clone(),
263 _ => self
264 .subscripts
265 .output
266 .iter()
267 .map(|label| label_dims.get(label).cloned())
268 .collect::<Option<Vec<_>>>()
269 .ok_or_else(|| {
270 TensorError::invalid_argument(
271 "einsum",
272 "output labels",
273 "must be present in input metadata",
274 )
275 })?,
276 };
277 if output_shape.len() != self.subscripts.output.len() {
278 return Err(TensorError::rank_mismatch(
279 "einsum",
280 self.subscripts.output.len(),
281 output_shape.len(),
282 ));
283 }
284 if let Some(external) = input_dtypes
285 .iter()
286 .find(|dtype| matches!(dtype, DType::External(_)))
287 {
288 return Err(TensorError::unsupported_dtype(
289 "einsum",
290 *external,
291 "einsum takes preset scalars only; an externally defined scalar is not supported",
292 ));
293 }
294 Ok(vec![(
295 promote_dtypes(input_dtypes.iter().copied()),
296 output_shape,
297 )])
298 }
299
300 fn lower_to_standard_ops(
301 &self,
302 builder: &mut GraphBuilder<StdTensorOp>,
303 inputs: &[ValueRef<StdTensorOp>],
304 input_dtypes: &[DType],
305 input_shapes: &[&[SymDim]],
306 ) -> ExtensionLoweringResult {
307 if inputs.len() != self.input_count()
308 || input_dtypes.len() != self.input_count()
309 || input_shapes.len() != self.input_count()
310 {
311 return Err(ExtensionLoweringError::new(format!(
312 "einsum extension expects {} inputs, got values={}, dtypes={}, shapes={}",
313 self.input_count(),
314 inputs.len(),
315 input_dtypes.len(),
316 input_shapes.len()
317 )));
318 }
319
320 let Some(shapes) = concrete_sym_shape_slices(input_shapes) else {
321 return Ok(ExtensionStandardLowering::Unsupported);
322 };
323 let shape_refs: Vec<&[usize]> = shapes.iter().map(Vec::as_slice).collect();
324 let subs = Subscripts::from(&self.subscripts);
325 let tree = resolve_plan_spec(self.plan_spec(), &subs, &shape_refs).map_err(|source| {
326 ExtensionLoweringError::from_source_with_kind(source.kind(), source)
327 })?;
328 let output = build_einsum_graph(builder, &tree, inputs, &shapes).map_err(|source| {
329 ExtensionLoweringError::from_source_with_kind(source.kind(), source)
330 })?;
331 Ok(ExtensionStandardLowering::Lowered(vec![output]))
332 }
333}
334
335fn concrete_sym_shape_slices(input_shapes: &[&[SymDim]]) -> Option<Vec<Vec<usize>>> {
336 input_shapes
337 .iter()
338 .map(|shape| {
339 shape
340 .iter()
341 .map(SymDim::constant_value)
342 .collect::<Option<Vec<_>>>()
343 })
344 .collect()
345}
346
347#[cfg(feature = "autodiff")]
349pub fn semantic_ad_rules(
356) -> std::result::Result<SemanticExtensionRuleSet, SemanticExtensionRegistryError> {
357 SemanticExtensionRuleSet::new()
358 .with_linearize(Arc::new(EinsumAdRule))?
359 .with_linear_transpose(Arc::new(EinsumAdRule))?
360 .with_primal_vjp(Arc::new(EinsumAdRule))
361}
362
363#[derive(Debug)]
364#[cfg(feature = "autodiff")]
365struct EinsumAdRule;
366
367#[cfg(feature = "autodiff")]
368impl SemanticLinearizeRule for EinsumAdRule {
369 fn family_id(&self) -> &'static str {
370 EINSUM_EXTENSION_FAMILY_ID
371 }
372
373 fn linearize(
374 &self,
375 request: SemanticLinearizeRequest<'_>,
376 builder: &mut SemanticProgramBuilder,
377 ) -> std::result::Result<SemanticLinearizeResult, SemanticAdError> {
378 let op = semantic_einsum_payload(request.op(), SemanticAdRuleRole::Linearize)?;
379 if !request.active_outputs()[0] {
380 return Ok(SemanticLinearizeResult::new([AdValue::Absent], []));
381 }
382 let mut terms = Vec::new();
383 for (active_idx, tangent) in request.tangent_inputs().iter().copied().enumerate() {
384 let AdValue::Value(tangent) = tangent else {
385 continue;
386 };
387 let inputs: Vec<_> = request
388 .primal_inputs()
389 .iter()
390 .copied()
391 .enumerate()
392 .map(|(input_idx, primal)| {
393 if input_idx == active_idx {
394 tangent
395 } else {
396 primal
397 }
398 })
399 .collect();
400 terms.push(builder.add_extension(Arc::new(op.clone()), &inputs)?[0]);
401 }
402 let tangent = semantic_sum_terms(builder, terms)?;
403 Ok(SemanticLinearizeResult::new([tangent], []))
404 }
405}
406
407#[cfg(feature = "autodiff")]
408impl SemanticLinearTransposeRule for EinsumAdRule {
409 fn family_id(&self) -> &'static str {
410 EINSUM_EXTENSION_FAMILY_ID
411 }
412
413 fn residual_mask(&self) -> ResidualSpec {
414 ResidualSpec::all_inputs()
419 }
420
421 fn linear_transpose(
422 &self,
423 request: SemanticLinearTransposeRequest<'_>,
424 builder: &mut SemanticProgramBuilder,
425 ) -> std::result::Result<Box<[AdValue]>, SemanticAdError> {
426 let primal_inputs = (0..request.primal_input_count())
427 .map(|index| request.primal_input_value(index))
428 .collect::<Result<Vec<_>, _>>()?;
429 let primal_output_metadata = request.primal_output_meta(0)?;
430 semantic_einsum_vjp(
431 request.op(),
432 &primal_inputs,
433 primal_output_metadata,
434 request.cotangent_outputs(),
435 request.active_inputs(),
436 request.residual_mask(),
437 builder,
438 )
439 }
440}
441
442#[cfg(feature = "autodiff")]
443impl SemanticPrimalVjpRule for EinsumAdRule {
444 fn family_id(&self) -> &'static str {
445 EINSUM_EXTENSION_FAMILY_ID
446 }
447
448 fn residual_mask(&self) -> ResidualSpec {
449 ResidualSpec::all_inputs()
452 }
453
454 fn primal_vjp(
455 &self,
456 request: SemanticPrimalVjpRequest<'_>,
457 builder: &mut SemanticProgramBuilder,
458 ) -> std::result::Result<Box<[AdValue]>, SemanticAdError> {
459 let primal_inputs = (0..request.primal_input_count())
460 .map(|index| request.primal_input_value(index))
461 .collect::<Result<Vec<_>, _>>()?;
462 let primal_output_metadata = request.primal_output_meta(0)?;
463 semantic_einsum_vjp(
464 request.op(),
465 &primal_inputs,
466 primal_output_metadata,
467 request.cotangent_outputs(),
468 request.active_inputs(),
469 request.residual_mask(),
470 builder,
471 )
472 }
473}
474
475#[cfg(feature = "autodiff")]
476fn semantic_einsum_vjp(
477 payload: &dyn ExtensionOp,
478 primal_inputs: &[ProgramValue],
479 primal_output_metadata: &ProgramValueMetadata,
480 cotangent_outputs: &[AdValue],
481 active_inputs: &[bool],
482 residual_mask: ResidualSpec,
483 builder: &mut SemanticProgramBuilder,
484) -> std::result::Result<Box<[AdValue]>, SemanticAdError> {
485 let op = semantic_einsum_payload(payload, SemanticAdRuleRole::LinearTranspose)?;
486 let input_count = op.subscripts.inputs.len();
487 let AdValue::Value(cotangent) = cotangent_outputs[0] else {
488 return Ok(vec![AdValue::Absent; input_count].into_boxed_slice());
489 };
490 let primal_input_shapes = primal_inputs
491 .iter()
492 .copied()
493 .map(|value| semantic_value_shape(builder, value))
494 .collect::<std::result::Result<Vec<_>, _>>()?;
495 let cotangent_shape = semantic_metadata_shape(primal_output_metadata)?;
496
497 let input_labels = &op.subscripts.inputs;
498 let output_labels = &op.subscripts.output;
499 let mut result = Vec::with_capacity(input_count);
500 for active_idx in 0..input_count {
501 if !active_inputs[active_idx] {
502 result.push(AdValue::Absent);
503 continue;
504 }
505 let mut available_labels: HashSet<u32> = output_labels.iter().copied().collect();
506 for (input_idx, labels) in input_labels.iter().enumerate() {
507 if input_idx != active_idx {
508 available_labels.extend(labels.iter().copied());
509 }
510 }
511 let summed_labels =
512 broadcast_summed_labels(builder, op, active_idx, primal_inputs, cotangent)?;
513 let vjp_output_labels: Vec<u32> = input_labels[active_idx]
516 .iter()
517 .copied()
518 .filter(|label| available_labels.contains(label) && !summed_labels.contains(label))
519 .collect();
520 let mut vjp_input_labels = vec![output_labels.clone()];
521 let mut vjp_inputs = vec![cotangent];
522 let mut vjp_input_shapes = vec![cotangent_shape.clone()];
523 for input_idx in 0..input_count {
524 if input_idx == active_idx {
525 continue;
526 }
527 vjp_input_labels.push(input_labels[input_idx].clone());
528 vjp_input_shapes.push(primal_input_shapes[input_idx].clone());
529 debug_assert!(
530 residual_mask.declares_input(input_idx),
531 "einsum transpose read primal input {input_idx} as a tensor operand but the \
532 residual mask does not declare it; declare it in the einsum rule's residual mask"
533 );
534 vjp_inputs.push(semantic_conjugate_if_complex(
535 builder,
536 primal_inputs[input_idx],
537 )?);
538 }
539 let vjp_op = semantic_vjp_einsum_op(
540 op,
541 active_idx,
542 EinsumSubscripts {
543 inputs: vjp_input_labels,
544 output: vjp_output_labels.clone(),
545 },
546 &vjp_input_shapes,
547 )?;
548 let mut input_cotangent = builder.add_extension(Arc::new(vjp_op), &vjp_inputs)?[0];
549 if vjp_output_labels != input_labels[active_idx] {
550 input_cotangent = semantic_broadcast_einsum_vjp(
551 builder,
552 input_cotangent,
553 &vjp_output_labels,
554 &input_labels[active_idx],
555 primal_input_shapes[active_idx].clone(),
556 )?;
557 }
558 result.push(AdValue::Value(input_cotangent));
559 }
560 Ok(result.into_boxed_slice())
561}
562
563#[cfg(feature = "autodiff")]
571fn broadcast_summed_labels(
572 builder: &SemanticProgramBuilder,
573 op: &EinsumExtensionOp,
574 active_idx: usize,
575 primal_inputs: &[ProgramValue],
576 cotangent: ProgramValue,
577) -> std::result::Result<HashSet<u32>, SemanticAdError> {
578 let mut summed = HashSet::new();
579 if !op.allow_broadcast() {
580 return Ok(summed);
581 }
582 let exact_extents = |value: ProgramValue| {
583 builder.resolved_extents(value).map(|extents| {
584 extents
585 .into_iter()
586 .map(|extent| match extent {
587 ShapeExtent::Exact(expr) => Some(expr),
588 ShapeExtent::UpperBound(_) | ShapeExtent::Unknown => None,
589 })
590 .collect::<Vec<_>>()
591 })
592 };
593 let input_extents = primal_inputs
594 .iter()
595 .map(|&value| exact_extents(value))
596 .collect::<std::result::Result<Vec<_>, _>>()?;
597 let output_extents = exact_extents(cotangent)?;
598
599 let subscripts = &op.subscripts;
600 for (axis, (&label, active)) in subscripts.inputs[active_idx]
601 .iter()
602 .zip(&input_extents[active_idx])
603 .enumerate()
604 {
605 let peer_operands = subscripts
606 .inputs
607 .iter()
608 .zip(&input_extents)
609 .enumerate()
610 .filter(|&(input_idx, _)| input_idx != active_idx)
611 .map(|(_, (labels, extents))| (labels.as_slice(), extents.as_slice()))
612 .chain(std::iter::once((
613 subscripts.output.as_slice(),
614 output_extents.as_slice(),
615 )));
616 let peers = peer_operands.flat_map(|(labels, extents)| {
617 labels
618 .iter()
619 .zip(extents)
620 .filter(move |&(&peer_label, _)| peer_label == label)
621 .map(move |(_, extent)| classify_dim_exprs(active.as_ref(), extent.as_ref()))
622 });
623 match broadcast_axis_reduce(peers) {
624 Ok(decision) => {
625 if decision.sums_label_out() {
626 summed.insert(label);
627 }
628 }
629 Err(UndecidedBroadcastAxis) => {
630 return Err(semantic_einsum_unsupported(format!(
631 "einsum VJP cannot decide whether axis {axis} of input {active_idx} \
632 (extent {active:?}) was singleton-broadcast: another extent of the same \
633 label is not provably equal to it or 1, and the gradient must sum the \
634 cotangent over the axis exactly when it was broadcast"
635 )));
636 }
637 }
638 }
639 Ok(summed)
640}
641
642#[cfg(feature = "autodiff")]
643fn semantic_vjp_einsum_op(
644 primal_op: &EinsumExtensionOp,
645 active_idx: usize,
646 subscripts: EinsumSubscripts,
647 input_shapes: &[Vec<DimExpr>],
648) -> std::result::Result<EinsumExtensionOp, SemanticAdError> {
649 let plan_spec =
650 vjp_plan_spec_for_active(primal_op.plan_spec(), primal_op.input_count(), active_idx)?;
651 let sym_shapes: Vec<Vec<SymDim>> = input_shapes
652 .iter()
653 .enumerate()
654 .map(|(input_idx, shape)| {
655 let tensor_id = u64::MAX - input_idx as u64;
656 shape
657 .iter()
658 .enumerate()
659 .map(|(axis, dim)| match dim {
660 DimExpr::Const(value) => SymDim::from(*value),
661 _ => SymDim::tensor_axis(tensor_id, axis),
662 })
663 .collect()
664 })
665 .collect();
666 if let Some(concrete_shapes) = concrete_sym_shapes(&sym_shapes) {
667 let shape_refs: Vec<&[usize]> = concrete_shapes.iter().map(Vec::as_slice).collect();
668 let raw_subscripts = Subscripts::from(&subscripts);
669 let _tree = resolve_plan_spec(&plan_spec, &raw_subscripts, &shape_refs)
670 .map_err(|source| semantic_einsum_unsupported(source.to_string()))?;
671 }
672 Ok(EinsumExtensionOp::with_plan_spec_and_broadcast(
673 subscripts,
674 plan_spec,
675 primal_op.allow_broadcast(),
676 ))
677}
678
679#[cfg(feature = "autodiff")]
680fn semantic_value_shape(
681 builder: &SemanticProgramBuilder,
682 value: ProgramValue,
683) -> std::result::Result<Vec<DimExpr>, SemanticAdError> {
684 semantic_metadata_shape(builder.value_metadata(value)?)
685}
686
687#[cfg(feature = "autodiff")]
688fn semantic_metadata_shape(
689 metadata: &ProgramValueMetadata,
690) -> std::result::Result<Vec<DimExpr>, SemanticAdError> {
691 metadata
692 .shape()
693 .iter()
694 .map(|extent| {
695 extent.bound_expr().cloned().ok_or_else(|| {
696 semantic_einsum_unsupported(
697 "einsum semantic AD requires a symbolic expression for every extent",
698 )
699 })
700 })
701 .collect()
702}
703
704#[cfg(feature = "autodiff")]
705fn semantic_conjugate_if_complex(
706 builder: &mut SemanticProgramBuilder,
707 value: ProgramValue,
708) -> std::result::Result<ProgramValue, SemanticAdError> {
709 if matches!(
710 builder.value_metadata(value)?.dtype(),
711 DType::C32 | DType::C64
712 ) {
713 Ok(builder.add_op(CoreSemanticOp::Conj, &[value])?[0])
714 } else {
715 Ok(value)
716 }
717}
718
719#[cfg(feature = "autodiff")]
720fn semantic_broadcast_einsum_vjp(
721 builder: &mut SemanticProgramBuilder,
722 cotangent: ProgramValue,
723 cotangent_labels: &[u32],
724 input_labels: &[u32],
725 shape: Vec<DimExpr>,
726) -> std::result::Result<ProgramValue, SemanticAdError> {
727 let dims = map_label_occurrences(cotangent_labels, input_labels).ok_or_else(|| {
728 semantic_einsum_unsupported(format!(
729 "einsum VJP cannot remap labels {cotangent_labels:?} into {input_labels:?}"
730 ))
731 })?;
732 let mut inputs = vec![cotangent];
736 let shape = builder.translate_input_shape_payload(&shape, &mut inputs);
737 let broadcast = builder.add_op(CoreSemanticOp::BroadcastInDim { shape, dims }, &inputs)?[0];
738 semantic_project_repeated_labels(builder, broadcast, input_labels)
739}
740
741#[cfg(feature = "autodiff")]
742fn semantic_project_repeated_labels(
743 builder: &mut SemanticProgramBuilder,
744 cotangent: ProgramValue,
745 labels: &[u32],
746) -> std::result::Result<ProgramValue, SemanticAdError> {
747 let mut result = cotangent;
748 let mut first_axis_by_label = HashMap::new();
749 for (axis_b, label) in labels.iter().copied().enumerate() {
750 let Some(&axis_a) = first_axis_by_label.get(&label) else {
751 first_axis_by_label.insert(label, axis_b);
752 continue;
753 };
754 let extracted =
755 builder.add_op(CoreSemanticOp::ExtractDiag { axis_a, axis_b }, &[result])?[0];
756 result = builder.add_op(CoreSemanticOp::EmbedDiag { axis_a, axis_b }, &[extracted])?[0];
757 }
758 Ok(result)
759}
760
761#[cfg(feature = "autodiff")]
762fn semantic_sum_terms(
763 builder: &mut SemanticProgramBuilder,
764 terms: Vec<ProgramValue>,
765) -> std::result::Result<AdValue, SemanticAdError> {
766 let mut terms = terms.into_iter();
767 let Some(mut sum) = terms.next() else {
768 return Ok(AdValue::Absent);
769 };
770 for term in terms {
771 sum = builder.add_op(CoreSemanticOp::Add, &[sum, term])?[0];
772 }
773 Ok(AdValue::Value(sum))
774}
775
776#[cfg(feature = "autodiff")]
777fn semantic_einsum_payload(
778 op: &dyn ExtensionOp,
779 role: SemanticAdRuleRole,
780) -> std::result::Result<&EinsumExtensionOp, SemanticAdError> {
781 op.as_any()
782 .downcast_ref::<EinsumExtensionOp>()
783 .ok_or_else(|| SemanticAdError::Unsupported {
784 family_id: EINSUM_EXTENSION_FAMILY_ID,
785 role,
786 message: "einsum semantic AD received an incompatible payload".into(),
787 })
788}
789
790#[cfg(feature = "autodiff")]
791fn semantic_einsum_unsupported(message: impl Into<String>) -> SemanticAdError {
792 SemanticAdError::Unsupported {
793 family_id: EINSUM_EXTENSION_FAMILY_ID,
794 role: SemanticAdRuleRole::LinearTranspose,
795 message: message.into(),
796 }
797}
798
799#[cfg(feature = "autodiff")]
800fn vjp_plan_spec_for_active(
801 primal_plan: &EinsumPlanSpec,
802 input_count: usize,
803 active_idx: usize,
804) -> std::result::Result<EinsumPlanSpec, SemanticAdError> {
805 if active_idx >= input_count {
806 return Err(semantic_einsum_unsupported(format!(
807 "einsum VJP active input {active_idx} is outside {input_count} inputs"
808 )));
809 }
810
811 match primal_plan {
812 EinsumPlanSpec::Auto(options) => Ok(EinsumPlanSpec::Auto(options.clone())),
813 EinsumPlanSpec::LeftToRight => Ok(EinsumPlanSpec::LeftToRight),
814 EinsumPlanSpec::Path(path) => {
815 let pairs = jax_path_to_v1_pairs(path, input_count).map_err(|err| {
816 semantic_einsum_unsupported(format!(
817 "failed to inherit einsum Path plan for VJP active input {active_idx}: {err}"
818 ))
819 })?;
820 derive_vjp_fixed_pairs(&pairs, input_count, active_idx).map(EinsumPlanSpec::FixedPairs)
821 }
822 EinsumPlanSpec::FixedPairs(pairs) => {
823 derive_vjp_fixed_pairs(pairs, input_count, active_idx).map(EinsumPlanSpec::FixedPairs)
824 }
825 }
826}
827
828#[cfg(feature = "autodiff")]
829fn derive_vjp_fixed_pairs(
830 primal_pairs: &[(usize, usize)],
831 input_count: usize,
832 active_idx: usize,
833) -> std::result::Result<Vec<(usize, usize)>, SemanticAdError> {
834 if input_count == 0 {
835 return Err(semantic_einsum_unsupported(
836 "einsum VJP cannot derive a plan for zero primal inputs",
837 ));
838 }
839 if active_idx >= input_count {
840 return Err(semantic_einsum_unsupported(format!(
841 "einsum VJP active input {active_idx} is outside {input_count} inputs"
842 )));
843 }
844 let required_steps = input_count.saturating_sub(1);
845 if primal_pairs.len() != required_steps {
846 return Err(semantic_einsum_unsupported(format!(
847 "einsum VJP cannot inherit explicit plan for active input {active_idx}: \
848 expected {required_steps} primal steps for {input_count} inputs, got {}",
849 primal_pairs.len()
850 )));
851 }
852 if input_count == 1 {
853 return Ok(Vec::new());
854 }
855
856 let children = fixed_pair_children(primal_pairs, input_count, active_idx)?;
857 let mut primal_to_vjp = vec![None; input_count];
858 let mut next_vjp_input = 1;
859 for (input_idx, slot) in primal_to_vjp.iter_mut().enumerate() {
860 if input_idx != active_idx {
861 *slot = Some(next_vjp_input);
862 next_vjp_input += 1;
863 }
864 }
865
866 let root = input_count + primal_pairs.len() - 1;
867 let mut pairs = Vec::with_capacity(required_steps);
868 let final_id = emit_vjp_adjoint(
869 root,
870 0,
871 &children,
872 input_count,
873 active_idx,
874 &primal_to_vjp,
875 &mut pairs,
876 )?;
877 let expected_final = input_count + pairs.len() - 1;
878 if final_id != expected_final || pairs.len() != required_steps {
879 return Err(semantic_einsum_unsupported(format!(
880 "einsum VJP plan derivation for active input {active_idx} produced an invalid \
881 tree: final id {final_id}, expected {expected_final}, steps {}",
882 pairs.len()
883 )));
884 }
885 Ok(pairs)
886}
887
888#[cfg(feature = "autodiff")]
889fn fixed_pair_children(
890 pairs: &[(usize, usize)],
891 input_count: usize,
892 active_idx: usize,
893) -> std::result::Result<Vec<Option<(usize, usize)>>, SemanticAdError> {
894 let mut live = vec![false; input_count + pairs.len()];
895 for slot in live.iter_mut().take(input_count) {
896 *slot = true;
897 }
898 let mut children = vec![None; input_count + pairs.len()];
899
900 for (step_idx, &(left, right)) in pairs.iter().enumerate() {
901 let next_idx = input_count + step_idx;
902 if left == right {
903 return Err(invalid_vjp_plan_error(
904 active_idx,
905 format!("pair ({left}, {right}) references the same operand"),
906 ));
907 }
908 if left >= next_idx || right >= next_idx {
909 return Err(invalid_vjp_plan_error(
910 active_idx,
911 format!("pair ({left}, {right}) references a non-existent operand"),
912 ));
913 }
914 if !live[left] || !live[right] {
915 return Err(invalid_vjp_plan_error(
916 active_idx,
917 format!("pair ({left}, {right}) references an operand that is no longer live"),
918 ));
919 }
920
921 live[left] = false;
922 live[right] = false;
923 live[next_idx] = true;
924 children[next_idx] = Some((left, right));
925 }
926
927 let live_count = live.iter().filter(|&&is_live| is_live).count();
928 if live_count != 1 {
929 return Err(invalid_vjp_plan_error(
930 active_idx,
931 format!("explicit plan leaves {live_count} live operands"),
932 ));
933 }
934
935 Ok(children)
936}
937
938#[cfg(feature = "autodiff")]
939fn emit_vjp_adjoint(
940 node: usize,
941 cotangent_id: usize,
942 children: &[Option<(usize, usize)>],
943 input_count: usize,
944 active_idx: usize,
945 primal_to_vjp: &[Option<usize>],
946 pairs: &mut Vec<(usize, usize)>,
947) -> std::result::Result<usize, SemanticAdError> {
948 if node < input_count {
949 return if node == active_idx {
950 Ok(cotangent_id)
951 } else {
952 Err(invalid_vjp_plan_error(
953 active_idx,
954 format!("adjoint walk reached inactive leaf {node}"),
955 ))
956 };
957 }
958
959 let (left, right) = children.get(node).and_then(|child| *child).ok_or_else(|| {
960 invalid_vjp_plan_error(active_idx, format!("missing children for node {node}"))
961 })?;
962 let left_has_active = subtree_contains_active(left, children, input_count, active_idx)?;
963 let right_has_active = subtree_contains_active(right, children, input_count, active_idx)?;
964 match (left_has_active, right_has_active) {
965 (true, false) => {
966 let sibling_id = emit_vjp_subtree(
967 right,
968 children,
969 input_count,
970 active_idx,
971 primal_to_vjp,
972 pairs,
973 )?;
974 let next = push_vjp_pair(cotangent_id, sibling_id, input_count, pairs);
975 emit_vjp_adjoint(
976 left,
977 next,
978 children,
979 input_count,
980 active_idx,
981 primal_to_vjp,
982 pairs,
983 )
984 }
985 (false, true) => {
986 let sibling_id = emit_vjp_subtree(
987 left,
988 children,
989 input_count,
990 active_idx,
991 primal_to_vjp,
992 pairs,
993 )?;
994 let next = push_vjp_pair(cotangent_id, sibling_id, input_count, pairs);
995 emit_vjp_adjoint(
996 right,
997 next,
998 children,
999 input_count,
1000 active_idx,
1001 primal_to_vjp,
1002 pairs,
1003 )
1004 }
1005 (true, true) => Err(invalid_vjp_plan_error(
1006 active_idx,
1007 format!("both children of node {node} contain the active input"),
1008 )),
1009 (false, false) => Err(invalid_vjp_plan_error(
1010 active_idx,
1011 format!("neither child of node {node} contains the active input"),
1012 )),
1013 }
1014}
1015
1016#[cfg(feature = "autodiff")]
1017fn emit_vjp_subtree(
1018 node: usize,
1019 children: &[Option<(usize, usize)>],
1020 input_count: usize,
1021 active_idx: usize,
1022 primal_to_vjp: &[Option<usize>],
1023 pairs: &mut Vec<(usize, usize)>,
1024) -> std::result::Result<usize, SemanticAdError> {
1025 if node < input_count {
1026 return primal_to_vjp[node].ok_or_else(|| {
1027 invalid_vjp_plan_error(
1028 active_idx,
1029 format!("sibling subtree unexpectedly reached active leaf {node}"),
1030 )
1031 });
1032 }
1033
1034 let (left, right) = children.get(node).and_then(|child| *child).ok_or_else(|| {
1035 invalid_vjp_plan_error(active_idx, format!("missing children for node {node}"))
1036 })?;
1037 let left_id = emit_vjp_subtree(
1038 left,
1039 children,
1040 input_count,
1041 active_idx,
1042 primal_to_vjp,
1043 pairs,
1044 )?;
1045 let right_id = emit_vjp_subtree(
1046 right,
1047 children,
1048 input_count,
1049 active_idx,
1050 primal_to_vjp,
1051 pairs,
1052 )?;
1053 Ok(push_vjp_pair(left_id, right_id, input_count, pairs))
1054}
1055
1056#[cfg(feature = "autodiff")]
1057fn push_vjp_pair(
1058 left: usize,
1059 right: usize,
1060 n_vjp_inputs: usize,
1061 pairs: &mut Vec<(usize, usize)>,
1062) -> usize {
1063 pairs.push((left, right));
1064 n_vjp_inputs + pairs.len() - 1
1065}
1066
1067#[cfg(feature = "autodiff")]
1068fn subtree_contains_active(
1069 node: usize,
1070 children: &[Option<(usize, usize)>],
1071 input_count: usize,
1072 active_idx: usize,
1073) -> std::result::Result<bool, SemanticAdError> {
1074 if node < input_count {
1075 return Ok(node == active_idx);
1076 }
1077 let (left, right) = children.get(node).and_then(|child| *child).ok_or_else(|| {
1078 invalid_vjp_plan_error(active_idx, format!("missing children for node {node}"))
1079 })?;
1080 Ok(
1081 subtree_contains_active(left, children, input_count, active_idx)?
1082 || subtree_contains_active(right, children, input_count, active_idx)?,
1083 )
1084}
1085
1086#[cfg(feature = "autodiff")]
1087fn invalid_vjp_plan_error(active_idx: usize, reason: String) -> SemanticAdError {
1088 semantic_einsum_unsupported(format!(
1089 "einsum VJP cannot inherit explicit plan for active input {active_idx}: {reason}"
1090 ))
1091}
1092
1093#[cfg(feature = "autodiff")]
1094fn concrete_sym_shapes(shapes: &[Vec<SymDim>]) -> Option<Vec<Vec<usize>>> {
1095 shapes
1096 .iter()
1097 .map(|shape| shape.iter().map(SymDim::constant_value).collect())
1098 .collect()
1099}
1100
1101define_extension_runtime! {
1102 runtime = EinsumRuntime,
1103 family_id = EINSUM_EXTENSION_FAMILY_ID,
1104 op_type = EinsumExtensionOp,
1105 execute_in_session = execute_einsum_extension_reads_in_session,
1106 session_supported = einsum_session_supported,
1107}
1108
1109pub(crate) fn execute_einsum_extension_session_reads(
1110 op: &EinsumExtensionOp,
1111 inputs: &[TensorRead<'_>],
1112 ctx: &mut ExtensionExecutionContext<'_, dyn Engine + '_>,
1113) -> tenferro_tensor::Result<Vec<Tensor>> {
1114 if inputs.is_empty() {
1115 return Err(tenferro_tensor::Error::invalid_argument(
1116 "einsum_extension",
1117 "inputs",
1118 "einsum requires at least one input tensor",
1119 ));
1120 }
1121
1122 let shapes: Vec<Vec<usize>> = inputs.iter().map(|input| input.shape().to_vec()).collect();
1123 let shape_refs: Vec<&[usize]> = shapes.iter().map(Vec::as_slice).collect();
1124 let subs = Subscripts::from(op.subscripts());
1125 let tree = cached_runtime_tree(ctx, op.subscripts(), op.plan_spec(), &shapes, || {
1126 resolve_plan_spec(op.plan_spec(), &subs, &shape_refs)
1127 })?;
1128 let output = crate::eager::eager_einsum_exec_read(ctx.backend_mut(), inputs, &tree)?;
1129 Ok(vec![output])
1130}
1131
1132fn execute_einsum_extension_reads_in_session(
1136 op: &EinsumExtensionOp,
1137 session: &mut dyn Engine,
1138 caches: &mut tenferro_runtime::ExtensionCacheStore,
1139 inputs: &[TensorRead<'_>],
1140) -> tenferro_tensor::Result<Vec<Tensor>> {
1141 let mut ctx = ExtensionExecutionContext::new(session, caches);
1142 execute_einsum_extension_session_reads(op, inputs, &mut ctx)
1143}
1144
1145fn einsum_session_supported<B: tenferro_tensor::Engine + 'static>(_op: &EinsumExtensionOp) -> bool {
1146 let type_id = std::any::TypeId::of::<B>();
1150 type_id == std::any::TypeId::of::<tenferro_cpu::CpuEngine>() || {
1151 #[cfg(feature = "cuda")]
1152 {
1153 type_id == std::any::TypeId::of::<tenferro_gpu::cuda::CudaEngine>()
1154 }
1155 #[cfg(not(feature = "cuda"))]
1156 {
1157 false
1158 }
1159 }
1160}
1161
1162#[derive(Clone)]
1163struct RuntimeTreeCacheKeyData {
1164 subscripts: EinsumSubscripts,
1165 shapes: Vec<Vec<usize>>,
1166 plan_spec: EinsumPlanSpec,
1167}
1168
1169impl RuntimeTreeCacheKeyData {
1170 fn new(
1171 subscripts: &EinsumSubscripts,
1172 shapes: &[Vec<usize>],
1173 plan_spec: &EinsumPlanSpec,
1174 ) -> Self {
1175 Self {
1176 subscripts: subscripts.clone(),
1177 shapes: shapes.to_vec(),
1178 plan_spec: plan_spec.clone(),
1179 }
1180 }
1181
1182 fn matches_runtime_tree(
1183 &self,
1184 subscripts: &EinsumSubscripts,
1185 shapes: &[Vec<usize>],
1186 plan_spec: &EinsumPlanSpec,
1187 ) -> bool {
1188 self.subscripts == *subscripts
1189 && self.shapes.as_slice() == shapes
1190 && plan_specs_equal(&self.plan_spec, plan_spec)
1191 }
1192
1193 fn retained_bytes(&self) -> usize {
1194 saturating_sum([
1195 einsum_subscripts_retained_bytes(&self.subscripts),
1196 saturating_sum(self.shapes.iter().map(vec_retained_bytes)),
1197 plan_spec_retained_bytes(&self.plan_spec),
1198 ])
1199 }
1200}
1201
1202struct CachedRuntimeTree {
1203 key_data: RuntimeTreeCacheKeyData,
1204 tree: Arc<ContractionTree>,
1205}
1206
1207fn cached_runtime_tree<B: Engine + ?Sized>(
1208 ctx: &mut ExtensionExecutionContext<'_, B>,
1209 subscripts: &EinsumSubscripts,
1210 plan_spec: &EinsumPlanSpec,
1211 shapes: &[Vec<usize>],
1212 build: impl FnOnce() -> EinsumResult<ContractionTree>,
1213) -> tenferro_tensor::Result<Arc<ContractionTree>> {
1214 let plan_hash = plan_spec_hash(plan_spec);
1215 let key = ExtensionCacheKey::new(
1216 EINSUM_EXTENSION_FAMILY_ID,
1217 EINSUM_RUNTIME_PLANS_CACHE,
1218 runtime_tree_cache_discriminator(subscripts, shapes, plan_hash),
1219 );
1220 if let Some(cached) = ctx.caches_mut().get::<CachedRuntimeTree>(&key) {
1221 let key_data = &cached.key_data;
1222 if key_data.matches_runtime_tree(subscripts, shapes, plan_spec) {
1223 return Ok(Arc::clone(&cached.tree));
1224 }
1225 }
1226
1227 let tree = Arc::new(build().map_err(einsum_runtime_error)?);
1228 let key_data = RuntimeTreeCacheKeyData::new(subscripts, shapes, plan_spec);
1229 let retained_bytes = saturating_sum([
1230 key_data.retained_bytes(),
1231 tree.retained_bytes_for_cache_stats(),
1232 ]);
1233 ctx.caches_mut().put(
1234 key,
1235 CachedRuntimeTree {
1236 key_data,
1237 tree: Arc::clone(&tree),
1238 },
1239 retained_bytes,
1240 );
1241 Ok(tree)
1242}
1243
1244fn einsum_runtime_error(error: EinsumError) -> tenferro_tensor::Error {
1245 error.into_tensor_error("einsum_extension")
1246}
1247
1248fn runtime_tree_cache_discriminator(
1249 subscripts: &EinsumSubscripts,
1250 shapes: &[Vec<usize>],
1251 plan_hash: u64,
1252) -> u64 {
1253 let mut hasher = DefaultHasher::new();
1254 subscripts.hash(&mut hasher);
1255 shapes.hash(&mut hasher);
1256 plan_hash.hash(&mut hasher);
1257 hasher.finish()
1258}
1259
1260fn plan_spec_hash(plan_spec: &EinsumPlanSpec) -> u64 {
1261 let mut hasher = DefaultHasher::new();
1262 hash_einsum_plan_spec(plan_spec, &mut hasher);
1263 hasher.finish()
1264}
1265
1266fn plan_spec_retained_bytes(plan_spec: &EinsumPlanSpec) -> usize {
1267 match plan_spec {
1268 EinsumPlanSpec::Auto(options) => saturating_sum([
1269 std::mem::size_of::<EinsumPlanSpec>(),
1270 vec_retained_bytes(&options.betas),
1271 ]),
1272 EinsumPlanSpec::LeftToRight => std::mem::size_of::<EinsumPlanSpec>(),
1273 EinsumPlanSpec::Path(path) | EinsumPlanSpec::FixedPairs(path) => saturating_sum([
1274 std::mem::size_of::<EinsumPlanSpec>(),
1275 vec_retained_bytes(path),
1276 ]),
1277 }
1278}
1279
1280fn promote_dtypes(dtypes: impl IntoIterator<Item = DType>) -> DType {
1281 dtypes
1282 .into_iter()
1283 .reduce(tenferro_tensor::validate::promote_dtype)
1284 .unwrap_or(DType::F64)
1285}
1286
1287#[cfg(test)]
1288mod tests;