forked from NUDT-compiler/nudt-compiler-cpp
You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
407 lines
12 KiB
407 lines
12 KiB
@mod = global i32 998244353
|
|
@d = global i32 0
|
|
@maxlen = global i32 2097152
|
|
@temp = global [2097152 x i32] zeroinitializer
|
|
@a = global [2097152 x i32] zeroinitializer
|
|
@b = global [2097152 x i32] zeroinitializer
|
|
@c = global [2097152 x i32] zeroinitializer
|
|
|
|
declare i32 @getint()
|
|
declare float @getfloat()
|
|
declare i32 @getarray(i32* %arg.a)
|
|
declare i32 @getfarray(float* %arg.a)
|
|
declare i32 @getch()
|
|
declare void @putint(i32 %arg.x)
|
|
declare void @putfloat(float %arg.x)
|
|
declare void @putarray(i32 %arg.n, i32* %arg.a)
|
|
declare void @putfarray(i32 %arg.n, float* %arg.a)
|
|
declare void @putch(i32 %arg.x)
|
|
declare void @starttime()
|
|
declare void @stoptime()
|
|
define i32 @multiply(i32 %arg.a, i32 %arg.b) {
|
|
entry:
|
|
%t12 = alloca i32
|
|
%t0 = alloca i32
|
|
store i32 %arg.a, i32* %t0
|
|
%t1 = alloca i32
|
|
store i32 %arg.b, i32* %t1
|
|
%t2 = load i32, i32* %t1
|
|
%t3 = icmp eq i32 %t2, 0
|
|
%t4 = zext i1 %t3 to i32
|
|
%t5 = icmp ne i32 %t4, 0
|
|
br i1 %t5, label %if.then.1, label %if.end.2
|
|
if.then.1:
|
|
ret i32 0
|
|
if.end.2:
|
|
%t6 = load i32, i32* %t1
|
|
%t7 = icmp eq i32 %t6, 1
|
|
%t8 = zext i1 %t7 to i32
|
|
%t9 = icmp ne i32 %t8, 0
|
|
br i1 %t9, label %if.then.3, label %if.end.4
|
|
if.then.3:
|
|
%t10 = load i32, i32* %t0
|
|
%t11 = srem i32 %t10, 998244353
|
|
ret i32 %t11
|
|
if.end.4:
|
|
%t13 = load i32, i32* %t0
|
|
%t14 = load i32, i32* %t1
|
|
%t15 = sdiv i32 %t14, 2
|
|
%t16 = call i32 @multiply(i32 %t13, i32 %t15)
|
|
store i32 %t16, i32* %t12
|
|
%t17 = load i32, i32* %t12
|
|
%t18 = load i32, i32* %t12
|
|
%t19 = add i32 %t17, %t18
|
|
%t20 = srem i32 %t19, 998244353
|
|
store i32 %t20, i32* %t12
|
|
%t21 = load i32, i32* %t1
|
|
%t22 = srem i32 %t21, 2
|
|
%t23 = icmp eq i32 %t22, 1
|
|
%t24 = zext i1 %t23 to i32
|
|
%t25 = icmp ne i32 %t24, 0
|
|
br i1 %t25, label %if.then.5, label %if.else.6
|
|
if.then.5:
|
|
%t26 = load i32, i32* %t12
|
|
%t27 = load i32, i32* %t0
|
|
%t28 = add i32 %t26, %t27
|
|
%t29 = srem i32 %t28, 998244353
|
|
ret i32 %t29
|
|
if.else.6:
|
|
%t30 = load i32, i32* %t12
|
|
ret i32 %t30
|
|
if.end.7:
|
|
ret i32 0
|
|
}
|
|
define i32 @power(i32 %arg.a, i32 %arg.b) {
|
|
entry:
|
|
%t37 = alloca i32
|
|
%t31 = alloca i32
|
|
store i32 %arg.a, i32* %t31
|
|
%t32 = alloca i32
|
|
store i32 %arg.b, i32* %t32
|
|
%t33 = load i32, i32* %t32
|
|
%t34 = icmp eq i32 %t33, 0
|
|
%t35 = zext i1 %t34 to i32
|
|
%t36 = icmp ne i32 %t35, 0
|
|
br i1 %t36, label %if.then.8, label %if.end.9
|
|
if.then.8:
|
|
ret i32 1
|
|
if.end.9:
|
|
%t38 = load i32, i32* %t31
|
|
%t39 = load i32, i32* %t32
|
|
%t40 = sdiv i32 %t39, 2
|
|
%t41 = call i32 @power(i32 %t38, i32 %t40)
|
|
store i32 %t41, i32* %t37
|
|
%t42 = load i32, i32* %t37
|
|
%t43 = load i32, i32* %t37
|
|
%t44 = call i32 @multiply(i32 %t42, i32 %t43)
|
|
store i32 %t44, i32* %t37
|
|
%t45 = load i32, i32* %t32
|
|
%t46 = srem i32 %t45, 2
|
|
%t47 = icmp eq i32 %t46, 1
|
|
%t48 = zext i1 %t47 to i32
|
|
%t49 = icmp ne i32 %t48, 0
|
|
br i1 %t49, label %if.then.10, label %if.else.11
|
|
if.then.10:
|
|
%t50 = load i32, i32* %t37
|
|
%t51 = load i32, i32* %t31
|
|
%t52 = call i32 @multiply(i32 %t50, i32 %t51)
|
|
ret i32 %t52
|
|
if.else.11:
|
|
%t53 = load i32, i32* %t37
|
|
ret i32 %t53
|
|
if.end.12:
|
|
ret i32 0
|
|
}
|
|
define i32 @memmove(i32* %arg.dst, i32 %arg.dst_pos, i32* %arg.src, i32 %arg.len) {
|
|
entry:
|
|
%t56 = alloca i32
|
|
%t54 = alloca i32
|
|
store i32 %arg.dst_pos, i32* %t54
|
|
%t55 = alloca i32
|
|
store i32 %arg.len, i32* %t55
|
|
store i32 0, i32* %t56
|
|
br label %while.cond.13
|
|
while.cond.13:
|
|
%t57 = load i32, i32* %t56
|
|
%t58 = load i32, i32* %t55
|
|
%t59 = icmp slt i32 %t57, %t58
|
|
%t60 = zext i1 %t59 to i32
|
|
%t61 = icmp ne i32 %t60, 0
|
|
br i1 %t61, label %while.body.14, label %while.end.15
|
|
while.body.14:
|
|
%t62 = load i32, i32* %t54
|
|
%t63 = load i32, i32* %t56
|
|
%t64 = add i32 %t62, %t63
|
|
%t65 = getelementptr inbounds i32, i32* %arg.dst, i32 %t64
|
|
%t66 = load i32, i32* %t56
|
|
%t67 = getelementptr inbounds i32, i32* %arg.src, i32 %t66
|
|
%t68 = load i32, i32* %t67
|
|
store i32 %t68, i32* %t65
|
|
%t69 = load i32, i32* %t56
|
|
%t70 = add i32 %t69, 1
|
|
store i32 %t70, i32* %t56
|
|
br label %while.cond.13
|
|
while.end.15:
|
|
%t71 = load i32, i32* %t56
|
|
ret i32 %t71
|
|
}
|
|
define i32 @fft(i32* %arg.arr, i32 %arg.begin_pos, i32 %arg.n, i32 %arg.w) {
|
|
entry:
|
|
%t79 = alloca i32
|
|
%t132 = alloca i32
|
|
%t139 = alloca i32
|
|
%t145 = alloca i32
|
|
%t72 = alloca i32
|
|
store i32 %arg.begin_pos, i32* %t72
|
|
%t73 = alloca i32
|
|
store i32 %arg.n, i32* %t73
|
|
%t74 = alloca i32
|
|
store i32 %arg.w, i32* %t74
|
|
%t75 = load i32, i32* %t73
|
|
%t76 = icmp eq i32 %t75, 1
|
|
%t77 = zext i1 %t76 to i32
|
|
%t78 = icmp ne i32 %t77, 0
|
|
br i1 %t78, label %if.then.16, label %if.end.17
|
|
if.then.16:
|
|
ret i32 1
|
|
if.end.17:
|
|
store i32 0, i32* %t79
|
|
br label %while.cond.18
|
|
while.cond.18:
|
|
%t80 = load i32, i32* %t79
|
|
%t81 = load i32, i32* %t73
|
|
%t82 = icmp slt i32 %t80, %t81
|
|
%t83 = zext i1 %t82 to i32
|
|
%t84 = icmp ne i32 %t83, 0
|
|
br i1 %t84, label %while.body.19, label %while.end.20
|
|
while.body.19:
|
|
%t85 = load i32, i32* %t79
|
|
%t86 = srem i32 %t85, 2
|
|
%t87 = icmp eq i32 %t86, 0
|
|
%t88 = zext i1 %t87 to i32
|
|
%t89 = icmp ne i32 %t88, 0
|
|
br i1 %t89, label %if.then.21, label %if.else.22
|
|
while.end.20:
|
|
%t111 = load i32, i32* %t72
|
|
%t112 = load i32, i32* %t73
|
|
%t113 = getelementptr inbounds [2097152 x i32], [2097152 x i32]* @temp, i32 0, i32 0
|
|
%t114 = call i32 @memmove(i32* %arg.arr, i32 %t111, i32* %t113, i32 %t112)
|
|
%t115 = load i32, i32* %t72
|
|
%t116 = load i32, i32* %t73
|
|
%t117 = sdiv i32 %t116, 2
|
|
%t118 = load i32, i32* %t74
|
|
%t119 = load i32, i32* %t74
|
|
%t120 = call i32 @multiply(i32 %t118, i32 %t119)
|
|
%t121 = call i32 @fft(i32* %arg.arr, i32 %t115, i32 %t117, i32 %t120)
|
|
%t122 = load i32, i32* %t72
|
|
%t123 = load i32, i32* %t73
|
|
%t124 = sdiv i32 %t123, 2
|
|
%t125 = add i32 %t122, %t124
|
|
%t126 = load i32, i32* %t73
|
|
%t127 = sdiv i32 %t126, 2
|
|
%t128 = load i32, i32* %t74
|
|
%t129 = load i32, i32* %t74
|
|
%t130 = call i32 @multiply(i32 %t128, i32 %t129)
|
|
%t131 = call i32 @fft(i32* %arg.arr, i32 %t125, i32 %t127, i32 %t130)
|
|
store i32 0, i32* %t79
|
|
store i32 1, i32* %t132
|
|
br label %while.cond.24
|
|
if.then.21:
|
|
%t90 = load i32, i32* %t79
|
|
%t91 = sdiv i32 %t90, 2
|
|
%t92 = getelementptr inbounds [2097152 x i32], [2097152 x i32]* @temp, i32 0, i32 %t91
|
|
%t93 = load i32, i32* %t79
|
|
%t94 = load i32, i32* %t72
|
|
%t95 = add i32 %t93, %t94
|
|
%t96 = getelementptr inbounds i32, i32* %arg.arr, i32 %t95
|
|
%t97 = load i32, i32* %t96
|
|
store i32 %t97, i32* %t92
|
|
br label %if.end.23
|
|
if.else.22:
|
|
%t98 = load i32, i32* %t73
|
|
%t99 = sdiv i32 %t98, 2
|
|
%t100 = load i32, i32* %t79
|
|
%t101 = sdiv i32 %t100, 2
|
|
%t102 = add i32 %t99, %t101
|
|
%t103 = getelementptr inbounds [2097152 x i32], [2097152 x i32]* @temp, i32 0, i32 %t102
|
|
%t104 = load i32, i32* %t79
|
|
%t105 = load i32, i32* %t72
|
|
%t106 = add i32 %t104, %t105
|
|
%t107 = getelementptr inbounds i32, i32* %arg.arr, i32 %t106
|
|
%t108 = load i32, i32* %t107
|
|
store i32 %t108, i32* %t103
|
|
br label %if.end.23
|
|
if.end.23:
|
|
%t109 = load i32, i32* %t79
|
|
%t110 = add i32 %t109, 1
|
|
store i32 %t110, i32* %t79
|
|
br label %while.cond.18
|
|
while.cond.24:
|
|
%t133 = load i32, i32* %t79
|
|
%t134 = load i32, i32* %t73
|
|
%t135 = sdiv i32 %t134, 2
|
|
%t136 = icmp slt i32 %t133, %t135
|
|
%t137 = zext i1 %t136 to i32
|
|
%t138 = icmp ne i32 %t137, 0
|
|
br i1 %t138, label %while.body.25, label %while.end.26
|
|
while.body.25:
|
|
%t140 = load i32, i32* %t72
|
|
%t141 = load i32, i32* %t79
|
|
%t142 = add i32 %t140, %t141
|
|
%t143 = getelementptr inbounds i32, i32* %arg.arr, i32 %t142
|
|
%t144 = load i32, i32* %t143
|
|
store i32 %t144, i32* %t139
|
|
%t146 = load i32, i32* %t72
|
|
%t147 = load i32, i32* %t79
|
|
%t148 = add i32 %t146, %t147
|
|
%t149 = load i32, i32* %t73
|
|
%t150 = sdiv i32 %t149, 2
|
|
%t151 = add i32 %t148, %t150
|
|
%t152 = getelementptr inbounds i32, i32* %arg.arr, i32 %t151
|
|
%t153 = load i32, i32* %t152
|
|
store i32 %t153, i32* %t145
|
|
%t154 = load i32, i32* %t72
|
|
%t155 = load i32, i32* %t79
|
|
%t156 = add i32 %t154, %t155
|
|
%t157 = getelementptr inbounds i32, i32* %arg.arr, i32 %t156
|
|
%t158 = load i32, i32* %t139
|
|
%t159 = load i32, i32* %t132
|
|
%t160 = load i32, i32* %t145
|
|
%t161 = call i32 @multiply(i32 %t159, i32 %t160)
|
|
%t162 = add i32 %t158, %t161
|
|
%t163 = srem i32 %t162, 998244353
|
|
store i32 %t163, i32* %t157
|
|
%t164 = load i32, i32* %t72
|
|
%t165 = load i32, i32* %t79
|
|
%t166 = add i32 %t164, %t165
|
|
%t167 = load i32, i32* %t73
|
|
%t168 = sdiv i32 %t167, 2
|
|
%t169 = add i32 %t166, %t168
|
|
%t170 = getelementptr inbounds i32, i32* %arg.arr, i32 %t169
|
|
%t171 = load i32, i32* %t139
|
|
%t172 = load i32, i32* %t132
|
|
%t173 = load i32, i32* %t145
|
|
%t174 = call i32 @multiply(i32 %t172, i32 %t173)
|
|
%t175 = sub i32 %t171, %t174
|
|
%t176 = add i32 %t175, 998244353
|
|
%t177 = srem i32 %t176, 998244353
|
|
store i32 %t177, i32* %t170
|
|
%t178 = load i32, i32* %t132
|
|
%t179 = load i32, i32* %t74
|
|
%t180 = call i32 @multiply(i32 %t178, i32 %t179)
|
|
store i32 %t180, i32* %t132
|
|
%t181 = load i32, i32* %t79
|
|
%t182 = add i32 %t181, 1
|
|
store i32 %t182, i32* %t79
|
|
br label %while.cond.24
|
|
while.end.26:
|
|
ret i32 0
|
|
}
|
|
define i32 @main() {
|
|
entry:
|
|
%t183 = alloca i32
|
|
%t186 = alloca i32
|
|
%t212 = alloca i32
|
|
%t184 = getelementptr inbounds [2097152 x i32], [2097152 x i32]* @a, i32 0, i32 0
|
|
%t185 = call i32 @getarray(i32* %t184)
|
|
store i32 %t185, i32* %t183
|
|
%t187 = getelementptr inbounds [2097152 x i32], [2097152 x i32]* @b, i32 0, i32 0
|
|
%t188 = call i32 @getarray(i32* %t187)
|
|
store i32 %t188, i32* %t186
|
|
call void @starttime()
|
|
store i32 1, i32* @d
|
|
br label %while.cond.27
|
|
while.cond.27:
|
|
%t190 = load i32, i32* @d
|
|
%t191 = load i32, i32* %t183
|
|
%t192 = load i32, i32* %t186
|
|
%t193 = add i32 %t191, %t192
|
|
%t194 = sub i32 %t193, 1
|
|
%t195 = icmp slt i32 %t190, %t194
|
|
%t196 = zext i1 %t195 to i32
|
|
%t197 = icmp ne i32 %t196, 0
|
|
br i1 %t197, label %while.body.28, label %while.end.29
|
|
while.body.28:
|
|
%t198 = load i32, i32* @d
|
|
%t199 = mul i32 %t198, 2
|
|
store i32 %t199, i32* @d
|
|
br label %while.cond.27
|
|
while.end.29:
|
|
%t200 = load i32, i32* @d
|
|
%t201 = load i32, i32* @d
|
|
%t202 = sdiv i32 998244352, %t201
|
|
%t203 = call i32 @power(i32 3, i32 %t202)
|
|
%t204 = getelementptr inbounds [2097152 x i32], [2097152 x i32]* @a, i32 0, i32 0
|
|
%t205 = call i32 @fft(i32* %t204, i32 0, i32 %t200, i32 %t203)
|
|
%t206 = load i32, i32* @d
|
|
%t207 = load i32, i32* @d
|
|
%t208 = sdiv i32 998244352, %t207
|
|
%t209 = call i32 @power(i32 3, i32 %t208)
|
|
%t210 = getelementptr inbounds [2097152 x i32], [2097152 x i32]* @b, i32 0, i32 0
|
|
%t211 = call i32 @fft(i32* %t210, i32 0, i32 %t206, i32 %t209)
|
|
store i32 0, i32* %t212
|
|
br label %while.cond.30
|
|
while.cond.30:
|
|
%t213 = load i32, i32* %t212
|
|
%t214 = load i32, i32* @d
|
|
%t215 = icmp slt i32 %t213, %t214
|
|
%t216 = zext i1 %t215 to i32
|
|
%t217 = icmp ne i32 %t216, 0
|
|
br i1 %t217, label %while.body.31, label %while.end.32
|
|
while.body.31:
|
|
%t218 = load i32, i32* %t212
|
|
%t219 = getelementptr inbounds [2097152 x i32], [2097152 x i32]* @a, i32 0, i32 %t218
|
|
%t220 = load i32, i32* %t212
|
|
%t221 = getelementptr inbounds [2097152 x i32], [2097152 x i32]* @a, i32 0, i32 %t220
|
|
%t222 = load i32, i32* %t221
|
|
%t223 = load i32, i32* %t212
|
|
%t224 = getelementptr inbounds [2097152 x i32], [2097152 x i32]* @b, i32 0, i32 %t223
|
|
%t225 = load i32, i32* %t224
|
|
%t226 = call i32 @multiply(i32 %t222, i32 %t225)
|
|
store i32 %t226, i32* %t219
|
|
%t227 = load i32, i32* %t212
|
|
%t228 = add i32 %t227, 1
|
|
store i32 %t228, i32* %t212
|
|
br label %while.cond.30
|
|
while.end.32:
|
|
%t229 = load i32, i32* @d
|
|
%t230 = load i32, i32* @d
|
|
%t231 = sdiv i32 998244352, %t230
|
|
%t232 = sub i32 998244352, %t231
|
|
%t233 = call i32 @power(i32 3, i32 %t232)
|
|
%t234 = getelementptr inbounds [2097152 x i32], [2097152 x i32]* @a, i32 0, i32 0
|
|
%t235 = call i32 @fft(i32* %t234, i32 0, i32 %t229, i32 %t233)
|
|
store i32 0, i32* %t212
|
|
br label %while.cond.33
|
|
while.cond.33:
|
|
%t236 = load i32, i32* %t212
|
|
%t237 = load i32, i32* @d
|
|
%t238 = icmp slt i32 %t236, %t237
|
|
%t239 = zext i1 %t238 to i32
|
|
%t240 = icmp ne i32 %t239, 0
|
|
br i1 %t240, label %while.body.34, label %while.end.35
|
|
while.body.34:
|
|
%t241 = load i32, i32* %t212
|
|
%t242 = getelementptr inbounds [2097152 x i32], [2097152 x i32]* @a, i32 0, i32 %t241
|
|
%t243 = load i32, i32* %t212
|
|
%t244 = getelementptr inbounds [2097152 x i32], [2097152 x i32]* @a, i32 0, i32 %t243
|
|
%t245 = load i32, i32* %t244
|
|
%t246 = load i32, i32* @d
|
|
%t247 = call i32 @power(i32 %t246, i32 998244351)
|
|
%t248 = call i32 @multiply(i32 %t245, i32 %t247)
|
|
store i32 %t248, i32* %t242
|
|
%t249 = load i32, i32* %t212
|
|
%t250 = add i32 %t249, 1
|
|
store i32 %t250, i32* %t212
|
|
br label %while.cond.33
|
|
while.end.35:
|
|
call void @stoptime()
|
|
%t252 = load i32, i32* %t183
|
|
%t253 = load i32, i32* %t186
|
|
%t254 = add i32 %t252, %t253
|
|
%t255 = sub i32 %t254, 1
|
|
%t256 = getelementptr inbounds [2097152 x i32], [2097152 x i32]* @a, i32 0, i32 0
|
|
call void @putarray(i32 %t255, i32* %t256)
|
|
ret i32 0
|
|
}
|