The ControlFlowGraphVisitor currently uses a std::vector<std::string> to store the variable that are accessed (read or written). This, however, is not enough as there might exists multiple variables with the same identifier but declared in different scopes. See #13 that addresses this issue.

In addition to the missing scope support, it would be useful to allow tracking of matrix accesses. As a current and very rudimentary workaround, a string like "Variable(M)[LiteralInt(21)][LiteralInt(3)]" is constructed and used. As we cannot generally assume that indices are always known, it would probably better to store the whole MatrixElementRef element.

The base Visitor implements the scope logic that defines when a new scope is opened or an existing one is closed. The scopes build a hierarchy, i.e., scopes are linked with each other while a scope refers to an outer scope and one or multiple nested scopes. This hierarchy is determined while visiting the statements, hence it is important that the classes call the base Visitor's visit method.

The initial design did not take into account that moving nodes may require updating the scope hierarchy. This is important as searching for a variable's value may otherwise fail if a variable declared in an outer scope cannot be found.

Also, sometimes nodes are visited out of order, for example, during partial loop unrolling in the CompileTimeExpressionSimplifier. This was not considered either. As an example, look into the doPartialLoopUnrolling method that moves the For loop's initializer into a Block but visits the initializer directly by skipping the block statement. This causes a wrongly assigned variable scope (but does not lead to break partial unrolling).

If-statements with conditions depending on runtime-known and public variables should not be rewritten because the runtime system can determine which branch must be executed. This is more efficient because rewriting would involve executing both branches (and involve additional condition checks before executing each statement). See TODO note in CompileTimeExpressionSimplifier class.

