[前][次][番号順一覧][スレッド一覧]

ruby-changes:73232

From: Kevin <ko1@a...>
Date: Tue, 30 Aug 2022 01:03:28 +0900 (JST)
Subject: [ruby-changes:73232] 0823260546 (master): Implement iterators and double-linked list for IR SSA

https://git.ruby-lang.org/ruby.git/commit/?id=0823260546

From 0823260546f5fd749c3e1e9afadc29f4c6072ef1 Mon Sep 17 00:00:00 2001
From: Kevin Newton <kddnewton@g...>
Date: Tue, 2 Aug 2022 13:44:17 -0400
Subject: Implement iterators and double-linked list for IR SSA

---
 yjit/src/backend/ir_ssa.rs | 248 +++++++++++++++++++++++++++++++--------------
 1 file changed, 172 insertions(+), 76 deletions(-)

diff --git a/yjit/src/backend/ir_ssa.rs b/yjit/src/backend/ir_ssa.rs
index 49974b90b7..cd7f03c4fa 100644
--- a/yjit/src/backend/ir_ssa.rs
+++ b/yjit/src/backend/ir_ssa.rs
@@ -378,10 +378,6 @@ type PosMarkerFn = Box<dyn Fn(CodePtr)>; https://github.com/ruby/ruby/blob/trunk/yjit/src/backend/ir_ssa.rs#L378
 /// YJIT IR instruction
 pub struct Insn
 {
-    /// Previous and next instruction (doubly linked list)
-    pub(super) prev: Option<InsnIdx>,
-    pub(super) next: Option<InsnIdx>,
-
     /// Other instructions using this instruction's output
     pub(super) uses: Vec<(InsnIdx, OpndIdx)>,
 
@@ -405,6 +401,128 @@ pub struct Insn https://github.com/ruby/ruby/blob/trunk/yjit/src/backend/ir_ssa.rs#L401
     pub(super) pos_marker: Option<PosMarkerFn>,
 }
 
