NilFoundation / zkLLVM

Zero-Knowledge Proof Systems Circuit Compiler
https://docs.nil.foundation/zkllvm
299 stars 48 forks source link

[Feature request]: for-loop inside for-loop. #522

Open ETatuzova opened 9 months ago

ETatuzova commented 9 months ago

It would be a useful improvement if this type of loops could be assigned.

#include <nil/crypto3/algebra/curves/pallas.hpp>

using namespace nil::crypto3::algebra::curves;

[[circuit]] typename pallas::base_field_type::value_type
    field_for_example(
        typename pallas::base_field_type::value_type a,
        typename pallas::base_field_type::value_type b
) {
    for( std::size_t i = 0; i < 100; i++){
        for( std::size_t j = 0; j < i; j++){
            a = a + b;
        }
    }
    return a;
}
ETatuzova commented 9 months ago

This construction will also be extremely useful:

#include <nil/crypto3/algebra/curves/pallas.hpp>

using namespace nil::crypto3::algebra::curves;

constexpr std::array<std::size_t, 5> sizes = {1,2,3,4,5};

[[circuit]] typename pallas::base_field_type::value_type
    field_for_example(
        typename pallas::base_field_type::value_type a,
        typename pallas::base_field_type::value_type b
) {
    for( std::size_t i = 0; i < 100; i++){
        for( std::size_t j = 0; j < sizes[i]; j++){
            a = a + b;
        }
    }
    return a;
}
akokoshn commented 9 months ago

Suggestion:

  1. Try to use loop fuse before unroll for make 1 loop: ~/zkLLVM/libs/circifier/llvm/lib/Transforms/Scalar/LoopFuse.cpp, by adding step to pipeline assBuilder::buildO1FunctionSimplificationPipeline in file ~/zkLLVM/libs/circifier/llvm/lib/Passes/PassBuilderPipelines.cpp
  2. Change order of unrolling (first unroll external loop), see ~/zkLLVM/libs/circifier/llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp , tryToUnrollLoop