This extension depends on the implementation of scope-handling in the SecretTaintingVisitor (see #3), to determine if a variable—given as pair of variable identifier and scope where it is declared in—is public.

The method AbstractNode::supportsCircuitMode is obsolete and its naming is confusing. Its initial intention was to provide a way to distinguish between AST nodes that use the AbstractNode's children/parent vector and those that do not. As now almost all AST nodes use the children vector to store its attributes, the method is not required anymore.

• Adapt CallExternal: Store attributes in AbstractNode's children vector
• Check if any class still does not use the children/parent vectors to store its attributes
  • Check if any class does not overwrite the inherited method AbstractNode::supportsCircuitMode
  • Check if the overwrite of AbstractNode::supportsCircuitMode in any class returns False
  • Check and remove usages of AbstractNode::supportsCircuitMode
• Remove the method AbstractNode::supportsCircuitMode

As described in this blogpost, it's possible to publish the code docs generated by Doxygen using Github pages. I prepared the necessary files (see a39ce2d). All that is now still required is to enable Github pages for this project. This requires repository owner permissions.

A future task could be to use Github Actions to automatically build the Doxygen docs and deploy them to Github pages.

While I running basic tests, I discovered that LLVM encounters an invalid pointer error.
Could you please give a some advice on how to fix this?

Thanks.

> ./build/bin/heco < test/example.mlir
realloc(): invalid pointer
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.      Program arguments: ./build/bin/heco
1.      MLIR Parser: custom op parser 'builtin.module'
2.      MLIR Parser: custom op parser 'func.func'
3.      MLIR Parser: custom op parser 'affine.for'
4.      MLIR Parser: custom op parser 'fhe.sub'
 #0 0x000055754d51a6ed llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) /home/x/fun/HECO/dependencies/llvm-project/llvm/lib/Support/Unix/Signals.inc:602:11
 #1 0x000055754d51ac8b PrintStackTraceSignalHandler(void*) /home/x/fun/HECO/dependencies/llvm-project/llvm/lib/Support/Unix/Signals.inc:675:1
 #2 0x000055754d518b53 llvm::sys::RunSignalHandlers() /home/x/fun/HECO/dependencies/llvm-project/llvm/lib/Support/Signals.cpp:104:5
 #3 0x000055754d51b521 SignalHandler(int) /home/x/fun/HECO/dependencies/llvm-project/llvm/lib/Support/Unix/Signals.inc:413:1
 #4 0x00007fae16fc5710 (/usr/lib/libc.so.6+0x3e710)
 #5 0x00007fae1701583c (/usr/lib/libc.so.6+0x8e83c)
 #6 0x00007fae16fc5668 gsignal (/usr/lib/libc.so.6+0x3e668)
 #7 0x00007fae16fad4b8 abort (/usr/lib/libc.so.6+0x264b8)
 #8 0x00007fae16fae390 (/usr/lib/libc.so.6+0x27390)
 #9 0x00007fae1701f7b7 (/usr/lib/libc.so.6+0x987b7)
#10 0x00007fae1702491c __libc_realloc (/usr/lib/libc.so.6+0x9d91c)
#11 0x000055754d46478d llvm::safe_realloc(void*, unsigned long) /home/x/fun/HECO/dependencies/llvm-project/llvm/include/llvm/Support/MemAlloc.h:53:9
#12 0x000055754d465012 llvm::SmallVectorBase<unsigned int>::grow_pod(void*, unsigned long, unsigned long) /home/x/fun/HECO/dependencies/llvm-project/llvm/lib/Support/SmallVector.cpp:151:13
#13 0x0000557545abb295 llvm::SmallVectorTemplateCommon<mlir::Type, void>::grow_pod(unsigned long, unsigned long) /home/x/fun/HECO/dependencies/llvm-project/llvm/include/llvm/ADT/SmallVector.h:142:3
#14 0x0000557545abb252 llvm::SmallVectorTemplateBase<mlir::Type, true>::grow(unsigned long) /home/x/fun/HECO/dependencies/llvm-project/llvm/include/llvm/ADT/SmallVector.h:529:71
#15 0x0000557545ad264c mlir::Type const* llvm::SmallVectorTemplateCommon<mlir::Type, void>::reserveForParamAndGetAddressImpl<llvm::SmallVectorTemplateBase<mlir::Type, true>>(llvm::SmallVectorTemplateBase<mlir::Type, true>*, mlir::Type const&, unsigned long) /home/x/fun/HECO/dependencies/llvm-project/llvm/include/llvm/ADT/SmallVector.h:247:12
#16 0x0000557545ad25d5 llvm::SmallVectorTemplateBase<mlir::Type, true>::reserveForParamAndGetAddress(mlir::Type&, unsigned long) /home/x/fun/HECO/dependencies/llvm-project/llvm/include/llvm/ADT/SmallVector.h:540:5
#17 0x0000557545aa32d3 llvm::SmallVectorTemplateBase<mlir::Type, true>::push_back(mlir::Type) /home/x/fun/HECO/dependencies/llvm-project/llvm/include/llvm/ADT/SmallVector.h:566:23
#18 0x0000557545ace30f mlir::Type& llvm::SmallVectorTemplateBase<mlir::Type, true>::growAndEmplaceBack<>() /home/x/fun/HECO/dependencies/llvm-project/llvm/include/llvm/ADT/SmallVector.h:560:5
#19 0x0000557545ace26f mlir::Type& llvm::SmallVectorImpl<mlir::Type>::emplace_back<>() /home/x/fun/HECO/dependencies/llvm-project/llvm/include/llvm/ADT/SmallVector.h:943:7
#20 0x0000557545ace210 mlir::AsmParser::parseTypeList(llvm::SmallVectorImpl<mlir::Type>&)::'lambda'()::operator()() const /home/x/fun/HECO/dependencies/llvm-project/mlir/include/mlir/IR/OpImplementation.h:1183:41
#21 0x0000557545ace1d5 mlir::ParseResult llvm::function_ref<mlir::ParseResult ()>::callback_fn<mlir::AsmParser::parseTypeList(llvm::SmallVectorImpl<mlir::Type>&)::'lambda'()>(long) /home/x/fun/HECO/dependencies/llvm-project/llvm/include/llvm/ADT/STLFunctionalExtras.h:45:12
#22 0x000055754a6ebea9 llvm::function_ref<mlir::ParseResult ()>::operator()() const /home/x/fun/HECO/dependencies/llvm-project/llvm/include/llvm/ADT/STLFunctionalExtras.h:68:12
#23 0x000055754a6d56e8 mlir::detail::Parser::parseCommaSeparatedList(mlir::AsmParser::Delimiter, llvm::function_ref<mlir::ParseResult ()>, llvm::StringRef) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:105:7
#24 0x000055754a6f140c mlir::detail::AsmParserImpl<mlir::OpAsmParser>::parseCommaSeparatedList(mlir::AsmParser::Delimiter, llvm::function_ref<mlir::ParseResult ()>, llvm::StringRef) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/AsmParserImpl.h:315:19
#25 0x0000557549e27d81 heco::fhe::AddOp::parse(mlir::OpAsmParser&, mlir::OperationState&) (./build/bin/heco+0x4741d81)
#26 0x0000557545adbd8d mlir::ParseResult llvm::detail::UniqueFunctionBase<mlir::ParseResult, mlir::OpAsmParser&, mlir::OperationState&>::CallImpl<mlir::ParseResult (*)(mlir::OpAsmParser&, mlir::OperationState&)>(void*, mlir::OpAsmParser&, mlir::OperationState&) /home/x/fun/HECO/dependencies/llvm-project/llvm/include/llvm/ADT/FunctionExtras.h:220:12
#27 0x000055754a098c2f llvm::unique_function<mlir::ParseResult (mlir::OpAsmParser&, mlir::OperationState&)>::operator()(mlir::OpAsmParser&, mlir::OperationState&) /home/x/fun/HECO/dependencies/llvm-project/llvm/include/llvm/ADT/FunctionExtras.h:382:12
#28 0x000055754a6ef9f5 mlir::ParseResult llvm::function_ref<mlir::ParseResult (mlir::OpAsmParser&, mlir::OperationState&)>::callback_fn<llvm::unique_function<mlir::ParseResult (mlir::OpAsmParser&, mlir::OperationState&)>>(long, mlir::OpAsmParser&, mlir::OperationState&) /home/x/fun/HECO/dependencies/llvm-project/llvm/include/llvm/ADT/STLFunctionalExtras.h:45:12
#29 0x000055754a0e3cc9 llvm::function_ref<mlir::ParseResult (mlir::OpAsmParser&, mlir::OperationState&)>::operator()(mlir::OpAsmParser&, mlir::OperationState&) const /home/x/fun/HECO/dependencies/llvm-project/llvm/include/llvm/ADT/STLFunctionalExtras.h:68:12
#30 0x000055754a6ddc97 (anonymous namespace)::CustomOpAsmParser::parseOperation(mlir::OperationState&) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:1491:9
#31 0x000055754a6dc245 (anonymous namespace)::OperationParser::parseCustomOperation(llvm::ArrayRef<std::tuple<llvm::StringRef, unsigned int, llvm::SMLoc>>) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:1987:19
#32 0x000055754a6d81b0 (anonymous namespace)::OperationParser::parseOperation() /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:1146:8
#33 0x000055754a6e71a6 (anonymous namespace)::OperationParser::parseBlockBody(mlir::Block*) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:2263:9
#34 0x000055754a6e5f91 (anonymous namespace)::OperationParser::parseBlock(mlir::Block*&) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:2193:12
#35 0x000055754a6e5aab (anonymous namespace)::OperationParser::parseRegionBody(mlir::Region&, llvm::SMLoc, llvm::ArrayRef<mlir::OpAsmParser::Argument>, bool) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:2151:7
#36 0x000055754a6e2723 (anonymous namespace)::OperationParser::parseRegion(mlir::Region&, llvm::ArrayRef<mlir::OpAsmParser::Argument>, bool) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:2088:7
#37 0x000055754a6dfd52 (anonymous namespace)::CustomOpAsmParser::parseRegion(mlir::Region&, llvm::ArrayRef<mlir::OpAsmParser::Argument>, bool) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:1755:16
#38 0x0000557545a4b657 mlir::affine::AffineForOp::parse(mlir::OpAsmParser&, mlir::OperationState&) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/Dialect/Affine/IR/AffineOps.cpp:2142:14
#39 0x0000557545adbd8d mlir::ParseResult llvm::detail::UniqueFunctionBase<mlir::ParseResult, mlir::OpAsmParser&, mlir::OperationState&>::CallImpl<mlir::ParseResult (*)(mlir::OpAsmParser&, mlir::OperationState&)>(void*, mlir::OpAsmParser&, mlir::OperationState&) /home/x/fun/HECO/dependencies/llvm-project/llvm/include/llvm/ADT/FunctionExtras.h:220:12
#40 0x000055754a098c2f llvm::unique_function<mlir::ParseResult (mlir::OpAsmParser&, mlir::OperationState&)>::operator()(mlir::OpAsmParser&, mlir::OperationState&) /home/x/fun/HECO/dependencies/llvm-project/llvm/include/llvm/ADT/FunctionExtras.h:382:12
#41 0x000055754a6ef9f5 mlir::ParseResult llvm::function_ref<mlir::ParseResult (mlir::OpAsmParser&, mlir::OperationState&)>::callback_fn<llvm::unique_function<mlir::ParseResult (mlir::OpAsmParser&, mlir::OperationState&)>>(long, mlir::OpAsmParser&, mlir::OperationState&) /home/x/fun/HECO/dependencies/llvm-project/llvm/include/llvm/ADT/STLFunctionalExtras.h:45:12
#42 0x000055754a0e3cc9 llvm::function_ref<mlir::ParseResult (mlir::OpAsmParser&, mlir::OperationState&)>::operator()(mlir::OpAsmParser&, mlir::OperationState&) const /home/x/fun/HECO/dependencies/llvm-project/llvm/include/llvm/ADT/STLFunctionalExtras.h:68:12
#43 0x000055754a6ddc97 (anonymous namespace)::CustomOpAsmParser::parseOperation(mlir::OperationState&) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:1491:9
#44 0x000055754a6dc245 (anonymous namespace)::OperationParser::parseCustomOperation(llvm::ArrayRef<std::tuple<llvm::StringRef, unsigned int, llvm::SMLoc>>) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:1987:19
#45 0x000055754a6d81b0 (anonymous namespace)::OperationParser::parseOperation() /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:1146:8
#46 0x000055754a6e71a6 (anonymous namespace)::OperationParser::parseBlockBody(mlir::Block*) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:2263:9
#47 0x000055754a6e5f91 (anonymous namespace)::OperationParser::parseBlock(mlir::Block*&) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:2193:12
#48 0x000055754a6e5aab (anonymous namespace)::OperationParser::parseRegionBody(mlir::Region&, llvm::SMLoc, llvm::ArrayRef<mlir::OpAsmParser::Argument>, bool) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:2151:7
#49 0x000055754a6e2723 (anonymous namespace)::OperationParser::parseRegion(mlir::Region&, llvm::ArrayRef<mlir::OpAsmParser::Argument>, bool) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:2088:7
#50 0x000055754a6dfd52 (anonymous namespace)::CustomOpAsmParser::parseRegion(mlir::Region&, llvm::ArrayRef<mlir::OpAsmParser::Argument>, bool) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:1755:16
#51 0x000055754a6dfe6b (anonymous namespace)::CustomOpAsmParser::parseOptionalRegion(mlir::Region&, llvm::ArrayRef<mlir::OpAsmParser::Argument>, bool) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:1766:12
#52 0x000055754a09a311 mlir::function_interface_impl::parseFunctionOp(mlir::OpAsmParser&, mlir::OperationState&, bool, mlir::StringAttr, llvm::function_ref<mlir::Type (mlir::Builder&, llvm::ArrayRef<mlir::Type>, llvm::ArrayRef<mlir::Type>, mlir::function_interface_impl::VariadicFlag, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char>>&)>, mlir::StringAttr, mlir::StringAttr) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/IR/FunctionImplementation.cpp:232:14
#53 0x00005575463db60c mlir::func::FuncOp::parse(mlir::OpAsmParser&, mlir::OperationState&) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/Dialect/Func/IR/FuncOps.cpp:199:10
#54 0x0000557545adbd8d mlir::ParseResult llvm::detail::UniqueFunctionBase<mlir::ParseResult, mlir::OpAsmParser&, mlir::OperationState&>::CallImpl<mlir::ParseResult (*)(mlir::OpAsmParser&, mlir::OperationState&)>(void*, mlir::OpAsmParser&, mlir::OperationState&) /home/x/fun/HECO/dependencies/llvm-project/llvm/include/llvm/ADT/FunctionExtras.h:220:12
#55 0x000055754a098c2f llvm::unique_function<mlir::ParseResult (mlir::OpAsmParser&, mlir::OperationState&)>::operator()(mlir::OpAsmParser&, mlir::OperationState&) /home/x/fun/HECO/dependencies/llvm-project/llvm/include/llvm/ADT/FunctionExtras.h:382:12
#56 0x000055754a6ef9f5 mlir::ParseResult llvm::function_ref<mlir::ParseResult (mlir::OpAsmParser&, mlir::OperationState&)>::callback_fn<llvm::unique_function<mlir::ParseResult (mlir::OpAsmParser&, mlir::OperationState&)>>(long, mlir::OpAsmParser&, mlir::OperationState&) /home/x/fun/HECO/dependencies/llvm-project/llvm/include/llvm/ADT/STLFunctionalExtras.h:45:12
#57 0x000055754a0e3cc9 llvm::function_ref<mlir::ParseResult (mlir::OpAsmParser&, mlir::OperationState&)>::operator()(mlir::OpAsmParser&, mlir::OperationState&) const /home/x/fun/HECO/dependencies/llvm-project/llvm/include/llvm/ADT/STLFunctionalExtras.h:68:12
#58 0x000055754a6ddc97 (anonymous namespace)::CustomOpAsmParser::parseOperation(mlir::OperationState&) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:1491:9
#59 0x000055754a6dc245 (anonymous namespace)::OperationParser::parseCustomOperation(llvm::ArrayRef<std::tuple<llvm::StringRef, unsigned int, llvm::SMLoc>>) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:1987:19
#60 0x000055754a6d81b0 (anonymous namespace)::OperationParser::parseOperation() /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:1146:8
#61 0x000055754a6e71a6 (anonymous namespace)::OperationParser::parseBlockBody(mlir::Block*) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:2263:9
#62 0x000055754a6e5f91 (anonymous namespace)::OperationParser::parseBlock(mlir::Block*&) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:2193:12
#63 0x000055754a6e5aab (anonymous namespace)::OperationParser::parseRegionBody(mlir::Region&, llvm::SMLoc, llvm::ArrayRef<mlir::OpAsmParser::Argument>, bool) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:2151:7
#64 0x000055754a6e2723 (anonymous namespace)::OperationParser::parseRegion(mlir::Region&, llvm::ArrayRef<mlir::OpAsmParser::Argument>, bool) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:2088:7
#65 0x000055754a6dfd52 (anonymous namespace)::CustomOpAsmParser::parseRegion(mlir::Region&, llvm::ArrayRef<mlir::OpAsmParser::Argument>, bool) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:1755:16
#66 0x0000557549ff4bea mlir::ModuleOp::parse(mlir::OpAsmParser&, mlir::OperationState&) /home/x/fun/HECO/dependencies/llvm-project/build/tools/mlir/include/mlir/IR/BuiltinOps.cpp.inc:383:14
#67 0x0000557545adbd8d mlir::ParseResult llvm::detail::UniqueFunctionBase<mlir::ParseResult, mlir::OpAsmParser&, mlir::OperationState&>::CallImpl<mlir::ParseResult (*)(mlir::OpAsmParser&, mlir::OperationState&)>(void*, mlir::OpAsmParser&, mlir::OperationState&) /home/x/fun/HECO/dependencies/llvm-project/llvm/include/llvm/ADT/FunctionExtras.h:220:12
#68 0x000055754a098c2f llvm::unique_function<mlir::ParseResult (mlir::OpAsmParser&, mlir::OperationState&)>::operator()(mlir::OpAsmParser&, mlir::OperationState&) /home/x/fun/HECO/dependencies/llvm-project/llvm/include/llvm/ADT/FunctionExtras.h:382:12
#69 0x000055754a6ef9f5 mlir::ParseResult llvm::function_ref<mlir::ParseResult (mlir::OpAsmParser&, mlir::OperationState&)>::callback_fn<llvm::unique_function<mlir::ParseResult (mlir::OpAsmParser&, mlir::OperationState&)>>(long, mlir::OpAsmParser&, mlir::OperationState&) /home/x/fun/HECO/dependencies/llvm-project/llvm/include/llvm/ADT/STLFunctionalExtras.h:45:12
#70 0x000055754a0e3cc9 llvm::function_ref<mlir::ParseResult (mlir::OpAsmParser&, mlir::OperationState&)>::operator()(mlir::OpAsmParser&, mlir::OperationState&) const /home/x/fun/HECO/dependencies/llvm-project/llvm/include/llvm/ADT/STLFunctionalExtras.h:68:12
#71 0x000055754a6ddc97 (anonymous namespace)::CustomOpAsmParser::parseOperation(mlir::OperationState&) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:1491:9
#72 0x000055754a6dc245 (anonymous namespace)::OperationParser::parseCustomOperation(llvm::ArrayRef<std::tuple<llvm::StringRef, unsigned int, llvm::SMLoc>>) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:1987:19
#73 0x000055754a6d81b0 (anonymous namespace)::OperationParser::parseOperation() /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:1146:8
#74 0x000055754a6d7b18 (anonymous namespace)::TopLevelOperationParser::parse(mlir::Block*, mlir::Location) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:2684:20
#75 0x000055754a6d7957 mlir::parseAsmSourceFile(llvm::SourceMgr const&, mlir::Block*, mlir::ParserConfig const&, mlir::AsmParserState*, mlir::AsmParserCodeCompleteContext*) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/AsmParser/Parser.cpp:2744:41
#76 0x000055754a12fe44 mlir::parseSourceFile(std::shared_ptr<llvm::SourceMgr> const&, mlir::Block*, mlir::ParserConfig const&, mlir::LocationAttr*) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/Parser/Parser.cpp:46:10
#77 0x0000557549e1a96c mlir::OwningOpRef<mlir::ModuleOp> mlir::detail::parseSourceFile<mlir::ModuleOp, std::shared_ptr<llvm::SourceMgr> const&>(mlir::ParserConfig const&, std::shared_ptr<llvm::SourceMgr> const&) /home/x/fun/HECO/dependencies/llvm-project/mlir/include/mlir/Parser/Parser.h:159:14
#78 0x0000557549e1a848 mlir::OwningOpRef<mlir::ModuleOp> mlir::parseSourceFile<mlir::ModuleOp>(std::shared_ptr<llvm::SourceMgr> const&, mlir::ParserConfig const&) /home/x/fun/HECO/dependencies/llvm-project/mlir/include/mlir/Parser/Parser.h:189:10
#79 0x0000557549e19e6e mlir::parseSourceFileForTool(std::shared_ptr<llvm::SourceMgr> const&, mlir::ParserConfig const&, bool) /home/x/fun/HECO/dependencies/llvm-project/mlir/include/mlir/Tools/ParseUtilities.h:31:12
#80 0x0000557549e0e6f7 performActions(llvm::raw_ostream&, std::shared_ptr<llvm::SourceMgr> const&, mlir::MLIRContext*, mlir::MlirOptMainConfig const&) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/Tools/mlir-opt/MlirOptMain.cpp:353:16
#81 0x0000557549e0e4d6 processBuffer(llvm::raw_ostream&, std::unique_ptr<llvm::MemoryBuffer, std::default_delete<llvm::MemoryBuffer>>, mlir::MlirOptMainConfig const&, mlir::DialectRegistry&, llvm::ThreadPool*) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/Tools/mlir-opt/MlirOptMain.cpp:431:12
#82 0x0000557549e0e229 mlir::MlirOptMain(llvm::raw_ostream&, std::unique_ptr<llvm::MemoryBuffer, std::default_delete<llvm::MemoryBuffer>>, mlir::DialectRegistry&, mlir::MlirOptMainConfig const&)::$_0::operator()(std::unique_ptr<llvm::MemoryBuffer, std::default_delete<llvm::MemoryBuffer>>, llvm::raw_ostream&) const /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/Tools/mlir-opt/MlirOptMain.cpp:472:12
#83 0x0000557549e0e193 mlir::LogicalResult llvm::function_ref<mlir::LogicalResult (std::unique_ptr<llvm::MemoryBuffer, std::default_delete<llvm::MemoryBuffer>>, llvm::raw_ostream&)>::callback_fn<mlir::MlirOptMain(llvm::raw_ostream&, std::unique_ptr<llvm::MemoryBuffer, std::default_delete<llvm::MemoryBuffer>>, mlir::DialectRegistry&, mlir::MlirOptMainConfig const&)::$_0>(long, std::unique_ptr<llvm::MemoryBuffer, std::default_delete<llvm::MemoryBuffer>>, llvm::raw_ostream&) /home/x/fun/HECO/dependencies/llvm-project/llvm/include/llvm/ADT/STLFunctionalExtras.h:45:12
#84 0x000055754cfa59ef llvm::function_ref<mlir::LogicalResult (std::unique_ptr<llvm::MemoryBuffer, std::default_delete<llvm::MemoryBuffer>>, llvm::raw_ostream&)>::operator()(std::unique_ptr<llvm::MemoryBuffer, std::default_delete<llvm::MemoryBuffer>>, llvm::raw_ostream&) const /home/x/fun/HECO/dependencies/llvm-project/llvm/include/llvm/ADT/STLFunctionalExtras.h:68:12
#85 0x000055754cfa4ed8 mlir::splitAndProcessBuffer(std::unique_ptr<llvm::MemoryBuffer, std::default_delete<llvm::MemoryBuffer>>, llvm::function_ref<mlir::LogicalResult (std::unique_ptr<llvm::MemoryBuffer, std::default_delete<llvm::MemoryBuffer>>, llvm::raw_ostream&)>, llvm::raw_ostream&, bool, bool) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/Support/ToolUtilities.cpp:28:12
#86 0x0000557549e0af76 mlir::MlirOptMain(llvm::raw_ostream&, std::unique_ptr<llvm::MemoryBuffer, std::default_delete<llvm::MemoryBuffer>>, mlir::DialectRegistry&, mlir::MlirOptMainConfig const&) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/Tools/mlir-opt/MlirOptMain.cpp:475:10
#87 0x0000557549e0b4da mlir::MlirOptMain(int, char**, llvm::StringRef, mlir::DialectRegistry&) /home/x/fun/HECO/dependencies/llvm-project/mlir/lib/Tools/mlir-opt/MlirOptMain.cpp:531:14
#88 0x00005575459e4f3b main (./build/bin/heco+0x2fef3b)
#89 0x00007fae16faecd0 (/usr/lib/libc.so.6+0x27cd0)
#90 0x00007fae16faed8a __libc_start_main (/usr/lib/libc.so.6+0x27d8a)
#91 0x0000557545a295e5 _start (./build/bin/heco+0x3435e5)
[1]    205705 IOT instruction (core dumped)  ./build/bin/heco < test/example.mlir

I ran this code in ubuntu 22.04 and followed the instructions in https://secartifacts.github.io/usenixsec2023/appendix-files/sec23winterae-final39.pdf.

Adding support for proper calls

Currently, the AST Call node is only used for "fake" calls like rotate. However, in general it would be nice to support real functions and calls.

Add inling

In v1.0, we supported function inlining, up to a certain threshold. This feature should be ported over.

Adding Tests:

In v1.0, Commit 97c1679 added a threshold to the inlining of Call nodes, i.e., functions are only inlined if their return statement has a depth smaller than N nodes.

• There exist no tests yet that check if that threshold really works.

• Also, there must be an additional check added that makes sure that the called function is fully inlined, that is, there are not other statements in the program except a Return statement. Because otherwise replacing only the function call by the return expression in the called function would lead to an invalid result.

Currently, it is not obvious which AST node attributes are mandatory and which are optional. For example, an If statement optionally takes an initializer and an update statement but requires a condition and a body statement.

We therefore should introduce a system to denote attributes as nullable/non-nullable, for example, using Clang's annotation feature that also throws warnings at compile-time. We should check in advance if these annotations are also supported by the other compilers (MSVC, gcc).

Because of the way that we define the ASTs for tests, e.g. "new If( , , )", the order in which AST elements get created is unspecified. Since most tests rely on comparing Nodes' uniqueID which increments sequentially, this makes the tests very brittle.

The brute-force way of solving this would be to introduce new variables for each parameter, however this would make the code very hard to read.

Instead, a cleaner solution would be to implement a parser that translates an AST from a text file into a C++ Ast object with deterministic initialisation order.

ABC AST Limitations

This document gathers limitations of our current AST which mainly became apparent while building the Python frontend. Some duplicates with #36 may exist.

Multi-Return Values / Multi-Assignment

What?

The following (Python) syntax is not supported in our AST:

def f():
  return 1, "abc", 2.0 # <- Multi-return

a, b, c = f() # <- Multi-assignment

Something similar is supported though: return values can be ExpressionLists, which contain (a fixed number of) entries of the same type. However, there is no multi-assignment. In fact, those vectors are never changed in size and we always operate on the full vector. All variables are vectors. Thus, assigning variables to parts of the vector is not (straightforward) to support.

Why is this useful?

To efficiently translate higher level languages as Python to our framework.

Type Casting

We do not support type casting yet. I.e., double * int will result in an error and not implicitly cast the int to a double. A real intermediate representation should solve such issues.

No Break Statement / No While Loop

There is no break statement for for-loops. This is an issue for the Python frontend, since Python has limited for-loops. Instead, we often use while-loops to express things.

But without break, some while loops cannot easily be translated, e.g.

i = 1
while True:
  i += i
  if i > 100:
    break

because here, we do an update before checking the condition. This is not the same as

int i;
for (i = 1; i > 100; i += i);

E.g., when we initialize i to 100, the first results in i = 200, the second in i = 100. Detecting how to transform those loops doesn't seem trivial.

Of course, this is only translatable to FHE if i is a non-secret value. We could emulate while loops with for loops (as for(; true; )) but that still requires a break statement for the terminating condition.

Slices

We don't support slices, e.g. v[3:5] to get part of a vector. This is also cumbersome to add, since the vectors used internally never change their size.

Tuple vs List

There is no distinction between tuples and lists in our AST. The main difference in Python is that Tuples are immutable while Lists are mutable. Currently, we use ExpressionLists for Python lists and don't translate Tuples. One of the disadvantages is that we cannot support return statements with multiple values (because they are tuples in Python).

Integrate this project with SHEEP or our own WOOL wrapper around it.

This would replace the current RuntimeVisitor, and would allow supporting multiple backends (e.g. SEAL, Pallisade, etc) relatively easily.

The header files are not all commented well yet:

• Add comments to every class briefly describing the entity it represents. Make sure that the used format is supported by Doxygen (check in generated docs).
  • Add a description of which attributes are mandatory/optional.
• Add comments to every method except the ones that are overridden, already commented on the top-level, and do not implement a different behavior.

Hello,

I've noticed that branch main isn't really HECO, so I've tried to build dev.
After building SEAL and MLIR as required, the command cmake --build . --target check-fhe as written in the README doesn't work (no such target).
Which target should I build? Is dev even the correct branch to work with?

Thanks,
Or

fhe::Multiply::fold (x,1) -> x does not apply to arith.constant

@pjattke The ConeWriting paper [1] has a heuristic for runtime of FHE operations at certain depths, we should probably add this to get some fast rough estimates of optimisation impact without having to burn compute resources

[1] Aubry, P. et al. 2020. Faster Homomorphic Encryption is not Enough: Improved Heuristic for Multiplicative Depth Minimization of Boolean Circuits. Topics in Cryptology – CT-RSA 2020 (2020), 345–363.

The current AST implementation does not support common FHE operations such as ModSwitch, Relinearization, and Key-Switching. These operations must be added as simple placeholders (without logic).

Maybe it makes sense to introduce a general node that does not contain any implementation but serves as placeholder? It could have an attribute "operation type" that designates the operation it stands for, e.g., ModSwitch.

Overwriting a secret variable by a public value on all execution paths lets the variable become public. See TODO note in SecretTaintingVisitor class.

Use the ControlFlowGraphVisitor to determine the execution paths and the generated data flow graph to analyze if a variable is written in all of these paths and if the written value is public.

Currently, the CompileTimeExpressionSimplifier replaces every variable by the variable's current value. The value can either be a literal (e.g., LiteralInt) or a symbolic expression (e.g., ArithmeticExpr).

As the expression defining a variable's value can be very long, it would make sense to define a subtree depth threshold that determines whether variable substitution should still be done or not. See TODO note in CompileTimeExpressionSimplifier class.

Our current parser implementation does not support the increment (++) and decrement (--) operators. As they are very common, supporting them would make it easier for users.

Also, currently our parser does not provide a meaningful error message in case that a increment/decrement operator was found. For example:

for (int i = 0; i < 22; i++) ...
unknown file: Failure

stdout:
> C++ exception with description "Syntax error: Expected '=' on Line 4, position 88" thrown in the test body.

Python Frontend Limitations

This issue tracks the current limitations of the Python frontend. Some of them are simply not implemented, others have more fundamental issues.

Reduced Syntax

Python has quite a rich syntax. Check python/pyabc/ABCVisitor.py to see which constructs are supported and which are not.

Multi-Assignment

This could be supported with our current AST, but would require us to build the JSON string manually in the Python frontend instead of building a dictionary. Manual building would allow one visit function to add more than one statement to the resulting string.

Alternatively, support for multi-assignments can be added to the AST. IMO, this would be a cleaner solution.

Float vs. Double

We just convert every decimal number (float in Python) to a double in C++. Keep in mind that the FHE circuit only does approximate computation on floats anyway, so such computations lose some precision even if the types could be preserved.

Dynamic Types

Variables cannot change their types (neither in C++ nor our FHE AST). Translations with an IR or to SSA would solve this issue.

Type Casting

The frontend does not support type casting. I.e., double * int will result in an error and not implicitly cast the int to a double. ABC does not support this either.

For this reason, the frontend currently simply parses the value of a variable declaration and then uses the data type of the first constant that it finds among those values. For a list, it takes the type of the first entry, as in ABC, all values are vectors, so a vector of LiteralInt also has type LiteralInt.

⚠️ An unexpected side-effect of this is, that the Python operator / behaves like // for Integers. The Python expression (2 * 6) / 5 would return 2.4 in Python, but returns 2 for our FHE program, since it is integer division and no type casting happens.

Returning expressions

Currently, a function has to return a variable and cannot return expressions. This is because the RuntimeVisitor requires a list of variables which should be returned in the end.

This is no fundamental limitation. Either the frontend parsing could introduce one variable for every returned expression, or the RuntimeVisitor could be changed to support non-variable return values. ABC AST Return nodes do support arbitrary AbstractExpression's to be returned.

Multiple Return Statements

Multiple return statements are currently not really supported. The ABC AST can return ExpressionList variables, but we currently use them to represent Python lists so we cannot use them for multi-return values (of the same type) as well. In Python, multi-return statements have a Tuple argument, which we don't support (see also #37).

Note that the frontend code would already be written in a way that would support multiple return values.

Mixed Return Types or Lists

We do not support returning different types, i.e.:

return 1, "abc" # not supported

The execute function of the Python wrapper supports some hackery to be able to return different literal types (casted to Python types). For this purpose, it is declared to return a Python object instead of a specific C++ type, so that it can return different values and lists. However, multi-return statements are currently not supported because they cannot be parsed. Returning the values would be possible using similar tricks.

For Loops Only Support Range

For loops currently only support iterating over a range. This construct only does addition/subtraction. The Pythonic way to do more complex conditions is usually to use while loops, but we do not yet support while loops.

Be aware, that the Python expression

for i in range(a, b, s)

is translated to the condition:

for(int i = a; ((a <= b) && i < b) || ((a > b) && i > b); i += s)

because s can be negative.

Like Python, for range(b) we use a = 0 and s = 1, and for range(a, b) we use s = 1.

At the moment, we just force the loop variable of for-loops to be an int.

Variable Types

⚠️ Type information on a variable gets lost when you declare a new variable to equal another one.
The problem is that at compile-time, we do not know the type of all variables in Python. For function arguments, the variable type is not known. We could solve this in the future by requiring type annotation for those values. The consequence is currently that variables always have to be set to literal types or expressions (without abstract targets).

The issue with "void"-type variables is, that we cannot operate on them. E.g., to compare them with other integers or do arithmetic. Or we would need to figure out the type when we perform an operation, but then it could change depending on the operation.

For example, the following works:

def main(a):
    r = a + 1
    return r

But not this, since b is of type void, which cannot be added with a LiteralInt:

def main(a):
    b = a
    r = a + 1
    return r

However, this would work if we know that a is always an int:

def main(a):
    b = 0
    b = a
    r = a + 1
    return r

Python Lists =/= ExpressionLists

At the moment, Python lists are translated to ABC ExpressionLists. We potentially need to give up some list features if we keep them like this (list comprehension, list concatenation).

Ciphertext Results

Currently, we only support the DummyCiphertextFactory. There is no way to export encrypted data to Python. We therefore always decrypt it and then return it. Only vector<int64_t> results are supported by the DummyCiphertextFactory.

Known Bug: Secret Tainting Return Values

There is a bug when we define and return a new variable that is tainted.

The following throws an error:

def main(a, b):
  r = a + b
  return r

Error: RuntimeError: Initialization value of VariableDeclaration ( r) could not be processed successfully.

However, using an input variable to store the output is a workaround:

def main(a, b):
  a += b
  return a

Ineractive Console

The frontend does not work on an interactive console (e.g., when executing python on the command line), since it cannot fetch the source code.

Return Ciphertext

At the moment, it is not possible to get the result of a function with secret inputs. The reason is that we don't have a wrapper for the serialized ciphertext and its context information.

As a temporary hack, we only use the DummyCiphertext suite and always decrypt results before returning them.

External Function Calls with Non-Secret Inputs

External function calls with non-secret inputs may return unexpected results. E.g., when the function branches based on an unknown input, then the translation can lead to unexpected result, since the condition is executed on a generic ciphertext object.
The underlying problem is that we don't explore all possible execution paths, since they depend on the unknown input. This is not an issue for secret inputs, since we cannot branch on them anyway. However, it also doesn't work for non-secret inputs, since we do not distinguish them and replace both with generic objects.

The SecretTaintingVisitor currently uses a variable's identifier only to distinguish between variables. This, however, does not uniquely identify a variable because there can be multiple variables with the same identifier, declared in different scopes. We therefore need to also take the scope into account.

This enhancement is already implemented in the CompileTimeExpressionSimplifier and uses scope information provided by the base Visitor class.

There are only very few tests for the evaluation logic of arithmetic expressions (ArithmeticExpr) and logical expressions (LogicalExpr). Even though exhaustive testing may not be required, it still would make sense to have at least a few tests for each operator involving different combinations of operand types.

See the tests for the OperatorExpr (OperatorExprTest.cpp) for an example of how this could be done and documented.

Hello,
Could it be that the latest version in main is not updated?
Since I've tried building HECO (after installing successfully all the necessary dependencies) and got compilation errors in HECO files, I fixed them only to get dozens of errors.

Build command: cmake --build . --target fhe-tool
System information: Windows 10, Visual Studio 17 2022" -A x64, python 3.10.6, SEAL 4.0.0, c++17, cmake 3.26.0-msvc3,

(NOTE: FIX THEN ANOTHER ERROR LOG AT THE END)

The initial error log before fixing the files is:

MSBuild version 17.6.3+07e294721 for .NET Framework

Checking Build System
Building LowerASTtoSSA.cpp.inc...
Building Custom Rule E:/myFolder/uni/masters/2nd_semestru/mpc/pr
oject/MPC-HECO/src/Passes/ast2hir/CMakeLists.txt
Building LowerBGVToEmitC.cpp.inc...
Building Custom Rule E:/myFolder/uni/masters/2nd_semestru/mpc/pr
oject/MPC-HECO/src/Passes/bgv2emitc/CMakeLists.txt
Building AST.cpp.inc...
E:/myFolder/uni/masters/2nd_semestru/mpc/project/MPC-HECO/include/
heco/IR/AST/AST.td(79,70): error GD3F9BD08: Variable not defined:
'NoSideEffect' [E:\myFolder\uni\masters\2nd_semestru\mpc\project\M
PC-HECO\build\include\heco\IR\AST\MLIRASTIncGen.vcxproj]
Op<AST_Dialect, mnemonic, !listconcat(traits, [NoTermina
tor, NoSideEffect])> {

   ^

E:\programs\Microsoft Visual Studio\2022\MSBuild\Microsoft\VC\v170
\Microsoft.CppCommon.targets(248,5): error MSB8066: Custom build f
or 'E:\myFolder\uni\masters\2nd_semestru\mpc\project\MPC-HECO\buil
d\CMakeFiles\6a7a3ad6bcfc65143adfa1cb24433f40\AST.cpp.inc.rule;E:
myFolder\uni\masters\2nd_semestru\mpc\project\MPC-HECO\build\CMake
Files\6a7a3ad6bcfc65143adfa1cb24433f40\AST.h.inc.rule;E:\myFolder
uni\masters\2nd_semestru\mpc\project\MPC-HECO\build\CMakeFiles\6a7
a3ad6bcfc65143adfa1cb24433f40\ASTDialect.cpp.inc.rule;E:\myFolder
uni\masters\2nd_semestru\mpc\project\MPC-HECO\build\CMakeFiles\6a7
a3ad6bcfc65143adfa1cb24433f40\ASTDialect.h.inc.rule;E:\myFolder\un
i\masters\2nd_semestru\mpc\project\MPC-HECO\build\CMakeFiles\6a7a3
ad6bcfc65143adfa1cb24433f40\ASTTypes.cpp.inc.rule;E:\myFolder\uni
masters\2nd_semestru\mpc\project\MPC-HECO\build\CMakeFiles\6a7a3ad
6bcfc65143adfa1cb24433f40\ASTTypes.h.inc.rule;E:\myFolder\uni\mast
ers\2nd_semestru\mpc\project\MPC-HECO\build\CMakeFiles\1f9081cc038
413f8f3810b5dd8cd7d90\MLIRASTIncGen.rule;E:\myFolder\uni\masters\2
nd_semestru\mpc\project\MPC-HECO\include\heco\IR\AST\CMakeLists.tx
t' exited with code 1. [E:\myFolder\uni\masters\2nd_semestru\mpc\p
roject\MPC-HECO\build\include\heco\IR\AST\MLIRASTIncGen.vcxproj]
Building BGV.cpp.inc...
E:/myFolder/uni/masters/2nd_semestru/mpc/project/MPC-HECO/include/
heco/IR/BGV/BGV.td(183,56): error GD3F9BD08: Variable not defined:
'NoSideEffect' [E:\myFolder\uni\masters\2nd_semestru\mpc\project
MPC-HECO\build\include\heco\IR\BGV\MLIRBGVIncGen.vcxproj]
Op<BGV_Dialect, mnemonic, !listconcat(traits, [NoSideEff
ect])> {
^
E:\programs\Microsoft Visual Studio\2022\MSBuild\Microsoft\VC\v170
\Microsoft.CppCommon.targets(248,5): error MSB8066: Custom build f
or 'E:\myFolder\uni\masters\2nd_semestru\mpc\project\MPC-HECO\buil
d\CMakeFiles\01ea4537eede8f0dcd4e92bf3f077017\BGV.cpp.inc.rule;E:
myFolder\uni\masters\2nd_semestru\mpc\project\MPC-HECO\build\CMake
Files\01ea4537eede8f0dcd4e92bf3f077017\BGV.h.inc.rule;E:\myFolder
uni\masters\2nd_semestru\mpc\project\MPC-HECO\build\CMakeFiles\01e
a4537eede8f0dcd4e92bf3f077017\BGVDialect.cpp.inc.rule;E:\myFolder
uni\masters\2nd_semestru\mpc\project\MPC-HECO\build\CMakeFiles\01e
a4537eede8f0dcd4e92bf3f077017\BGVDialect.h.inc.rule;E:\myFolder\un
i\masters\2nd_semestru\mpc\project\MPC-HECO\build\CMakeFiles\01ea4
537eede8f0dcd4e92bf3f077017\BGVTypes.cpp.inc.rule;E:\myFolder\uni
masters\2nd_semestru\mpc\project\MPC-HECO\build\CMakeFiles\01ea453
7eede8f0dcd4e92bf3f077017\BGVTypes.h.inc.rule;E:\myFolder\uni\mast
ers\2nd_semestru\mpc\project\MPC-HECO\build\CMakeFiles\1ac8efa7e4c
b1de68e0b331477a6dee1\MLIRBGVIncGen.rule;E:\myFolder\uni\masters\2
nd_semestru\mpc\project\MPC-HECO\include\heco\IR\BGV\CMakeLists.tx
t' exited with code 1. [E:\myFolder\uni\masters\2nd_semestru\mpc\p
roject\MPC-HECO\build\include\heco\IR\BGV\MLIRBGVIncGen.vcxproj]
Building FHE.cpp.inc...
E:/myFolder/uni/masters/2nd_semestru/mpc/project/MPC-HECO/include/
heco/IR/FHE/FHE.td(113,56): error GD3F9BD08: Variable not defined:
'NoSideEffect' [E:\myFolder\uni\masters\2nd_semestru\mpc\project
MPC-HECO\build\include\heco\IR\FHE\MLIRFHEIncGen.vcxproj]
Op<FHE_Dialect, mnemonic, !listconcat(traits, [NoSideEff
ect])> {
^
E:\programs\Microsoft Visual Studio\2022\MSBuild\Microsoft\VC\v170
\Microsoft.CppCommon.targets(248,5): error MSB8066: Custom build f
or 'E:\myFolder\uni\masters\2nd_semestru\mpc\project\MPC-HECO\buil
d\CMakeFiles\e468c8c4cdbb186cb76c31d8565023c4\FHE.cpp.inc.rule;E:
myFolder\uni\masters\2nd_semestru\mpc\project\MPC-HECO\build\CMake
Files\e468c8c4cdbb186cb76c31d8565023c4\FHE.h.inc.rule;E:\myFolder
uni\masters\2nd_semestru\mpc\project\MPC-HECO\build\CMakeFiles\e46
8c8c4cdbb186cb76c31d8565023c4\FHEDialect.cpp.inc.rule;E:\myFolder
uni\masters\2nd_semestru\mpc\project\MPC-HECO\build\CMakeFiles\e46
8c8c4cdbb186cb76c31d8565023c4\FHEDialect.h.inc.rule;E:\myFolder\un
i\masters\2nd_semestru\mpc\project\MPC-HECO\build\CMakeFiles\e468c
8c4cdbb186cb76c31d8565023c4\FHETypes.cpp.inc.rule;E:\myFolder\uni
masters\2nd_semestru\mpc\project\MPC-HECO\build\CMakeFiles\e468c8c
4cdbb186cb76c31d8565023c4\FHETypes.h.inc.rule;E:\myFolder\uni\mast
ers\2nd_semestru\mpc\project\MPC-HECO\build\CMakeFiles\ba84f29a516
0a3c7cfb8c4f0cf0beffb\MLIRFHEIncGen.rule;E:\myFolder\uni\masters\2
nd_semestru\mpc\project\MPC-HECO\include\heco\IR\FHE\CMakeLists.tx
t' exited with code 1. [E:\myFolder\uni\masters\2nd_semestru\mpc\p
roject\MPC-HECO\build\include\heco\IR\FHE\MLIRFHEIncGen.vcxproj]
Building Poly.cpp.inc...
E:/myFolder/uni/masters/2nd_semestru/mpc/project/MPC-HECO/include/
heco/IR/Poly/Poly.td(94,57): error GD3F9BD08: Variable not defined
: 'NoSideEffect' [E:\myFolder\uni\masters\2nd_semestru\mpc\project
\MPC-HECO\build\include\heco\IR\Poly\MLIRPolyIncGen.vcxproj]
Op<Poly_Dialect, mnemonic, !listconcat(traits, [NoSideEf
fect])> {
^
E:\programs\Microsoft Visual Studio\2022\MSBuild\Microsoft\VC\v170
\Microsoft.CppCommon.targets(248,5): error MSB8066: Custom build f
or 'E:\myFolder\uni\masters\2nd_semestru\mpc\project\MPC-HECO\buil
d\CMakeFiles\e0ddedf1159f9df4ee43ad39ffd703a6\Poly.cpp.inc.rule;E:
\myFolder\uni\masters\2nd_semestru\mpc\project\MPC-HECO\build\CMak
eFiles\e0ddedf1159f9df4ee43ad39ffd703a6\Poly.h.inc.rule;E:\myFolde
r\uni\masters\2nd_semestru\mpc\project\MPC-HECO\build\CMakeFiles\e
0ddedf1159f9df4ee43ad39ffd703a6\PolyDialect.cpp.inc.rule;E:\myFold
er\uni\masters\2nd_semestru\mpc\project\MPC-HECO\build\CMakeFiles
e0ddedf1159f9df4ee43ad39ffd703a6\PolyDialect.h.inc.rule;E:\myFolde
r\uni\masters\2nd_semestru\mpc\project\MPC-HECO\build\CMakeFiles\e
0ddedf1159f9df4ee43ad39ffd703a6\PolyTypes.cpp.inc.rule;E:\myFolder
\uni\masters\2nd_semestru\mpc\project\MPC-HECO\build\CMakeFiles\e0
ddedf1159f9df4ee43ad39ffd703a6\PolyTypes.h.inc.rule;E:\myFolder\un
i\masters\2nd_semestru\mpc\project\MPC-HECO\build\CMakeFiles\ff50a
cfb62e704ede97a8906d13fa96b\MLIRPolyIncGen.rule;E:\myFolder\uni\ma
sters\2nd_semestru\mpc\project\MPC-HECO\include\heco\IR\Poly\CMake
Lists.txt' exited with code 1. [E:\myFolder\uni\masters\2nd_semest
ru\mpc\project\MPC-HECO\build\include\heco\IR\Poly\MLIRPolyIncGen.
vcxproj]
Building Custom Rule E:/myFolder/uni/masters/2nd_semestru/mpc/pr
oject/MPC-HECO/CMakeLists.txt
Building LowerBGVToLLVM.cpp.inc...
Building Custom Rule E:/myFolder/uni/masters/2nd_semestru/mpc/pr
oject/MPC-HECO/src/Passes/bgv2llvm/CMakeLists.txt
Building LowerFHEToBGV.cpp.inc...
Building Custom Rule E:/myFolder/uni/masters/2nd_semestru/mpc/pr
oject/MPC-HECO/src/Passes/fhe2bgv/CMakeLists.txt

After editing files: AST.td, BGV.td, FHE.td, Poly.td s.t replaced: "NoSideEffect" with "NoMemoryEffect" and "operands" with "operand"
I got the following error log (it was too long so attached in file):

cmake --build . --target fhe-tool
MSBuild version 17.6.3+07e294721 for .NET Framework

Building AST.cpp.inc...
Building AST.h.inc...
Building ASTDialect.cpp.inc...
Building ASTDialect.h.inc...
Building ASTTypes.cpp.inc...
Building ASTTypes.h.inc...
Building BGV.cpp.inc...
Building BGV.h.inc...
Building BGVDialect.cpp.inc...
Building BGVDialect.h.inc...
Building BGVTypes.cpp.inc...
Building BGVTypes.h.inc...
Building FHE.cpp.inc...
Building FHE.h.inc...
Building FHEDialect.cpp.inc...
Building FHEDialect.h.inc...
Building FHETypes.cpp.inc...
Building FHETypes.h.inc...
Building Poly.cpp.inc...
Building Poly.h.inc...
Building PolyDialect.cpp.inc...
Building PolyDialect.h.inc...
Building PolyTypes.cpp.inc...
Building PolyTypes.h.inc...
Building Custom Rule E:/myFolder/uni/masters/2nd_semestru/mpc/project/MPC-HECO/CMakeLists.txt
Building Custom Rule E:/myFolder/uni/masters/2nd_semestru/mpc/project/MPC-HECO/src/IR/AST/CMake
Lists.txt
cl : command line warning D9025: overriding '/EHs' with '/EHs-' [E:\myFolder\uni\masters\2nd_sem
estru\mpc\project\MPC-HECO\build\src\IR\AST\obj.HECOASTDialect.vcxproj]
ASTDialect.cpp
cl : command line warning D9025: overriding '/EHc' with '/EHc-' [E:\myFolder\uni\masters\2nd_sem
estru\mpc\project\MPC-HECO\build\src\IR\AST\obj.HECOASTDialect.vcxproj]
obj.HECOASTDialect.vcxproj -> E:\myFolder\uni\masters\2nd_semestru\mpc\project\MPC-HECO\build\s
rc\IR\AST\obj.HECOASTDialect.dir\Debug\obj.HECOASTDialect.lib
Building Custom Rule E:/myFolder/uni/masters/2nd_semestru/mpc/project/MPC-HECO/src/IR/AST/CMake
Lists.txt
HECOASTDialect.vcxproj -> E:\myFolder\uni\masters\2nd_semestru\mpc\project\MPC-HECO\build\lib\H
ECOASTDialect.lib
Building Custom Rule E:/myFolder/uni/masters/2nd_semestru/mpc/project/MPC-HECO/src/IR/BGV/CMake
Lists.txt
cl : command line warning D9025: overriding '/EHs' with '/EHs-' [E:\myFolder\uni\masters\2nd_sem
estru\mpc\project\MPC-HECO\build\src\IR\BGV\obj.HECOBGVDialect.vcxproj]
cl : command line warning D9025: overriding '/EHc' with '/EHc-' [E:\myFolder\uni\masters\2nd_sem
estru\mpc\project\MPC-HECO\build\src\IR\BGV\obj.HECOBGVDialect.vcxproj]
BGVDialect.cpp
E:\myFolder\uni\masters\2nd_semestru\mpc\project\llvm-new\llvm-project\mlir\include\mlir/IR/Built
inAttributes.h(359,7): warning C4996: 'std::complexllvm::APFloat::complex': warning STL4037: Th
e effect of instantiating the template std::complex for any type other than float, double, or lon
g double is unspecified. You can define _SILENCE_NONFLOATING_COMPLEX_DEPRECATION_WARNING to suppr
ess this warning. [E:\myFolder\uni\masters\2nd_semestru\mpc\project\MPC-HECO\build\src\IR\BGV\obj
.HECOBGVDialect.vcxproj]
E:\myFolder\uni\masters\2nd_semestru\mpc\project\MPC-HECO\src\IR\BGV\BGVDialect.cpp(25,43): error
C2039: 'Optional': is not a member of 'llvm' [E:\myFolder\uni\masters\2nd_semestru\mpc\project\M
PC-HECO\build\src\IR\BGV\obj.HECOBGVDialect.vcxproj]
E:\myFolder\uni\masters\2nd_semestru\mpc\project\llvm-new\llvm-project\llvm\include\llvm/ADT/Type
Switch.h(22,11): message : see declaration of 'llvm' [E:\myFolder\uni\masters\2nd_semestru\mpc\pr
oject\MPC-HECO\build\src\IR\BGV\obj.HECOBGVDialect.vcxproj]
E:\myFolder\uni\masters\2nd_semestru\mpc\project\MPC-HECO\src\IR\BGV\BGVDialect.cpp(25,51): error
C2061: syntax error: identifier 'Optional' [E:\myFolder\uni\masters\2nd_semestru\mpc\project\MPC
-HECO\build\src\IR\BGV\obj.HECOBGVDialect.vcxproj]

THE FULL ERROR LOG IS IN THE FILE:

error-log2.txt

Any help will be appreciated!

HECO doesn't build against MLIR commit on July 18th, 2024
llvm/llvm-project@a41a4b8

with the error,

n file included from /Users/mannamalai/devel/HECO/include/heco/IR/FHE/FHEDialect.h:4:
/usr/local/include/mlir/IR/Builders.h:511:11: error: no matching member function for call to 'build'
  511 |     OpTy::build(*this, state, std::forward<Args>(args)...);
      |     ~~~~~~^~~~~
/usr/local/include/mlir/IR/PatternMatch.h:537:18: note: in instantiation of function template specialization 'mlir::OpBuilder::create<mlir::emitc::CallOp, mlir::TypeRange, llvm::StringRef, mlir::ArrayAttr, mlir::ArrayAttr, llvm::SmallVector<mlir::Value> &>' requested here
  537 |     auto newOp = create<OpTy>(op->getLoc(), std::forward<Args>(args)...);
      |                  ^
/Users/mannamalai/devel/HECO/src/Passes/fhe2emitc/LowerFHEToEmitC.cpp:235:18: note: in instantiation of function template specialization 'mlir::RewriterBase::replaceOpWithNewOp<mlir::emitc::CallOp, mlir::TypeRange, llvm::StringRef, mlir::ArrayAttr, mlir::ArrayAttr, llvm::SmallVector<mlir::Value> &>' requested here
  235 |         rewriter.replaceOpWithNewOp<emitc::CallOp>(
      |                  ^
/Library/Developer/CommandLineTools/SDKs/MacOSX14.4.sdk/usr/include/c++/v1/__memory/unique_ptr.h:689:30: note: in instantiation of member function 'EmitCArithmeticPattern<heco::fhe::MultiplyOp>::matchAndRewrite' requested here
  689 |   return unique_ptr<_Tp>(new _Tp(_VSTD::forward<_Args>(__args)...));
      |                              ^
/usr/local/include/mlir/IR/PatternMatch.h:278:14: note: in instantiation of function template specialization 'std::make_unique<EmitCArithmeticPattern<heco::fhe::MultiplyOp>, mlir::TypeConverter &, mlir::MLIRContext *>' requested here
  278 |         std::make_unique<T>(std::forward<Args>(args)...);
      |              ^
/usr/local/include/mlir/IR/PatternMatch.h:990:25: note: in instantiation of function template specialization 'mlir::RewritePattern::create<EmitCArithmeticPattern<heco::fhe::MultiplyOp>, mlir::TypeConverter &, mlir::MLIRContext *>' requested here
  990 |         RewritePattern::create<T>(std::forward<Args>(args)...);
      |                         ^
/usr/local/include/mlir/IR/PatternMatch.h:850:6: note: in instantiation of function template specialization 'mlir::RewritePatternSet::addImpl<EmitCArithmeticPattern<heco::fhe::MultiplyOp>, mlir::TypeConverter &, mlir::MLIRContext *>' requested here
  850 |     (addImpl<Ts>(/*debugLabels=*/std::nullopt,
      |      ^
/Users/mannamalai/devel/HECO/src/Passes/fhe2emitc/LowerFHEToEmitC.cpp:359:14: note: in instantiation of function template specialization 'mlir::RewritePatternSet::add<EmitCReturnPattern, EmitCArithmeticPattern<heco::fhe::SubOp>, EmitCArithmeticPattern<heco::fhe::AddOp>, EmitCArithmeticPattern<heco::fhe::MultiplyOp>, EmitCRotatePattern, EmitCCombinePattern, EmitCFunctionPattern, mlir::TypeConverter &, mlir::MLIRContext *, void>' requested here
  359 |     patterns.add<

Currently, our parser does not understand ternary operators (e.g., int a = c > 10 ? 2 : 0). As this is just syntactic sugar for writing an dependent assignment in a concise way, it would be nice to provide this as convenience to the user.

Currently, the parser only supports for loops. A simple workaround that does not require to extend the AST would be to transform parsed while loops into for loops of the form for ( ; condition ; ), i.e., without initializer and update statements.

I suspect that the If-statement rewriting will break the AST if certain non-rewriteable statements are in the Then- or Else-branch, for example, a For-loop.

A test must be added to verify or falsify the CompileTimeExpressionSimplifier's result if an If-statement includes a For-loop.

Partial loop unrolling considers the number of ciphertext slots. For example, if there are 256 slots then 256 iterations are unrolled to enable simultaneous execution using SIMD capabilities of the underlying FHE scheme. The remaining loops are executed using a cleanup loop For example, if the initial number of iteration is 500 then the remaining 244 iterations would be executed using the cleanup loop.

Currently, the cleanup loop only executes a single operation at once. This could be improved by generating a binary series of cleanup loops, for example, the unrolled loop uses 256 slots, followed by a 128-unrolled cleanup loop, then a 64-unrolled cleanup loop, then a 32-unrolled cleanup loop, etc. See TODO note in CompileTimeExpressionSimplifier.

A question involved in the implementation is to decide at which point to stop (minimum unroll factor of cleanup loop). Maybe this must be determined using an empirical approach.

The GitHub Actions build does currently not work. On the local dev machine (macOS) it works, however, without any issues. Probably, the issues are related to implementation-specific differences between Apple's Clang and gcc.

I would recommend debugging the issues using a local Linux (e.g., Ubuntu) installation with gcc. Maybe it's worth investigating the exact gcc version that is used in the CI/CD build.

In v1.0, we had a MultDepthVisitor that determined the multiplicative depth of variables, which might be handy to port over.

Note that the visitor in v1.0 does not work properly if an If-statement that contains an Else-branch is involved.

The statement following an If-statement, i.e., the statement after the Else-branch's closing bracket if (...) { ...} else { ... } must take the "highest depth" of a variable by comparing the calculated depth of both branches.

The ControlFlowGraphVisitor currently uses a variable's identifier only to distinguish between variables. This, however, does not uniquely identify a variable because there can be multiple variables with the same identifier, declared in different scopes. We therefore need to also take the scope into account.

This enhancement is already implemented in the CompileTimeExpressionSimplifier and uses scope information provided by the base Visitor class.