+impl Insn {
+    fn new(op: Op, out: Opnd) -> Self {
+        Self {
+            uses: Vec::new(),
+            op,
+            text: None,
+            opnds: Vec::default(),
+            out,
+            target: None,
+            pos_marker: None,
+        }
+    }
+}
+
+/// A container for an instruction within a doubly-linked list.
+struct InsnNode {
+    insn: Insn,
+    prev_idx: Option<InsnIdx>,
+    next_idx: Option<InsnIdx>
+}
+
+impl InsnNode {
+    fn new(insn: Insn, prev_idx: Option<InsnIdx>) -> Self {
+        Self { insn, prev_idx, next_idx: None }
+    }
+}
+
+/// A doubly-linked list containing instructions.
+pub(super) struct InsnList {
+    insns: Vec<InsnNode>,
+    first_idx: Option<InsnIdx>,
+    last_idx: Option<InsnIdx>
+}
+
+impl InsnList {
+    fn new() -> Self {
+        Self { insns: Vec::default(), first_idx: None, last_idx: None }
+    }
+
+    /// Returns the next instruction index that will be generated
+    fn next_idx(&self) -> InsnIdx {
+        self.insns.len() as InsnIdx
+    }
+
+    /// Return a mutable reference to the instruction for the given index
+    fn get_ref_mut(&mut self, idx: InsnIdx) -> &mut Insn {
+        &mut self.insns[idx as usize].insn
+    }
+
+    /// Push a new instruction onto the end of the list
+    fn push(&mut self, insn: Insn) -> InsnIdx {
+        let insn_idx = self.next_idx();
+
+        // Push the new node onto the list
+        self.insns.push(InsnNode::new(insn, self.last_idx));
+
+        // Update the first index if it's not already set
+        self.first_idx = self.first_idx.or(Some(insn_idx));
+
+        // Update the last node's next_idx field if necessary
+        if let Some(last_idx) = self.last_idx {
+            self.insns[last_idx as usize].next_idx = Some(insn_idx);
+        }
+
+        // Update the last index
+        self.last_idx = Some(insn_idx);
+
+        insn_idx
+    }
+
+    /// Remove an instruction from the list at a given index
+    fn remove(&mut self, insn_idx: InsnIdx) {
+        let prev_idx = self.insns[insn_idx as usize].prev_idx;
+        let next_idx = self.insns[insn_idx as usize].next_idx;
+
+        // Update the previous node's next_idx field if necessary
+        if let Some(prev_idx) = prev_idx {
+            self.insns[prev_idx as usize].next_idx = next_idx;
+        } else {
+            assert_eq!(self.first_idx, Some(insn_idx));
+            self.first_idx = next_idx;
+        }
+
+        // Update the next node's prev_idx field if necessary
+        if let Some(next_idx) = next_idx {
+            self.insns[next_idx as usize].prev_idx = prev_idx;
+        } else {
+            assert_eq!(self.last_idx, Some(insn_idx));
+            self.last_idx = prev_idx;
+        }
+    }
+}
+
+/// An iterator that will walk through the list of instructions in order
+/// according to the linked list.
+pub(super) struct InsnListIterator<'a> {
+    insn_list: &'a InsnList,
+    insn_idx: Option<InsnIdx>
+}
+
+impl<'a> Iterator for InsnListIterator<'a> {
+    type Item = &'a Insn;
+
+    /// Return an option containing the next instruction in the list.
+    fn next(&mut self) -> Option<Self::Item> {
+        self.insn_idx.map(|idx| {
+            let node = &self.insn_list.insns[idx as usize];
+            self.insn_idx = node.next_idx;
+            &node.insn
+        })
+    }
+}
+
+impl<'a> IntoIterator for &'a InsnList {
+    type Item = &'a Insn;
+    type IntoIter = InsnListIterator<'a>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        InsnListIterator { insn_list: self, insn_idx: self.first_idx }
+    }
+}
+
 /*
 impl fmt::Debug for Insn {
     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
@@ -442,18 +560,12 @@ impl fmt::Debug for Insn { https://github.com/ruby/ruby/blob/trunk/yjit/src/backend/ir_ssa.rs#L560
 /// optimized and lowered
 pub struct Assembler
 {
-    /// All instructions created for this assembler (out of order)
-    pub(super) insns: Vec<Insn>,
-
-    /// First and last instructions in the linked list
-    pub(super) first_insn: Option<InsnIdx>,
-    pub(super) last_insn: Option<InsnIdx>,
+    /// The list of instructions created by this assembler
+    pub(super) insn_list: InsnList,
 
     /// Names of labels
     pub(super) label_names: Vec<String>,
 
-
-
     /*
     /// FIXME: only compute the live ranges when doing register allocation?
     ///
@@ -471,19 +583,10 @@ pub struct Assembler https://github.com/ruby/ruby/blob/trunk/yjit/src/backend/ir_ssa.rs#L583
 
 impl Assembler
 {
-    pub fn new() -> Assembler {
-        Assembler {
-            insns: Vec::default(),
-            first_insn: None,
-            last_insn: None,
-            label_names: Vec::default(),
-        }
+    pub fn new() -> Self {
+        Self { insn_list: InsnList::new(), label_names: Vec::default() }
     }
 
-
-
-
-
     /// Append an instruction to the list
     pub(super) fn push_insn(
         &mut self,
@@ -494,9 +597,7 @@ impl Assembler https://github.com/ruby/ruby/blob/trunk/yjit/src/backend/ir_ssa.rs#L597
         pos_marker: Option<PosMarkerFn>
     ) -> Opnd
     {
-        // Id of this instruction
-        let insn_idx = self.insns.len() as InsnIdx;
-
+        let insn_idx = self.insn_list.next_idx();
         let mut out_num_bits: u8 = 0;
 
         for (opnd_idx, opnd) in opnds.iter().enumerate() {
@@ -516,7 +617,7 @@ impl Assembler https://github.com/ruby/ruby/blob/trunk/yjit/src/backend/ir_ssa.rs#L617
 
             // Track which instructions this insn is using as operands
             if let Opnd::InsnOut { idx, .. } = *opnd {
-                self.insns[idx as usize].uses.push((insn_idx, opnd_idx as OpndIdx));
+                self.insn_list.get_ref_mut(idx).uses.push((insn_idx, opnd_idx as OpndIdx));
             }
         }
 
@@ -527,9 +628,7 @@ impl Assembler https://github.com/ruby/ruby/blob/trunk/yjit/src/backend/ir_ssa.rs#L628
         // Operand for the output of this instruction
         let out_opnd = Opnd::InsnOut{ idx: insn_idx, num_bits: out_num_bits };
 
-        let insn = Insn {
-            prev: self.last_insn,
-            next: None,
+        self.insn_list.push(Insn {
             uses: Vec::default(),
             op,
             text,
@@ -537,15 +636,7 @@ impl Assembler https://github.com/ruby/ruby/blob/trunk/yjit/src/backend/ir_ssa.rs#L636
             out: out_opnd,
             target,
             pos_marker,
-        };
-
-        self.insns.push(insn);
-
-        if let Some(last_insn_idx) = self.last_insn {
-            self.insns[last_insn_idx as usize].next = Some(insn_idx);
-        }
-        self.last_insn = Some(insn_idx);
-        self.first_insn = self.first_insn.or(Some(insn_idx));
+        });
 
         // Return an operand for the output of this instruction
         out_opnd
@@ -555,21 +646,21 @@ impl Assembler https://github.com/ruby/ruby/blob/trunk/yjit/src/backend/ir_ssa.rs#L646
     pub(super) fn replace_uses(&mut self, insn_idx: InsnIdx, replace_with: Opnd)
     {
         // We're going to clear the vector of uses
-        let uses = std::mem::take(&mut self.insns[insn_idx as usize].uses);
+        let uses = std::mem::take(&mut self.insn_list.get_ref_mut(insn_idx).uses);
 
         // For each use of this instruction
         for (use_idx, opnd_idx) in uses {
 
             // TODO: assert that this is indeed a use of this insn (sanity check)
 
-            let use_insn = &mut self.insns[use_idx as usize];
+            let use_insn = self.insn_list.get_ref_mut(use_idx);
             use_insn.opnds[opnd_idx as usize] = replace_with;
 
             // If replace_with is an insn, update its uses
             if let Opnd::InsnOut { idx, .. } = replace_with {
-                let repl_insn = &mut self.insns[idx as usize];
-                assert!(repl_insn.prev.is_some() || repl_insn.next.is_some());
-                repl_insn.uses.push((use_idx, opnd_idx));
+                let repl_insn = &mut self.insn_list.insns[idx as usize];
+                assert!(repl_insn.prev_idx.is_some() || repl_insn.next_idx.is_some());
+                repl_insn.insn.uses.push((use_idx, opnd_idx));
             }
         }
     }
@@ -577,33 +668,9 @@ impl Assembler https://github.com/ruby/ruby/blob/trunk/yjit/src/backend/ir_ssa.rs#L668
     /// Remove a specific insn from the assembler
     pub(super) fn remove_insn(&mut self, insn_idx: InsnIdx)
     {
-        let prev = self.insns[insn_idx as usize].prev;
-        let next = self.insns[insn_idx as usize].next;
-
-        match prev {
-            Some(prev_idx) => {
-                let prev_insn = &mut self.insns[prev_idx as usize];
-                prev_insn.next = next;
-            }
-            None => {
-                assert!(self.first_insn == Some(insn_idx));
-                self.first_insn = next;
-            }
-        };
-
-        match next {
-            Some(next_idx) => {
-  (... truncated)

--
ML: ruby-changes@q...
Info: http://www.atdot.net/~ko1/quickml/

[前][次][番号順一覧][スレッド一覧]