fork(1) download
copy 
  1. sealed trait Regex
  2. case object Empty                  extends Regex
  3. case class Let(c: Char)            extends Regex
  4. case class Con(a: Regex, b: Regex) extends Regex
  5. case class Alt(a: Regex, b: Regex) extends Regex
  6. case class Star(a: Regex)          extends Regex
  7.  
  8. sealed trait Value
  9. case class RInt(n: Int)            extends Value
  10. case class RStr(s: String)         extends Value
  11. case class VInt(n: Int)            extends Value
  12. case class BA(f: String, l: Value) extends Value
  13.  
  14. sealed trait Type
  15. case object I1   extends Type
  16. case object I8   extends Type
  17. case object I8P  extends Type
  18. case object I64  extends Type
  19. case object I64P extends Type
  20.  
  21. sealed trait Cond
  22. case object Eq extends Cond
  23.  
  24. sealed trait Inst
  25. case class Label(n: Value)                                    extends Inst
  26. case class Assign(l: Value, r: Inst)                          extends Inst
  27. case class Add(t: Type, v: Value, n: Int)                     extends Inst
  28. case class Cmp(c: Cond, t: Type, a: Value, b: Value)          extends Inst
  29. case class Br1(d: Value)                                      extends Inst
  30. case class Br2(c: Value, t: Value, e: Value)                  extends Inst
  31. case class Call(f: String, rt: Type, at: List[(Type, Value)]) extends Inst
  32. case class Load(t: Type, p: Value)                            extends Inst
  33. case class Store(vt: Type, v: Value, pt: Type, pv: Value)     extends Inst
  34. case class GetElementPtr(t: Type, v: Value, i: Value)         extends Inst
  35.  
  36. object Main {
  37.   def nsp    = RStr("sp")
  38.   def nstr   = RStr("str")
  39.   def nmatch = RStr("match")
  40.   def nmiss  = RStr("miss")
  41.  
  42.   def fname = "@test"
  43.  
  44.   def assign(r: Inst, n: Int): (Inst, Int) = (Assign(RInt(n), r), n + 1)
  45.   def mk_label(n: Int): (Inst, Int) = (Label(RInt(n)), n + 1)
  46.  
  47.   def insts_of_regex(re: Regex): List[Inst] = {
  48.     def loop(re: Regex, n: Int): (List[Inst], Int) = re match {
  49.       case Empty => (Nil, n)
  50.  
  51.       case Let(c) =>
  52.         val (i1, n1) = mk_label(n)
  53.         val (i2, n2) = assign(Load(I64P, nsp), n1)
  54.         val (i3, n3) = assign(GetElementPtr(I8P, nstr, RInt(n1)), n2)
  55.         val (i4, n4) = assign(Add(I64, RInt(n1), 1), n3)
  56.         val  i5      = Store(I64, RInt(n3), I64P, nsp)
  57.         val (i6, n5) = assign(Load(I8P, RInt(n2)), n4)
  58.         val (i7, n6) = assign(Cmp(Eq, I8, RInt(n4), VInt(c.toInt)), n5)
  59.         val  i8      = Br2(RInt(n5), RInt(n6), nmiss)
  60.         (List(i1, i2, i3, i4, i5, i6, i7, i8), n6)
  61.  
  62.       case Con(a, b) =>
  63.         val (i1, n1) = loop(a, n)
  64.         val (i2, n2) = loop(b, n1)
  65.         (i1 ++ i2, n2)
  66.  
  67.       case Alt(a, b) =>
  68.         val (i1, n1) = mk_label(n)
  69.         val (i2, n2) = assign(Load(I64P, nsp), n1)
  70.         val (i3, _)  = assign(Call(fname, I1, List((I8P, BA(fname, RInt(n2 + 1))), (I64, RInt(n1)))), n2)
  71.         val (i4, n4) = loop(a, n2 + 1)
  72.         val (i5, n5) = mk_label(n4)
  73.         val (i6, n6) = loop(b, n5)
  74.         val i7       = Br1(RInt(n6))
  75.         val i8       = Br2(RInt(n2), nmatch, RInt(n5))
  76.         (List(i1, i2, i3, i8) ++ i4 ++ List(i5, i7) ++ i6, n6)
  77.  
  78.       case Star(Star(r)) => loop(Star(r), n)
  79.  
  80.       case Star(r) =>
  81.         val (i1, n1) = mk_label(n)
  82.         val (i2, n2) = assign(Load(I64P, nsp), n1)
  83.         val (i3, _)  = assign(Call(fname, I1, List((I8P, BA(fname, RInt(n2 + 1))), (I64, RInt(n1)))), n2)
  84.         val (i4, n3) = loop(r, n2 + 1)
  85.         val (i5, n4) = mk_label(n3)
  86.         val  i6      = Br1(RInt(n))
  87.         val  i7      = Br2(RInt(n2), nmatch, RInt(n4))
  88.         (List(i1, i2, i3, i7) ++ i4 ++ List(i5, i6), n4)
  89.     }
  90.  
  91.     val (i, n) = loop(re, 1)
  92.     i ++ List(Label(RInt(n)), Br1(nmatch))
  93.   }
  94.  
  95.   def label_of_value(v: Value): String = v match {
  96.     case RInt(n) => n.toString
  97.     case _       => throw new Exception()
  98.   }
  99.  
  100.   def var_of_value(v: Value): String = v match {
  101.     case RInt(n)  => "%" + n
  102.     case RStr(s)  => "%" + s
  103.     case VInt(n)  => n.toString
  104.     case BA(f, l) => "blockaddress(" + f + ", " + var_of_value(l) + ")"
  105.   }
  106.  
  107.   def pp_cond(c: Cond): String = c match {
  108.     case Eq => "eq"
  109.   }
  110.  
  111.   def pp_type(t: Type): String = t match {
  112.     case I1   => "i1"
  113.     case I8   => "i8"
  114.     case I8P  => "i8*"
  115.     case I64  => "i64"
  116.     case I64P => "i64*"
  117.   }
  118.  
  119.   def align(t: Type): Int = t match {
  120.     case I8   => 1
  121.     case I8P  => 8
  122.     case I64  => 8
  123.     case I64P => 8
  124.     case I1   => throw new Exception()
  125.   }
  126.  
  127.   def pp_inst(i: Inst, tab: String = ""): String =
  128.     tab + (i match {
  129.       case Label(n) =>
  130.         "\n; <label>:" + label_of_value(n)
  131.       case Assign(l, r) =>
  132.         var_of_value(l) + " = " + pp_inst(r)
  133.       case Add(t, v, n) =>
  134.         "add nsw " + pp_type(t) + " " + var_of_value(v) + ", " + n
  135.       case Cmp(c, t, a, b) =>
  136.         "icmp " + pp_cond(c) + " " + pp_type(t) + " " + var_of_value(a) + ", " + var_of_value(b)
  137.       case Br1(d) =>
  138.         "br label " + var_of_value(d)
  139.       case Br2(c, t, e) =>
  140.         "br i1 " + var_of_value(c) + ", label " + var_of_value(t) + ", label " + var_of_value(e)
  141.       case Call(f, rt, a) =>
  142.         val s = a.foldLeft("i8* %str")((x, y) => x + ", " + pp_type(y._1) + " " + var_of_value(y._2))
  143.         "call " + pp_type(rt) + " " + f + "(" + s + ")"
  144.       case Load(t, p) =>
  145.         "load " + pp_type(t) + " " + var_of_value(p) + ", align " + align(t)
  146.       case Store(vt, v, pt, pv) =>
  147.         "store " + pp_type(vt) + " " + var_of_value(v) + ", " + pp_type(pt) + " " +
  148.           var_of_value(pv) + ", align " + align(vt)
  149.       case GetElementPtr(t, v, i) =>
  150.         "getelementptr inbounds " + pp_type(t) + " " + var_of_value(v) + ", i64 " + var_of_value(i)
  151.     })
  152.  
  153.   def make(i: List[Inst]): String = {
  154.     val s =
  155.       "@.match   = private unnamed_addr constant [7 x i8] c\"match\\0A\\00\", align 1\n"  +
  156.       "@.unmatch = private unnamed_addr constant [9 x i8] c\"unmatch\\0A\\00\", align 1\n\n" +
  157.       "define i1 @test(i8* %str, i8* %l, i64 %sp_value) {\n" +
  158.       "  %sp = alloca i64, align 8\n" +
  159.       "  store i64 %sp_value, i64* %sp, align 8\n" +
  160.       "  %isnull = icmp eq i8* %l, null\n" +
  161.       "  br i1 %isnull, label %1, label %jump\n\n" +
  162.       "jump:\n" +
  163.       "  indirectbr i8* %l, [" +
  164.         i.foldRight(List[String]())((x, y) => x match {
  165.           case Label(n) => ("label " + var_of_value(n)) :: y
  166.           case _        => y
  167.         }).mkString(", ") + "]\n"
  168.  
  169.     val llvmir = i.map(pp_inst(_, "  ")).foldLeft("")((x, y) => x + y + "\n")
  170.  
  171.     val e =
  172.       "\nmiss:\n" +
  173.       "  ret i1 0\n\n" +
  174.       "match:\n" +
  175.       "  ret i1 1\n" +
  176.       "}\n\n" +
  177.       "define i32 @main(i32 %argc, i8** %argv) {\n" +
  178.       "  %arg1 = getelementptr inbounds i8** %argv, i64 1\n" +
  179.       "  %str  = load i8** %arg1, align 8\n" +
  180.       "  %res  = call i1 @test(i8* %str, i8* null, i64 0)\n" +
  181.       "  br i1 %res, label %match, label %unmatch\n\n" +
  182.       "match:\n" +
  183.       "  call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([7 x i8]* @.match, i32 0, i32 0))\n" +
  184.       "  br label %ret\n\n" +
  185.       "unmatch:\n" +
  186.       "  call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([9 x i8]* @.unmatch, i32 0, i32 0))\n" +
  187.       "  br label %ret\n\n" +
  188.       "ret:\n" +
  189.       "  ret i32 0\n" +
  190.       "}\n\n" +
  191.       "declare i32 @printf(i8*, ...)"
  192.  
  193.     s + llvmir + e
  194.   }
  195.  
  196.   def main(args: Array[String]): Unit = {
  197.     // aa*bb*
  198.     val re1 = Con( Con(Let('a'), Star(Let('a'))), Con(Let('b'), Star(Let('b'))) )
  199.     // (a|b)c
  200.     val re2 = Con( Alt(Let('a'), Let('b')),  Let('c')  )
  201.     // (a*)*a
  202.     val re3 = Con(Star(Star(Let('a'))), Let('a'))
  203.     // aaaa
  204.     val re4 = Con( Con(Let('a'), Let('a')), Con(Let('a'), Let('a')) )
  205.     // (ba*ba*)*a
  206.     val re5 = Con(Star(Con(Con(Star(Let('a')), Let('b')), Star(Let('a')))), Let('a'))
  207.     // sa*(ba*ba*)*a*e
  208.     val re6 = Con(Con(Let('s'), Con(Con(Star(Let('a')), Star(Con(Con(Let('b'), Star(Let('a'))), Con(Let('b'), Star(Let('a')))))), Star(Let('a')))), Let('e'))
  209.     // s(ab*)*e
  210.     val re7 = Con(Con(Let('s'), Star(Con(Let('a'), Star(Let('b'))))), Let('e'))
  211.     // ba*b
  212.     val re8 = Con(Con(Let('b'), Star(Let('a'))), Let('b'))
  213.  
  214.     val i   = insts_of_regex(re8)
  215.     println(make(i))
  216.   }
  217. }
  218.  
