Bug: RecursionError while parsing AIG file

[pganguli]

When the following example code is run with the attached 6s128.aig circuit from the HWMCC'17 dataset,

https://github.com/Ironprop-Stone/python-deepgate/blob/cc91c1f7f9844aabf5d1a4f80b0ca0c5579a97ee/examples/feature_extract.py#L1-L23

the following error is encountered:

deepgate2 $ python feature_extract.py
[INFO] Create and load pretrained DeepGate
[INFO] Parse AIG:  ./6s128.aig
Traceback (most recent call last):
  File "/python-deepgate/examples/feature_extract.py", line 16, in <module>
    graph = parser.read_aiger(aig_path) # Parse AIG into Graph
            ^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/python-deepgate/test/lib64/python3.11/site-packages/deepgate/parser.py", line 121, in read_aiger
    x_data, edge_index = aig_to_xdata(aig_path)
                         ^^^^^^^^^^^^^^^^^^^^^^
  File "/python-deepgate/test/lib64/python3.11/site-packages/deepgate/utils/aiger_utils.py", line 288, in aig_to_xdata
    f = str(aiger.BoolExpr(aig))
        ^^^^^^^^^^^^^^^^^^^^^^^^
  File "<attrs generated repr aiger.expr.BoolExpr>", line 13, in __repr__
  File "/python-deepgate/test/lib64/python3.11/site-packages/aiger/aig.py", line 112, in __repr__
    return writer.dump(self)
           ^^^^^^^^^^^^^^^^^
  File "/python-deepgate/test/lib64/python3.11/site-packages/aiger/writer.py", line 89, in dump
    omap, lmap = circ(inputs=inputs, latches=latches, lift=lift)
                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/python-deepgate/test/lib64/python3.11/site-packages/aiger/aig.py", line 192, in __call__
    boundary = set(self.node_map.values()) | set(latch_map.values())
               ^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "<attrs generated hash aiger.aig.AndGate>", line 3, in __hash__
  File "<attrs generated hash aiger.aig.AndGate>", line 3, in __hash__
  File "<attrs generated hash aiger.aig.AndGate>", line 3, in __hash__
  [Previous line repeated 481 more times]
  File "<attrs generated hash aiger.aig.Inverter>", line 2, in __hash__
  File "<attrs generated hash aiger.aig.AndGate>", line 3, in __hash__
  File "<attrs generated hash aiger.aig.AndGate>", line 3, in __hash__
  File "<attrs generated hash aiger.aig.AndGate>", line 3, in __hash__
  [Previous line repeated 1 more time]
  File "<attrs generated hash aiger.aig.Inverter>", line 2, in __hash__
  File "<attrs generated hash aiger.aig.AndGate>", line 3, in __hash__
  File "<attrs generated hash aiger.aig.Inverter>", line 2, in __hash__
  File "<attrs generated hash aiger.aig.AndGate>", line 3, in __hash__
  File "<attrs generated hash aiger.aig.Inverter>", line 2, in __hash__
  File "<attrs generated hash aiger.aig.Input>", line 2, in __hash__
RecursionError: maximum recursion depth exceeded while calling a Python object

The following is the result of abc:print_stats on the same circuit; note that the circuit only has 1 output, and 0 latches:

6s128                         : i/o =  512/    1  lat =    0  and = 314879  lev =14405

6s128.aig.zip

[zshi0616]

Hi Pganguli,
The parser encouters error because aig_to_xdata function tries to parse AIG with very large logic level, but exceeds the recursion depth limitation.
To address the error, please increase the recursion limitation: https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-and-how-to-increase-it
In my laptop, I change it to 1000000 and parse 6s128.aig successfully.

Thanks,
Stone

[pganguli]

Hi,

Thank you for your suggestion. Unfortunately, I have already tried that:

Setting recursion limit to 2**31 or higher:

test $ python feature_extract.py
[INFO] MAXRECUR=2147483648
Traceback (most recent call last):
  File "/python-deepgate/examples/feature_extract.py", line 10, in <module>
    sys.setrecursionlimit(MAXRECUR)
OverflowError: Python int too large to convert to C int

Setting recursion limit to 2**31-1 (max that CPython seems to support on my 64-bit system):

test $ python feature_extract.py
[INFO] MAXRECUR=2147483647
[INFO] Create and load pretrained DeepGate
[INFO] Parse AIG:  ./6s128.aig
[1]    499712 segmentation fault (core dumped)  python feature_extract.py

