flows.dl

#pragma once
#include "dominators.dl"

//
// *** Data flow and dependency analysis ***
//

.comp GlobalFlowAnalysis {
  // Inputs
  .decl TransferStmt(stmt: Statement)
  .decl InitialFlowVar(var: Variable)
  .decl TransferBoundary(block: Block)

  .decl Uses(stmt: Statement, use: Variable) overridable
  .decl Defines(stmt: Statement, def: Variable) overridable

  // Intermediate
  .decl FlowsBase(from: Variable, to: Variable)
  .decl VarOfInterest(var: Variable)

  // Outputs
  .decl Flows(from: Variable, to: Variable)

  Uses(stmt, use):-
    Statement_Uses(stmt, use, _).

  Defines(stmt, def):-
    Statement_Defines(stmt, def, _).

  VarOfInterest(var) :-
    Flows(_, var).

  // Although FlowsBase is mutually recursive with Flows, it represents an attempt to break
  // up the transitive closure into smaller relations, so that the same final tuples aren't
  // computed in many different ways.
  FlowsBase(x, x) :- InitialFlowVar(x).

  //   Flows(x, y) :- Flows(_, x), PHI(_, x, y).
  /// This is commented out on purpose and will be eliminated later!
  /// Please don't put it back in without consulting--it will break
  /// the type inference client. It will make no difference for most
  /// other clients, since their TransferOpcodes include PHIs anyway.

  FlowsBase(x, y) :-
    VarOfInterest(x),
    Uses(stmt, x),
    Defines(stmt, y),
    TransferStmt(stmt),
    Statement_Block(stmt, block),
    TransferBoundary(block).

  // Case: Flows from formal to formal return
  FlowsBase(actual, actualReturn) :-
    FunctionFlowSummary(fn, formal, m),
    FunctionCallReturn(block, fn, _),
    FormalArgs(fn, formal, n),
    ActualArgs(block, actual, n),
    ActualReturnArgs(block, actualReturn, m),
    TransferBoundary(block).
   
  // Case: Flows from local variable to formal return
  FlowsBase(variable, actualReturn) :-
    FunctionFlowSummary(fn, variable, m),
    FunctionCallReturn(block, fn, _),
    !FormalArgs(fn, variable, _),
    ActualReturnArgs(block, actualReturn, m),
    TransferBoundary(block).

  // Recursive Case
  Flows(x, y) :-
    FlowsBase(x, y).
     
  Flows(x, z) :-
    Flows(x, y),
    FlowsBase(y, z).
   .plan 1:(2,1)
      
   
  // Flows from variable to return argument
  .decl FunctionFlowSummary(fn: Function, from:Variable, n:number)
   
  // Flow from local or formal to formal return
  FunctionFlowSummary(fn, from, n) :-
    Flows(from, to),
    FormalReturnArgs(fn, to, n).

  .decl InterFunctionActualArgFlow(actual:Variable, formal:Variable)

  InterFunctionActualArgFlow(actual, inFunctionVar):-
    ActualArgs(caller, actual, n),
    TransferBoundary(caller),
    CallGraphEdge(caller, fn),
    FormalArgs(fn, formal, n),
    Flows(formal, inFunctionVar),
    Variable_Function(inFunctionVar, fn). // Make it local. Global transitivity restored later with separate rule.

   
  // Case: flow within the same function, or back to local
   
  .decl GlobalFlows(from:Variable, to:Variable)
  GlobalFlows(x, y) :- Flows(x, y).
   
  // Case: forward inter-procedural assignment only
  GlobalFlows(from, to) :-
    GlobalFlows(from, actual),
    InterFunctionActualArgFlow(actual, to).

  GlobalFlows(from, to) :-
    GlobalFlows(from, interm),
    FlowsBase(interm, to).

}

.init standardflowanalysis = GlobalFlowAnalysis
standardflowanalysis.TransferStmt(stmt) :- FlowOp(op), Statement_Opcode(stmt, op).
standardflowanalysis.InitialFlowVar(v) :- isVariable(v).
standardflowanalysis.TransferBoundary(b) :- IsBlock(b).

#define DataFlows standardflowanalysis.GlobalFlows

.init constantOpFlows = GlobalFlowAnalysis
constantOpFlows.TransferStmt(stmt):-
  UnaryArith(op),
  Statement_Opcode(stmt, op).

constantOpFlows.TransferStmt(stmt):-
  BinArith(op),
  Statement_Opcode(stmt, op),
  Statement_Uses(stmt, var, _),
  Variable_Value(var, _). // Maybe replace with BasicVariable_Value

constantOpFlows.TransferStmt(stmt):-
  Statement_Opcode(stmt, "PHI").

constantOpFlows.InitialFlowVar(v):- isVariable(v).
constantOpFlows.TransferBoundary(b):- IsBlock(b).

#define DataFlowsThroughConstOps constantOpFlows.GlobalFlows

