Safe Haskell	None
Language	Haskell2010

Data.Macaw.Analysis.RegisterUse

Contents

Exports for function recovery
- Input information
Architecture specific summarization
- FunPredMap
- Inferred information.
  - Mem Access info
  - Use information

Description

This analyzes a Macaw function to compute information about what information must be available for the code to execute. It is a key analysis task needed before deleting unused code.

Synopsis

registerUse :: ArchConstraints arch => RegisterUseContext arch -> DiscoveryFunInfo arch ids -> Except (RegisterUseError arch) (BlockInvariantMap arch ids)
type BlockInvariantMap arch ids = Map (ArchSegmentOff arch) (BlockInvariants arch ids)
data RegisterUseError arch = RegisterUseError {
- ruBlock :: !(ArchSegmentOff arch)
- ruStmt :: !StmtIndex
- ruReason :: !RegisterUseErrorReason
}
data RegisterUseErrorReason = Reason !(RegisterUseErrorTag e) !e
ppRegisterUseErrorReason :: RegisterUseErrorReason -> String
data RegisterUseErrorTag e where
- CallStackHeightError :: RegisterUseErrorTag ()
- UnresolvedStackRead :: RegisterUseErrorTag ()
- UnsupportedCondStackRead :: RegisterUseErrorTag ()
- IndirectCallTarget :: RegisterUseErrorTag ()
- InvalidCallTargetAddress :: RegisterUseErrorTag Word64
- CallTargetNotFunctionEntryPoint :: RegisterUseErrorTag Word64
- UnknownCallTargetArguments :: RegisterUseErrorTag ByteString
- ResolutonFailureCallToKnownVarArgsFunction :: RegisterUseErrorTag [Char]
- UnsupportedCallTargetCallingConvention :: RegisterUseErrorTag ByteString
data RegisterUseContext arch = RegisterUseContext {
- archCallParams :: !(CallParams (ArchReg arch))
- archPostTermStmtInvariants :: !(forall ids. PostTermStmtInvariants arch ids)
- calleeSavedRegisters :: ![Some (ArchReg arch)]
- callScratchRegisters :: ![Some (ArchReg arch)]
- returnRegisters :: ![Some (ArchReg arch)]
- reguseTermFn :: !(forall ids. ArchTermStmtUsageFn arch ids)
- callDemandFn :: !(forall ids. ArchSegmentOff arch -> RegState (ArchReg arch) (Value arch ids) -> Either RegisterUseErrorReason (CallRegs arch ids))
- demandContext :: !(DemandContext arch)
}
type family ArchFunType arch
data CallRegs arch ids = CallRegs {
- callRegsFnType :: !(ArchFunType arch)
- callArgValues :: [Some (Value arch ids)]
- callReturnRegs :: [Some (ArchReg arch)]
}
type PostTermStmtInvariants arch ids = StartInferContext arch -> InferState arch ids -> Int -> ArchTermStmt arch (Value arch ids) -> RegState (ArchReg arch) (Value arch ids) -> Either (RegisterUseError arch) (PostValueMap arch ids, BlockStartConstraints arch)
data PostValueMap arch ids
pvmFind :: forall arch (tp :: Type) ids. OrdF (ArchReg arch) => BoundLoc (ArchReg arch) tp -> PostValueMap arch ids -> BlockInferValue arch ids tp
data MemSlice (wtp :: Type) (rtp :: Type) where
- NoMemSlice :: forall (wtp :: Type). MemSlice wtp wtp
- MemSlice :: forall (wtp :: Type) (rtp :: Type). !Integer -> !(MemRepr wtp) -> !(MemRepr rtp) -> MemSlice wtp rtp
type ArchTermStmtUsageFn arch ids = ArchTermStmt arch (Value arch ids) -> RegState (ArchReg arch) (Value arch ids) -> BlockUsageSummary arch ids -> Either (RegisterUseError arch) (RegDependencyMap arch ids)
type RegisterUseM arch ids = ReaderT (RegisterUseContext arch) (StateT (BlockUsageSummary arch ids) (Except (RegisterUseError arch)))
newtype BlockStartConstraints arch = BSC {
- bscLocMap :: LocMap (ArchReg arch) (InitInferValue arch)
}
locDomain :: forall arch (tp :: Type). (MemWidth (ArchAddrWidth arch), OrdF (ArchReg arch)) => BlockStartConstraints arch -> BoundLoc (ArchReg arch) tp -> InitInferValue arch tp
postCallConstraints :: ArchConstraints arch => CallParams (ArchReg arch) -> StartInferContext arch -> InferState arch ids -> Int -> RegState (ArchReg arch) (Value arch ids) -> Either (RegisterUseError arch) (PostValueMap arch ids, BlockStartConstraints arch)
data BlockUsageSummary arch ids = BUS {
- blockUsageStartConstraints :: !(BlockStartConstraints arch)
- blockCurOff :: !(ArchAddrWord arch)
- blockInferState :: !(InferState arch ids)
- _blockExecDemands :: !(DependencySet (ArchReg arch) ids)
- blockRegDependencies :: !(RegDependencyMap arch ids)
- blockWriteDependencies :: !(Map StmtIndex (DependencySet (ArchReg arch) ids))
- assignDeps :: !(Map (Some (AssignId ids)) (DependencySet (ArchReg arch) ids))
- pendingMemAccesses :: ![(StmtIndex, MemAccessInfo arch ids)]
- blockCallFunType :: !(Maybe (ArchFunType arch))
}
data RegDependencyMap arch ids
setRegDep :: forall arch (tp :: Type) ids. OrdF (ArchReg arch) => ArchReg arch tp -> DependencySet (ArchReg arch) ids -> RegDependencyMap arch ids -> RegDependencyMap arch ids
data StartInferContext arch
data InferState arch ids
data BlockInferValue arch ids (tp :: Type) where
- IVDomain :: forall arch (wtp :: Type) (tp :: Type) ids. !(InitInferValue arch wtp) -> !(MemSlice wtp tp) -> BlockInferValue arch ids tp
- IVAssignValue :: forall ids (tp :: Type) arch. !(AssignId ids tp) -> BlockInferValue arch ids tp
- IVCValue :: forall arch (tp :: Type) ids. !(CValue arch tp) -> BlockInferValue arch ids tp
- IVCondWrite :: forall (tp :: Type) arch ids. !StmtIndex -> !(MemRepr tp) -> BlockInferValue arch ids tp
valueDeps :: forall arch ids (tp :: Type). (HasCallStack, MemWidth (ArchAddrWidth arch), OrdF (ArchReg arch)) => BlockStartConstraints arch -> Map (Some (AssignId ids)) (DependencySet (ArchReg arch) ids) -> Value arch ids tp -> DependencySet (ArchReg arch) ids
type FunPredMap (w :: Nat) = Map (MemSegmentOff w) [MemSegmentOff w]
funBlockPreds :: DiscoveryFunInfo arch ids -> FunPredMap (ArchAddrWidth arch)
data BlockInvariants arch ids
biStartConstraints :: BlockInvariants arch ids -> BlockStartConstraints arch
biMemAccessList :: BlockInvariants arch ids -> [(StmtIndex, MemAccessInfo arch ids)]
biPhiLocs :: BlockInvariants arch ids -> [Some (BoundLoc (ArchReg arch))]
biPredPostValues :: BlockInvariants arch ids -> Map (ArchSegmentOff arch) (PostValueMap arch ids)
biLocMap :: BlockInvariants arch ids -> MapF (BoundLoc (ArchReg arch)) (LocList (ArchReg arch))
biCallFunType :: BlockInvariants arch ids -> Maybe (ArchFunType arch)
biAssignMap :: BlockInvariants arch ids -> MapF (AssignId ids) (BlockInferValue arch ids)
newtype LocList (r :: Type -> Type) (tp :: Type) = LL {
- llValues :: [BoundLoc r tp]
}
data LocMap (r :: Type -> Type) (v :: Type -> Type) = LocMap {
- locMapRegs :: !(MapF r v)
- locMapStack :: !(MemMap (MemInt (RegAddrWidth r)) v)
}
locMapToList :: forall (r :: Type -> Type) (v :: Type -> Type). LocMap r v -> [Pair (BoundLoc r) v]
data BoundLoc (r :: Type -> Type) (tp :: Type) where
- RegLoc :: forall (r :: Type -> Type) (tp :: Type). !(r tp) -> BoundLoc r tp
- StackOffLoc :: forall (r :: Type -> Type) (tp :: Type). !(MemInt (RegAddrWidth r)) -> !(MemRepr tp) -> BoundLoc r tp
data MemAccessInfo arch ids
- = NotFrameAccess
- | FrameReadInitAccess !(MemInt (ArchAddrWidth arch)) !(InitInferValue arch tp)
- | FrameReadWriteAccess !StmtIndex
- | FrameReadOverlapAccess !(MemInt (ArchAddrWidth arch))
- | FrameWriteAccess !(MemInt (ArchAddrWidth arch))
- | FrameCondWriteAccess !(MemInt (ArchAddrWidth arch)) !(MemRepr tp) !(InferStackValue arch ids tp)
- | FrameCondWriteOverlapAccess !(MemInt (ArchAddrWidth arch))
data InitInferValue arch (tp :: Type) where
- InferredStackOffset :: forall arch. !(MemInt (ArchAddrWidth arch)) -> InitInferValue arch ('BVType (ArchAddrWidth arch))
- FnStartRegister :: forall arch (tp :: Type). !(ArchReg arch tp) -> InitInferValue arch tp
- RegEqualLoc :: forall arch (tp :: Type). !(BoundLoc (ArchReg arch) tp) -> InitInferValue arch tp
type StmtIndex = Int
biAssignIdUsed :: forall ids (tp :: Type) arch. AssignId ids tp -> BlockInvariants arch ids -> Bool
biWriteUsed :: StmtIndex -> BlockInvariants arch ids -> Bool

Exports for function recovery

registerUse :: ArchConstraints arch => RegisterUseContext arch -> DiscoveryFunInfo arch ids -> Except (RegisterUseError arch) (BlockInvariantMap arch ids) Source #

This analyzes a function to determine which registers must be available to the highest index above sp0 that is read or written.

type BlockInvariantMap arch ids = Map (ArchSegmentOff arch) (BlockInvariants arch ids) Source #

Map from block starting addresses to the invariants inferred for that block.

data RegisterUseError arch Source #

Errors from register use

Constructors

RegisterUseError
Fields ruBlock :: !(ArchSegmentOff arch) ruStmt :: !StmtIndex ruReason :: !RegisterUseErrorReason

data RegisterUseErrorReason Source #

Constructors

Reason !(RegisterUseErrorTag e) !e

ppRegisterUseErrorReason :: RegisterUseErrorReason -> String Source #

data RegisterUseErrorTag e where Source #

Errors from register use

Tag parameter used for addition information in tag

Constructors

CallStackHeightError :: RegisterUseErrorTag ()	Could not resolve height of call stack at given block
UnresolvedStackRead :: RegisterUseErrorTag ()	The value read at given block and statement index could not be resolved.
UnsupportedCondStackRead :: RegisterUseErrorTag ()	We do not have support for stack reads.
IndirectCallTarget :: RegisterUseErrorTag ()	Call with indirect target
InvalidCallTargetAddress :: RegisterUseErrorTag Word64	Call target address was not a valid memory location.
CallTargetNotFunctionEntryPoint :: RegisterUseErrorTag Word64	Call target was not a known function.
UnknownCallTargetArguments :: RegisterUseErrorTag ByteString	Could not determine arguments to call.
ResolutonFailureCallToKnownVarArgsFunction :: RegisterUseErrorTag [Char]	We could not resolve the arguments to a known var-args function.
UnsupportedCallTargetCallingConvention :: RegisterUseErrorTag ByteString	We do not yet support the calling convention needed for this function.

Instances

Instances details

TestEquality RegisterUseErrorTag Source #
Instance details Defined in Data.Macaw.Analysis.RegisterUse Methods testEquality :: RegisterUseErrorTag a -> RegisterUseErrorTag b -> Maybe (a :~: b) #
OrdF RegisterUseErrorTag Source #
Instance details Defined in Data.Macaw.Analysis.RegisterUse Methods compareF :: RegisterUseErrorTag x -> RegisterUseErrorTag y -> OrderingF x y leqF :: RegisterUseErrorTag x -> RegisterUseErrorTag y -> Bool ltF :: RegisterUseErrorTag x -> RegisterUseErrorTag y -> Bool geqF :: RegisterUseErrorTag x -> RegisterUseErrorTag y -> Bool gtF :: RegisterUseErrorTag x -> RegisterUseErrorTag y -> Bool
Show (RegisterUseErrorTag e) Source #
Instance details Defined in Data.Macaw.Analysis.RegisterUse Methods showsPrec :: Int -> RegisterUseErrorTag e -> ShowS # show :: RegisterUseErrorTag e -> String # showList :: [RegisterUseErrorTag e] -> ShowS #

Input information

data RegisterUseContext arch Source #

Constructors

RegisterUseContext

Fields

archCallParams :: !(CallParams (ArchReg arch))
Set of registers preserved by a call.
archPostTermStmtInvariants :: !(forall ids. PostTermStmtInvariants arch ids)
Given a terminal statement and list of registers it returns Map containing values afterwards.
calleeSavedRegisters :: ![Some (ArchReg arch)]
Registers that are saved by calls (excludes rsp)
callScratchRegisters :: ![Some (ArchReg arch)]
List of registers that callers may freely change.
returnRegisters :: ![Some (ArchReg arch)]
reguseTermFn :: !(forall ids. ArchTermStmtUsageFn arch ids)
Callback function for summarizing register usage of terminal statements.
callDemandFn :: !(forall ids. ArchSegmentOff arch -> RegState (ArchReg arch) (Value arch ids) -> Either RegisterUseErrorReason (CallRegs arch ids))
Given the address of a call instruction and registers, this returns the values read and returned.
demandContext :: !(DemandContext arch)
Information needed to demands of architecture-specific functions.

type family ArchFunType arch Source #

Architecture specific information about the type of function called by inferring call-site information.

Used to memoize analysis returned by callDemandFn.

data CallRegs arch ids Source #

Identifies demand information about a particular call.

Constructors

CallRegs
Fields callRegsFnType :: !(ArchFunType arch) callArgValues :: [Some (Value arch ids)] callReturnRegs :: [Some (ArchReg arch)]

type PostTermStmtInvariants arch ids = StartInferContext arch -> InferState arch ids -> Int -> ArchTermStmt arch (Value arch ids) -> RegState (ArchReg arch) (Value arch ids) -> Either (RegisterUseError arch) (PostValueMap arch ids, BlockStartConstraints arch) Source #

data PostValueMap arch ids Source #

Maps locations to the values to initialize next locations with.

Instances

Instances details

ShowF (ArchReg arch) => Show (PostValueMap arch ids) Source #
Instance details Defined in Data.Macaw.Analysis.RegisterUse Methods showsPrec :: Int -> PostValueMap arch ids -> ShowS # show :: PostValueMap arch ids -> String # showList :: [PostValueMap arch ids] -> ShowS #

pvmFind :: forall arch (tp :: Type) ids. OrdF (ArchReg arch) => BoundLoc (ArchReg arch) tp -> PostValueMap arch ids -> BlockInferValue arch ids tp Source #

data MemSlice (wtp :: Type) (rtp :: Type) where Source #

This is used to to control which parts of a value we need to read.

Constructors

NoMemSlice :: forall (wtp :: Type). MemSlice wtp wtp
MemSlice	`MemSlize o w r` indicates that we read a value of type `r` `o` bytes into the write of type `w`.
Fields :: forall (wtp :: Type) (rtp :: Type). !Integer Offset of read relative to write. -> !(MemRepr wtp) Write repr -> !(MemRepr rtp) Read repr -> MemSlice wtp rtp

Instances

Instances details

TestEquality (MemSlice wtp :: Type -> Type) Source #
Instance details Defined in Data.Macaw.Analysis.RegisterUse Methods testEquality :: forall (a :: Type) (b :: Type). MemSlice wtp a -> MemSlice wtp b -> Maybe (a :~: b) #
OrdF (MemSlice wtp :: Type -> Type) Source #
Instance details Defined in Data.Macaw.Analysis.RegisterUse Methods compareF :: forall (x :: Type) (y :: Type). MemSlice wtp x -> MemSlice wtp y -> OrderingF x y leqF :: forall (x :: Type) (y :: Type). MemSlice wtp x -> MemSlice wtp y -> Bool ltF :: forall (x :: Type) (y :: Type). MemSlice wtp x -> MemSlice wtp y -> Bool geqF :: forall (x :: Type) (y :: Type). MemSlice wtp x -> MemSlice wtp y -> Bool gtF :: forall (x :: Type) (y :: Type). MemSlice wtp x -> MemSlice wtp y -> Bool
Show (MemSlice w r) Source #
Instance details Defined in Data.Macaw.Analysis.RegisterUse Methods showsPrec :: Int -> MemSlice w r -> ShowS # show :: MemSlice w r -> String # showList :: [MemSlice w r] -> ShowS #

Architecture specific summarization

type ArchTermStmtUsageFn arch ids = ArchTermStmt arch (Value arch ids) -> RegState (ArchReg arch) (Value arch ids) -> BlockUsageSummary arch ids -> Either (RegisterUseError arch) (RegDependencyMap arch ids) Source #

type RegisterUseM arch ids = ReaderT (RegisterUseContext arch) (StateT (BlockUsageSummary arch ids) (Except (RegisterUseError arch))) Source #

newtype BlockStartConstraints arch Source #

This maps r registers and stack offsets at start of block to inferred information about their value.

If a register or stack location does not appear here, it is implicitly set to itself.

Constructors

BSC
Fields bscLocMap :: LocMap (ArchReg arch) (InitInferValue arch)

locDomain :: forall arch (tp :: Type). (MemWidth (ArchAddrWidth arch), OrdF (ArchReg arch)) => BlockStartConstraints arch -> BoundLoc (ArchReg arch) tp -> InitInferValue arch tp Source #

Return domain for location in constraints

postCallConstraints Source #

Arguments

:: ArchConstraints arch
=> CallParams (ArchReg arch)	Architecture-specific call parameters
-> StartInferContext arch	Context for block invariants inference.
-> InferState arch ids	State for start inference
-> Int	Index of term statement
-> RegState (ArchReg arch) (Value arch ids)	Registers at time of call.
-> Either (RegisterUseError arch) (PostValueMap arch ids, BlockStartConstraints arch)

Post call constraints for return address.

data BlockUsageSummary arch ids Source #

This contains information about a specific block needed to infer which locations and assignments are needed to execute the block along with information about the demands to compute the value of particular locations after the block executes.

Constructors

BUS

Fields

blockUsageStartConstraints :: !(BlockStartConstraints arch)
blockCurOff :: !(ArchAddrWord arch)
Offset of start of last instruction processed relative to start of block.
blockInferState :: !(InferState arch ids)
Inferred state computed at beginning
_blockExecDemands :: !(DependencySet (ArchReg arch) ids)
Dependencies needed to execute statements with side effects.
blockRegDependencies :: !(RegDependencyMap arch ids)
Map registers to the dependencies of the values they store.
Defined in block terminator.
blockWriteDependencies :: !(Map StmtIndex (DependencySet (ArchReg arch) ids))
Map indexes of writes and cond write instructions to their dependency set.
assignDeps :: !(Map (Some (AssignId ids)) (DependencySet (ArchReg arch) ids))
Maps assignments to their dependencies.
pendingMemAccesses :: ![(StmtIndex, MemAccessInfo arch ids)]
Information about next memory reads.
blockCallFunType :: !(Maybe (ArchFunType arch))
If this block ends with a call, this has the type of the function called. Otherwise, the value should be Nothing.

data RegDependencyMap arch ids Source #

Map from register to the dependencies for that register.

Instances

Instances details

OrdF (ArchReg arch) => Monoid (RegDependencyMap arch ids) Source #
Instance details Defined in Data.Macaw.Analysis.RegisterUse Methods mempty :: RegDependencyMap arch ids # mappend :: RegDependencyMap arch ids -> RegDependencyMap arch ids -> RegDependencyMap arch ids # mconcat :: [RegDependencyMap arch ids] -> RegDependencyMap arch ids #
OrdF (ArchReg arch) => Semigroup (RegDependencyMap arch ids) Source #
Instance details Defined in Data.Macaw.Analysis.RegisterUse Methods (<>) :: RegDependencyMap arch ids -> RegDependencyMap arch ids -> RegDependencyMap arch ids # sconcat :: NonEmpty (RegDependencyMap arch ids) -> RegDependencyMap arch ids # stimes :: Integral b => b -> RegDependencyMap arch ids -> RegDependencyMap arch ids #

setRegDep :: forall arch (tp :: Type) ids. OrdF (ArchReg arch) => ArchReg arch tp -> DependencySet (ArchReg arch) ids -> RegDependencyMap arch ids -> RegDependencyMap arch ids Source #

Set dependency for register

data StartInferContext arch Source #

Read-only information needed to infer successor start constraints for a lbok.

Instances

Instances details

(ShowF (ArchReg arch), MemWidth (ArchAddrWidth arch)) => Show (StartInferContext arch) Source #
Instance details Defined in Data.Macaw.Analysis.RegisterUse Methods showsPrec :: Int -> StartInferContext arch -> ShowS # show :: StartInferContext arch -> String # showList :: [StartInferContext arch] -> ShowS #

data InferState arch ids Source #

State tracked to infer block preconditions.

data BlockInferValue arch ids (tp :: Type) where Source #

This is an expression that represents a more canonical representation of a Macaw value inferred by the invariant inference routine.

This difference between InitInferValue and BlockInferValue is that InitInferValue captures constraints important to capture between blocks while BlockInferValue has a richer constraint language capturing inferrences within a block.

Constructors

IVDomain :: forall arch (wtp :: Type) (tp :: Type) ids. !(InitInferValue arch wtp) -> !(MemSlice wtp tp) -> BlockInferValue arch ids tp	Value register use domain
IVAssignValue :: forall ids (tp :: Type) arch. !(AssignId ids tp) -> BlockInferValue arch ids tp	The value of an assignment.
IVCValue :: forall arch (tp :: Type) ids. !(CValue arch tp) -> BlockInferValue arch ids tp	A constant
IVCondWrite :: forall (tp :: Type) arch ids. !StmtIndex -> !(MemRepr tp) -> BlockInferValue arch ids tp	Denotes the value written by a conditional write at the given index if the condition is true, or the value currently stored in memory if the condition is false. The MemRepr is the type of the write, and used for comparison.

Instances

Instances details

TestEquality (ArchReg arch) => TestEquality (BlockInferValue arch ids :: Type -> Type) Source #
Instance details Defined in Data.Macaw.Analysis.RegisterUse Methods testEquality :: forall (a :: Type) (b :: Type). BlockInferValue arch ids a -> BlockInferValue arch ids b -> Maybe (a :~: b) #
OrdF (ArchReg arch) => OrdF (BlockInferValue arch ids :: Type -> Type) Source #
Instance details Defined in Data.Macaw.Analysis.RegisterUse Methods compareF :: forall (x :: Type) (y :: Type). BlockInferValue arch ids x -> BlockInferValue arch ids y -> OrderingF x y leqF :: forall (x :: Type) (y :: Type). BlockInferValue arch ids x -> BlockInferValue arch ids y -> Bool ltF :: forall (x :: Type) (y :: Type). BlockInferValue arch ids x -> BlockInferValue arch ids y -> Bool geqF :: forall (x :: Type) (y :: Type). BlockInferValue arch ids x -> BlockInferValue arch ids y -> Bool gtF :: forall (x :: Type) (y :: Type). BlockInferValue arch ids x -> BlockInferValue arch ids y -> Bool
ShowF (ArchReg arch) => ShowF (BlockInferValue arch ids :: Type -> Type) Source #
Instance details Defined in Data.Macaw.Analysis.RegisterUse Methods withShow :: forall p q (tp :: Type) a. p (BlockInferValue arch ids) -> q tp -> (Show (BlockInferValue arch ids tp) => a) -> a showF :: forall (tp :: Type). BlockInferValue arch ids tp -> String showsPrecF :: forall (tp :: Type). Int -> BlockInferValue arch ids tp -> String -> String
ShowF (ArchReg arch) => Show (BlockInferValue arch ids tp) Source #
Instance details Defined in Data.Macaw.Analysis.RegisterUse Methods showsPrec :: Int -> BlockInferValue arch ids tp -> ShowS # show :: BlockInferValue arch ids tp -> String # showList :: [BlockInferValue arch ids tp] -> ShowS #

valueDeps :: forall arch ids (tp :: Type). (HasCallStack, MemWidth (ArchAddrWidth arch), OrdF (ArchReg arch)) => BlockStartConstraints arch -> Map (Some (AssignId ids)) (DependencySet (ArchReg arch) ids) -> Value arch ids tp -> DependencySet (ArchReg arch) ids Source #

Return the register and assignment dependencies needed to

FunPredMap

type FunPredMap (w :: Nat) = Map (MemSegmentOff w) [MemSegmentOff w] Source #

A map from each starting block address l to the addresses of blocks that may jump to l.

funBlockPreds :: DiscoveryFunInfo arch ids -> FunPredMap (ArchAddrWidth arch) Source #

Return the FunPredMap for the discovered block function.

Inferred information.

data BlockInvariants arch ids Source #

This describes information about a block inferred by register-use.

biStartConstraints :: BlockInvariants arch ids -> BlockStartConstraints arch Source #

Start constraints for block

biMemAccessList :: BlockInvariants arch ids -> [(StmtIndex, MemAccessInfo arch ids)] Source #

In-order list of memory accesses in block.

biPhiLocs :: BlockInvariants arch ids -> [Some (BoundLoc (ArchReg arch))] Source #

Locations from previous block used to initial phi variables.

biPredPostValues :: BlockInvariants arch ids -> Map (ArchSegmentOff arch) (PostValueMap arch ids) Source #

Map predecessors for this block along with map from locations to phi value

biLocMap :: BlockInvariants arch ids -> MapF (BoundLoc (ArchReg arch)) (LocList (ArchReg arch)) Source #

Map from locations to the non-representative locations that are equal to them.

biCallFunType :: BlockInvariants arch ids -> Maybe (ArchFunType arch) Source #

If this block ends with a call, this has the type of the function called. Otherwise, the value should be Nothing.

biAssignMap :: BlockInvariants arch ids -> MapF (AssignId ids) (BlockInferValue arch ids) Source #

Maps assignment identifiers to the associated value.

If an assignment id aid is not in this map, then we assume it is equal to SAVEqualAssign aid

newtype LocList (r :: Type -> Type) (tp :: Type) Source #

Constructors

LL
Fields llValues :: [BoundLoc r tp]

Instances

Instances details

Semigroup (LocList r tp) Source #
Instance details Defined in Data.Macaw.Analysis.RegisterUse Methods (<>) :: LocList r tp -> LocList r tp -> LocList r tp # sconcat :: NonEmpty (LocList r tp) -> LocList r tp # stimes :: Integral b => b -> LocList r tp -> LocList r tp #

data LocMap (r :: Type -> Type) (v :: Type -> Type) Source #

A map from BoundLoc locations to values.

Constructors

LocMap
Fields locMapRegs :: !(MapF r v) locMapStack :: !(MemMap (MemInt (RegAddrWidth r)) v)

locMapToList :: forall (r :: Type -> Type) (v :: Type -> Type). LocMap r v -> [Pair (BoundLoc r) v] Source #

Construct a list out of a location map.

data BoundLoc (r :: Type -> Type) (tp :: Type) where Source #

A location within a function tracked by our bounds analysis algorithms.

Locations for these purposes are registers, stack offsets, and global memory offsets.

Constructors

RegLoc :: forall (r :: Type -> Type) (tp :: Type). !(r tp) -> BoundLoc r tp

RegLoc r denotes the register r.

StackOffLoc :: forall (r :: Type -> Type) (tp :: Type). !(MemInt (RegAddrWidth r)) -> !(MemRepr tp) -> BoundLoc r tp

StackkOffLoc o repr denotes the bytes from address range [initSP + o .. initSP + o + memReprBytes repr).

initSP denotes the stack offset at the start of function execution.

We should note that this makes no claim that those addresses are valid.

Instances

Instances details

TestEquality r => TestEquality (BoundLoc r :: Type -> Type) Source #
Instance details Defined in Data.Macaw.AbsDomain.StackAnalysis Methods testEquality :: forall (a :: Type) (b :: Type). BoundLoc r a -> BoundLoc r b -> Maybe (a :~: b) #
ShowF r => PrettyF (BoundLoc r :: Type -> Type) Source #
Instance details Defined in Data.Macaw.AbsDomain.StackAnalysis Methods prettyF :: forall (tp :: Type) ann. BoundLoc r tp -> Doc ann Source #
OrdF r => OrdF (BoundLoc r :: Type -> Type) Source #
Instance details Defined in Data.Macaw.AbsDomain.StackAnalysis Methods compareF :: forall (x :: Type) (y :: Type). BoundLoc r x -> BoundLoc r y -> OrderingF x y leqF :: forall (x :: Type) (y :: Type). BoundLoc r x -> BoundLoc r y -> Bool ltF :: forall (x :: Type) (y :: Type). BoundLoc r x -> BoundLoc r y -> Bool geqF :: forall (x :: Type) (y :: Type). BoundLoc r x -> BoundLoc r y -> Bool gtF :: forall (x :: Type) (y :: Type). BoundLoc r x -> BoundLoc r y -> Bool
ShowF r => ShowF (BoundLoc r :: Type -> Type) Source #
Instance details Defined in Data.Macaw.AbsDomain.StackAnalysis Methods withShow :: forall p q (tp :: Type) a. p (BoundLoc r) -> q tp -> (Show (BoundLoc r tp) => a) -> a showF :: forall (tp :: Type). BoundLoc r tp -> String showsPrecF :: forall (tp :: Type). Int -> BoundLoc r tp -> String -> String
HasRepr r TypeRepr => HasRepr (BoundLoc r :: Type -> Type) TypeRepr Source #
Instance details Defined in Data.Macaw.AbsDomain.StackAnalysis Methods typeRepr :: forall (tp :: Type). BoundLoc r tp -> TypeRepr tp Source #
ShowF r => Show (BoundLoc r tp) Source #
Instance details Defined in Data.Macaw.AbsDomain.StackAnalysis Methods showsPrec :: Int -> BoundLoc r tp -> ShowS # show :: BoundLoc r tp -> String # showList :: [BoundLoc r tp] -> ShowS #
TestEquality r => Eq (BoundLoc r tp) Source #
Instance details Defined in Data.Macaw.AbsDomain.StackAnalysis Methods (==) :: BoundLoc r tp -> BoundLoc r tp -> Bool # (/=) :: BoundLoc r tp -> BoundLoc r tp -> Bool #
ShowF r => Pretty (BoundLoc r tp) Source #
Instance details Defined in Data.Macaw.AbsDomain.StackAnalysis Methods pretty :: BoundLoc r tp -> Doc ann prettyList :: [BoundLoc r tp] -> Doc ann

data MemAccessInfo arch ids Source #

Information about a memory access within a block

Constructors

NotFrameAccess	The access was not inferred to affect the current frame
FrameReadInitAccess !(MemInt (ArchAddrWidth arch)) !(InitInferValue arch tp)	The access read a frame offset that has not been written to by the current block. The inferred value describes the value read.
FrameReadWriteAccess !StmtIndex	The access read a frame offset that has been written to by a previous write or cond-write in this block, and the instruction had the given index.
FrameReadOverlapAccess !(MemInt (ArchAddrWidth arch))	The access was a memory read that overlapped, but did not exactly match a previous write.
FrameWriteAccess !(MemInt (ArchAddrWidth arch))	The access was a write to the current frame.
FrameCondWriteAccess !(MemInt (ArchAddrWidth arch)) !(MemRepr tp) !(InferStackValue arch ids tp)	The access was a conditional write to the current frame at the given offset. The current
FrameCondWriteOverlapAccess !(MemInt (ArchAddrWidth arch))	The access was a conditional write to the current frame at the given offset, and the default value would overlap with a previous write.

data InitInferValue arch (tp :: Type) where Source #

This denotes specific value equalities that invariant inferrences associates with Macaw values.

Constructors

InferredStackOffset :: forall arch. !(MemInt (ArchAddrWidth arch)) -> InitInferValue arch ('BVType (ArchAddrWidth arch))

Denotes the value must be the given offset of the stack frame.

FnStartRegister :: forall arch (tp :: Type). !(ArchReg arch tp) -> InitInferValue arch tp

Denotes the value must be the value passed into the function at the given register.

RegEqualLoc :: forall arch (tp :: Type). !(BoundLoc (ArchReg arch) tp) -> InitInferValue arch tp

Denotes a value is equal to the value stored at the representative location when the block start.

Note. The location in this must a "representative" location. Representative locations are those locations chosen to represent equivalence classes of locations inferred equal by block inference.

Instances

Instances details

TestEquality (ArchReg arch) => TestEquality (InitInferValue arch :: Type -> Type) Source #
Instance details Defined in Data.Macaw.Analysis.RegisterUse Methods testEquality :: forall (a :: Type) (b :: Type). InitInferValue arch a -> InitInferValue arch b -> Maybe (a :~: b) #
OrdF (ArchReg arch) => OrdF (InitInferValue arch :: Type -> Type) Source #
Instance details Defined in Data.Macaw.Analysis.RegisterUse Methods compareF :: forall (x :: Type) (y :: Type). InitInferValue arch x -> InitInferValue arch y -> OrderingF x y leqF :: forall (x :: Type) (y :: Type). InitInferValue arch x -> InitInferValue arch y -> Bool ltF :: forall (x :: Type) (y :: Type). InitInferValue arch x -> InitInferValue arch y -> Bool geqF :: forall (x :: Type) (y :: Type). InitInferValue arch x -> InitInferValue arch y -> Bool gtF :: forall (x :: Type) (y :: Type). InitInferValue arch x -> InitInferValue arch y -> Bool
ShowF (ArchReg arch) => ShowF (InitInferValue arch :: Type -> Type) Source #
Instance details Defined in Data.Macaw.Analysis.RegisterUse Methods withShow :: forall p q (tp :: Type) a. p (InitInferValue arch) -> q tp -> (Show (InitInferValue arch tp) => a) -> a showF :: forall (tp :: Type). InitInferValue arch tp -> String showsPrecF :: forall (tp :: Type). Int -> InitInferValue arch tp -> String -> String
ShowF (ArchReg arch) => Show (InitInferValue arch tp) Source #
Instance details Defined in Data.Macaw.Analysis.RegisterUse Methods showsPrec :: Int -> InitInferValue arch tp -> ShowS # show :: InitInferValue arch tp -> String # showList :: [InitInferValue arch tp] -> ShowS #

Mem Access info

type StmtIndex = Int Source #

Index of a stmt in a block.

Use information

biAssignIdUsed :: forall ids (tp :: Type) arch. AssignId ids tp -> BlockInvariants arch ids -> Bool Source #

Return true if assignment is needed to execute block.

biWriteUsed :: StmtIndex -> BlockInvariants arch ids -> Bool Source #

Return true if index corresponds to a write of the current stack frame.