Success #stdin #stdout 0.37s 322368KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
@.match   = private unnamed_addr constant [7 x i8] c"match\0A\00", align 1
@.unmatch = private unnamed_addr constant [9 x i8] c"unmatch\0A\00", align 1

define i1 @test(i8* %str, i8* %l, i64 %sp_value) {
  %sp = alloca i64, align 8
  store i64 %sp_value, i64* %sp, align 8
  %isnull = icmp eq i8* %l, null
  br i1 %isnull, label %1, label %jump

jump:
  indirectbr i8* %l, [label %1, label %7, label %10, label %16, label %17, label %23]
  
; <label>:1
  %2 = load i64* %sp, align 8
  %3 = getelementptr inbounds i8* %str, i64 %2
  %4 = add nsw i64 %2, 1
  store i64 %4, i64* %sp, align 8
  %5 = load i8* %3, align 8
  %6 = icmp eq i8 %5, 98
  br i1 %6, label %7, label %miss
  
; <label>:7
  %8 = load i64* %sp, align 8
  %9 = call i1 @test(i8* %str, i8* blockaddress(@test, %10), i64 %8)
  br i1 %9, label %match, label %17
  
; <label>:10
  %11 = load i64* %sp, align 8
  %12 = getelementptr inbounds i8* %str, i64 %11
  %13 = add nsw i64 %11, 1
  store i64 %13, i64* %sp, align 8
  %14 = load i8* %12, align 8
  %15 = icmp eq i8 %14, 97
  br i1 %15, label %16, label %miss
  
; <label>:16
  br label %7
  
; <label>:17
  %18 = load i64* %sp, align 8
  %19 = getelementptr inbounds i8* %str, i64 %18
  %20 = add nsw i64 %18, 1
  store i64 %20, i64* %sp, align 8
  %21 = load i8* %19, align 8
  %22 = icmp eq i8 %21, 98
  br i1 %22, label %23, label %miss
  
; <label>:23
  br label %match

miss:
  ret i1 0

match:
  ret i1 1
}

define i32 @main(i32 %argc, i8** %argv) {
  %arg1 = getelementptr inbounds i8** %argv, i64 1
  %str  = load i8** %arg1, align 8
  %res  = call i1 @test(i8* %str, i8* null, i64 0)
  br i1 %res, label %match, label %unmatch

match:
  call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([7 x i8]* @.match, i32 0, i32 0))
  br label %ret

unmatch:
  call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([9 x i8]* @.unmatch, i32 0, i32 0))
  br label %ret

ret:
  ret i32 0
}

declare i32 @printf(i8*, ...)
https://ideone.com/ahuaWI
language:
Scala (scala 2.12.8)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!