loop

Documentation

Overview

Package loop provides utilities for loop representation and detection.

Loop detection works by inspecting the SSA block comments to determine the state of loop, and tracks the transition between the states. Combining the state information and instructions encountered, the loop parameters (e.g. index variable, bounds, increment) are extracted if possible.

A condition graph is built from the transition between short-circuited loop conditions so to reconstruct the loop conditions.

Index

• Variables
• type BinTree
  • func (t *BinTree) FalseString() string
  • func (t *BinTree) SetFalse(c ssa.Value)
  • func (t *BinTree) SetTrue(c ssa.Value)
  • func (t *BinTree) String() string
  • func (t *BinTree) TrueString() string
• type BinTreeVisitor
  • func NewBinTreeVisitor() *BinTreeVisitor
  • func (v *BinTreeVisitor) CalcPrefix()
  • func (v *BinTreeVisitor) VisitRoot(t *BinTree)
• type Detector
  • func NewDetector() *Detector
  • func (d *Detector) Detect(from, to *ssa.BasicBlock)
  • func (d *Detector) ExtractCond(ifelse *ssa.If)
  • func (d *Detector) ExtractIndex(phi *ssa.Phi)
  • func (d *Detector) ForLoopAt(b *ssa.BasicBlock) *Info
  • func (d *Detector) SetLog(w io.Writer)
• type Info
  • func New(index int) *Info
  • func (i *Info) AddFalse(cond ssa.Value)
  • func (i *Info) AddTrue(cond ssa.Value)
  • func (i *Info) BodyIdx() int
  • func (i *Info) DoneIdx() int
  • func (i *Info) MarkTarget()
  • func (i *Info) ParamsOK() bool
  • func (i *Info) SetBodyBlock(index int)
  • func (i *Info) SetCond(cond ssa.Value)
  • func (i *Info) SetDoneBlock(index int)
  • func (i *Info) SetParentCond(prevCond ssa.Value)
  • func (i *Info) String() string
• type Stack
  • func NewStack() *Stack
  • func (s *Stack) IsEmpty() bool
  • func (s *Stack) Pop() (*Info, error)
  • func (s *Stack) Push(i *Info)
• type State

Variables

var ErrEmptyStack = errors.New("error: empty stack")

var ErrIdxNotInt = errors.New("index is not int")

Types

type BinTree

type BinTree struct {
	Cond  ssa.Value
	True  *BinTree
	False *BinTree

	Target bool
	// contains filtered or unexported fields
}

BinTree is a binary tree for conditions.

func (*BinTree) FalseString

func (t *BinTree) FalseString() string

func (*BinTree) SetFalse

func (t *BinTree) SetFalse(c ssa.Value)

func (*BinTree) SetTrue

func (t *BinTree) SetTrue(c ssa.Value)

func (*BinTree) String

func (t *BinTree) String() string

func (*BinTree) TrueString

func (t *BinTree) TrueString() string

type BinTreeVisitor

type BinTreeVisitor struct {
	// contains filtered or unexported fields
}

func NewBinTreeVisitor

func NewBinTreeVisitor() *BinTreeVisitor

func (*BinTreeVisitor) CalcPrefix

func (v *BinTreeVisitor) CalcPrefix()

CalcPrefix propagates all conditions prefix to the 'prefix' so that String() will give the string representation of the whole conditional expression.

func (*BinTreeVisitor) VisitRoot

func (v *BinTreeVisitor) VisitRoot(t *BinTree)

type Detector

type Detector struct {
	// contains filtered or unexported fields
}

func NewDetector

func NewDetector() *Detector

func (*Detector) Detect

func (d *Detector) Detect(from, to *ssa.BasicBlock)

func (*Detector) ExtractCond

func (d *Detector) ExtractCond(ifelse *ssa.If)

func (*Detector) ExtractIndex

func (d *Detector) ExtractIndex(phi *ssa.Phi)

ExtractIndex takes a Phi inside an Enter state work out the initial value and increment.

func (*Detector) ForLoopAt

func (d *Detector) ForLoopAt(b *ssa.BasicBlock) *Info

func (*Detector) SetLog

func (d *Detector) SetLog(w io.Writer)

type Info

type Info struct {
	// contains filtered or unexported fields
}

Info is a data structure to hold loop information, for tracking condition variables, index variable.

func New

func New(index int) *Info

func (*Info) AddFalse

func (i *Info) AddFalse(cond ssa.Value)

func (*Info) AddTrue

func (i *Info) AddTrue(cond ssa.Value)

func (*Info) BodyIdx

func (i *Info) BodyIdx() int

func (*Info) DoneIdx

func (i *Info) DoneIdx() int

func (*Info) MarkTarget

func (i *Info) MarkTarget()

MarkTarget points a part of a loop condition to an existing subtree.

func (*Info) ParamsOK

func (i *Info) ParamsOK() bool

ParamsOK returns true iff both index and cond are detected correctly.

func (*Info) SetBodyBlock

func (i *Info) SetBodyBlock(index int)

SetBodyBlock sets the body block index of the for-loop.

func (*Info) SetCond

func (i *Info) SetCond(cond ssa.Value)

SetCond is used for setting the first (i.e., 'root') condition.

func (*Info) SetDoneBlock

func (i *Info) SetDoneBlock(index int)

SetDoneBlock sets the done block index of the for-loop.

func (*Info) SetParentCond

func (i *Info) SetParentCond(prevCond ssa.Value)

SetParentCond is for adjusting the BinTree so it points to the correct conditional subtree root.

func (*Info) String

func (i *Info) String() string

type Stack

type Stack struct {
	sync.Mutex
	// contains filtered or unexported fields
}

Stack is a stack of ssa.BasicBlock

func NewStack

func NewStack() *Stack

NewStack creates a new LoopStack.

func (*Stack) IsEmpty

func (s *Stack) IsEmpty() bool

IsEmpty returns true if stack is empty.

func (*Stack) Pop

func (s *Stack) Pop() (*Info, error)

Pop removes a Loop from top of stack.

func (*Stack) Push

func (s *Stack) Push(i *Info)

Push adds a new Info to the top of stack.

type State

type State int

State is the loop transition states.

const (
	NonLoop State = iota
	Enter
	CondTrue  // CondTrue is an extension of Enter for complex conditions
	CondFalse // CondFalse is an extensions of Enter for complex conditions
	Body
	Exit
)