From f3718a9bf100596cce88f0d5ed27c16a204fe58f Mon Sep 17 00:00:00 2001 From: Andrew Wilkins Date: Thu, 8 Jan 2015 07:49:28 +0000 Subject: [PATCH] [llgo] irgen: generate switch instructions Summary: With this patch, llgo uses ssautil.Switches to reconstitute (and synthesise) switches, which can then be lowered to lookup tables, trees, etc. We currently only handle integer const case switches. We erase the comparison blocks (other than the initial block), and generate a switch instruction at the end of the block starting the if-else-if chain. ssautil.Switches does not remove duplicate const cases (e.g. same operands for "||"), so we do this in llgo for now. Test Plan: lit test added Reviewers: pcc Reviewed By: pcc Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D6831 llvm-svn: 225433 --- llgo/irgen/ssa.go | 10 +++- llgo/irgen/switches.go | 145 ++++++++++++++++++++++++++++++++++++++++++++++ llgo/test/irgen/switch.go | 62 ++++++++++++++++++++ 3 files changed, 216 insertions(+), 1 deletion(-) create mode 100644 llgo/irgen/switches.go create mode 100644 llgo/test/irgen/switch.go diff --git a/llgo/irgen/ssa.go b/llgo/irgen/ssa.go index 1991ddb..903e804 100644 --- a/llgo/irgen/ssa.go +++ b/llgo/irgen/ssa.go @@ -352,6 +352,7 @@ func (u *unit) defineFunction(f *ssa.Function) { fr.blocks[i] = llvm.AddBasicBlock(fr.function, fmt.Sprintf(".%d.%s", i, block.Comment)) } fr.builder.SetInsertPointAtEnd(fr.blocks[0]) + fr.transformSwitches(f) prologueBlock := llvm.InsertBasicBlock(fr.blocks[0], "prologue") fr.builder.SetInsertPointAtEnd(prologueBlock) @@ -433,7 +434,11 @@ func (u *unit) defineFunction(f *ssa.Function) { fr.allocaBuilder.SetInsertPointBefore(prologueBlock.FirstInstruction()) for _, block := range f.DomPreorder() { - fr.translateBlock(block, fr.blocks[block.Index]) + llblock := fr.blocks[block.Index] + if llblock.IsNil() { + continue + } + fr.translateBlock(block, llblock) } fr.fixupPhis() @@ -1179,6 +1184,9 @@ func (fr *frame) instruction(instr ssa.Instruction) { fr.builder.CreateStore(value, addr) } + case *switchInstr: + fr.emitSwitch(instr) + case *ssa.TypeAssert: x := fr.value(instr.X) if instr.CommaOk { diff --git a/llgo/irgen/switches.go b/llgo/irgen/switches.go new file mode 100644 index 0000000..861a2dd --- /dev/null +++ b/llgo/irgen/switches.go @@ -0,0 +1,145 @@ +//===- switches.go - misc utils -------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements transformations and IR generation for switches. +// +//===----------------------------------------------------------------------===// + +package irgen + +import ( + "go/token" + + "llvm.org/llgo/third_party/go.tools/go/exact" + "llvm.org/llgo/third_party/go.tools/go/ssa" + "llvm.org/llgo/third_party/go.tools/go/ssa/ssautil" + "llvm.org/llvm/bindings/go/llvm" +) + +// switchInstr is an instruction representing a switch on constant +// integer values. +type switchInstr struct { + ssa.Instruction + ssautil.Switch +} + +func (sw *switchInstr) String() string { + return sw.Switch.String() +} + +func (sw *switchInstr) Parent() *ssa.Function { + return sw.Default.Instrs[0].Parent() +} + +func (sw *switchInstr) Block() *ssa.BasicBlock { + return sw.Start +} + +func (sw *switchInstr) Operands(rands []*ssa.Value) []*ssa.Value { + return nil +} + +func (sw *switchInstr) Pos() token.Pos { + return token.NoPos +} + +// emitSwitch emits an LLVM switch instruction. +func (fr *frame) emitSwitch(instr *switchInstr) { + cases, _ := dedupConstCases(fr, instr.ConstCases) + ncases := len(cases) + elseblock := fr.block(instr.Default) + llswitch := fr.builder.CreateSwitch(fr.llvmvalue(instr.X), elseblock, ncases) + for _, c := range cases { + llswitch.AddCase(fr.llvmvalue(c.Value), fr.block(c.Body)) + } +} + +// transformSwitches replaces the final If statement in start blocks +// with a high-level switch instruction, and erases chained condition +// blocks. +func (fr *frame) transformSwitches(f *ssa.Function) { + for _, sw := range ssautil.Switches(f) { + if sw.ConstCases == nil { + // TODO(axw) investigate switch + // on hashes in type switches. + continue + } + if !isInteger(sw.X.Type()) && !isBoolean(sw.X.Type()) { + // LLVM switches can only operate on integers. + continue + } + instr := &switchInstr{Switch: sw} + sw.Start.Instrs[len(sw.Start.Instrs)-1] = instr + for _, c := range sw.ConstCases[1:] { + fr.blocks[c.Block.Index].EraseFromParent() + fr.blocks[c.Block.Index] = llvm.BasicBlock{} + } + + // Fix predecessors in successor blocks for fixupPhis. + cases, duplicates := dedupConstCases(fr, instr.ConstCases) + for _, c := range cases { + for _, succ := range c.Block.Succs { + for i, pred := range succ.Preds { + if pred == c.Block { + succ.Preds[i] = sw.Start + break + } + } + } + } + + // Remove redundant edges corresponding to duplicate cases + // that will not feature in the LLVM switch instruction. + for _, c := range duplicates { + for _, succ := range c.Block.Succs { + for i, pred := range succ.Preds { + if pred == c.Block { + head := succ.Preds[:i] + tail := succ.Preds[i+1:] + succ.Preds = append(head, tail...) + removePhiEdge(succ, i) + break + } + } + } + } + } +} + +// dedupConstCases separates duplicate const cases. +// +// TODO(axw) fix this in go/ssa/ssautil. +func dedupConstCases(fr *frame, in []ssautil.ConstCase) (unique, duplicates []ssautil.ConstCase) { + unique = make([]ssautil.ConstCase, 0, len(in)) +dedup: + for i, c1 := range in { + for _, c2 := range in[i+1:] { + if exact.Compare(c1.Value.Value, token.EQL, c2.Value.Value) { + duplicates = append(duplicates, c1) + continue dedup + } + } + unique = append(unique, c1) + } + return unique, duplicates +} + +// removePhiEdge removes the i'th edge from each PHI +// instruction in the specified basic block. +func removePhiEdge(bb *ssa.BasicBlock, i int) { + for _, instr := range bb.Instrs { + instr, ok := instr.(*ssa.Phi) + if !ok { + return + } + head := instr.Edges[:i] + tail := instr.Edges[i+1:] + instr.Edges = append(head, tail...) + } +} diff --git a/llgo/test/irgen/switch.go b/llgo/test/irgen/switch.go new file mode 100644 index 0000000..af05d41 --- /dev/null +++ b/llgo/test/irgen/switch.go @@ -0,0 +1,62 @@ +// RUN: llgo -S -emit-llvm -o - %s | FileCheck %s + +package foo + +// CHECK: switch i32 +// CHECK-NEXT: i32 0, label %[[L0:.*]] +// CHECK-NEXT: i32 1, label %[[L1:.*]] +// CHECK-NEXT: i32 2, label %[[L2:.*]] +// CHECK-NEXT: ] +// CHECK: [[L0]]: +// CHECK-NEXT: ret i32 1 +// CHECK: [[L1]]: +// CHECK-NEXT: ret i32 2 +// CHECK: [[L2]]: +// CHECK-NEXT: ret i32 0 +func F1(x int32) int32 { + switch x { + case 0: + return 1 + case 1: + return 2 + case 2: + return 0 + } + panic("unreachable") +} + +// CHECK: switch i64 +// CHECK-NEXT: i64 0 +// CHECK-NEXT: ] +// CHECK: icmp eq i64 {{.*}}, 1 +func F2(x int64) bool { + return x == 0 || x == 0 || x == 1 +} + +// CHECK: switch i64 +// CHECK-NEXT: i64 0 +// CHECK-NEXT: ] +func F3(x int64) bool { + return x == 0 || x == 0 || x == 0 +} + +// CHECK: switch i64 +// CHECK-NEXT: i64 0 +// CHECK-NEXT: i64 1 +// CHECK-NEXT: i64 2 +// CHECK-NEXT: ] +// CHECK: icmp eq i64 {{.*}}, 3 +func F4(x int64) bool { + return x == 0 || x == 1 || x == 2 || x == 3 +} + +// CHECK-NOT: switch double +func F5(x float64) float64 { + switch x { + case 0: + return 1.0 + case 1.0: + return 0 + } + panic("unreachable") +} -- 2.7.4