Trying to attach a debugger to see the exact instruction where the segfault occurs:

test $ gdb --args python feature_extract.py
GNU gdb (GDB) Fedora Linux 13.2-7.fc38
Copyright (C) 2023 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
Type "show copying" and "show warranty" for details.
This GDB was configured as "x86_64-redhat-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<https://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
    <http://www.gnu.org/software/gdb/documentation/>.

For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from python...
Reading symbols from /home/pgan/.cache/debuginfod_client/68dbf1c2fdfa0701964120231a7af395fae67499/debuginfo...
(gdb) run
Starting program: /python-deepgate/test/bin/python feature_extract.py
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib64/libthread_db.so.1".
[New Thread 0x7fff3e7ff6c0 (LWP 500177)]
[New Thread 0x7fff3bffe6c0 (LWP 500178)]
[New Thread 0x7fff3b7fd6c0 (LWP 500179)]
[New Thread 0x7fff38ffc6c0 (LWP 500180)]
[New Thread 0x7fff347fb6c0 (LWP 500181)]
[New Thread 0x7fff33ffa6c0 (LWP 500182)]
[New Thread 0x7fff317f96c0 (LWP 500183)]
[New Thread 0x7fff26dff6c0 (LWP 500184)]
[New Thread 0x7fff265fe6c0 (LWP 500185)]
[New Thread 0x7fff23dfd6c0 (LWP 500186)]
[New Thread 0x7fff1f5fc6c0 (LWP 500187)]
[New Thread 0x7fff1cdfb6c0 (LWP 500188)]
[New Thread 0x7fff1c5fa6c0 (LWP 500189)]
[New Thread 0x7fff17df96c0 (LWP 500190)]
[INFO] MAXRECUR=2147483647
[INFO] Create and load pretrained DeepGate
[New Thread 0x7fff140496c0 (LWP 500191)]
[New Thread 0x7fff138486c0 (LWP 500192)]
[New Thread 0x7fff130476c0 (LWP 500193)]
[INFO] Parse AIG:  ./6s128.aig

Thread 1 "python" received signal SIGSEGV, Segmentation fault.
0x00007ffff7ba32b7 in _Py_dict_lookup (mp=mp@entry=0x7fff29fa5580, key=<optimized out>, hash=<optimized out>, value_addr=value_addr@entry=0x7fffff7ff090)
    at /usr/src/debug/python3.11-3.11.6-1.fc38.x86_64/Objects/dictobject.c:1053
1053                ix = unicodekeys_lookup_unicode(dk, key, hash);

From what I understand, this is a routine internal to the Python interpreter that is responsible for looking up dictionary (hash) values using a Unicode string as a key; possibly the size of this dictionary is too large for what can be represented as a Python object.

Memory usage on my system for this particular process (or its children threads) never rose beyond around 3-4 GiB. I do not have any GPU based HW acceleration.

[pganguli]

Code used for reference:

import sys

MAXRECUR = 1000000
print(f"[INFO] {MAXRECUR=}")
sys.setrecursionlimit(MAXRECUR)


from __future__ import absolute_import
from __future__ import division
from __future__ import print_function

import deepgate

if __name__ == "__main__":
    print("[INFO] Create and load pretrained DeepGate")
    model = deepgate.Model()  # Create DeepGate
    model.load_pretrained()  # Load pretrained model

    aig_path = "./6s128.aig"
    print("[INFO] Parse AIG: ", aig_path)
    parser = deepgate.AigParser()  # Create AigParser
    graph = parser.read_aiger(aig_path)  # Parse AIG into Graph
    print("[INFO] Get embeddings ...")
    hs, hf = model(graph)  # Model inference

    # hs: structural embeddings, hf: functional embeddings
    # hs/hf: [N, D]. N: number of gates, D: embedding dimension (default: 128)
    print(hs.shape, hf.shape)

[zshi0616]

Hi,
The parser in DeepGate2 require aiger package to read .aig. Seems like it cannot support very large aig file due to the recursion limitation.
If your server doesn't have enough memory, maybe you can try to reformulate the input aig. I have tried to apply "balance; rewrite -lz; balance; rewrite -lz" to transform the case 6s128.aig, the depth will be reduced. Then, deepgate2 can easily parse it. As in formal verification application, we can simplify the instance before solving, it may be a better solution.

Thanks,
Stone