// Need a custom data flow analysis? Of course you do!
// Initialise this component and indicate with opcodes to use as transfer functions.
// Also indicate the transfer boundary (e.g. Loop blocks for induction variables)
.comp LocalFlowAnalysis {
  .decl TransferStmt(stmt: Statement)
  .decl TransferBoundary(block: Block)

  .decl Uses(stmt: Statement, use: Variable) overridable
  .decl Defines(stmt: Statement, def: Variable) overridable

  // Output
  .decl Flows(x: Variable, y: Variable)
  .decl NonTransitiveFlows(x: Variable, y: Variable)

  Uses(stmt, use):-
    Statement_Uses(stmt, use, _).

  Defines(stmt, def):-
    Statement_Defines(stmt, def, _).


  NonTransitiveFlows(x, x),
  Flows(x, x) :- isVariable(x).

  // NonTransitiveFlows(x, y),
  // Flows(x, y) :-
  //   TransferOpcodeArgument(op, n),
  //   Statement_Opcode(stmt, op),
  //   Statement_Block(stmt, block),
  //   TransferBoundary(block),
  //   Defines(stmt, y, _),
  //   Uses(stmt, x, n).
  
  NonTransitiveFlows(x, y),
  Flows(x, y) :-
    TransferStmt(stmt),
    Statement_Block(stmt, block),
    TransferBoundary(block),
    Defines(stmt, y),
    Uses(stmt, x).

  // Case: Flows from formal to formal return
  NonTransitiveFlows(actual, actualReturn),
  Flows(actual, actualReturn) :-
    FunctionFlowSummary(fn, formal, m),
    FunctionCallReturn(block, fn, _),
    FormalArgs(fn, formal, n),
    ActualArgs(block, actual, n),
    ActualReturnArgs(block, actualReturn, m),
    TransferBoundary(block).

    // Flows from variable to return argument
   .decl FunctionFlowSummary(fn: Function, from:Variable, n:number)

   // Flow from local or formal to formal return
   FunctionFlowSummary(fn, from, n) :-
      Flows(from, to),
      FormalReturnArgs(fn, to, n).

  Flows(x, z) :-
    Flows(x, y),
    Flows(y, z).
    .plan 1:(2,1)

  // SL: Why is this here? remove it?
  .decl TransferOpcodeArgument(op: Opcode, argument: number)
  TransferOpcodeArgument(op, n) :- TransferOpcodeArgument(op, n). // suppress warning
}

// Note that this is an inter-procedural analysis with no context sensitivity
// The value of x depends on the value of y
// I.e. y is used to calculate x, either directly as an input of the operation
// that defined x, or transitively.
.init dependencyAnalysis = LocalFlowAnalysis

dependencyAnalysis.TransferStmt(stmt) :- Statement_Opcode(stmt, _).
dependencyAnalysis.TransferBoundary(block) :- IsBlock(block).

#define DependsOn dependencyAnalysis.Flows

.init localFlowAnalysis = LocalFlowAnalysis

localFlowAnalysis.TransferStmt(stmt) :- FlowOp(op), Statement_Opcode(stmt, op).
localFlowAnalysis.TransferBoundary(block) :- IsBlock(block).

#define LocalFlows localFlowAnalysis.Flows

/**
  Local flows excluding PHIs
  To be used when more precise, local inferrences are needed
*/
.init altLocalFlowAnalysis = LocalFlowAnalysis

altLocalFlowAnalysis.TransferStmt(stmt) :- FlowOp(op), Statement_Opcode(stmt, op), op != "PHI".
altLocalFlowAnalysis.TransferBoundary(block) :- IsBlock(block).

#define LocalFlowsExclPHI altLocalFlowAnalysis.Flows

// x controls whether y is executed.
.decl Controls(x:Statement, y:Block)

.decl DecisionEdge(jmpi: Statement, w1: Block, w2: Block)

DecisionEdge(jmpi, w1, w2) :-
  LocalBlockEdge(x, w1),
  FallthroughEdge(x, w2),
  w1 != w2,
  Block_Tail(x, jmpi),
  JUMPI(jmpi, _, _).

Controls(jmpi, y) :-
  (DecisionEdge(jmpi, w1, w2) ; DecisionEdge(jmpi, w2, w1)),
  Dominates(w2, y),
  !Dominates(w1, y).

Controls(x, z) :- Controls(x, y), Statement_Block(yjmp, y), Controls(yjmp, z). // Transitivity

// var is the guard variable of some conditional jump or throw stmt
.decl ConditionVar(var: Variable, stmt:Statement)
ConditionVar(var, stmt) :- JUMPI(stmt, _, var).

// x controls whether y executes by the value in condVar
.decl ControlsWith(x:Statement, y:Block, condVar:Variable)
ControlsWith(x, yHead, condVar) :-
  Controls(x, yHead),
  ConditionVar(condVar, x).

.decl ThrowBlock(block: Block)

ThrowBlock(revertblock) :-
   Block_Tail(revertblock, revert),
   (THROW(revert) ; REVERT(revert, _, _)).

.decl NonLinearEdge(block: Block)

NonLinearEdge(block) :-
   GlobalBlockEdge(block, next),
   GlobalBlockEdge(block, next2),
   next2 != next.
   
ThrowBlock(block) :-
   GlobalBlockEdge(block, next),
   !NonLinearEdge(block),
   ThrowBlock(next).

.decl AddResult(b: Variable, d: Variable)

AddResult(b, d) :-
   (ADD(_, b, c, d) ; ADD(_, c, b, d)),
   !NOT(_, _, c).   

// calls
.decl CallSuccessControlsException(callStmt:Statement, throwStmt: Statement)
// The return value of a call (callStmt) controls
// whether an exception is thrown by throwStmt
// Either through a control dependency        
CallSuccessControlsException(callStmt, throwStmt) :-
  CallResult(resVar, callStmt),
  DataFlows(resVar, condVar),
  JUMPI(throwStmt, _, condVar),
  ControlsWith(_, throwBlock, condVar),
  ThrowBlock(throwBlock).

.decl CallFailureControls(call: Statement, to: Block)

CallFailureControls(call, to) :-
   CallResult(res, call),
   ISZERO(_, res, notres),
   JUMPI(jmp, _, notres),
   Statement_Block(jmp, from),
   LocalBlockEdge(from, to),
   !FallthroughEdge(from, to).

CallFailureControls(call, to) :-
   CallResult(res, call),
   JUMPI(jmp, _, res),
   Statement_Block(jmp, from),
   FallthroughEdge(from, to).

CallFailureControls(call, to) :-
   CallFailureControls(call, from),
   Dominates(from, to).