shader-compiler/src/cfg.rs

   1 // SPDX-License-Identifier: LGPL-2.1-or-later
   2 // Copyright 2018 Jacob Lifshay
   3
   4 use spirv_parser::{IdRef, IdResult, Instruction};
   5 use std::cell::RefCell;
   6 use std::collections::HashMap;
   7 use std::fmt;
   8 use std::mem;
   9 use std::rc::{Rc, Weak};
  10
  11 pub(crate) trait GenericNode: Clone + fmt::Debug {
  12     fn instructions(&self) -> &Vec<Instruction>;
  13     fn to_node(this: Rc<Self>) -> Node;
  14     fn label(&self) -> IdRef;
  15 }
  16
  17 #[derive(Clone, Debug)]
  18 pub(crate) struct SimpleNode {
  19     pub(crate) label: IdRef,
  20     pub(crate) instructions: Vec<Instruction>,
  21     pub(crate) next: Node,
  22 }
  23
  24 impl GenericNode for SimpleNode {
  25     fn instructions(&self) -> &Vec<Instruction> {
  26         &self.instructions
  27     }
  28     fn to_node(this: Rc<Self>) -> Node {
  29         Node::Simple(this)
  30     }
  31     fn label(&self) -> IdRef {
  32         self.label
  33     }
  34 }
  35
  36 #[derive(Clone, Debug)]
  37 pub(crate) struct SwitchDefault {
  38     pub(crate) default_case: Node,
  39     pub(crate) after_default_cases: Vec<Node>,
  40 }
  41
  42 #[derive(Clone, Debug)]
  43 pub(crate) struct SwitchNode {
  44     pub(crate) label: IdRef,
  45     pub(crate) instructions: Vec<Instruction>,
  46     pub(crate) before_default_cases: Vec<Node>,
  47     pub(crate) default: Option<SwitchDefault>,
  48     pub(crate) next: Node,
  49 }
  50
  51 impl GenericNode for SwitchNode {
  52     fn instructions(&self) -> &Vec<Instruction> {
  53         &self.instructions
  54     }
  55     fn to_node(this: Rc<Self>) -> Node {
  56         Node::Switch(this)
  57     }
  58     fn label(&self) -> IdRef {
  59         self.label
  60     }
  61 }
  62
  63 #[derive(Clone, Debug)]
  64 pub(crate) struct SwitchFallthroughNode {
  65     pub(crate) label: IdRef,
  66     pub(crate) instructions: Vec<Instruction>,
  67     pub(crate) switch: RefCell<Weak<SwitchNode>>,
  68 }
  69
  70 impl GenericNode for SwitchFallthroughNode {
  71     fn instructions(&self) -> &Vec<Instruction> {
  72         &self.instructions
  73     }
  74     fn to_node(this: Rc<Self>) -> Node {
  75         Node::SwitchFallthrough(this)
  76     }
  77     fn label(&self) -> IdRef {
  78         self.label
  79     }
  80 }
  81
  82 #[derive(Clone, Debug)]
  83 pub(crate) struct SwitchMergeNode {
  84     pub(crate) label: IdRef,
  85     pub(crate) instructions: Vec<Instruction>,
  86     pub(crate) switch: RefCell<Weak<SwitchNode>>,
  87 }
  88
  89 impl GenericNode for SwitchMergeNode {
  90     fn instructions(&self) -> &Vec<Instruction> {
  91         &self.instructions
  92     }
  93     fn to_node(this: Rc<Self>) -> Node {
  94         Node::SwitchMerge(this)
  95     }
  96     fn label(&self) -> IdRef {
  97         self.label
  98     }
  99 }
 100
 101 #[derive(Clone, Debug)]
 102 pub(crate) struct ConditionNode {
 103     pub(crate) label: IdRef,
 104     pub(crate) instructions: Vec<Instruction>,
 105     pub(crate) true_node: Option<Node>,
 106     pub(crate) false_node: Option<Node>,
 107     pub(crate) next: Node,
 108 }
 109
 110 impl GenericNode for ConditionNode {
 111     fn instructions(&self) -> &Vec<Instruction> {
 112         &self.instructions
 113     }
 114     fn to_node(this: Rc<Self>) -> Node {
 115         Node::Condition(this)
 116     }
 117     fn label(&self) -> IdRef {
 118         self.label
 119     }
 120 }
 121
 122 #[derive(Clone, Debug)]
 123 pub(crate) struct ConditionMergeNode {
 124     pub(crate) label: IdRef,
 125     pub(crate) instructions: Vec<Instruction>,
 126     pub(crate) condition_node: RefCell<Weak<ConditionNode>>,
 127 }
 128
 129 impl GenericNode for ConditionMergeNode {
 130     fn instructions(&self) -> &Vec<Instruction> {
 131         &self.instructions
 132     }
 133     fn to_node(this: Rc<Self>) -> Node {
 134         Node::ConditionMerge(this)
 135     }
 136     fn label(&self) -> IdRef {
 137         self.label
 138     }
 139 }
 140
 141 #[derive(Clone, Debug)]
 142 pub(crate) struct ReturnNode {
 143     pub(crate) label: IdRef,
 144     pub(crate) instructions: Vec<Instruction>,
 145 }
 146
 147 impl GenericNode for ReturnNode {
 148     fn instructions(&self) -> &Vec<Instruction> {
 149         &self.instructions
 150     }
 151     fn to_node(this: Rc<Self>) -> Node {
 152         Node::Return(this)
 153     }
 154     fn label(&self) -> IdRef {
 155         self.label
 156     }
 157 }
 158
 159 #[derive(Clone, Debug)]
 160 pub(crate) struct DiscardNode {
 161     pub(crate) label: IdRef,
 162     pub(crate) instructions: Vec<Instruction>,
 163 }
 164
 165 impl GenericNode for DiscardNode {
 166     fn instructions(&self) -> &Vec<Instruction> {
 167         &self.instructions
 168     }
 169     fn to_node(this: Rc<Self>) -> Node {
 170         Node::Discard(this)
 171     }
 172     fn label(&self) -> IdRef {
 173         self.label
 174     }
 175 }
 176
 177 #[derive(Clone, Debug)]
 178 pub(crate) enum Node {
 179     Simple(Rc<SimpleNode>),
 180     Return(Rc<ReturnNode>),
 181     Discard(Rc<DiscardNode>),
 182     Switch(Rc<SwitchNode>),
 183     SwitchFallthrough(Rc<SwitchFallthroughNode>),
 184     SwitchMerge(Rc<SwitchMergeNode>),
 185     Condition(Rc<ConditionNode>),
 186     ConditionMerge(Rc<ConditionMergeNode>),
 187 }
 188
 189 impl Node {
 190     pub(crate) fn instructions(&self) -> &Vec<Instruction> {
 191         match self {
 192             Node::Simple(v) => v.instructions(),
 193             Node::Return(v) => v.instructions(),
 194             Node::Discard(v) => v.instructions(),
 195             Node::Switch(v) => v.instructions(),
 196             Node::SwitchFallthrough(v) => v.instructions(),
 197             Node::SwitchMerge(v) => v.instructions(),
 198             Node::Condition(v) => v.instructions(),
 199             Node::ConditionMerge(v) => v.instructions(),
 200         }
 201     }
 202     pub(crate) fn label(&self) -> IdRef {
 203         match self {
 204             Node::Simple(v) => v.label(),
 205             Node::Return(v) => v.label(),
 206             Node::Discard(v) => v.label(),
 207             Node::Switch(v) => v.label(),
 208             Node::SwitchFallthrough(v) => v.label(),
 209             Node::SwitchMerge(v) => v.label(),
 210             Node::Condition(v) => v.label(),
 211             Node::ConditionMerge(v) => v.label(),
 212         }
 213     }
 214 }
 215
 216 impl<T: GenericNode> From<Rc<T>> for Node {
 217     fn from(v: Rc<T>) -> Node {
 218         GenericNode::to_node(v)
 219     }
 220 }
 221
 222 #[derive(Copy, Clone, Eq, PartialEq, Hash, Debug)]
 223 enum SwitchCaseKind {
 224     Default,
 225     Normal,
 226 }
 227
 228 #[derive(Copy, Clone, Eq, PartialEq, Hash, Debug)]
 229 enum BlockKind {
 230     Unknown,
 231     ConditionMerge,
 232     LoopMerge,
 233     LoopContinue,
 234     SwitchCase(SwitchCaseKind),
 235     SwitchMerge,
 236 }
 237
 238 struct BasicBlock<'a> {
 239     label_id: IdRef,
 240     label_line_instructions: &'a [Instruction],
 241     instructions: &'a [Instruction],
 242     kind: RefCell<BlockKind>,
 243 }
 244
 245 impl<'a> BasicBlock<'a> {
 246     fn get_instructions(&self) -> Vec<Instruction> {
 247         let mut retval: Vec<Instruction> =
 248             Vec::with_capacity(self.label_line_instructions.len() + 1 + self.instructions.len());
 249         retval.extend(self.label_line_instructions.iter().map(Clone::clone));
 250         retval.push(Instruction::Label {
 251             id_result: IdResult(self.label_id),
 252         });
 253         retval.extend(self.instructions.iter().map(Clone::clone));
 254         retval
 255     }
 256     fn set_kind(&self, kind: BlockKind) {
 257         match self.kind.replace(kind) {
 258             BlockKind::Unknown => {}
 259             kind => unreachable!("block kind already set to {:?}", kind),
 260         }
 261     }
 262 }
 263
 264 impl<'a> fmt::Debug for BasicBlock<'a> {
 265     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 266         write!(f, "BasicBlock:\n")?;
 267         for instruction in self.get_instructions() {
 268             write!(f, "{}", instruction)?;
 269         }
 270         Ok(())
 271     }
 272 }
 273
 274 struct ParseStateCondition {
 275     merges: Vec<Rc<ConditionMergeNode>>,
 276     merge_label: IdRef,
 277 }
 278
 279 struct ParseStateSwitch {
 280     fallthrough: Option<Rc<SwitchFallthroughNode>>,
 281     default_label: IdRef,
 282     merges: Vec<Rc<SwitchMergeNode>>,
 283     merge_label: IdRef,
 284     fallthrough_target: Option<IdRef>,
 285 }
 286
 287 struct ParseState {
 288     condition: Option<ParseStateCondition>,
 289     switch: Option<ParseStateSwitch>,
 290 }
 291
 292 fn get_basic_block<'a, 'b>(
 293     basic_blocks: &'b HashMap<IdRef, BasicBlock<'a>>,
 294     label_id: IdRef,
 295 ) -> &'b BasicBlock<'a> {
 296     basic_blocks
 297         .get(&label_id)
 298         .unwrap_or_else(|| unreachable!("label not found: {}", label_id))
 299 }
 300
 301 impl ParseState {
 302     fn push_condition(&mut self, condition: ParseStateCondition) -> Option<ParseStateCondition> {
 303         mem::replace(&mut self.condition, Some(condition))
 304     }
 305     fn pop_condition(&mut self, old_condition: Option<ParseStateCondition>) -> ParseStateCondition {
 306         mem::replace(&mut self.condition, old_condition).unwrap()
 307     }
 308     fn push_switch(&mut self, switch: ParseStateSwitch) -> Option<ParseStateSwitch> {
 309         mem::replace(&mut self.switch, Some(switch))
 310     }
 311     fn pop_switch(&mut self, old_switch: Option<ParseStateSwitch>) -> ParseStateSwitch {
 312         mem::replace(&mut self.switch, old_switch).unwrap()
 313     }
 314     fn get_switch(&mut self) -> &mut ParseStateSwitch {
 315         self.switch.as_mut().unwrap()
 316     }
 317     fn parse_switch<T>(
 318         &mut self,
 319         basic_blocks: &HashMap<IdRef, BasicBlock>,
 320         label_id: IdRef,
 321         basic_block: &BasicBlock,
 322         targets: &[(T, IdRef)],
 323         default_label: IdRef,
 324         merge_block: IdRef,
 325     ) -> Node {
 326         get_basic_block(basic_blocks, merge_block).set_kind(BlockKind::SwitchMerge);
 327         let mut last_target = None;
 328         for &(_, target) in targets {
 329             if Some(target) == last_target {
 330                 continue;
 331             }
 332             last_target = Some(target);
 333             if target != merge_block {
 334                 get_basic_block(basic_blocks, target)
 335                     .set_kind(BlockKind::SwitchCase(SwitchCaseKind::Normal));
 336             }
 337         }
 338         if default_label != merge_block {
 339             get_basic_block(basic_blocks, default_label)
 340                 .set_kind(BlockKind::SwitchCase(SwitchCaseKind::Default));
 341         }
 342         let old_switch = self.push_switch(ParseStateSwitch {
 343             default_label: default_label,
 344             fallthrough: None,
 345             merge_label: merge_block,
 346             merges: vec![],
 347             fallthrough_target: None,
 348         });
 349         let default_node = if default_label != merge_block {
 350             Some(self.parse(basic_blocks, default_label))
 351         } else {
 352             None
 353         };
 354         let mut default_fallthrough = self.get_switch().fallthrough.take();
 355         let mut default_fallthrough_target = self.get_switch().fallthrough_target.take();
 356         let mut cases = Vec::with_capacity(targets.len());
 357         struct Case {
 358             node: Node,
 359             fallthrough: Option<Rc<SwitchFallthroughNode>>,
 360             fallthrough_target: Option<IdRef>,
 361         }
 362         let mut last_target = None;
 363         for (index, &(_, target)) in targets.iter().enumerate() {
 364             if Some(target) == last_target {
 365                 continue;
 366             }
 367             last_target = Some(target);
 368             let node = self.parse(basic_blocks, target);
 369             let fallthrough_target = self.get_switch().fallthrough_target.take();
 370             if let Some(fallthrough_target) = fallthrough_target {
 371                 if default_label != fallthrough_target {
 372                     assert_eq!(
 373                         Some(fallthrough_target),
 374                         targets.get(index + 1).map(|v| v.1),
 375                         "invalid fallthrough branch"
 376                     );
 377                 }
 378             }
 379             cases.push(Case {
 380                 node,
 381                 fallthrough: self.get_switch().fallthrough.take(),
 382                 fallthrough_target,
 383             });
 384         }
 385         let switch = self.pop_switch(old_switch);
 386         let mut before_default_cases = None;
 387         let mut output_cases = vec![];
 388         let mut fallthroughs = vec![];
 389         fallthroughs.extend(default_fallthrough);
 390         for (
 391             index,
 392             Case {
 393                 node,
 394                 fallthrough,
 395                 fallthrough_target,
 396             },
 397         ) in cases.into_iter().enumerate()
 398         {
 399             if Some(node.label()) == default_fallthrough_target {
 400                 if before_default_cases.is_none() {
 401                     before_default_cases = Some(mem::replace(&mut output_cases, vec![]));
 402                 } else {
 403                     assert!(output_cases.is_empty(), "invalid fallthrough branch");
 404                 }
 405             }
 406             output_cases.push(node);
 407             fallthroughs.extend(fallthrough);
 408             if Some(default_label) == fallthrough_target {
 409                 assert!(before_default_cases.is_none());
 410                 before_default_cases = Some(mem::replace(&mut output_cases, vec![]));
 411             }
 412         }
 413         let before_default_cases =
 414             before_default_cases.unwrap_or_else(|| mem::replace(&mut output_cases, vec![]));
 415         let default = if let Some(default_node) = default_node {
 416             Some(SwitchDefault {
 417                 default_case: default_node,
 418                 after_default_cases: output_cases,
 419             })
 420         } else {
 421             None
 422         };
 423         let next = self.parse(basic_blocks, merge_block);
 424         let retval = Rc::new(SwitchNode {
 425             label: label_id,
 426             instructions: basic_block.get_instructions(),
 427             before_default_cases,
 428             default,
 429             next,
 430         });
 431         for fallthrough in fallthroughs {
 432             fallthrough.switch.replace(Rc::downgrade(&retval));
 433         }
 434         for merge in switch.merges {
 435             merge.switch.replace(Rc::downgrade(&retval));
 436         }
 437         retval.into()
 438     }
 439     #[cfg_attr(feature = "cargo-clippy", allow(clippy::cyclomatic_complexity))]
 440     fn parse(&mut self, basic_blocks: &HashMap<IdRef, BasicBlock>, label_id: IdRef) -> Node {
 441         let basic_block = get_basic_block(basic_blocks, label_id);
 442         let (terminating_instruction, instructions_without_terminator) = basic_block
 443             .instructions
 444             .split_last()
 445             .expect("missing terminating instruction");
 446         let control_header_instruction = instructions_without_terminator.last();
 447         match (terminating_instruction, control_header_instruction) {
 448             (
 449                 &Instruction::Branch { target_label },
 450                 Some(&Instruction::LoopMerge {
 451                     merge_block,
 452                     continue_target,
 453                     ..
 454                 }),
 455             ) => unimplemented!(),
 456             (&Instruction::Branch { target_label }, _) => {
 457                 let kind = *get_basic_block(basic_blocks, target_label).kind.borrow();
 458                 match kind {
 459                     BlockKind::Unknown => {
 460                         let next = self.parse(basic_blocks, target_label);
 461                         Rc::new(SimpleNode {
 462                             label: label_id,
 463                             instructions: basic_block.get_instructions(),
 464                             next,
 465                         })
 466                         .into()
 467                     }
 468                     BlockKind::ConditionMerge => {
 469                         let mut condition = self
 470                             .condition
 471                             .as_mut()
 472                             .expect("invalid branch to merge block");
 473                         assert_eq!(
 474                             target_label, condition.merge_label,
 475                             "invalid branch to merge block"
 476                         );
 477                         let retval = Rc::new(ConditionMergeNode {
 478                             label: label_id,
 479                             instructions: basic_block.get_instructions(),
 480                             condition_node: Default::default(),
 481                         });
 482                         condition.merges.push(retval.clone());
 483                         retval.into()
 484                     }
 485                     BlockKind::LoopMerge => unimplemented!(),
 486                     BlockKind::LoopContinue => unimplemented!(),
 487                     BlockKind::SwitchCase(kind) => {
 488                         let mut switch = self.get_switch();
 489                         let retval = Rc::new(SwitchFallthroughNode {
 490                             label: label_id,
 491                             instructions: basic_block.get_instructions(),
 492                             switch: Default::default(),
 493                         });
 494                         assert!(switch.fallthrough_target.is_none());
 495                         assert!(switch.fallthrough.is_none());
 496                         switch.fallthrough_target = Some(target_label);
 497                         switch.fallthrough = Some(retval.clone());
 498                         retval.into()
 499                     }
 500                     BlockKind::SwitchMerge => {
 501                         assert_eq!(
 502                             target_label,
 503                             self.get_switch().merge_label,
 504                             "invalid branch to merge block"
 505                         );
 506                         let retval = Rc::new(SwitchMergeNode {
 507                             label: label_id,
 508                             instructions: basic_block.get_instructions(),
 509                             switch: Default::default(),
 510                         });
 511                         self.get_switch().merges.push(retval.clone());
 512                         retval.into()
 513                     }
 514                 }
 515             }
 516             (
 517                 &Instruction::BranchConditional {
 518                     true_label,
 519                     false_label,
 520                     ..
 521                 },
 522                 Some(&Instruction::LoopMerge {
 523                     merge_block,
 524                     continue_target,
 525                     ..
 526                 }),
 527             ) => unimplemented!(),
 528             (
 529                 &Instruction::BranchConditional {
 530                     true_label,
 531                     false_label,
 532                     ..
 533                 },
 534                 Some(&Instruction::SelectionMerge { merge_block, .. }),
 535             ) => {
 536                 get_basic_block(basic_blocks, merge_block).set_kind(BlockKind::ConditionMerge);
 537                 let old_condition = self.push_condition(ParseStateCondition {
 538                     merge_label: merge_block,
 539                     merges: Vec::new(),
 540                 });
 541                 let true_node = if true_label != merge_block {
 542                     Some(self.parse(basic_blocks, true_label))
 543                 } else {
 544                     None
 545                 };
 546                 let false_node = if false_label != merge_block {
 547                     Some(self.parse(basic_blocks, false_label))
 548                 } else {
 549                     None
 550                 };
 551                 let condition = self.pop_condition(old_condition);
 552                 let next = self.parse(basic_blocks, merge_block);
 553                 let retval = Rc::new(ConditionNode {
 554                     label: label_id,
 555                     instructions: basic_block.get_instructions(),
 556                     true_node,
 557                     false_node,
 558                     next,
 559                 });
 560                 for merge in condition.merges {
 561                     merge.condition_node.replace(Rc::downgrade(&retval));
 562                 }
 563                 retval.into()
 564             }
 565             (&Instruction::BranchConditional { .. }, _) => {
 566                 unreachable!("missing merge instruction")
 567             }
 568             (
 569                 &Instruction::Switch32 {
 570                     default: default_label,
 571                     target: ref targets,
 572                     ..
 573                 },
 574                 Some(&Instruction::SelectionMerge { merge_block, .. }),
 575             ) => self.parse_switch(
 576                 basic_blocks,
 577                 label_id,
 578                 basic_block,
 579                 targets,
 580                 default_label,
 581                 merge_block,
 582             ),
 583             (
 584                 &Instruction::Switch64 {
 585                     default: default_label,
 586                     target: ref targets,
 587                     ..
 588                 },
 589                 Some(&Instruction::SelectionMerge { merge_block, .. }),
 590             ) => self.parse_switch(
 591                 basic_blocks,
 592                 label_id,
 593                 basic_block,
 594                 targets,
 595                 default_label,
 596                 merge_block,
 597             ),
 598             (&Instruction::Switch32 { .. }, _) => unreachable!("missing merge instruction"),
 599             (&Instruction::Switch64 { .. }, _) => unreachable!("missing merge instruction"),
 600             (&Instruction::Kill {}, _) => Rc::new(DiscardNode {
 601                 label: label_id,
 602                 instructions: basic_block.get_instructions(),
 603             })
 604             .into(),
 605             (&Instruction::Return {}, _) => Rc::new(ReturnNode {
 606                 label: label_id,
 607                 instructions: basic_block.get_instructions(),
 608             })
 609             .into(),
 610             (&Instruction::ReturnValue { .. }, _) => Rc::new(ReturnNode {
 611                 label: label_id,
 612                 instructions: basic_block.get_instructions(),
 613             })
 614             .into(),
 615             (&Instruction::Unreachable {}, _) => unimplemented!(),
 616             _ => unreachable!(
 617                 "invalid basic block terminating instruction:\n{}",
 618                 terminating_instruction
 619             ),
 620         }
 621     }
 622 }
 623
 624 pub(crate) fn create_cfg(mut input_instructions: &[Instruction]) -> Node {
 625     let mut basic_blocks = HashMap::new();
 626     let mut first_block = None;
 627     'split_into_blocks: while !input_instructions.is_empty() {
 628         let (label_id, label_line_instructions) = 'find_label: loop {
 629             for (i, instruction) in input_instructions.iter().enumerate() {
 630                 match instruction {
 631                     Instruction::Label { id_result } => {
 632                         break 'find_label (id_result.0, &input_instructions[..i]);
 633                     }
 634                     Instruction::NoLine {} | Instruction::Line { .. } => {}
 635                     _ => break,
 636                 }
 637             }
 638             unreachable!("missing OpLabel")
 639         };
 640         if first_block.is_none() {
 641             first_block = Some(label_id);
 642         }
 643         for i in 0..input_instructions.len() {
 644             match &input_instructions[i] {
 645                 Instruction::Branch { .. }
 646                 | Instruction::BranchConditional { .. }
 647                 | Instruction::Switch32 { .. }
 648                 | Instruction::Switch64 { .. }
 649                 | Instruction::Kill { .. }
 650                 | Instruction::Return { .. }
 651                 | Instruction::ReturnValue { .. }
 652                 | Instruction::Unreachable { .. } => {
 653                     let (instructions, rest) = input_instructions.split_at(i + 1);
 654                     input_instructions = rest;
 655                     let previous = basic_blocks.insert(
 656                         label_id,
 657                         BasicBlock {
 658                             label_line_instructions,
 659                             label_id,
 660                             instructions,
 661                             kind: RefCell::new(BlockKind::Unknown),
 662                         },
 663                     );
 664                     assert!(previous.is_none(), "duplicate OpLabel: {}", label_id);
 665                     continue 'split_into_blocks;
 666                 }
 667                 _ => {}
 668             }
 669         }
 670         unreachable!("missing terminating instruction");
 671     }
 672     let first_block = first_block.expect("missing OpLabel");
 673     ParseState {
 674         condition: None,
 675         switch: None,
 676     }
 677     .parse(&basic_blocks, first_block)
 678 }
 679
 680 #[cfg(test)]
 681 mod tests {
 682     use super::*;
 683
 684     struct IdFactory(u32);
 685
 686     impl IdFactory {
 687         fn new() -> IdFactory {
 688             IdFactory(1)
 689         }
 690         fn next(&mut self) -> IdRef {
 691             let retval = IdRef(self.0);
 692             self.0 += 1;
 693             retval
 694         }
 695     }
 696
 697     #[derive(Debug, Eq, PartialEq, Clone)]
 698     enum SerializedCFGElement {
 699         Simple,
 700         Return,
 701         Discard,
 702         Switch,
 703         SwitchCase,
 704         SwitchDefaultCase,
 705         SwitchEnd,
 706         SwitchFallthrough,
 707         SwitchMerge,
 708         Condition,
 709         ConditionTrue,
 710         ConditionFalse,
 711         ConditionEnd,
 712         ConditionMerge,
 713     }
 714
 715     trait SerializeCFG {
 716         fn serialize_cfg(&self, output: &mut Vec<SerializedCFGElement>);
 717         fn serialize_cfg_into_vec(&self) -> Vec<SerializedCFGElement> {
 718             let mut retval = Vec::new();
 719             self.serialize_cfg(&mut retval);
 720             retval
 721         }
 722     }
 723
 724     impl<T: SerializeCFG> SerializeCFG for Rc<T> {
 725         fn serialize_cfg(&self, output: &mut Vec<SerializedCFGElement>) {
 726             (**self).serialize_cfg(output)
 727         }
 728     }
 729
 730     impl<'a, T: SerializeCFG> SerializeCFG for &'a T {
 731         fn serialize_cfg(&self, output: &mut Vec<SerializedCFGElement>) {
 732             (**self).serialize_cfg(output)
 733         }
 734     }
 735
 736     impl SerializeCFG for SimpleNode {
 737         fn serialize_cfg(&self, output: &mut Vec<SerializedCFGElement>) {
 738             output.push(SerializedCFGElement::Simple);
 739             self.next.serialize_cfg(output)
 740         }
 741     }
 742
 743     impl SerializeCFG for ReturnNode {
 744         fn serialize_cfg(&self, output: &mut Vec<SerializedCFGElement>) {
 745             output.push(SerializedCFGElement::Return);
 746         }
 747     }
 748
 749     impl SerializeCFG for DiscardNode {
 750         fn serialize_cfg(&self, output: &mut Vec<SerializedCFGElement>) {
 751             output.push(SerializedCFGElement::Discard);
 752         }
 753     }
 754
 755     impl SerializeCFG for SwitchNode {
 756         fn serialize_cfg(&self, output: &mut Vec<SerializedCFGElement>) {
 757             output.push(SerializedCFGElement::Switch);
 758             for case in &self.before_default_cases {
 759                 output.push(SerializedCFGElement::SwitchCase);
 760                 case.serialize_cfg(output);
 761             }
 762             if let Some(default) = &self.default {
 763                 output.push(SerializedCFGElement::SwitchDefaultCase);
 764                 default.default_case.serialize_cfg(output);
 765                 for case in &default.after_default_cases {
 766                     output.push(SerializedCFGElement::SwitchCase);
 767                     case.serialize_cfg(output);
 768                 }
 769             }
 770             output.push(SerializedCFGElement::SwitchEnd);
 771             self.next.serialize_cfg(output);
 772         }
 773     }
 774
 775     impl SerializeCFG for SwitchFallthroughNode {
 776         fn serialize_cfg(&self, output: &mut Vec<SerializedCFGElement>) {
 777             output.push(SerializedCFGElement::SwitchFallthrough);
 778         }
 779     }
 780
 781     impl SerializeCFG for SwitchMergeNode {
 782         fn serialize_cfg(&self, output: &mut Vec<SerializedCFGElement>) {
 783             output.push(SerializedCFGElement::SwitchMerge);
 784         }
 785     }
 786
 787     impl SerializeCFG for ConditionNode {
 788         fn serialize_cfg(&self, output: &mut Vec<SerializedCFGElement>) {
 789             output.push(SerializedCFGElement::Condition);
 790             if let Some(true_node) = &self.true_node {
 791                 output.push(SerializedCFGElement::ConditionTrue);
 792                 true_node.serialize_cfg(output);
 793             }
 794             if let Some(false_node) = &self.false_node {
 795                 output.push(SerializedCFGElement::ConditionFalse);
 796                 false_node.serialize_cfg(output);
 797             }
 798             output.push(SerializedCFGElement::ConditionEnd);
 799             self.next.serialize_cfg(output)
 800         }
 801     }
 802
 803     impl SerializeCFG for ConditionMergeNode {
 804         fn serialize_cfg(&self, output: &mut Vec<SerializedCFGElement>) {
 805             output.push(SerializedCFGElement::ConditionMerge);
 806         }
 807     }
 808
 809     impl SerializeCFG for Node {
 810         fn serialize_cfg(&self, output: &mut Vec<SerializedCFGElement>) {
 811             match self {
 812                 Node::Simple(v) => v.serialize_cfg(output),
 813                 Node::Return(v) => v.serialize_cfg(output),
 814                 Node::Discard(v) => v.serialize_cfg(output),
 815                 Node::Switch(v) => v.serialize_cfg(output),
 816                 Node::SwitchFallthrough(v) => v.serialize_cfg(output),
 817                 Node::SwitchMerge(v) => v.serialize_cfg(output),
 818                 Node::Condition(v) => v.serialize_cfg(output),
 819                 Node::ConditionMerge(v) => v.serialize_cfg(output),
 820             }
 821         }
 822     }
 823
 824     fn test_cfg(instructions: &[Instruction], expected: &[SerializedCFGElement]) {
 825         println!("instructions:");
 826         for instruction in instructions {
 827             print!("{}", instruction);
 828         }
 829         println!();
 830         let cfg = create_cfg(&instructions);
 831         assert_eq!(&*cfg.serialize_cfg_into_vec(), expected);
 832     }
 833
 834     #[test]
 835     fn test_cfg_return() {
 836         let mut id_factory = IdFactory::new();
 837         let mut instructions = Vec::new();
 838
 839         let label1 = id_factory.next();
 840         instructions.push(Instruction::NoLine);
 841         instructions.push(Instruction::Label {
 842             id_result: IdResult(label1),
 843         });
 844         instructions.push(Instruction::Return);
 845
 846         test_cfg(&instructions, &[SerializedCFGElement::Return]);
 847     }
 848
 849     #[test]
 850     fn test_cfg_return_value() {
 851         let mut id_factory = IdFactory::new();
 852         let mut instructions = Vec::new();
 853
 854         let label1 = id_factory.next();
 855         instructions.push(Instruction::NoLine);
 856         instructions.push(Instruction::Label {
 857             id_result: IdResult(label1),
 858         });
 859         instructions.push(Instruction::ReturnValue {
 860             value: id_factory.next(),
 861         });
 862
 863         test_cfg(&instructions, &[SerializedCFGElement::Return]);
 864     }
 865
 866     #[test]
 867     fn test_cfg_simple_discard() {
 868         let mut id_factory = IdFactory::new();
 869         let mut instructions = Vec::new();
 870
 871         let label1 = id_factory.next();
 872         let label2 = id_factory.next();
 873
 874         instructions.push(Instruction::NoLine);
 875         instructions.push(Instruction::Label {
 876             id_result: IdResult(label1),
 877         });
 878         instructions.push(Instruction::Branch {
 879             target_label: label2,
 880         });
 881
 882         instructions.push(Instruction::Label {
 883             id_result: IdResult(label2),
 884         });
 885         instructions.push(Instruction::Kill);
 886
 887         test_cfg(
 888             &instructions,
 889             &[SerializedCFGElement::Simple, SerializedCFGElement::Discard],
 890         );
 891     }
 892
 893     #[test]
 894     fn test_cfg_conditional_none_none() {
 895         let mut id_factory = IdFactory::new();
 896         let mut instructions = Vec::new();
 897
 898         let label_start = id_factory.next();
 899         let label_endif = id_factory.next();
 900
 901         instructions.push(Instruction::NoLine);
 902         instructions.push(Instruction::Label {
 903             id_result: IdResult(label_start),
 904         });
 905         instructions.push(Instruction::SelectionMerge {
 906             merge_block: label_endif,
 907             selection_control: spirv_parser::SelectionControl::default(),
 908         });
 909         instructions.push(Instruction::BranchConditional {
 910             condition: id_factory.next(),
 911             true_label: label_endif,
 912             false_label: label_endif,
 913             branch_weights: vec![],
 914         });
 915
 916         instructions.push(Instruction::Label {
 917             id_result: IdResult(label_endif),
 918         });
 919         instructions.push(Instruction::Return);
 920
 921         test_cfg(
 922             &instructions,
 923             &[
 924                 SerializedCFGElement::Condition,
 925                 SerializedCFGElement::ConditionEnd,
 926                 SerializedCFGElement::Return,
 927             ],
 928         );
 929     }
 930
 931     #[test]
 932     fn test_cfg_conditional_merge_none() {
 933         let mut id_factory = IdFactory::new();
 934         let mut instructions = Vec::new();
 935
 936         let label_start = id_factory.next();
 937         let label_then = id_factory.next();
 938         let label_endif = id_factory.next();
 939
 940         instructions.push(Instruction::NoLine);
 941         instructions.push(Instruction::Label {
 942             id_result: IdResult(label_start),
 943         });
 944         instructions.push(Instruction::SelectionMerge {
 945             merge_block: label_endif,
 946             selection_control: spirv_parser::SelectionControl::default(),
 947         });
 948         instructions.push(Instruction::BranchConditional {
 949             condition: id_factory.next(),
 950             true_label: label_then,
 951             false_label: label_endif,
 952             branch_weights: vec![],
 953         });
 954
 955         instructions.push(Instruction::Label {
 956             id_result: IdResult(label_then),
 957         });
 958         instructions.push(Instruction::Branch {
 959             target_label: label_endif,
 960         });
 961
 962         instructions.push(Instruction::Label {
 963             id_result: IdResult(label_endif),
 964         });
 965         instructions.push(Instruction::Return);
 966
 967         test_cfg(
 968             &instructions,
 969             &[
 970                 SerializedCFGElement::Condition,
 971                 SerializedCFGElement::ConditionTrue,
 972                 SerializedCFGElement::ConditionMerge,
 973                 SerializedCFGElement::ConditionEnd,
 974                 SerializedCFGElement::Return,
 975             ],
 976         );
 977     }
 978
 979     #[test]
 980     fn test_cfg_conditional_return_merge() {
 981         let mut id_factory = IdFactory::new();
 982         let mut instructions = Vec::new();
 983
 984         let label_start = id_factory.next();
 985         let label_then = id_factory.next();
 986         let label_else = id_factory.next();
 987         let label_endif = id_factory.next();
 988
 989         instructions.push(Instruction::NoLine);
 990         instructions.push(Instruction::Label {
 991             id_result: IdResult(label_start),
 992         });
 993         instructions.push(Instruction::SelectionMerge {
 994             merge_block: label_endif,
 995             selection_control: spirv_parser::SelectionControl::default(),
 996         });
 997         instructions.push(Instruction::BranchConditional {
 998             condition: id_factory.next(),
 999             true_label: label_then,
1000             false_label: label_else,
1001             branch_weights: vec![],
1002         });
1003
1004         instructions.push(Instruction::Label {
1005             id_result: IdResult(label_then),
1006         });
1007         instructions.push(Instruction::Return);
1008
1009         instructions.push(Instruction::Label {
1010             id_result: IdResult(label_else),
1011         });
1012         instructions.push(Instruction::Branch {
1013             target_label: label_endif,
1014         });
1015
1016         instructions.push(Instruction::Label {
1017             id_result: IdResult(label_endif),
1018         });
1019         instructions.push(Instruction::Return);
1020
1021         test_cfg(
1022             &instructions,
1023             &[
1024                 SerializedCFGElement::Condition,
1025                 SerializedCFGElement::ConditionTrue,
1026                 SerializedCFGElement::Return,
1027                 SerializedCFGElement::ConditionFalse,
1028                 SerializedCFGElement::ConditionMerge,
1029                 SerializedCFGElement::ConditionEnd,
1030                 SerializedCFGElement::Return,
1031             ],
1032         );
1033     }
1034
1035     #[test]
1036     fn test_cfg_switch_default_break() {
1037         let mut id_factory = IdFactory::new();
1038         let mut instructions = Vec::new();
1039
1040         let label_start = id_factory.next();
1041         let label_default = id_factory.next();
1042         let label_merge = id_factory.next();
1043
1044         instructions.push(Instruction::NoLine);
1045         instructions.push(Instruction::Label {
1046             id_result: IdResult(label_start),
1047         });
1048         instructions.push(Instruction::SelectionMerge {
1049             merge_block: label_merge,
1050             selection_control: spirv_parser::SelectionControl::default(),
1051         });
1052         instructions.push(Instruction::Switch64 {
1053             selector: id_factory.next(),
1054             default: label_default,
1055             target: vec![],
1056         });
1057
1058         instructions.push(Instruction::Label {
1059             id_result: IdResult(label_default),
1060         });
1061         instructions.push(Instruction::Branch {
1062             target_label: label_merge,
1063         });
1064
1065         instructions.push(Instruction::Label {
1066             id_result: IdResult(label_merge),
1067         });
1068         instructions.push(Instruction::Return);
1069
1070         test_cfg(
1071             &instructions,
1072             &[
1073                 SerializedCFGElement::Switch,
1074                 SerializedCFGElement::SwitchDefaultCase,
1075                 SerializedCFGElement::SwitchMerge,
1076                 SerializedCFGElement::SwitchEnd,
1077                 SerializedCFGElement::Return,
1078             ],
1079         );
1080     }
1081
1082     #[test]
1083     fn test_cfg_switch_return_default_break() {
1084         let mut id_factory = IdFactory::new();
1085         let mut instructions = Vec::new();
1086
1087         let label_start = id_factory.next();
1088         let label_case1 = id_factory.next();
1089         let label_default = id_factory.next();
1090         let label_merge = id_factory.next();
1091
1092         instructions.push(Instruction::NoLine);
1093         instructions.push(Instruction::Label {
1094             id_result: IdResult(label_start),
1095         });
1096         instructions.push(Instruction::SelectionMerge {
1097             merge_block: label_merge,
1098             selection_control: spirv_parser::SelectionControl::default(),
1099         });
1100         instructions.push(Instruction::Switch64 {
1101             selector: id_factory.next(),
1102             default: label_default,
1103             target: vec![(0, label_case1)],
1104         });
1105
1106         instructions.push(Instruction::Label {
1107             id_result: IdResult(label_case1),
1108         });
1109         instructions.push(Instruction::Return);
1110
1111         instructions.push(Instruction::Label {
1112             id_result: IdResult(label_default),
1113         });
1114         instructions.push(Instruction::Branch {
1115             target_label: label_merge,
1116         });
1117
1118         instructions.push(Instruction::Label {
1119             id_result: IdResult(label_merge),
1120         });
1121         instructions.push(Instruction::Return);
1122
1123         test_cfg(
1124             &instructions,
1125             &[
1126                 SerializedCFGElement::Switch,
1127                 SerializedCFGElement::SwitchCase,
1128                 SerializedCFGElement::Return,
1129                 SerializedCFGElement::SwitchDefaultCase,
1130                 SerializedCFGElement::SwitchMerge,
1131                 SerializedCFGElement::SwitchEnd,
1132                 SerializedCFGElement::Return,
1133             ],
1134         );
1135     }
1136
1137     #[test]
1138     fn test_cfg_switch_fallthrough_default_break() {
1139         let mut id_factory = IdFactory::new();
1140         let mut instructions = Vec::new();
1141
1142         let label_start = id_factory.next();
1143         let label_case1 = id_factory.next();
1144         let label_default = id_factory.next();
1145         let label_merge = id_factory.next();
1146
1147         instructions.push(Instruction::NoLine);
1148         instructions.push(Instruction::Label {
1149             id_result: IdResult(label_start),
1150         });
1151         instructions.push(Instruction::SelectionMerge {
1152             merge_block: label_merge,
1153             selection_control: spirv_parser::SelectionControl::default(),
1154         });
1155         instructions.push(Instruction::Switch64 {
1156             selector: id_factory.next(),
1157             default: label_default,
1158             target: vec![(0, label_case1)],
1159         });
1160
1161         instructions.push(Instruction::Label {
1162             id_result: IdResult(label_case1),
1163         });
1164         instructions.push(Instruction::Branch {
1165             target_label: label_default,
1166         });
1167
1168         instructions.push(Instruction::Label {
1169             id_result: IdResult(label_default),
1170         });
1171         instructions.push(Instruction::Branch {
1172             target_label: label_merge,
1173         });
1174
1175         instructions.push(Instruction::Label {
1176             id_result: IdResult(label_merge),
1177         });
1178         instructions.push(Instruction::Return);
1179
1180         test_cfg(
1181             &instructions,
1182             &[
1183                 SerializedCFGElement::Switch,
1184                 SerializedCFGElement::SwitchCase,
1185                 SerializedCFGElement::SwitchFallthrough,
1186                 SerializedCFGElement::SwitchDefaultCase,
1187                 SerializedCFGElement::SwitchMerge,
1188                 SerializedCFGElement::SwitchEnd,
1189                 SerializedCFGElement::Return,
1190             ],
1191         );
1192     }
1193
1194     #[test]
1195     fn test_cfg_switch_fallthrough_default_fallthrough_break() {
1196         let mut id_factory = IdFactory::new();
1197         let mut instructions = Vec::new();
1198
1199         let label_start = id_factory.next();
1200         let label_case1 = id_factory.next();
1201         let label_default = id_factory.next();
1202         let label_case2 = id_factory.next();
1203         let label_merge = id_factory.next();
1204
1205         instructions.push(Instruction::NoLine);
1206         instructions.push(Instruction::Label {
1207             id_result: IdResult(label_start),
1208         });
1209         instructions.push(Instruction::SelectionMerge {
1210             merge_block: label_merge,
1211             selection_control: spirv_parser::SelectionControl::default(),
1212         });
1213         instructions.push(Instruction::Switch64 {
1214             selector: id_factory.next(),
1215             default: label_default,
1216             target: vec![(0, label_case1), (1, label_case1), (2, label_case2)],
1217         });
1218
1219         instructions.push(Instruction::Label {
1220             id_result: IdResult(label_case1),
1221         });
1222         instructions.push(Instruction::Branch {
1223             target_label: label_default,
1224         });
1225
1226         instructions.push(Instruction::Label {
1227             id_result: IdResult(label_default),
1228         });
1229         instructions.push(Instruction::Branch {
1230             target_label: label_case2,
1231         });
1232
1233         instructions.push(Instruction::Label {
1234             id_result: IdResult(label_case2),
1235         });
1236         instructions.push(Instruction::Branch {
1237             target_label: label_merge,
1238         });
1239
1240         instructions.push(Instruction::Label {
1241             id_result: IdResult(label_merge),
1242         });
1243         instructions.push(Instruction::Return);
1244
1245         test_cfg(
1246             &instructions,
1247             &[
1248                 SerializedCFGElement::Switch,
1249                 SerializedCFGElement::SwitchCase,
1250                 SerializedCFGElement::SwitchFallthrough,
1251                 SerializedCFGElement::SwitchDefaultCase,
1252                 SerializedCFGElement::SwitchFallthrough,
1253                 SerializedCFGElement::SwitchCase,
1254                 SerializedCFGElement::SwitchMerge,
1255                 SerializedCFGElement::SwitchEnd,
1256                 SerializedCFGElement::Return,
1257             ],
1258         );
1259     }
1260
1261     #[test]
1262     fn test_cfg_switch_break_default_fallthrough_break() {
1263         let mut id_factory = IdFactory::new();
1264         let mut instructions = Vec::new();
1265
1266         let label_start = id_factory.next();
1267         let label_case1 = id_factory.next();
1268         let label_default = id_factory.next();
1269         let label_case2 = id_factory.next();
1270         let label_merge = id_factory.next();
1271
1272         instructions.push(Instruction::NoLine);
1273         instructions.push(Instruction::Label {
1274             id_result: IdResult(label_start),
1275         });
1276         instructions.push(Instruction::SelectionMerge {
1277             merge_block: label_merge,
1278             selection_control: spirv_parser::SelectionControl::default(),
1279         });
1280         instructions.push(Instruction::Switch32 {
1281             selector: id_factory.next(),
1282             default: label_default,
1283             target: vec![(0, label_case1), (1, label_case1), (2, label_case2)],
1284         });
1285
1286         instructions.push(Instruction::Label {
1287             id_result: IdResult(label_case1),
1288         });
1289         instructions.push(Instruction::Branch {
1290             target_label: label_merge,
1291         });
1292
1293         instructions.push(Instruction::Label {
1294             id_result: IdResult(label_default),
1295         });
1296         instructions.push(Instruction::Branch {
1297             target_label: label_case2,
1298         });
1299
1300         instructions.push(Instruction::Label {
1301             id_result: IdResult(label_case2),
1302         });
1303         instructions.push(Instruction::Branch {
1304             target_label: label_merge,
1305         });
1306
1307         instructions.push(Instruction::Label {
1308             id_result: IdResult(label_merge),
1309         });
1310         instructions.push(Instruction::Return);
1311
1312         test_cfg(
1313             &instructions,
1314             &[
1315                 SerializedCFGElement::Switch,
1316                 SerializedCFGElement::SwitchCase,
1317                 SerializedCFGElement::SwitchMerge,
1318                 SerializedCFGElement::SwitchDefaultCase,
1319                 SerializedCFGElement::SwitchFallthrough,
1320                 SerializedCFGElement::SwitchCase,
1321                 SerializedCFGElement::SwitchMerge,
1322                 SerializedCFGElement::SwitchEnd,
1323                 SerializedCFGElement::Return,
1324             ],
1325         );
1326     }
1327 }